New function.

Sat Aug 14 17:56:33 2004  Soeren Sandmann  <sandmann@daimi.au.dk>

	* gtk/gtkentry.c (gtk_entry_get_pixel_ranges): New function.

	* gtk/gtkentry.c (in_selection): New function using
	gtk_entry_get_pixel_ranges() to determine whether a click is in
	the selection. Improve entry behavior wrt. dragging and
	selecting. Bug #143249.

Sat Aug 14 17:53:46 2004  Soeren Sandmann  <sandmann@daimi.au.dk>

	* configure.in: Require glib 2.5.2

	* gtk/gtksequence.[ch]: New internal data structure.

	* gtk/gtkliststore.[hc]: Reimplement in terms of new data
	structure

	* tests/Makefile.am (testtreemodel_SOURCES):
	* tests/testtreemodel.c: New test program written by Matthias.

6 files changed, 1497 insertions, 881 deletions

diff --git a/gtk/Makefile.am b/gtk/Makefile.am
index 2fde0bfee0..26e223ac9a 100644
--- a/gtk/Makefile.am
+++ b/gtk/Makefile.am
@@ -285,7 +285,7 @@ gtk_semi_private_h_sources =    \
 	gtkfilesystem.h
 
 # GTK+ header files that don't get installed
-gtk_private_h_sources =         \
+gtk_private_h_sources =		\
 	gtkentryprivate.h	\
 	gtkfilechooserembed.h	\
 	gtkfilechooserentry.h	\
@@ -296,9 +296,10 @@ gtk_private_h_sources =         \
 	gtkfilesystemmodel.h	\
 	gtkinternals.h		\
 	gtkpathbar.h		\
-	gtkrbtree.h 		\
+	gtkrbtree.h		\
+	gtksequence.h		\
 	gtktextbtree.h		\
-	gtktextchildprivate.h   \
+	gtktextchildprivate.h	\
 	gtktextsegment.h	\
 	gtktexttypes.h		\
 	gtktextutil.h		\
@@ -441,6 +442,7 @@ gtk_c_sources =                 \
 	gtkscale.c		\
 	gtkscrollbar.c		\
 	gtkscrolledwindow.c	\
+	gtksequence.c		\
 	gtkselection.c		\
 	gtkseparator.c		\
 	gtkseparatormenuitem.c	\
