Re: g_s?list_sort doesn't do stable sort



Tim Janik <timj gtk org> writes:

> On 8 Aug 2000, Kristian Hogsberg Kristensen wrote:
> 
> > 
> > Hi,
> > 
> > The g_s?list_sort functions don't do a stable sort of the list
> > elements, that is they don't preserve the order of elements considered
> > equal by the comparison function.  The patch to fix this is really

[...]

> ok, i agree mith maciej here.
> you had a typo in your patch though, so if you could
> actually test it out and resubmit it against recent
> CVS (cvs diff -u) that'd be good.

Yeah, that's a bit sloppy, I guess :).  

> if i may be so bold, i wouldn't mind if you also cleaned up
> the indentation and missing spaces in the surrounding
> functions ;)

Sure, but they are actually OK, indentation-wise.  However, I changed
the function pointer argument to just func instead of compare_func,
since this seems to be convention.  Also, is there a reason
g_list_sort_merge shouldn't be publicly available?  It's a general
purpose list function, and it is already in the library.  I changed it
to g_list_merge and made it public.

Finally, I added test cases for the new merge functions and a test
that checks if g_list_sort now actually does a stable sort.

Btw, the patch below is against glib-1.3.1, since I couldn't get
through to the CVS server. 

regards,
Kristian

diff -ur glib-1.3.1-orig/glib.h glib-1.3.1/glib.h
--- glib-1.3.1-orig/glib.h	Fri Jul 14 18:31:28 2000
+++ glib-1.3.1/glib.h	Fri Sep 29 16:17:24 2000
@@ -1017,8 +1017,11 @@
 void   g_list_foreach		(GList		*list,
 				 GFunc		 func,
 				 gpointer	 user_data);
+GList* g_list_merge             (GList          *list1, 
+				 GList          *list2,
+				 GCompareFunc    func);
 GList* g_list_sort              (GList          *list,
-		                 GCompareFunc    compare_func);
+		                 GCompareFunc    func);
 gpointer g_list_nth_data	(GList		*list,
 				 guint		 n);
 #define g_list_previous(list)	((list) ? (((GList *)(list))->prev) : NULL)
@@ -1071,8 +1074,11 @@
 void	g_slist_foreach		(GSList		*list,
 				 GFunc		 func,
 				 gpointer	 user_data);
-GSList*  g_slist_sort           (GSList          *list,
-		                 GCompareFunc    compare_func);
+GSList* g_slist_merge           (GSList         *list1,
+				 GSList         *list2,
+				 GCompareFunc    func);
+GSList* g_slist_sort            (GSList         *list,
+		                 GCompareFunc    func);
 gpointer g_slist_nth_data	(GSList		*list,
 				 guint		 n);
 #define  g_slist_next(slist)	((slist) ? (((GSList *)(slist))->next) : NULL)
diff -ur glib-1.3.1-orig/glist.c glib-1.3.1/glist.c
--- glib-1.3.1-orig/glist.c	Tue Apr 18 16:01:33 2000
+++ glib-1.3.1/glist.c	Thu Sep 28 17:50:55 2000
@@ -595,85 +595,92 @@
     return list;
 }
 
-static GList *
-g_list_sort_merge (GList       *l1, 
-		   GList       *l2,
-		   GCompareFunc compare_func)
+GList*
+g_list_merge (GList        *list1, 
+	      GList        *list2,
+	      GCompareFunc  func)
 {
-  GList list, *l, *lprev;
+  GList list, *last, *lprev;
 
-  l = &list; 
+  g_return_val_if_fail (func != NULL, NULL);
+
+  last = &list; 
   lprev = NULL;
 
-  while (l1 && l2)
+  while (list1 && list2)
     {
-      if (compare_func (l1->data, l2->data) < 0)
+      if ((*func) (list1->data, list2->data) <= 0)
         {
-	  l->next = l1;
-	  l = l->next;
-	  l->prev = lprev; 
-	  lprev = l;
-	  l1 = l1->next;
+	  last->next = list1;
+	  last = last->next;
+	  last->prev = lprev; 
+	  lprev = last;
+	  list1 = list1->next;
         } 
       else 
 	{
-	  l->next = l2;
-	  l = l->next;
-	  l->prev = lprev; 
-	  lprev = l;
-	  l2 = l2->next;
+	  last->next = list2;
+	  last = last->next;
+	  last->prev = lprev; 
+	  lprev = last;
+	  list2 = list2->next;
         }
     }
-  l->next = l1 ? l1 : l2;
-  l->next->prev = l;
+
+  last->next = list1 ? list1 : list2;
+  last->next->prev = last;
 
   return list.next;
 }
 
 GList* 
