diff -r b60487c3ec36 -r af685cc9d623 ucx/linked_list.c --- a/ucx/linked_list.c Sun Aug 31 14:39:13 2025 +0200 +++ b/ucx/linked_list.c Sat Nov 08 23:06:11 2025 +0100 @@ -244,6 +244,147 @@ begin, end, loc_prev, loc_next, new_node, cmp_func); } +static void *cx_linked_list_insert_sorted_chain_impl( + void **begin, + void **end, + ptrdiff_t loc_prev, + ptrdiff_t loc_next, + void *insert_begin, + cx_compare_func cmp_func, + bool allow_duplicates +) { + assert(begin != NULL); + assert(loc_next >= 0); + assert(insert_begin != NULL); + + // strategy: build completely new chains from scratch + void *source_original = *begin; + void *source_argument = insert_begin; + void *new_begin = NULL; + void *new_end = NULL; + void *dup_begin = NULL; + void *dup_end = NULL; + + // determine the new start + { + int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument); + if (d <= 0) { + // the new chain starts with the original chain + new_begin = new_end = source_original; + source_original = ll_next(source_original); + if (d == 0) { + if (allow_duplicates) { + // duplicate allowed, append it to the chain + cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); + new_end = source_argument; + } else { + // duplicate is not allowed, start a duplicate chain with the argument + dup_begin = dup_end = source_argument; + } + source_argument = ll_next(source_argument); + } + } else { + // input is smaller, or there is no original chain; + // start the new chain with the source argument + new_begin = new_end = source_argument; + source_argument = ll_next(source_argument); + } + } + + // now successively compare the elements and add them to the correct chains + while (source_original != NULL && source_argument != NULL) { + int d = cmp_func(source_original, source_argument); + if (d <= 0) { + // the original is not larger, add it to the chain + cx_linked_list_link(new_end, source_original, loc_prev, loc_next); + new_end = source_original; + source_original = ll_next(source_original); + if (d == 0) { + if (allow_duplicates) { + // duplicate allowed, append it to the chain + cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); + new_end = source_argument; + } else { + // duplicate is not allowed, append it to the duplicate chain + if (dup_end == NULL) { + dup_begin = dup_end = source_argument; + } else { + cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); + dup_end = source_argument; + } + } + source_argument = ll_next(source_argument); + } + } else { + // the original is larger, append the source argument to the chain + // check if we must discard the source argument as duplicate + if (!allow_duplicates && cmp_func(new_end, source_argument) == 0) { + if (dup_end == NULL) { + dup_begin = dup_end = source_argument; + } else { + cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); + dup_end = source_argument; + } + } else { + // no duplicate or duplicates allowed + cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); + new_end = source_argument; + } + source_argument = ll_next(source_argument); + } + } + + if (source_original != NULL) { + // something is left from the original chain, append it + cx_linked_list_link(new_end, source_original, loc_prev, loc_next); + new_end = cx_linked_list_last(source_original, loc_next); + } else if (source_argument != NULL) { + // something is left from the input chain; + // when we allow duplicates, append it + if (allow_duplicates) { + cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); + new_end = cx_linked_list_last(source_argument, loc_next); + } else { + // otherwise we must check one-by-one + while (source_argument != NULL) { + if (cmp_func(new_end, source_argument) == 0) { + if (dup_end == NULL) { + dup_begin = dup_end = source_argument; + } else { + cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); + dup_end = source_argument; + } + } else { + cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); + new_end = source_argument; + } + source_argument = ll_next(source_argument); + } + } + } + + // null the next pointers at the end of the chain + ll_next(new_end) = NULL; + if (dup_end != NULL) { + ll_next(dup_end) = NULL; + } + + // null the optional prev pointers + if (loc_prev >= 0) { + ll_prev(new_begin) = NULL; + if (dup_begin != NULL) { + ll_prev(dup_begin) = NULL; + } + } + + // output + *begin = new_begin; + if (end != NULL) { + *end = new_end; + } + return dup_begin; +} + void cx_linked_list_insert_sorted_chain( void **begin, void **end, @@ -252,72 +393,35 @@ void *insert_begin, cx_compare_func cmp_func ) { - assert(begin != NULL); - assert(loc_next >= 0); - assert(insert_begin != NULL); - - // track currently observed nodes - void *dest_prev = NULL; - void *dest = *begin; - void *src = insert_begin; - - // special case: list is empty - if (dest == NULL) { - *begin = src; - if (end != NULL) { - *end = cx_linked_list_last(src, loc_next); - } - return; - } - - // search the list for insertion points - while (dest != NULL && src != NULL) { - // compare current list node with source node - // if less or equal, skip - if (cmp_func(dest, src) <= 0) { - dest_prev = dest; - dest = ll_next(dest); - continue; - } + cx_linked_list_insert_sorted_chain_impl( + begin, end, loc_prev, loc_next, + insert_begin, cmp_func, true); +} - // determine chain of elements that can be inserted - void *end_of_chain = src; - void *next_in_chain = ll_next(src); - while (next_in_chain != NULL) { - // once we become larger than the list elem, break - if (cmp_func(dest, next_in_chain) <= 0) { - break; - } - // otherwise, we can insert one more - end_of_chain = next_in_chain; - next_in_chain = ll_next(next_in_chain); - } +int cx_linked_list_insert_unique( + void **begin, + void **end, + ptrdiff_t loc_prev, + ptrdiff_t loc_next, + void *new_node, + cx_compare_func cmp_func +) { + assert(ll_next(new_node) == NULL); + return NULL != cx_linked_list_insert_unique_chain( + begin, end, loc_prev, loc_next, new_node, cmp_func); +} - // insert the elements - if (dest_prev == NULL) { - // new begin - *begin = src; - } else { - cx_linked_list_link(dest_prev, src, loc_prev, loc_next); - } - cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next); - - // continue with next - src = next_in_chain; - dest_prev = dest; - dest = ll_next(dest); - } - - // insert remaining items - if (src != NULL) { - cx_linked_list_link(dest_prev, src, loc_prev, loc_next); - } - - // determine new end of list, if requested - if (end != NULL) { - *end = cx_linked_list_last( - dest != NULL ? dest : dest_prev, loc_next); - } +void *cx_linked_list_insert_unique_chain( + void **begin, + void **end, + ptrdiff_t loc_prev, + ptrdiff_t loc_next, + void *insert_begin, + cx_compare_func cmp_func +) { + return cx_linked_list_insert_sorted_chain_impl( + begin, end, loc_prev, loc_next, + insert_begin, cmp_func, false); } size_t cx_linked_list_remove_chain( @@ -370,6 +474,16 @@ return removed; } +void cx_linked_list_remove( + void **begin, + void **end, + ptrdiff_t loc_prev, + ptrdiff_t loc_next, + void *node +) { + cx_linked_list_remove_chain(begin, end, loc_prev, loc_next, node, 1); +} + size_t cx_linked_list_size( const void *node, ptrdiff_t loc_next @@ -401,7 +515,7 @@ ) { void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? - malloc(sizeof(void *) * length) : sbo; + cxMallocDefault(sizeof(void *) * length) : sbo; if (sorted == NULL) abort(); void *rc, *lc; @@ -439,7 +553,7 @@ *begin = sorted[0]; *end = sorted[length - 1]; if (sorted != sbo) { - free(sorted); + cxFreeDefault(sorted); } } @@ -564,62 +678,46 @@ // HIGH LEVEL LINKED LIST IMPLEMENTATION -typedef struct cx_linked_list_node cx_linked_list_node; -struct cx_linked_list_node { - cx_linked_list_node *prev; - cx_linked_list_node *next; - char payload[]; -}; - -#define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev) -#define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next) -#define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload) - -typedef struct { - struct cx_list_s base; - cx_linked_list_node *begin; - cx_linked_list_node *end; -} cx_linked_list; - -static cx_linked_list_node *cx_ll_node_at( +static void *cx_ll_node_at( const cx_linked_list *list, size_t index ) { if (index >= list->base.collection.size) { return NULL; } else if (index > list->base.collection.size / 2) { - return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index); + return cx_linked_list_at(list->end, list->base.collection.size - 1, list->loc_prev, index); } else { - return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); + return cx_linked_list_at(list->begin, 0, list->loc_next, index); } } -static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) { - return cxMalloc(list->collection.allocator, - sizeof(cx_linked_list_node) + list->collection.elem_size); +static void *cx_ll_malloc_node(const cx_linked_list *list) { + return cxZalloc(list->base.collection.allocator, + list->loc_data + list->base.collection.elem_size + list->extra_data_len); } static int cx_ll_insert_at( struct cx_list_s *list, - cx_linked_list_node *node, + void *node, const void *elem ) { + cx_linked_list *ll = (cx_linked_list *) list; // create the new new_node - cx_linked_list_node *new_node = cx_ll_malloc_node(list); + void *new_node = cx_ll_malloc_node(ll); // sortir if failed if (new_node == NULL) return 1; - // initialize new new_node - new_node->prev = new_node->next = NULL; - memcpy(new_node->payload, elem, list->collection.elem_size); + // copy the data + if (elem != NULL) { + memcpy((char*)new_node + ll->loc_data, elem, list->collection.elem_size); + } // insert - cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_insert_chain( - (void **) &ll->begin, (void **) &ll->end, - CX_LL_LOC_PREV, CX_LL_LOC_NEXT, + &ll->begin, &ll->end, + ll->loc_prev, ll->loc_next, node, new_node, new_node ); @@ -638,7 +736,7 @@ if (index > list->collection.size || n == 0) return 0; // find position efficiently - cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); + void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); // perform first insert if (0 != cx_ll_insert_at(list, node, array)) return 1; @@ -647,32 +745,119 @@ if (n == 1) return 1; // we now know exactly where we are - node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; + cx_linked_list *ll = (cx_linked_list *) list; + node = node == NULL ? ((cx_linked_list *) list)->begin : CX_LL_PTR(node, ll->loc_next); // we can add the remaining nodes and immediately advance to the inserted node const char *source = array; for (size_t i = 1; i < n; i++) { - source += list->collection.elem_size; + if (source != NULL) { + source += list->collection.elem_size; + } if (0 != cx_ll_insert_at(list, node, source)) return i; - node = node->next; + node = CX_LL_PTR(node, ll->loc_next); } return n; } -static int cx_ll_insert_element( +static void *cx_ll_insert_element( struct cx_list_s *list, size_t index, const void *element ) { - return 1 != cx_ll_insert_array(list, index, element, 1); + // out-of-bounds check + if (index > list->collection.size) return NULL; + + // find position efficiently + void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); + + // perform first insert + if (cx_ll_insert_at(list, node, element)) return NULL; + + // return a pointer to the data of the inserted node + cx_linked_list *ll = (cx_linked_list *) list; + if (node == NULL) { + return (char*)(ll->begin) + ll->loc_data; + } else { + char *next = CX_LL_PTR(node, ll->loc_next); + return next + ll->loc_data; + } } static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; +static _Thread_local off_t cx_ll_insert_sorted_loc_data; static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { - const cx_linked_list_node *left = l; - const cx_linked_list_node *right = r; - return cx_ll_insert_sorted_cmp_func(left->payload, right->payload); + const char *left = (const char*)l + cx_ll_insert_sorted_loc_data; + const char *right = (const char*)r + cx_ll_insert_sorted_loc_data; + return cx_ll_insert_sorted_cmp_func(left, right); +} + +static size_t cx_ll_insert_sorted_impl( + struct cx_list_s *list, + const void *array, + size_t n, + bool allow_duplicates +) { + cx_linked_list *ll = (cx_linked_list *) list; + + // special case + if (n == 0) return 0; + + // create a new chain of nodes + void *chain = cx_ll_malloc_node(ll); + if (chain == NULL) return 0; + + memcpy((char*)chain + ll->loc_data, array, list->collection.elem_size); + + // add all elements from the array to that chain + void *prev = chain; + const char *src = array; + size_t inserted = 1; + for (; inserted < n; inserted++) { + void *next = cx_ll_malloc_node(ll); + if (next == NULL) break; + src += list->collection.elem_size; + memcpy((char*)next + ll->loc_data, src, list->collection.elem_size); + CX_LL_PTR(prev, ll->loc_next) = next; + CX_LL_PTR(next, ll->loc_prev) = prev; + prev = next; + } + CX_LL_PTR(prev, ll->loc_next) = NULL; + + // invoke the low level function + cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; + cx_ll_insert_sorted_loc_data = ll->loc_data; + if (allow_duplicates) { + cx_linked_list_insert_sorted_chain( + &ll->begin, + &ll->end, + ll->loc_prev, + ll->loc_next, + chain, + cx_ll_insert_sorted_cmp_helper + ); + list->collection.size += inserted; + } else { + void *duplicates = cx_linked_list_insert_unique_chain( + &ll->begin, + &ll->end, + ll->loc_prev, + ll->loc_next, + chain, + cx_ll_insert_sorted_cmp_helper + ); + list->collection.size += inserted; + // free the nodes that did not make it into the list + while (duplicates != NULL) { + void *next = CX_LL_PTR(duplicates, ll->loc_next); + cxFree(list->collection.allocator, duplicates); + duplicates = next; + list->collection.size--; + } + } + + return inserted; } static size_t cx_ll_insert_sorted( @@ -680,48 +865,15 @@ const void *array, size_t n ) { - // special case - if (n == 0) return 0; - - // create a new chain of nodes - cx_linked_list_node *chain = cx_ll_malloc_node(list); - if (chain == NULL) return 0; - - memcpy(chain->payload, array, list->collection.elem_size); - chain->prev = NULL; - chain->next = NULL; + return cx_ll_insert_sorted_impl(list, array, n, true); +} - // add all elements from the array to that chain - cx_linked_list_node *prev = chain; - const char *src = array; - size_t inserted = 1; - for (; inserted < n; inserted++) { - cx_linked_list_node *next = cx_ll_malloc_node(list); - if (next == NULL) break; - src += list->collection.elem_size; - memcpy(next->payload, src, list->collection.elem_size); - prev->next = next; - next->prev = prev; - prev = next; - } - prev->next = NULL; - - // invoke the low level function - cx_linked_list *ll = (cx_linked_list *) list; - cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; - cx_linked_list_insert_sorted_chain( - (void **) &ll->begin, - (void **) &ll->end, - CX_LL_LOC_PREV, - CX_LL_LOC_NEXT, - chain, - cx_ll_insert_sorted_cmp_helper - ); - - // adjust the list metadata - list->collection.size += inserted; - - return inserted; +static size_t cx_ll_insert_unique( + struct cx_list_s *list, + const void *array, + size_t n +) { + return cx_ll_insert_sorted_impl(list, array, n, false); } static size_t cx_ll_remove( @@ -731,7 +883,7 @@ void *targetbuf ) { cx_linked_list *ll = (cx_linked_list *) list; - cx_linked_list_node *node = cx_ll_node_at(ll, index); + void *node = cx_ll_node_at(ll, index); // out-of-bounds check if (node == NULL) return 0; @@ -740,8 +892,8 @@ size_t removed = cx_linked_list_remove_chain( (void **) &ll->begin, (void **) &ll->end, - CX_LL_LOC_PREV, - CX_LL_LOC_NEXT, + ll->loc_prev, + ll->loc_next, node, num ); @@ -751,28 +903,28 @@ // copy or destroy the removed chain if (targetbuf == NULL) { - cx_linked_list_node *n = node; + char *n = node; for (size_t i = 0; i < removed; i++) { // element destruction - cx_invoke_destructor(list, n->payload); + cx_invoke_destructor(list, n + ll->loc_data); // free the node and advance - void *next = n->next; + void *next = CX_LL_PTR(n, ll->loc_next); cxFree(list->collection.allocator, n); n = next; } } else { char *dest = targetbuf; - cx_linked_list_node *n = node; + char *n = node; for (size_t i = 0; i < removed; i++) { // copy payload - memcpy(dest, n->payload, list->collection.elem_size); + memcpy(dest, n + ll->loc_data, list->collection.elem_size); // advance target buffer dest += list->collection.elem_size; // free the node and advance - void *next = n->next; + void *next = CX_LL_PTR(n, ll->loc_next); cxFree(list->collection.allocator, n); n = next; } @@ -785,10 +937,10 @@ if (list->collection.size == 0) return; cx_linked_list *ll = (cx_linked_list *) list; - cx_linked_list_node *node = ll->begin; + char *node = ll->begin; while (node != NULL) { - cx_invoke_destructor(list, node->payload); - cx_linked_list_node *next = node->next; + cx_invoke_destructor(list, node + ll->loc_data); + void *next = CX_LL_PTR(node, ll->loc_next); cxFree(list->collection.allocator, node); node = next; } @@ -815,14 +967,14 @@ left = j; right = i; } - cx_linked_list_node *nleft = NULL, *nright = NULL; + void *nleft = NULL, *nright = NULL; if (left < mid && right < mid) { // case 1: both items left from mid nleft = cx_ll_node_at(ll, left); assert(nleft != NULL); nright = nleft; for (size_t c = left; c < right; c++) { - nright = nright->next; + nright = CX_LL_PTR(nright, ll->loc_next); } } else if (left >= mid && right >= mid) { // case 2: both items right from mid @@ -830,7 +982,7 @@ assert(nright != NULL); nleft = nright; for (size_t c = right; c > left; c--) { - nleft = nleft->prev; + nleft = CX_LL_PTR(nleft, ll->loc_prev); } } else { // case 3: one item left, one item right @@ -856,12 +1008,12 @@ if (closest == left) { nright = nleft; for (size_t c = left; c < right; c++) { - nright = nright->next; + nright = CX_LL_PTR(nright, ll->loc_next); } } else { nleft = nright; for (size_t c = right; c > left; c--) { - nleft = nleft->prev; + nleft = CX_LL_PTR(nleft, ll->loc_prev); } } } else { @@ -874,33 +1026,33 @@ } } - cx_linked_list_node *prev = nleft->prev; - cx_linked_list_node *next = nright->next; - cx_linked_list_node *midstart = nleft->next; - cx_linked_list_node *midend = nright->prev; + void *prev = CX_LL_PTR(nleft, ll->loc_prev); + void *next = CX_LL_PTR(nright, ll->loc_next); + void *midstart = CX_LL_PTR(nleft, ll->loc_next); + void *midend = CX_LL_PTR(nright, ll->loc_prev); if (prev == NULL) { ll->begin = nright; } else { - prev->next = nright; + CX_LL_PTR(prev, ll->loc_next) = nright; } - nright->prev = prev; + CX_LL_PTR(nright, ll->loc_prev) = prev; if (midstart == nright) { // special case: both nodes are adjacent - nright->next = nleft; - nleft->prev = nright; + CX_LL_PTR(nright, ll->loc_next) = nleft; + CX_LL_PTR(nleft, ll->loc_prev) = nright; } else { // likely case: a chain is between the two nodes - nright->next = midstart; - midstart->prev = nright; - midend->next = nleft; - nleft->prev = midend; + CX_LL_PTR(nright, ll->loc_next) = midstart; + CX_LL_PTR(midstart, ll->loc_prev) = nright; + CX_LL_PTR(midend, ll->loc_next) = nleft; + CX_LL_PTR(nleft, ll->loc_prev) = midend; } - nleft->next = next; + CX_LL_PTR(nleft, ll->loc_next) = next; if (next == NULL) { ll->end = nleft; } else { - next->prev = nleft; + CX_LL_PTR(next, ll->loc_prev) = nleft; } return 0; @@ -911,8 +1063,8 @@ size_t index ) { cx_linked_list *ll = (cx_linked_list *) list; - cx_linked_list_node *node = cx_ll_node_at(ll, index); - return node == NULL ? NULL : node->payload; + char *node = cx_ll_node_at(ll, index); + return node == NULL ? NULL : node + ll->loc_data; } static size_t cx_ll_find_remove( @@ -920,11 +1072,13 @@ const void *elem, bool remove ) { + if (list->collection.size == 0) return 0; + size_t index; - cx_linked_list *ll = ((cx_linked_list *) list); - cx_linked_list_node *node = cx_linked_list_find( + cx_linked_list *ll = (cx_linked_list *) list; + char *node = cx_linked_list_find( ll->begin, - CX_LL_LOC_NEXT, CX_LL_LOC_DATA, + ll->loc_next, ll->loc_data, list->collection.cmpfunc, elem, &index ); @@ -932,9 +1086,9 @@ return list->collection.size; } if (remove) { - cx_invoke_destructor(list, node->payload); - cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, - CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); + cx_invoke_destructor(list, node + ll->loc_data); + cx_linked_list_remove(&ll->begin, &ll->end, + ll->loc_prev, ll->loc_next, node); list->collection.size--; cxFree(list->collection.allocator, node); } @@ -943,14 +1097,14 @@ static void cx_ll_sort(struct cx_list_s *list) { cx_linked_list *ll = (cx_linked_list *) list; - cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, - CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, + cx_linked_list_sort(&ll->begin, &ll->end, + ll->loc_prev, ll->loc_next, ll->loc_data, list->collection.cmpfunc); } static void cx_ll_reverse(struct cx_list_s *list) { cx_linked_list *ll = (cx_linked_list *) list; - cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); + cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next); } static int cx_ll_compare( @@ -959,8 +1113,10 @@ ) { cx_linked_list *left = (cx_linked_list *) list; cx_linked_list *right = (cx_linked_list *) other; + assert(left->loc_next == right->loc_next); + assert(left->loc_data == right->loc_data); return cx_linked_list_compare(left->begin, right->begin, - CX_LL_LOC_NEXT, CX_LL_LOC_DATA, + left->loc_next, left->loc_data, list->collection.cmpfunc); } @@ -971,49 +1127,52 @@ static void cx_ll_iter_next(void *it) { struct cx_iterator_s *iter = it; + cx_linked_list *ll = iter->src_handle; if (iter->base.remove) { iter->base.remove = false; - struct cx_list_s *list = iter->src_handle.m; - cx_linked_list *ll = iter->src_handle.m; - cx_linked_list_node *node = iter->elem_handle; - iter->elem_handle = node->next; - cx_invoke_destructor(list, node->payload); - cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, - CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); + struct cx_list_s *list = iter->src_handle; + char *node = iter->elem_handle; + iter->elem_handle = CX_LL_PTR(node, ll->loc_next); + cx_invoke_destructor(list, node + ll->loc_data); + cx_linked_list_remove(&ll->begin, &ll->end, + ll->loc_prev, ll->loc_next, node); list->collection.size--; + iter->elem_count--; cxFree(list->collection.allocator, node); } else { iter->index++; - cx_linked_list_node *node = iter->elem_handle; - iter->elem_handle = node->next; + void *node = iter->elem_handle; + iter->elem_handle = CX_LL_PTR(node, ll->loc_next); } } static void cx_ll_iter_prev(void *it) { struct cx_iterator_s *iter = it; + cx_linked_list *ll = iter->src_handle; if (iter->base.remove) { iter->base.remove = false; - struct cx_list_s *list = iter->src_handle.m; - cx_linked_list *ll = iter->src_handle.m; - cx_linked_list_node *node = iter->elem_handle; - iter->elem_handle = node->prev; + struct cx_list_s *list = iter->src_handle; + char *node = iter->elem_handle; + iter->elem_handle = CX_LL_PTR(node, ll->loc_prev); iter->index--; - cx_invoke_destructor(list, node->payload); - cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, - CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); + cx_invoke_destructor(list, node + ll->loc_data); + cx_linked_list_remove(&ll->begin, &ll->end, + ll->loc_prev, ll->loc_next, node); list->collection.size--; + iter->elem_count--; cxFree(list->collection.allocator, node); } else { iter->index--; - cx_linked_list_node *node = iter->elem_handle; - iter->elem_handle = node->prev; + char *node = iter->elem_handle; + iter->elem_handle = CX_LL_PTR(node, ll->loc_prev); } } static void *cx_ll_iter_current(const void *it) { const struct cx_iterator_s *iter = it; - cx_linked_list_node *node = iter->elem_handle; - return node->payload; + const cx_linked_list *ll = iter->src_handle; + char *node = iter->elem_handle; + return node + ll->loc_data; } static CxIterator cx_ll_iterator( @@ -1023,14 +1182,14 @@ ) { CxIterator iter; iter.index = index; - iter.src_handle.c = list; + iter.src_handle = (void*)list; iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index); iter.elem_size = list->collection.elem_size; iter.elem_count = list->collection.size; iter.base.valid = cx_ll_iter_valid; iter.base.current = cx_ll_iter_current; iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; - iter.base.mutating = false; + iter.base.allow_remove = true; iter.base.remove = false; return iter; } @@ -1040,11 +1199,12 @@ const void *elem, int prepend ) { - struct cx_list_s *list = iter->src_handle.m; - cx_linked_list_node *node = iter->elem_handle; + struct cx_list_s *list = iter->src_handle; + cx_linked_list *ll = iter->src_handle; + void *node = iter->elem_handle; if (node != NULL) { assert(prepend >= 0 && prepend <= 1); - cx_linked_list_node *choice[2] = {node, node->prev}; + void *choice[2] = {node, CX_LL_PTR(node, ll->loc_prev)}; int result = cx_ll_insert_at(list, choice[prepend], elem); if (result == 0) { iter->elem_count++; @@ -1054,22 +1214,22 @@ } return result; } else { - int result = cx_ll_insert_element(list, list->collection.size, elem); - if (result == 0) { - iter->elem_count++; - iter->index = list->collection.size; + if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) { + return 1; } - return result; + iter->elem_count++; + iter->index = list->collection.size; + return 0; } } static void cx_ll_destructor(CxList *list) { cx_linked_list *ll = (cx_linked_list *) list; - cx_linked_list_node *node = ll->begin; + char *node = ll->begin; while (node) { - cx_invoke_destructor(list, node->payload); - void *next = node->next; + cx_invoke_destructor(list, node + ll->loc_data); + void *next = CX_LL_PTR(node, ll->loc_next); cxFree(list->collection.allocator, node); node = next; } @@ -1082,6 +1242,7 @@ cx_ll_insert_element, cx_ll_insert_array, cx_ll_insert_sorted, + cx_ll_insert_unique, cx_ll_insert_iter, cx_ll_remove, cx_ll_clear, @@ -1105,6 +1266,10 @@ cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); if (list == NULL) return NULL; + list->extra_data_len = 0; + list->loc_prev = 0; + list->loc_next = sizeof(void*); + list->loc_data = sizeof(void*)*2; cx_list_init((CxList*)list, &cx_linked_list_class, allocator, comparator, elem_size);