comparison: src/ucx/linked_list.c
src/ucx/linked_list.c
- changeset 504
- c094afcdfb27
- parent 491
- 5454ae7bf86b
equal
deleted
inserted
replaced
| 503:aeaf7db26fac | 504:c094afcdfb27 |
|---|---|
| 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, |
| 602 ll->begin = ll->end = NULL; | 605 ll->begin = ll->end = NULL; |
| 603 list->size = 0; | 606 list->size = 0; |
| 604 } | 607 } |
| 605 | 608 |
| 606 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE | 609 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE |
| 607 #define CX_LINKED_LIST_SWAP_SBO_SIZE 16 | 610 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128 |
| 608 #endif | 611 #endif |
| 609 | 612 |
| 610 static int cx_ll_swap( | 613 static int cx_ll_swap( |
| 611 struct cx_list_s *list, | 614 struct cx_list_s *list, |
| 612 size_t i, | 615 size_t i, |
| 871 static void cx_ll_destructor(CxList *list) { | 874 static void cx_ll_destructor(CxList *list) { |
| 872 cx_linked_list *ll = (cx_linked_list *) list; | 875 cx_linked_list *ll = (cx_linked_list *) list; |
| 873 | 876 |
| 874 cx_linked_list_node *node = ll->begin; | 877 cx_linked_list_node *node = ll->begin; |
| 875 while (node) { | 878 while (node) { |
| 879 cx_invoke_destructor(list, node->payload); | |
| 876 void *next = node->next; | 880 void *next = node->next; |
| 877 cxFree(list->allocator, node); | 881 cxFree(list->allocator, node); |
| 878 node = next; | 882 node = next; |
| 879 } | 883 } |
| 880 // do not free the list pointer, this is just a destructor! | 884 |
| 885 cxFree(list->allocator, list); | |
| 881 } | 886 } |
| 882 | 887 |
| 883 static cx_list_class cx_linked_list_class = { | 888 static cx_list_class cx_linked_list_class = { |
| 884 cx_ll_destructor, | 889 cx_ll_destructor, |
| 885 cx_ll_insert_element, | 890 cx_ll_insert_element, |
