The attached patch reimplements GtkListStore in terms of a new data
structure, GtkSequence. This data structure has the API of a list, but
is internally implemented as a tree, making inserting into a sorted
GtkListStore O(log n) instead of O(n) as it is now.
For now the GtkSequence is internal API. I think it makes sense at
some point to add it to glib (as GSequence), but not until it has at
least tests and documentation, Also, actually porting GtkListStore to
use it uncovered a ton of small issues that needs to be considered.
A testprogram written by Matthias shows that the new data structure is
much faster on some operations and only a little slower on others. The
most spectacular result I have is inserting 16384 into a sorted
ListStore. Before:
16384 492038.314000 30.031635 257k
After:
16384 1465.426000 0.089443 768k
Ie. 8 minutes before, 1.5 second.after. The new data structure is also
much faster for inserting at a fixed position: Before:
16384 5573.062000 0.340153 259k
After:
16384 531.947500 0.032467 768k
However for prepending and appending, the new data structure is
slower: Before:
16384 357.230500 0.021804 259k
AFter:
16384 413.595500 0.025244 768k
But not dramatically slower.
The one concern I have is that the new data structure uses a lot more
memory. A node in the new data structure is 6 words, whereas a node in
the old one is just 2, so the new data structure uses 16 bytes extra
per item.
(Matthias' program produces numbers on memory use, but they use
mallinfo() which reports how much memory was malloc()ed. That is not
the number we are interested in here becasue the nodes in the old data
structure come from a freelist, so they don't get reported. The nodes
in the new data structure are malloc()ed so they do get reported).
Attached is
- two new files gtksequence.c and gtksequence.h
- a patch
- a testprogram, written by Matthias that produces various
numbers on the performance of various operations on
GtkListStore
- two data files, before and after, produced by the
testprogram.
Søren
Attachment:
gtksequence.c
Description: gtksequence.c
Attachment:
gtksequence.h
Description: gtksequence.h
? 136446.patch
? 57100.patch
? accels
? after
? asdf.c
? birnan
? bogus.patch
? column-resize.patch
? core.11586
? core.12028
? core.14263
? core.15648
? core.21013
? core.25523
? core.27588
? cursors.patch
? emfle.patch
? entryfix
? group.patch
? groupproperty.patch
? gtksequence.c
? gtksequence.h
? gtktoolbar.bad-approach.c
? mb-childspace-2.patch
? menu.start.patch
? notebook-bogus-draw.patch
? seqconvert.sh
? sequencediff.patch
? showattachment.cgi
? sizer.patch
? vaek
? window-fix.c
? window-fix.patch
? window-group.patch
Index: Makefile.am
===================================================================
RCS file: /cvs/gnome/gtk+/gtk/Makefile.am,v
retrieving revision 1.245
diff -u -p -u -r1.245 Makefile.am
--- Makefile.am 19 Jul 2004 19:07:27 -0000 1.245
+++ Makefile.am 7 Aug 2004 20:00:28 -0000
@@ -275,30 +275,31 @@ gtk_semi_private_h_sources = \
gtkfilesystem.h
# GTK+ header files that don't get installed
-gtk_private_h_sources = \
- gtkcellrendererseptext.h\
- gtkentryprivate.h \
- gtkfilechooserembed.h \
- gtkfilechooserentry.h \
- gtkfilechooserdefault.h \
- gtkfilechooserprivate.h \
- gtkfilechooserutils.h \
- gtkfilesystemunix.h \
- gtkfilesystemmodel.h \
- gtkpathbar.h \
- gtkrbtree.h \
- gtktextbtree.h \
- gtktextchildprivate.h \
- gtktextsegment.h \
- gtktexttypes.h \
- gtktextutil.h \
- gtktextiterprivate.h \
- gtktextmarkprivate.h \
- gtktexttagprivate.h \
- gtkthemes.h \
- gtktreedatalist.h \
- gtktreeprivate.h \
- gtkwindow-decorate.h \
+gtk_private_h_sources = \
+ gtkcellrendererseptext.h \
+ gtkentryprivate.h \
+ gtkfilechooserembed.h \
+ gtkfilechooserentry.h \
+ gtkfilechooserdefault.h \
+ gtkfilechooserprivate.h \
+ gtkfilechooserutils.h \
+ gtkfilesystemunix.h \
+ gtkfilesystemmodel.h \
+ gtkpathbar.h \
+ gtkrbtree.h \
+ gtksequence.h \
+ gtktextbtree.h \
+ gtktextchildprivate.h \
+ gtktextsegment.h \
+ gtktexttypes.h \
+ gtktextutil.h \
+ gtktextiterprivate.h \
+ gtktextmarkprivate.h \
+ gtktexttagprivate.h \
+ gtkthemes.h \
+ gtktreedatalist.h \
+ gtktreeprivate.h \
+ gtkwindow-decorate.h \
gtktoggleactionprivate.h
# GTK+ C sources to build the library from
@@ -432,6 +433,7 @@ gtk_c_sources = \
gtkscale.c \
gtkscrollbar.c \
gtkscrolledwindow.c \
+ gtksequence.c \
gtkselection.c \
gtkseparator.c \
gtkseparatormenuitem.c \
Index: gtkentry.c
===================================================================
RCS file: /cvs/gnome/gtk+/gtk/gtkentry.c,v
retrieving revision 1.256
diff -u -p -u -r1.256 gtkentry.c
--- gtkentry.c 31 Jul 2004 05:15:32 -0000 1.256
+++ gtkentry.c 7 Aug 2004 20:00:29 -0000
@@ -1383,6 +1383,70 @@ gtk_entry_expose (GtkWidget *widget
return FALSE;
}
+static void
+gtk_entry_get_pixel_ranges (GtkEntry *entry,
+ gint **ranges,
+ gint *n_ranges)
+{
+ gint start_char, end_char;
+
+ if (gtk_editable_get_selection_bounds (GTK_EDITABLE (entry), &start_char, &end_char))
+ {
+ PangoLayout *layout = gtk_entry_ensure_layout (entry, TRUE);
+ PangoLayoutLine *line = pango_layout_get_lines (layout)->data;
+ const char *text = pango_layout_get_text (layout);
+ gint start_index = g_utf8_offset_to_pointer (text, start_char) - text;
+ gint end_index = g_utf8_offset_to_pointer (text, end_char) - text;
+ gint real_n_ranges, i;
+
+ pango_layout_line_get_x_ranges (line, start_index, end_index, ranges, &real_n_ranges);
+
+ if (ranges)
+ {
+ gint *r = *ranges;
+
+ for (i = 0; i < real_n_ranges; ++i)
+ {
+ r[2 * i + 1] = (r[2 * i + 1] - r[2 * i]) / PANGO_SCALE;
+ r[2 * i] = r[2 * i] / PANGO_SCALE;
+ }
+ }
+
+ if (n_ranges)
+ *n_ranges = real_n_ranges;
+ }
+ else
+ {
+ if (n_ranges)
+ *n_ranges = 0;
+ if (ranges)
+ *ranges = NULL;
+ }
+}
+
+static gboolean
+in_selection (GtkEntry *entry,
+ gint x)
+{
+ gint *ranges;
+ gint n_ranges, i;
+ gint retval = FALSE;
+
+ gtk_entry_get_pixel_ranges (entry, &ranges, &n_ranges);
+
+ for (i = 0; i < n_ranges; ++i)
+ {
+ if (x >= ranges[2 * i] && x < ranges[2 * i] + ranges[2 * i + 1])
+ {
+ retval = TRUE;
+ break;
+ }
+ }
+
+ g_free (ranges);
+ return retval;
+}
+
static gint
gtk_entry_button_press (GtkWidget *widget,
GdkEventButton *event)
@@ -1474,21 +1538,18 @@ gtk_entry_button_press (GtkWidget *
switch (event->type)
{
case GDK_BUTTON_PRESS:
- if (have_selection && tmp_pos >= sel_start && tmp_pos <= sel_end)
+ if (in_selection (entry, event->x + entry->scroll_offset))
{
/* Click inside the selection - we'll either start a drag, or
* clear the selection
*/
-
entry->in_drag = TRUE;
entry->drag_start_x = event->x + entry->scroll_offset;
entry->drag_start_y = event->y + entry->scroll_offset;
}
else
gtk_editable_set_position (editable, tmp_pos);
-
break;
-
case GDK_2BUTTON_PRESS:
/* We ALWAYS receive a GDK_BUTTON_PRESS immediately before
@@ -2913,7 +2974,6 @@ static void
gtk_entry_draw_text (GtkEntry *entry)
{
GtkWidget *widget;
- PangoLayoutLine *line;
if (!entry->visible && entry->invisible_char == 0)
return;
@@ -2937,19 +2997,12 @@ gtk_entry_draw_text (GtkEntry *entry)
gint *ranges;
gint n_ranges, i;
PangoRectangle logical_rect;
- const gchar *text = pango_layout_get_text (layout);
- gint start_index = g_utf8_offset_to_pointer (text, start_pos) - text;
- gint end_index = g_utf8_offset_to_pointer (text, end_pos) - text;
- GdkRegion *clip_region = gdk_region_new ();
- GdkGC *text_gc;
- GdkGC *selection_gc;
+ GdkGC *selection_gc, *text_gc;
+ GdkRegion *clip_region;
- line = pango_layout_get_lines (layout)->data;
-
- pango_layout_line_get_x_ranges (line, start_index, end_index, &ranges, &n_ranges);
+ pango_layout_get_pixel_extents (layout, NULL, &logical_rect);
+ gtk_entry_get_pixel_ranges (entry, &ranges, &n_ranges);
- pango_layout_get_extents (layout, NULL, &logical_rect);
-
if (GTK_WIDGET_HAS_FOCUS (entry))
{
selection_gc = widget->style->base_gc [GTK_STATE_SELECTED];
@@ -2961,21 +3014,22 @@ gtk_entry_draw_text (GtkEntry *entry)
text_gc = widget->style->text_gc [GTK_STATE_ACTIVE];
}
- for (i=0; i < n_ranges; i++)
+ clip_region = gdk_region_new ();
+ for (i = 0; i < n_ranges; ++i)
{
GdkRectangle rect;
- rect.x = INNER_BORDER - entry->scroll_offset + ranges[2*i] / PANGO_SCALE;
+ rect.x = INNER_BORDER - entry->scroll_offset + ranges[2 * i];
rect.y = y;
- rect.width = (ranges[2*i + 1] - ranges[2*i]) / PANGO_SCALE;
- rect.height = logical_rect.height / PANGO_SCALE;
+ rect.width = ranges[2 * i + 1];
+ rect.height = logical_rect.height;
gdk_draw_rectangle (entry->text_area, selection_gc, TRUE,
rect.x, rect.y, rect.width, rect.height);
gdk_region_union_with_rect (clip_region, &rect);
}
-
+
gdk_gc_set_clip_region (text_gc, clip_region);
gdk_draw_layout (entry->text_area, text_gc,
x, y,
Index: gtkliststore.c
===================================================================
RCS file: /cvs/gnome/gtk+/gtk/gtkliststore.c,v
retrieving revision 1.93
diff -u -p -u -r1.93 gtkliststore.c
--- gtkliststore.c 6 Mar 2004 03:37:58 -0000 1.93
+++ gtkliststore.c 7 Aug 2004 20:00:29 -0000
@@ -24,10 +24,13 @@
#include "gtkliststore.h"
#include "gtktreedatalist.h"
#include "gtktreednd.h"
+#include "gtksequence.h"
+#if 0
#define G_SLIST(x) ((GSList *) x)
+#endif
#define GTK_LIST_STORE_IS_SORTED(list) (GTK_LIST_STORE (list)->sort_column_id != -2)
-#define VALID_ITER(iter, list_store) (iter!= NULL && iter->user_data != NULL && list_store->stamp == iter->stamp)
+#define VALID_ITER(iter, list_store) ((iter)!= NULL && (iter)->user_data != NULL && list_store->stamp == (iter)->stamp && !_gtk_sequence_ptr_is_end ((iter)->user_data) && _gtk_sequence_ptr_get_sequence ((iter)->user_data) == list_store->seq)
static void gtk_list_store_init (GtkListStore *list_store);
static void gtk_list_store_class_init (GtkListStoreClass *class);
@@ -112,11 +115,6 @@ static void gtk_list_store_set_defau
GtkDestroyNotify destroy);
static gboolean gtk_list_store_has_default_sort_func (GtkTreeSortable *sortable);
-static void gtk_list_store_move (GtkListStore *store,
- GtkTreeIter *iter,
- GtkTreeIter *path,
- gboolean before);
-
static GObjectClass *parent_class = NULL;
@@ -126,9 +124,11 @@ validate_list_store (GtkListStore *list_
{
if (gtk_debug_flags & GTK_DEBUG_TREE)
{
+#if 0
g_assert (g_slist_length (list_store->root) == list_store->length);
g_assert (g_slist_last (list_store->root) == list_store->tail);
+#endif
}
}
@@ -256,11 +256,11 @@ gtk_list_store_sortable_init (GtkTreeSor
static void
gtk_list_store_init (GtkListStore *list_store)
{
- list_store->root = NULL;
- list_store->tail = NULL;
+ list_store->seq = _gtk_sequence_new (NULL);
+ list_store->dummy = NULL;
list_store->sort_list = NULL;
list_store->stamp = g_random_int ();
- list_store->length = 0;
+ list_store->dummy2 = 0;
list_store->sort_column_id = -2;
list_store->columns_dirty = FALSE;
}
@@ -282,7 +282,7 @@ gtk_list_store_init (GtkListStore *list_
**/
GtkListStore *
gtk_list_store_new (gint n_columns,
- ...)
+ ...)
{
GtkListStore *retval;
va_list args;
@@ -440,8 +440,10 @@ gtk_list_store_finalize (GObject *object
{
GtkListStore *list_store = GTK_LIST_STORE (object);
- g_slist_foreach (list_store->root, (GFunc) _gtk_tree_data_list_free, list_store->column_headers);
- g_slist_free (list_store->root);
+ _gtk_sequence_foreach (list_store->seq,
+ (GFunc) _gtk_tree_data_list_free, list_store->column_headers);
+
+ _gtk_sequence_free (list_store->seq);
_gtk_tree_data_list_header_free (list_store->sort_list);
g_free (list_store->column_headers);
@@ -501,7 +503,7 @@ gtk_list_store_get_iter (GtkTreeModel *t
GtkTreePath *path)
{
GtkListStore *list_store = (GtkListStore *) tree_model;
- GSList *list;
+ GtkSequence *seq;
gint i;
g_return_val_if_fail (GTK_IS_LIST_STORE (tree_model), FALSE);
@@ -509,18 +511,15 @@ gtk_list_store_get_iter (GtkTreeModel *t
list_store->columns_dirty = TRUE;
+ seq = list_store->seq;
+
i = gtk_tree_path_get_indices (path)[0];
- if (i >= list_store->length)
+ if (i >= _gtk_sequence_get_length (seq))
return FALSE;
- list = g_slist_nth (G_SLIST (list_store->root), i);
-
- /* If this fails, list_store->length has gotten mangled. */
- g_assert (list);
-
iter->stamp = list_store->stamp;
- iter->user_data = list;
+ iter->user_data = _gtk_sequence_get_ptr_at_pos (seq, i);
return TRUE;
}
@@ -529,31 +528,18 @@ static GtkTreePath *
gtk_list_store_get_path (GtkTreeModel *tree_model,
GtkTreeIter *iter)
{
- GtkTreePath *retval;
- GSList *list;
- gint i = 0;
+ GtkTreePath *path;
g_return_val_if_fail (GTK_IS_LIST_STORE (tree_model), NULL);
g_return_val_if_fail (iter->stamp == GTK_LIST_STORE (tree_model)->stamp, NULL);
- if (G_SLIST (iter->user_data) == G_SLIST (GTK_LIST_STORE (tree_model)->tail))
- {
- retval = gtk_tree_path_new ();
- gtk_tree_path_append_index (retval, GTK_LIST_STORE (tree_model)->length - 1);
- return retval;
- }
- for (list = G_SLIST (GTK_LIST_STORE (tree_model)->root); list; list = list->next)
- {
- if (list == G_SLIST (iter->user_data))
- break;
- i++;
- }
- if (list == NULL)
+ if (_gtk_sequence_ptr_is_end (iter->user_data))
return NULL;
-
- retval = gtk_tree_path_new ();
- gtk_tree_path_append_index (retval, i);
- return retval;
+
+ path = gtk_tree_path_new ();
+ gtk_tree_path_append_index (path, _gtk_sequence_ptr_get_position (iter->user_data));
+
+ return path;
}
static void
@@ -568,8 +554,9 @@ gtk_list_store_get_value (GtkTreeModel *
g_return_if_fail (GTK_IS_LIST_STORE (tree_model));
g_return_if_fail (column < GTK_LIST_STORE (tree_model)->n_columns);
g_return_if_fail (GTK_LIST_STORE (tree_model)->stamp == iter->stamp);
-
- list = G_SLIST (iter->user_data)->data;
+ g_return_if_fail (VALID_ITER (iter, GTK_LIST_STORE(tree_model)));
+
+ list = _gtk_sequence_ptr_get_data (iter->user_data);
while (tmp_column-- > 0 && list)
list = list->next;
@@ -588,10 +575,9 @@ gtk_list_store_iter_next (GtkTreeModel
{
g_return_val_if_fail (GTK_IS_LIST_STORE (tree_model), FALSE);
g_return_val_if_fail (GTK_LIST_STORE (tree_model)->stamp == iter->stamp, FALSE);
+ iter->user_data = _gtk_sequence_ptr_next (iter->user_data);
- iter->user_data = G_SLIST (iter->user_data)->next;
-
- return (iter->user_data != NULL);
+ return !_gtk_sequence_ptr_is_end (iter->user_data);
}
static gboolean
@@ -599,18 +585,18 @@ gtk_list_store_iter_children (GtkTreeMod
GtkTreeIter *iter,
GtkTreeIter *parent)
{
+ GtkListStore *list_store;
+
/* this is a list, nodes have no children */
if (parent)
return FALSE;
- /* but if parent == NULL we return the list itself as children of the
- * "root"
- */
+ list_store = GTK_LIST_STORE (tree_model);
- if (GTK_LIST_STORE (tree_model)->root)
+ if (_gtk_sequence_get_length (list_store->seq) == 0)
{
- iter->stamp = GTK_LIST_STORE (tree_model)->stamp;
- iter->user_data = GTK_LIST_STORE (tree_model)->root;
+ iter->stamp = list_store->stamp;
+ iter->user_data = _gtk_sequence_get_begin_ptr (list_store->seq);
return TRUE;
}
else
@@ -628,11 +614,16 @@ static gint
gtk_list_store_iter_n_children (GtkTreeModel *tree_model,
GtkTreeIter *iter)
{
+ GtkListStore *store;
+
g_return_val_if_fail (GTK_IS_LIST_STORE (tree_model), -1);
+
+ store = GTK_LIST_STORE (tree_model);
+
if (iter == NULL)
- return GTK_LIST_STORE (tree_model)->length;
+ return _gtk_sequence_get_length (store->seq);
- g_return_val_if_fail (GTK_LIST_STORE (tree_model)->stamp == iter->stamp, -1);
+ g_return_val_if_fail (store->stamp == iter->stamp, -1);
return 0;
}
@@ -642,23 +633,24 @@ gtk_list_store_iter_nth_child (GtkTreeMo
GtkTreeIter *parent,
gint n)
{
- GSList *child;
+ GtkSequencePtr child;
+ GtkListStore *store;
g_return_val_if_fail (GTK_IS_LIST_STORE (tree_model), FALSE);
+ store = GTK_LIST_STORE (tree_model);
+
if (parent)
return FALSE;
- child = g_slist_nth (G_SLIST (GTK_LIST_STORE (tree_model)->root), n);
+ child = _gtk_sequence_get_ptr_at_pos (store->seq, n);
- if (child)
- {
- iter->stamp = GTK_LIST_STORE (tree_model)->stamp;
- iter->user_data = child;
- return TRUE;
- }
- else
+ if (_gtk_sequence_ptr_is_end (child))
return FALSE;
+
+ iter->stamp = store->stamp;
+ iter->user_data = child;
+ return TRUE;
}
static gboolean
@@ -711,7 +703,7 @@ gtk_list_store_real_set_value (GtkListSt
converted = TRUE;
}
- prev = list = G_SLIST (iter->user_data)->data;
+ prev = list = _gtk_sequence_ptr_get_data (iter->user_data);
while (list != NULL)
{
@@ -734,9 +726,10 @@ gtk_list_store_real_set_value (GtkListSt
list = list->next;
}
- if (G_SLIST (iter->user_data)->data == NULL)
+ if (_gtk_sequence_ptr_get_data (iter->user_data) == NULL)
{
- G_SLIST (iter->user_data)->data = list = _gtk_tree_data_list_alloc ();
+ list = _gtk_tree_data_list_alloc();
+ _gtk_sequence_set (iter->user_data, list);
list->next = NULL;
}
else
@@ -929,68 +922,6 @@ gtk_list_store_set (GtkListStore *list_s
va_end (var_args);
}
-static GSList*
-remove_link_saving_prev (GSList *list,
- GSList *link,
- GSList **prevp)
-{
- GSList *tmp;
- GSList *prev;
-
- prev = NULL;
- tmp = list;
-
- while (tmp)
- {
- if (tmp == link)
- {
- if (prev)
- prev->next = link->next;
-
- if (list == link)
- list = list->next;
-
- link->next = NULL;
- break;
- }
-
- prev = tmp;
- tmp = tmp->next;
- }
-
- *prevp = prev;
-
- return list;
-}
-
-static void
-gtk_list_store_remove_silently (GtkListStore *list_store,
- GtkTreeIter *iter,
- GtkTreePath *path)
-{
- if (G_SLIST (iter->user_data)->data)
- {
- _gtk_tree_data_list_free ((GtkTreeDataList *) G_SLIST (iter->user_data)->data,
- list_store->column_headers);
- G_SLIST (iter->user_data)->data = NULL;
- }
-
- {
- GSList *prev = NULL;
-
- list_store->root = remove_link_saving_prev (G_SLIST (list_store->root),
- G_SLIST (iter->user_data),
- &prev);
-
- list_store->length -= 1;
-
- if (iter->user_data == list_store->tail)
- list_store->tail = prev;
-
- g_slist_free (G_SLIST (iter->user_data));
- }
-}
-
/**
* gtk_list_store_remove:
* @list_store: A #GtkListStore
@@ -1007,54 +938,37 @@ gtk_list_store_remove (GtkListStore *lis
GtkTreeIter *iter)
{
GtkTreePath *path;
- GSList *next;
+ GtkSequencePtr ptr, next;
g_return_val_if_fail (GTK_IS_LIST_STORE (list_store), FALSE);
g_return_val_if_fail (VALID_ITER (iter, list_store), FALSE);
- next = G_SLIST (iter->user_data)->next;
path = gtk_list_store_get_path (GTK_TREE_MODEL (list_store), iter);
validate_list_store (list_store);
- gtk_list_store_remove_silently (list_store, iter, path);
-
+ ptr = iter->user_data;
+ next = _gtk_sequence_ptr_next (ptr);
+
+ _gtk_tree_data_list_free (_gtk_sequence_ptr_get_data (ptr), list_store->column_headers);
+ _gtk_sequence_remove (iter->user_data);
+
validate_list_store (list_store);
gtk_tree_model_row_deleted (GTK_TREE_MODEL (list_store), path);
gtk_tree_path_free (path);
- if (next)
+ if (_gtk_sequence_ptr_is_end (next))
{
- iter->stamp = list_store->stamp;
- iter->user_data = next;
- return TRUE;
+ iter->stamp = 0;
+ return FALSE;
}
else
{
- iter->stamp = 0;
+ iter->stamp = list_store->stamp;
+ iter->user_data = next;
+ return TRUE;
}
-
- return FALSE;
-}
-
-static void
-insert_after (GtkListStore *list_store,
- GSList *sibling,
- GSList *new_list)
-{
- g_return_if_fail (sibling != NULL);
- g_return_if_fail (new_list != NULL);
-
- /* insert new node after list */
- new_list->next = sibling->next;
- sibling->next = new_list;
-
- /* if list was the tail, the new node is the new tail */
- if (sibling == ((GSList *) list_store->tail))
- list_store->tail = new_list;
-
- list_store->length += 1;
}
/**
@@ -1075,9 +989,9 @@ gtk_list_store_insert (GtkListStore *lis
GtkTreeIter *iter,
gint position)
{
- GSList *list;
GtkTreePath *path;
- GSList *new_list;
+ GtkSequence *seq;
+ GtkSequencePtr ptr;
g_return_if_fail (GTK_IS_LIST_STORE (list_store));
g_return_if_fail (iter != NULL);
@@ -1085,31 +999,15 @@ gtk_list_store_insert (GtkListStore *lis
list_store->columns_dirty = TRUE;
- if (position == 0 ||
- GTK_LIST_STORE_IS_SORTED (list_store))
- {
- gtk_list_store_prepend (list_store, iter);
- return;
- }
-
- list = g_slist_nth (G_SLIST (list_store->root), position - 1);
-
- if (list == NULL)
- {
- /* position if off the end of the list, append it */
- gtk_list_store_append (list_store, iter);
-
- return;
- }
-
- new_list = g_slist_alloc ();
+ seq = list_store->seq;
- insert_after (list_store, list, new_list);
+ ptr = _gtk_sequence_get_ptr_at_pos (seq, position);
+ ptr = _gtk_sequence_insert (ptr, NULL);
iter->stamp = list_store->stamp;
- iter->user_data = new_list;
+ iter->user_data = ptr;
- validate_list_store (list_store);
+ g_assert (VALID_ITER (iter, list_store));
path = gtk_tree_path_new ();
gtk_tree_path_append_index (path, position);
@@ -1134,76 +1032,19 @@ gtk_list_store_insert_before (GtkListSto
GtkTreeIter *iter,
GtkTreeIter *sibling)
{
- GtkTreePath *path;
- GSList *list, *prev, *new_list;
- gint i = 0;
-
+ GtkSequencePtr after;
+
g_return_if_fail (GTK_IS_LIST_STORE (list_store));
g_return_if_fail (iter != NULL);
if (sibling)
g_return_if_fail (VALID_ITER (sibling, list_store));
- list_store->columns_dirty = TRUE;
-
- if (GTK_LIST_STORE_IS_SORTED (list_store))
- {
- gtk_list_store_prepend (list_store, iter);
- return;
- }
-
- if (sibling == NULL)
- {
- gtk_list_store_append (list_store, iter);
- return;
- }
-
- new_list = g_slist_alloc ();
-
- prev = NULL;
- list = list_store->root;
- while (list && list != sibling->user_data)
- {
- prev = list;
- list = list->next;
- i++;
- }
-
- if (list != sibling->user_data)
- {
- g_warning ("%s: sibling iterator invalid? not found in the list", G_STRLOC);
- return;
- }
-
- /* if there are no nodes, we become the list tail, otherwise we
- * are inserting before any existing nodes so we can't change
- * the tail
- */
-
- if (list_store->root == NULL)
- list_store->tail = new_list;
-
- if (prev)
- {
- new_list->next = prev->next;
- prev->next = new_list;
- }
+ if (!sibling)
+ after = _gtk_sequence_get_end_ptr (list_store->seq);
else
- {
- new_list->next = list_store->root;
- list_store->root = new_list;
- }
+ after = sibling->user_data;
- iter->stamp = list_store->stamp;
- iter->user_data = new_list;
-
- list_store->length += 1;
-
- validate_list_store (list_store);
-
- path = gtk_tree_path_new ();
- gtk_tree_path_append_index (path, i);
- gtk_tree_model_row_inserted (GTK_TREE_MODEL (list_store), path, iter);
- gtk_tree_path_free (path);
+ gtk_list_store_insert (list_store, iter, _gtk_sequence_ptr_get_position (after));
}
/**
@@ -1223,42 +1064,19 @@ gtk_list_store_insert_after (GtkListStor
GtkTreeIter *iter,
GtkTreeIter *sibling)
{
- GtkTreePath *path;
- GSList *list, *new_list;
- gint i = 0;
+ GtkSequencePtr after;
g_return_if_fail (GTK_IS_LIST_STORE (list_store));
g_return_if_fail (iter != NULL);
if (sibling)
g_return_if_fail (VALID_ITER (sibling, list_store));
- list_store->columns_dirty = TRUE;
-
- if (sibling == NULL ||
- GTK_LIST_STORE_IS_SORTED (list_store))
- {
- gtk_list_store_prepend (list_store, iter);
- return;
- }
-
- for (list = list_store->root; list && list != sibling->user_data; list = list->next)
- i++;
-
- g_return_if_fail (list == sibling->user_data);
-
- new_list = g_slist_alloc ();
-
- insert_after (list_store, list, new_list);
-
- iter->stamp = list_store->stamp;
- iter->user_data = new_list;
-
- validate_list_store (list_store);
+ if (!sibling)
+ after = _gtk_sequence_get_begin_ptr (list_store->seq);
+ else
+ after = _gtk_sequence_ptr_next (sibling->user_data);
- path = gtk_tree_path_new ();
- gtk_tree_path_append_index (path, i + 1);
- gtk_tree_model_row_inserted (GTK_TREE_MODEL (list_store), path, iter);
- gtk_tree_path_free (path);
+ gtk_list_store_insert (list_store, iter, _gtk_sequence_ptr_get_position (after));
}
/**
@@ -1275,30 +1093,10 @@ void
gtk_list_store_prepend (GtkListStore *list_store,
GtkTreeIter *iter)
{
- GtkTreePath *path;
-
g_return_if_fail (GTK_IS_LIST_STORE (list_store));
g_return_if_fail (iter != NULL);
- iter->stamp = list_store->stamp;
- iter->user_data = g_slist_alloc ();
-
- list_store->columns_dirty = TRUE;
-
- if (list_store->root == NULL)
- list_store->tail = iter->user_data;
-
- G_SLIST (iter->user_data)->next = G_SLIST (list_store->root);
- list_store->root = iter->user_data;
-
- list_store->length += 1;
-
- validate_list_store (list_store);
-
- path = gtk_tree_path_new ();
- gtk_tree_path_append_index (path, 0);
- gtk_tree_model_row_inserted (GTK_TREE_MODEL (list_store), path, iter);
- gtk_tree_path_free (path);
+ gtk_list_store_insert (list_store, iter, 0);
}
/**
@@ -1315,37 +1113,10 @@ void
gtk_list_store_append (GtkListStore *list_store,
GtkTreeIter *iter)
{
- GtkTreePath *path;
-
g_return_if_fail (GTK_IS_LIST_STORE (list_store));
g_return_if_fail (iter != NULL);
- list_store->columns_dirty = TRUE;
-
- if (GTK_LIST_STORE_IS_SORTED (list_store))
- {
- gtk_list_store_prepend (list_store, iter);
- return;
- }
-
- iter->stamp = list_store->stamp;
- iter->user_data = g_slist_alloc ();
-
- if (list_store->tail)
- ((GSList *)list_store->tail)->next = iter->user_data;
- else
- list_store->root = iter->user_data;
-
- list_store->tail = iter->user_data;
-
- list_store->length += 1;
-
- validate_list_store (list_store);
-
- path = gtk_tree_path_new ();
- gtk_tree_path_append_index (path, list_store->length - 1);
- gtk_tree_model_row_inserted (GTK_TREE_MODEL (list_store), path, iter);
- gtk_tree_path_free (path);
+ gtk_list_store_insert (list_store, iter, _gtk_sequence_get_length (list_store->seq));
}
/**
@@ -1361,10 +1132,10 @@ gtk_list_store_clear (GtkListStore *list
GtkTreeIter iter;
g_return_if_fail (GTK_IS_LIST_STORE (list_store));
- while (list_store->root)
+ while (_gtk_sequence_get_length (list_store->seq) > 0)
{
iter.stamp = list_store->stamp;
- iter.user_data = list_store->root;
+ iter.user_data = _gtk_sequence_get_begin_ptr (list_store->seq);
gtk_list_store_remove (list_store, &iter);
}
}
@@ -1387,24 +1158,16 @@ gboolean
gtk_list_store_iter_is_valid (GtkListStore *list_store,
GtkTreeIter *iter)
{
- GList *list;
-
g_return_val_if_fail (GTK_IS_LIST_STORE (list_store), FALSE);
g_return_val_if_fail (iter != NULL, FALSE);
if (!VALID_ITER (iter, list_store))
return FALSE;
- if (iter->user_data == list_store->root)
- return TRUE;
- if (iter->user_data == list_store->tail)
- return TRUE;
-
- for (list = ((GList *)list_store->root)->next; list; list = list->next)
- if (list == iter->user_data)
- return TRUE;
+ if (_gtk_sequence_ptr_get_sequence (iter->user_data) != list_store->seq)
+ return FALSE;
- return FALSE;
+ return TRUE;
}
static gboolean real_gtk_list_store_row_draggable (GtkTreeDragSource *drag_source,
@@ -1520,7 +1283,7 @@ gtk_list_store_drag_data_received (GtkTr
*/
if (retval)
{
- GtkTreeDataList *dl = G_SLIST (src_iter.user_data)->data;
+ GtkTreeDataList *dl = _gtk_sequence_ptr_get_data (src_iter.user_data);
GtkTreeDataList *copy_head = NULL;
GtkTreeDataList *copy_prev = NULL;
GtkTreeDataList *copy_iter = NULL;
@@ -1546,7 +1309,7 @@ gtk_list_store_drag_data_received (GtkTr
}
dest_iter.stamp = list_store->stamp;
- G_SLIST (dest_iter.user_data)->data = copy_head;
+ _gtk_sequence_set (dest_iter.user_data, copy_head);
path = gtk_list_store_get_path (tree_model, &dest_iter);
gtk_tree_model_row_changed (tree_model, path, &dest_iter);
@@ -1599,7 +1362,7 @@ gtk_list_store_row_drop_possible (GtkTre
indices = gtk_tree_path_get_indices (dest_path);
- if (indices[0] <= GTK_LIST_STORE (drag_dest)->length)
+ if (indices[0] <= _gtk_sequence_get_length (GTK_LIST_STORE (drag_dest)->seq))
retval = TRUE;
out:
@@ -1610,11 +1373,6 @@ gtk_list_store_row_drop_possible (GtkTre
}
/* Sorting and reordering */
-typedef struct _SortTuple
-{
- gint offset;
- GSList *el;
-} SortTuple;
/* Reordering */
static gint
@@ -1622,20 +1380,17 @@ gtk_list_store_reorder_func (gconstpoint
gconstpointer b,
gpointer user_data)
{
- SortTuple *a_reorder;
- SortTuple *b_reorder;
-
- a_reorder = (SortTuple *)a;
- b_reorder = (SortTuple *)b;
+ GHashTable *new_positions = user_data;
+ gint apos = GPOINTER_TO_INT (g_hash_table_lookup (new_positions, a));
+ gint bpos = GPOINTER_TO_INT (g_hash_table_lookup (new_positions, b));
- if (a_reorder->offset < b_reorder->offset)
+ if (apos < bpos)
return -1;
- if (a_reorder->offset > b_reorder->offset)
+ if (apos > bpos)
return 1;
-
return 0;
}
-
+
/**
* gtk_list_store_reorder:
* @store: A #GtkListStore.
@@ -1653,45 +1408,34 @@ gtk_list_store_reorder (GtkListStore *st
gint *new_order)
{
gint i;
- GSList *current_list;
GtkTreePath *path;
- SortTuple *sort_array;
+ GHashTable *new_positions;
+ GtkSequencePtr ptr;
g_return_if_fail (GTK_IS_LIST_STORE (store));
g_return_if_fail (!GTK_LIST_STORE_IS_SORTED (store));
g_return_if_fail (new_order != NULL);
- sort_array = g_new (SortTuple, store->length);
+ new_positions = g_hash_table_new (g_direct_hash, g_direct_equal);
- current_list = store->root;
-
- for (i = 0; i < store->length; i++)
+ ptr = _gtk_sequence_get_begin_ptr (store->seq);
+ i = 0;
+ while (ptr)
{
- sort_array[new_order[i]].offset = i;
- sort_array[i].el = current_list;
+ g_hash_table_insert (new_positions, ptr, GINT_TO_POINTER (new_order[i++]));
- current_list = current_list->next;
+ ptr = _gtk_sequence_ptr_next (ptr);
}
+
+ _gtk_sequence_sort (store->seq, gtk_list_store_reorder_func, new_positions);
- g_qsort_with_data (sort_array,
- store->length,
- sizeof (SortTuple),
- gtk_list_store_reorder_func,
- NULL);
-
- for (i = 0; i < store->length - 1; i++)
- G_SLIST (sort_array[i].el)->next = G_SLIST (sort_array[i+1].el);
-
- store->root = G_SLIST (sort_array[0].el);
- store->tail = G_SLIST (sort_array[store->length-1].el);
- G_SLIST (store->tail)->next = NULL;
-
+ g_hash_table_destroy (new_positions);
+
/* emit signal */
path = gtk_tree_path_new ();
gtk_tree_model_rows_reordered (GTK_TREE_MODEL (store),
path, NULL, new_order);
gtk_tree_path_free (path);
- g_free (sort_array);
}
/**
@@ -1710,8 +1454,6 @@ gtk_list_store_swap (GtkListStore *store
GtkTreeIter *a,
GtkTreeIter *b)
{
- GSList *i, *prev_a = NULL, *prev_b = NULL;
- gint j, a_count = 0, b_count = 0, *order;
GtkTreePath *path;
g_return_if_fail (GTK_IS_LIST_STORE (store));
@@ -1722,270 +1464,76 @@ gtk_list_store_swap (GtkListStore *store
if (a->user_data == b->user_data)
return;
- if (a->user_data == store->root)
- prev_a = NULL;
- else
- {
- for (i = store->root; i; i = i->next, a_count++)
- if (i->next == a->user_data)
- {
- prev_a = i;
- break;
- }
-
- a_count++;
- }
-
- if (b->user_data == store->root)
- prev_b = NULL;
- else
- {
- for (i = store->root; i; i = i->next, b_count++)
- if (i->next == b->user_data)
- {
- prev_b = i;
- break;
- }
-
- b_count++;
- }
-
- if (!prev_a)
- store->root = b->user_data;
- else
- prev_a->next = b->user_data;
-
- if (!prev_b)
- store->root = a->user_data;
- else
- prev_b->next = a->user_data;
-
- /* think a_next inspead of a_prev here ... */
- prev_a = G_SLIST (a->user_data)->next;
- prev_b = G_SLIST (b->user_data)->next;
-
- G_SLIST (a->user_data)->next = prev_b;
- G_SLIST (b->user_data)->next = prev_a;
-
- /* update tail if needed */
- if (! G_SLIST (a->user_data)->next)
- store->tail = G_SLIST (a->user_data);
- else if (! G_SLIST (b->user_data)->next)
- store->tail = G_SLIST (b->user_data);
-
+ _gtk_sequence_swap (a->user_data, b->user_data);
+
/* emit signal */
- order = g_new (gint, store->length);
- for (j = 0; j < store->length; j++)
- if (j == a_count)
- order[j] = b_count;
- else if (j == b_count)
- order[j] = a_count;
- else
- order[j] = j;
-
path = gtk_tree_path_new ();
- gtk_tree_model_rows_reordered (GTK_TREE_MODEL (store),
- path, NULL, order);
+
+ gtk_tree_model_row_changed (GTK_TREE_MODEL (store), path, a);
+ gtk_tree_model_row_changed (GTK_TREE_MODEL (store), path, b);
+
gtk_tree_path_free (path);
- g_free (order);
}
-static void
-gtk_list_store_move (GtkListStore *store,
- GtkTreeIter *iter,
- GtkTreeIter *position,
- gboolean before)
-{
- GtkTreeIter dst_a;
- GSList *i, *a, *prev = NULL, *tmp;
- gint new_pos = 0, old_pos = 0, j = 0, *order;
- GtkTreePath *path = NULL, *pos_path = NULL;
-
- g_return_if_fail (GTK_IS_LIST_STORE (store));
- g_return_if_fail (!GTK_LIST_STORE_IS_SORTED (store));
- g_return_if_fail (VALID_ITER (iter, store));
- if (position)
- g_return_if_fail (VALID_ITER (position, store));
-
- /* lots of sanity checks */
- if (position)
- {
- path = gtk_tree_model_get_path (GTK_TREE_MODEL (store), iter);
- pos_path = gtk_tree_model_get_path (GTK_TREE_MODEL (store), position);
-
- if (gtk_tree_path_get_depth (pos_path) != 1)
- goto free_paths_and_out;
-
- /* if before:
- * moving the iter before path or "path + 1" doesn't make sense
- * else
- * moving the iter before path or "path - 1" doesn't make sense
- */
- if (!gtk_tree_path_compare (path, pos_path))
- goto free_paths_and_out;
-
- if (before)
- gtk_tree_path_next (path);
- else
- gtk_tree_path_prev (path);
-
- if (!gtk_tree_path_compare (path, pos_path))
- goto free_paths_and_out;
-
- gtk_tree_path_free (path);
- path = NULL;
- }
-
- /* getting destination iters */
- if (before && position)
- {
- if (gtk_tree_path_get_indices (pos_path)[0] > 0)
- {
- gtk_tree_path_prev (pos_path);
- if (gtk_tree_model_get_iter (GTK_TREE_MODEL (store), &dst_a, pos_path))
- a = G_SLIST (dst_a.user_data);
- else
- a = NULL;
- gtk_tree_path_next (pos_path);
- }
- else
- a = NULL;
- }
- else if (before && !position)
- a = NULL;
- else /* !before */
- {
- if (position)
- a = G_SLIST (position->user_data);
- else
- a = NULL;
- }
-
- /* don't try to reorder the iter to it's own position */
- if (a)
- {
- if (a == iter->user_data)
- goto free_paths_and_out;
- }
- else if (before)
- {
- if (iter->user_data == store->tail)
- goto free_paths_and_out;
- }
- else
- {
- if (iter->user_data == store->root)
- goto free_paths_and_out;
- }
-
- /* getting the old prev node */
- if (iter->user_data == store->root)
- prev = NULL;
- else
- {
- for (i = store->root; i; i = i->next, old_pos++)
- if (i->next == iter->user_data)
- {
- prev = i;
- break;
- }
-
- old_pos++;
- }
+static GHashTable *
+save_positions (GtkSequence *seq)
+{
+ GHashTable *positions = g_hash_table_new (g_direct_hash, g_direct_equal);
+ GtkSequencePtr ptr;
- /* remove node */
- if (!prev)
- store->root = G_SLIST (iter->user_data)->next;
- else
+ ptr = _gtk_sequence_get_begin_ptr (seq);
+ while (!_gtk_sequence_ptr_is_end (ptr))
{
- prev->next = G_SLIST (iter->user_data)->next;
- if (!prev->next)
- store->tail = prev;
+ g_hash_table_insert (positions, ptr,
+ GINT_TO_POINTER (_gtk_sequence_ptr_get_position (ptr)));
+ ptr = _gtk_sequence_ptr_next (ptr);
}
- /* and reinsert it */
- if (a)
- {
- tmp = a->next;
+ return positions;
+}
- a->next = G_SLIST (iter->user_data);
- a->next->next = tmp;
- }
- else if (!a && !before)
- {
- tmp = G_SLIST (store->root);
+static int *
+generate_order (GtkSequence *seq,
+ GHashTable *old_positions)
+{
+ GtkSequencePtr ptr;
+ int *order = g_new (int, _gtk_sequence_get_length (seq));
+ int i;
- store->root = G_SLIST (iter->user_data);
- G_SLIST (store->root)->next = tmp;
- }
- else if (!a && before)
+ i = 0;
+ ptr = _gtk_sequence_get_begin_ptr (seq);
+ while (!_gtk_sequence_ptr_is_end (ptr))
{
- G_SLIST (store->tail)->next = G_SLIST (iter->user_data);
- G_SLIST (iter->user_data)->next = NULL;
+ int old_pos = GPOINTER_TO_INT (g_hash_table_lookup (old_positions, ptr));
+ order[old_pos] = i++;
+ ptr = _gtk_sequence_ptr_next (ptr);
}
- /* update tail if needed */
- if (!G_SLIST (iter->user_data)->next)
- store->tail = G_SLIST (iter->user_data);
-
- /* emit signal */
- if (position)
- new_pos = gtk_tree_path_get_indices (pos_path)[0];
- else if (before)
- new_pos = gtk_tree_model_iter_n_children (GTK_TREE_MODEL (store), NULL) - 1;
- else
- new_pos = 0;
+ g_hash_table_destroy (old_positions);
- if (new_pos > old_pos)
- {
- if (before && position)
- new_pos--;
- }
- else
- {
- if (!before && position)
- new_pos++;
- }
+ return order;
+}
- order = g_new (gint, store->length);
- if (new_pos > old_pos)
- {
- for (j = 0; j < store->length; j++)
- if (j < old_pos)
- order[j] = j;
- else if (j >= old_pos && j < new_pos)
- order[j] = j + 1;
- else if (j == new_pos)
- order[j] = old_pos;
- else
- order[j] = j;
- }
- else
- {
- for (j = 0; j < store->length; j++)
- if (j == new_pos)
- order[j] = old_pos;
- else if (j > new_pos && j <= old_pos)
- order[j] = j - 1;
- else
- order[j] = j;
- }
+static void
+gtk_list_store_move_to (GtkListStore *store,
+ GtkTreeIter *iter,
+ gint new_pos)
+{
+ GHashTable *old_positions;
+ GtkTreePath *path;
+ gint *order;
+
+ old_positions = save_positions (store->seq);
+
+ _gtk_sequence_move (iter->user_data, _gtk_sequence_get_ptr_at_pos (store->seq, new_pos));
+ order = generate_order (store->seq, old_positions);
+
path = gtk_tree_path_new ();
gtk_tree_model_rows_reordered (GTK_TREE_MODEL (store),
path, NULL, order);
gtk_tree_path_free (path);
- if (position)
- gtk_tree_path_free (pos_path);
g_free (order);
-
- return;
-
-free_paths_and_out:
- if (path)
- gtk_tree_path_free (path);
- if (pos_path)
- gtk_tree_path_free (pos_path);
}
/**
@@ -2005,7 +1553,20 @@ gtk_list_store_move_before (GtkListStore
GtkTreeIter *iter,
GtkTreeIter *position)
{
- gtk_list_store_move (store, iter, position, TRUE);
+ gint pos;
+
+ g_return_if_fail (GTK_IS_LIST_STORE (store));
+ g_return_if_fail (!GTK_LIST_STORE_IS_SORTED (store));
+ g_return_if_fail (VALID_ITER (iter, store));
+ if (position)
+ g_return_if_fail (VALID_ITER (position, store));
+
+ if (position)
+ pos = _gtk_sequence_ptr_get_position (iter->user_data);
+ else
+ pos = -1;
+
+ gtk_list_store_move_to (store, iter, pos);
}
/**
@@ -2022,12 +1583,25 @@ gtk_list_store_move_before (GtkListStore
**/
void
gtk_list_store_move_after (GtkListStore *store,
- GtkTreeIter *iter,
+ GtkTreeIter *iter,
GtkTreeIter *position)
{
- gtk_list_store_move (store, iter, position, FALSE);
-}
+ gint pos;
+
+ g_return_if_fail (GTK_IS_LIST_STORE (store));
+ g_return_if_fail (!GTK_LIST_STORE_IS_SORTED (store));
+ g_return_if_fail (VALID_ITER (iter, store));
+ if (position)
+ g_return_if_fail (VALID_ITER (position, store));
+ if (position)
+ pos = _gtk_sequence_ptr_get_position (iter->user_data);
+ else
+ pos = 0;
+
+ gtk_list_store_move_to (store, iter, pos);
+}
+
/* Sorting */
static gint
gtk_list_store_compare_func (gconstpointer a,
@@ -2035,15 +1609,12 @@ gtk_list_store_compare_func (gconstpoint
gpointer user_data)
{
GtkListStore *list_store = user_data;
- GSList *el_a; /* Los Angeles? */
- GSList *el_b;
GtkTreeIter iter_a;
GtkTreeIter iter_b;
gint retval;
GtkTreeIterCompareFunc func;
gpointer data;
-
if (list_store->sort_column_id != -1)
{
GtkTreeDataSortHeader *header;
@@ -2063,14 +1634,14 @@ gtk_list_store_compare_func (gconstpoint
data = list_store->default_sort_data;
}
- el_a = ((SortTuple *) a)->el;
- el_b = ((SortTuple *) b)->el;
-
iter_a.stamp = list_store->stamp;
- iter_a.user_data = el_a;
+ iter_a.user_data = (gpointer)a;
iter_b.stamp = list_store->stamp;
- iter_b.user_data = el_b;
+ iter_b.user_data = (gpointer)b;
+ g_assert (VALID_ITER (&iter_a, list_store));
+ g_assert (VALID_ITER (&iter_b, list_store));
+
retval = (* func) (GTK_TREE_MODEL (list_store), &iter_a, &iter_b, data);
if (list_store->order == GTK_SORT_DESCENDING)
@@ -2080,63 +1651,32 @@ gtk_list_store_compare_func (gconstpoint
else if (retval < 0)
retval = 1;
}
+
return retval;
}
static void
gtk_list_store_sort (GtkListStore *list_store)
{
- GArray *sort_array;
- gint i;
gint *new_order;
- GSList *list;
GtkTreePath *path;
+ GHashTable *old_positions;
- if (list_store->length <= 1)
+ if (_gtk_sequence_get_length (list_store->seq) <= 1)
return;
- g_assert (GTK_LIST_STORE_IS_SORTED (list_store));
-
- list = G_SLIST (list_store->root);
-
- sort_array = g_array_sized_new (FALSE, FALSE,
- sizeof (SortTuple),
- list_store->length);
-
- for (i = 0; i < list_store->length; i++)
- {
- SortTuple tuple = {0,};
-
- /* If this fails, we are in an inconsistent state. Bad */
- g_return_if_fail (list != NULL);
+ old_positions = save_positions (list_store->seq);
- tuple.offset = i;
- tuple.el = list;
- g_array_append_val (sort_array, tuple);
-
- list = list->next;
- }
-
- g_array_sort_with_data (sort_array, gtk_list_store_compare_func, list_store);
-
- for (i = 0; i < list_store->length - 1; i++)
- g_array_index (sort_array, SortTuple, i).el->next =
- g_array_index (sort_array, SortTuple, i + 1).el;
- g_array_index (sort_array, SortTuple, list_store->length - 1).el->next = NULL;
- list_store->root = g_array_index (sort_array, SortTuple, 0).el;
- list_store->tail = g_array_index (sort_array, SortTuple, list_store->length - 1).el;
+ _gtk_sequence_sort (list_store->seq, gtk_list_store_compare_func, list_store);
/* Let the world know about our new order */
- new_order = g_new (gint, list_store->length);
- for (i = 0; i < list_store->length; i++)
- new_order[i] = g_array_index (sort_array, SortTuple, i).offset;
+ new_order = generate_order (list_store->seq, old_positions);
path = gtk_tree_path_new ();
gtk_tree_model_rows_reordered (GTK_TREE_MODEL (list_store),
path, NULL, new_order);
gtk_tree_path_free (path);
g_free (new_order);
- g_array_free (sort_array, TRUE);
}
static void
@@ -2145,180 +1685,15 @@ gtk_list_store_sort_iter_changed (GtkLis
gint column)
{
- GSList *prev = NULL;
- GSList *next = NULL;
- GSList *list = G_SLIST (list_store->root);
GtkTreePath *tmp_path;
- GtkTreeIter tmp_iter;
- gint cmp_a = 0;
- gint cmp_b = 0;
- gint i;
- gint old_location;
- gint new_location;
- gint *new_order;
- GtkTreeIterCompareFunc func;
- gpointer data;
-
- if (list_store->length < 2)
- return;
-
- tmp_iter.stamp = list_store->stamp;
-
- if (list_store->sort_column_id != -1)
- {
- GtkTreeDataSortHeader *header;
- header = _gtk_tree_data_list_get_header (list_store->sort_list,
- list_store->sort_column_id);
- g_return_if_fail (header != NULL);
- g_return_if_fail (header->func != NULL);
- func = header->func;
- data = header->data;
- }
- else
- {
- g_return_if_fail (list_store->default_sort_func != NULL);
- func = list_store->default_sort_func;
- data = list_store->default_sort_data;
- }
- /* If it's the built in function, we don't sort. */
- if (func == gtk_tree_data_list_compare_func &&
- list_store->sort_column_id != column)
- return;
-
- old_location = 0;
- /* First we find the iter, its prev, and its next */
- while (list)
- {
- if (list == G_SLIST (iter->user_data))
- break;
- prev = list;
- list = list->next;
- old_location++;
- }
- g_assert (list != NULL);
-
- next = list->next;
-
- /* Check the common case, where we don't need to sort it moved. */
- if (prev != NULL)
- {
- tmp_iter.user_data = prev;
- cmp_a = (* func) (GTK_TREE_MODEL (list_store), &tmp_iter, iter, data);
- }
-
- if (next != NULL)
- {
- tmp_iter.user_data = next;
- cmp_b = (* func) (GTK_TREE_MODEL (list_store), iter, &tmp_iter, data);
- }
-
- if (list_store->order == GTK_SORT_DESCENDING)
- {
- if (cmp_a < 0)
- cmp_a = 1;
- else if (cmp_a > 0)
- cmp_a = -1;
-
- if (cmp_b < 0)
- cmp_b = 1;
- else if (cmp_b > 0)
- cmp_b = -1;
- }
-
- if (prev == NULL && cmp_b <= 0)
- return;
- else if (next == NULL && cmp_a <= 0)
- return;
- else if (prev != NULL && next != NULL &&
- cmp_a <= 0 && cmp_b <= 0)
- return;
-
- /* We actually need to sort it */
- /* First, remove the old link. */
-
- if (prev == NULL)
- list_store->root = next;
- else
- prev->next = next;
- if (next == NULL)
- list_store->tail = prev;
- list->next = NULL;
-
- /* FIXME: as an optimization, we can potentially start at next */
- prev = NULL;
- list = G_SLIST (list_store->root);
- new_location = 0;
- tmp_iter.user_data = list;
- if (list_store->order == GTK_SORT_DESCENDING)
- cmp_a = (* func) (GTK_TREE_MODEL (list_store), &tmp_iter, iter, data);
- else
- cmp_a = (* func) (GTK_TREE_MODEL (list_store), iter, &tmp_iter, data);
-
- while ((list->next) && (cmp_a > 0))
- {
- prev = list;
- list = list->next;
- new_location++;
- tmp_iter.user_data = list;
- if (list_store->order == GTK_SORT_DESCENDING)
- cmp_a = (* func) (GTK_TREE_MODEL (list_store), &tmp_iter, iter, data);
- else
- cmp_a = (* func) (GTK_TREE_MODEL (list_store), iter, &tmp_iter, data);
- }
-
- if ((!list->next) && (cmp_a > 0))
- {
- new_location++;
- list->next = G_SLIST (iter->user_data);
- list_store->tail = list->next;
- }
- else if (prev)
- {
- prev->next = G_SLIST (iter->user_data);
- G_SLIST (iter->user_data)->next = list;
- }
- else
- {
- G_SLIST (iter->user_data)->next = G_SLIST (list_store->root);
- list_store->root = G_SLIST (iter->user_data);
- }
-
- /* Emit the reordered signal. */
- new_order = g_new (int, list_store->length);
- if (old_location < new_location)
- for (i = 0; i < list_store->length; i++)
- {
- if (i < old_location ||
- i > new_location)
- new_order[i] = i;
- else if (i >= old_location &&
- i < new_location)
- new_order[i] = i + 1;
- else if (i == new_location)
- new_order[i] = old_location;
- }
- else
- for (i = 0; i < list_store->length; i++)
- {
- if (i < new_location ||
- i > old_location)
- new_order[i] = i;
- else if (i > new_location &&
- i <= old_location)
- new_order[i] = i - 1;
- else if (i == new_location)
- new_order[i] = old_location;
- }
+ _gtk_sequence_sort_changed (iter->user_data,
+ gtk_list_store_compare_func,
+ list_store);
tmp_path = gtk_tree_path_new ();
- tmp_iter.user_data = NULL;
-
- gtk_tree_model_rows_reordered (GTK_TREE_MODEL (list_store),
- tmp_path, NULL,
- new_order);
+ gtk_tree_model_row_changed (GTK_TREE_MODEL (list_store), tmp_path, iter);
gtk_tree_path_free (tmp_path);
- g_free (new_order);
}
static gboolean
Index: gtkliststore.h
===================================================================
RCS file: /cvs/gnome/gtk+/gtk/gtkliststore.h,v
retrieving revision 1.29
diff -u -p -u -r1.29 gtkliststore.h
--- gtkliststore.h 18 Nov 2002 19:33:28 -0000 1.29
+++ gtkliststore.h 7 Aug 2004 20:00:29 -0000
@@ -43,14 +43,14 @@ struct _GtkListStore
/*< private >*/
gint stamp;
- gpointer root;
- gpointer tail;
- GList *sort_list;
+ gpointer seq; /* head of the list */
+ gpointer dummy; /* used to be tail of the list */
+ GList *sort_list; /* a list of 'sort headers' */
gint n_columns;
gint sort_column_id;
GtkSortType order;
GType *column_headers;
- gint length;
+ gint dummy2; /* used to be length */
GtkTreeIterCompareFunc default_sort_func;
gpointer default_sort_data;
GtkDestroyNotify default_sort_destroy;
Attachment:
testtreemodel.c
Description: The testprogram
Attachment:
before
Description: Before data
Attachment:
after
Description: After data