Added g_list_sort() and g_slist_sort() to merge sort GLists and GSLists.

Fri Nov 13 15:17:34 1998  Owen Taylor  <otaylor@redhat.com>

	* glist.c gslist.c glib.h: Added g_list_sort() and
	g_slist_sort() to merge sort GLists and GSLists.
	Submitted by Sven Over <sven.over@ob.kamp.net>
	over a year ago!

	* testglib.c: Test the new sort functions.

1 files changed, 64 insertions, 1 deletions

diff --git a/glist.c b/glist.c
index dc211580a..eaa77d82c 100644
--- a/glist.c
+++ b/glist.c
@@ -106,7 +106,7 @@ void
 g_list_free (GList *list)
 {
   GList *last;
-  
+
   if (list)
     {
       last = g_list_last (list);
@@ -479,3 +479,66 @@ g_list_insert_sorted (GList        *list,
   else
     return list;
 }
+
+static GList *
+g_list_sort_merge (GList       *l1, 
+		   GList       *l2,
+		   GCompareFunc compare_func)
+{
+  GList list, *l, *lprev;
+
+  l = &list; 
+  lprev = NULL;
+
+  while (l1 && l2)
+    {
+      if (compare_func (l1->data, l2->data) < 0)
+        {
+	  l->next = l1;
+	  l = l->next;
+	  l->prev = lprev; 
+	  lprev = l;
+	  l1 = l1->next;
+        } 
+      else 
+	{
+	  l->next = l2;
+	  l = l->next;
+	  l->prev = lprev; 
+	  lprev = l;
+	  l2 = l2->next;
+        }
+    }
+  l->next = l1 ? l1 : l2;
+  l->next->prev = l;
+
+  return list.next;
+}
+
+GList* 
+g_list_sort (GList       *list,
+	     GCompareFunc compare_func)
+{
+  GList *l1, *l2;
+  
+  if (!list) 
+    return NULL;
+  if (!list->next) 
+    return list;
+  
+  l1 = list; 
+  l2 = list->next;
+
+  while ((l2 = l2->next) != NULL)
+    {
+      if ((l2 = l2->next) == NULL) 
+	break;
+      l1 = l1->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);
+}