Patch by Soren Sandmann

2003-06-27  Alexander Larsson  <alexl@redhat.com>

        Patch by Soren Sandmann

	* configure.in:
	CFLAGS for gsequence

	* cut-n-paste-code/Makefile.am:
	* cut-n-paste-code/gsequence/.cvsignore:
	* cut-n-paste-code/gsequence/Makefile.am:
	* cut-n-paste-code/gsequence/gsequence.[ch]:
	New cut-n-paste lib for gsequence (by Soren Sandmann)

	* src/Makefile.am:
	Link to gsequence

	* src/file-manager/fm-list-model.c:
	Use gsequence plus a reverse mapping hashtable.

9 files changed, 1251 insertions, 208 deletions

diff --git a/ChangeLog b/ChangeLog
index 8dde65af3..060194409 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,24 @@
 2003-06-27  Alexander Larsson  <alexl@redhat.com>
 
+        Patch by Soren Sandmann
+	
+	* configure.in:
+	CFLAGS for gsequence
+	
+	* cut-n-paste-code/Makefile.am:
+	* cut-n-paste-code/gsequence/.cvsignore:
+	* cut-n-paste-code/gsequence/Makefile.am:
+	* cut-n-paste-code/gsequence/gsequence.[ch]:
+	New cut-n-paste lib for gsequence (by Soren Sandmann)
+	
+	* src/Makefile.am:
+	Link to gsequence
+	
+	* src/file-manager/fm-list-model.c:
+	Use gsequence plus a reverse mapping hashtable.
+
+2003-06-27  Alexander Larsson  <alexl@redhat.com>
+
 	This is based on a patch by Jürg Billeter <j@bitron.ch> which was
 	partly based on a patch by Wolfgang Pichler <madmin@dialog-telekom.at>.
 
diff --git a/configure.in b/configure.in
index 8d4612f42..dda913b40 100644
--- a/configure.in
+++ b/configure.in
@@ -293,6 +293,11 @@ GIMPHWRAPBOX_MODULES="gtk+-2.0"
 GIMPHWRAPBOX_CFLAGS="`$PKG_CONFIG --cflags $GIMPHWRAPBOX_MODULES`"
 AC_SUBST(GIMPHWRAPBOX_CFLAGS)
 
+dnl gsequence
+GSEQUENCE_MODULES="glib-2.0"
+GSEQUENCE_CFLAGS="`$PKG_CONFIG --cflags $GSEQUENCE_MODULES`"
+AC_SUBST(GSEQUENCE_CFLAGS)
+	
 dnl libegg
 LIBEGG_MODULES="gtk+-2.0 libgnome-2.0"
 LIBEGG_CFLAGS="`$PKG_CONFIG --cflags $LIBEGG_MODULES`"
@@ -387,6 +392,7 @@ components/emblem/Makefile
 components/image_properties/Makefile
 cut-n-paste-code/Makefile
 cut-n-paste-code/libegg/Makefile
+cut-n-paste-code/gsequence/Makefile
 cut-n-paste-code/widgets/Makefile
 cut-n-paste-code/widgets/gimphwrapbox/Makefile
 data/Makefile
diff --git a/cut-n-paste-code/Makefile.am b/cut-n-paste-code/Makefile.am
index dd85ee073..fc3b8bc05 100644
--- a/cut-n-paste-code/Makefile.am
+++ b/cut-n-paste-code/Makefile.am
@@ -1,2 +1,2 @@
-SUBDIRS = widgets libegg
+SUBDIRS = widgets libegg gsequence
 
