[gtk+] Replace GArray with GSequence in GtkTreeModelSort

From: Kristian Rietveld <kristian src gnome org>
To: commits-list gnome org
Cc:
Subject: [gtk+] Replace GArray with GSequence in GtkTreeModelSort
Date: Mon, 22 Aug 2011 19:44:04 +0000 (UTC)
commit 60d031e311790570e1e9410649dce2e58462a9b7
Author: Kristian Rietveld <kris gtk org>
Date:   Wed Aug 10 23:24:58 2011 +0200

    Replace GArray with GSequence in GtkTreeModelSort
    
    This is done in the same way as GArray was replaced with GSequence in
    GtkTreeModelFilter, in a patch done by Xavier Claessens.
    
    All sorting code has been reworked to use the GSequence sorting
    and insert sort functions, instead of doing a lot on our own.

 gtk/gtktreemodelsort.c |  741 +++++++++++++++++++++++++-----------------------
 1 files changed, 380 insertions(+), 361 deletions(-)
---
diff --git a/gtk/gtktreemodelsort.c b/gtk/gtktreemodelsort.c
index fd6aee2..be85711 100644
--- a/gtk/gtktreemodelsort.c
+++ b/gtk/gtktreemodelsort.c
@@ -153,20 +153,21 @@
 typedef struct _SortElt SortElt;
 typedef struct _SortLevel SortLevel;
 typedef struct _SortData SortData;
-typedef struct _SortTuple SortTuple;
 
 struct _SortElt
 {
-  GtkTreeIter  iter;
-  SortLevel   *children;
-  gint         offset;
-  gint         ref_count;
-  gint         zero_ref_count;
+  GtkTreeIter    iter;
+  SortLevel     *children;
+  gint           offset;
+  gint           ref_count;
+  gint           zero_ref_count;
+  GSequenceIter *siter; /* iter into seq */
+  gint           old_index; /* used while sorting */
 };
 
 struct _SortLevel
 {
-  GArray    *array;
+  GSequence *seq;
   gint       ref_count;
   SortElt   *parent_elt;
   SortLevel *parent_level;
@@ -175,17 +176,12 @@ struct _SortLevel
 struct _SortData
 {
   GtkTreeModelSort *tree_model_sort;
-  GtkTreePath *parent_path;
-  gint parent_path_depth;
-  gint *parent_path_indices;
   GtkTreeIterCompareFunc sort_func;
   gpointer sort_data;
-};
 
-struct _SortTuple
-{
-  SortElt   *elt;
-  gint       offset;
+  GtkTreePath *parent_path;
+  gint parent_path_depth;
+  gint *parent_path_indices;
 };
 
 /* Properties */
@@ -236,6 +232,7 @@ struct _GtkTreeModelSortPrivate
 
 #define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
 #define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)
+#define GET_ELT(siter) ((SortElt *) (siter ? g_sequence_get (siter) : NULL))
 
 
 #define GET_CHILD_ITER(tree_model_sort,ch_iter,so_iter) gtk_tree_model_sort_convert_iter_to_child_iter((GtkTreeModelSort*)(tree_model_sort), (ch_iter), (so_iter));
@@ -360,10 +357,6 @@ static void         gtk_tree_model_sort_sort_level        (GtkTreeModelSort *tre
 							   gboolean          recurse,
 							   gboolean          emit_reordered);
 static void         gtk_tree_model_sort_sort              (GtkTreeModelSort *tree_model_sort);
-static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
-							   SortLevel        *level,
-							   GtkTreeIter      *iter,
-							   gint             skip_index);
 static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
 							   SortLevel        *level,
 							   GtkTreePath      *s_path,
@@ -376,6 +369,15 @@ static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTree
 									 GtkTreePath      *child_path,
 									 gboolean          build_levels);
 
+static gint         gtk_tree_model_sort_compare_func        (gconstpointer     a,
+                                                             gconstpointer     b,
+                                                             gpointer          user_data);
+static gint         gtk_tree_model_sort_offset_compare_func (gconstpointer     a,
+                                                             gconstpointer     b,
+                                                             gpointer          user_data);
+static void         gtk_tree_model_sort_clear_cache_helper  (GtkTreeModelSort *tree_model_sort,
+                                                             SortLevel        *level);
+
 
 G_DEFINE_TYPE_WITH_CODE (GtkTreeModelSort, gtk_tree_model_sort, G_TYPE_OBJECT,
 			 G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_MODEL,
@@ -553,6 +555,122 @@ gtk_tree_model_sort_get_property (GObject    *object,
     }
 }
 
