[evince/gnome-3-24] ev-sidebar-links: Optimize reverse link lookup for a page

[Carlos Garcia Campos <carlosgc src gnome org>]

commit d2cea51e6a49e7e151ad68e08f93a0b41b5c4af9
Author: Benjamin Berg <bberg redhat com>
Date:   Wed Apr 26 23:06:01 2017 +0200

    ev-sidebar-links: Optimize reverse link lookup for a page
    
    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 |  142 ++++++++++++++++++++++++++-------------------
 1 files changed, 82 insertions(+), 60 deletions(-)
---
diff --git a/shell/ev-sidebar-links.c b/shell/ev-sidebar-links.c
index 230a96a..c16e649 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 {
@@ -152,6 +154,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;
@@ -470,40 +477,20 @@ 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;
+typedef struct EvSidebarLinkPageSearch {
+       gint page;
+       gint best_existing;
+} EvSidebarLinkPageSearch;
 
-       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);
+static gint
+page_link_tree_search_best_page (gpointer page_ptr, EvSidebarLinkPageSearch* data)
+{
+       gint page = GPOINTER_TO_INT (page_ptr);
 
-               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);
-                       
-                       return TRUE;
-               }
-       }
+       if (page <= data->page && page > data->best_existing)
+               data->best_existing = page;
 
-       return FALSE;
+       return data->page - page;
 }
 
 static void
@@ -511,45 +498,35 @@ 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);
-                       
-                       if (dest_page == current_page)
-                               return;
-               }
-       }               
+       /* Still no hit, give up. */
+       if (!path)
+               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);
 }
@@ -599,6 +576,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)
@@ -612,6 +625,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");
 }