[libdazzle] list-store: directly access GSequence from GtkListStore

[Christian Hergert <chergert src gnome org>]

commit a20677accf9651d9cb4b1a2f5d30c29a4ec7895e
Author: Christian Hergert <chergert redhat com>
Date:   Tue Jul 4 23:34:07 2017 -0700

    list-store: directly access GSequence from GtkListStore
    
    With knowledge of the GtkListStore implementation, we can
    directly access the GSequenceIter in GtkTreeIter.user_data.
    Doing so allows us to avoid traversing the GSequence treap
    multiple times while inserting a value.
    
    This is not guaranteed to do inserts exactly as a binary
    search, as the GSequence approximates the mid-point based
    on the sequence hierarchy.

 src/util/dzl-gtk.c      |  112 ++++++++++++++++++++++++++++++++++-------------
 tests/meson.build       |    6 +++
 tests/test-list-store.c |   68 ++++++++++++++++++++++++++++
 3 files changed, 155 insertions(+), 31 deletions(-)
---
diff --git a/src/util/dzl-gtk.c b/src/util/dzl-gtk.c
index 87c6fce..91d2b78 100644
--- a/src/util/dzl-gtk.c
+++ b/src/util/dzl-gtk.c
@@ -444,6 +444,42 @@ dzl_gtk_widget_mux_action_groups (GtkWidget   *widget,
                           (GDestroyNotify) g_strfreev);
 }
 
+static gboolean
+list_store_iter_middle (GtkListStore      *store,
+                        const GtkTreeIter *begin,
+                        const GtkTreeIter *end,
+                        GtkTreeIter       *middle)
+{
+  g_assert (store != NULL);
+  g_assert (begin != NULL);
+  g_assert (end != NULL);
+  g_assert (middle != NULL);
+  g_assert (middle->stamp == begin->stamp);
+  g_assert (middle->stamp == end->stamp);
+
+  /*
+   * middle MUST ALREADY BE VALID as it saves us some copying
+   * as well as just makes things easier when binary searching.
+   */
+
+  middle->user_data = g_sequence_range_get_midpoint (begin->user_data, end->user_data);
+
+  if (g_sequence_iter_is_end (middle->user_data))
+    {
+      middle->stamp = 0;
+      return FALSE;
+    }
+
+  return TRUE;
+}
+
+static inline gboolean
+list_store_iter_equal (const GtkTreeIter *a,
+                       const GtkTreeIter *b)
+{
+  return a->user_data == b->user_data;
+}
+
 /**
  * dzl_gtk_list_store_insert_sorted:
  * @store: A #GtkListStore
@@ -459,9 +495,9 @@ dzl_gtk_widget_mux_action_groups (GtkWidget   *widget,
  * @compare_column must be the index of a column that is a %G_TYPE_POINTER,
  * %G_TYPE_BOXED or %G_TYPE_OBJECT based column.
  *
- * @compare_func will be called with the column data as the first
- * parameter and @key as the second parameter.  The final parameter will
- * be the @compare_data passed to this function.
+ * @compare_func will be called with @key as the first parameter and the
+ * value from the #GtkListStore row as the second parameter. The third and
+ * final parameter is @compare_data.
  *
  * Since: 3.26
  */
