From f4199d79aabc830a6747ff8237ce9766002da0ae Mon Sep 17 00:00:00 2001
From: Marco Pesenti Gritti <marco@it.gnome.org>
Date: Sun, 6 Jul 2003 19:26:24 +0000
Subject: 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.
---
lib/egg/eggtreemodelfilter.c | 349 ++++++++++++++++++++++++++-----------------
1 file changed, 213 insertions(+), 136 deletions(-)
(limited to 'lib/egg')
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;
}
--
cgit