changeset
add functions to insert elements into lists/arrays without duplicates - resolves #557
Fri, 10 Oct 2025 17:24:19 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Fri, 10 Oct 2025 17:24:19 +0200
- changeset 1419
- e46406fd1b3c
- parent 1418
- 5e1579713bcf
- child 1420
- c6f55a2b3495
add functions to insert elements into lists/arrays without duplicates - resolves #557
--- a/CHANGELOG Fri Oct 10 12:26:43 2025 +0200 +++ b/CHANGELOG Fri Oct 10 17:24:19 2025 +0200 @@ -11,6 +11,9 @@ * adds cxListRemoveAndGetFirst() and cxListRemoveAndGetLast(), and corresponding macro aliases cxListPopFront() and cxListPop() * adds cxListEmplace(), cxListEmplaceAt(), and cxMapEmplace() + * adds cxListInsertUnique() and cxListInsertUniqueArray() + * adds cx_array_insert_unique() and various convenience macros + * adds cx_linked_list_insert_unique() and cx_linked_list_insert_unique_chain() * adds cxBufferShrink() * adds cxTreeSize() * adds CX_PRIstr and CX_SFMT macros for formatting UCX strings @@ -26,6 +29,7 @@ * changes all cxListIterator() and cxMapIterator() family of functions to also accept NULL as argument * changes insert_element member function of CxList to accept NULL source and return a pointer to the inserted element * fixes critical memory overflow in the stack-based array reallocator (this unfortunately breaks the function signature) + * fixes critical bug in cx_array_insert_sorted() that caused an infinite loop when inserting duplicates * fixes mempool implementation not supporting NULL as argument for realloc * fixes mempool implementation not supporting zero as size for realloc * fixes that the elem_count member of an iterator was not updated after removing an element flagged by cxIteratorFlagRemoval()
--- a/docs/Writerside/topics/about.md Fri Oct 10 12:26:43 2025 +0200 +++ b/docs/Writerside/topics/about.md Fri Oct 10 17:24:19 2025 +0200 @@ -38,6 +38,9 @@ * adds cxListRemoveAndGetFirst() and cxListRemoveAndGetLast(), and corresponding macro aliases cxListPopFront() and cxListPop() * adds cxListEmplace(), cxListEmplaceAt(), and cxMapEmplace() +* adds cxListInsertUnique() and cxListInsertUniqueArray() +* adds cx_array_insert_unique() and various convenience macros +* adds cx_linked_list_insert_unique() and cx_linked_list_insert_unique_chain() * adds cxBufferShrink() * adds cxTreeSize() * adds CX_PRIstr and CX_SFMT macros for formatting UCX strings @@ -53,6 +56,7 @@ * changes all cxListIterator() and cxMapIterator() family of functions to also accept NULL as argument * changes insert_element member function of CxList to accept NULL source and return a pointer to the inserted element * fixes critical memory overflow in the stack-based array reallocator (this unfortunately breaks the function signature) +* fixes critical bug in cx_array_insert_sorted() that caused an infinite loop when inserting duplicates * fixes mempool implementation not supporting NULL as argument for realloc * fixes mempool implementation not supporting zero as size for realloc * fixes that the elem_count member of an iterator was not updated after removing an element flagged by cxIteratorFlagRemoval()
--- a/docs/Writerside/topics/array_list.h.md Fri Oct 10 12:26:43 2025 +0200 +++ b/docs/Writerside/topics/array_list.h.md Fri Oct 10 17:24:19 2025 +0200 @@ -217,6 +217,8 @@ ## Insertion Sort ```C +#include <cx/array_list.h> + int cx_array_insert_sorted( void **target, size_t *size, size_t *capacity, cx_compare_func cmp_func, @@ -251,6 +253,36 @@ The convenience macros are all calling `cx_array_insert_sorted()` by deducing the missing arguments. The `cx_array_add_sorted()` family of macros are interpreting the `elem` as a `src` array with an `elem_count` of one. +## Sets of Unique Elements + +```C +#include <cx/array_list.h> + +int cx_array_insert_unique( + void **target, size_t *size, size_t *capacity, + cx_compare_func cmp_func, + const void *src, size_t elem_size, size_t elem_count, + CxArrayReallocator *reallocator); + +#define cx_array_simple_insert_unique(ARRAY, + src, elem_count, cmp_func) + +#define cx_array_simple_insert_unique_a(reallocator, ARRAY, + src, elem_count, cmp_func) + +#define cx_array_add_unique(target, size, capacity, + elem_size, elem, cx_compare_func cmp_func, reallocator); + +#define cx_array_simple_add_unique(ARRAY, + elem, cmp_func) + +#define cx_array_simple_add_unique_a(reallocator, ARRAY, + elem, cmp_func) +``` + +The above functions are similar to `cx_array_insert_sorted()` and its [relatives](#insertion-sort), +except that they skip insertion of elements that are already present in the target array. + ## Binary Search ```C
--- a/docs/Writerside/topics/linked_list.h.md Fri Oct 10 12:26:43 2025 +0200 +++ b/docs/Writerside/topics/linked_list.h.md Fri Oct 10 17:24:19 2025 +0200 @@ -115,6 +115,14 @@ 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); + +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); + +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); ``` The above functions can be used to insert one or more elements into a linked list. @@ -136,6 +144,12 @@ except that `begin` and `loc_next` are always required, and the target list must already be sorted. The order is determined by the `cmp_func` to which the pointers to the nodes are passed. +The functions `cx_linked_list_insert_unique()` and `cx_linked_list_insert_unique_chain()` are similar to +`cx_linked_list_insert_sorted()` and `cx_linked_list_insert_sorted_chain()`, except that they only insert the node +if it is not already contained in the list. +When a duplicate is found, `cx_linked_list_insert_unique()` returns non-zero and `cx_linked_list_insert_unique_chain()` +returns a pointer to a new chain starting with the first node that was not inserted. + > The `cx_linked_list_insert_sorted_chain()` function does not have an `insert_end` argument, because > it cannot take advantage of simply inserting the entire chain as-is, as the chain might need to be broken > to maintain the sort order.
--- a/docs/Writerside/topics/list.h.md Fri Oct 10 12:26:43 2025 +0200 +++ b/docs/Writerside/topics/list.h.md Fri Oct 10 17:24:19 2025 +0200 @@ -122,6 +122,8 @@ int cxListInsertSorted(CxList *list, const void *elem); +int cxListInsertUnique(CxList *list, const void *elem); + size_t cxListAddArray(CxList *list, const void *array, size_t n); size_t cxListInsertArray(CxList *list, size_t index, @@ -130,6 +132,9 @@ size_t cxListInsertSortedArray(CxList *list, const void *array, size_t n); +size_t cxListInsertUniqueArray(CxList *list, + const void *array, size_t n); + int cxListInsertAfter(CxIterator *iter, const void *elem); int cxListInsertBefore(CxIterator *iter, const void *elem); @@ -143,6 +148,7 @@ Be aware that when the list is storing pointers, the allocated memory will be for the pointer, not the actual element's data. The function `cxListInsertSorted()` inserts the element at the correct position so that the list remains sorted according to the list's compare function. +On top of that, `cxListInsertUnique()` inserts the element only if it is not already in the list. When you are currently iterating through a list, you can insert elements before or after the current position of the iterator with `cxListInsertBefore()` or `cxListInsertAfter()`, respectively. @@ -151,15 +157,20 @@ If the list is storing pointers (cf. `cxCollectionStoresPointers()`), the pointer `elem` is directly added to the list. Otherwise, the contents at the location pointed to by `elem` are copied to the list's memory with the element size specified during creation of the list. -On the other hand, the `array` argument for `cxListAddArray()`, `cxListInsertArray()`, and `cxListInsertSortedArray()` +On the other hand, the `array` argument for `cxListAddArray()`, `cxListInsertArray()`, `cxListInsertSortedArray()`, and `cxListInsertUniqueArray()` must always point to an array of elements to be added (i.e., either an array of pointers or an array of actual elements). -A special requirement for `cxListInsertSortedArray()` is, that the `array` must already be sorted. +When calling `cxListInsertSortedArray()` or `cxListInsertUniqueArray()`, the `array` must already be sorted. + +The return values of the array-inserting functions are the number of elements that have been successfully _processed_. +Usually this is equivalent to the number of inserted elements, except for `cxListInsertUniqueArray()`, +where the actual number of inserted elements may be less than the number of successfully processed elements. > Implementations are required to optimize the insertion of a sorted array into a sorted list in linear time, > while inserting each element separately via `cxListInsertSorted()` may take quadratic time. -> The functions `cxListInsertSorted()` and `cxListInsertSortedArray()` do neither check if the list is already sorted, nor do they actively sort the list. +> The functions do not check if the list is already sorted, nor do they actively sort the list. +> In debug builds, invoking the functions on unsorted lists may trigger an assertion. > {style="note"} ## Access and Find
--- a/src/array_list.c Fri Oct 10 12:26:43 2025 +0200 +++ b/src/array_list.c Fri Oct 10 17:24:19 2025 +0200 @@ -335,7 +335,7 @@ return 0; } -int cx_array_insert_sorted( +static int cx_array_insert_sorted_impl( void **target, size_t *size, size_t *capacity, @@ -343,7 +343,8 @@ const void *sorted_data, size_t elem_size, size_t elem_count, - CxArrayReallocator *reallocator + CxArrayReallocator *reallocator, + bool allow_duplicates ) { // assert pointers assert(target != NULL); @@ -369,6 +370,7 @@ // store some counts size_t old_size = *size; size_t old_capacity = *capacity; + // the necessary capacity is the worst case assumption, including duplicates size_t needed_capacity = old_size + elem_count; // if we need more than we have, try a reallocation @@ -418,6 +420,16 @@ bptr, cmp_func ); + // handle the identical elements + size_t skip_len = 0; + while (copy_len < elem_count - si + && cmp_func(bptr, src+copy_len*elem_size) == 0) { + copy_len++; + if (!allow_duplicates) { + skip_len++; + } + } + copy_len -= skip_len; // copy the source elements bytes_copied = copy_len * elem_size; @@ -425,6 +437,12 @@ dest += bytes_copied; src += bytes_copied; si += copy_len; + di += copy_len; + + // skip duplicates when they are not allowed + src += skip_len * elem_size; + si += skip_len; + *size -= skip_len; // when all source elements are in place, we are done if (si >= elem_count) break; @@ -443,7 +461,18 @@ memmove(dest, bptr, bytes_copied); dest += bytes_copied; bptr += bytes_copied; + di += copy_len; bi += copy_len; + + // check if the last restored element is a duplicate of the next source + if (!allow_duplicates && copy_len > 0) { + char *last = dest - elem_size; + while (si < elem_count && cmp_func(last, src) == 0) { + src += elem_size; + si++; + (*size)--; + } + } } // still source elements left? simply append them @@ -451,12 +480,44 @@ memcpy(dest, src, elem_size * (elem_count - si)); } - // still buffer elements left? - // don't worry, we already moved them to the correct place + // buffered elements need to be moved when we skipped duplicates + size_t total_skipped = new_size - *size; + if (bi < new_size && total_skipped > 0) { + // move the remaining buffer to the end of the array + memmove(dest, bptr, elem_size * (new_size - bi)); + } return 0; } +int cx_array_insert_sorted( + void **target, + size_t *size, + size_t *capacity, + cx_compare_func cmp_func, + const void *sorted_data, + size_t elem_size, + size_t elem_count, + CxArrayReallocator *reallocator +) { + return cx_array_insert_sorted_impl(target, size, capacity, + cmp_func, sorted_data, elem_size, elem_count, reallocator, true); +} + +int cx_array_insert_unique( + void **target, + size_t *size, + size_t *capacity, + cx_compare_func cmp_func, + const void *sorted_data, + size_t elem_size, + size_t elem_count, + CxArrayReallocator *reallocator +) { + return cx_array_insert_sorted_impl(target, size, capacity, + cmp_func, sorted_data, elem_size, elem_count, reallocator, false); +} + size_t cx_array_binary_search_inf( const void *arr, size_t size, @@ -502,6 +563,13 @@ result = cmp_func(elem, arr_elem); if (result == 0) { // found it! + // check previous elements; + // when they are equal, report the smallest index + arr_elem -= elem_size; + while (pivot_index > 0 && cmp_func(elem, arr_elem) == 0) { + pivot_index--; + arr_elem -= elem_size; + } return pivot_index; } else if (result < 0) { // element is smaller than pivot, continue search left @@ -700,6 +768,31 @@ } } +static size_t cx_arl_insert_unique( + struct cx_list_s *list, + const void *sorted_data, + size_t n +) { + // get a correctly typed pointer to the list + cx_array_list *arl = (cx_array_list *) list; + + if (cx_array_insert_unique( + &arl->data, + &list->collection.size, + &arl->capacity, + list->collection.cmpfunc, + sorted_data, + list->collection.elem_size, + n, + &arl->reallocator + )) { + // array list implementation is "all or nothing" + return 0; + } else { + return n; + } +} + static void *cx_arl_insert_element( struct cx_list_s *list, size_t index, @@ -993,6 +1086,7 @@ cx_arl_insert_element, cx_arl_insert_array, cx_arl_insert_sorted, + cx_arl_insert_unique, cx_arl_insert_iter, cx_arl_remove, cx_arl_clear,
--- a/src/cx/array_list.h Fri Oct 10 12:26:43 2025 +0200 +++ b/src/cx/array_list.h Fri Oct 10 17:24:19 2025 +0200 @@ -586,6 +586,136 @@ #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \ cx_array_simple_insert_sorted_a(NULL, array, src, n, cmp_func) + +/** + * Inserts a sorted array into another sorted array, avoiding duplicates. + * + * If either the target or the source array is not already sorted with respect + * to the specified @p cmp_func, the behavior is undefined. + * Also, the @p src array must not contain duplicates within itself. + * + * If the capacity is insufficient to hold the new data, a reallocation + * attempt is made. + * You can create your own reallocator by hand, use #cx_array_default_reallocator, + * or use the convenience function cx_array_reallocator() to create a custom reallocator. + * + * @param target a pointer to the target array + * @param size a pointer to the size of the target array + * @param capacity a pointer to the capacity of the target array + * @param cmp_func the compare function for the elements + * @param src the source array + * @param elem_size the size of one element + * @param elem_count the number of elements to insert + * @param reallocator the array reallocator to use + * (@c NULL defaults to #cx_array_default_reallocator) + * @retval zero success + * @retval non-zero failure + */ +cx_attr_nonnull_arg(1, 2, 3, 5) +cx_attr_export +int cx_array_insert_unique( + void **target, + size_t *size, + size_t *capacity, + cx_compare_func cmp_func, + const void *src, + size_t elem_size, + size_t elem_count, + CxArrayReallocator *reallocator +); + +/** + * Inserts an element into a sorted array if it does not exist. + * + * If the target array is not already sorted with respect + * to the specified @p cmp_func, the behavior is undefined. + * + * If the capacity is insufficient to hold the new data, a reallocation + * attempt is made. + * + * The \@ SIZE_TYPE is flexible and can be any unsigned integer type. + * It is important, however, that @p size and @p capacity are pointers to + * variables of the same type. + * + * @param target (@c void**) a pointer to the target array + * @param size (@c SIZE_TYPE*) a pointer to the size of the target array + * @param capacity (@c SIZE_TYPE*) a pointer to the capacity of the target array + * @param elem_size (@c size_t) the size of one element + * @param elem (@c void*) a pointer to the element to add + * @param cmp_func (@c cx_cmp_func) the compare function for the elements + * @param reallocator (@c CxArrayReallocator*) the array reallocator to use + * @retval zero success (also when the element was already present) + * @retval non-zero failure + */ +#define cx_array_add_unique(target, size, capacity, elem_size, elem, cmp_func, reallocator) \ + cx_array_insert_unique((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator) + +/** + * Convenience macro for cx_array_add_unique() with a default + * layout and the specified reallocator. + * + * @param reallocator (@c CxArrayReallocator*) the array reallocator to use + * @param array the name of the array (NOT a pointer or alias to the array) + * @param elem the element to add (NOT a pointer, address is automatically taken) + * @param cmp_func (@c cx_cmp_func) the compare function for the elements + * @retval zero success + * @retval non-zero failure + * @see CX_ARRAY_DECLARE() + * @see cx_array_simple_add_unique() + */ +#define cx_array_simple_add_unique_a(reallocator, array, elem, cmp_func) \ + cx_array_add_unique(&array, &(array##_size), &(array##_capacity), \ + sizeof((array)[0]), &(elem), cmp_func, reallocator) + +/** + * Convenience macro for cx_array_add_unique() with a default + * layout and the default reallocator. + * + * @param array the name of the array (NOT a pointer or alias to the array) + * @param elem the element to add (NOT a pointer, address is automatically taken) + * @param cmp_func (@c cx_cmp_func) the compare function for the elements + * @retval zero success + * @retval non-zero failure + * @see CX_ARRAY_DECLARE() + * @see cx_array_simple_add_unique_a() + */ +#define cx_array_simple_add_unique(array, elem, cmp_func) \ + cx_array_simple_add_unique_a(NULL, array, elem, cmp_func) + +/** + * Convenience macro for cx_array_insert_unique() with a default + * layout and the specified reallocator. + * + * @param reallocator (@c CxArrayReallocator*) the array reallocator to use + * @param array the name of the array (NOT a pointer or alias to the array) + * @param src (@c void*) pointer to the source array + * @param n (@c size_t) number of elements in the source array + * @param cmp_func (@c cx_cmp_func) the compare function for the elements + * @retval zero success + * @retval non-zero failure + * @see CX_ARRAY_DECLARE() + * @see cx_array_simple_insert_unique() + */ +#define cx_array_simple_insert_unique_a(reallocator, array, src, n, cmp_func) \ + cx_array_insert_unique((void**)(&array), &(array##_size), &(array##_capacity), \ + cmp_func, src, sizeof((array)[0]), n, reallocator) + +/** + * Convenience macro for cx_array_insert_unique() with a default + * layout and the default reallocator. + * + * @param array the name of the array (NOT a pointer or alias to the array) + * @param src (@c void*) pointer to the source array + * @param n (@c size_t) number of elements in the source array + * @param cmp_func (@c cx_cmp_func) the compare function for the elements + * @retval zero success + * @retval non-zero failure + * @see CX_ARRAY_DECLARE() + * @see cx_array_simple_insert_unique_a() + */ +#define cx_array_simple_insert_unique(array, src, n, cmp_func) \ + cx_array_simple_insert_unique_a(NULL, array, src, n, cmp_func) + /** * Searches the largest lower bound in a sorted array. *
--- a/src/cx/linked_list.h Fri Oct 10 12:26:43 2025 +0200 +++ b/src/cx/linked_list.h Fri Oct 10 17:24:19 2025 +0200 @@ -387,7 +387,7 @@ /** * Inserts a chain of nodes into a sorted linked list. - * The chain must not be part of any list already. + * The chain must not be part of any list yet. * * If either the list starting with the node pointed to by @p begin or the list * starting with @p insert_begin is not sorted, the behavior is undefined. @@ -416,6 +416,64 @@ ); /** + * Inserts a node into a sorted linked list if no other node with the same value already exists. + * The new node must not be part of any list yet. + * + * If the list starting with the node pointed to by @p begin is not sorted + * already, the behavior is undefined. + * + * @param begin a pointer to the beginning node pointer (required) + * @param end a pointer to the end node pointer (if your list has one) + * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) + * @param loc_next the location of a @c next pointer within your node struct (required) + * @param new_node a pointer to the node that shall be inserted + * @param cmp_func a compare function that will receive the node pointers + * @retval zero when the node was inserted + * @retval non-zero when a node with the same value already exists + */ +cx_attr_nonnull_arg(1, 5, 6) +cx_attr_export +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 +); + +/** + * Inserts a chain of nodes into a sorted linked list, avoiding duplicates. + * The chain must not be part of any list yet. + * + * If either the list starting with the node pointed to by @p begin or the list + * starting with @p insert_begin is not sorted, the behavior is undefined. + * Also, the chain to be inserted must not contain duplicates within itself. + * + * @attention In contrast to cx_linked_list_insert_sorted(), not all nodes of the + * chain might be added. This function returns a new chain consisting of all the duplicates. + * + * @param begin a pointer to the beginning node pointer (required) + * @param end a pointer to the end node pointer (if your list has one) + * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) + * @param loc_next the location of a @c next pointer within your node struct (required) + * @param insert_begin a pointer to the first node of the chain that shall be inserted + * @param cmp_func a compare function that will receive the node pointers + * @return a pointer to a new chain with all duplicates which were not inserted (or @c NULL when there were no duplicates) + */ +cx_attr_nonnull_arg(1, 5, 6) +cx_attr_nodiscard +cx_attr_export +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 +); + +/** * Removes a chain of nodes from the linked list. * * If one of the nodes to remove is the beginning (resp. end) node of the list and if @p begin (resp. @p end)
--- a/src/cx/list.h Fri Oct 10 12:26:43 2025 +0200 +++ b/src/cx/list.h Fri Oct 10 17:24:19 2025 +0200 @@ -115,6 +115,17 @@ ); /** + * Member function for inserting multiple elements if they do not exist. + * + * @see cx_list_default_insert_unique() + */ + size_t (*insert_unique)( + struct cx_list_s *list, + const void *sorted_data, + size_t n + ); + + /** * Member function for inserting an element relative to an iterator position. */ int (*insert_iter)( @@ -269,6 +280,31 @@ ); /** + * Default implementation of an array insert where only elements are inserted when they don't exist in the list. + * + * This function is similar to cx_list_default_insert_sorted(), except it skips elements that are already in the list. + * The @p sorted_data itself must not contain duplicates. + * + * @note The return value of this function denotes the number of elements from the @p sorted_data that are definitely + * contained in the list after completing the call. It is @em not the number of elements that were newly inserted. + * That means, when no error occurred, the return value should be @p n. + * + * Use this in your own list class if you do not want to implement an optimized version for your list. + * + * @param list the list + * @param sorted_data a pointer to the array of pre-sorted data to insert + * @param n the number of elements to insert + * @return the number of elements from the @p sorted_data that are definitely present in the list after this call + */ +cx_attr_nonnull +cx_attr_export +size_t cx_list_default_insert_unique( + struct cx_list_s *list, + const void *sorted_data, + size_t n +); + +/** * Default unoptimized sort implementation. * * This function will copy all data to an array, sort the array with standard @@ -490,6 +526,27 @@ } /** + * Inserts an item into a sorted list if it does not exist. + * + * If the list is not sorted already, the behavior is undefined. + * + * @param list the list + * @param elem a pointer to the element to add + * @retval zero success (also when the element was already in the list) + * @retval non-zero memory allocation failure + */ +cx_attr_nonnull +static inline int cxListInsertUnique( + CxList *list, + const void *elem +) { + assert(list->collection.sorted || list->collection.size == 0); + list->collection.sorted = true; + const void *data = list->collection.store_pointer ? &elem : elem; + return list->cl->insert_unique(list, data, 1) == 0; +} + +/** * Inserts multiple items to the list at the specified index. * If @p index equals the list size, this is effectively cxListAddArray(). * @@ -522,7 +579,7 @@ /** * Inserts a sorted array into a sorted list. * - * This method is usually more efficient than inserting each element separately, + * This method is usually more efficient than inserting each element separately * because consecutive chunks of sorted data are inserted in one pass. * * If there is not enough memory to add all elements, the returned value is @@ -550,6 +607,45 @@ } /** + * Inserts a sorted array into a sorted list, skipping duplicates. + * + * This method is usually more efficient than inserting each element separately + * because consecutive chunks of sorted data are inserted in one pass. + * + * If there is not enough memory to add all elements, the returned value is + * less than @p n. + * + * @note The return value of this function denotes the number of elements + * from the @p sorted_data that are definitely contained in the list after + * completing the call. It is @em not the number of elements that were newly + * inserted. That means, when no error occurred, the return value should + * be @p n. + * + * If this list is storing pointers instead of objects @p array is expected to + * be an array of pointers. + * + * If the list is not sorted already, the behavior is undefined. + * This is also the case when the @p array is not sorted or already contains duplicates. + * + * @param list the list + * @param array a pointer to the elements to add + * @param n the number of elements to add + * @return the number of added elements + * + * @return the number of elements from the @p sorted_data that are definitely present in the list after this call + */ +cx_attr_nonnull +static inline size_t cxListInsertUniqueArray( + CxList *list, + const void *array, + size_t n +) { + assert(list->collection.sorted || list->collection.size == 0); + list->collection.sorted = true; + return list->cl->insert_unique(list, array, n); +} + +/** * Inserts an element after the current location of the specified iterator. * * The used iterator remains operational, but all other active iterators should
--- a/src/kv_list.c Fri Oct 10 12:26:43 2025 +0200 +++ b/src/kv_list.c Fri Oct 10 17:24:19 2025 +0200 @@ -138,6 +138,15 @@ return kv_list->list_methods->insert_sorted(list, sorted_data, n); } +static size_t cx_kvl_insert_unique( + struct cx_list_s *list, + const void *sorted_data, + size_t n +) { + cx_kv_list *kv_list = (cx_kv_list*)list; + return kv_list->list_methods->insert_unique(list, sorted_data, n); +} + static int cx_kvl_insert_iter( struct cx_iterator_s *iter, const void *elem, @@ -503,6 +512,7 @@ cx_kvl_insert_element, cx_kvl_insert_array, cx_kvl_insert_sorted, + cx_kvl_insert_unique, cx_kvl_insert_iter, cx_kvl_remove, cx_kvl_clear,
--- a/src/linked_list.c Fri Oct 10 12:26:43 2025 +0200 +++ b/src/linked_list.c Fri Oct 10 17:24:19 2025 +0200 @@ -30,6 +30,7 @@ #include "cx/compare.h" #include <string.h> #include <assert.h> +#include <unistd.h> // LOW LEVEL LINKED LIST FUNCTIONS @@ -244,19 +245,22 @@ 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 + void *dup_start = NULL; + void *dup_last = NULL; void *dest_prev = NULL; void *dest = *begin; void *src = insert_begin; @@ -267,17 +271,38 @@ if (end != NULL) { *end = cx_linked_list_last(src, loc_next); } - return; + return NULL; } // 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; + { + int d = cmp_func(dest, src); + if (d <= 0) { + if (!allow_duplicates && d == 0) { + if (dup_last == NULL) { + dup_start = src; + dup_last = src; + if (loc_prev >= 0) { + ll_prev(dup_start) = NULL; + } + } else { + cx_linked_list_link(dup_last, src, loc_prev, loc_next); + dup_last = src; + } + src = ll_next(src); + while (src != NULL && cmp_func(dest, src) == 0) { + dup_last = src; + src = ll_next(src); + } + } + + dest_prev = dest; + dest = ll_next(dest); + continue; + } } // determine chain of elements that can be inserted @@ -308,6 +333,27 @@ dest = ll_next(dest); } + // skip duplicates in the remaining items + if (!allow_duplicates && src != NULL) { + if (cmp_func(dest_prev, src) == 0) { + if (dup_last == NULL) { + dup_start = src; + dup_last = src; + if (loc_prev >= 0) { + ll_prev(dup_start) = NULL; + } + } else { + cx_linked_list_link(dup_last, src, loc_prev, loc_next); + dup_last = src; + } + src = ll_next(src); + while (src != NULL && cmp_func(dest_prev, src) == 0) { + dup_last = src; + src = ll_next(src); + } + } + } + // insert remaining items if (src != NULL) { cx_linked_list_link(dest_prev, src, loc_prev, loc_next); @@ -318,6 +364,51 @@ *end = cx_linked_list_last( dest != NULL ? dest : dest_prev, loc_next); } + + if (dup_last != NULL) { + ll_next(dup_last) = NULL; + } + return dup_start; +} + +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 +) { + void *ret = cx_linked_list_insert_sorted_chain_impl( + begin, end, loc_prev, loc_next, + insert_begin, cmp_func, true); + assert(ret == NULL); +} + +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( @@ -677,10 +768,11 @@ return cx_ll_insert_sorted_cmp_func(left, right); } -static size_t cx_ll_insert_sorted( +static size_t cx_ll_insert_sorted_impl( struct cx_list_s *list, const void *array, - size_t n + size_t n, + bool allow_duplicates ) { cx_linked_list *ll = (cx_linked_list *) list; @@ -711,21 +803,54 @@ // invoke the low level function cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; cx_ll_insert_sorted_loc_data = ll->loc_data; - cx_linked_list_insert_sorted_chain( - &ll->begin, - &ll->end, - ll->loc_prev, - ll->loc_next, - chain, - cx_ll_insert_sorted_cmp_helper - ); - - // adjust the list metadata - list->collection.size += inserted; + 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 +) { + return cx_ll_insert_sorted_impl(list, array, n, true); +} + +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( struct cx_list_s *list, size_t index, @@ -1094,6 +1219,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,
--- a/src/list.c Fri Oct 10 12:26:43 2025 +0200 +++ b/src/list.c Fri Oct 10 17:24:19 2025 +0200 @@ -90,6 +90,17 @@ return result; } +static size_t cx_pl_insert_unique( + struct cx_list_s *list, + const void *array, + size_t n +) { + cx_pl_hack_cmpfunc(list); + size_t result = list->climpl->insert_unique(list, array, n); + cx_pl_unhack_cmpfunc(list); + return result; +} + static int cx_pl_insert_iter( struct cx_iterator_s *iter, const void *elem, @@ -181,6 +192,7 @@ cx_pl_insert_element, cx_pl_insert_array, cx_pl_insert_sorted, + cx_pl_insert_unique, cx_pl_insert_iter, cx_pl_remove, cx_pl_clear, @@ -238,6 +250,7 @@ NULL, NULL, NULL, + NULL, cx_emptyl_noop, NULL, cx_emptyl_at, @@ -289,10 +302,11 @@ return i; } -size_t cx_list_default_insert_sorted( +static size_t cx_list_default_insert_sorted_impl( struct cx_list_s *list, const void *sorted_data, - size_t n + size_t n, + bool allow_duplicates ) { // corner case if (n == 0) return 0; @@ -310,8 +324,22 @@ // compare current list element with first source element // if less or equal, skip - if (cmp(list_elm, src) <= 0) { - continue; + { + int d = cmp(list_elm, src); + if (d <= 0) { + if (!allow_duplicates && d == 0) { + src += elem_size; + si++; + inserted++; // we also count duplicates for the return value + while (si < n && cmp(list_elm, src) == 0) { + src += elem_size; + si++; + inserted++; + } + if (inserted == n) return inserted; + } + continue; + } } // determine number of consecutive elements that can be inserted @@ -351,6 +379,22 @@ return inserted; } +size_t cx_list_default_insert_sorted( + struct cx_list_s *list, + const void *sorted_data, + size_t n +) { + return cx_list_default_insert_sorted_impl(list, sorted_data, n, true); +} + +size_t cx_list_default_insert_unique( + struct cx_list_s *list, + const void *sorted_data, + size_t n +) { + return cx_list_default_insert_sorted_impl(list, sorted_data, n, false); +} + void cx_list_default_sort(struct cx_list_s *list) { size_t elem_size = list->collection.elem_size; size_t list_size = list->collection.size;
--- a/tests/test_list.c Fri Oct 10 12:26:43 2025 +0200 +++ b/tests/test_list.c Fri Oct 10 17:24:19 2025 +0200 @@ -171,9 +171,11 @@ int d6a[6] = {52, 54, 56, 62, 64, 75}; int d7a[6] = {51, 57, 58, 65, 77, 78}; int d8 = 90; - int expected[18] = { - 40, 50, 51, 52, 54, 56, 57, 58, 60, - 62, 64, 65, 70, 75, 77, 78, 80, 90 + int d9 = 56; + int d10a[3] = {67, 75, 90}; + int expected[22] = { + 40, 50, 51, 52, 54, 56, 56, 57, 58, 60, + 62, 64, 65, 67, 70, 75, 75, 77, 78, 80, 90, 90 }; CX_ARRAY_DECLARE(int, array); @@ -204,8 +206,70 @@ CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d8, cx_cmp_int)); CX_TEST_ASSERT(array_size == 18); CX_TEST_ASSERT(array_capacity >= 18); + CX_TEST_ASSERT(0 == cx_array_simple_add_sorted(array, d9, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 19); + CX_TEST_ASSERT(array_capacity >= 19); + CX_TEST_ASSERT(0 == cx_array_simple_insert_sorted(array, d10a, 3, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 22); + CX_TEST_ASSERT(array_capacity >= 22); - CX_TEST_ASSERT(0 == memcmp(array, expected, 18 * sizeof(int))); + CX_TEST_ASSERT(0 == memcmp(array, expected, 22 * sizeof(int))); + } + cxFreeDefault(array); +} + +CX_TEST(test_array_insert_unique) { + int d1 = 50; + int d2 = 80; + int d3 = 60; + int d4 = 40; + int d5 = 70; + int d6a[6] = {52, 54, 56, 62, 64, 75}; + int d7a[6] = {51, 57, 58, 65, 77, 78}; + int d8 = 90; + int d9 = 56; + int d10a[3] = {67, 75, 90}; + int expected[19] = { + 40, 50, 51, 52, 54, 56, 57, 58, 60, + 62, 64, 65, 67, 70, 75, 77, 78, 80, 90 + }; + + CX_ARRAY_DECLARE(int, array); + cx_array_initialize(array, 4); + + CX_TEST_DO { + CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d1, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 1); + CX_TEST_ASSERT(array_capacity == 4); + CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d2, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 2); + CX_TEST_ASSERT(array_capacity == 4); + CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d3, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 3); + CX_TEST_ASSERT(array_capacity == 4); + CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d4, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 4); + CX_TEST_ASSERT(array_capacity == 4); + CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d5, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 5); + CX_TEST_ASSERT(array_capacity >= 5); + CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d6a, 6, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 11); + CX_TEST_ASSERT(array_capacity >= 11); + CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d7a, 6, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 17); + CX_TEST_ASSERT(array_capacity >= 17); + CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d8, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 18); + CX_TEST_ASSERT(array_capacity >= 18); + CX_TEST_ASSERT(0 == cx_array_simple_add_unique(array, d9, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 18); + CX_TEST_ASSERT(array_capacity >= 18); + CX_TEST_ASSERT(0 == cx_array_simple_insert_unique(array, d10a, 3, cx_cmp_int)); + CX_TEST_ASSERT(array_size == 19); + CX_TEST_ASSERT(array_capacity >= 19); + + CX_TEST_ASSERT(0 == memcmp(array, expected, 19 * sizeof(int))); } cxFreeDefault(array); } @@ -737,6 +801,121 @@ } } +CX_TEST(test_linked_list_insert_unique) { + node nodes[5] = {0}; + void *begin, *end; + nodes[0].data = 3; + nodes[1].data = 6; + nodes[2].data = 10; + nodes[3].data = 11; + nodes[4].data = 15; + for (unsigned i = 0 ; i < 4 ; i++) { + cx_linked_list_link(&nodes[i], &nodes[i+1], loc_prev, loc_next); + } + begin = &nodes[0]; + end = &nodes[4]; + CX_TEST_DO { + // insert a single node + node new_node = {0}; + new_node.data = 5; + CX_TEST_ASSERT(0 == cx_linked_list_insert_unique( + &begin, &end, + loc_prev, loc_next, + &new_node, test_cmp_node + )); + CX_TEST_ASSERT(new_node.prev == &nodes[0]); + CX_TEST_ASSERT(new_node.next == &nodes[1]); + CX_TEST_ASSERT(nodes[0].next == &new_node); + CX_TEST_ASSERT(nodes[1].prev == &new_node); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[4]); + + // now as duplicate + node new_node_dup = {0}; + new_node_dup.data = 5; + CX_TEST_ASSERT(0 != cx_linked_list_insert_unique( + &begin, &end, + loc_prev, loc_next, + &new_node_dup, test_cmp_node + )); + CX_TEST_ASSERT(new_node_dup.prev == NULL); + CX_TEST_ASSERT(new_node_dup.next == NULL); + CX_TEST_ASSERT(new_node.prev == &nodes[0]); + CX_TEST_ASSERT(new_node.next == &nodes[1]); + CX_TEST_ASSERT(nodes[0].next == &new_node); + CX_TEST_ASSERT(nodes[1].prev == &new_node); + CX_TEST_ASSERT(begin == &nodes[0]); + CX_TEST_ASSERT(end == &nodes[4]); + + // insert a new beginning node + node new_begin = {0}; + new_begin.data = 1; + CX_TEST_ASSERT(0 == cx_linked_list_insert_unique( + &begin, &end, + loc_prev, loc_next, + &new_begin, test_cmp_node + )); + CX_TEST_ASSERT(new_begin.prev == NULL); + CX_TEST_ASSERT(new_begin.next == &nodes[0]); + CX_TEST_ASSERT(nodes[0].prev == &new_begin); + CX_TEST_ASSERT(begin == &new_begin); + CX_TEST_ASSERT(end == &nodes[4]); + + // now as duplicate + node new_begin_dup = {0}; + new_begin_dup.data = 1; + CX_TEST_ASSERT(0 != cx_linked_list_insert_unique( + &begin, &end, + loc_prev, loc_next, + &new_begin_dup, test_cmp_node + )); + CX_TEST_ASSERT(new_begin_dup.prev == NULL); + CX_TEST_ASSERT(new_begin_dup.next == NULL); + CX_TEST_ASSERT(new_begin.prev == NULL); + CX_TEST_ASSERT(new_begin.next == &nodes[0]); + CX_TEST_ASSERT(nodes[0].prev == &new_begin); + CX_TEST_ASSERT(begin == &new_begin); + CX_TEST_ASSERT(end == &nodes[4]); + + // now insert a chain with two duplicates + node chain_start = {NULL, NULL, 8}; + node chain_mid1 = {NULL, NULL, 11}; + node chain_mid2 = {NULL, NULL, 14}; + node chain_mid3 = {NULL, NULL, 15}; + node chain_mid4 = {NULL, NULL, 15}; + node chain_end = {NULL, NULL, 17}; + cx_linked_list_link(&chain_start, &chain_mid1, loc_prev, loc_next); + cx_linked_list_link(&chain_mid1, &chain_mid2, loc_prev, loc_next); + cx_linked_list_link(&chain_mid2, &chain_mid3, loc_prev, loc_next); + cx_linked_list_link(&chain_mid3, &chain_mid4, loc_prev, loc_next); + cx_linked_list_link(&chain_mid4, &chain_end, loc_prev, loc_next); + + node *dup_start = cx_linked_list_insert_unique_chain( + &begin, &end, + loc_prev, loc_next, + &chain_start, test_cmp_node + ); + + CX_TEST_ASSERT(chain_start.prev == &nodes[1]); + CX_TEST_ASSERT(chain_start.next == &nodes[2]); + CX_TEST_ASSERT(chain_mid2.prev == &nodes[3]); + CX_TEST_ASSERT(chain_mid2.next == &nodes[4]); + CX_TEST_ASSERT(chain_end.prev == &nodes[4]); + CX_TEST_ASSERT(chain_end.next == NULL); + CX_TEST_ASSERT(begin == &new_begin); + CX_TEST_ASSERT(end == &chain_end); + + // the duplicates + CX_TEST_ASSERT(dup_start == &chain_mid1); + CX_TEST_ASSERT(dup_start->prev == NULL); + CX_TEST_ASSERT(dup_start->next == &chain_mid3); + CX_TEST_ASSERT(chain_mid3.prev == &chain_mid1); + CX_TEST_ASSERT(chain_mid3.next == &chain_mid4); + CX_TEST_ASSERT(chain_mid4.prev == &chain_mid3); + CX_TEST_ASSERT(chain_mid4.next == NULL); + } +} + CX_TEST(test_linked_list_first) { node *testdata = create_nodes_test_data(3); void *begin = testdata; @@ -1299,6 +1478,7 @@ const cx_list_class *cl = list->climpl == NULL ? list->cl : list->climpl; memcpy(defaulted_cl, cl, sizeof(cx_list_class)); defaulted_cl->insert_array = cx_list_default_insert_array; + defaulted_cl->insert_unique = cx_list_default_insert_unique; defaulted_cl->insert_sorted = cx_list_default_insert_sorted; defaulted_cl->sort = cx_list_default_sort; defaulted_cl->swap = cx_list_default_swap; @@ -1513,16 +1693,22 @@ int d6a[6] = array_init(52, 54, 56, 62, 64, 75); int d7a[6] = array_init(51, 57, 58, 65, 77, 78); int d8 = 90; + int d9 = 56; + int d10a[3] = array_init(67, 75, 90); int *d6ptr[6]; int *d7ptr[6]; + int *d10ptr[3]; for (size_t i = 0; i < 6; i++) { d6ptr[i] = &d6a[i]; d7ptr[i] = &d7a[i]; } + for (size_t i = 0 ; i < 3 ; i++) { + d10ptr[i] = &d10a[i]; + } size_t inserted; - int expected[18] = array_init( - 40, 50, 51, 52, 54, 56, 57, 58, 60, - 62, 64, 65, 70, 75, 77, 78, 80, 90 + int expected[22] = array_init( + 40, 50, 51, 52, 54, 56, 56, 57, 58, 60, + 62, 64, 65, 67, 70, 75, 75, 77, 78, 80, 90, 90 ); CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d1)); @@ -1543,9 +1729,73 @@ } CX_TEST_ASSERT(inserted == 6); CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d8)); + CX_TEST_ASSERT(0 == cxListInsertSorted(list, &d9)); + if (isptrlist) { + inserted = cxListInsertSortedArray(list, d10ptr, 3); + } else { + inserted = cxListInsertSortedArray(list, d10a, 3); + } + CX_TEST_ASSERT(inserted == 3); + CX_TEST_ASSERT(cxListSize(list) == 22); + for (size_t i = 0; i < 22; i++) { + CX_TEST_ASSERT(*(int *) cxListAt(list, i) == expected[i]); + } +}) - CX_TEST_ASSERT(cxListSize(list) == 18); - for (size_t i = 0; i < 18; i++) { +roll_out_test_combos_with_defaulted_funcs(insert_unique, { + int d1 = 50; + int d2 = 80; + int d3 = 60; + int d4 = 40; + int d5 = 70; + int d6a[6] = array_init(52, 54, 56, 62, 64, 75); + int d7a[6] = array_init(51, 57, 58, 65, 77, 78); + int d8 = 90; + int d9 = 56; + int d10a[3] = array_init(67, 75, 90); + int *d6ptr[6]; + int *d7ptr[6]; + int *d10ptr[3]; + for (size_t i = 0; i < 6; i++) { + d6ptr[i] = &d6a[i]; + d7ptr[i] = &d7a[i]; + } + for (size_t i = 0 ; i < 3 ; i++) { + d10ptr[i] = &d10a[i]; + } + size_t inserted; + int expected[19] = array_init( + 40, 50, 51, 52, 54, 56, 57, 58, 60, + 62, 64, 65, 67, 70, 75, 77, 78, 80, 90 + ); + + CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d1)); + CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d2)); + CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d3)); + CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d4)); + CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d5)); + if (isptrlist) { + inserted = cxListInsertUniqueArray(list, d6ptr, 6); + } else { + inserted = cxListInsertUniqueArray(list, d6a, 6); + } + CX_TEST_ASSERT(inserted == 6); + if (isptrlist) { + inserted = cxListInsertUniqueArray(list, d7ptr, 6); + } else { + inserted = cxListInsertUniqueArray(list, d7a, 6); + } + CX_TEST_ASSERT(inserted == 6); + CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d8)); + CX_TEST_ASSERT(0 == cxListInsertUnique(list, &d9)); + if (isptrlist) { + inserted = cxListInsertUniqueArray(list, d10ptr, 3); + } else { + inserted = cxListInsertUniqueArray(list, d10a, 3); + } + CX_TEST_ASSERT(inserted == 3); + CX_TEST_ASSERT(cxListSize(list) == 19); + for (size_t i = 0; i < 19; i++) { CX_TEST_ASSERT(*(int *) cxListAt(list, i) == expected[i]); } }) @@ -2173,6 +2423,7 @@ cx_test_register(suite, test_array_copy_unsupported_width); cx_test_register(suite, test_array_reserve); cx_test_register(suite, test_array_insert_sorted); + cx_test_register(suite, test_array_insert_unique); cx_test_register(suite, test_array_binary_search); cx_test_register(suite, test_list_arl_create); @@ -2192,6 +2443,8 @@ cx_test_register(suite, test_list_parl_insert_array); cx_test_register(suite, test_list_arl_insert_sorted); cx_test_register(suite, test_list_parl_insert_sorted); + cx_test_register(suite, test_list_arl_insert_unique); + cx_test_register(suite, test_list_parl_insert_unique); cx_test_register(suite, test_list_arl_remove); cx_test_register(suite, test_list_parl_remove); cx_test_register(suite, test_list_arl_remove_and_get); @@ -2247,6 +2500,8 @@ cx_test_register(suite, test_list_parlm_insert_array); cx_test_register(suite, test_list_arlm_insert_sorted); cx_test_register(suite, test_list_parlm_insert_sorted); + cx_test_register(suite, test_list_arlm_insert_unique); + cx_test_register(suite, test_list_parlm_insert_unique); cx_test_register(suite, test_list_arlm_swap); cx_test_register(suite, test_list_parlm_swap); cx_test_register(suite, test_list_arlm_sort); @@ -2272,6 +2527,7 @@ cx_test_register(suite, test_linked_list_insert); cx_test_register(suite, test_linked_list_insert_chain); cx_test_register(suite, test_linked_list_insert_sorted); + cx_test_register(suite, test_linked_list_insert_unique); cx_test_register(suite, test_linked_list_first); cx_test_register(suite, test_linked_list_last); cx_test_register(suite, test_linked_list_prev); @@ -2299,6 +2555,8 @@ cx_test_register(suite, test_list_pll_insert_array); cx_test_register(suite, test_list_ll_insert_sorted); cx_test_register(suite, test_list_pll_insert_sorted); + cx_test_register(suite, test_list_ll_insert_unique); + cx_test_register(suite, test_list_pll_insert_unique); cx_test_register(suite, test_list_ll_remove); cx_test_register(suite, test_list_pll_remove); cx_test_register(suite, test_list_ll_remove_and_get); @@ -2353,6 +2611,8 @@ cx_test_register(suite, test_list_pllm_insert_array); cx_test_register(suite, test_list_llm_insert_sorted); cx_test_register(suite, test_list_pllm_insert_sorted); + cx_test_register(suite, test_list_llm_insert_unique); + cx_test_register(suite, test_list_pllm_insert_unique); cx_test_register(suite, test_list_llm_swap); cx_test_register(suite, test_list_pllm_swap); cx_test_register(suite, test_list_llm_sort); @@ -2379,6 +2639,8 @@ cx_test_register(suite, test_list_pkvl_insert_array); cx_test_register(suite, test_list_kvl_insert_sorted); cx_test_register(suite, test_list_pkvl_insert_sorted); + cx_test_register(suite, test_list_kvl_insert_unique); + cx_test_register(suite, test_list_pkvl_insert_unique); cx_test_register(suite, test_list_kvl_remove); cx_test_register(suite, test_list_pkvl_remove); cx_test_register(suite, test_list_kvl_remove_and_get);
