listbox: Optimize for sequential accessgbsneto/optimize-listbox

GSequence always iterates from 0 to log(N) when retrieving
the Nth element. That means writing a for-loop like this:

  for (i = 0; i < N; i++)
    row = gtk_list_box_get_row_at_index (listbox, i);

is accidentally O(n * log n). Ooops - this should be linear!

Bring the GListStore optimization for sequential access.

2 files changed, 76 insertions, 2 deletions

diff --git a/gtk/gtklistbox.c b/gtk/gtklistbox.c
index 8e2c5409ea..c75950a3f3 100644
--- a/gtk/gtklistbox.c
+++ b/gtk/gtklistbox.c
@@ -96,6 +96,10 @@ struct _GtkListBox
   GSequence *children;
   GHashTable *header_hash;
 
+  gint last_position;
+  GSequenceIter *last_iter;
+  gboolean last_position_valid;
+
   GtkWidget *placeholder;
 
   GtkListBoxSortFunc sort_func;
@@ -329,6 +333,13 @@ static guint row_signals[ROW__LAST_SIGNAL] = { 0 };
 static GtkBuildableIface *parent_row_buildable_iface;
 
 static void
+invalidate_cached_iter (GtkListBox *box)
+{
+  box->last_position = 0;
+  box->last_position_valid = FALSE;
+}
+
+static void
 gtk_list_box_row_buildable_add_child (GtkBuildable *buildable,
                                       GtkBuilder   *builder,
                                       GObject      *child,
@@ -690,6 +701,8 @@ gtk_list_box_init (GtkListBox *box)
 
   gtk_widget_set_focusable (GTK_WIDGET (box), TRUE);
 
+  invalidate_cached_iter (box);
+
   box->selection_mode = GTK_SELECTION_SINGLE;
   box->activate_single_click = TRUE;
 
@@ -751,11 +764,27 @@ GtkListBoxRow *
 gtk_list_box_get_row_at_index (GtkListBox *box,
                                gint        index_)
 {
-  GSequenceIter *iter;
+  GSequenceIter *iter = NULL;
 
   g_return_val_if_fail (GTK_IS_LIST_BOX (box), NULL);
 
-  iter = g_sequence_get_iter_at_pos (box->children, index_);
+  if (box->last_position_valid)
+    {
+      if (index_ < G_MAXINT && box->last_position == index_ + 1)
+        iter = g_sequence_iter_prev (box->last_iter);
+      else if (index_ > 0 && box->last_position == index_ - 1)
+        iter = g_sequence_iter_next (box->last_iter);
+      else if (box->last_position == index_)
+        iter = box->last_iter;
+    }
+
+  if (iter == NULL)
+    iter = g_sequence_get_iter_at_pos (box->children, index_);
+
+  box->last_iter = iter;
+  box->last_position = index_;
+  box->last_position_valid = TRUE;
+
   if (!g_sequence_iter_is_end (iter))
     return g_sequence_get (iter);
 
@@ -1243,6 +1272,7 @@ gtk_list_box_invalidate_filter (GtkListBox *box)
 {
   g_return_if_fail (GTK_IS_LIST_BOX (box));
 
+  invalidate_cached_iter (box);
   gtk_list_box_apply_filter_all (box);
   gtk_list_box_invalidate_headers (box);
   gtk_widget_queue_resize (GTK_WIDGET (box));
@@ -1295,6 +1325,8 @@ gtk_list_box_invalidate_sort (GtkListBox *box)
   if (box->sort_func == NULL)
     return;
 
+  invalidate_cached_iter (box);
+
   g_sequence_sort (box->children, (GCompareDataFunc)do_sort, box);
   g_sequence_foreach (box->children, gtk_list_box_css_node_foreach, &previous);
 
@@ -2310,6 +2342,8 @@ gtk_list_box_remove (GtkListBox   *box,
       return;
     }
 
+  invalidate_cached_iter (box);
+
   row = GTK_LIST_BOX_ROW (child);
   iter = ROW_PRIV (row)->iter;
   if (g_sequence_iter_get_sequence (iter) != box->children)
@@ -2633,6 +2667,8 @@ gtk_list_box_insert (GtkListBox *box,
       iter = g_sequence_insert_before (current_iter, row);
     }
 
+  invalidate_cached_iter (box);
+
   ROW_PRIV (row)->iter = iter;
   prev = g_sequence_iter_prev (iter);
   gtk_widget_insert_after (GTK_WIDGET (row), GTK_WIDGET (box),
diff --git a/testsuite/gtk/listbox.c b/testsuite/gtk/listbox.c
index 88b24108eb..1fe1dacf6d 100644
--- a/testsuite/gtk/listbox.c
+++ b/testsuite/gtk/listbox.c
@@ -440,6 +440,43 @@ test_header (void)
   g_object_unref (list);
 }
 
+static void
+test_sequencial_access (void)
+{
+  GtkListBox *list;
+  GtkWidget *label;
+  GtkWidget *rows[1000];
+  GtkWidget *row;
+  gchar *s;
+  gint i;
+
+  list = GTK_LIST_BOX (gtk_list_box_new ());
+  g_object_ref_sink (list);
+  gtk_widget_show (GTK_WIDGET (list));
+
+  for (i = 0; i < 1000; i++)
+    {
+      row = gtk_list_box_row_new ();
+      s = g_strdup_printf ("%d", i);
+      label = gtk_label_new (s);
+      gtk_list_box_row_set_child (GTK_LIST_BOX_ROW (row), label);
+
+      gtk_list_box_insert (GTK_LIST_BOX (list), row, -1);
+      rows[i] = row;
+    }
+
+  for (i = 0; i < 1000; i++)
+    {
+      row = (GtkWidget *) gtk_list_box_get_row_at_index (list, i);
+      g_assert_true (row == rows[i]);
+    }
+
+  row = (GtkWidget *) gtk_list_box_get_row_at_index (list, 1001);
+  g_assert_null (row);
+
+  g_object_unref (list);
+}
+
 int
 main (int argc, char *argv[])
 {
@@ -450,6 +487,7 @@ main (int argc, char *argv[])
   g_test_add_func ("/listbox/multi-selection", test_multi_selection);
   g_test_add_func ("/listbox/filter", test_filter);
   g_test_add_func ("/listbox/header", test_header);
+  g_test_add_func ("/listbox/sequencial-access", test_sequencial_access);
 
   return g_test_run ();
 }