From e010cd242c577fa4da3b05f67728dcbbe1781cb3 Mon Sep 17 00:00:00 2001
From: Benjamin Otte <otte@redhat.com>
Date: Sat, 15 Apr 2023 05:24:29 +0200
Subject: [PATCH] listlistmodel: Add a cache

Cache the last looked up item and use it for looking up the next item if
it's closest. This massively speeds up iteration over the model, because
each call to get_item() will be adjacent to the previous one.

Improves performance of the inspector quite a bit.
---
 gtk/gtklistlistmodel.c | 64 ++++++++++++++++++++++++++++++++++++------
 1 file changed, 56 insertions(+), 8 deletions(-)

diff --git a/gtk/gtklistlistmodel.c b/gtk/gtklistlistmodel.c
index 9644b896c5..a35493b03b 100644
--- a/gtk/gtklistlistmodel.c
+++ b/gtk/gtklistlistmodel.c
@@ -41,6 +41,9 @@ struct _GtkListListModel
   gpointer (* get_item) (gpointer, gpointer);
   gpointer data;
   GDestroyNotify notify;
+
+  guint cache_pos;
+  gpointer cache_item;
 };
 
 struct _GtkListListModelClass
@@ -72,6 +75,18 @@ gtk_list_list_model_get_n_items (GListModel *list)
   return self->n_items;
 }
 
+static gboolean
+gtk_list_list_model_cache_is_valid (GtkListListModel *self)
+{
+  return self->cache_item != NULL;
+}
+
+static void
+gtk_list_list_model_invalidate_cache (GtkListListModel *self)
+{
+  self->cache_item = NULL;
+}
+
 static gpointer
 gtk_list_list_model_get_item (GListModel *list,
                               guint       position)
@@ -79,31 +94,50 @@ gtk_list_list_model_get_item (GListModel *list,
   GtkListListModel *self = GTK_LIST_LIST_MODEL (list);
   gpointer result;
   guint i;
+  guint start, end;
 
   if (position >= self->n_items)
+    return NULL;
+
+  start = 0;
+  end = self->n_items;
+  if (gtk_list_list_model_cache_is_valid (self))
     {
-      return NULL;
+      if (self->cache_pos <= position)
+        start = self->cache_pos;
+      else
+        end = self->cache_pos;
     }
-  else if (self->get_last &&
-           position >= self->n_items / 2)
+
+  if (self->get_last &&
+      position > (start + end) / 2)
     {
-      result = self->get_last (self->data);
+      if (end == self->cache_pos && gtk_list_list_model_cache_is_valid (self))
+        result = self->get_previous (self->cache_item, self->data);
+      else
+        result = self->get_last (self->data);
 
-      for (i = self->n_items - 1; i > position; i--)
+      for (i = end - 1; i > position; i--)
         {
           result = self->get_previous (result, self->data);
         }
     }
   else
     {
-      result = self->get_first (self->data);
+      if (start == self->cache_pos && gtk_list_list_model_cache_is_valid (self))
+        result = self->cache_item;
+      else
+        result = self->get_first (self->data);
 
-      for (i = 0; i < position; i++)
+      for (i = start; i < position; i++)
         {
           result = self->get_next (result, self->data);
         }
     }
 
+  self->cache_item = result;
+  self->cache_pos = position;
+
   return self->get_item (result, self->data);
 }
 
@@ -275,7 +309,9 @@ gtk_list_list_model_item_added_at (GtkListListModel *self,
   g_return_if_fail (GTK_IS_LIST_LIST_MODEL (self));
   g_return_if_fail (position <= self->n_items);
 
-  self->n_items += 1;
+  self->n_items++;
+  if (position <= self->cache_pos)
+    self->cache_pos++;
 
   g_list_model_items_changed (G_LIST_MODEL (self), position, 0, 1);
   g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_N_ITEMS]);
@@ -327,6 +363,12 @@ gtk_list_list_model_item_moved (GtkListListModel *self,
 
   min = MIN (position, previous_position);
   max = MAX (position, previous_position) + 1;
+
+  if (self->cache_item == item)
+    self->cache_pos = position;
+  else if (self->cache_pos >= min && self->cache_pos < max)
+    self->cache_pos += (self->cache_pos > position ? 1 : -1);
+
   g_list_model_items_changed (G_LIST_MODEL (self), min, max - min, max - min);
 }
 
@@ -338,6 +380,10 @@ gtk_list_list_model_item_removed_at (GtkListListModel *self,
   g_return_if_fail (position < self->n_items);
 
   self->n_items -= 1;
+  if (position == self->cache_pos)
+    gtk_list_list_model_invalidate_cache (self);
+  else if (position < self->cache_pos)
+    self->cache_pos--;
 
   g_list_model_items_changed (G_LIST_MODEL (self), position, 1, 0);
   g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_N_ITEMS]);
@@ -358,6 +404,8 @@ gtk_list_list_model_clear (GtkListListModel *self)
   self->n_items = 0;
   self->notify = NULL;
 
+  gtk_list_list_model_invalidate_cache (self);
+
   if (n_items > 0)
     {
       g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, 0);
-- 
2.30.2