summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorChristoph Fritz <[email protected]>2021-03-08 13:54:39 +0100
committerraveit65 <[email protected]>2021-06-15 20:10:04 +0200
commit50d0b23c608020dd1da3fb3e13883941182ec89e (patch)
treeb4e92acb4becea0bd83c41eed2af0ee217fb3ad2
parentae1c8e7e9e881022bbad8da68b3efcee10268ed0 (diff)
downloadatril-50d0b23c608020dd1da3fb3e13883941182ec89e.tar.bz2
atril-50d0b23c608020dd1da3fb3e13883941182ec89e.tar.xz
ev-sidebar-links: Optimize reverse link lookup for a page
Commit adapted for atril, picked up from: https://gitlab.gnome.org/GNOME/evince/-/commit/c3de8e75d6d0920478af210ba19a2d94b0734917 Credits to Benjamin Berg <[email protected]> | For large documents the linear search for the first link that is on a | certain page is really slow. Because of this scrolling becomes slow | whenever the page changes. | | Replace the linear search with a search in a binary tree populated with | the first link on each page and the corresponding GtkTreePath. This way | a specialized binary tree lookup can be used to find the closest | matching link and select that in the treeview. | | https://bugzilla.gnome.org/show_bug.cgi?id=779614
Diffstat
-rw-r--r--shell/ev-sidebar-links.c139
1 files changed, 80 insertions, 59 deletions
diff --git a/shell/ev-sidebar-links.c b/shell/ev-sidebar-links.c
index 92caa959..7acbff7c 100644
--- a/shell/ev-sidebar-links.c
+++ b/shell/ev-sidebar-links.c
@@ -47,6 +47,8 @@ struct _EvSidebarLinksPrivate {
GtkTreeModel *model;
EvDocument *document;
EvDocumentModel *doc_model;
+
+ GTree *page_link_tree;
};
enum {
@@ -149,6 +151,11 @@ ev_sidebar_links_dispose (GObject *object)
sidebar->priv->model = NULL;
}
+ if (sidebar->priv->page_link_tree) {
+ g_tree_unref (sidebar->priv->page_link_tree);
+ sidebar->priv->page_link_tree = NULL;
+ }
+
if (sidebar->priv->document) {
g_object_unref (sidebar->priv->document);
sidebar->priv->document = NULL;
@@ -461,40 +468,19 @@ ev_sidebar_links_new (void)
return ev_sidebar_links;
}
-static gboolean
-update_page_callback_foreach (GtkTreeModel *model,
- GtkTreePath *path,
- GtkTreeIter *iter,
- gpointer data)
-{
- EvSidebarLinks *sidebar_links = (data);
- EvLink *link;
-
- gtk_tree_model_get (model, iter,
- EV_DOCUMENT_LINKS_COLUMN_LINK, &link,
- -1);
-
- if (link) {
- int current_page;
- int dest_page;
- EvDocumentLinks *document_links = EV_DOCUMENT_LINKS (sidebar_links->priv->document);
-
- dest_page = ev_document_links_get_link_page (document_links, link);
- g_object_unref (link);
-
- current_page = ev_document_model_get_page (sidebar_links->priv->doc_model);
-
- if (dest_page == current_page) {
- gtk_tree_view_expand_to_path (GTK_TREE_VIEW (sidebar_links->priv->tree_view),
- path);
- gtk_tree_view_set_cursor (GTK_TREE_VIEW (sidebar_links->priv->tree_view),
- path, NULL, FALSE);
+typedef struct EvSidebarLinkPageSearch {
+ gint page;
+ gint best_existing;
+} EvSidebarLinkPageSearch;
- return TRUE;
- }
- }
+static gint
+page_link_tree_search_best_page (gpointer page_ptr, EvSidebarLinkPageSearch* data)
+{
+ gint page = GPOINTER_TO_INT (page_ptr);
+ if (page <= data->page && page > data->best_existing)
+ data->best_existing = page;
- return FALSE;
+ return data->page - page;
}
static void
@@ -502,44 +488,34 @@ ev_sidebar_links_set_current_page (EvSidebarLinks *sidebar_links,
gint current_page)
{
GtkTreeSelection *selection;
- GtkTreeModel *model;
- GtkTreeIter iter;
+ GtkTreePath *path;
+ EvSidebarLinkPageSearch search_data;
/* Widget is not currently visible */
- if (!gtk_widget_get_mapped (GTK_WIDGET (sidebar_links)))
+ if (!gtk_widget_is_visible (GTK_WIDGET (sidebar_links)))
return;
- selection = gtk_tree_view_get_selection (GTK_TREE_VIEW (sidebar_links->priv->tree_view));
-
- if (gtk_tree_selection_get_selected (selection, &model, &iter)) {
- EvLink *link;
+ search_data.page = current_page;
+ search_data.best_existing = G_MININT;
- gtk_tree_model_get (model, &iter,
- EV_DOCUMENT_LINKS_COLUMN_LINK, &link,
- -1);
- if (link) {
- gint dest_page;
- EvDocumentLinks *document_links = EV_DOCUMENT_LINKS (sidebar_links->priv->document);
+ path = g_tree_search (sidebar_links->priv->page_link_tree, (GCompareFunc) page_link_tree_search_best_page, &search_data);
+ /* No direct hit, try a lookup on the best match. */
+ if (!path)
+ path = g_tree_lookup (sidebar_links->priv->page_link_tree, GINT_TO_POINTER (search_data.best_existing));
- dest_page = ev_document_links_get_link_page (document_links, link);
- g_object_unref (link);
+ /* Still no hit, give up. */
+ if (!path)
+ return;
- if (dest_page == current_page)
- return;
- }
- }
+ selection = gtk_tree_view_get_selection (GTK_TREE_VIEW (sidebar_links->priv->tree_view));
- /* We go through the tree linearly looking for the first page that
- * matches. This is pretty inefficient. We can do something neat with
- * a GtkTreeModelSort here to make it faster, if it turns out to be
- * slow.
- */
g_signal_handler_block (selection, sidebar_links->priv->selection_id);
g_signal_handler_block (sidebar_links->priv->tree_view, sidebar_links->priv->row_activated_id);
- gtk_tree_model_foreach (model,
- update_page_callback_foreach,
- sidebar_links);
+ gtk_tree_view_expand_to_path (GTK_TREE_VIEW (sidebar_links->priv->tree_view),
+ path);
+ gtk_tree_view_set_cursor (GTK_TREE_VIEW (sidebar_links->priv->tree_view),
+ path, NULL, FALSE);
g_signal_handler_unblock (selection, sidebar_links->priv->selection_id);
g_signal_handler_unblock (sidebar_links->priv->tree_view, sidebar_links->priv->row_activated_id);
@@ -590,6 +566,42 @@ expand_open_links (GtkTreeView *tree_view, GtkTreeModel *model, GtkTreeIter *par
}
}
+
+static gint
+page_link_tree_sort (gconstpointer a, gconstpointer b, void *data)
+{
+ return GPOINTER_TO_INT (a) - GPOINTER_TO_INT (b);
+}
+
+static gboolean
+update_page_link_tree_foreach (GtkTreeModel *model,
+ GtkTreePath *path,
+ GtkTreeIter *iter,
+ gpointer data)
+{
+ EvSidebarLinks *sidebar_links = data;
+ EvSidebarLinksPrivate *priv = sidebar_links->priv;
+ EvDocumentLinks *document_links = EV_DOCUMENT_LINKS (priv->document);
+ EvLink *link;
+ int page;
+
+ gtk_tree_model_get (model, iter,
+ EV_DOCUMENT_LINKS_COLUMN_LINK, &link,
+ -1);
+
+ if (!link)
+ return FALSE;
+
+ page = ev_document_links_get_link_page (document_links, link);
+ g_object_unref (link);
+
+ /* Only save the first link we find per page. */
+ if (!g_tree_lookup (priv->page_link_tree, GINT_TO_POINTER (page)))
+ g_tree_insert (priv->page_link_tree, GINT_TO_POINTER (page), gtk_tree_path_copy (path));
+
+ return FALSE;
+}
+
static void
ev_sidebar_links_set_links_model (EvSidebarLinks *sidebar_links,
GtkTreeModel *model)
@@ -603,6 +615,15 @@ ev_sidebar_links_set_links_model (EvSidebarLinks *sidebar_links,
g_object_unref (priv->model);
priv->model = g_object_ref (model);
+ /* Rebuild the binary search tree for finding links on pages. */
+ if (priv->page_link_tree)
+ g_tree_unref (priv->page_link_tree);
+ priv->page_link_tree = g_tree_new_full (page_link_tree_sort, NULL, NULL, (GDestroyNotify) gtk_tree_path_free);
+
+ gtk_tree_model_foreach (model,
+ update_page_link_tree_foreach,
+ sidebar_links);
+
g_object_notify (G_OBJECT (sidebar_links), "model");
}
generated by cgit v1.2.1 (git 2.18.0) at 2024-04-20 04:17:14 +0000