dav: comparison ucx/linked

-:b60487c3ec36
+:af685cc9d623
 assert(ll_next(new_node) == NULL);
 cx_linked_list_insert_sorted_chain(
 begin, end, loc_prev, loc_next, new_node, cmp_func);
 }
-void cx_linked_list_insert_sorted_chain(
+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
+cx_compare_func cmp_func,
+bool allow_duplicates
 ) {
 assert(begin != NULL);
 assert(loc_next >= 0);
 assert(insert_begin != NULL);
-// track currently observed nodes
+// strategy: build completely new chains from scratch
-void *dest_prev = NULL;
+void *source_original = *begin;
-void *dest = *begin;
+void *source_argument = insert_begin;
-void *src = insert_begin;
+void *new_begin = NULL;
+void *new_end = NULL;
-// special case: list is empty
+void *dup_begin = NULL;
-if (dest == NULL) {
+void *dup_end = NULL;
-*begin = src;
-if (end != NULL) {
+// determine the new start
-*end = cx_linked_list_last(src, loc_next);
+{
-}
+int d = source_original ==  NULL ? 1 : cmp_func(source_original, source_argument);
-return;
+if (d <= 0) {
-}
+// the new chain starts with the original chain
+new_begin = new_end = source_original;
-// search the list for insertion points
+source_original = ll_next(source_original);
-while (dest != NULL && src != NULL) {
+if (d == 0) {
-// compare current list node with source node
+if (allow_duplicates) {
-// if less or equal, skip
+// duplicate allowed, append it to the chain
-if (cmp_func(dest, src) <= 0) {
+cx_linked_list_link(new_end, source_argument, loc_prev, loc_next);
-dest_prev = dest;
+new_end = source_argument;
-dest = ll_next(dest);
+} else {
-continue;
+// duplicate is not allowed, start a duplicate chain with the argument
-}
+dup_begin = dup_end = source_argument;
+}
-// determine chain of elements that can be inserted
+source_argument = ll_next(source_argument);
-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);
-}
-// insert the elements
-if (dest_prev == NULL) {
-// new begin
-*begin = src;
 } else {
-cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
+// input is smaller, or there is no original chain;
-}
+// start the new chain with the source argument
-cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next);
+new_begin = new_end = source_argument;
+source_argument = ll_next(source_argument);
-// continue with next
+}
-src = next_in_chain;
+}
-dest_prev = dest;
-dest = ll_next(dest);
+// 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);
-// insert remaining items
+if (d <= 0) {
-if (src != NULL) {
+// the original is not larger, add it to the chain
-cx_linked_list_link(dest_prev, src, loc_prev, loc_next);
+cx_linked_list_link(new_end, source_original, loc_prev, loc_next);
-}
+new_end = source_original;
+source_original = ll_next(source_original);
-// determine new end of list, if requested
+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 = cx_linked_list_last(
+*end = new_end;
-dest != NULL ? dest : dest_prev, loc_next);
+}
-}
+return dup_begin;
+}
+void cx_linked_list_insert_sorted_chain(
+void **begin,
+void **end,
+ptrdiff_t loc_prev,
+ptrdiff_t loc_next,
+void *insert_begin,
+cx_compare_func cmp_func
+) {
+cx_linked_list_insert_sorted_chain_impl(
+begin, end, loc_prev, loc_next,
+insert_begin, cmp_func, true);
+}
+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);
+}
+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(
 void **begin,
 void **end,
 } else if (loc_prev >= 0) {
 ll_prev(next) = prev;
 }
 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
 void **begin,
 void **end
 ) {
 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;
 lc = ls;
 rc = le;
 ll_next(sorted[length - 1]) = NULL;
 *begin = sorted[0];
 *end = sorted[length - 1];
 if (sorted != sbo) {
-free(sorted);
+cxFreeDefault(sorted);
 }
 }
 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function
 void **begin,
 *begin = prev;
 }
 // HIGH LEVEL LINKED LIST IMPLEMENTATION
