Mercurial > hg > ucx / changeset

     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 */

     2.1 --- a/ucx/list.c	Thu Aug 16 11:31:16 2012 +0200
     2.2 +++ b/ucx/list.c	Thu Aug 16 12:36:23 2012 +0200
     2.3 @@ -108,62 +108,92 @@
     2.4      return s;
     2.5  }
     2.6  
     2.7 -int ucx_list_qsort_devide(UcxList** list, int l, int r, cmp_func f, void* d) {
     2.8 -    int i = l;
     2.9 -    int j = r - 1;
    2.10 -    void *p = list[r]->data;
    2.11 -    UcxList *b;
    2.12 +UcxList *ucx_list_sort_merge(int length,
    2.13 +        UcxList* ls, UcxList* rs, UcxList* le, UcxList* re,
    2.14 +        cmp_func fnc, void* data) {
    2.15 +    UcxList *sorted[length];
    2.16 +    UcxList *rc, *lc;
    2.17  
    2.18 -    do {
    2.19 -        while (i < r && f(list[i]->data, p, d) <= 0) i++;
    2.20 -        while (j > l && f(list[j]->data, p, d) >= 0) j--;
    2.21 -        if (i < j) {
    2.22 -            b = list[i];
    2.23 -            list[i] = list[j];
    2.24 -            list[j] = b;
    2.25 +    lc = ls; rc = rs;
    2.26 +    int n = 0;
    2.27 +    while (lc != le && rc != re) {
    2.28 +        if (fnc(lc->data, rc->data, data) <= 0) {
    2.29 +            sorted[n] = lc;
    2.30 +            lc = lc->next;
    2.31 +        } else {
    2.32 +            sorted[n] = rc;
    2.33 +            rc = rc->next;
    2.34          }
    2.35 -    } while (i < j);
    2.36 -
    2.37 -    if (f(list[i]->data, p, d) > 0) {
    2.38 -        b = list[r];
    2.39 -        list[r] = list[i];
    2.40 -        list[i] = b;
    2.41 +        n++;
    2.42 +    }
    2.43 +    while (lc != le) {
    2.44 +        sorted[n] = lc;
    2.45 +        lc = lc->next;
    2.46 +        n++;
    2.47 +    }
    2.48 +    while (rc != re) {
    2.49 +        sorted[n] = rc;
    2.50 +        rc = rc->next;
    2.51 +        n++;
    2.52      }
    2.53  
    2.54 -    return i;
    2.55 -}
    2.56 +    // Update pointer
    2.57 +    for (int i = 0 ; i < length-1 ; i++) {
    2.58 +        sorted[i]->next = sorted[i+1];
    2.59 +    }
    2.60 +    sorted[length-1]->next = NULL;
    2.61  
    2.62 -void ucx_list_qsort_sort(UcxList** list, int l, int r, cmp_func f, void* d) {
    2.63 -    if (l < r) {
    2.64 -        int m = ucx_list_qsort_devide(list, l, r, f, d);
    2.65 -        ucx_list_qsort_sort(list, l, m-1, f, d);
    2.66 -        ucx_list_qsort_sort(list, m+1, r, f, d);
    2.67 -    }
    2.68 +    return sorted[0];
    2.69  }
    2.70  
    2.71  UcxList *ucx_list_sort(UcxList *l, cmp_func fnc, void *data) {
    2.72      if (l == NULL) {
    2.73          return NULL;
    2.74      }
    2.75 -    size_t n = ucx_list_size(l);
    2.76 -    if (n == 1) {
    2.77 +
    2.78 +    UcxList *lc;
    2.79 +    int ln = 1;
    2.80 +
    2.81 +    UcxList *ls = l, *le;
    2.82 +    lc = ls;
    2.83 +    while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) {
    2.84 +        lc = lc->next;
    2.85 +        ln++;
    2.86 +    }
    2.87 +    le = lc->next;
    2.88 +
    2.89 +    UcxList *rs = le, *re;
    2.90 +    if (rs == NULL) {
    2.91 +        return l; // this list is already sorted :)
    2.92 +    } else {
    2.93 +        UcxList *rc;
    2.94 +        int rn = 1;
    2.95 +        rc = rs;
    2.96 +        while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
    2.97 +            rc = rc->next;
    2.98 +            rn++;
    2.99 +        }
   2.100 +        re = rc->next;
   2.101 +
   2.102 +        // Something left? Sort it!
   2.103 +        UcxList *remainder = re;
   2.104 +        size_t remainder_length = ucx_list_size(remainder);
   2.105 +        if (remainder != NULL) {
   2.106 +            remainder = ucx_list_sort(remainder, fnc, data);
   2.107 +        }
   2.108 +
   2.109 +        // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
   2.110 +        UcxList *sorted = ucx_list_sort_merge(ln+rn,
   2.111 +                ls, rs, le, re,
   2.112 +                fnc, data);
   2.113 +
   2.114 +        // merge sorted list with (also sorted) remainder
   2.115 +        l = ucx_list_sort_merge(ln+rn+remainder_length,
   2.116 +                sorted, remainder, NULL, NULL,
   2.117 +                fnc, data);
   2.118 +
   2.119          return l;
   2.120      }
   2.121 -
   2.122 -    UcxList *entries[n];
   2.123 -    entries[0] = l;
   2.124 -    for (int i = 1 ; i < n ; i++) {
   2.125 -      entries[i] = entries[i-1]->next;
   2.126 -    }
   2.127 -
   2.128 -    ucx_list_qsort_sort(entries, 0, n-1, fnc, data);
   2.129 -
   2.130 -    for (int i = 0 ; i < n-1 ; i++) {
   2.131 -      entries[i]->next = entries[i+1];
   2.132 -    }
   2.133 -    entries[n-1]->next = NULL;
   2.134 -
   2.135 -    return entries[0];
   2.136  }
   2.137  
   2.138  /* list specific functions */