[glib] Make g_array_sort* methods use a stable sort

[Alexander Larsson <alexl src gnome org>]

commit a43dd7435af92d70fa0ef5a2c48e77156b0ad304
Author: Alexander Larsson <alexl redhat com>
Date:   Wed Mar 14 21:17:47 2012 +0100

    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 files 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,