+/* helpers */
+static SortElt *
+sort_elt_new (void)
+{
+  return g_slice_new (SortElt);
+}
+
+static void
+sort_elt_free (gpointer elt)
+{
+  g_slice_free (SortElt, elt);
+}
+
+static void
+increase_offset_iter (gpointer data,
+                      gpointer user_data)
+{
+  SortElt *elt = data;
+  gint offset = GPOINTER_TO_INT (user_data);
+
+  if (elt->offset >= offset)
+    elt->offset++;
+}
+
+static void
+decrease_offset_iter (gpointer data,
+                      gpointer user_data)
+{
+  SortElt *elt = data;
+  gint offset = GPOINTER_TO_INT (user_data);
+
+  if (elt->offset > offset)
+    elt->offset--;
+}
+
+static void
+fill_sort_data (SortData         *data,
+                GtkTreeModelSort *tree_model_sort,
+                SortLevel        *level)
+{
+  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
+
+  data->tree_model_sort = tree_model_sort;
+
+  if (priv->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
+    {
+      GtkTreeDataSortHeader *header;
+      
+      header = _gtk_tree_data_list_get_header (priv->sort_list,
+					       priv->sort_column_id);
+      
+      g_return_if_fail (header != NULL);
+      g_return_if_fail (header->func != NULL);
+      
+      data->sort_func = header->func;
+      data->sort_data = header->data;
+    }
+  else
+    {
+      /* absolutely SHOULD NOT happen: */
+      g_return_if_fail (priv->default_sort_func != NULL);
+
+      data->sort_func = priv->default_sort_func;
+      data->sort_data = priv->default_sort_data;
+    }
+
+  if (level->parent_elt)
+    {
+      data->parent_path = gtk_tree_model_sort_elt_get_path (level->parent_level,
+                                                            level->parent_elt);
+      gtk_tree_path_append_index (data->parent_path, 0);
+    }
+  else
+    {
+      data->parent_path = gtk_tree_path_new_first ();
+    }
+  data->parent_path_depth = gtk_tree_path_get_depth (data->parent_path);
+  data->parent_path_indices = gtk_tree_path_get_indices (data->parent_path);
+}
+
+static void
+free_sort_data (SortData *data)
+{
+  gtk_tree_path_free (data->parent_path);
+}
+
+static SortElt *
+lookup_elt_with_offset (GtkTreeModelSort *tree_model_sort,
+                        SortLevel        *level,
+                        gint              offset,
+                        GSequenceIter   **ret_siter)
+{
+  GSequenceIter *siter, *end_siter;
+
+  /* FIXME: We have to do a search like this, because the sequence is not
+   * (always) sorted on offset order.  Perhaps we should introduce a
+   * second sequence which is sorted on offset order.
+   */
+  end_siter = g_sequence_get_end_iter (level->seq);
+  for (siter = g_sequence_get_begin_iter (level->seq);
+       siter != end_siter;
+       siter = g_sequence_iter_next (siter))
+    {
+      SortElt *elt = g_sequence_get (siter);
+
+      if (elt->offset == offset)
+        break;
+    }
+
+  if (ret_siter)
+    *ret_siter = siter;
+
+  return GET_ELT (siter);
+}
+
+
 static void
 gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
 				 GtkTreePath  *start_s_path,
@@ -565,13 +683,13 @@ gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
   GtkTreeIter iter;
   GtkTreeIter tmpiter;
 
-  SortElt tmp;
   SortElt *elt;
   SortLevel *level;
+  SortData sort_data;
 
   gboolean free_s_path = FALSE;
 
-  gint index = 0, old_index, i;
+  gint index = 0, old_index;
 
   g_return_if_fail (start_s_path != NULL || start_s_iter != NULL);
 
@@ -597,7 +715,7 @@ gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
   level = iter.user_data;
   elt = iter.user_data2;
 
-  if (level->array->len < 2 ||
+  if (g_sequence_get_length (level->seq) < 2 ||
       (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
        priv->default_sort_func == NO_SORT_FUNC))
     {
@@ -611,47 +729,24 @@ gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
 
       return;
     }
-  
-  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
-    {
-      gtk_tree_model_get_iter (priv->child_model,
-			       &tmpiter, start_s_path);
-    }
-
-  old_index = elt - SORT_ELT (level->array->data);
-
-  memcpy (&tmp, elt, sizeof (SortElt));
 
   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
-    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
-						   level,
-						   &tmp.iter,
-						   old_index);
+    tmpiter = elt->iter;
   else
-    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
-						   level,
-						   &tmpiter,
-						   old_index);
+    gtk_tree_model_get_iter (priv->child_model,
+                             &tmpiter, start_s_path);
 
-  if (index < old_index)
-    {
-      g_memmove (level->array->data + ((index + 1)*sizeof (SortElt)),
-		 level->array->data + ((index)*sizeof (SortElt)),
-		 (old_index - index)* sizeof(SortElt));
-    }
-  else if (index > old_index)
-    {
-      g_memmove (level->array->data + ((old_index)*sizeof (SortElt)),
-		 level->array->data + ((old_index + 1)*sizeof (SortElt)),
-		 (index - old_index)* sizeof(SortElt));
-    }
-  memcpy (level->array->data + ((index)*sizeof (SortElt)),
-	  &tmp, sizeof (SortElt));
+  old_index = g_sequence_iter_get_position (elt->siter);
+
+  fill_sort_data (&sort_data, tree_model_sort, level);
+  g_sequence_sort_changed (elt->siter,
+                           gtk_tree_model_sort_compare_func,
+                           &sort_data);
+  free_sort_data (&sort_data);
 
-  for (i = 0; i < level->array->len; i++)
-    if (g_array_index (level->array, SortElt, i).children)
-      g_array_index (level->array, SortElt, i).children->parent_elt = &g_array_index (level->array, SortElt, i);
+  index = g_sequence_iter_get_position (elt->siter);
 
+  /* Prepare the path for signal emission */
   gtk_tree_path_up (path);
   gtk_tree_path_append_index (path, index);
 
