1.1 --- a/ucx/dlist.c Thu Aug 16 11:31:16 2012 +0200
1.2 +++ b/ucx/dlist.c Thu Aug 16 12:36:23 2012 +0200
1.3 @@ -112,64 +112,94 @@
1.4 return s;
1.5 }
1.6
1.7 -int ucx_dlist_qsort_devide(UcxDlist** list, int l, int r, cmp_func f, void* d) {
1.8 - int i = l;
1.9 - int j = r - 1;
1.10 - void *p = list[r]->data;
1.11 - UcxDlist *b;
1.12 +UcxDlist *ucx_dlist_sort_merge(int length,
1.13 + UcxDlist* ls, UcxDlist* rs, UcxDlist* le, UcxDlist* re,
1.14 + cmp_func fnc, void* data) {
1.15 + UcxDlist *sorted[length];
1.16 + UcxDlist *rc, *lc;
1.17
1.18 - do {
1.19 - while (i < r && f(list[i]->data, p, d) <= 0) i++;
1.20 - while (j > l && f(list[j]->data, p, d) >= 0) j--;
1.21 - if (i < j) {
1.22 - b = list[i];
1.23 - list[i] = list[j];
1.24 - list[j] = b;
1.25 + lc = ls; rc = rs;
1.26 + int n = 0;
1.27 + while (lc != le && rc != re) {
1.28 + if (fnc(lc->data, rc->data, data) <= 0) {
1.29 + sorted[n] = lc;
1.30 + lc = lc->next;
1.31 + } else {
1.32 + sorted[n] = rc;
1.33 + rc = rc->next;
1.34 }
1.35 - } while (i < j);
1.36 -
1.37 - if (f(list[i]->data, p, d) > 0) {
1.38 - b = list[r];
1.39 - list[r] = list[i];
1.40 - list[i] = b;
1.41 + n++;
1.42 + }
1.43 + while (lc != le) {
1.44 + sorted[n] = lc;
1.45 + lc = lc->next;
1.46 + n++;
1.47 + }
1.48 + while (rc != re) {
1.49 + sorted[n] = rc;
1.50 + rc = rc->next;
1.51 + n++;
1.52 }
1.53
1.54 - return i;
1.55 -}
1.56 + // Update pointer
1.57 + sorted[0]->prev = NULL;
1.58 + for (int i = 0 ; i < length-1 ; i++) {
1.59 + sorted[i]->next = sorted[i+1];
1.60 + sorted[i+1]->prev = sorted[i];
1.61 + }
1.62 + sorted[length-1]->next = NULL;
1.63
1.64 -void ucx_dlist_qsort_sort(UcxDlist** list, int l, int r, cmp_func f, void* d) {
1.65 - if (l < r) {
1.66 - int m = ucx_dlist_qsort_devide(list, l, r, f, d);
1.67 - ucx_dlist_qsort_sort(list, l, m-1, f, d);
1.68 - ucx_dlist_qsort_sort(list, m+1, r, f, d);
1.69 - }
1.70 + return sorted[0];
1.71 }
1.72
1.73 UcxDlist *ucx_dlist_sort(UcxDlist *l, cmp_func fnc, void *data) {
1.74 if (l == NULL) {
1.75 return NULL;
1.76 }
1.77 - size_t n = ucx_dlist_size(l);
1.78 - if (n == 1) {
1.79 +
1.80 + UcxDlist *lc;
1.81 + int ln = 1;
1.82 +
1.83 + UcxDlist *ls = l, *le;
1.84 + lc = ls;
1.85 + while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
1.86 + lc = lc->next;
1.87 + ln++;
1.88 + }
1.89 + le = lc->next;
1.90 +
1.91 + UcxDlist *rs = le, *re;
1.92 + if (rs == NULL) {
1.93 + return l; // this list is already sorted :)
1.94 + } else {
1.95 + UcxDlist *rc;
1.96 + int rn = 1;
1.97 + rc = rs;
1.98 + while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
1.99 + rc = rc->next;
1.100 + rn++;
1.101 + }
1.102 + re = rc->next;
1.103 +
1.104 + // Something left? Sort it!
1.105 + UcxDlist *remainder = re;
1.106 + size_t remainder_length = ucx_dlist_size(remainder);
1.107 + if (remainder != NULL) {
1.108 + remainder = ucx_dlist_sort(remainder, fnc, data);
1.109 + }
1.110 +
1.111 + // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
1.112 + UcxDlist *sorted = ucx_dlist_sort_merge(ln+rn,
1.113 + ls, rs, le, re,
1.114 + fnc, data);
1.115 +
1.116 + // merge sorted list with (also sorted) remainder
1.117 + l = ucx_dlist_sort_merge(ln+rn+remainder_length,
1.118 + sorted, remainder, NULL, NULL,
1.119 + fnc, data);
1.120 +
1.121 return l;
1.122 }
1.123 -
1.124 - UcxDlist *entries[n];
1.125 - entries[0] = l;
1.126 - for (int i = 1 ; i < n ; i++) {
1.127 - entries[i] = entries[i-1]->next;
1.128 - }
1.129 -
1.130 - ucx_dlist_qsort_sort(entries, 0, n-1, fnc, data);
1.131 -
1.132 - entries[0]->prev = NULL;
1.133 - for (int i = 0 ; i < n-1 ; i++) {
1.134 - entries[i]->next = entries[i+1];
1.135 - entries[i+1]->prev = entries[i];
1.136 - }
1.137 - entries[n-1]->next = NULL;
1.138 -
1.139 - return entries[0];
1.140 }
1.141
1.142 /* dlist specific functions */