@@ -476,11 +512,12 @@ dzl_gtk_list_store_insert_sorted (GtkListStore     *store,
   GValue value = G_VALUE_INIT;
   gpointer (*get_func) (const GValue *) = NULL;
   GtkTreeModel *model = (GtkTreeModel *)store;
+  GtkTreeIter begin;
+  GtkTreeIter end;
+  GtkTreeIter middle;
+  guint n_children;
+  gint cmpval = 0;
   GType type;
-  gint left;
-  gint right;
-  gint middle;
-  gint cmpval;
 
   g_return_if_fail (GTK_IS_LIST_STORE (store));
   g_return_if_fail (GTK_IS_LIST_STORE (model));
@@ -504,40 +541,53 @@ dzl_gtk_list_store_insert_sorted (GtkListStore     *store,
       return;
     }
 
-  cmpval = 1;
-  left = 0;
-  middle = 0;
-  right = gtk_tree_model_iter_n_children (model, NULL) - 1;
-
-  /* Binary search to locate the target position */
-
-  while (left <= right)
+  /* Try to get the first iter instead of calling n_children to
+   * avoid walking the GSequence all the way to the right. If this
+   * matches, we know there are some children.
+   */
+  if (!gtk_tree_model_get_iter_first (model, &begin))
     {
-      GtkTreeIter cur;
-
-      middle = (left + right) / 2;
+      gtk_list_store_append (store, iter);
+      return;
+    }
 
-      gtk_tree_model_iter_nth_child (model, &cur, NULL, middle);
-      gtk_tree_model_get_value (model, &cur, compare_column, &value);
+  n_children = gtk_tree_model_iter_n_children (model, NULL);
+  if (!gtk_tree_model_iter_nth_child (model, &end, NULL, n_children - 1))
+    g_assert_not_reached ();
 
-      cmpval = compare_func (get_func (&value), key, compare_data);
+  middle = begin;
 
+  while (list_store_iter_middle (store, &begin, &end, &middle))
+    {
+      gtk_tree_model_get_value (model, &middle, compare_column, &value);
+      cmpval = compare_func (key, get_func (&value), compare_data);
       g_value_unset (&value);
 
+      if (cmpval == 0 || list_store_iter_equal (&begin, &end))
+        break;
+
       if (cmpval < 0)
-        left = middle + 1;
+        {
+          end = middle;
+
+          if (!list_store_iter_equal (&begin, &end) &&
+              !gtk_tree_model_iter_previous (model, &end))
+            break;
+        }
       else if (cmpval > 0)
-        right = middle - 1;
+        {
+          begin = middle;
+
+          if (!list_store_iter_equal (&begin, &end) &&
+              !gtk_tree_model_iter_next (model, &begin))
+            break;
+        }
       else
-        break;
+        g_assert_not_reached ();
     }
 
-  /*
-   * If we binary searched and middle was compared previous
-   * to our new position, advance one position.
-   */
   if (cmpval < 0)
-    middle++;
-
-  gtk_list_store_insert (store, iter, middle);
+    gtk_list_store_insert_before (store, iter, &middle);
+  else
+    gtk_list_store_insert_after (store, iter, &middle);
 }
diff --git a/tests/meson.build b/tests/meson.build
index db501d4..347c0a4 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -286,4 +286,10 @@ test_counters_window = executable('test-counters-window', 'test-counters-window.
   dependencies: libdazzle_deps + [libdazzle_dep],
 )
 
+test_list_store = executable('test-list-store', 'test-list-store.c',
+        c_args: test_cflags,
+     link_args: test_link_args,
+  dependencies: libdazzle_deps + [libdazzle_dep],
+)
+
 endif
diff --git a/tests/test-list-store.c b/tests/test-list-store.c
new file mode 100644
index 0000000..06ad64e
--- /dev/null
+++ b/tests/test-list-store.c
@@ -0,0 +1,68 @@
+#include <dazzle.h>
+#include <stdlib.h>
+
+static gint
+compare_direct (gconstpointer a,
+                gconstpointer b,
+                gpointer      data)
+{
+  if (a < b)
+    return -1;
+  else if (a > b)
+    return 1;
+  return 0;
+}
+
+#define assert_cmpptr(a,eq,b) \
+  G_STMT_START { \
+    if (!((a) eq (b))) { \
+      g_error (#a "(%p) " #eq " " #b "(%p)\n", (a), (b)); \
+    } \
+  } G_STMT_END
+
+static void
+test_insert_sorted (void)
+{
+  GtkListStore *store = gtk_list_store_new (1, G_TYPE_POINTER);
+  GtkTreeIter iter;
+  gboolean r;
+  gpointer last = NULL;
+  guint count = 0;
+
+  for (guint i = 0; i < 1000; i++)
+    {
+      gpointer value = GINT_TO_POINTER (rand ());
+
+      dzl_gtk_list_store_insert_sorted (store, &iter, value, 0, compare_direct, NULL);
+      gtk_list_store_set (store, &iter, 0, value, -1);
+    }
+
+  r = gtk_tree_model_get_iter_first (GTK_TREE_MODEL (store), &iter);
+  g_assert_cmpint (r, ==, TRUE);
+
+  do
+    {
+      gpointer value = NULL;
+
+      gtk_tree_model_get (GTK_TREE_MODEL (store), &iter, 0, &value, -1);
+      assert_cmpptr (value, >=, last);
+      last = value;
+
+      count++;
+    }
+  while (gtk_tree_model_iter_next (GTK_TREE_MODEL (store), &iter));
+
+  g_assert_cmpint (count, ==, 1000);
+
+  g_object_unref (store);
+}
+
+gint
+main (gint argc,
+      gchar *argv[])
+{
+  gtk_init (&argc, &argv);
+  g_test_init (&argc, &argv, NULL);
+  g_test_add_func ("/Dazzle/GtkListStore/insert_sorted", test_insert_sorted);
+  return g_test_run ();
+}