@@ -665,9 +760,9 @@ gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
 
       GtkTreePath *tmppath;
 
-      new_order = g_new (gint, level->array->len);
+      new_order = g_new (gint, g_sequence_get_length (level->seq));
 
-      for (j = 0; j < level->array->len; j++)
+      for (j = 0; j < g_sequence_get_length (level->seq); j++)
         {
 	  if (index > old_index)
 	    {
@@ -772,15 +867,13 @@ gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
   /* find the parent level */
   while (i < gtk_tree_path_get_depth (s_path) - 1)
     {
-      gint j;
-
       if (!level)
 	{
 	  /* level not yet build, we won't cover this signal */
 	  goto done;
 	}
 
-      if (level->array->len < gtk_tree_path_get_indices (s_path)[i])
+      if (g_sequence_get_length (level->seq) < gtk_tree_path_get_indices (s_path)[i])
 	{
 	  g_warning ("%s: A node was inserted with a parent that's not in the tree.\n"
 		     "This possibly means that a GtkTreeModel inserted a child node\n"
@@ -789,13 +882,9 @@ gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
 	  goto done;
 	}
 
-      elt = NULL;
-      for (j = 0; j < level->array->len; j++)
-	if (g_array_index (level->array, SortElt, j).offset == gtk_tree_path_get_indices (s_path)[i])
-	  {
-	    elt = &g_array_index (level->array, SortElt, j);
-	    break;
-	  }
+      elt = lookup_elt_with_offset (tree_model_sort, level,
+                                    gtk_tree_path_get_indices (s_path)[i],
+                                    NULL);
 
       g_return_if_fail (elt != NULL);
 
@@ -879,7 +968,6 @@ gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
   SortLevel *level;
   GtkTreeIter iter;
   gint offset;
-  gint i;
 
   g_return_if_fail (s_path != NULL);
 
@@ -922,22 +1010,14 @@ gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
       return;
     }
 
-  /* Remove the row */
-  for (i = 0; i < level->array->len; i++)
-    if (elt->offset == g_array_index (level->array, SortElt, i).offset)
-      break;
-
-  g_array_remove_index (level->array, i);
+  g_sequence_remove (elt->siter);
+  elt = NULL;
 
-  /* update all offsets */
-  for (i = 0; i < level->array->len; i++)
-    {
-      elt = & (g_array_index (level->array, SortElt, i));
-      if (elt->offset > offset)
-	elt->offset--;
-      if (elt->children)
-	elt->children->parent_elt = elt;
-    }
+  /* The sequence is not ordered on offset, so we traverse the entire
+   * sequence.
+   */
+  g_sequence_foreach (level->seq, decrease_offset_iter,
+                      GINT_TO_POINTER (offset));
 
   gtk_tree_model_sort_increment_stamp (tree_model_sort);
   gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);
@@ -956,8 +1036,9 @@ gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
   SortLevel *level;
   GtkTreeIter iter;
   gint *tmp_array;
-  int i, j;
+  int i, length;
   GtkTreePath *path;
+  GSequenceIter *siter, *end_siter;
   GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
 
@@ -989,30 +1070,55 @@ gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
       level = elt->children;
     }
 
-  if (level->array->len < 2)
+  length = g_sequence_get_length (level->seq);
+  if (length < 2)
     {
       gtk_tree_path_free (path);
       return;
     }
 
-  tmp_array = g_new (int, level->array->len);
-  for (i = 0; i < level->array->len; i++)
+  tmp_array = g_new (int, length);
+
+  /* FIXME: I need to think about whether this can be done in a more
+   * efficient way?
+   */
+  i = 0;
+  end_siter = g_sequence_get_end_iter (level->seq);
+  for (siter = g_sequence_get_begin_iter (level->seq);
+       siter != end_siter;
+       siter = g_sequence_iter_next (siter))
     {
-      for (j = 0; j < level->array->len; j++)
+      gint j;
+      SortElt *elt = g_sequence_get (siter);
+
+      for (j = 0; j < length; j++)
 	{
-	  if (g_array_index (level->array, SortElt, i).offset == new_order[j])
+	  if (elt->offset == new_order[j])
 	    tmp_array[i] = j;
 	}
+
+      i++;
     }
 
-  for (i = 0; i < level->array->len; i++)
-    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
+  /* This loop cannot be merged with the above loop nest, because that
+   * would introduce duplicate offsets.
+   */
+  i = 0;
+  end_siter = g_sequence_get_end_iter (level->seq);
+  for (siter = g_sequence_get_begin_iter (level->seq);
+       siter != end_siter;
+       siter = g_sequence_iter_next (siter))
+    {
+      SortElt *elt = g_sequence_get (siter);
+
+      elt->offset = tmp_array[i];
+      i++;
+    }
   g_free (tmp_array);
 
   if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
       priv->default_sort_func == NO_SORT_FUNC)
     {
-
       gtk_tree_model_sort_sort_level (tree_model_sort, level,
 				      FALSE, FALSE);
       gtk_tree_model_sort_increment_stamp (tree_model_sort);
@@ -1082,8 +1188,10 @@ gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
   GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
   gint *indices;
+  SortElt *elt;
   SortLevel *level;
   gint depth, i;
+  GSequenceIter *siter;
 
   g_return_val_if_fail (priv->child_model != NULL, FALSE);
 
@@ -1103,19 +1211,27 @@ gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
   for (i = 0; i < depth - 1; i++)
     {
       if ((level == NULL) ||
-	  (indices[i] >= level->array->len))
+	  (indices[i] >= g_sequence_get_length (level->seq)))
         {
           iter->stamp = 0;
           return FALSE;
         }
 
-      if (g_array_index (level->array, SortElt, indices[i]).children == NULL)
-	gtk_tree_model_sort_build_level (tree_model_sort, level,
-                                         &g_array_index (level->array, SortElt, indices[i]));
-      level = g_array_index (level->array, SortElt, indices[i]).children;
+      siter = g_sequence_get_iter_at_pos (level->seq, indices[i]);
+      if (g_sequence_iter_is_end (siter))
+        {
+          iter->stamp = 0;
+          return FALSE;
+        }
+
+      elt = GET_ELT (siter);
+      if (elt->children == NULL)
+	gtk_tree_model_sort_build_level (tree_model_sort, level, elt);
+
+      level = elt->children;
     }
 
