[gtk+/filesystemmodel: 6/28] speed up node index computation by only doing it on demand

[Benjamin Otte <otte src gnome org>]

commit 45cb31233fedf786534c1dd2774951dd26f396ba
Author: Benjamin Otte <otte gnome org>
Date:   Thu Jun 18 19:56:50 2009 +0200

    speed up node index computation by only doing it on demand

 gtk/gtkfilesystemmodel.c |  112 +++++++++++++++++++++++++++++++---------------
 1 files changed, 75 insertions(+), 37 deletions(-)
---
diff --git a/gtk/gtkfilesystemmodel.c b/gtk/gtkfilesystemmodel.c
index c8bee02..a9a88fa 100644
--- a/gtk/gtkfilesystemmodel.c
+++ b/gtk/gtkfilesystemmodel.c
@@ -50,7 +50,7 @@ struct _FileModelNode
   GFile *               file;           /* file represented by this node or NULL for editable */
   GFileInfo *           info;           /* info for this file or NULL if unknown */
 
-  guint                 index;          /* index in path - aka visible nodes before this one */
+  guint                 index;          /* if valid, index in path - aka visible nodes before this one */
 
   guint                 visible :1;     /* if the file is currently visible */
   guint                 values_set :1;  /* true if the set function has been called on this node */
@@ -68,6 +68,7 @@ struct _GtkFileSystemModel
 
   GCancellable *        cancellable;    /* cancellable in use for all operations - cancelled on dispose */
   GArray *              files;          /* array of FileModelNode containing all our files */
+  guint                 n_indexes_valid;/* count of valid indexes */
 
   guint                 n_columns;      /* number of columns */
   GType *               column_types;   /* types of each column */
@@ -115,14 +116,53 @@ struct _GtkFileSystemModelClass
 #define NODE_SIZE(_model) (sizeof (FileModelNode) + sizeof (GValue) * (MAX ((model)->n_columns, 1) - 1))
 #define get_node(_model, _index) ((FileModelNode *) (((guint8 *) (_model)->files->data) + (_index) * NODE_SIZE (_model)))
 
+static void
+node_validate_indexes (GtkFileSystemModel *model, guint min_index, guint min_visible)
+{
+  guint validate, current;
+
+  if (model->files->len == 0)
+    return;
+  min_index = MIN (min_index, model->files->len - 1);
+  validate = model->n_indexes_valid;
+  if (validate)
+    current = get_node (model, validate - 1)->index;
+  else
+    current = 0;
+  while (validate <= min_index && current <= min_visible)
+    {
+      FileModelNode *node = get_node (model, validate);
+      if (node->visible)
+        current++;
+      node->index = current;
+      validate++;
+    }
+  model->n_indexes_valid = validate;
+}
+
+static guint
+node_get_index (GtkFileSystemModel *model, guint id)
+{
+  if (model->n_indexes_valid <= id)
+    node_validate_indexes (model, id, G_MAXUINT);
+
+  return get_node (model, id)->index - 1;
+}
+
+static void 
+node_invalidate_index (GtkFileSystemModel *model, guint id)
+{
+  model->n_indexes_valid = MIN (model->n_indexes_valid, id);
+}
+
 static GtkTreePath *
 gtk_tree_path_new_from_node (GtkFileSystemModel *model, guint id)
 {
-  FileModelNode *node = get_node (model, id);
+  guint i = node_get_index (model, id);
 
-  g_assert (node->index < model->files->len);
+  g_assert (i < model->files->len);
 
-  return gtk_tree_path_new_from_indices (node->index, -1);
+  return gtk_tree_path_new_from_indices (i, -1);
 }
 
 static void
@@ -143,16 +183,14 @@ node_set_visible (GtkFileSystemModel *model, guint id, gboolean visible)
   FileModelNode *node = get_node (model, id);
   GtkTreePath *path;
   GtkTreeIter iter;
-  guint i;
 
   if (node->visible == visible)
     return;
 
-  node->visible = visible;
   if (visible)
     {
-      for (i = id; i < model->files->len; i++)
-        get_node (model, i)->index++;
+      node->visible = TRUE;
+      node_invalidate_index (model, id);
       path = gtk_tree_path_new_from_node (model, id);
       ITER_INIT_FROM_INDEX (model, &iter, id);
       gtk_tree_model_row_inserted (GTK_TREE_MODEL (model), path, &iter);
@@ -161,20 +199,11 @@ node_set_visible (GtkFileSystemModel *model, guint id, gboolean visible)
   else
     {
       path = gtk_tree_path_new_from_node (model, id);
-      for (i = id; i < model->files->len; i++)
-        get_node (model, i)->index--;
+      node->visible = FALSE;
+      node_invalidate_index (model, id);
       gtk_tree_model_row_deleted (GTK_TREE_MODEL (model), path);
       gtk_tree_path_free (path);
     }
-
-  id = -1;
-  for (i = 0; i < model->files->len; i++)
-    {
-      node = get_node (model, i);
-      if (node->visible)
-        id++;
-      g_assert (node->index == id);
-    }
 }
 
 static gboolean
@@ -249,24 +278,38 @@ gtk_file_system_model_iter_nth_child (GtkTreeModel *tree_model,
 {
   GtkFileSystemModel *model = GTK_FILE_SYSTEM_MODEL (tree_model);
   char *node;
-  guint id;
+  guint id, find;
 
   g_return_val_if_fail (n >= 0, FALSE);
 
-  if (parent != NULL || (guint) n > get_node (model, model->files->len - 1)->index)
+  if (parent != NULL)
     return FALSE;
 
-  node = bsearch (GUINT_TO_POINTER ((guint) n), 
-                  model->files->data,
-                  model->files->len,
-                  NODE_SIZE (model),
-                  compare_indices);
-  if (node == NULL)
-    return FALSE;
+  find = n + 1;
 
-  id = (node - model->files->data) / NODE_SIZE (model);
-  while (!get_node (model, id)->visible)
-    id--;
+  if (model->n_indexes_valid > 0 &&
+      get_node (model, model->n_indexes_valid - 1)->index >= find)
+    {
+      /* fast path */
+      node = bsearch (GUINT_TO_POINTER (find), 
+                      model->files->data,
+                      model->n_indexes_valid,
+                      NODE_SIZE (model),
+                      compare_indices);
+      if (node == NULL)
+        return FALSE;
+
+      id = (node - model->files->data) / NODE_SIZE (model);
+      while (!get_node (model, id)->visible)
+        id--;
+    }
+  else
+    {
+      node_validate_indexes (model, G_MAXUINT, n);
+      id = model->n_indexes_valid - 1;
+      if (model->n_indexes_valid == 0 || get_node (model, id)->index != find)
+        return FALSE;
+    }
 
   ITER_INIT_FROM_INDEX (model, iter, id);
   return TRUE;
@@ -365,7 +408,7 @@ gtk_file_system_model_iter_n_children (GtkTreeModel *tree_model,
   if (iter)
     return 0;
 
-  return get_node (model, model->files->len - 1)->index + 1;
+  return node_get_index (model, model->files->len - 1) + 1;
 }
 
 static gboolean
@@ -537,11 +580,6 @@ gtk_file_system_model_add_node (GtkFileSystemModel *model, GFile *file, GFileInf
   node->file = file;
   node->info = info;
 
-  if (model->files->len > 0)
-    node->index = get_node (model, model->files->len - 1)->index;
-  else
-    node->index = -1;
-
   for (i = 0; i < model->n_columns; i++)
     {
       g_value_init (&node->values[i], model->column_types[i]);