comparison: ucx/linked_list.c
ucx/linked_list.c
- branch
- dav-2
- changeset 886
- da79af4baec8
- parent 854
- 1c8401ece69e
- child 889
- 42cdbf9bbd49
equal
deleted
inserted
replaced
| 885:591377a27fa3 | 886:da79af4baec8 |
|---|---|
| 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, |
| 563 } | 563 } |
| 564 | 564 |
| 565 // HIGH LEVEL LINKED LIST IMPLEMENTATION | 565 // HIGH LEVEL LINKED LIST IMPLEMENTATION |
| 566 | 566 |
| 567 typedef struct cx_linked_list_node cx_linked_list_node; | 567 typedef struct cx_linked_list_node cx_linked_list_node; |
| 568 // IMPORTANT: the layout must stay exactly like this, because kv_list.c uses that! | |
| 568 struct cx_linked_list_node { | 569 struct cx_linked_list_node { |
| 569 cx_linked_list_node *prev; | 570 cx_linked_list_node *prev; |
| 570 cx_linked_list_node *next; | 571 cx_linked_list_node *next; |
| 571 char payload[]; | 572 char payload[]; |
| 572 }; | 573 }; |
| 611 // sortir if failed | 612 // sortir if failed |
| 612 if (new_node == NULL) return 1; | 613 if (new_node == NULL) return 1; |
| 613 | 614 |
| 614 // initialize new new_node | 615 // initialize new new_node |
| 615 new_node->prev = new_node->next = NULL; | 616 new_node->prev = new_node->next = NULL; |
| 616 memcpy(new_node->payload, elem, list->collection.elem_size); | 617 if (elem != NULL) { |
| 618 memcpy(new_node->payload, elem, list->collection.elem_size); | |
| 619 } | |
| 617 | 620 |
| 618 // insert | 621 // insert |
| 619 cx_linked_list *ll = (cx_linked_list *) list; | 622 cx_linked_list *ll = (cx_linked_list *) list; |
| 620 cx_linked_list_insert_chain( | 623 cx_linked_list_insert_chain( |
| 621 (void **) &ll->begin, (void **) &ll->end, | 624 (void **) &ll->begin, (void **) &ll->end, |
| 657 node = node->next; | 660 node = node->next; |
| 658 } | 661 } |
| 659 return n; | 662 return n; |
| 660 } | 663 } |
| 661 | 664 |
| 662 static int cx_ll_insert_element( | 665 static void *cx_ll_insert_element( |
| 663 struct cx_list_s *list, | 666 struct cx_list_s *list, |
| 664 size_t index, | 667 size_t index, |
| 665 const void *element | 668 const void *element |
| 666 ) { | 669 ) { |
| 667 return 1 != cx_ll_insert_array(list, index, element, 1); | 670 // out-of-bounds check |
| 671 if (index > list->collection.size) return NULL; | |
| 672 | |
| 673 // find position efficiently | |
| 674 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); | |
| 675 | |
| 676 // perform first insert | |
| 677 if (cx_ll_insert_at(list, node, element)) return NULL; | |
| 678 | |
| 679 // return a pointer to the data of the inserted node | |
| 680 if (node == NULL) { | |
| 681 return ((cx_linked_list *) list)->begin->payload; | |
| 682 } else { | |
| 683 return node->next->payload; | |
| 684 } | |
| 668 } | 685 } |
| 669 | 686 |
| 670 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; | 687 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; |
| 671 | 688 |
| 672 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { | 689 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { |
| 918 static size_t cx_ll_find_remove( | 935 static size_t cx_ll_find_remove( |
| 919 struct cx_list_s *list, | 936 struct cx_list_s *list, |
| 920 const void *elem, | 937 const void *elem, |
| 921 bool remove | 938 bool remove |
| 922 ) { | 939 ) { |
| 940 if (list->collection.size == 0) return 0; | |
| 941 | |
| 923 size_t index; | 942 size_t index; |
| 924 cx_linked_list *ll = ((cx_linked_list *) list); | 943 cx_linked_list *ll = ((cx_linked_list *) list); |
| 925 cx_linked_list_node *node = cx_linked_list_find( | 944 cx_linked_list_node *node = cx_linked_list_find( |
| 926 ll->begin, | 945 ll->begin, |
| 927 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | 946 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
| 1052 iter->index++; | 1071 iter->index++; |
| 1053 } | 1072 } |
| 1054 } | 1073 } |
| 1055 return result; | 1074 return result; |
| 1056 } else { | 1075 } else { |
| 1057 int result = cx_ll_insert_element(list, list->collection.size, elem); | 1076 if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) { |
| 1058 if (result == 0) { | 1077 return 1; |
| 1059 iter->elem_count++; | 1078 } |
| 1060 iter->index = list->collection.size; | 1079 iter->elem_count++; |
| 1061 } | 1080 iter->index = list->collection.size; |
| 1062 return result; | 1081 return 0; |
| 1063 } | 1082 } |
| 1064 } | 1083 } |
| 1065 | 1084 |
| 1066 static void cx_ll_destructor(CxList *list) { | 1085 static void cx_ll_destructor(CxList *list) { |
| 1067 cx_linked_list *ll = (cx_linked_list *) list; | 1086 cx_linked_list *ll = (cx_linked_list *) list; |