diff --git a/gtk/gtkentry.c b/gtk/gtkentry.c
index c583f3f5cf..82b89b201b 100644
--- a/gtk/gtkentry.c
+++ b/gtk/gtkentry.c
@@ -1400,6 +1400,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)
@@ -1491,21 +1555,18 @@ gtk_entry_button_press (GtkWidget      *widget,
 	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 
@@ -2997,7 +3058,6 @@ static void
 gtk_entry_draw_text (GtkEntry *entry)
 {
   GtkWidget *widget;
-  PangoLayoutLine *line;
   
   if (!entry->visible && entry->invisible_char == 0)
     return;
@@ -3021,19 +3081,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;
-
-          line = pango_layout_get_lines (layout)->data;
-          
-	  pango_layout_line_get_x_ranges (line, start_index, end_index, &ranges, &n_ranges);
+	  GdkGC *selection_gc, *text_gc;
+	  GdkRegion *clip_region;
+
+	  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];
@@ -3045,21 +3098,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,
diff --git a/gtk/gtkliststore.c b/gtk/gtkliststore.c
index 74dcb8cfa4..24ca369f53 100644
--- a/gtk/gtkliststore.c
+++ b/gtk/gtkliststore.c
@@ -25,10 +25,10 @@
 #include "gtkliststore.h"
 #include "gtktreedatalist.h"
 #include "gtktreednd.h"
+#include "gtksequence.h"
 
-#define G_SLIST(x) ((GSList *) x)
 #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);
@@ -113,26 +113,9 @@ static void     gtk_list_store_set_default_sort_func (GtkTreeSortable        *so
 						      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;
 
-
-static void
-validate_list_store (GtkListStore *list_store)
-{
-  if (gtk_debug_flags & GTK_DEBUG_TREE)
-    {
-      g_assert (g_slist_length (list_store->root) == list_store->length);
-
-      g_assert (g_slist_last (list_store->root) == list_store->tail);
-    }
-}
-
 GType
 gtk_list_store_get_type (void)
 {
@@ -257,11 +240,9 @@ gtk_list_store_sortable_init (GtkTreeSortableIface *iface)
 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->sort_list = NULL;
   list_store->stamp = g_random_int ();
-  list_store->length = 0;
   list_store->sort_column_id = -2;
   list_store->columns_dirty = FALSE;
 }
@@ -283,7 +264,7 @@ gtk_list_store_init (GtkListStore *list_store)
  **/
 GtkListStore *
 gtk_list_store_new (gint n_columns,
-			       ...)
+		    ...)
 {
   GtkListStore *retval;
   va_list args;
@@ -441,8 +422,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);
@@ -502,7 +485,7 @@ gtk_list_store_get_iter (GtkTreeModel *tree_model,
 			 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);
@@ -510,18 +493,15 @@ gtk_list_store_get_iter (GtkTreeModel *tree_model,
 
   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;
 }
@@ -530,31 +510,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
@@ -569,8 +536,9 @@ gtk_list_store_get_value (GtkTreeModel *tree_model,
   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;
@@ -589,10 +557,9 @@ gtk_list_store_iter_next (GtkTreeModel  *tree_model,
 {
   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
@@ -600,18 +567,18 @@ gtk_list_store_iter_children (GtkTreeModel *tree_model,
 			      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
@@ -629,11 +596,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;
 }
 
@@ -643,23 +615,24 @@ gtk_list_store_iter_nth_child (GtkTreeModel *tree_model,
 			       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
@@ -712,7 +685,7 @@ gtk_list_store_real_set_value (GtkListStore *list_store,
       converted = TRUE;
     }
 
-  prev = list = G_SLIST (iter->user_data)->data;
+  prev = list = _gtk_sequence_ptr_get_data (iter->user_data);
 
   while (list != NULL)
     {
@@ -735,9 +708,10 @@ gtk_list_store_real_set_value (GtkListStore *list_store,
       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
@@ -930,68 +904,6 @@ gtk_list_store_set (GtkListStore *list_store,
   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
@@ -1008,54 +920,33 @@ gtk_list_store_remove (GtkListStore *list_store,
 		       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);
-
-  validate_list_store (list_store);
-
+  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);
+  
   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;
 }
 
 /**
@@ -1076,9 +967,9 @@ gtk_list_store_insert (GtkListStore *list_store,
 		       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);
@@ -1086,31 +977,15 @@ gtk_list_store_insert (GtkListStore *list_store,
 
   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);
@@ -1135,76 +1010,19 @@ gtk_list_store_insert_before (GtkListStore *list_store,
 			      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;
-    }
-
-  iter->stamp = list_store->stamp;
-  iter->user_data = new_list;
+    after = sibling->user_data;
 
-  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));
 }
 
 /**
@@ -1224,42 +1042,19 @@ gtk_list_store_insert_after (GtkListStore *list_store,
 			     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));
 }
 
 /**
@@ -1276,30 +1071,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);
 }
 
 /**
@@ -1316,37 +1091,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));
 }
 
 /**
@@ -1362,10 +1110,10 @@ gtk_list_store_clear (GtkListStore *list_store)
   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);
     }
 }
@@ -1388,24 +1136,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,
@@ -1521,7 +1261,7 @@ gtk_list_store_drag_data_received (GtkTreeDragDest   *drag_dest,
        */
       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;
@@ -1547,7 +1287,7 @@ gtk_list_store_drag_data_received (GtkTreeDragDest   *drag_dest,
             }
 
 	  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);
@@ -1600,7 +1340,7 @@ gtk_list_store_row_drop_possible (GtkTreeDragDest  *drag_dest,
 
   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:
@@ -1611,11 +1351,6 @@ gtk_list_store_row_drop_possible (GtkTreeDragDest  *drag_dest,
 }
 
 /* Sorting and reordering */
-typedef struct _SortTuple
-{
-  gint offset;
-  GSList *el;
-} SortTuple;
 
 /* Reordering */
 static gint
@@ -1623,20 +1358,17 @@ gtk_list_store_reorder_func (gconstpointer a,
 			     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.
@@ -1654,45 +1386,34 @@ gtk_list_store_reorder (GtkListStore *store,
 			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);
 }
 
 /**
@@ -1711,8 +1432,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));
@@ -1723,270 +1442,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)
+static GHashTable *
+save_positions (GtkSequence *seq)
 {
-  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;
-    }
+  GHashTable *positions = g_hash_table_new (g_direct_hash, g_direct_equal);
+  GtkSequencePtr ptr;
 
-  /*  don't try to reorder the iter to it's own position  */
-  if (a)
+  ptr = _gtk_sequence_get_begin_ptr (seq);
+  while (!_gtk_sequence_ptr_is_end (ptr))
     {
-      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++;
-    }
-
-  /* remove node */
-  if (!prev)
-    store->root = G_SLIST (iter->user_data)->next;
-  else
-    {
-      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);
+  g_hash_table_destroy (old_positions);
 
-  /* 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;
-
-  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);
 }
 
 /**
@@ -2006,7 +1531,20 @@ gtk_list_store_move_before (GtkListStore *store,
                             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);
 }
 
 /**
@@ -2023,12 +1561,25 @@ gtk_list_store_move_before (GtkListStore *store,
  **/
 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,
@@ -2036,15 +1587,12 @@ gtk_list_store_compare_func (gconstpointer a,
 			     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;
@@ -2064,14 +1612,14 @@ gtk_list_store_compare_func (gconstpointer a,
       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)
@@ -2081,63 +1629,32 @@ gtk_list_store_compare_func (gconstpointer a,
       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);
+  old_positions = save_positions (list_store->seq);
 
-  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);
-
-      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
@@ -2146,180 +1663,15 @@ gtk_list_store_sort_iter_changed (GtkListStore *list_store,
 				  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
diff --git a/gtk/gtkliststore.h b/gtk/gtkliststore.h
index bb17678aa0..cd0993c163 100644
--- a/gtk/gtkliststore.h
+++ b/gtk/gtkliststore.h
@@ -43,14 +43,14 @@ struct _GtkListStore
 
   /*< private >*/
   gint stamp;
-  gpointer root;
-  gpointer tail;
-  GList *sort_list;
+  gpointer seq;		/* head of the list */
+  gpointer _gtk_reserved1;
+  GList *sort_list;	
   gint n_columns;
   gint sort_column_id;
   GtkSortType order;
   GType *column_headers;
-  gint length;
+  gint _gtk_reserved2;
   GtkTreeIterCompareFunc default_sort_func;
   gpointer default_sort_data;
   GtkDestroyNotify default_sort_destroy;
diff --git a/gtk/gtksequence.c b/gtk/gtksequence.c
new file mode 100644
index 0000000000..5a569b7d01
--- /dev/null
+++ b/gtk/gtksequence.c
@@ -0,0 +1,1104 @@
+/* GLIB - Library of useful routines for C programming
+ * Copyright (C) 2002  Soeren Sandmann (sandmann@daimi.au.dk)
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include <glib.h>
+
+#include "gtksequence.h"
+
+typedef struct _GtkSequenceNode GtkSequenceNode;
+
+struct _GtkSequence {
+  GtkSequenceNode *node;	/* does not necessarily point to the root.
+				 * You can splay it if you want it to
+				 */
+  GDestroyNotify data_destroy_notify;
+};
+
+struct _GtkSequenceNode {
+  guint is_end  : 1;
+  gint  n_nodes : 31;		/* number of nodes below this node,
+				 * including this node
+				 */
+  GtkSequenceNode *parent;
+  GtkSequenceNode *left;
+  GtkSequenceNode *right;
+  
+  GtkSequence *sequence;
+  
+  gpointer data;
+};
+
+static GtkSequenceNode *_gtk_sequence_node_new          (gpointer          data);
+static GtkSequenceNode *_gtk_sequence_node_find_first   (GtkSequenceNode    *node);
+static GtkSequenceNode *_gtk_sequence_node_find_last    (GtkSequenceNode    *node);
+static GtkSequenceNode *_gtk_sequence_node_find_by_pos  (GtkSequenceNode    *node,
+							 gint pos);
+static GtkSequenceNode *_gtk_sequence_node_prev         (GtkSequenceNode    *node);
+static GtkSequenceNode *_gtk_sequence_node_next         (GtkSequenceNode    *node);
+static gint           _gtk_sequence_node_get_pos (GtkSequenceNode    *node);
+static GtkSequence     *_gtk_sequence_node_get_sequence (GtkSequenceNode    *node);
+static GtkSequenceNode *_gtk_sequence_node_find_closest (GtkSequenceNode    *node,
+							 GtkSequenceNode    *other,
+							 GCompareDataFunc  cmp,
+							 gpointer          data);
+static gint           _gtk_sequence_node_get_length   (GtkSequenceNode    *node);
+static void           _gtk_sequence_node_free         (GtkSequenceNode    *node,
+						       GDestroyNotify    destroy);
+#if 0
+static gboolean       _gtk_sequence_node_is_singleton (GtkSequenceNode    *node);
+#endif
+static void           _gtk_sequence_node_split        (GtkSequenceNode    *node,
+						       GtkSequenceNode   **left,
+						       GtkSequenceNode   **right);
+static void           _gtk_sequence_node_insert_before (GtkSequenceNode *node,
+							GtkSequenceNode *new);
+static void           _gtk_sequence_node_remove        (GtkSequenceNode *node);
+static void           _gtk_sequence_node_insert_sorted (GtkSequenceNode *node,
+							GtkSequenceNode *new,
+							GCompareDataFunc cmp_func,
+							gpointer cmp_data);
+
+/* GtkSequence */
+GtkSequence *
+_gtk_sequence_new                (GDestroyNotify           data_destroy)
+{
+  GtkSequence *seq = g_new (GtkSequence, 1);
+  seq->data_destroy_notify = data_destroy;
+  
+  seq->node = _gtk_sequence_node_new (NULL);
+  seq->node->is_end = TRUE;
+  seq->node->sequence = seq;
+  
+  return seq;
+}
+
+void
+_gtk_sequence_foreach	      (GtkSequence	 *seq,
+			       GFunc		  func,
+			       gpointer		  data)
+{
+  GtkSequencePtr ptr;
+  
+  g_return_if_fail (seq != NULL);
+  g_return_if_fail (func != NULL);
+  
+  ptr = _gtk_sequence_get_begin_ptr (seq);
+  
+  while (!_gtk_sequence_ptr_is_end (ptr))
+    {
+      GtkSequenceNode *node = ptr;
+      
+      func (node->data, data);
+      
+      ptr = _gtk_sequence_ptr_next (ptr);
+    }
+  
+}
+
+void
+_gtk_sequence_free               (GtkSequence               *seq)
+{
+  g_return_if_fail (seq != NULL);
+  
+  _gtk_sequence_node_free (seq->node, seq->data_destroy_notify);
+  
+  g_free (seq);
+}
+
+#if 0
+static void
+flatten_nodes (GtkSequenceNode *node, GList **list)
+{
+  g_print ("flatten %p\n", node);
+  if (!node)
+    return;
+  else if (_gtk_sequence_node_is_singleton (node))
+    *list = g_list_prepend (*list, node);
+  else
+    {
+      GtkSequenceNode *left;
+      GtkSequenceNode *right;
+      
+      _gtk_sequence_node_split (node, &left, &right);
+      
+      flatten_nodes (left, list);
+      flatten_nodes (right, list);
+    }
+}
+#endif
+
+typedef struct SortInfo SortInfo;
+struct SortInfo {
+  GCompareDataFunc cmp;
+  gpointer data;
+};
+
+static gint
+node_compare (gconstpointer n1, gconstpointer n2, gpointer data)
+{
+  SortInfo *info = data;
+  const GtkSequenceNode *node1 = n1;
+  const GtkSequenceNode *node2 = n2;
+  
+  if (node1->is_end)
+    return 1;
+  else if (node2->is_end)
+    return -1;
+  else
+    return (* info->cmp) (node1, node2, info->data);
+}
+
+void
+_gtk_sequence_append             (GtkSequence               *seq,
+				  gpointer                 data)
+{
+  GtkSequenceNode *node, *last;
+  
+  g_return_if_fail (seq != NULL);
+  
+  node = _gtk_sequence_node_new (data);
+  node->sequence = seq;
+  last = _gtk_sequence_node_find_last (seq->node);
+  _gtk_sequence_node_insert_before (last, node);
+}
+
+void
+_gtk_sequence_prepend            (GtkSequence               *seq,
+				  gpointer                 data)
+{
+  GtkSequenceNode *node, *second;
+  
+  g_return_if_fail (seq != NULL);
+  
+  node = _gtk_sequence_node_new (data);
+  node->sequence = seq;
+  second = _gtk_sequence_node_next (_gtk_sequence_node_find_first (seq->node));
+  
+  _gtk_sequence_node_insert_before (second, node);
+}
+
+GtkSequencePtr 
+_gtk_sequence_insert             (GtkSequencePtr             ptr,
+				  gpointer                 data)
+{
+  GtkSequenceNode *node;
+  
+  g_return_val_if_fail (ptr != NULL, NULL);
+  
+  node = _gtk_sequence_node_new (data);
+  node->sequence = ptr->sequence;
+  
+  _gtk_sequence_node_insert_before (ptr, node);
+
+  return node;
+}
+
+static void
+_gtk_sequence_unlink (GtkSequence *seq,
+		      GtkSequenceNode *node)
+{
+  g_assert (!node->is_end);
+  
+  seq->node = _gtk_sequence_node_next (node);
+  
+  g_assert (seq->node);
+  g_assert (seq->node != node);
+  
+  _gtk_sequence_node_remove (node);
+}
+
+void
+_gtk_sequence_remove             (GtkSequencePtr             ptr)
+{
+  GtkSequence *seq;
+  
+  g_return_if_fail (ptr != NULL);
+  g_return_if_fail (!ptr->is_end);
+  
+  seq = _gtk_sequence_node_get_sequence (ptr); 
+  _gtk_sequence_unlink (seq, ptr);
+  _gtk_sequence_node_free (ptr, seq->data_destroy_notify);
+}
+
+void
+_gtk_sequence_sort               (GtkSequence               *seq,
+				  GCompareDataFunc         cmp_func,
+				  gpointer                 cmp_data)
+{
+  GtkSequence *tmp;
+  GtkSequenceNode *begin, *end;
+  
+  g_return_if_fail (seq != NULL);
+  g_return_if_fail (cmp_func != NULL);
+  
+  begin = _gtk_sequence_get_begin_ptr (seq);
+  end   = _gtk_sequence_get_end_ptr (seq);
+  
+  _gtk_sequence_remove_range (begin, end, &tmp);
+  
+  while (_gtk_sequence_get_length (tmp) > 0)
+    {
+      GtkSequenceNode *node = _gtk_sequence_get_begin_ptr (tmp);
+      _gtk_sequence_unlink (tmp, node);
+      
+      _gtk_sequence_node_insert_sorted (seq->node, node, cmp_func, cmp_data);
+    }
+  
+  _gtk_sequence_free (tmp);
+}
+
+gpointer
+_gtk_sequence_ptr_get_data           (GtkSequencePtr             ptr)
+{
+  g_return_val_if_fail (ptr != NULL, NULL);
+  g_return_val_if_fail (!ptr->is_end, NULL);
+  
+  return ptr->data;
+}
+
+GtkSequencePtr
+_gtk_sequence_insert_sorted      (GtkSequence               *seq,
+				  gpointer                 data,
+				  GCompareDataFunc         cmp_func,
+				  gpointer                 cmp_data)
+{
+  GtkSequenceNode *new_node = _gtk_sequence_node_new (data);
+  new_node->sequence = seq;
+  _gtk_sequence_node_insert_sorted (seq->node, new_node, cmp_func, cmp_data);
+  return new_node;
+}
+
+void
+_gtk_sequence_insert_sequence    (GtkSequencePtr             ptr,
+				  GtkSequence               *other_seq)
+{
+  GtkSequenceNode *last;
+  
+  g_return_if_fail (other_seq != NULL);
+  g_return_if_fail (ptr != NULL);
+  
+  last = _gtk_sequence_node_find_last (other_seq->node);
+  _gtk_sequence_node_insert_before (ptr, last);
+  _gtk_sequence_node_remove (last);
+  _gtk_sequence_node_free (last, NULL);
+  other_seq->node = NULL;
+  _gtk_sequence_free (other_seq);
+}
+
+void
+_gtk_sequence_concatenate        (GtkSequence               *seq1,
+				  GtkSequence               *seq2)
+{
+  GtkSequenceNode *last;
+  
+  g_return_if_fail (seq1 != NULL);
+  g_return_if_fail (seq2 != NULL);
+  
+  last = _gtk_sequence_node_find_last (seq1->node);
+  _gtk_sequence_insert_sequence (last, seq2);
+}
+
+/*
+ * The new sequence inherits the destroy notify from the sequence that
+ * beign and end comes from
+ */
+void
+_gtk_sequence_remove_range       (GtkSequencePtr             begin,
+				  GtkSequencePtr             end,
+				  GtkSequence              **removed)
+{
+  GtkSequence *seq;
+  GtkSequenceNode *s1, *s2, *s3;
+  
+  seq = _gtk_sequence_node_get_sequence (begin);
+  
+  g_assert (end != NULL);
+  
+  g_return_if_fail (seq == _gtk_sequence_node_get_sequence (end));
+  
+  _gtk_sequence_node_split (begin, &s1, &s2);
+  _gtk_sequence_node_split (end, NULL, &s3);
+  
+  if (s1)
+    _gtk_sequence_node_insert_before (s3, s1);
+  
+  seq->node = s3;
+  
+  if (removed)
+    {
+      *removed = _gtk_sequence_new (seq->data_destroy_notify);
+      _gtk_sequence_node_insert_before ((*removed)->node, s2);
+    }
+  else
+    {
+      _gtk_sequence_node_free (s2, seq->data_destroy_notify);
+    }
+}
+
+gint
+_gtk_sequence_get_length         (GtkSequence               *seq)
+{
+  return _gtk_sequence_node_get_length (seq->node) - 1;
+}
+
+GtkSequencePtr
+_gtk_sequence_get_end_ptr        (GtkSequence               *seq)
+{
+  g_return_val_if_fail (seq != NULL, NULL);
+  return _gtk_sequence_node_find_last (seq->node);
+}
+
+GtkSequencePtr
+_gtk_sequence_get_begin_ptr      (GtkSequence               *seq)
+{
+  g_return_val_if_fail (seq != NULL, NULL);
+  return _gtk_sequence_node_find_first (seq->node);
+}
+
+/*
+ * if pos > number of items or -1, will return end pointer
+ */
+GtkSequencePtr
+_gtk_sequence_get_ptr_at_pos     (GtkSequence               *seq,
+				  gint                     pos)
+{
+  gint len;
+  
+  g_return_val_if_fail (seq != NULL, NULL);
+  
+  len = _gtk_sequence_get_length (seq);
+  
+  if (pos > len || pos == -1)
+    pos = len;
+  
+  return _gtk_sequence_node_find_by_pos (seq->node, pos);
+}
+
+
+/* GtkSequencePtr */
+gboolean
+_gtk_sequence_ptr_is_end         (GtkSequencePtr             ptr)
+{
+  g_return_val_if_fail (ptr != NULL, FALSE);
+  return ptr->is_end;
+}
+
+gboolean
+_gtk_sequence_ptr_is_begin       (GtkSequencePtr             ptr)
+{
+  return (_gtk_sequence_node_prev (ptr) == ptr);
+}
+
+gint
+_gtk_sequence_ptr_get_position   (GtkSequencePtr             ptr)
+{
+  g_return_val_if_fail (ptr != NULL, -1);
+  
+  return _gtk_sequence_node_get_pos (ptr);
+}
+
+GtkSequencePtr
+_gtk_sequence_ptr_next           (GtkSequencePtr             ptr)
+{
+  g_return_val_if_fail (ptr != NULL, NULL);
+  
+  return _gtk_sequence_node_next (ptr);
+}
+
+GtkSequencePtr
+_gtk_sequence_ptr_prev           (GtkSequencePtr             ptr)
+{
+  g_return_val_if_fail (ptr != NULL, NULL);
+  
+  return _gtk_sequence_node_prev (ptr);
+}
+
+GtkSequencePtr
+_gtk_sequence_ptr_move           (GtkSequencePtr             ptr,
+				  guint                    delta)
+{
+  gint new_pos;
+  
+  g_return_val_if_fail (ptr != NULL, NULL);
+  
+  new_pos = _gtk_sequence_node_get_pos (ptr) + delta;
+  
+  return _gtk_sequence_node_find_by_pos (ptr, new_pos);
+}
+
+void
+_gtk_sequence_sort_changed  (GtkSequencePtr	     ptr,
+			     GCompareDataFunc	     cmp_func,
+			     gpointer		     cmp_data)
+  
+{
+  GtkSequence *seq;
+  
+  g_return_if_fail (!ptr->is_end);
+  
+  seq = _gtk_sequence_node_get_sequence (ptr);
+  _gtk_sequence_unlink (seq, ptr);
+  _gtk_sequence_node_insert_sorted (seq->node, ptr, cmp_func, cmp_data);
+}
+
+/* search
+ *
+ * The only restriction on the search function is that it
+ * must not delete any nodes. It is permitted to insert new nodes,
+ * but the caller should "know what he is doing"
+ */
+void
+_gtk_sequence_search             (GtkSequence               *seq,
+				  GtkSequenceSearchFunc      f,
+				  gpointer                 data)
+{
+  GQueue *intervals = g_queue_new ();
+  
+  g_queue_push_tail (intervals, _gtk_sequence_node_find_first (seq->node));
+  g_queue_push_tail (intervals, _gtk_sequence_node_find_last (seq->node));
+  
+  while (!g_queue_is_empty (intervals))
+    {
+      GtkSequenceNode *begin = g_queue_pop_head (intervals);
+      GtkSequenceNode *end   = g_queue_pop_head (intervals);
+      
+      if (f (begin, end, data))
+	{
+	  gint begin_pos = _gtk_sequence_node_get_pos (begin);
+	  gint end_pos   = _gtk_sequence_node_get_pos (end);
+	  
+	  if (end_pos - begin_pos > 1)
+	    {
+	      GtkSequenceNode *mid;
+	      gint mid_pos;
+	      
+	      mid_pos = begin_pos + (end_pos - begin_pos) / 2;
+	      mid = _gtk_sequence_node_find_by_pos (begin, mid_pos);
+	      
+	      g_queue_push_tail (intervals, begin);
+	      g_queue_push_tail (intervals, mid);
+	      
+	      g_queue_push_tail (intervals, mid);
+	      g_queue_push_tail (intervals, end);
+	    }
+	}
+    }
+  
+  g_queue_free (intervals);
+}
+
+#if 0
+/* aggregates */
+void
+_gtk_sequence_add_aggregate      (GtkSequence               *seq,
+				  const gchar             *aggregate,
+				  GtkSequenceAggregateFunc   f,
+				  gpointer                 data,
+				  GDestroyNotify           destroy)
+{
+  /* FIXME */
+}
+
+void
+_gtk_sequence_remove_aggregate   (GtkSequence               *seq,
+				  const gchar              aggregate)
+{
+  /* FIXME */
+  
+}
+
+void
+_gtk_sequence_set_aggregate_data (GtkSequencePtr             ptr,
+				  const gchar             *aggregate,
+				  gpointer                 data)
+{
+  /* FIXME */
+  
+}
+
+gpointer
+_gtk_sequence_get_aggregate_data (GtkSequencePtr             begin,
+				  GtkSequencePtr             end,
+				  const gchar             *aggregate)
+{
+  g_assert_not_reached();
+  return NULL;
+}
+#endif
+
+
+/* Nodes
+ */
+static void
+_gtk_sequence_node_update_fields (GtkSequenceNode *node)
+{
+  g_assert (node != NULL);
+  
+  node->n_nodes = 1;
+  
+  if (node->left)
+    node->n_nodes += node->left->n_nodes;
+  
+  if (node->right)
+    node->n_nodes += node->right->n_nodes;
+  
+#if 0
+  if (node->left || node->right)
+    g_assert (node->n_nodes > 1);
+#endif
+}
+
+#define NODE_LEFT_CHILD(n)  (((n)->parent) && ((n)->parent->left) == (n))
+#define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
+
+static void
+_gtk_sequence_node_rotate (GtkSequenceNode *node)
+{
+  GtkSequenceNode *tmp, *old;
+  
+  g_assert (node->parent);
+  g_assert (node->parent != node);
+  
+  if (NODE_LEFT_CHILD (node))
+    {
+      /* rotate right */
+      tmp = node->right;
+      
+      node->right = node->parent;
+      node->parent = node->parent->parent;
+      if (node->parent)
+	{
+	  if (node->parent->left == node->right)
+	    node->parent->left = node;
+	  else
+	    node->parent->right = node;
+	}
+      
+      g_assert (node->right);
+      
+      node->right->parent = node;
+      node->right->left = tmp;
+      
+      if (node->right->left)
+	node->right->left->parent = node->right;
+      
+      old = node->right;
+    }
+  else
+    {
+      /* rotate left */
+      tmp = node->left;
+      
+      node->left = node->parent;
+      node->parent = node->parent->parent;
+      if (node->parent)
+	{
+	  if (node->parent->right == node->left)
+	    node->parent->right = node;
+	  else
+	    node->parent->left = node;
+	}
+      
+      g_assert (node->left);
+      
+      node->left->parent = node;
+      node->left->right = tmp;
+      
+      if (node->left->right)
+	node->left->right->parent = node->left;
+      
+      old = node->left;
+    }
+  
+  _gtk_sequence_node_update_fields (old);
+  _gtk_sequence_node_update_fields (node);
+}
+
+static GtkSequenceNode *
+splay (GtkSequenceNode *node)
+{
+  while (node->parent)
+    {
+      if (!node->parent->parent)
+	{
+	  /* zig */
+	  _gtk_sequence_node_rotate (node);
+	}
+      else if ((NODE_LEFT_CHILD (node) && NODE_LEFT_CHILD (node->parent)) ||
+	       (NODE_RIGHT_CHILD (node) && NODE_RIGHT_CHILD (node->parent)))
+	{
+	  /* zig-zig */
+	  _gtk_sequence_node_rotate (node->parent);
+	  _gtk_sequence_node_rotate (node);
+	}
+      else
+	{
+	  /* zig-zag */
+	  _gtk_sequence_node_rotate (node);
+	  _gtk_sequence_node_rotate (node);
+	}
+    }
+  
+  return node;
+}
+
+static GtkSequenceNode *
+_gtk_sequence_node_new (gpointer          data)
+{
+  GtkSequenceNode *node = g_new0 (GtkSequenceNode, 1);
+  
+  node->parent = NULL;
+  node->left = NULL;
+  node->right = NULL;
+  
+  node->data = data;
+  node->is_end = FALSE;
+  node->n_nodes = 1;
+  
+  return node;
+}
+
+static GtkSequenceNode *
+find_min (GtkSequenceNode *node)
+{
+  splay (node);
+  
+  while (node->left)
+    node = node->left;
+  
+  return node;
+}
+
+static GtkSequenceNode *
+find_max (GtkSequenceNode *node)
+{
+  splay (node);
+  
+  while (node->right)
+    node = node->right;
+  
+  return node;
+}
+
+static GtkSequenceNode *
+_gtk_sequence_node_find_first   (GtkSequenceNode    *node)
+{
+  return splay (find_min (node));
+}
+
+static GtkSequenceNode *
+_gtk_sequence_node_find_last    (GtkSequenceNode    *node)
+{
+  return splay (find_max (node));
+}
+
+static gint
+get_n_nodes (GtkSequenceNode *node)
+{
+  if (node)
+    return node->n_nodes;
+  else
+    return 0;
+}
+
+static GtkSequenceNode *
+_gtk_sequence_node_find_by_pos  (GtkSequenceNode    *node,
+				 gint              pos)
+{
+  gint i;
+  
+  g_assert (node != NULL);
+  
+  splay (node);
+  
+  while ((i = get_n_nodes (node->left)) != pos)
+    {
+      if (i < pos)
+	{
+	  node = node->right;
+	  pos -= (i + 1);
+	}
+      else
+	{
+	  node = node->left;
+	  g_assert (node->parent != NULL);
+	}
+    }
+  
+  return splay (node);
+}
+
+static GtkSequenceNode *
+_gtk_sequence_node_prev         (GtkSequenceNode    *node)
+{
+  splay (node);
+  
+  if (node->left)
+    {
+      node = node->left;
+      while (node->right)
+	node = node->right;
+    }
+  
+  return splay (node);
+}
+
+static GtkSequenceNode *
+_gtk_sequence_node_next         (GtkSequenceNode    *node)
+{
+  splay (node);
+  
+  if (node->right)
+    {
+      node = node->right;
+      while (node->left)
+	node = node->left;
+    }
+  
+  return splay (node);
+}
+
+static gint
+_gtk_sequence_node_get_pos (GtkSequenceNode    *node)
+{
+  splay (node);
+  
+  return get_n_nodes (node->left);
+}
+
+static GtkSequence *
+_gtk_sequence_node_get_sequence (GtkSequenceNode    *node)
+{
+  splay (node);
+  
+  return node->sequence;
+}
+
+static GtkSequenceNode *
+_gtk_sequence_node_find_closest (GtkSequenceNode    *node,
+				 GtkSequenceNode    *other,
+				 GCompareDataFunc  cmp,
+				 gpointer          data)
+{
+  GtkSequenceNode *best;
+  gint c;
+  
+  splay (node);
+
+  do
+    {
+      best = node;
+
+      if ((c = cmp (node, other, data)) != 0)
+	{
+	  if (c < 0)
+	    node = node->right;
+	  else
+	    node = node->left;
+	}
+    }
+  while (c != 0 && node != NULL);
+  
+  return best;
+}
+
+static void
+_gtk_sequence_node_free         (GtkSequenceNode    *node,
+				 GDestroyNotify    destroy)
+{
+  /* FIXME:
+   *
+   * This is to avoid excessively deep recursions. A splay tree is not necessarily
+   * balanced at all.
+   *
+   * I _think_ this is still linear in the number of nodes, but I'd like to
+   * do something more efficient.
+   */
+  
+  while (node)
+    {
+      GtkSequenceNode *next;
+      
+      node = splay (find_min (node));
+      next = node->right;
+      if (next)
+	next->parent = NULL;
+      
+      if (destroy && !node->is_end)
+	destroy (node->data);
+      g_free (node);
+      
+      node = next;
+    }
+}
+
+#if 0
+static gboolean
+_gtk_sequence_node_is_singleton (GtkSequenceNode    *node)
+{
+  splay (node);
+  
+  if (node->left || node->right)
+    return FALSE;
+  
+  return TRUE;
+}
+#endif
+
+static void
+_gtk_sequence_node_split        (GtkSequenceNode    *node,
+				 GtkSequenceNode   **left,
+				 GtkSequenceNode   **right)
+{
+  GtkSequenceNode *left_tree;
+  
+  splay (node);
+  
+  left_tree = node->left;
+  if (left_tree)
+    {
+      left_tree->parent = NULL;
+      _gtk_sequence_node_update_fields (left_tree);
+    }
+  
+  node->left = NULL;
+  _gtk_sequence_node_update_fields (node);
+  
+  if (left)
+    *left = left_tree;
+  
+  if (right)
+    *right = node;
+}
+
+static void
+_gtk_sequence_node_insert_before (GtkSequenceNode *node,
+				  GtkSequenceNode *new)
+{
+  g_assert (node != NULL);
+  g_assert (new != NULL);
+  
+  splay (node);
+  
+  new = splay (find_min (new));
+  g_assert (new->left == NULL);
+  
+  if (node->left)
+    node->left->parent = new;
+  
+  new->left = node->left;
+  new->parent = node;
+  
+  node->left = new;
+  
+  _gtk_sequence_node_update_fields (new);
+  _gtk_sequence_node_update_fields (node);
+}
+
+static gint
+_gtk_sequence_node_get_length (GtkSequenceNode    *node)
+{
+  g_assert (node != NULL);
+  
+  splay (node);
+  return node->n_nodes;
+}
+
+static void
+_gtk_sequence_node_remove        (GtkSequenceNode *node)
+{
+  GtkSequenceNode *right, *left;
+  
+  splay (node);
+  
+  left = node->left;
+  right = node->right;
+  
+  node->left = node->right = NULL;
+  
+  if (right)
+    {
+      right->parent = NULL;
+      
+      right = _gtk_sequence_node_find_first (right);
+      g_assert (right->left == NULL);
+      
+      right->left = left;
+      if (left)
+	{
+	  left->parent = right;
+	  _gtk_sequence_node_update_fields (right);
+	}
+    }
+  else if (left)
+    left->parent = NULL;
+}
+
+#if 0
+/* debug func */
+static gint
+_gtk_sequence_node_calc_height (GtkSequenceNode *node)
+{
+  /* breadth first traversal */
+  gint height = 0;
+  GQueue *nodes = g_queue_new ();
+  
+  g_queue_push_tail (nodes, node);
+  
+  while (!g_queue_is_empty (nodes))
+    {
+      GQueue *tmp = g_queue_new ();
+      
+      height++;
+      while (!g_queue_is_empty (nodes))
+	{
+	  GtkSequenceNode *node = g_queue_pop_head (nodes);
+	  if (node->left)
+	    g_queue_push_tail (tmp, node->left);
+	  if (node->right)
+	    g_queue_push_tail (tmp, node->right);
+	}
+      
+      g_queue_free (nodes);
+      
+      nodes = tmp;
+    }
+  g_queue_free (nodes);
+  
+  return height;
+}
+#endif
+
+static void
+_gtk_sequence_node_insert_sorted (GtkSequenceNode *node,
+				  GtkSequenceNode *new,
+				  GCompareDataFunc cmp_func,
+				  gpointer cmp_data)
+{
+  SortInfo info;
+  GtkSequenceNode *closest;
+  info.cmp = cmp_func;
+  info.data = cmp_data;
+  
+  closest =
+    _gtk_sequence_node_find_closest (node, new, node_compare, &info);
+
+  g_assert (closest != new);
+  
+  if (node_compare (new, closest, &info) > 0)
+    closest = _gtk_sequence_node_next (closest);
+  
+  /* this can never fail since we have a bigger-than-everything
+   * end-node
+   */
+  g_assert (node_compare (new, closest, &info) <= 0);
+  _gtk_sequence_node_insert_before (closest, new);
+}
+
+static gint
+_gtk_sequence_node_calc_height (GtkSequenceNode *node)
+{
+  gint left_height;
+  gint right_height;
+  
+  if (node)
+    {
+      left_height = 0;
+      right_height = 0;
+      
+      if (node->left)
+	left_height = _gtk_sequence_node_calc_height (node->left);
+      
+      if (node->right)
+	right_height = _gtk_sequence_node_calc_height (node->right);
+      
+      return MAX (left_height, right_height) + 1;
+    }
+  
+  return 0;
+}
+
+gint
+_gtk_sequence_calc_tree_height   (GtkSequence               *seq)
+{
+  GtkSequenceNode *node = seq->node;
+  gint r, l;
+  while (node->parent)
+    node = node->parent;
+  
+  if (node)
+    {
+      r = _gtk_sequence_node_calc_height (node->right);
+      l = _gtk_sequence_node_calc_height (node->left);
+      
+      return MAX (r, l) + 1;
+    }
+  else
+    return 0;
+}
+
+GtkSequence   *
+_gtk_sequence_ptr_get_sequence (GtkSequencePtr	  ptr)
+{
+  GtkSequenceNode *node = ptr;
+  
+  return node->sequence;
+}
+
+void
+_gtk_sequence_swap (GtkSequencePtr a,
+		    GtkSequencePtr b)
+{
+  GtkSequenceNode temp;
+  gpointer temp_data;
+  
+  g_return_if_fail (!_gtk_sequence_ptr_is_end (a));
+  g_return_if_fail (!_gtk_sequence_ptr_is_end (b));
+  
+  /* swap contents of the nodes */
+  temp = *a;
+  *a = *b;
+  *b = temp;
+  
+  /* swap data back */
+  temp_data = a->data;
+  a->data = b->data;
+  b->data = temp_data;
+}
+
+void
+_gtk_sequence_move (GtkSequencePtr ptr,
+		    GtkSequencePtr new_pos)
+{
+  _gtk_sequence_unlink (ptr->sequence, ptr);
+  _gtk_sequence_node_insert_before (new_pos, ptr);
+}
+
+/* Overwrites the existing pointer. */
+void
+_gtk_sequence_set	      (GtkSequencePtr	  ptr,
+			       gpointer		  data)
+{
+  g_return_if_fail (!_gtk_sequence_ptr_is_end (ptr));
+  
+  GtkSequence *seq = _gtk_sequence_node_get_sequence (ptr);
+  if (seq->data_destroy_notify)
+    seq->data_destroy_notify (ptr->data);
+  ptr->data = data;
+}
diff --git a/gtk/gtksequence.h b/gtk/gtksequence.h
new file mode 100644
index 0000000000..a61cf5aed4
--- /dev/null
+++ b/gtk/gtksequence.h
@@ -0,0 +1,104 @@
+/* GLIB - Library of useful routines for C programming
+ * Copyright (C) 2002  Soeren Sandmann (sandmann@daimi.au.dk)
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include <glib.h>
+
+#ifndef __GSEQUENCE_H__
+#define __GSEQUENCE_H__
+
+
+/* Warning
+ *
+ * Do not use this API. It is here, internal to gtk+, for 2.6 only.
+ * In 2.8 the plan is to add a similar data structure to GLib. 
+ */
+
+typedef struct _GtkSequence      GtkSequence;
+typedef struct _GtkSequenceNode *GtkSequencePtr;
+
+/* GtkSequence */
+GtkSequence *  _gtk_sequence_new              (GDestroyNotify     data_destroy);
+void           _gtk_sequence_free             (GtkSequence       *seq);
+void           _gtk_sequence_sort             (GtkSequence       *seq,
+					       GCompareDataFunc   cmp_func,
+					       gpointer           cmp_data);
+void           _gtk_sequence_append           (GtkSequence       *seq,
+					       gpointer           data);
+void           _gtk_sequence_prepend          (GtkSequence       *seq,
+					       gpointer           data);
+GtkSequencePtr _gtk_sequence_insert           (GtkSequencePtr     ptr,
+					       gpointer           data);
+void           _gtk_sequence_remove           (GtkSequencePtr     ptr);
+void	       _gtk_sequence_move             (GtkSequencePtr     ptr,
+					       GtkSequencePtr	  pos);
+void	       _gtk_sequence_swap             (GtkSequencePtr     a,
+					       GtkSequencePtr	  b);
+GtkSequencePtr _gtk_sequence_insert_sorted    (GtkSequence       *seq,
+					       gpointer           data,
+					       GCompareDataFunc   cmp_func,
+					       gpointer           cmp_data);
+void	       _gtk_sequence_set	      (GtkSequencePtr	  ptr,
+					       gpointer		  data);
+void           _gtk_sequence_insert_sequence  (GtkSequencePtr     ptr,
+					       GtkSequence       *other_seq);
+void           _gtk_sequence_concatenate      (GtkSequence       *seq1,
+					       GtkSequence       *seq);
+void           _gtk_sequence_remove_range     (GtkSequencePtr     begin,
+					       GtkSequencePtr     end,
+					       GtkSequence      **removed);
+gint           _gtk_sequence_get_length       (GtkSequence       *seq);
+GtkSequencePtr _gtk_sequence_get_end_ptr      (GtkSequence       *seq);
+GtkSequencePtr _gtk_sequence_get_begin_ptr    (GtkSequence       *seq);
+GtkSequencePtr _gtk_sequence_get_ptr_at_pos   (GtkSequence       *seq,
+					       gint               pos);
+void           _gtk_sequence_sort_changed     (GtkSequencePtr     ptr,
+					       GCompareDataFunc   cmp_func,
+					       gpointer           cmp_data);
+void	       _gtk_sequence_foreach	      (GtkSequence	 *seq,
+					       GFunc		  func,
+					       gpointer		  data);
+
+/* GtkSequencePtr */
+gboolean       _gtk_sequence_ptr_is_end       (GtkSequencePtr     ptr);
+gboolean       _gtk_sequence_ptr_is_begin     (GtkSequencePtr     ptr);
+gint           _gtk_sequence_ptr_get_position (GtkSequencePtr     ptr);
+GtkSequencePtr _gtk_sequence_ptr_next         (GtkSequencePtr     ptr);
+GtkSequencePtr _gtk_sequence_ptr_prev         (GtkSequencePtr     ptr);
+GtkSequencePtr _gtk_sequence_ptr_move         (GtkSequencePtr     ptr,
+					       guint              leap);
+gpointer       _gtk_sequence_ptr_get_data     (GtkSequencePtr     ptr);
+GtkSequence   *_gtk_sequence_ptr_get_sequence (GtkSequencePtr	  ptr);
+
+/* search */
+
+/* return TRUE if you want to be called again with two
+ * smaller segments
+ */
+typedef gboolean (* GtkSequenceSearchFunc) (GtkSequencePtr begin,
+					     GtkSequencePtr end,
+					     gpointer     data);
+
+void         _gtk_sequence_search             (GtkSequence               *seq,
+					       GtkSequenceSearchFunc      f,
+					       gpointer                 data);
+
+/* debug */
+gint         _gtk_sequence_calc_tree_height   (GtkSequence               *seq);
+
+#endif /* __GSEQUENCE_H__ */