comparison: ucx/list.c
ucx/list.c
- changeset 172
- 7084e8e8433c
- parent 161
- 1031dd910f8e
- child 173
- 31a8682fffb7
equal
deleted
inserted
replaced
| 171:49cebb8eceff | 172:7084e8e8433c |
|---|---|
| 119 | 119 |
| 120 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { | 120 UcxList *ucx_list_concat(UcxList *l1, UcxList *l2) { |
| 121 if (l1) { | 121 if (l1) { |
| 122 UcxList *last = ucx_list_last(l1); | 122 UcxList *last = ucx_list_last(l1); |
| 123 last->next = l2; | 123 last->next = l2; |
| 124 l2->prev = last; | 124 if (l2) { |
| 125 l2->prev = last; | |
| 126 } | |
| 125 return l1; | 127 return l1; |
| 126 } else { | 128 } else { |
| 127 return l2; | 129 return l2; |
| 128 } | 130 } |
| 129 } | 131 } |
| 148 index++; | 150 index++; |
| 149 } | 151 } |
| 150 return -1; | 152 return -1; |
| 151 } | 153 } |
| 152 | 154 |
| 153 UcxList *ucx_list_get(const UcxList *l, int index) { | 155 UcxList *ucx_list_get(const UcxList *l, size_t index) { |
| 154 if (l == NULL) return NULL; | 156 if (l == NULL) return NULL; |
| 155 | 157 |
| 156 const UcxList *e = l; | 158 const UcxList *e = l; |
| 157 while (e->next && index > 0) { | 159 while (e->next && index > 0) { |
| 158 e = e->next; | 160 e = e->next; |
| 194 } | 196 } |
| 195 | 197 |
| 196 return s; | 198 return s; |
| 197 } | 199 } |
| 198 | 200 |
| 199 UcxList *ucx_list_sort_merge(int length, | 201 static UcxList *ucx_list_sort_merge(int length, |
| 200 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re, | 202 UcxList* restrict ls, UcxList* restrict le, UcxList* restrict re, |
| 201 cmp_func fnc, void* data) { | 203 cmp_func fnc, void* data) { |
| 202 | 204 |
| 203 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); | 205 UcxList** sorted = (UcxList**) malloc(sizeof(UcxList*)*length); |
| 204 UcxList *rc, *lc; | 206 UcxList *rc, *lc; |
| 246 | 248 |
| 247 UcxList *lc; | 249 UcxList *lc; |
| 248 int ln = 1; | 250 int ln = 1; |
| 249 | 251 |
| 250 UcxList *restrict ls = l, *restrict le, *restrict re; | 252 UcxList *restrict ls = l, *restrict le, *restrict re; |
| 253 | |
| 254 // check how many elements are already sorted | |
| 251 lc = ls; | 255 lc = ls; |
| 252 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { | 256 while (lc->next != NULL && fnc(lc->next->data, lc->data, data) > 0) { |
| 253 lc = lc->next; | 257 lc = lc->next; |
| 254 ln++; | 258 ln++; |
| 255 } | 259 } |
| 259 return l; // this list is already sorted :) | 263 return l; // this list is already sorted :) |
| 260 } else { | 264 } else { |
| 261 UcxList *rc; | 265 UcxList *rc; |
| 262 int rn = 1; | 266 int rn = 1; |
| 263 rc = le; | 267 rc = le; |
| 268 // skip already sorted elements | |
| 264 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { | 269 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) { |
| 265 rc = rc->next; | 270 rc = rc->next; |
| 266 rn++; | 271 rn++; |
| 267 } | 272 } |
| 268 re = rc->next; | 273 re = rc->next; |
| 269 | |
| 270 // Something left? Sort it! | |
| 271 UcxList *remainder = re; | |
| 272 size_t remainder_length = ucx_list_size(remainder); | |
| 273 if (remainder != NULL) { | |
| 274 remainder = ucx_list_sort(remainder, fnc, data); | |
| 275 } | |
| 276 | 274 |
| 277 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them | 275 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them |
| 278 UcxList *sorted = ucx_list_sort_merge(ln+rn, | 276 UcxList *sorted = ucx_list_sort_merge(ln+rn, |
| 279 ls, le, re, | 277 ls, le, re, |
| 280 fnc, data); | 278 fnc, data); |
| 281 | 279 |
| 282 // merge sorted list with (also sorted) remainder | 280 // Something left? Sort it! |
| 283 l = ucx_list_sort_merge(ln+rn+remainder_length, | 281 size_t remainder_length = ucx_list_size(re); |
| 284 sorted, remainder, NULL, fnc, data); | 282 if (remainder_length > 0) { |
| 283 UcxList *remainder = ucx_list_sort(re, fnc, data); | |
| 284 | |
| 285 // merge sorted list with (also sorted) remainder | |
| 286 l = ucx_list_sort_merge(ln+rn+remainder_length, | |
| 287 sorted, remainder, NULL, fnc, data); | |
| 288 } else { | |
| 289 // no remainder - we've got our sorted list | |
| 290 l = sorted; | |
| 291 } | |
| 285 | 292 |
| 286 return l; | 293 return l; |
| 287 } | 294 } |
| 288 } | 295 } |
| 289 | 296 |