-  if (!level || indices[i] >= level->array->len)
+  if (!level || indices[i] >= g_sequence_get_length (level->seq))
     {
       iter->stamp = 0;
       return FALSE;
@@ -1123,7 +1239,14 @@ gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
 
   iter->stamp = priv->stamp;
   iter->user_data = level;
-  iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
+
+  siter = g_sequence_get_iter_at_pos (level->seq, indices[depth - 1]);
+  if (g_sequence_iter_is_end (siter))
+    {
+      iter->stamp = 0;
+      return FALSE;
+    }
+  iter->user_data2 = GET_ELT (siter);
 
   return TRUE;
 }
@@ -1148,7 +1271,10 @@ gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
 
   while (level)
     {
-      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);
+      gint index;
+
+      index = g_sequence_iter_get_position (elt->siter);
+      gtk_tree_path_prepend_index (retval, index);
 
       elt = level->parent_elt;
       level = level->parent_level;
@@ -1183,6 +1309,7 @@ gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
   SortLevel *level;
   SortElt *elt;
+  GSequenceIter *siter;
 
   g_return_val_if_fail (priv->child_model != NULL, FALSE);
   g_return_val_if_fail (priv->stamp == iter->stamp, FALSE);
@@ -1190,12 +1317,13 @@ gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
   level = iter->user_data;
   elt = iter->user_data2;
 
-  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
+  siter = g_sequence_iter_next (elt->siter);
+  if (g_sequence_iter_is_end (siter))
     {
       iter->stamp = 0;
       return FALSE;
     }
-  iter->user_data2 = elt + 1;
+  iter->user_data2 = GET_ELT (siter);
 
   return TRUE;
 }
@@ -1208,6 +1336,7 @@ gtk_tree_model_sort_iter_previous (GtkTreeModel *tree_model,
   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
   SortLevel *level;
   SortElt *elt;
+  GSequenceIter *siter;
 
   g_return_val_if_fail (priv->child_model != NULL, FALSE);
   g_return_val_if_fail (priv->stamp == iter->stamp, FALSE);
@@ -1215,12 +1344,13 @@ gtk_tree_model_sort_iter_previous (GtkTreeModel *tree_model,
   level = iter->user_data;
   elt = iter->user_data2;
 
-  if (elt == (SortElt *)level->array->data)
+  siter = g_sequence_iter_prev (elt->siter);
+  if (g_sequence_iter_is_begin (siter))
     {
       iter->stamp = 0;
       return FALSE;
     }
-  iter->user_data2 = elt - 1;
+  iter->user_data2 = GET_ELT (siter);
 
   return TRUE;
 }
@@ -1249,7 +1379,7 @@ gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
       level = priv->root;
       iter->stamp = priv->stamp;
       iter->user_data = level;
-      iter->user_data2 = level->array->data;
+      iter->user_data2 = g_sequence_get (g_sequence_get_begin_iter (level->seq));
     }
   else
     {
@@ -1266,7 +1396,7 @@ gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
 
       iter->stamp = priv->stamp;
       iter->user_data = elt->children;
-      iter->user_data2 = elt->children->array->data;
+      iter->user_data2 = g_sequence_get (g_sequence_get_begin_iter (elt->children->seq));
     }
 
   return TRUE;
@@ -1330,7 +1460,7 @@ gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
     }
 
   level = children.user_data;
-  if (n >= level->array->len)
+  if (n >= g_sequence_get_length (level->seq))
     {
       iter->stamp = 0;
       return FALSE;
@@ -1338,7 +1468,7 @@ gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
 
   iter->stamp = tree_model_sort->priv->stamp;
   iter->user_data = level;
-  iter->user_data2 = &g_array_index (level->array, SortElt, n);
+  iter->user_data2 = g_sequence_get (g_sequence_get_iter_at_pos (level->seq, n));
 
   return TRUE;
 }