-g_list_sort (GList       *list,
-	     GCompareFunc compare_func)
+g_list_sort (GList        *list,
+	     GCompareFunc  func)
 {
-  GList *l1, *l2;
+  GList *list1, *list2;
   
-  if (!list) 
-    return NULL;
-  if (!list->next) 
+  g_return_val_if_fail (func != NULL, list);
+
+  if (!list || !list->next)
     return list;
   
-  l1 = list; 
-  l2 = list->next;
+  list1 = list; 
+  list2 = list->next;
 
-  while ((l2 = l2->next) != NULL)
+  while ((list2 = list2->next) != NULL)
     {
-      if ((l2 = l2->next) == NULL) 
+      if ((list2 = list2->next) == NULL) 
 	break;
-      l1 = l1->next;
+      list1 = list1->next;
     }
-  l2 = l1->next; 
-  l1->next = NULL; 
 
-  return g_list_sort_merge (g_list_sort (list, compare_func),
-			    g_list_sort (l2,   compare_func),
-			    compare_func);
+  list2 = list1->next; 
+  list1->next = NULL; 
+
+  return g_list_merge (g_list_sort (list, func),
+		       g_list_sort (list2, func),
+		       func);
 }
 
 GList* 
-g_list_sort2 (GList       *list,
-	      GCompareFunc compare_func)
+g_list_sort2 (GList        *list,
+	      GCompareFunc  func)
 {
   GSList *runs = NULL;
   GList *tmp;
 
+  g_return_val_if_fail (func != NULL, list);
+
   /* Degenerate case.  */
-  if (!list) return NULL;
+  if (!list || !list->next)
+    return list;
 
   /* Assume: list = [12,2,4,11,2,4,6,1,1,12].  */
   for (tmp = list; tmp; )
     {
       GList *tmp2;
       for (tmp2 = tmp;
-	   tmp2->next && compare_func (tmp2->data, tmp2->next->data) <= 0;
+	   tmp2->next && (*func) (tmp2->data, tmp2->next->data) <= 0;
 	   tmp2 = tmp2->next)
 	/* Nothing */;
       runs = g_slist_append (runs, tmp);
@@ -689,9 +696,9 @@
       dst = src = runs;
       while (src && src->next)
 	{
-	  dst->data = g_list_sort_merge (src->data,
-					 src->next->data,
-					 compare_func);
+	  dst->data = g_list_merge (src->data,
+				    src->next->data,
+				    func);
 	  dstprev = dst;
 	  dst = dst->next;
 	  src = src->next->next;
diff -ur glib-1.3.1-orig/gslist.c glib-1.3.1/gslist.c
--- glib-1.3.1-orig/gslist.c	Fri May 19 10:18:29 2000
+++ glib-1.3.1/gslist.c	Thu Sep 28 18:08:00 2000
@@ -580,57 +580,58 @@
     }
 }
 
-static GSList* 
-g_slist_sort_merge  (GSList      *l1, 
-		     GSList      *l2,
-		     GCompareFunc compare_func)
+GSList* 
+g_slist_merge  (GSList       *list1,
+		GSList       *list2,
+		GCompareFunc  func)
 {
-  GSList list, *l;
+  GSList list, *last;
 
-  l=&list;
+  last = &list;
 
-  while (l1 && l2)
+  while (list1 && list2)
     {
-      if (compare_func(l1->data,l2->data) < 0)
+      if ((*func) (list1->data, list2->data) <= 0)
         {
-	  l=l->next=l1;
-	  l1=l1->next;
+	  last->next = list1;
+	  last = last->next;
+	  list1 = list1->next;
         } 
       else 
 	{
-	  l=l->next=l2;
-	  l2=l2->next;
+	  last->next = list2;
+	  last = last->next;
+	  list2 = list2->next;
         }
     }
-  l->next= l1 ? l1 : l2;
+  last->next = list1 ? list1 : list2;
   
   return list.next;
 }
 
 GSList* 
 g_slist_sort (GSList       *list,
-	      GCompareFunc compare_func)
+	      GCompareFunc  func)
 {
-  GSList *l1, *l2;
+  GSList *list1, *list2;
 
-  if (!list) 
-    return NULL;
-  if (!list->next) 
+  if (!list || !list->next) 
     return list;
 
-  l1 = list; 
-  l2 = list->next;
+  list1 = list; 
+  list2 = list->next;
 
-  while ((l2 = l2->next) != NULL)
+  while ((list2 = list2->next) != NULL)
     {
-      if ((l2 = l2->next) == NULL) 
+      if ((list2 = list2->next) == NULL) 
 	break;
-      l1=l1->next;
+      list1 = list1->next;
     }
-  l2 = l1->next; 
-  l1->next = NULL;
 
-  return g_slist_sort_merge (g_slist_sort (list, compare_func),
-			     g_slist_sort (l2,   compare_func),
-			     compare_func);
+  list2 = list1->next; 
+  list1->next = NULL;
+
+  return g_slist_merge (g_slist_sort (list, func),
+			g_slist_sort (list2, func),
+			func);
 }
