Mercurial > hg > webserver / file diff

--- a/src/server/ucx/list.c	Sat Aug 18 11:39:34 2012 +0200
+++ b/src/server/ucx/list.c	Sat Oct 06 13:00:07 2012 +0200
@@ -25,7 +25,7 @@
         l1 = l1->next;
         l2 = l2->next;
     }
-
+    
     return (l1 == NULL && l2 == NULL);
 }
 
@@ -41,7 +41,7 @@
 UcxList *ucx_list_append(UcxList *l, void *data)  {
     UcxList *nl = (UcxList*) malloc(sizeof(UcxList));
     if (nl == NULL) return NULL;
-
+    
     nl->data = data;
     nl->next = NULL;
     if (l == NULL) {
@@ -56,7 +56,7 @@
 UcxList *ucx_list_prepend(UcxList *l, void *data) {
     UcxList *nl = ucx_list_append(NULL, data);
     if (nl == NULL) return NULL;
-
+    
     if (l != NULL) {
         nl->next = l;
     }
@@ -75,7 +75,7 @@
 
 UcxList *ucx_list_last(UcxList *l) {
     if (l == NULL) return NULL;
-
+    
     UcxList *e = l;
     while (e->next != NULL) {
         e = e->next;
@@ -91,13 +91,13 @@
         e = e->next;
         index--;
     }
-
+    
     return index == 0 ? e : NULL;
 }
 
 size_t ucx_list_size(UcxList *l) {
     if (l == NULL) return 0;
-
+    
     UcxList *e = l;
     size_t s = 1;
     while (e->next != NULL) {
@@ -108,13 +108,91 @@
     return s;
 }
 
-void ucx_list_foreach(UcxList *l, ucx_callback fnc, void* data) {
-    UcxList *e = l;
-    UcxList *n;
-    while (e != NULL) {
-        n = e->next;
-        fnc(e, data);
-        e = n;
+UcxList *ucx_list_sort_merge(int length,
+        UcxList* ls, UcxList* rs, UcxList* le, UcxList* re,
+        cmp_func fnc, void* data) {
+    UcxList *sorted[length];
+    UcxList *rc, *lc;
+
+    lc = ls; rc = rs;
+    int n = 0;
+    while (lc != le && rc != re) {
+        if (fnc(lc->data, rc->data, data) <= 0) {
+            sorted[n] = lc;
+            lc = lc->next;
+        } else {
+            sorted[n] = rc;
+            rc = rc->next;
+        }
+        n++;
+    }
+    while (lc != le) {
+        sorted[n] = lc;
+        lc = lc->next;
+        n++;
+    }
+    while (rc != re) {
+        sorted[n] = rc;
+        rc = rc->next;
+        n++;
+    }
+
+    // Update pointer
+    for (int i = 0 ; i < length-1 ; i++) {
+        sorted[i]->next = sorted[i+1];
+    }
+    sorted[length-1]->next = NULL;
+
+    return sorted[0];
+}
+
+UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
+    if (l == NULL) {
+        return NULL;
+    }
+
+    UcxList *lc;
+    int ln = 1;
+
+    UcxList *ls = l, *le;
+    lc = ls;
+    while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
+        lc = lc->next;
+        ln++;
+    }
+    le = lc->next;
+
+    UcxList *rs = le, *re;
+    if (rs == NULL) {
+        return l; // this list is already sorted :)
+    } else {
+        UcxList *rc;
+        int rn = 1;
+        rc = rs;
+        while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
+            rc = rc->next;
+            rn++;
+        }
+        re = rc->next;
+
+        // Something left? Sort it!
+        UcxList *remainder = re;
+        size_t remainder_length = ucx_list_size(remainder);
+        if (remainder != NULL) {
+            remainder = ucx_list_sort(remainder, fnc, data);
+        }
+
+        // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
+        UcxList *sorted = ucx_list_sort_merge(ln+rn,
+                ls, rs, le, re,
+                fnc, data);
+
+        // merge sorted list with (also sorted) remainder
+        l = ucx_list_sort_merge(ln+rn+remainder_length,
+                sorted, remainder, NULL, NULL,
+                fnc, data);
+
+        return l;
     }
 }
 
@@ -128,7 +206,7 @@
         while (f->next != NULL && f->next != e) {
             f = f->next;
         }
-        /* perform remove iff this element is found in this list */
+        /* perform remove if this element is found in this list */
         if (f->next == e) {
             f->next = e->next;
             free(e);