comparison: src/ucx/linked_list.c
src/ucx/linked_list.c
- changeset 582
- 82b60a8dd55c
- parent 579
- e10457d74fe1
- child 621
- 956c03c25edd
equal
deleted
inserted
replaced
| 581:4a049e416021 | 582:82b60a8dd55c |
|---|---|
| 399 void **begin, | 399 void **begin, |
| 400 void **end | 400 void **end |
| 401 ) { | 401 ) { |
| 402 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; | 402 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; |
| 403 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? | 403 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? |
| 404 malloc(sizeof(void *) * length) : sbo; | 404 cxMallocDefault(sizeof(void *) * length) : sbo; |
| 405 if (sorted == NULL) abort(); | 405 if (sorted == NULL) abort(); |
| 406 void *rc, *lc; | 406 void *rc, *lc; |
| 407 | 407 |
| 408 lc = ls; | 408 lc = ls; |
| 409 rc = le; | 409 rc = le; |
| 437 ll_next(sorted[length - 1]) = NULL; | 437 ll_next(sorted[length - 1]) = NULL; |
| 438 | 438 |
| 439 *begin = sorted[0]; | 439 *begin = sorted[0]; |
| 440 *end = sorted[length - 1]; | 440 *end = sorted[length - 1]; |
| 441 if (sorted != sbo) { | 441 if (sorted != sbo) { |
| 442 free(sorted); | 442 cxFreeDefault(sorted); |
| 443 } | 443 } |
| 444 } | 444 } |
| 445 | 445 |
| 446 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function | 446 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function |
| 447 void **begin, | 447 void **begin, |
| 611 // sortir if failed | 611 // sortir if failed |
| 612 if (new_node == NULL) return 1; | 612 if (new_node == NULL) return 1; |
| 613 | 613 |
| 614 // initialize new new_node | 614 // initialize new new_node |
| 615 new_node->prev = new_node->next = NULL; | 615 new_node->prev = new_node->next = NULL; |
| 616 memcpy(new_node->payload, elem, list->collection.elem_size); | 616 if (elem != NULL) { |
| 617 memcpy(new_node->payload, elem, list->collection.elem_size); | |
| 618 } | |
| 617 | 619 |
| 618 // insert | 620 // insert |
| 619 cx_linked_list *ll = (cx_linked_list *) list; | 621 cx_linked_list *ll = (cx_linked_list *) list; |
| 620 cx_linked_list_insert_chain( | 622 cx_linked_list_insert_chain( |
| 621 (void **) &ll->begin, (void **) &ll->end, | 623 (void **) &ll->begin, (void **) &ll->end, |
| 657 node = node->next; | 659 node = node->next; |
| 658 } | 660 } |
| 659 return n; | 661 return n; |
| 660 } | 662 } |
| 661 | 663 |
| 662 static int cx_ll_insert_element( | 664 static void *cx_ll_insert_element( |
| 663 struct cx_list_s *list, | 665 struct cx_list_s *list, |
| 664 size_t index, | 666 size_t index, |
| 665 const void *element | 667 const void *element |
| 666 ) { | 668 ) { |
| 667 return 1 != cx_ll_insert_array(list, index, element, 1); | 669 // out-of-bounds check |
| 670 if (index > list->collection.size) return NULL; | |
| 671 | |
| 672 // find position efficiently | |
| 673 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); | |
| 674 | |
| 675 // perform first insert | |
| 676 if (cx_ll_insert_at(list, node, element)) return NULL; | |
| 677 | |
| 678 // return a pointer to the data of the inserted node | |
| 679 if (node == NULL) { | |
| 680 return ((cx_linked_list *) list)->begin->payload; | |
| 681 } else { | |
| 682 return node->next->payload; | |
| 683 } | |
| 668 } | 684 } |
| 669 | 685 |
| 670 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; | 686 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; |
| 671 | 687 |
| 672 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { | 688 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { |
| 1054 iter->index++; | 1070 iter->index++; |
| 1055 } | 1071 } |
| 1056 } | 1072 } |
| 1057 return result; | 1073 return result; |
| 1058 } else { | 1074 } else { |
| 1059 int result = cx_ll_insert_element(list, list->collection.size, elem); | 1075 if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) { |
| 1060 if (result == 0) { | 1076 return 1; |
| 1061 iter->elem_count++; | 1077 } |
| 1062 iter->index = list->collection.size; | 1078 iter->elem_count++; |
| 1063 } | 1079 iter->index = list->collection.size; |
| 1064 return result; | 1080 return 0; |
| 1065 } | 1081 } |
| 1066 } | 1082 } |
| 1067 | 1083 |
| 1068 static void cx_ll_destructor(CxList *list) { | 1084 static void cx_ll_destructor(CxList *list) { |
| 1069 cx_linked_list *ll = (cx_linked_list *) list; | 1085 cx_linked_list *ll = (cx_linked_list *) list; |
