From 40f3d279fc7868e92d75f54fc3ac2d83f0bb6c00 Mon Sep 17 00:00:00 2001 From: Christoph Fritz Date: Mon, 8 Mar 2021 13:54:39 +0100 Subject: 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 | 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 --- shell/ev-sidebar-links.c | 139 +++++++++++++++++++++++++++-------------------- 1 file changed, 80 insertions(+), 59 deletions(-) (limited to 'shell') 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"); } -- cgit v1.2.1