comparison: src/linked_list.c
src/linked_list.c
- changeset 703
- 425d4279856f
- parent 702
- 3390b58ad15a
- child 708
- 1caed6c9ba68
equal
deleted
inserted
replaced
| 702:3390b58ad15a | 703:425d4279856f |
|---|---|
| 281 | 281 |
| 282 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE | 282 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE |
| 283 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024 | 283 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024 |
| 284 #endif | 284 #endif |
| 285 | 285 |
| 286 static void *cx_linked_list_sort_merge( | 286 static void cx_linked_list_sort_merge( |
| 287 ptrdiff_t loc_prev, | 287 ptrdiff_t loc_prev, |
| 288 ptrdiff_t loc_next, | 288 ptrdiff_t loc_next, |
| 289 ptrdiff_t loc_data, | 289 ptrdiff_t loc_data, |
| 290 size_t length, | 290 size_t length, |
| 291 void *ls, | 291 void *ls, |
| 292 void *le, | 292 void *le, |
| 293 void *re, | 293 void *re, |
| 294 cx_compare_func cmp_func | 294 cx_compare_func cmp_func, |
| 295 void **begin, | |
| 296 void **end | |
| 295 ) { | 297 ) { |
| 296 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; | 298 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; |
| 297 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? | 299 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? |
| 298 malloc(sizeof(void *) * length) : sbo; | 300 malloc(sizeof(void *) * length) : sbo; |
| 299 if (sorted == NULL) abort(); | 301 if (sorted == NULL) abort(); |
| 328 cx_for_n (i, length - 1) { | 330 cx_for_n (i, length - 1) { |
| 329 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next); | 331 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next); |
| 330 } | 332 } |
| 331 ll_next(sorted[length - 1]) = NULL; | 333 ll_next(sorted[length - 1]) = NULL; |
| 332 | 334 |
| 333 void *ret = sorted[0]; | 335 *begin = sorted[0]; |
| 336 *end = sorted[length-1]; | |
| 334 if (sorted != sbo) { | 337 if (sorted != sbo) { |
| 335 free(sorted); | 338 free(sorted); |
| 336 } | 339 } |
| 337 return ret; | |
| 338 } | 340 } |
| 339 | 341 |
| 340 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function | 342 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function |
| 341 void **begin, | 343 void **begin, |
| 342 void **end, | 344 void **end, |
| 378 rn++; | 380 rn++; |
| 379 } | 381 } |
| 380 re = ll_next(rc); | 382 re = ll_next(rc); |
| 381 | 383 |
| 382 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them | 384 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them |
| 383 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, | 385 void *sorted_begin, *sorted_end; |
| 384 ln + rn, ls, le, re, cmp_func); | 386 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, |
| 387 ln + rn, ls, le, re, cmp_func, | |
| 388 &sorted_begin, &sorted_end); | |
| 385 | 389 |
| 386 // Something left? Sort it! | 390 // Something left? Sort it! |
| 387 size_t remainder_length = cx_linked_list_size(re, loc_next); | 391 size_t remainder_length = cx_linked_list_size(re, loc_next); |
| 388 if (remainder_length > 0) { | 392 if (remainder_length > 0) { |
| 389 void *remainder = re; | 393 void *remainder = re; |
| 390 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); | 394 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); |
| 391 | 395 |
| 392 // merge sorted list with (also sorted) remainder | 396 // merge sorted list with (also sorted) remainder |
| 393 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, | 397 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, |
| 394 ln + rn + remainder_length, | 398 ln + rn + remainder_length, |
| 395 sorted, remainder, NULL, cmp_func); | 399 sorted_begin, remainder, NULL, cmp_func, |
| 396 } else { | 400 &sorted_begin, &sorted_end); |
| 397 // no remainder - we've got our sorted list | 401 } |
| 398 *begin = sorted; | 402 *begin = sorted_begin; |
| 399 } | 403 if (end) *end = sorted_end; |
| 400 if (end) *end = cx_linked_list_last(sorted, loc_next); | |
| 401 } | 404 } |
| 402 } | 405 } |
| 403 | 406 |
| 404 int cx_linked_list_compare( | 407 int cx_linked_list_compare( |
| 405 void const *begin_left, | 408 void const *begin_left, |
