From a43dd7435af92d70fa0ef5a2c48e77156b0ad304 Mon Sep 17 00:00:00 2001
From: Alexander Larsson <alexl@redhat.com>
Date: Wed, 14 Mar 2012 21:17:47 +0100
Subject: [PATCH] Make g_array_sort* methods use a stable sort

Also, remove previous comments about sort stability in g_array_sort docs,
as the method that was explained does not work. Adds a new comment
about this.

https://bugzilla.gnome.org/show_bug.cgi?id=672095
---
 glib/garray.c | 42 +++++++++++++++++++++++-------------------
 1 file changed, 23 insertions(+), 19 deletions(-)

diff --git a/glib/garray.c b/glib/garray.c
index e6894a6..567774c 100644
--- a/glib/garray.c
+++ b/glib/garray.c
@@ -693,11 +693,7 @@ g_array_remove_range (GArray *farray,
  * than second arg, zero for equal, greater zero if first arg is
  * greater than second arg).
  *
- * If two array elements compare equal, their order in the sorted array
- * is undefined. If you want equal elements to keep their order (i.e.
- * you want a stable sort) you can write a comparison function that,
- * if two elements would otherwise compare equal, compares them by
- * their addresses.
+ * This is guaranteed to be a stable sort since version 2.32.
  **/
 void
 g_array_sort (GArray       *farray,
@@ -707,10 +703,12 @@ g_array_sort (GArray       *farray,
 
   g_return_if_fail (array != NULL);
 
-  qsort (array->data,
-	 array->len,
-	 array->elt_size,
-	 compare_func);
+  /* Don't use qsort as we want a guaranteed stable sort */
+  g_qsort_with_data (array->data,
+		     array->len,
+		     array->elt_size,
+		     (GCompareDataFunc)compare_func,
+		     NULL);
 }
 
 /**
@@ -721,6 +719,12 @@ g_array_sort (GArray       *farray,
  *
  * Like g_array_sort(), but the comparison function receives an extra
  * user data argument.
+ *
+ * This is guaranteed to be a stable sort since version 2.32.
+ *
+ * There used to be a comment here about making the sort stable by
+ * using the addresses of the elements in the comparison function.
+ * This did not actually work, so any such code should be removed.
  **/
 void
 g_array_sort_with_data (GArray           *farray,
@@ -1358,15 +1362,11 @@ g_ptr_array_add (GPtrArray *farray,
  * than second arg, zero for equal, greater than zero if irst arg is
  * greater than second arg).
  *
- * If two array elements compare equal, their order in the sorted array
- * is undefined. If you want equal elements to keep their order (i.e.
- * you want a stable sort) you can write a comparison function that,
- * if two elements would otherwise compare equal, compares them by
- * their addresses.
- *
  * <note><para>The comparison function for g_ptr_array_sort() doesn't
  * take the pointers from the array as arguments, it takes pointers to
  * the pointers in the array.</para></note>
+ *
+ * This is guaranteed to be a stable sort since version 2.32.
  **/
 void
 g_ptr_array_sort (GPtrArray    *array,
@@ -1374,10 +1374,12 @@ g_ptr_array_sort (GPtrArray    *array,
 {
   g_return_if_fail (array != NULL);
 
-  qsort (array->pdata,
-	 array->len,
-	 sizeof (gpointer),
-	 compare_func);
+  /* Don't use qsort as we want a guaranteed stable sort */
+  g_qsort_with_data (array->pdata,
+		     array->len,
+		     sizeof (gpointer),
+		     (GCompareDataFunc)compare_func,
+		     NULL);
 }
 
 /**
@@ -1392,6 +1394,8 @@ g_ptr_array_sort (GPtrArray    *array,
  * <note><para>The comparison function for g_ptr_array_sort_with_data()
  * doesn't take the pointers from the array as arguments, it takes
  * pointers to the pointers in the array.</para></note>
+ *
+ * This is guaranteed to be a stable sort since version 2.32.
  **/
 void
 g_ptr_array_sort_with_data (GPtrArray        *array,
-- 
2.7.4