1.1 --- a/ucx/list.c Fri Jun 01 12:35:30 2012 +0200
1.2 +++ b/ucx/list.c Wed Aug 15 19:32:29 2012 +0200
1.3 @@ -108,6 +108,64 @@
1.4 return s;
1.5 }
1.6
1.7 +int ucx_list_qsort_devide(UcxList** 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 + UcxList *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_list_qsort_sort(UcxList** list, int l, int r, cmp_func f, void* d) {
1.33 + if (l < r) {
1.34 + int m = ucx_list_qsort_devide(list, l, r, f, d);
1.35 + ucx_list_qsort_sort(list, l, m-1, f, d);
1.36 + ucx_list_qsort_sort(list, m+1, r, f, d);
1.37 + }
1.38 +}
1.39 +
1.40 +UcxList *ucx_list_qsort(UcxList *l, cmp_func fnc, void *data) {
1.41 + if (l == NULL) {
1.42 + return NULL;
1.43 + }
1.44 + size_t n = ucx_list_size(l);
1.45 + if (n == 1) {
1.46 + return l;
1.47 + }
1.48 +
1.49 + UcxList *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_list_qsort_sort(entries, 0, n-1, fnc, data);
1.56 +
1.57 + for (int i = 0 ; i < n-1 ; i++) {
1.58 + entries[i]->next = entries[i+1];
1.59 + }
1.60 + entries[n-1]->next = NULL;
1.61 +
1.62 + return entries[0];
1.63 +}
1.64 +
1.65 /* list specific functions */
1.66 UcxList *ucx_list_remove(UcxList *l, UcxList *e) {
1.67 if (e == l) {