diff -ur glib-1.3.1-orig/tests/list-test.c glib-1.3.1/tests/list-test.c
--- glib-1.3.1-orig/tests/list-test.c	Wed Feb 24 07:14:20 1999
+++ glib-1.3.1/tests/list-test.c	Fri Sep 29 16:08:28 2000
@@ -71,6 +71,98 @@
   return two-one;
 }
 
+static void
+random_permutation (int *numbers, int length)
+{
+  int i;
+
+  for (i = 0; i < length; i++)
+    numbers[i] = i;
+
+  for (i = 0; i < length; i++)
+    {
+      int tmp, index;
+
+      index = g_random_int_range (i, length);
+      tmp = numbers[i];
+      numbers[i] = numbers[index];
+      numbers[index] = tmp;
+    }
+}
+
+static void
+test_merge (void)
+{
+  GList *list, *l1, *l2, *t;
+  int i, numbers[20];
+
+  random_permutation (numbers, 20);
+  l1 = NULL;
+  l2 = NULL;
+
+  for (i = 0; i < 10; i++)
+    {
+      l1 = g_list_prepend (l1, &numbers[i]);
+      l2 = g_list_prepend (l2, &numbers[i + 10]);
+    }
+
+  l1 = g_list_sort (l1, my_list_compare_one);
+  l2 = g_list_sort (l2, my_list_compare_one);
+  list = g_list_merge (l1, l2, my_list_compare_one);
+  g_assert (g_list_length (list) == 20);
+
+  for (i = 0; i < 20; i++)
+    {
+      t = g_list_nth (list, i);
+      g_assert (*((gint *) t->data) == i);
+    }
+}
+
+static void
+test_sort (void)
+{
+  GList *list, *t, *prev;
+  int i, numbers[20], pairs[20][2];
+
+  random_permutation (numbers, 20);
+  list = NULL;
+
+  for (i = 0; i < 20; i++)
+    list = g_list_prepend (list, &numbers[i]);
+
+  list = g_list_sort (list, my_list_compare_one);
+
+  for (i = 0; i < 20; i++)
+    {
+      t = g_list_nth (list, i);
+      g_assert (*((gint*) t->data) == i);
+    }
+  g_list_free(list);
+
+  for (i = 0; i < 20; i++)
+    {
+      pairs[i][0] = g_random_int_range (0, 5);
+      pairs[i][1] = i;
+    }
+
+  list = NULL;
+  for (i = 0; i < 20; i++)
+    list = g_list_prepend (list, pairs[i]);
+  list = g_list_reverse (list);
+
+  list = g_list_sort (list, my_list_compare_one);
+  
+  prev = NULL;
+  for (t = list; t != NULL; t = t->next)
+    {
+      if (prev != NULL && ((int *) prev->data)[0] == ((int *) t->data)[0])
+	g_assert (((int *) prev->data)[1] <= ((int *) t->data)[1]);
+      prev = t;
+    }
+
+  g_list_free (list);
+}
+
 int
 main (int   argc,
       char *argv[])
@@ -129,25 +221,10 @@
     }
 
   g_list_free (list);
-  list = NULL;
 
