1.1 --- a/ucx/dlist.c Fri Jun 01 12:35:30 2012 +0200 1.2 +++ b/ucx/dlist.c Wed Aug 15 19:32:29 2012 +0200 1.3 @@ -112,6 +112,66 @@ 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 + 1.13 + do { 1.14 + while (i < r && f(list[i]->data, p, d) <= 0) i++; 1.15 + while (j > l && f(list[j]->data, p, d) >= 0) j--; 1.16 + if (i < j) { 1.17 + b = list[i]; 1.18 + list[i] = list[j]; 1.19 + list[j] = b; 1.20 + } 1.21 + } while (i < j); 1.22 + 1.23 + if (f(list[i]->data, p, d) > 0) { 1.24 + b = list[r]; 1.25 + list[r] = list[i]; 1.26 + list[i] = b; 1.27 + } 1.28 + 1.29 + return i; 1.30 +} 1.31 + 1.32 +void ucx_dlist_qsort_sort(UcxDlist** list, int l, int r, cmp_func f, void* d) { 1.33 + if (l < r) { 1.34 + int m = ucx_dlist_qsort_devide(list, l, r, f, d); 1.35 + ucx_dlist_qsort_sort(list, l, m-1, f, d); 1.36 + ucx_dlist_qsort_sort(list, m+1, r, f, d); 1.37 + } 1.38 +} 1.39 + 1.40 +UcxDlist *ucx_dlist_qsort(UcxDlist *l, cmp_func fnc, void *data) { 1.41 + if (l == NULL) { 1.42 + return NULL; 1.43 + } 1.44 + size_t n = ucx_dlist_size(l); 1.45 + if (n == 1) { 1.46 + return l; 1.47 + } 1.48 + 1.49 + UcxDlist *entries[n]; 1.50 + entries[0] = l; 1.51 + for (int i = 1 ; i < n ; i++) { 1.52 + entries[i] = entries[i-1]->next; 1.53 + } 1.54 + 1.55 + ucx_dlist_qsort_sort(entries, 0, n-1, fnc, data); 1.56 + 1.57 + entries[0]->prev = NULL; 1.58 + for (int i = 0 ; i < n-1 ; i++) { 1.59 + entries[i]->next = entries[i+1]; 1.60 + entries[i+1]->prev = entries[i]; 1.61 + } 1.62 + entries[n-1]->next = NULL; 1.63 + 1.64 + return entries[0]; 1.65 +} 1.66 + 1.67 /* dlist specific functions */ 1.68 UcxDlist *ucx_dlist_first(UcxDlist *l) { 1.69 if (l == NULL) return NULL;