@@ -1641,26 +1771,22 @@ gtk_tree_model_sort_compare_func (gconstpointer a,
   SortData *data = (SortData *)user_data;
   GtkTreeModelSort *tree_model_sort = data->tree_model_sort;
   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
-  SortTuple *sa = (SortTuple *)a;
-  SortTuple *sb = (SortTuple *)b;
+  const SortElt *sa = a;
+  const SortElt *sb = b;
 
   GtkTreeIter iter_a, iter_b;
   gint retval;
 
-  /* shortcut, if we've the same offsets here, they should be equal */
-  if (sa->offset == sb->offset)
-    return 0;
-
   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
     {
-      iter_a = sa->elt->iter;
-      iter_b = sb->elt->iter;
+      iter_a = sa->iter;
+      iter_b = sb->iter;
     }
   else
     {
-      data->parent_path_indices [data->parent_path_depth-1] = sa->elt->offset;
+      data->parent_path_indices [data->parent_path_depth-1] = sa->offset;
       gtk_tree_model_get_iter (GTK_TREE_MODEL (priv->child_model), &iter_a, data->parent_path);
-      data->parent_path_indices [data->parent_path_depth-1] = sb->elt->offset;
+      data->parent_path_indices [data->parent_path_depth-1] = sb->offset;
       gtk_tree_model_get_iter (GTK_TREE_MODEL (priv->child_model), &iter_b, data->parent_path);
     }
 
@@ -1686,14 +1812,14 @@ gtk_tree_model_sort_offset_compare_func (gconstpointer a,
 {
   gint retval;
 
-  SortTuple *sa = (SortTuple *)a;
-  SortTuple *sb = (SortTuple *)b;
+  const SortElt *sa = (SortElt *)a;
+  const SortElt *sb = (SortElt *)b;
 
   SortData *data = (SortData *)user_data;
 
-  if (sa->elt->offset < sb->elt->offset)
+  if (sa->offset < sb->offset)
     retval = -1;
-  else if (sa->elt->offset > sb->elt->offset)
+  else if (sa->offset > sb->offset)
     retval = 1;
   else
     retval = 0;
@@ -1717,9 +1843,8 @@ gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
 {
   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
   gint i;
-  gint ref_offset;
-  GArray *sort_array;
-  GArray *new_array;
+  GSequenceIter *begin_siter, *end_siter, *siter;
+  SortElt *begin_elt;
   gint *new_order;
 
   GtkTreeIter iter;
@@ -1729,95 +1854,53 @@ gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
 
   g_return_if_fail (level != NULL);
 
-  if (level->array->len < 1 && !((SortElt *)level->array->data)->children)
+  begin_siter = g_sequence_get_begin_iter (level->seq);
+  begin_elt = g_sequence_get (begin_siter);
+
+  if (g_sequence_get_length (level->seq) < 1 && !begin_elt->children)
     return;
 
   iter.stamp = priv->stamp;
   iter.user_data = level;
-  iter.user_data2 = &g_array_index (level->array, SortElt, 0);
+  iter.user_data2 = begin_elt;
 
   gtk_tree_model_sort_ref_node (GTK_TREE_MODEL (tree_model_sort), &iter);
-  ref_offset = g_array_index (level->array, SortElt, 0).offset;
-
-  /* Set up data */
-  data.tree_model_sort = tree_model_sort;
-  if (level->parent_elt)
-    {
-      data.parent_path = gtk_tree_model_sort_elt_get_path (level->parent_level,
-                                                           level->parent_elt);
-      gtk_tree_path_append_index (data.parent_path, 0);
-    }
-  else
-    {
-      data.parent_path = gtk_tree_path_new_first ();
-    }
-  data.parent_path_depth = gtk_tree_path_get_depth (data.parent_path);
-  data.parent_path_indices = gtk_tree_path_get_indices (data.parent_path);
 
-  /* make the array to be sorted */
-  sort_array = g_array_sized_new (FALSE, FALSE, sizeof (SortTuple), level->array->len);
-  for (i = 0; i < level->array->len; i++)
+  i = 0;
+  end_siter = g_sequence_get_end_iter (level->seq);
+  for (siter = g_sequence_get_begin_iter (level->seq);
+       siter != end_siter;
+       siter = g_sequence_iter_next (siter))
     {
-      SortTuple tuple;
+      SortElt *elt = g_sequence_get (siter);
 
-      tuple.elt = &g_array_index (level->array, SortElt, i);
-      tuple.offset = i;
-
-      g_array_append_val (sort_array, tuple);
+      elt->old_index = i;
+      i++;
     }
 
-    if (priv->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
-      {
-	GtkTreeDataSortHeader *header = NULL;
-
-	header = _gtk_tree_data_list_get_header (priv->sort_list,
-						 priv->sort_column_id);
-
-	g_return_if_fail (header != NULL);
-	g_return_if_fail (header->func != NULL);
-
-	data.sort_func = header->func;
-	data.sort_data = header->data;
-      }
-    else
-      {
-	/* absolutely SHOULD NOT happen: */
-	g_return_if_fail (priv->default_sort_func != NULL);
-
-	data.sort_func = priv->default_sort_func;
-	data.sort_data = priv->default_sort_data;
-      }
+  fill_sort_data (&data, tree_model_sort, level);
 
   if (data.sort_func == NO_SORT_FUNC)
-    g_array_sort_with_data (sort_array,
-			    gtk_tree_model_sort_offset_compare_func,
-			    &data);
+    g_sequence_sort (level->seq, gtk_tree_model_sort_offset_compare_func,
+                     &data);
   else
-    g_array_sort_with_data (sort_array,
-			    gtk_tree_model_sort_compare_func,
-			    &data);
+    g_sequence_sort (level->seq, gtk_tree_model_sort_compare_func, &data);
 
-  gtk_tree_path_free (data.parent_path);
+  free_sort_data (&data);
 
-  new_array = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), level->array->len);
-  new_order = g_new (gint, level->array->len);
+  new_order = g_new (gint, g_sequence_get_length (level->seq));
 
-  for (i = 0; i < level->array->len; i++)
+  i = 0;
+  end_siter = g_sequence_get_end_iter (level->seq);
+  for (siter = g_sequence_get_begin_iter (level->seq);
+       siter != end_siter;
+       siter = g_sequence_iter_next (siter))
     {
-      SortElt *elt;
+      SortElt *elt = g_sequence_get (siter);
 
-      elt = g_array_index (sort_array, SortTuple, i).elt;
-      new_order[i] = g_array_index (sort_array, SortTuple, i).offset;
-
-      g_array_append_val (new_array, *elt);
-      if (elt->children)
-	elt->children->parent_elt = elt;
+      new_order[i++] = elt->old_index;
     }
 
-  g_array_free (level->array, TRUE);
-  level->array = new_array;
-  g_array_free (sort_array, TRUE);
-
   if (emit_reordered)
     {
       gtk_tree_model_sort_increment_stamp (tree_model_sort);
@@ -1847,9 +1930,12 @@ gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
   /* recurse, if possible */
   if (recurse)
     {
-      for (i = 0; i < level->array->len; i++)
+      end_siter = g_sequence_get_end_iter (level->seq);
+      for (siter = g_sequence_get_begin_iter (level->seq);
+           siter != end_siter;
+           siter = g_sequence_iter_next (siter))
 	{
-	  SortElt *elt = &g_array_index (level->array, SortElt, i);
+	  SortElt *elt = g_sequence_get (siter);
 
 	  if (elt->children)
 	    gtk_tree_model_sort_sort_level (tree_model_sort,
@@ -1865,15 +1951,7 @@ gtk_tree_model_sort_sort_level (GtkTreeModelSort *tree_model_sort,
    */
   iter.stamp = priv->stamp;
   iter.user_data = level;
-
-  for (i = 0; i < level->array->len; i++)
-    {
-      if (g_array_index (level->array, SortElt, i).offset == ref_offset)
-        {
-	  iter.user_data2 = &g_array_index (level->array, SortElt, i);
-	  break;
-	}
-    }
+  iter.user_data2 = begin_elt;
 
   gtk_tree_model_sort_unref_node (GTK_TREE_MODEL (tree_model_sort), &iter);
 }
@@ -1908,91 +1986,6 @@ gtk_tree_model_sort_sort (GtkTreeModelSort *tree_model_sort)
 }
 
 /* signal helpers */
-static gint
-gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
-				       SortLevel        *level,
-				       GtkTreeIter      *iter,
-				       gint             skip_index)
-{
-  GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
-  gint start, middle, end;
-  gint cmp;
-  SortElt *tmp_elt;
-  GtkTreeIter tmp_iter;
-
-  GtkTreeIterCompareFunc func;
-  gpointer data;
-
-  if (priv->sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
-    {
-      GtkTreeDataSortHeader *header;
-      
-      header = _gtk_tree_data_list_get_header (priv->sort_list,
-					       priv->sort_column_id);
-      
-      g_return_val_if_fail (header != NULL, 0);
-      
-      func = header->func;
-      data = header->data;
-    }
-  else
-    {
-      func = priv->default_sort_func;
-      data = priv->default_sort_data;
-      
-      g_return_val_if_fail (func != NO_SORT_FUNC, 0);
-    }
-
-  g_return_val_if_fail (func != NULL, 0);
-
-  start = 0;
-  end = level->array->len;
-  if (skip_index < 0)
-    skip_index = end;
-  else
-    end--;
-
-  if (start == end)
-    return 0;
-  
-  while (start != end)
-    {
-      middle = (start + end) / 2;
-
-      if (middle < skip_index)
-	tmp_elt = &(g_array_index (level->array, SortElt, middle));
-      else
-	tmp_elt = &(g_array_index (level->array, SortElt, middle + 1));
-  
-      if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
-	{
-	  GtkTreePath *path = gtk_tree_model_sort_elt_get_path (level, tmp_elt);
-	  gtk_tree_model_get_iter (priv->child_model,
-				   &tmp_iter, path);
-	  gtk_tree_path_free (path);
-	}
-      else
-	tmp_iter = tmp_elt->iter;
-  
-      if (priv->order == GTK_SORT_ASCENDING)
-	cmp = (* func) (GTK_TREE_MODEL (priv->child_model),
-			&tmp_iter, iter, data);
-      else
-	cmp = (* func) (GTK_TREE_MODEL (priv->child_model),
-			iter, &tmp_iter, data);
-
-      if (cmp <= 0)
-	start = middle + 1;
-      else
-	end = middle;
-    }
-
-  if (cmp <= 0)
-    return middle + 1;
-  else
-    return middle;
-}
-
 static gboolean
 gtk_tree_model_sort_insert_value (GtkTreeModelSort *tree_model_sort,
 				  SortLevel        *level,
@@ -2000,39 +1993,41 @@ gtk_tree_model_sort_insert_value (GtkTreeModelSort *tree_model_sort,
 				  GtkTreeIter      *s_iter)
 {
   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
-  gint offset, index, i;
+  SortElt *elt;
+  SortData data;
+  gint offset;
 
-  SortElt elt;
-  SortElt *tmp_elt;
+  elt = sort_elt_new ();
 
   offset = gtk_tree_path_get_indices (s_path)[gtk_tree_path_get_depth (s_path) - 1];
 
   if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
-    elt.iter = *s_iter;
-  elt.offset = offset;
-  elt.zero_ref_count = 0;
-  elt.ref_count = 0;
-  elt.children = NULL;
+    elt->iter = *s_iter;
+  elt->offset = offset;
+  elt->zero_ref_count = 0;
+  elt->ref_count = 0;
+  elt->children = NULL;
 
   /* update all larger offsets */
-  tmp_elt = SORT_ELT (level->array->data);
-  for (i = 0; i < level->array->len; i++, tmp_elt++)
-    if (tmp_elt->offset >= offset)
-      tmp_elt->offset++;
+  g_sequence_foreach (level->seq, increase_offset_iter, GINT_TO_POINTER (offset));
+
+  fill_sort_data (&data, tree_model_sort, level);
 
   if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
       priv->default_sort_func == NO_SORT_FUNC)
-    index = offset;
+    {
+      elt->siter = g_sequence_insert_sorted (level->seq, elt,
+                                             gtk_tree_model_sort_offset_compare_func,
+                                             &data);
+    }
   else
-    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
-                                                   level, s_iter,
-                                                   -1);
+    {
+      elt->siter = g_sequence_insert_sorted (level->seq, elt,
+                                             gtk_tree_model_sort_compare_func,
+                                             &data);
+    }
 
-  g_array_insert_vals (level->array, index, &elt, 1);
-  tmp_elt = SORT_ELT (level->array->data);
-  for (i = 0; i < level->array->len; i++, tmp_elt++)
-    if (tmp_elt->children)
-      tmp_elt->children->parent_elt = tmp_elt;
+  free_sort_data (&data);
 
   return TRUE;
 }
@@ -2189,7 +2184,8 @@ gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_mode
 
   for (i = 0; i < gtk_tree_path_get_depth (child_path); i++)
     {
-      gint j;
+      SortElt *tmp;
+      GSequenceIter *siter;
       gboolean found_child = FALSE;
 
       if (!level)
@@ -2198,26 +2194,23 @@ gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_mode
 	  return NULL;
 	}
 
-      if (child_indices[i] >= level->array->len)
+      if (child_indices[i] >= g_sequence_get_length (level->seq))
 	{
 	  gtk_tree_path_free (retval);
 	  return NULL;
 	}
-      for (j = 0; j < level->array->len; j++)
-	{
-	  if ((g_array_index (level->array, SortElt, j)).offset == child_indices[i])
-	    {
-	      gtk_tree_path_append_index (retval, j);
-	      if (g_array_index (level->array, SortElt, j).children == NULL && build_levels)
-		{
-		  gtk_tree_model_sort_build_level (tree_model_sort, level,
-                                                   &g_array_index (level->array, SortElt, j));
-		}
-	      level = g_array_index (level->array, SortElt, j).children;
-	      found_child = TRUE;
-	      break;
-	    }
-	}
+      tmp = lookup_elt_with_offset (tree_model_sort, level,
+                                    child_indices[i], &siter);
+      if (tmp)
+        {
+          gtk_tree_path_append_index (retval, g_sequence_iter_get_position (siter));
+          if (tmp->children == NULL && build_levels)
+            gtk_tree_model_sort_build_level (tree_model_sort, level, tmp);
+
+          level = tmp->children;
+          found_child = TRUE;
+        }
+
       if (! found_child)
 	{
 	  gtk_tree_path_free (retval);
@@ -2336,18 +2329,26 @@ gtk_tree_model_sort_convert_path_to_child_path (GtkTreeModelSort *tree_model_sor
 
   for (i = 0; i < gtk_tree_path_get_depth (sorted_path); i++)
     {
-      gint count = sorted_indices[i];
+      SortElt *elt = NULL;
+      GSequenceIter *siter;
 
       if ((level == NULL) ||
-	  (level->array->len <= count))
+	  (g_sequence_get_length (level->seq) <= sorted_indices[i]))
 	{
 	  gtk_tree_path_free (retval);
 	  return NULL;
 	}
 
-      if (g_array_index (level->array, SortElt, count).children == NULL)
-	gtk_tree_model_sort_build_level (tree_model_sort, level,
-                                         &g_array_index (level->array, SortElt, count));
+      siter = g_sequence_get_iter_at_pos (level->seq, sorted_indices[i]);
+      if (g_sequence_iter_is_end (siter))
+        {
+          gtk_tree_path_free (retval);
+          return NULL;
+        }
+
+      elt = GET_ELT (siter);
+      if (elt->children == NULL)
+	gtk_tree_model_sort_build_level (tree_model_sort, level, elt);
 
       if (level == NULL)
         {
@@ -2355,8 +2356,8 @@ gtk_tree_model_sort_convert_path_to_child_path (GtkTreeModelSort *tree_model_sor
 	  break;
 	}
 
-      gtk_tree_path_append_index (retval, g_array_index (level->array, SortElt, count).offset);
-      level = g_array_index (level->array, SortElt, count).children;
+      gtk_tree_path_append_index (retval, elt->offset);
+      level = elt->children;
     }
  
   return retval;
@@ -2450,7 +2451,7 @@ gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
   g_return_if_fail (length > 0);
 
   new_level = g_new (SortLevel, 1);
-  new_level->array = g_array_sized_new (FALSE, FALSE, sizeof (SortElt), length);
+  new_level->seq = g_sequence_new (sort_elt_free);
   new_level->ref_count = 0;
   new_level->parent_level = parent_level;
   new_level->parent_elt = parent_elt;
@@ -2474,15 +2475,17 @@ gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
 
   for (i = 0; i < length; i++)
     {
-      SortElt sort_elt;
-      sort_elt.offset = i;
-      sort_elt.zero_ref_count = 0;
-      sort_elt.ref_count = 0;
-      sort_elt.children = NULL;
+      SortElt *sort_elt;
+
+      sort_elt = sort_elt_new ();
+      sort_elt->offset = i;
+      sort_elt->zero_ref_count = 0;
+      sort_elt->ref_count = 0;
+      sort_elt->children = NULL;
 
       if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
 	{
-	  sort_elt.iter = iter;
+	  sort_elt->iter = iter;
 	  if (gtk_tree_model_iter_next (priv->child_model, &iter) == FALSE &&
 	      i < length - 1)
 	    {
@@ -2513,7 +2516,8 @@ gtk_tree_model_sort_build_level (GtkTreeModelSort *tree_model_sort,
 	      return;
 	    }
 	}
-      g_array_append_val (new_level->array, sort_elt);
+
+      sort_elt->siter = g_sequence_append (new_level->seq, sort_elt);
     }
 
   /* sort level */
@@ -2527,15 +2531,21 @@ gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
                                 gboolean          unref)
 {
   GtkTreeModelSortPrivate *priv = tree_model_sort->priv;
-  gint i;
+  GSequenceIter *siter;
+  GSequenceIter *end_siter;
 
   g_assert (sort_level);
 
-  for (i = 0; i < sort_level->array->len; i++)
+  end_siter = g_sequence_get_end_iter (sort_level->seq);
+  for (siter = g_sequence_get_begin_iter (sort_level->seq);
+       siter != end_siter;
+       siter = g_sequence_iter_next (siter))
     {
-      if (g_array_index (sort_level->array, SortElt, i).children)
-	gtk_tree_model_sort_free_level (tree_model_sort,
-					SORT_LEVEL (g_array_index (sort_level->array, SortElt, i).children), unref);
+      SortElt *elt = g_sequence_get (siter);
+
+      if (elt->children)
+        gtk_tree_model_sort_free_level (tree_model_sort,
+                                        elt->children, unref);
     }
 
   if (sort_level->ref_count == 0)
@@ -2574,8 +2584,8 @@ gtk_tree_model_sort_free_level (GtkTreeModelSort *tree_model_sort,
   else
     priv->root = NULL;
 
-  g_array_free (sort_level->array, TRUE);
-  sort_level->array = NULL;
+  g_sequence_free (sort_level->seq);
+  sort_level->seq = NULL;
 
   g_free (sort_level);
   sort_level = NULL;
@@ -2596,18 +2606,24 @@ gtk_tree_model_sort_increment_stamp (GtkTreeModelSort *tree_model_sort)
 }
 
 static void
+gtk_tree_model_sort_clear_cache_helper_iter (gpointer data,
+                                             gpointer user_data)
+{
+  GtkTreeModelSort *tree_model_sort = user_data;
+  SortElt *elt = data;
+
+  if (elt->zero_ref_count > 0)
+    gtk_tree_model_sort_clear_cache_helper (tree_model_sort, elt->children);
+}
+
+static void
 gtk_tree_model_sort_clear_cache_helper (GtkTreeModelSort *tree_model_sort,
 					SortLevel        *level)
 {
-  gint i;
-
   g_assert (level != NULL);
 
-  for (i = 0; i < level->array->len; i++)
-    {
-      if (g_array_index (level->array, SortElt, i).zero_ref_count > 0)
-	gtk_tree_model_sort_clear_cache_helper (tree_model_sort, g_array_index (level->array, SortElt, i).children);
-    }
+  g_sequence_foreach (level->seq, gtk_tree_model_sort_clear_cache_helper_iter,
+                      tree_model_sort);
 
   if (level->ref_count == 0 && level != tree_model_sort->priv->root)
     gtk_tree_model_sort_free_level (tree_model_sort, level, TRUE);
@@ -2670,11 +2686,14 @@ static gboolean
 gtk_tree_model_sort_iter_is_valid_helper (GtkTreeIter *iter,
 					  SortLevel   *level)
 {
-  gint i;
+  GSequenceIter *siter;
+  GSequenceIter *end_siter;
 
-  for (i = 0; i < level->array->len; i++)
+  end_siter = g_sequence_get_end_iter (level->seq);
+  for (siter = g_sequence_get_begin_iter (level->seq);
+       siter != end_siter; siter = g_sequence_iter_next (siter))
     {
-      SortElt *elt = &g_array_index (level->array, SortElt, i);
+      SortElt *elt = g_sequence_get (siter);
 
       if (iter->user_data == level && iter->user_data2 == elt)
 	return TRUE;
[Date Prev][Date Next] [Thread Prev][Thread Next] [Thread Index] [Date Index] [Author Index]