Mercurial > hg > toolkit / file diff

--- a/ucx/list.c	Tue Feb 16 17:39:33 2016 +0100
+++ b/ucx/list.c	Mon May 23 12:28:32 2016 +0200
@@ -1,7 +1,7 @@
 /*
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
  *
- * Copyright 2013 Olaf Wintermann. All rights reserved.
+ * Copyright 2015 Olaf Wintermann. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are met:
@@ -72,7 +72,7 @@
     while (e != NULL) {
         f = e;
         e = e->next;
-        alloc->free(alloc->pool, f);
+        alfree(alloc, f);
     }
 }
 
@@ -81,7 +81,7 @@
 }
 
 UcxList *ucx_list_append_a(UcxAllocator *alloc, UcxList *l, void *data)  {
-    UcxList *nl = (UcxList*) alloc->malloc(alloc->pool, sizeof(UcxList));
+    UcxList *nl = (UcxList*) almalloc(alloc, sizeof(UcxList));
     if (!nl) {
         return NULL;
     }
@@ -121,7 +121,9 @@
     if (l1) {
         UcxList *last = ucx_list_last(l1);
         last->next = l2;
-        l2->prev = last;
+        if (l2) {
+            l2->prev = last;
+        }
         return l1;
     } else {
         return l2;
@@ -150,7 +152,7 @@
     return -1;
 }
 
-UcxList *ucx_list_get(const UcxList *l, int index) {
+UcxList *ucx_list_get(const UcxList *l, size_t index) {
     if (l == NULL) return NULL;
 
     const UcxList *e = l;
@@ -196,7 +198,7 @@
     return s;
 }
 
-UcxList *ucx_list_sort_merge(int length,
+static UcxList *ucx_list_sort_merge(int length,
         UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re,
         cmp_func fnc, void* data) {
 
@@ -248,6 +250,8 @@
     int ln = 1;
 
     UcxList *restrict ls = l, *restrict le, *restrict re;
+    
+    // check how many elements are already sorted
     lc = ls;
     while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
         lc = lc->next;
@@ -261,27 +265,30 @@
         UcxList *rc;
         int rn = 1;
         rc = le;
+        // skip already sorted elements
         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, le, re,
                 fnc, data);
+        
+        // Something left? Sort it!
+        size_t remainder_length = ucx_list_size(re);
+        if (remainder_length > 0) {
+            UcxList *remainder = ucx_list_sort(re, fnc, data);
 
-        // merge sorted list with (also sorted) remainder
-        l = ucx_list_sort_merge(ln+rn+remainder_length,
-                sorted, remainder, NULL, fnc, data);
+            // merge sorted list with (also sorted) remainder
+            l = ucx_list_sort_merge(ln+rn+remainder_length,
+                    sorted, remainder, NULL, fnc, data);
+        } else {
+            // no remainder - we've got our sorted list
+            l = sorted;
+        }
 
         return l;
     }
@@ -316,6 +323,6 @@
         e->prev->next = e->next;
     }
     
-    alloc->free(alloc->pool, e);
+    alfree(alloc, e);
     return l;
 }