-typedef struct cx_linked_list_node cx_linked_list_node;
+static void *cx_ll_node_at(
-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(
 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) {
+static void *cx_ll_malloc_node(const cx_linked_list *list) {
-return cxMalloc(list->collection.allocator,
+return cxZalloc(list->base.collection.allocator,
-sizeof(cx_linked_list_node) + list->collection.elem_size);
+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
+// copy the data
-new_node->prev = new_node->next = NULL;
+if (elem != NULL) {
-memcpy(new_node->payload, elem, list->collection.elem_size);
+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,
+&ll->begin, &ll->end,
-CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
+ll->loc_prev, ll->loc_next,
 node, new_node, new_node
 );
 // increase the size and return
 list->collection.size++;
 ) {
 // out-of bounds and corner case check
 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;
 // is there more?
 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 char *left = (const char*)l + cx_ll_insert_sorted_loc_data;
-const cx_linked_list_node *right = r;
+const char *right = (const char*)r + cx_ll_insert_sorted_loc_data;
-return cx_ll_insert_sorted_cmp_func(left->payload, right->payload);
+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(
 struct cx_list_s *list,
 const void *array,
 size_t n
 ) {
-// special case
+return cx_ll_insert_sorted_impl(list, array, n, true);
-if (n == 0) return 0;
+}
-// create a new chain of nodes
+static size_t cx_ll_insert_unique(
-cx_linked_list_node *chain = cx_ll_malloc_node(list);
+struct cx_list_s *list,
-if (chain == NULL) return 0;
+const void *array,
+size_t n
-memcpy(chain->payload, array, list->collection.elem_size);
+) {
-chain->prev = NULL;
+return cx_ll_insert_sorted_impl(list, array, n, false);
-chain->next = NULL;
-// 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_remove(
 struct cx_list_s *list,
 size_t index,
 size_t num,
 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;
 // remove
 size_t removed = cx_linked_list_remove_chain(
 (void **) &ll->begin,
 (void **) &ll->end,
-CX_LL_LOC_PREV,
+ll->loc_prev,
-CX_LL_LOC_NEXT,
+ll->loc_next,
 node,
 num
 );
 // adjust size
 list->collection.size -= removed;
 // 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;
 }
 }
 static void cx_ll_clear(struct cx_list_s *list) {
 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_invoke_destructor(list, node + ll->loc_data);
-cx_linked_list_node *next = node->next;
+void *next = CX_LL_PTR(node, ll->loc_next);
 cxFree(list->collection.allocator, node);
 node = next;
 }
 ll->begin = ll->end = NULL;
 list->collection.size = 0;
 right = j;
 } else {
 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
 nright = cx_ll_node_at(ll, right);
 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
 // chose the closest to begin / end
 if (right - left <= diff2boundary) {
 // search other element starting from already found element
 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 {
 // search other element starting at the boundary
 if (closest == left) {
 nleft = cx_ll_node_at(ll, other);
 }
 }
 }
-cx_linked_list_node *prev = nleft->prev;
+void *prev = CX_LL_PTR(nleft, ll->loc_prev);
-cx_linked_list_node *next = nright->next;
+void *next = CX_LL_PTR(nright, ll->loc_next);
-cx_linked_list_node *midstart = nleft->next;
+void *midstart = CX_LL_PTR(nleft, ll->loc_next);
-cx_linked_list_node *midend = nright->prev;
+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;
+CX_LL_PTR(nright, ll->loc_next) = nleft;
-nleft->prev = nright;
+CX_LL_PTR(nleft, ll->loc_prev) = nright;
 } else {
 // likely case: a chain is between the two nodes
-nright->next = midstart;
+CX_LL_PTR(nright, ll->loc_next) = midstart;
-midstart->prev = nright;
+CX_LL_PTR(midstart, ll->loc_prev) = nright;
-midend->next = nleft;
+CX_LL_PTR(midend, ll->loc_next) = nleft;
-nleft->prev = midend;
+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;
 }
 static void *cx_ll_at(
 const struct cx_list_s *list,
 size_t index
 ) {
 cx_linked_list *ll = (cx_linked_list *) list;
-cx_linked_list_node *node = cx_ll_node_at(ll, index);
+char *node = cx_ll_node_at(ll, index);
-return node == NULL ? NULL : node->payload;
+return node == NULL ? NULL : node + ll->loc_data;
 }
 static size_t cx_ll_find_remove(
 struct cx_list_s *list,
 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 *ll = (cx_linked_list *) list;
-cx_linked_list_node *node = cx_linked_list_find(
+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
 );
 if (node == NULL) {
 return list->collection.size;
 }
 if (remove) {
-cx_invoke_destructor(list, node->payload);
+cx_invoke_destructor(list, node + ll->loc_data);
-cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
+cx_linked_list_remove(&ll->begin, &ll->end,
-CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
+ll->loc_prev, ll->loc_next, node);
 list->collection.size--;
 cxFree(list->collection.allocator, node);
 }
 return index;
 }
 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_linked_list_sort(&ll->begin, &ll->end,
-CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+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(
 const struct cx_list_s *list,
 const struct cx_list_s *other
 ) {
 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);
 }
 static bool cx_ll_iter_valid(const void *it) {
 const struct cx_iterator_s *iter = it;
 return iter->elem_handle != NULL;
 }
 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;
+struct cx_list_s *list = iter->src_handle;
-cx_linked_list *ll = iter->src_handle.m;
+char *node = iter->elem_handle;
-cx_linked_list_node *node = iter->elem_handle;
+iter->elem_handle = CX_LL_PTR(node, ll->loc_next);
-iter->elem_handle = node->next;
+cx_invoke_destructor(list, node + ll->loc_data);
-cx_invoke_destructor(list, node->payload);
+cx_linked_list_remove(&ll->begin, &ll->end,
-cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
+ll->loc_prev, ll->loc_next, node);
-CX_LL_LOC_PREV, CX_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;
+void *node = iter->elem_handle;
-iter->elem_handle = node->next;
+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;
+struct cx_list_s *list = iter->src_handle;
-cx_linked_list *ll = iter->src_handle.m;
+char *node = iter->elem_handle;
-cx_linked_list_node *node = iter->elem_handle;
+iter->elem_handle = CX_LL_PTR(node, ll->loc_prev);
-iter->elem_handle = node->prev;
 iter->index--;
-cx_invoke_destructor(list, node->payload);
+cx_invoke_destructor(list, node + ll->loc_data);
-cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
+cx_linked_list_remove(&ll->begin, &ll->end,
-CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
+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;
+char *node = iter->elem_handle;
-iter->elem_handle = node->prev;
+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;
+const cx_linked_list *ll = iter->src_handle;
-return node->payload;
+char *node = iter->elem_handle;
+return node + ll->loc_data;
 }
 static CxIterator cx_ll_iterator(
 const struct cx_list_s *list,
 size_t index,
 bool backwards
 ) {
 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;
 }
 static int cx_ll_insert_iter(
 CxIterator *iter,
 const void *elem,
 int prepend
 ) {
-struct cx_list_s *list = iter->src_handle.m;
+struct cx_list_s *list = iter->src_handle;
-cx_linked_list_node *node = iter->elem_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++;
 if (prepend) {
 iter->index++;
 }
 }
 return result;
 } else {
-int result = cx_ll_insert_element(list, list->collection.size, elem);
+if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) {
-if (result == 0) {
+return 1;
-iter->elem_count++;
+}
-iter->index = list->collection.size;
+iter->elem_count++;
-}
+iter->index = list->collection.size;
-return result;
+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);
+cx_invoke_destructor(list, node + ll->loc_data);
-void *next = node->next;
+void *next = CX_LL_PTR(node, ll->loc_next);
 cxFree(list->collection.allocator, node);
 node = next;
 }
 cxFree(list->collection.allocator, list);
 static cx_list_class cx_linked_list_class = {
 cx_ll_destructor,
 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,
 cx_ll_swap,
 cx_ll_at,
 allocator = cxDefaultAllocator;
 }
 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);
 return (CxList *) list;
 }

comparison: ucx/linked_list.c

ucx/linked_list.c

Mercurial > hg > dav / file comparison

comparison: ucx/linked_list.c

ucx/linked_list.c