Patch by kris to speed it up.

2003-07-06  Marco Pesenti Gritti  <marco@it.gnome.org>

	* lib/egg/eggtreemodelfilter.c:

	Patch by kris to speed it up.

1 files changed, 213 insertions, 136 deletions

diff --git a/lib/egg/eggtreemodelfilter.c b/lib/egg/eggtreemodelfilter.c
index 89debc559..4358b94e9 100644
--- a/lib/egg/eggtreemodelfilter.c
+++ b/lib/egg/eggtreemodelfilter.c
@@ -182,15 +182,19 @@ static GtkTreePath *egg_real_tree_model_filter_convert_child_path_to_path (EggTr
                                                                            gboolean            build_levels,
                                                                            gboolean            fetch_childs);
 
-static gboolean     egg_tree_model_filter_fetch_child         (EggTreeModelFilter *filter,
+static FilterElt   *egg_tree_model_filter_fetch_child         (EggTreeModelFilter *filter,
 						               FilterLevel        *level,
-						               gint                offset);
+						               gint                offset,
+							       gint               *index);
 static void         egg_tree_model_filter_remove_node         (EggTreeModelFilter *filter,
 					                       GtkTreeIter        *iter,
 					                       gboolean            emit_signal);
 static void         egg_tree_model_filter_update_childs       (EggTreeModelFilter *filter,
 						               FilterLevel        *level,
 						               FilterElt          *elt);
+static FilterElt   *bsearch_elt_with_offset                   (GArray             *array,
+                                                               gint                offset,
+                                                               gint               *index);
 
 
 static GObjectClass *parent_class = NULL;
@@ -659,12 +663,14 @@ egg_tree_model_filter_clear_cache_helper (EggTreeModelFilter *filter,
     }
 }
 
