add sorting to llist
authorChristian Thaeter <ct@pipapo.org>
Sat, 16 Feb 2008 23:22:51 +0000 (00:22 +0100)
committerChristian Thaeter <ct@pipapo.org>
Sat, 16 Feb 2008 23:22:51 +0000 (00:22 +0100)
src/llist.h

index a478b08..fc4cdf7 100644 (file)
@@ -88,6 +88,7 @@ typedef llist * LList;
 typedef const llist * const_LList;
 typedef llist ** LList_ref;
 
+
 /**
  * Macro to instantiate a local llist.
  * @param name of the llist node
@@ -95,6 +96,14 @@ typedef llist ** LList_ref;
 #define LLIST_AUTO(name) llist name = {&name,&name}
 
 
+/*
+  some macros for convenience
+*/
+#define llist_insert_head(list, element) llist_insert_next (list, element)
+#define llist_insert_tail(list, element) llist_insert_prev (list, element)
+#define llist_head llist_next
+#define llist_tail llist_prev
+
 /**
  * cast back from a member of a structure to a pointer of the structure
  */
@@ -516,24 +525,41 @@ LLIST_FUNC (LList llist_get_nth_stop (LList self, int n, const_LList stop),
             return self;
 );
 
-/*
-  some macros for convenience
-*/
-#define llist_insert_head(list, element) llist_insert_next (list, element)
-#define llist_insert_tail(list, element) llist_insert_prev (list, element)
-#define llist_head llist_next
-#define llist_tail llist_prev
 
-#endif /* LLIST_H */
-/*
-// Local Variables:
-// mode: C
-// c-file-style: "gnu"
-// End:
-// arch-tag: e8fe4a59-fd55-4c45-b860-5cd1e0771213
-// end_of_file
-*/
+/**
+ * Sort a list.
+ * @param self list to be sorted
+ * @param cmp function takeing 2 LLists
+ * simple recursive mergesort
+ */
+typedef int (*llist_cmpfn)(LList a, LList b);
+
+LLIST_FUNC (LList llist_sort (LList self, llist_cmpfn cmp),
+            llist left;
+            llist right;
+            llist_init (&left);
+            llist_init (&right);
+            unsigned n = 0;
+            if (!llist_is_single (self))
+              {
+                LLIST_WHILE_HEAD (self, head)
+                  llist_insert_prev (++n & 1 ? &left : &right, head);
+
+                llist_sort (&left, cmp);
+                llist_sort (&right, cmp);
 
+                while (!llist_is_empty (&left) && !llist_is_empty (&right))
+                  llist_insert_prev (self, cmp (left.next, right.next) > 0 ? left.next : right.next);
+
+                if (!llist_is_empty (&left))
+                  llist_insertlist_prev (self, &left);
+                if (!llist_is_empty (&right))
+                  llist_insertlist_prev (self, &right);
+              }
+            return self;
+)
+
+#endif /* LLIST_H */
 /*
 //      Local Variables:
 //      mode: C