diff options
| -rw-r--r-- | ChangeLog | 6 | ||||
| -rw-r--r-- | lib/egg/eggtreemodelfilter.c | 349 |
2 files changed, 219 insertions, 136 deletions
@@ -1,3 +1,9 @@ +2003-07-06 Marco Pesenti Gritti <marco@it.gnome.org> + + * lib/egg/eggtreemodelfilter.c: + + Patch by kris to speed it up. + 2003-07-06 Christian Persch <chpe@cvs.gnome.org> * src/ephy-go-action.c: (button_clicked), (activate_cb), 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; } |