diff --git a/cut-n-paste-code/gsequence/.cvsignore b/cut-n-paste-code/gsequence/.cvsignore
new file mode 100644
index 000000000..282522db0
--- /dev/null
+++ b/cut-n-paste-code/gsequence/.cvsignore
@@ -0,0 +1,2 @@
+Makefile
+Makefile.in
diff --git a/cut-n-paste-code/gsequence/Makefile.am b/cut-n-paste-code/gsequence/Makefile.am
new file mode 100644
index 000000000..5849efc91
--- /dev/null
+++ b/cut-n-paste-code/gsequence/Makefile.am
@@ -0,0 +1,10 @@
+NULL=
+
+noinst_LTLIBRARIES = libgsequence.la
+
+INCLUDES = $(GSEQUENCE_CFLAGS)
+
+libgsequence_la_SOURCES = \
+	gsequence.c \
+	gsequence.h \
+	$(NULL)
diff --git a/cut-n-paste-code/gsequence/gsequence.c b/cut-n-paste-code/gsequence/gsequence.c
new file mode 100644
index 000000000..eb17a6842
--- /dev/null
+++ b/cut-n-paste-code/gsequence/gsequence.c
@@ -0,0 +1,1024 @@
+/* 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 "gsequence.h"
+
+typedef struct _GSequenceNode GSequenceNode;
+
+struct _GSequence {
+    GSequenceNode *node;	/* does not necessarily point to the root.
+				 * You can splay it if you want it to
+				 */
+    GDestroyNotify data_destroy_notify;
+};
+
+struct _GSequenceNode {
+    guint is_end  : 1;
+    gint  n_nodes : 31;		/* number of nodes below this node,
+				 * including this node
+				 */
+    GSequenceNode *parent;
+    GSequenceNode *left;
+    GSequenceNode *right;
+
+    GSequence *sequence;
+    
+    gpointer data;
+};
+
+static GSequenceNode *g_sequence_node_new          (gpointer          data);
+static GSequenceNode *g_sequence_node_find_first   (GSequenceNode    *node);
+static GSequenceNode *g_sequence_node_find_last    (GSequenceNode    *node);
+static GSequenceNode *g_sequence_node_find_by_pos  (GSequenceNode    *node,
+						    gint pos);
+static GSequenceNode *g_sequence_node_prev         (GSequenceNode    *node);
+static GSequenceNode *g_sequence_node_next         (GSequenceNode    *node);
+static gint           g_sequence_node_get_pos (GSequenceNode    *node);
+static GSequence     *g_sequence_node_get_sequence (GSequenceNode    *node);
+static GSequenceNode *g_sequence_node_find_closest (GSequenceNode    *node,
+						    GSequenceNode    *other,
+						    GCompareDataFunc  cmp,
+						    gpointer          data);
+static gint           g_sequence_node_get_length   (GSequenceNode    *node);
+static void           g_sequence_node_free         (GSequenceNode    *node,
+						    GDestroyNotify    destroy);
+#if 0
+static gboolean       g_sequence_node_is_singleton (GSequenceNode    *node);
+#endif
+static void           g_sequence_node_split        (GSequenceNode    *node,
+						    GSequenceNode   **left,
+						    GSequenceNode   **right);
+static void           g_sequence_node_insert_before (GSequenceNode *node,
+						     GSequenceNode *new);
+static void           g_sequence_node_remove        (GSequenceNode *node);
+static void           g_sequence_node_insert_sorted (GSequenceNode *node,
+						     GSequenceNode *new,
+						     GCompareDataFunc cmp_func,
+						     gpointer cmp_data);
+
+
+/* GSequence */
+GSequence *
+g_sequence_new                (GDestroyNotify           data_destroy)
+{
+    GSequence *seq = g_new (GSequence, 1);
+    seq->data_destroy_notify = data_destroy;
+
+    seq->node = g_sequence_node_new (NULL);
+    seq->node->is_end = TRUE;
+    seq->node->sequence = seq;
+    
+    return seq;
+}
+
+void
+g_sequence_free               (GSequence               *seq)
+{
+    g_return_if_fail (seq != NULL);
+
+    g_sequence_node_free (seq->node, seq->data_destroy_notify);
+
+    g_free (seq);
+}
+
+#if 0
+static void
+flatten_nodes (GSequenceNode *node, GList **list)
+{
+    g_print ("flatten %p\n", node);
+    if (!node)
+	return;
+    else if (g_sequence_node_is_singleton (node))
+	*list = g_list_prepend (*list, node);
+    else
+    {
+	GSequenceNode *left;
+	GSequenceNode *right;
+
+	g_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 GSequenceNode *node1 = n1;
+    const GSequenceNode *node2 = n2;
+
+    if (node1->is_end)
+	return 1;
+    else if (node2->is_end)
+	return -1;
+    else
+	return (* info->cmp) (node1->data, node2->data, info->data);
+}
+
+void
+g_sequence_append             (GSequence               *seq,
+			       gpointer                 data)
+{
+    GSequenceNode *node, *last;
+
+    g_return_if_fail (seq != NULL);
+
+    node = g_sequence_node_new (data);
+    node->sequence = seq;
+    last = g_sequence_node_find_last (seq->node);
+    g_sequence_node_insert_before (last, node);
+}
+
+void
+g_sequence_prepend            (GSequence               *seq,
+			       gpointer                 data)
+{
+    GSequenceNode *node, *second;
+
+    g_return_if_fail (seq != NULL);
+    
+    node = g_sequence_node_new (data);
+    node->sequence = seq;
+    second = g_sequence_node_next (g_sequence_node_find_first (seq->node));
+    
+    g_sequence_node_insert_before (second, node);
+}
+
+void
+g_sequence_insert             (GSequencePtr             ptr,
+			       gpointer                 data)
+{
+    GSequenceNode *node;
+    
+    g_return_if_fail (ptr != NULL);
+
+    node = g_sequence_node_new (data);
+    node->sequence = ptr->sequence;
+
+    g_sequence_node_insert_before (ptr, node);
+}
+
+static void
+g_sequence_unlink (GSequence *seq,
+		   GSequenceNode *node)
+{
+    g_assert (!node->is_end);
+
+    seq->node = g_sequence_node_next (node);
+
+    g_assert (seq->node);
+    g_assert (seq->node != node);
+
+    g_sequence_node_remove (node);
+}
+
+void
+g_sequence_remove             (GSequencePtr             ptr)
+{
+    GSequence *seq;
+    
+    g_return_if_fail (ptr != NULL);
+    g_return_if_fail (!ptr->is_end);
+
+    seq = g_sequence_node_get_sequence (ptr); 
+    g_sequence_unlink (seq, ptr);
+    g_sequence_node_free (ptr, seq->data_destroy_notify);
+}
+
+void
+g_sequence_sort               (GSequence               *seq,
+			       GCompareDataFunc         cmp_func,
+			       gpointer                 cmp_data)
+{
+    GSequence *tmp;
+    GSequenceNode *begin, *end;
+
+    g_return_if_fail (seq != NULL);
+    g_return_if_fail (cmp_func != NULL);
+
+    begin = g_sequence_get_begin_ptr (seq);
+    end   = g_sequence_get_end_ptr (seq);
+
+    g_sequence_remove_range (begin, end, &tmp);
+
+    while (g_sequence_get_length (tmp) > 0)
+    {
+	GSequenceNode *node = g_sequence_get_begin_ptr (tmp);
+	g_sequence_unlink (tmp, node);
+
+	g_sequence_node_insert_sorted (seq->node, node, cmp_func, cmp_data);
+    }
+
+    g_sequence_free (tmp);
+}
+
+gpointer
+g_sequence_ptr_get_data           (GSequencePtr             ptr)
+{
+    g_return_val_if_fail (ptr != NULL, NULL);
+    g_return_val_if_fail (!ptr->is_end, NULL);
+
+    return ptr->data;
+}
+
+GSequencePtr
+g_sequence_insert_sorted      (GSequence               *seq,
+			       gpointer                 data,
+			       GCompareDataFunc         cmp_func,
+			       gpointer                 cmp_data)
+{
+    GSequenceNode *new_node = g_sequence_node_new (data);
+    new_node->sequence = seq;
+    g_sequence_node_insert_sorted (seq->node, new_node, cmp_func, cmp_data);
+    return new_node;
+}
+
+void
+g_sequence_insert_sequence    (GSequencePtr             ptr,
+			       GSequence               *other_seq)
+{
+    GSequenceNode *last;
+
+    g_return_if_fail (other_seq != NULL);
+    g_return_if_fail (ptr != NULL);
+
+    last = g_sequence_node_find_last (other_seq->node);
+    g_sequence_node_insert_before (ptr, last);
+    g_sequence_node_remove (last);
+    g_sequence_node_free (last, NULL);
+    other_seq->node = NULL;
+    g_sequence_free (other_seq);
+}
+
+void
+g_sequence_concatenate        (GSequence               *seq1,
+			       GSequence               *seq2)
+{
+    GSequenceNode *last;
+
+    g_return_if_fail (seq1 != NULL);
+    g_return_if_fail (seq2 != NULL);
+    
+    last = g_sequence_node_find_last (seq1->node);
+    g_sequence_insert_sequence (last, seq2);
+}
+
+/*
+ * The new sequence inherits the destroy notify from the sequence that
+ * beign and end comes from
+ */
+void
+g_sequence_remove_range       (GSequencePtr             begin,
+			       GSequencePtr             end,
+			       GSequence              **removed)
+{
+    GSequence *seq;
+    GSequenceNode *s1, *s2, *s3;
+
+    seq = g_sequence_node_get_sequence (begin);
+
+    g_assert (end != NULL);
+    
+    g_return_if_fail (seq == g_sequence_node_get_sequence (end));
+
+    g_sequence_node_split (begin, &s1, &s2);
+    g_sequence_node_split (end, NULL, &s3);
+
+    if (s1)
+	g_sequence_node_insert_before (s3, s1);
+
+    seq->node = s3;
+
+    if (removed)
+    {
+	*removed = g_sequence_new (seq->data_destroy_notify);
+	g_sequence_node_insert_before ((*removed)->node, s2);
+    }
+    else
+    {
+	g_sequence_node_free (s2, seq->data_destroy_notify);
+    }
+}
+
+gint
+g_sequence_get_length         (GSequence               *seq)
+{
+    return g_sequence_node_get_length (seq->node) - 1;
+}
+
+GSequencePtr
+g_sequence_get_end_ptr        (GSequence               *seq)
+{
+    g_return_val_if_fail (seq != NULL, NULL);
+    return g_sequence_node_find_last (seq->node);
+}
+
+GSequencePtr
+g_sequence_get_begin_ptr      (GSequence               *seq)
+{
+    g_return_val_if_fail (seq != NULL, NULL);
+    return g_sequence_node_find_first (seq->node);
+}
+
+/*
+ * if pos > number of items or -1, will return end pointer
+ */
+GSequencePtr
+g_sequence_get_ptr_at_pos     (GSequence               *seq,
+			       gint                     pos)
+{
+    gint len;
+    
+    g_return_val_if_fail (seq != NULL, NULL);
+
+    len = g_sequence_get_length (seq);
+
+    if (pos > len || pos == -1)
+	pos = len;
+
+    return g_sequence_node_find_by_pos (seq->node, pos);
+}
+
+
+/* GSequencePtr */
+gboolean
+g_sequence_ptr_is_end         (GSequencePtr             ptr)
+{
+    g_return_val_if_fail (ptr != NULL, FALSE);
+    return ptr->is_end;
+}
+
+gboolean
+g_sequence_ptr_is_begin       (GSequencePtr             ptr)
+{
+    return (g_sequence_node_prev (ptr) == NULL);
+}
+
+gint
+g_sequence_ptr_get_position   (GSequencePtr             ptr)
+{
+    g_return_val_if_fail (ptr != NULL, -1);
+
+    return g_sequence_node_get_pos (ptr);
+}
+
+GSequencePtr
+g_sequence_ptr_next           (GSequencePtr             ptr)
+{
+    g_return_val_if_fail (ptr != NULL, NULL);
+
+    return g_sequence_node_next (ptr);
+}
+
+GSequencePtr
+g_sequence_ptr_prev           (GSequencePtr             ptr)
+{
+    g_return_val_if_fail (ptr != NULL, NULL);
+
+    return g_sequence_node_prev (ptr);
+}
+
+GSequencePtr
+g_sequence_ptr_move           (GSequencePtr             ptr,
+			       guint                    delta)
+{
+    gint new_pos;
+    
+    g_return_val_if_fail (ptr != NULL, NULL);
+
+    new_pos = g_sequence_node_get_pos (ptr) + delta;
+    
+    return g_sequence_node_find_by_pos (ptr, new_pos);
+}
+
+void
+g_sequence_ptr_sort_changed  (GSequencePtr	     ptr,
+			      GCompareDataFunc	     cmp_func,
+			      gpointer		     cmp_data)
+{
+    GSequence *seq;
+    
+    g_return_if_fail (!ptr->is_end);
+    
+    seq = g_sequence_node_get_sequence (ptr); 
+    g_sequence_unlink (seq, ptr);
+    g_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
+g_sequence_search             (GSequence               *seq,
+			       GSequenceSearchFunc      f,
+			       gpointer                 data)
+{
+    GQueue *intervals = g_queue_new ();
+
+    g_queue_push_tail (intervals, g_sequence_node_find_first (seq->node));
+    g_queue_push_tail (intervals, g_sequence_node_find_last (seq->node));
+
+    while (!g_queue_is_empty (intervals))
+    {
+	GSequenceNode *begin = g_queue_pop_head (intervals);
+	GSequenceNode *end   = g_queue_pop_head (intervals);
+	
+	if (f (begin, end, data))
+	{
+	    gint begin_pos = g_sequence_node_get_pos (begin);
+	    gint end_pos   = g_sequence_node_get_pos (end);
+
+	    if (end_pos - begin_pos > 1)
+	    {
+		GSequenceNode *mid;
+		gint mid_pos;
+
+		mid_pos = begin_pos + (end_pos - begin_pos) / 2;
+		mid = g_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
+g_sequence_add_aggregate      (GSequence               *seq,
+			       const gchar             *aggregate,
+			       GSequenceAggregateFunc   f,
+			       gpointer                 data,
+			       GDestroyNotify           destroy)
+{
+    /* FIXME */
+}
+
+void
+g_sequence_remove_aggregate   (GSequence               *seq,
+			       const gchar              aggregate)
+{
+    /* FIXME */
+
+}
+
+void
+g_sequence_set_aggregate_data (GSequencePtr             ptr,
+			       const gchar             *aggregate,
+			       gpointer                 data)
+{
+    /* FIXME */
+    
+}
+
+gpointer
+g_sequence_get_aggregate_data (GSequencePtr             begin,
+			       GSequencePtr             end,
+			       const gchar             *aggregate)
+{
+    g_assert_not_reached();
+    return NULL;
+}
+#endif
+
+
+/* Nodes
+ */
+static void
+g_sequence_node_update_fields (GSequenceNode *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
+g_sequence_node_rotate (GSequenceNode *node)
+{
+    GSequenceNode *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;
+    }
+    
+    g_sequence_node_update_fields (old);
+    g_sequence_node_update_fields (node);
+}
+
+static GSequenceNode *
+splay (GSequenceNode *node)
+{
+    while (node->parent)
+    {
+	if (!node->parent->parent)
+	{
+	    /* zig */
+	    g_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 */
+	    g_sequence_node_rotate (node->parent);
+	    g_sequence_node_rotate (node);
+	}
+	else
+	{
+	    /* zig-zag */
+	    g_sequence_node_rotate (node);
+	    g_sequence_node_rotate (node);
+	}
+    }
+
+    return node;
+}
+
+static GSequenceNode *
+g_sequence_node_new (gpointer          data)
+{
+    GSequenceNode *node = g_new0 (GSequenceNode, 1);
+
+    node->parent = NULL;
+    node->left = NULL;
+    node->right = NULL;
+
+    node->data = data;
+    node->is_end = FALSE;
+    node->n_nodes = 1;
+
+    return node;
+}
+
+static GSequenceNode *
+find_min (GSequenceNode *node)
+{
+    splay (node);
+
+    while (node->left)
+	node = node->left;
+    
+    return node;
+}
+
+static GSequenceNode *
+find_max (GSequenceNode *node)
+{
+    splay (node);
+
+    while (node->right)
+	node = node->right;
+
+    return node;
+}
+
+static GSequenceNode *
+g_sequence_node_find_first   (GSequenceNode    *node)
+{
+    return splay (find_min (node));
+}
+
+static GSequenceNode *
+g_sequence_node_find_last    (GSequenceNode    *node)
+{
+    return splay (find_max (node));
+}
+
+static gint
+get_n_nodes (GSequenceNode *node)
+{
+    if (node)
+	return node->n_nodes;
+    else
+	return 0;
+}
+
+static GSequenceNode *
+g_sequence_node_find_by_pos  (GSequenceNode    *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 GSequenceNode *
+g_sequence_node_prev         (GSequenceNode    *node)
+{
+    splay (node);
+
+    if (node->left)
+    {
+	node = node->left;
+	while (node->right)
+	    node = node->right;
+    }
+
+    return splay (node);
+}
+
+static GSequenceNode *
+g_sequence_node_next         (GSequenceNode    *node)
+{
+    splay (node);
+
+    if (node->right)
+    {
+	node = node->right;
+	while (node->left)
+	    node = node->left;
+    }
+
+    return splay (node);
+}
+
+static gint
+g_sequence_node_get_pos (GSequenceNode    *node)
+{
+    splay (node);
+
+    return get_n_nodes (node->left);
+}
+
+static GSequence *
+g_sequence_node_get_sequence (GSequenceNode    *node)
+{
+    splay (node);
+
+    return node->sequence;
+}
+
+static GSequenceNode *
+g_sequence_node_find_closest (GSequenceNode    *node,
+			      GSequenceNode    *other,
+			      GCompareDataFunc  cmp,
+			      gpointer          data)
+{
+    GSequenceNode *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
+g_sequence_node_free         (GSequenceNode    *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)
+    {
+	GSequenceNode *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
+g_sequence_node_is_singleton (GSequenceNode    *node)
+{
+    splay (node);
+
+    if (node->left || node->right)
+	return FALSE;
+
+    return TRUE;
+}
+#endif
+
+static void
+g_sequence_node_split        (GSequenceNode    *node,
+			      GSequenceNode   **left,
+			      GSequenceNode   **right)
+{
+    GSequenceNode *left_tree;
+    
+    splay (node);
+
+    left_tree = node->left;
+    if (left_tree)
+    {
+	left_tree->parent = NULL;
+	g_sequence_node_update_fields (left_tree);
+    }
+    
+    node->left = NULL;
+    g_sequence_node_update_fields (node);
+
+    if (left)
+	*left = left_tree;
+
+    if (right)
+	*right = node;
+}
+
+static void
+g_sequence_node_insert_before (GSequenceNode *node,
+			       GSequenceNode *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;
+
+    g_sequence_node_update_fields (new);
+    g_sequence_node_update_fields (node);
+}
+
+static gint
+g_sequence_node_get_length (GSequenceNode    *node)
+{
+    g_assert (node != NULL);
+    
+    splay (node);
+    return node->n_nodes;
+}
+
+static void
+g_sequence_node_remove        (GSequenceNode *node)
+{
+    GSequenceNode *right, *left;
+    
+    splay (node);
+
+    left = node->left;
+    right = node->right;
+
+    node->left = node->right = NULL;
+
+    if (right)
+    {
+	right->parent = node->parent;
+	right->left = left;
+	if (left)
+	    left->parent = right;
+    }
+    else if (left)
+	left->parent = node->parent;
+}
+
+
+#if 0
+/* debug func */
+static gint
+g_sequence_node_calc_height (GSequenceNode *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))
+	{
+	    GSequenceNode *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
+g_sequence_node_insert_sorted (GSequenceNode *node,
+			       GSequenceNode *new,
+			       GCompareDataFunc cmp_func,
+			       gpointer cmp_data)
+{
+    SortInfo info;
+    GSequenceNode *closest;
+    info.cmp = cmp_func;
+    info.data = cmp_data;
+    
+    closest =
+	g_sequence_node_find_closest (node, new, node_compare, &info);
+
+    if (node_compare (new, closest, &info) > 0)
+	closest = g_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);
+    g_sequence_node_insert_before (closest, new);
+}
+
+static gint
+g_sequence_node_calc_height (GSequenceNode *node)
+{
+  gint left_height;
+  gint right_height;
+
+  if (node)
+  {
+      left_height = 0;
+      right_height = 0;
+
+      if (node->left)
+	left_height = g_sequence_node_calc_height (node->left);
+
+      if (node->right)
+	right_height = g_sequence_node_calc_height (node->right);
+
+      return MAX (left_height, right_height) + 1;
+  }
+
+  return 0;
+}
+
+gint
+g_sequence_calc_tree_height   (GSequence               *seq)
+{
+    GSequenceNode *node = seq->node;
+    gint r, l;
+    while (node->parent)
+	node = node->parent;
+
+    if (node)
+    {
+	r = g_sequence_node_calc_height (node->right);
+	l = g_sequence_node_calc_height (node->left);
+
+	return MAX (r, l) + 1;
+    }
+    else
+	return 0;
+}
+
diff --git a/cut-n-paste-code/gsequence/gsequence.h b/cut-n-paste-code/gsequence/gsequence.h
new file mode 100644
index 000000000..b5901973e
--- /dev/null
+++ b/cut-n-paste-code/gsequence/gsequence.h
@@ -0,0 +1,87 @@
+/* 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__
+
+typedef struct _GSequence      GSequence;
+typedef struct _GSequenceNode *GSequencePtr;
+
+/* GSequence */
+GSequence *  g_sequence_new                (GDestroyNotify           data_destroy);
+void         g_sequence_free               (GSequence               *seq);
+void         g_sequence_sort               (GSequence               *seq,
+					    GCompareDataFunc         cmp_func,
+					    gpointer                 cmp_data);
+void         g_sequence_append             (GSequence               *seq,
+					    gpointer                 data);
+void         g_sequence_prepend            (GSequence               *seq,
+					    gpointer                 data);
+void         g_sequence_insert             (GSequencePtr             ptr,
+					    gpointer                 data);
+void         g_sequence_remove             (GSequencePtr             ptr);
+GSequencePtr g_sequence_insert_sorted      (GSequence               *seq,
+					    gpointer                 data,
+					    GCompareDataFunc         cmp_func,
+					    gpointer                 cmp_data);
+void         g_sequence_insert_sequence    (GSequencePtr             ptr,
+					    GSequence               *other_seq);
+void         g_sequence_concatenate        (GSequence               *seq1,
+					    GSequence               *seq);
+void         g_sequence_remove_range       (GSequencePtr             begin,
+					    GSequencePtr             end,
+					    GSequence              **removed);
+gint	     g_sequence_get_length         (GSequence               *seq);
+GSequencePtr g_sequence_get_end_ptr        (GSequence               *seq);
+GSequencePtr g_sequence_get_begin_ptr      (GSequence               *seq);
+GSequencePtr g_sequence_get_ptr_at_pos     (GSequence               *seq,
+					    gint                     pos);
+
+/* GSequencePtr */
+gboolean     g_sequence_ptr_is_end         (GSequencePtr             ptr);
+gboolean     g_sequence_ptr_is_begin       (GSequencePtr             ptr);
+gint         g_sequence_ptr_get_position   (GSequencePtr             ptr);
+GSequencePtr g_sequence_ptr_next           (GSequencePtr             ptr);
+GSequencePtr g_sequence_ptr_prev           (GSequencePtr             ptr);
+GSequencePtr g_sequence_ptr_move           (GSequencePtr             ptr,
+					    guint                    leap);
+void         g_sequence_ptr_sort_changed   (GSequencePtr	     ptr,
+					    GCompareDataFunc	     cmp_func,
+					    gpointer		     cmp_data);
+gpointer     g_sequence_ptr_get_data       (GSequencePtr             ptr);
+
+/* search */
+
+/* return TRUE if you want to be called again with two
+ * smaller segments
+ */
+typedef gboolean (* GSequenceSearchFunc) (GSequencePtr begin,
+					  GSequencePtr end,
+					  gpointer     data);
+
+void         g_sequence_search             (GSequence               *seq,
+					    GSequenceSearchFunc      f,
+					    gpointer                 data);
+
+/* debug */
+gint         g_sequence_calc_tree_height   (GSequence               *seq);
+
+#endif /* __GSEQUENCE_H__ */
diff --git a/src/Makefile.am b/src/Makefile.am
index eaf003d10..9f98a4215 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -34,6 +34,7 @@ LDADD =\
 	$(top_builddir)/libnautilus/libnautilus.la \
 	$(top_builddir)/libnautilus-adapter/libnautilus-adapter.la \
 	$(top_builddir)/libnautilus-private/libnautilus-private.la  \
+        $(top_builddir)/cut-n-paste-code/gsequence/libgsequence.la \
 	$(CORE_LIBS) \
 	$(POPT_LIBS) \
 	$(NULL)
diff --git a/src/file-manager/fm-list-model.c b/src/file-manager/fm-list-model.c
index 56e834227..ad3c746f9 100644
--- a/src/file-manager/fm-list-model.c
+++ b/src/file-manager/fm-list-model.c
@@ -2,7 +2,8 @@
 
 /* fm-list-model.h - a GtkTreeModel for file lists. 
 
-   Copyright (C) 2001, 2002 Anders Carlsson 
+   Copyright (C) 2001, 2002 Anders Carlsson
+   Copyright (C) 2003, Soeren Sandmann
 
    The Gnome Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public License as
@@ -19,7 +20,7 @@
    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.
 
-   Authors: Anders Carlsson <andersca@gnu.org>
+   Authors: Anders Carlsson <andersca@gnu.org>, Soeren Sandmann (sandmann@daimi.au.dk)
 */
 
 #include <config.h>
@@ -32,15 +33,17 @@
 #include <gtk/gtktreesortable.h>
 #include <libnautilus-private/nautilus-icon-factory.h>
 #include <libnautilus-private/nautilus-dnd.h>
+#include <gsequence/gsequence.h>
 
-#define G_SLIST(x) ((GSList *) x)
+static int fm_list_model_compare_func (gconstpointer a,
+				       gconstpointer b,
+				       gpointer      user_data);
 
 static GObjectClass *parent_class;
 
 struct FMListModelDetails {
-	GSList *files;
-	GSList *tail;
-	int length;
+	GSequence *files;
+	GHashTable *reverse_map;	/* map from files to GSequencePtr's */
 
 	int stamp;
 
@@ -134,22 +137,24 @@ static gboolean
 fm_list_model_get_iter (GtkTreeModel *tree_model, GtkTreeIter *iter, GtkTreePath *path)
 {
 	FMListModel *model;
-	GSList *list;
+	GSequencePtr ptr;
 	int i;
 	
 	model = (FMListModel *)tree_model;
 
 	i = gtk_tree_path_get_indices (path)[0];
 
-	if (i >= model->details->length) {
+	if (i >= g_sequence_get_length (model->details->files)) {
 		return FALSE;
 	}
 
-	list = g_slist_nth (model->details->files, i);
+	ptr = g_sequence_get_ptr_at_pos (model->details->files, i);
 
 	iter->stamp = model->details->stamp;
-	iter->user_data = list;
+	iter->user_data = ptr;
 
+	g_assert (!g_sequence_ptr_is_end (iter->user_data));
+	
 	return TRUE;
 }
 
@@ -158,30 +163,19 @@ fm_list_model_get_path (GtkTreeModel *tree_model, GtkTreeIter *iter)
 {
 	GtkTreePath *path;
 	FMListModel *model;
-	GSList *list;
-	int i;
 
 	model = (FMListModel *)tree_model;
 	
 	g_return_val_if_fail (iter->stamp == model->details->stamp, NULL);
-	
-	i = 0;
-
-	for (list = model->details->files; list; list = list->next) {
-		if (list == iter->user_data) {
-			break;
-		}
 
-		i++;
-	}
-
-	if (list == NULL) {
+	if (g_sequence_ptr_is_end (iter->user_data)) {
+		/* FIXME is this right? */
 		return NULL;
 	}
-
-	path = gtk_tree_path_new ();
-	gtk_tree_path_append_index (path, i);
 	
+	path = gtk_tree_path_new ();
+	gtk_tree_path_append_index (path, g_sequence_ptr_get_position (iter->user_data));
+
 	return path;
 }
 
@@ -199,8 +193,9 @@ fm_list_model_get_value (GtkTreeModel *tree_model, GtkTreeIter *iter, int column
 	model = (FMListModel *)tree_model;
 
 	g_return_if_fail (model->details->stamp == iter->stamp);
+	g_return_if_fail (!g_sequence_ptr_is_end (iter->user_data));
 
-	file = G_SLIST (iter->user_data)->data;
+	file = g_sequence_ptr_get_data (iter->user_data);
 	
 	switch (column) {
 	case FM_LIST_MODEL_FILE_COLUMN:
@@ -275,9 +270,9 @@ fm_list_model_iter_next (GtkTreeModel *tree_model, GtkTreeIter *iter)
 
 	g_return_val_if_fail (model->details->stamp == iter->stamp, FALSE);
 
-	iter->user_data = G_SLIST (iter->user_data)->next;
+	iter->user_data = g_sequence_ptr_next (iter->user_data);
 
-	return (iter->user_data != NULL);
+	return !g_sequence_ptr_is_end (iter->user_data);
 }
 
 static gboolean
@@ -291,15 +286,14 @@ fm_list_model_iter_children (GtkTreeModel *tree_model, GtkTreeIter *iter, GtkTre
 		return FALSE;
 	}
 
-	if (model->details->files != NULL) {
-		iter->stamp = model->details->stamp;
-		iter->user_data = model->details->files;
-
-		return TRUE;
-	}
-	else {
+	if (g_sequence_get_length (model->details->files) == 0) {
 		return FALSE;
 	}
+
+	iter->stamp = model->details->stamp;
+	iter->user_data = g_sequence_get_begin_ptr (model->details->files);
+
+	return TRUE;
 }
 
 static gboolean
@@ -316,7 +310,7 @@ fm_list_model_iter_n_children (GtkTreeModel *tree_model, GtkTreeIter *iter)
 	model = (FMListModel *)tree_model;
 
 	if (iter == NULL) {
-		return model->details->length;
+		return g_sequence_get_length (model->details->files);
 	}
 
 	g_return_val_if_fail (model->details->stamp == iter->stamp, -1);
@@ -328,7 +322,7 @@ static gboolean
 fm_list_model_iter_nth_child (GtkTreeModel *tree_model, GtkTreeIter *iter, GtkTreeIter *parent, int n)
 {
 	FMListModel *model;
-	GSList *child;
+	GSequencePtr child;
 
 	model = (FMListModel *)tree_model;
 	
@@ -336,17 +330,16 @@ fm_list_model_iter_nth_child (GtkTreeModel *tree_model, GtkTreeIter *iter, GtkTr
 		return FALSE;
 	}
 
-	child = g_slist_nth (model->details->files, n);
+	child = g_sequence_get_ptr_at_pos (model->details->files, n);
 
-	if (child != NULL) {
-		iter->stamp = model->details->stamp;
-		iter->user_data = child;
-
-		return TRUE;
-	}
-	else {
+	if (g_sequence_ptr_is_end (child)) {
 		return FALSE;
 	}
+
+	iter->stamp = model->details->stamp;
+	iter->user_data = child;
+
+	return TRUE;
 }
 
 static gboolean
@@ -358,33 +351,25 @@ fm_list_model_iter_parent (GtkTreeModel *tree_model, GtkTreeIter *iter, GtkTreeI
 gboolean
 fm_list_model_get_tree_iter_from_file (FMListModel *model, NautilusFile *file, GtkTreeIter *iter)
 {
-	GSList *list;
+	GSequencePtr ptr;
 
-	for (list = model->details->files; list; list = list->next) {
-		if (list->data == file) {
-			break;
-		}
-	}
+	ptr = g_hash_table_lookup (model->details->reverse_map, file);
 
-	if (list == NULL) {
+	if (!ptr) {
 		return FALSE;
 	}
 
+	g_assert (!g_sequence_ptr_is_end (ptr));
+	g_assert (g_sequence_ptr_get_data (ptr) == file);
+	
 	if (iter != NULL) {
 		iter->stamp = model->details->stamp;
-		iter->user_data = list;
+		iter->user_data = ptr;
 	}
 	
 	return TRUE;
 }
 
-/* Sorting */
-typedef struct _SortTuple
-{
-  gint offset;
-  GSList *el;
-} SortTuple;
-
 static int
 fm_list_model_compare_func (gconstpointer a,
 			    gconstpointer b,
@@ -394,11 +379,11 @@ fm_list_model_compare_func (gconstpointer a,
 	NautilusFile *file2;
 	FMListModel *model;
 	int result;
-	
+
 	model = (FMListModel *)user_data;
 
-	file1 = ((SortTuple *)a)->el->data;
-	file2 = ((SortTuple *)b)->el->data;
+	file1 = (NautilusFile *)a;
+	file2 = (NautilusFile *)b;
 
 	result = nautilus_file_compare_for_sort (file1, file2,
 						 fm_list_model_get_sort_type_from_sort_column_id (model->details->sort_column_id),
@@ -411,58 +396,47 @@ fm_list_model_compare_func (gconstpointer a,
 static void
 fm_list_model_sort (FMListModel *model)
 {
-	GtkTreeIter iter;
-	GArray *sort_array;
-	gint i;
-	gint *new_order;
-	GSList *list;
+	GSequence *files;
+	GSequencePtr *old_order;
 	GtkTreePath *path;
+	int *new_order;
+	int length;
+	int i;
 
-	if (model->details->length <= 1) {
+	files = model->details->files;
+	length = g_sequence_get_length (files);
+
+	if (length <= 1) {
 		return;
 	}
-
-	list = G_SLIST (model->details->files);
 	
-	sort_array = g_array_sized_new (FALSE, FALSE,
-					sizeof (SortTuple),
-					model->details->length);
-
-	for (i = 0; i < model->details->length; i++) {
-		SortTuple tuple;
+	/* generate old order of GSequencePtr's */
+	old_order = g_new (GSequencePtr, length);
+	for (i = 0; i < length; ++i) {
+		GSequencePtr ptr = g_sequence_get_ptr_at_pos (files, i);
 
-		/* 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;
+		old_order[i] = ptr;
 	}
 
-	g_array_sort_with_data (sort_array, fm_list_model_compare_func, model);
-	
-	for (i = 0; i < model->details->length - 1; i++) {
-		g_array_index (sort_array, SortTuple, i).el->next = g_array_index (sort_array, SortTuple, i + 1).el;
+	/* sort */
+	g_sequence_sort (files, fm_list_model_compare_func, model);
+
+	/* generate new order */
+	new_order = g_new (int, length);
+	for (i = 0; i < length; ++i) {
+		new_order[i] = g_sequence_ptr_get_position (old_order[i]);
 	}
-	g_array_index (sort_array, SortTuple, model->details->length - 1).el->next = NULL;
-	model->details->files = g_array_index (sort_array, SortTuple, 0).el;
 
 	/* Let the world know about our new order */
-	new_order = g_new (int, model->details->length);
-	for (i = 0; i < model->details->length; i++) {
-		new_order[i] = g_array_index (sort_array, SortTuple, i).offset;
-	}
 	path = gtk_tree_path_new ();
-	iter.stamp = model->details->stamp;
-	iter.user_data = NULL;
 
+	g_assert (new_order != NULL);
 	gtk_tree_model_rows_reordered (GTK_TREE_MODEL (model),
 				       path, NULL, new_order);
+
 	gtk_tree_path_free (path);
+	g_free (old_order);
 	g_free (new_order);
-	g_array_free (sort_array, TRUE);
 }
 
 static gboolean
@@ -624,65 +598,22 @@ fm_list_model_add_file (FMListModel *model, NautilusFile *file)
 {
 	GtkTreeIter iter;
 	GtkTreePath *path;
-	GSList *list, *tmp, *tmp_prev;
-	NautilusFile *file1;
-	int result;
+	GSequencePtr new_ptr;
 	
 	/* We may only add each file once. */
-	if (fm_list_model_get_tree_iter_from_file (model, file, NULL) == TRUE) {
+	if (fm_list_model_get_tree_iter_from_file (model, file, NULL)) {
 		return;
 	}
 
-	tmp_prev = NULL;
+	nautilus_file_ref (file);
 	
-	list = g_slist_alloc ();
-	list->data = nautilus_file_ref (file);
+	new_ptr = g_sequence_insert_sorted (model->details->files, file,
+					    fm_list_model_compare_func, model);
+
+	g_hash_table_insert (model->details->reverse_map, file, new_ptr);
 	
 	iter.stamp = model->details->stamp;
-	iter.user_data = list;
-
-	if (model->details->tail == NULL) {
-		model->details->files = iter.user_data;
-		model->details->tail = iter.user_data;
-	}
-	else {
-		for (tmp = model->details->files; tmp; tmp = tmp->next) {
-			file1 = tmp->data;
-
-			result = nautilus_file_compare_for_sort (file, file1,
-								 fm_list_model_get_sort_type_from_sort_column_id (model->details->sort_column_id),
-								 model->details->sort_directories_first,
-								 (model->details->order == GTK_SORT_DESCENDING));
-			if (result < 0) {
-				break;
-			}
-
-			tmp_prev = tmp;
-		}
-
-		if (tmp != NULL) {
-			if (tmp == model->details->files) {
-				list->next = model->details->files;
-				model->details->files = list;
-			}
-			else {
-				list->next = tmp;
-			}
-		}
-
-		if (tmp_prev != NULL) {
-			if (tmp_prev == model->details->tail) {
-				model->details->tail->next = list;
-				model->details->tail = list;
-			}
-			else {
-				tmp_prev->next = list;
-			}
-		}
-
-	}
-
-	model->details->length += 1;
+	iter.user_data = new_ptr;
 
 	path = gtk_tree_model_get_path (GTK_TREE_MODEL (model), &iter);
 	gtk_tree_model_row_inserted (GTK_TREE_MODEL (model), path, &iter);
@@ -694,21 +625,19 @@ fm_list_model_file_changed (FMListModel *model, NautilusFile *file)
 {
 	GtkTreeIter iter;
 	GtkTreePath *path;
-	GSList *list;
+	GSequencePtr ptr;
 
-	for (list = model->details->files; list; list = list->next) {
-		if (list->data == file) {
-			break;
-		}
+	ptr = g_hash_table_lookup (model->details->reverse_map, file);
+	if (!ptr) {
+		return;
 	}
 
-	if (list == NULL) {
+	g_sequence_ptr_sort_changed (ptr, fm_list_model_compare_func, model);
+
+	if (!fm_list_model_get_tree_iter_from_file (model, file, &iter)) {
 		return;
 	}
-	
-	iter.stamp = model->details->stamp;
-	iter.user_data = list;
-	
+
 	path = gtk_tree_model_get_path (GTK_TREE_MODEL (model), &iter);
 	gtk_tree_model_row_changed (GTK_TREE_MODEL (model), path, &iter);
 	gtk_tree_path_free (path);
@@ -717,64 +646,25 @@ fm_list_model_file_changed (FMListModel *model, NautilusFile *file)
 gboolean
 fm_list_model_is_empty (FMListModel *model)
 {
-	return model->details->length == 0;
-}
-
-static GSList *
-remove_link_saving_prev (GSList *list, GSList *link, GSList **prevp)
-{
-	GSList *node;
-	GSList *prev;
-	
-	prev = NULL;
-
-	for (node = list; node; node = node->next) {
-		if (node == link) {
-			if (prev != NULL) {
-				prev->next = link->next;
-			}
-			
-			if (list == link) {
-				list = list->next;
-			}
-			
-			link->next = NULL;
-			break;
-		}
-
-		prev = node;
-	}
-
-	*prevp = prev;
-
-	return list;
+	return (g_sequence_get_length (model->details->files) == 0);
 }
 
 static void
 fm_list_model_remove (FMListModel *model, GtkTreeIter *iter)
 {
+	GSequencePtr ptr;
 	GtkTreePath *path;
-	GSList *prev;
 
 	path = gtk_tree_model_get_path (GTK_TREE_MODEL (model), iter);
-	nautilus_file_unref (NAUTILUS_FILE (G_SLIST (iter->user_data)->data));
-	
-	prev = NULL;
-	model->details->files = remove_link_saving_prev (model->details->files,
-							 iter->user_data,
-							 &prev);
-	model->details->length -= 1;
-
-	if (iter->user_data == model->details->tail) {
-		model->details->tail = prev;
-	}
+	ptr = iter->user_data;
 
-	model->details->stamp++;
+	g_hash_table_remove (model->details->reverse_map, g_sequence_ptr_get_data (ptr));
+	g_sequence_remove (ptr);
 
+	model->details->stamp++;
 	
 	gtk_tree_model_row_deleted (GTK_TREE_MODEL (model), path);
 	gtk_tree_path_free (path);
-
 }
 
 void
@@ -794,9 +684,9 @@ fm_list_model_clear (FMListModel *model)
 
 	g_return_if_fail (model != NULL);
 
-	while (model->details->files != NULL) {
+	while (g_sequence_get_length (model->details->files) > 0) {
 		iter.stamp = model->details->stamp;
-		iter.user_data = model->details->files;
+		iter.user_data = g_sequence_get_begin_ptr (model->details->files);
 		fm_list_model_remove (model, &iter);
 	}
 }
@@ -960,6 +850,8 @@ fm_list_model_finalize (GObject *object)
 
 	model = FM_LIST_MODEL (object);
 
+	g_sequence_free (model->details->files);
+	g_hash_table_destroy (model->details->reverse_map);
 	g_free (model->details);
 	
 	EEL_CALL_PARENT (G_OBJECT_CLASS, finalize, (object));
@@ -969,6 +861,8 @@ static void
 fm_list_model_init (FMListModel *model)
 {
 	model->details = g_new0 (FMListModelDetails, 1);
+	model->details->files = g_sequence_new ((GDestroyNotify)nautilus_file_unref);
+	model->details->reverse_map = g_hash_table_new (g_direct_hash, g_direct_equal);
 	model->details->stamp = g_random_int ();
 	model->details->sort_column_id = -1;
 }