-  for (i = 0; i < 10; i++)
-    list = g_list_prepend (list, &morenums[i]);
-
-  list = g_list_sort (list, my_list_compare_two);
-
-  /*
-  g_print("\n");
-  g_list_foreach (list, my_list_print, NULL);
-  */
+  test_sort ();
 
-  for (i = 0; i < 10; i++)
-    {
-      t = g_list_nth (list, i);
-      g_assert (*((gint*) t->data) == (9 - i));
-    }
-
-  g_list_free (list);
+  test_merge ();
 
   return 0;
 }
diff -ur glib-1.3.1-orig/tests/slist-test.c glib-1.3.1/tests/slist-test.c
--- glib-1.3.1-orig/tests/slist-test.c	Wed Feb 24 07:14:23 1999
+++ glib-1.3.1/tests/slist-test.c	Fri Sep 29 16:04:35 2000
@@ -71,6 +71,100 @@
   return two-one;
 }
 
+static void
+random_permutation (int *numbers, int length)
+{
+  int i;
+
+  for (i = 0; i < length; i++)
+    numbers[i] = i;
+
+  for (i = 0; i < length; i++)
+    {
+      int tmp, index;
+
+      index = g_random_int_range (i, length);
+      tmp = numbers[i];
+      numbers[i] = numbers[index];
+      numbers[index] = tmp;
+    }
+}
+
+static void
+test_merge (void)
+{
+  GSList *slist, *sl1, *sl2, *st;
+  int i, numbers[20];
+
+  random_permutation (numbers, 20);
+  sl1 = NULL;
+  sl2 = NULL;
+
+  for (i = 0; i < 10; i++)
+    {
+      sl1 = g_slist_prepend (sl1, &numbers[i]);
+      sl2 = g_slist_prepend (sl2, &numbers[i + 10]);
+    }
+
+  sl1 = g_slist_sort (sl1, my_list_compare_one);
+  sl2 = g_slist_sort (sl2, my_list_compare_one);
+  slist = g_slist_merge (sl1, sl2, my_list_compare_one);
+  g_assert (g_slist_length (slist) == 20);
+
+  for (i = 0; i < 20; i++)
+    {
+      st = g_slist_nth (slist, i);
+      g_assert (*((gint *) st->data) == i);
+    }
+
+  g_slist_free (slist);
+}
+
+static void
+test_sort (void)
+{
+  GSList *slist, *st, *prev;
+  int i, numbers[20], pairs[20][2];
+
+  random_permutation (numbers, 20);
+  slist = NULL;
+
+  for (i = 0; i < 20; i++)
+    slist = g_slist_prepend (slist, &numbers[i]);
+
+  slist = g_slist_sort (slist, my_list_compare_one);
+
+  for (i = 0; i < 20; i++)
+    {
+      st = g_slist_nth (slist, i);
+      g_assert (*((gint*) st->data) == i);
+    }
+  g_slist_free(slist);
+
+  for (i = 0; i < 20; i++)
+    {
+      pairs[i][0] = g_random_int_range (0, 5);
+      pairs[i][1] = i;
+    }
+
+  slist = NULL;
+  for (i = 0; i < 20; i++)
+    slist = g_slist_prepend (slist, pairs[i]);
+  slist = g_slist_reverse (slist);
+
+  slist = g_slist_sort (slist, my_list_compare_one);
+  
+  prev = NULL;
+  for (st = slist; st != NULL; st = st->next)
+    {
+      if (prev != NULL && ((int *) prev->data)[0] == ((int *) st->data)[0])
+	g_assert (((int *) prev->data)[1] <= ((int *) st->data)[1]);
+      prev = st;
+    }
+
+  g_slist_free (slist);
+}
+
 int
 main (int   argc,
       char *argv[])
@@ -128,23 +222,9 @@
   g_slist_free(slist);
   slist = NULL;
 
-  for (i = 0; i < 10; i++)
-    slist = g_slist_prepend (slist, &morenums[i]);
-
-  slist = g_slist_sort (slist, my_list_compare_two);
-
-  /*
-  g_print("\n");
-  g_slist_foreach (slist, my_list_print, NULL);
-  */
+  test_sort ();
 
-  for (i = 0; i < 10; i++)
-    {
-      st = g_slist_nth (slist, i);
-      g_assert (*((gint*) st->data) == (9 - i));
-    }
-
-  g_slist_free(slist);
+  test_merge ();
 
   return 0;
 }




[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]