comparison: src/linked_list.c
src/linked_list.c
- changeset 855
- 35bcb3216c0d
- parent 854
- fe0d69d72bcd
- child 856
- 6bbbf219251d
equal
deleted
inserted
replaced
| 854:fe0d69d72bcd | 855:35bcb3216c0d |
|---|---|
| 516 void const *elem | 516 void const *elem |
| 517 ) { | 517 ) { |
| 518 | 518 |
| 519 // create the new new_node | 519 // create the new new_node |
| 520 cx_linked_list_node *new_node = cxMalloc(list->base.allocator, | 520 cx_linked_list_node *new_node = cxMalloc(list->base.allocator, |
| 521 sizeof(cx_linked_list_node) + list->base.item_size); | 521 sizeof(cx_linked_list_node) + list->base.elem_size); |
| 522 | 522 |
| 523 // sortir if failed | 523 // sortir if failed |
| 524 if (new_node == NULL) return 1; | 524 if (new_node == NULL) return 1; |
| 525 | 525 |
| 526 // initialize new new_node | 526 // initialize new new_node |
| 527 new_node->prev = new_node->next = NULL; | 527 new_node->prev = new_node->next = NULL; |
| 528 memcpy(new_node->payload, elem, list->base.item_size); | 528 memcpy(new_node->payload, elem, list->base.elem_size); |
| 529 | 529 |
| 530 // insert | 530 // insert |
| 531 cx_linked_list *ll = (cx_linked_list *) list; | 531 cx_linked_list *ll = (cx_linked_list *) list; |
| 532 cx_linked_list_insert_chain( | 532 cx_linked_list_insert_chain( |
| 533 (void **) &ll->begin, (void **) &ll->end, | 533 (void **) &ll->begin, (void **) &ll->end, |
| 564 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; | 564 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; |
| 565 | 565 |
| 566 // we can add the remaining nodes and immedately advance to the inserted node | 566 // we can add the remaining nodes and immedately advance to the inserted node |
| 567 char const *source = array; | 567 char const *source = array; |
| 568 for (size_t i = 1; i < n; i++) { | 568 for (size_t i = 1; i < n; i++) { |
| 569 source += list->base.item_size; | 569 source += list->base.elem_size; |
| 570 if (0 != cx_ll_insert_at(list, node, source)) { | 570 if (0 != cx_ll_insert_at(list, node, source)) { |
| 571 return i; | 571 return i; |
| 572 } | 572 } |
| 573 node = node->next; | 573 node = node->next; |
| 574 } | 574 } |
| 705 nleft = cx_ll_node_at(ll, other); | 705 nleft = cx_ll_node_at(ll, other); |
| 706 } | 706 } |
| 707 } | 707 } |
| 708 } | 708 } |
| 709 | 709 |
| 710 if (list->base.item_size > CX_LINKED_LIST_SWAP_SBO_SIZE) { | 710 if (list->base.elem_size > CX_LINKED_LIST_SWAP_SBO_SIZE) { |
| 711 cx_linked_list_node *prev = nleft->prev; | 711 cx_linked_list_node *prev = nleft->prev; |
| 712 cx_linked_list_node *next = nright->next; | 712 cx_linked_list_node *next = nright->next; |
| 713 cx_linked_list_node *midstart = nleft->next; | 713 cx_linked_list_node *midstart = nleft->next; |
| 714 cx_linked_list_node *midend = nright->prev; | 714 cx_linked_list_node *midend = nright->prev; |
| 715 | 715 |
| 737 next->prev = nleft; | 737 next->prev = nleft; |
| 738 } | 738 } |
| 739 } else { | 739 } else { |
| 740 // swap payloads to avoid relinking | 740 // swap payloads to avoid relinking |
| 741 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; | 741 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; |
| 742 memcpy(buf, nleft->payload, list->base.item_size); | 742 memcpy(buf, nleft->payload, list->base.elem_size); |
| 743 memcpy(nleft->payload, nright->payload, list->base.item_size); | 743 memcpy(nleft->payload, nright->payload, list->base.elem_size); |
| 744 memcpy(nright->payload, buf, list->base.item_size); | 744 memcpy(nright->payload, buf, list->base.elem_size); |
| 745 } | 745 } |
| 746 | 746 |
| 747 return 0; | 747 return 0; |
| 748 } | 748 } |
| 749 | 749 |
| 869 ) { | 869 ) { |
| 870 CxIterator iter; | 870 CxIterator iter; |
| 871 iter.index = index; | 871 iter.index = index; |
| 872 iter.src_handle.c = list; | 872 iter.src_handle.c = list; |
| 873 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); | 873 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); |
| 874 iter.elem_size = list->base.item_size; | 874 iter.elem_size = list->base.elem_size; |
| 875 iter.elem_count = list->base.size; | 875 iter.elem_count = list->base.size; |
| 876 iter.base.valid = cx_ll_iter_valid; | 876 iter.base.valid = cx_ll_iter_valid; |
| 877 iter.base.current = cx_ll_iter_current; | 877 iter.base.current = cx_ll_iter_current; |
| 878 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; | 878 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; |
| 879 iter.base.mutating = false; | 879 iter.base.mutating = false; |
| 932 }; | 932 }; |
| 933 | 933 |
| 934 CxList *cxLinkedListCreate( | 934 CxList *cxLinkedListCreate( |
| 935 CxAllocator const *allocator, | 935 CxAllocator const *allocator, |
| 936 cx_compare_func comparator, | 936 cx_compare_func comparator, |
| 937 size_t item_size | 937 size_t elem_size |
| 938 ) { | 938 ) { |
| 939 if (allocator == NULL) { | 939 if (allocator == NULL) { |
| 940 allocator = cxDefaultAllocator; | 940 allocator = cxDefaultAllocator; |
| 941 } | 941 } |
| 942 | 942 |
| 944 if (list == NULL) return NULL; | 944 if (list == NULL) return NULL; |
| 945 | 945 |
| 946 list->base.cl = &cx_linked_list_class; | 946 list->base.cl = &cx_linked_list_class; |
| 947 list->base.base.allocator = allocator; | 947 list->base.base.allocator = allocator; |
| 948 | 948 |
| 949 if (item_size > 0) { | 949 if (elem_size > 0) { |
| 950 list->base.base.item_size = item_size; | 950 list->base.base.elem_size = elem_size; |
| 951 list->base.base.cmpfunc = comparator; | 951 list->base.base.cmpfunc = comparator; |
| 952 } else { | 952 } else { |
| 953 list->base.base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; | 953 list->base.base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; |
| 954 cxListStorePointers((CxList *) list); | 954 cxListStorePointers((CxList *) list); |
| 955 } | 955 } |
