comparison: ucx/dlist.c
ucx/dlist.c
- changeset 37
- ec296899d12f
- parent 36
- a9d656e4f7ce
- child 67
- 27e67e725d35
equal
deleted
inserted
replaced
| 36:a9d656e4f7ce | 37:ec296899d12f |
|---|---|
| 110 } | 110 } |
| 111 | 111 |
| 112 return s; | 112 return s; |
| 113 } | 113 } |
| 114 | 114 |
| 115 int ucx_dlist_qsort_devide(UcxDlist** list, int l, int r, cmp_func f, void* d) { | 115 UcxDlist *ucx_dlist_sort_merge(int length, |
| 116 int i = l; | 116 UcxDlist* ls, UcxDlist* rs, UcxDlist* le, UcxDlist* re, |
| 117 int j = r - 1; | 117 cmp_func fnc, void* data) { |
| 118 void *p = list[r]->data; | 118 UcxDlist *sorted[length]; |
| 119 UcxDlist *b; | 119 UcxDlist *rc, *lc; |
| 120 | 120 |
| 121 do { | 121 lc = ls; rc = rs; |
| 122 while (i < r && f(list[i]->data, p, d) <= 0) i++; | 122 int n = 0; |
| 123 while (j > l && f(list[j]->data, p, d) >= 0) j--; | 123 while (lc != le && rc != re) { |
| 124 if (i < j) { | 124 if (fnc(lc->data, rc->data, data) <= 0) { |
| 125 b = list[i]; | 125 sorted[n] = lc; |
| 126 list[i] = list[j]; | 126 lc = lc->next; |
| 127 list[j] = b; | 127 } else { |
| 128 } | 128 sorted[n] = rc; |
| 129 } while (i < j); | 129 rc = rc->next; |
| 130 | 130 } |
| 131 if (f(list[i]->data, p, d) > 0) { | 131 n++; |
| 132 b = list[r]; | 132 } |
| 133 list[r] = list[i]; | 133 while (lc != le) { |
| 134 list[i] = b; | 134 sorted[n] = lc; |
| 135 } | 135 lc = lc->next; |
| 136 | 136 n++; |
| 137 return i; | 137 } |
| 138 } | 138 while (rc != re) { |
| 139 | 139 sorted[n] = rc; |
| 140 void ucx_dlist_qsort_sort(UcxDlist** list, int l, int r, cmp_func f, void* d) { | 140 rc = rc->next; |
| 141 if (l < r) { | 141 n++; |
| 142 int m = ucx_dlist_qsort_devide(list, l, r, f, d); | 142 } |
| 143 ucx_dlist_qsort_sort(list, l, m-1, f, d); | 143 |
| 144 ucx_dlist_qsort_sort(list, m+1, r, f, d); | 144 // Update pointer |
| 145 } | 145 sorted[0]->prev = NULL; |
| 146 for (int i = 0 ; i < length-1 ; i++) { | |
| 147 sorted[i]->next = sorted[i+1]; | |
| 148 sorted[i+1]->prev = sorted[i]; | |
| 149 } | |
| 150 sorted[length-1]->next = NULL; | |
| 151 | |
| 152 return sorted[0]; | |
| 146 } | 153 } |
| 147 | 154 |
| 148 UcxDlist *ucx_dlist_sort(UcxDlist *l, cmp_func fnc, void *data) { | 155 UcxDlist *ucx_dlist_sort(UcxDlist *l, cmp_func fnc, void *data) { |
| 149 if (l == NULL) { | 156 if (l == NULL) { |
| 150 return NULL; | 157 return NULL; |
| 151 } | 158 } |
| 152 size_t n = ucx_dlist_size(l); | 159 |
| 153 if (n == 1) { | 160 UcxDlist *lc; |
| 161 int ln = 1; | |
| 162 | |
| 163 UcxDlist *ls = l, *le; | |
| 164 lc = ls; | |
| 165 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { | |
| 166 lc = lc->next; | |
| 167 ln++; | |
| 168 } | |
| 169 le = lc->next; | |
| 170 | |
| 171 UcxDlist *rs = le, *re; | |
| 172 if (rs == NULL) { | |
| 173 return l; // this list is already sorted :) | |
| 174 } else { | |
| 175 UcxDlist *rc; | |
| 176 int rn = 1; | |
| 177 rc = rs; | |
| 178 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { | |
| 179 rc = rc->next; | |
| 180 rn++; | |
| 181 } | |
| 182 re = rc->next; | |
| 183 | |
| 184 // Something left? Sort it! | |
| 185 UcxDlist *remainder = re; | |
| 186 size_t remainder_length = ucx_dlist_size(remainder); | |
| 187 if (remainder != NULL) { | |
| 188 remainder = ucx_dlist_sort(remainder, fnc, data); | |
| 189 } | |
| 190 | |
| 191 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them | |
| 192 UcxDlist *sorted = ucx_dlist_sort_merge(ln+rn, | |
| 193 ls, rs, le, re, | |
| 194 fnc, data); | |
| 195 | |
| 196 // merge sorted list with (also sorted) remainder | |
| 197 l = ucx_dlist_sort_merge(ln+rn+remainder_length, | |
| 198 sorted, remainder, NULL, NULL, | |
| 199 fnc, data); | |
| 200 | |
| 154 return l; | 201 return l; |
| 155 } | 202 } |
| 156 | |
| 157 UcxDlist *entries[n]; | |
| 158 entries[0] = l; | |
| 159 for (int i = 1 ; i < n ; i++) { | |
| 160 entries[i] = entries[i-1]->next; | |
| 161 } | |
| 162 | |
| 163 ucx_dlist_qsort_sort(entries, 0, n-1, fnc, data); | |
| 164 | |
| 165 entries[0]->prev = NULL; | |
| 166 for (int i = 0 ; i < n-1 ; i++) { | |
| 167 entries[i]->next = entries[i+1]; | |
| 168 entries[i+1]->prev = entries[i]; | |
| 169 } | |
| 170 entries[n-1]->next = NULL; | |
| 171 | |
| 172 return entries[0]; | |
| 173 } | 203 } |
| 174 | 204 |
| 175 /* dlist specific functions */ | 205 /* dlist specific functions */ |
| 176 UcxDlist *ucx_dlist_first(UcxDlist *l) { | 206 UcxDlist *ucx_dlist_first(UcxDlist *l) { |
| 177 if (l == NULL) return NULL; | 207 if (l == NULL) return NULL; |