-static gboolean
+static FilterElt *
 egg_tree_model_filter_fetch_child (EggTreeModelFilter *filter,
 				   FilterLevel        *level,
-				   gint                offset)
+				   gint                offset,
+                                   gint               *index)
 {
   gint i = 0;
+  gint start, middle, end;
   gint len;
   GtkTreePath *c_path = NULL;
   GtkTreeIter c_iter;
@@ -680,7 +686,7 @@ egg_tree_model_filter_fetch_child (EggTreeModelFilter *filter,
 					    level->parent_elt,
 					    filter->virtual_root);
       if (!c_parent_path)
-	return FALSE;
+	return NULL;
     }
   else
     {
@@ -712,7 +718,7 @@ egg_tree_model_filter_fetch_child (EggTreeModelFilter *filter,
   gtk_tree_path_free (c_path);
 
   if (offset >= len || !egg_tree_model_filter_visible (filter, &c_iter))
-    return FALSE;
+    return NULL;
 
   /* add child */
   elt.offset = offset;
@@ -725,21 +731,41 @@ egg_tree_model_filter_fetch_child (EggTreeModelFilter *filter,
   if (EGG_TREE_MODEL_FILTER_CACHE_CHILD_ITERS (filter))
     elt.iter = c_iter;
 
-  /* find index */
-  for (i = 0; i < level->array->len; i++)
-    if (g_array_index (level->array, FilterElt, i).offset > offset)
-      break;
+  /* find index (binary search on offset) */
+  start = 0;
+  end = level->array->len;
+
+  if (start != end)
+    {
+      while (start != end)
+        {
+          middle = (start + end) / 2;
+
+          if (g_array_index (level->array, FilterElt, middle).offset <= offset)
+            start = middle + 1;
+          else
+            end = middle;
+        }
+
+      if (g_array_index (level->array, FilterElt, middle).offset <= offset)
+        i = middle + 1;
+      else
+        i = middle;
+    }
+  else
+    i = 0;
 
   g_array_insert_val (level->array, i, elt);
+  *index = i;
 
-  for (i = 0; i < level->array->len; i++)
+  for (i = MAX (--i, 0); i < level->array->len; i++)
     {
       FilterElt *e = &(g_array_index (level->array, FilterElt, i));
       if (e->children)
 	e->children->parent_elt = e;
     }
 
-  return TRUE;
+  return &g_array_index (level->array, FilterElt, *index);
 }
 
 static void
@@ -799,21 +825,24 @@ egg_tree_model_filter_remove_node (EggTreeModelFilter *filter,
     }
   else
     {
-      /* remove the node */
-      for (i = 0; i < level->array->len; i++)
-        if (elt->offset == g_array_index (level->array, FilterElt, i).offset)
-          break;
+      FilterElt *tmp;
 
-      g_array_remove_index (level->array, i);
+      /* remove the node */
+      tmp = bsearch_elt_with_offset (level->array, elt->offset, &i);
 
-      for (i = 0; i < level->array->len; i++)
+      if (tmp)
         {
-          /* NOTE: here we do *not* decrease offsets, because the node was
-           * not removed from the child model
-           */
-          elt = &g_array_index (level->array, FilterElt, i);
-          if (elt->children)
-	    elt->children->parent_elt = elt;
+          g_array_remove_index (level->array, i);
+
+          for (i = MAX (--i, 0); i < level->array->len; i++)
+            {
+              /* NOTE: here we do *not* decrease offsets, because the node was
+               * not removed from the child model
+               */
+              elt = &g_array_index (level->array, FilterElt, i);
+              if (elt->children)
+	        elt->children->parent_elt = elt;
+            }
         }
     }
 
@@ -870,6 +899,56 @@ egg_tree_model_filter_update_childs (EggTreeModelFilter *filter,
     }
 }
 
+static FilterElt *
+bsearch_elt_with_offset (GArray *array,
+                         gint    offset,
+                         gint   *index)
+{
+  gint start, middle, end;
+  FilterElt *elt;
+
+  start = 0;
+  end = array->len;
+
+  if (array->len < 1)
+    return NULL;
+
+  if (start == end)
+    {
+      elt = &g_array_index (array, FilterElt, 0);
+
+      if (elt->offset == offset)
+        {
+          *index = 0;
+          return elt;
+        }
+      else
+        return NULL;
+    }
+
+  while (start != end)
+    {
+      middle = (start + end) / 2;
+
+      elt = &g_array_index (array, FilterElt, middle);
+
+      if (elt->offset < offset)
+        start = middle + 1;
+      else if (elt->offset > offset)
+        end = middle;
+      else
+        break;
+    }
+
+  if (elt->offset == offset)
+    {
+      *index = middle;
+      return elt;
+    }
+
+  return NULL;
+}
+
 /* TreeModel signals */
 static void
 egg_tree_model_filter_row_changed (GtkTreeModel *c_model,
@@ -879,14 +958,15 @@ egg_tree_model_filter_row_changed (GtkTreeModel *c_model,
 {
   EggTreeModelFilter *filter = EGG_TREE_MODEL_FILTER (data);
   GtkTreeIter iter;
+  GtkTreeIter childs;
   GtkTreeIter real_c_iter;
-  GtkTreePath *path;
+  GtkTreePath *path = NULL;
 
   FilterElt *elt;
   FilterLevel *level;
-  gint offset;
 
-  gboolean new;
+  gboolean requested_state;
+  gboolean current_state;
   gboolean free_c_path = FALSE;
 
   g_return_if_fail (c_path != NULL || c_iter != NULL);
@@ -902,21 +982,72 @@ egg_tree_model_filter_row_changed (GtkTreeModel *c_model,
   else
     gtk_tree_model_get_iter (c_model, &real_c_iter, c_path);
 
+  /* what's the requested state? */
+  requested_state = egg_tree_model_filter_visible (filter, &real_c_iter);
+
+  /* now, let's see whether the item is there */
+  path = egg_real_tree_model_filter_convert_child_path_to_path (filter,
+                                                                c_path,
+                                                                FALSE,
+                                                                FALSE);
+
+  if (path)
+    {
+      gtk_tree_model_get_iter (GTK_TREE_MODEL (filter), &iter, path);
+      current_state = FILTER_ELT (iter.user_data2)->visible;
+    }
+  else
+    current_state = FALSE;
+
+  if (current_state == FALSE && requested_state == FALSE)
+    /* no changes required */
+    goto done;
+
+  if (current_state == TRUE && requested_state == FALSE)
+    {
+      /* get rid of this node */
+      gtk_tree_model_get_iter (GTK_TREE_MODEL (filter), &iter, path);
+      egg_tree_model_filter_remove_node (filter, &iter, TRUE);
+
+      level = FILTER_LEVEL (iter.user_data);
+
+      if (!level->parent_level)
+        filter->root_level_visible--;
+
+      goto done;
+    }
+
+  if (current_state == TRUE && requested_state == TRUE)
+    {
+      /* progate the signal */
+      gtk_tree_model_get_iter (GTK_TREE_MODEL (filter), &iter, path);
+      gtk_tree_model_row_changed (GTK_TREE_MODEL (filter), path, &iter);
+
+      level = FILTER_LEVEL (iter.user_data);
+      elt = FILTER_ELT (iter.user_data2);
+
+      /* and update the childs */
+      if (gtk_tree_model_iter_children (c_model, &childs, &real_c_iter))
+        egg_tree_model_filter_update_childs (filter, level, elt);
+
+      goto done;
+    }
+
+  /* only current == FALSE and requested == TRUE is left,
+   * pull in the child
+   */
+  g_return_if_fail (current_state == FALSE && requested_state == TRUE);
+
+  /* make sure the new item has been pulled in */
   if (!filter->root)
     {
       gint i;
       FilterLevel *root;
 
-      /* build root level */
       egg_tree_model_filter_build_level (filter, NULL, NULL);
 
       root = FILTER_LEVEL (filter->root);
 
-      /* FIXME:
-       * we set the visibilities to FALSE here, so we ever emit
-       * a row_inserted. maybe it's even better to emit row_inserted
-       * here, not sure.
-       */
       if (root)
         {
           for (i = 0; i < root->array->len; i++)
@@ -925,63 +1056,35 @@ egg_tree_model_filter_row_changed (GtkTreeModel *c_model,
 	}
     }
 
-  path = egg_real_tree_model_filter_convert_child_path_to_path (filter,
-								c_path,
-								FALSE,
-								TRUE);
   if (!path)
-    goto done;
+    path = egg_real_tree_model_filter_convert_child_path_to_path (filter,
+								  c_path,
+								  FALSE,
+								  TRUE);
+
+  g_return_if_fail (path != NULL);
 
+  egg_tree_model_filter_increment_stamp (filter);
   gtk_tree_model_get_iter (GTK_TREE_MODEL (filter), &iter, path);
 
   level = FILTER_LEVEL (iter.user_data);
   elt = FILTER_ELT (iter.user_data2);
-  offset = elt->offset;
-  new = egg_tree_model_filter_visible (filter, c_iter);
 
-  if (elt->visible == TRUE && new == FALSE)
-    {
-      egg_tree_model_filter_remove_node (filter, &iter, TRUE);
+  elt->visible = TRUE;
 
-      if (!level->parent_level)
-	filter->root_level_visible--;
-    }
-  else if (elt->visible == FALSE && new == TRUE)
-    {
-      GtkTreeIter childs;
+  if (!level->parent_level)
+    filter->root_level_visible++;
 
-      elt->visible = TRUE;
+  /* update stamp */
+  gtk_tree_model_row_inserted (GTK_TREE_MODEL (filter), path, &iter);
 
-      egg_tree_model_filter_increment_stamp (filter);
-
-      if (!level->parent_level)
-	filter->root_level_visible++;
-
-      /* update stamp */
-      gtk_tree_model_get_iter (GTK_TREE_MODEL (filter), &iter, path);
-      gtk_tree_model_row_inserted (GTK_TREE_MODEL (filter), path, &iter);
-
-      if (gtk_tree_model_iter_children (c_model, &childs, c_iter))
-	egg_tree_model_filter_update_childs (filter, level, elt);
-    }
-  else if (elt->visible == FALSE && new == FALSE)
-    {
-      egg_tree_model_filter_remove_node (filter, &iter, FALSE);
-    }
-  else
-    {
-      GtkTreeIter childs;
-
-      gtk_tree_model_row_changed (GTK_TREE_MODEL (filter), path, &iter);
-
-      if (gtk_tree_model_iter_children (c_model, &childs, c_iter) &&
-	  elt->visible)
-	egg_tree_model_filter_update_childs (filter, level, elt);
-    }
-
-  gtk_tree_path_free (path);
+  if (gtk_tree_model_iter_children (c_model, &childs, c_iter))
+    egg_tree_model_filter_update_childs (filter, level, elt);
 
 done:
+  if (path)
+    gtk_tree_path_free (path);
+
   if (free_c_path)
     gtk_tree_path_free (c_path);
 }
@@ -1073,14 +1176,9 @@ egg_tree_model_filter_row_inserted (GtkTreeModel *c_model,
 	    /* we don't cover this signal */
 	    goto done;
 
-	  elt = NULL;
-	  for (j = 0; j < level->array->len; j++)
-	    if (g_array_index (level->array, FilterElt, j).offset ==
-		gtk_tree_path_get_indices (real_path)[i])
-	      {
-		elt = &g_array_index (level->array, FilterElt, j);
-		break;
-	      }
+          elt = bsearch_elt_with_offset (level->array,
+                                         gtk_tree_path_get_indices (real_path)[i],
+                                         &j);
 
 	  if (!elt)
 	    /* parent is probably being filtered out */
@@ -1332,14 +1430,10 @@ egg_tree_model_filter_row_deleted (GtkTreeModel *c_model,
 		      return;
 		    }
 
-		  elt = NULL;
-		  for (j = 0; j < level->array->len; j++)
-		    if (g_array_index (level->array, FilterElt, j).offset ==
-			gtk_tree_path_get_indices (real_path)[i])
-		      {
-			elt = &g_array_index (level->array, FilterElt, j);
-			break;
-		      }
+                  elt = bsearch_elt_with_offset (level->array,
+                                                 gtk_tree_path_get_indices (real_path)[i],
+                                                 &j);
+
 
 		  if (!elt || !elt->children)
 		    {
@@ -1414,15 +1508,15 @@ egg_tree_model_filter_row_deleted (GtkTreeModel *c_model,
     }
   else
     {
+      FilterElt *tmp;
+
       /* remove the row */
-      for (i = 0; i < level->array->len; i++)
-        if (elt->offset == g_array_index (level->array, FilterElt, i).offset)
-          break;
+      tmp = bsearch_elt_with_offset (level->array, elt->offset, &i);
 
-      offset = g_array_index (level->array, FilterElt, i).offset;
+      offset = tmp->offset;
       g_array_remove_index (level->array, i);
 
-      for (i = 0; i < level->array->len; i++)
+      for (i = MAX (--i, 0); i < level->array->len; i++)
         {
           elt = &g_array_index (level->array, FilterElt, i);
           if (elt->offset > offset)
@@ -2391,6 +2485,7 @@ egg_real_tree_model_filter_convert_child_path_to_path (EggTreeModelFilter *filte
   GtkTreePath *retval;
   GtkTreePath *real_path;
   FilterLevel *level;
+  FilterElt *tmp;
   gint i;
 
   g_return_val_if_fail (EGG_IS_TREE_MODEL_FILTER (filter), NULL);
@@ -2425,25 +2520,24 @@ egg_real_tree_model_filter_convert_child_path_to_path (EggTreeModelFilter *filte
           return NULL;
         }
 
-      for (j = 0; j < level->array->len; j++)
+      tmp = bsearch_elt_with_offset (level->array, child_indices[i], &j);
+      if (tmp)
         {
-          if ((g_array_index (level->array, FilterElt, j)).offset == child_indices[i])
-            {
-              gtk_tree_path_append_index (retval, j);
-              if (g_array_index (level->array, FilterElt, j).children == NULL && build_levels)
-                egg_tree_model_filter_build_level (filter,
-                                                   level,
-                                                   &g_array_index (level->array, FilterElt, j));
-              level = g_array_index (level->array, FilterElt, j).children;
-              found_child = TRUE;
-              break;
-            }
+          gtk_tree_path_append_index (retval, j);
+          if (!tmp->children && build_levels)
+            egg_tree_model_filter_build_level (filter, level, tmp);
+          level = tmp->children;
+          found_child = TRUE;
         }
 
       if (!found_child && fetch_childs)
         {
+          tmp = egg_tree_model_filter_fetch_child (filter, level,
+                                                   child_indices[i],
+                                                   &j);
+
           /* didn't find the child, let's try to bring it back */
-          if (!egg_tree_model_filter_fetch_child (filter, level, child_indices[i]))
+          if (!tmp || tmp->offset != child_indices[i])
             {
               /* not there */
               gtk_tree_path_free (real_path);
@@ -2451,29 +2545,11 @@ egg_real_tree_model_filter_convert_child_path_to_path (EggTreeModelFilter *filte
               return NULL;
             }
 
-          /* yay, let's search for the child again */
-          for (j = 0; j < level->array->len; j++)
-            {
-              if ((g_array_index (level->array, FilterElt, j)).offset == child_indices[i])
-                {
-                  gtk_tree_path_append_index (retval, j);
-                  if (g_array_index (level->array, FilterElt, j).children == NULL && build_levels)
-                    egg_tree_model_filter_build_level (filter,
-                                                       level,
-                                                       &g_array_index (level->array, FilterElt, j));
-                  level = g_array_index (level->array, FilterElt, j).children;
-                  found_child = TRUE;
-                  break;
-                }
-            }
-
-          if (!found_child)
-            {
-              /* our happy fun fetch attempt failed ?!?!?! no child! */
-              gtk_tree_path_free (real_path);
-              gtk_tree_path_free (retval);
-              return NULL;
-            }
+          gtk_tree_path_append_index (retval, j);
+          if (!tmp->children && build_levels)
+            egg_tree_model_filter_build_level (filter, level, tmp);
+          level = tmp->children;
+          found_child = TRUE;
         }
       else if (!found_child && !fetch_childs)
         {
@@ -2588,7 +2664,8 @@ egg_tree_model_filter_refilter_helper (GtkTreeModel *model,
                                        GtkTreeIter  *iter,
                                        gpointer      data)
 {
-  gtk_tree_model_row_changed (model, path, iter);
+  /* evil, don't try this at home, but certainly speeds things up */
+  egg_tree_model_filter_row_changed (model, path, iter, data);
 
   return FALSE;
 }