[glib] tests: Add tests to ensure g_[s]list_sort() are stable sorts

[Philip Withnall <pwithnall src gnome org>]

commit 2cd26714e59f5a95a2c8a263167e61897f97b126
Author: Philip Withnall <withnall endlessm com>
Date:   Thu Nov 16 10:28:22 2017 +0000

    tests: Add tests to ensure g_[s]list_sort() are stable sorts
    
    Given that we guarantee it in the API…
    
    Signed-off-by: Philip Withnall <withnall endlessm com>
    
    https://bugzilla.gnome.org/show_bug.cgi?id=508976

 glib/tests/list.c  |   33 +++++++++++++++++++++++++++++++++
 glib/tests/slist.c |   33 +++++++++++++++++++++++++++++++++
 2 files changed, 66 insertions(+), 0 deletions(-)
---
diff --git a/glib/tests/list.c b/glib/tests/list.c
index a53e326..1b5d6ca 100644
--- a/glib/tests/list.c
+++ b/glib/tests/list.c
@@ -69,6 +69,38 @@ test_list_sort_with_data (void)
   g_list_free (list);
 }
 
+/* Test that the sort is stable. */
+static void
+test_list_sort_stable (void)
+{
+  GList *list = NULL;  /* (element-type utf8) */
+  GList *copy = NULL;  /* (element-type utf8) */
+  gsize i;
+
+  /* Build a test list, already ordered. */
+  for (i = 0; i < SIZE; i++)
+    list = g_list_append (list, g_strdup_printf ("%" G_GSIZE_FORMAT, i / 5));
+
+  /* Take a copy and sort it. */
+  copy = g_list_copy (list);
+  copy = g_list_sort (copy, (GCompareFunc) g_strcmp0);
+
+  /* Compare the two lists, checking pointers are equal to ensure the elements
+   * have been kept stable. */
+  for (i = 0; i < SIZE; i++)
+    {
+      gpointer p1, p2;
+
+      p1 = g_list_nth_data (list, i);
+      p2 = g_list_nth_data (list, i);
+
+      g_assert (p1 == p2);
+    }
+
+  g_list_free (copy);
+  g_list_free_full (list, g_free);
+}
+
 static void
 test_list_insert_sorted (void)
 {
@@ -529,6 +561,7 @@ main (int argc, char *argv[])
 
   g_test_add_func ("/list/sort", test_list_sort);
   g_test_add_func ("/list/sort-with-data", test_list_sort_with_data);
+  g_test_add_func ("/list/sort/stable", test_list_sort_stable);
   g_test_add_func ("/list/insert-sorted", test_list_insert_sorted);
   g_test_add_func ("/list/insert-sorted-with-data", test_list_insert_sorted_with_data);
   g_test_add_func ("/list/reverse", test_list_reverse);
diff --git a/glib/tests/slist.c b/glib/tests/slist.c
index beb4767..1f81743 100644
--- a/glib/tests/slist.c
+++ b/glib/tests/slist.c
@@ -68,6 +68,38 @@ test_slist_sort_with_data (void)
   g_slist_free (slist);
 }
 
+/* Test that the sort is stable. */
+static void
+test_slist_sort_stable (void)
+{
+  GSList *list = NULL;  /* (element-type utf8) */
+  GSList *copy = NULL;  /* (element-type utf8) */
+  gsize i;
+
+  /* Build a test list, already ordered. */
+  for (i = 0; i < SIZE; i++)
+    list = g_slist_append (list, g_strdup_printf ("%" G_GSIZE_FORMAT, i / 5));
+
+  /* Take a copy and sort it. */
+  copy = g_slist_copy (list);
+  copy = g_slist_sort (copy, (GCompareFunc) g_strcmp0);
+
+  /* Compare the two lists, checking pointers are equal to ensure the elements
+   * have been kept stable. */
+  for (i = 0; i < SIZE; i++)
+    {
+      gpointer p1, p2;
+
+      p1 = g_slist_nth_data (list, i);
+      p2 = g_slist_nth_data (list, i);
+
+      g_assert (p1 == p2);
+    }
+
+  g_slist_free (copy);
+  g_slist_free_full (list, g_free);
+}
+
 static void
 test_slist_insert_sorted (void)
 {
@@ -409,6 +441,7 @@ main (int argc, char *argv[])
 
   g_test_add_func ("/slist/sort", test_slist_sort);
   g_test_add_func ("/slist/sort-with-data", test_slist_sort_with_data);
+  g_test_add_func ("/slist/sort/stable", test_slist_sort_stable);
   g_test_add_func ("/slist/insert-sorted", test_slist_insert_sorted);
   g_test_add_func ("/slist/insert-sorted-with-data", test_slist_insert_sorted_with_data);
   g_test_add_func ("/slist/reverse", test_slist_reverse);