From 9814143feb4a1c8f34988f28c3f469a74f924da1 Mon Sep 17 00:00:00 2001
From: Pekka Riikonen <priikone@silcnet.org>
Date: Sat, 28 Jun 2008 16:57:45 +0300
Subject: [PATCH] Added silc_list_sort, sorts SilcList using Gnome Sort
 algorithm

---
 lib/silcutil/silclist.h            | 60 ++++++++++++++++++++++++++++++
 lib/silcutil/tests/test_silclist.c | 49 +++++++++++++++++++++++-
 2 files changed, 108 insertions(+), 1 deletion(-)

diff --git a/lib/silcutil/silclist.h b/lib/silcutil/silclist.h
index 52454c30..7336c5e1 100644
--- a/lib/silcutil/silclist.h
+++ b/lib/silcutil/silclist.h
@@ -394,4 +394,64 @@ void *__silc_list_pop(SilcList *list)
   return head;
 }
 
+/****f* silcutil/silc_list_sort
+ *
+ * SYNOPSIS
+ *
+ *    void silc_list_sort(SilcList *list,
+ *                        int (*compare)(void *entry1, void *entry2,
+ *                                       void *context), void *context);
+ *
+ * DESCRIPTION
+ *
+ *    Sort the list.  The `compare' function will be called with `context'
+ *    to do comparison between the entries.  The `compare' must return
+ *    less than, equal to, or greater than zero if the first argument is
+ *    considered to be respectively less than, equal to, or greater than
+ *    the second.  The entries are then sorted in ascending order.
+ *
+ * NOTES
+ *
+ *    The list must be initialized with silc_list_init_prev for sorting
+ *    to work.
+ *
+ ***/
+#define silc_list_sort(x, comp, ctx) __silc_list_sort(&(x), comp, ctx)
+static inline
+void __silc_list_sort(SilcList *list,
+		      int (*compare)(void *entry1, void *entry2,
+				     void *context), void *context)
+{
+  void *c_cur, *c_prev;
+
+  SILC_ASSERT(list->prev_set);
+  if (!list->prev_set)
+    return;
+
+  if (silc_list_count(*list) < 2)
+    return;
+
+  /* Gnome sort */
+  silc_list_start(*list);
+  c_prev = silc_list_get(*list);
+  while ((c_cur = silc_list_get(*list))) {
+    if (compare(c_prev, c_cur, context) > 0) {
+      list->current = *__silc_list_prev(*list, c_prev);
+      silc_list_del(*list, c_prev);
+      silc_list_insert(*list, c_cur, c_prev);
+
+      if (list->current) {
+        c_prev = list->current;
+        list->current = c_cur;
+        continue;
+      }
+      list->current = c_cur;
+      silc_list_get(*list);
+    }
+    c_prev = c_cur;
+  }
+
+  list->current = NULL;
+}
+
 #endif /* SILCLIST_H */
diff --git a/lib/silcutil/tests/test_silclist.c b/lib/silcutil/tests/test_silclist.c
index 70c1cb0e..86de91e7 100644
--- a/lib/silcutil/tests/test_silclist.c
+++ b/lib/silcutil/tests/test_silclist.c
@@ -8,11 +8,21 @@ struct foo {
   struct foo *prev;
 };
 
+static int compare(void *e1, void *e2, void *context)
+{
+  struct foo *ee1 = e1, *ee2 = e2;
+  SILC_LOG_DEBUG(("entry %d, %p, next=%p, prev=%p", ee1->i, ee1, ee1->next,
+		   ee1->prev));
+  SILC_LOG_DEBUG(("> entry %d, %p, next=%p, prev=%p", ee2->i, ee2, ee2->next,
+		   ee2->prev));
+  return ee1->i - ee2->i;
+}
+
 int main(int argc, char **argv)
 {
   SilcBool success = FALSE;
   SilcList list;
-  struct foo *f, *f1, *f2, *f3, *f4;
+  struct foo *f, *f1, *f2, *f3, *f4, *f5, *f6, *f7;
 
   if (argc > 1 && !strcmp(argv[1], "-d")) {
     silc_log_debug(TRUE);
@@ -37,6 +47,18 @@ int main(int argc, char **argv)
   if (!f4)
     goto err;
   f4->i = 4;
+  f5 = silc_calloc(1, sizeof(*f4));
+  if (!f5)
+    goto err;
+  f5->i = 5;
+  f6 = silc_calloc(1, sizeof(*f4));
+  if (!f6)
+    goto err;
+  f6->i = 6;
+  f7 = silc_calloc(1, sizeof(*f4));
+  if (!f7)
+    goto err;
+  f7->i = 7;
 
   SILC_LOG_DEBUG(("Add one entry"));
   silc_list_add(list, f1);
@@ -162,6 +184,31 @@ int main(int argc, char **argv)
   if (silc_list_count(list))
     goto err;
 
+  /* Sort */
+  silc_list_init_prev(list, struct foo, next, prev);
+  silc_list_add(list, f2);
+  silc_list_add(list, f7);
+  silc_list_add(list, f4);
+  silc_list_add(list, f6);
+  silc_list_add(list, f5);
+  silc_list_add(list, f1);
+  silc_list_add(list, f3);
+
+  SILC_LOG_DEBUG(("Unsorted list"));
+  silc_list_start(list);
+  while ((f = silc_list_get(list)) != SILC_LIST_END)
+    SILC_LOG_DEBUG(("entry %d, %p, next=%p, prev=%p", f->i, f, f->next,
+		   f->prev));
+
+  SILC_LOG_DEBUG(("Sorting"));  
+  silc_list_sort(list, compare, NULL);
+
+  SILC_LOG_DEBUG(("Sorted list"));
+  silc_list_start(list);
+  while ((f = silc_list_get(list)) != SILC_LIST_END)
+    SILC_LOG_DEBUG(("entry %d, %p, next=%p, prev=%p", f->i, f, f->next,
+		   f->prev));
+
   success = TRUE;
 
  err:
-- 
2.24.0