Mercurial > hg > ucx / changeset

--- a/docs/Writerside/topics/list.h.md	Fri Oct 17 14:14:21 2025 +0200
+++ b/docs/Writerside/topics/list.h.md	Fri Oct 17 15:04:56 2025 +0200
@@ -148,7 +148,9 @@
 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. 
+It is important that the list is already sorted before calling this function.
+On the other hand, `cxListInsertUnique()` inserts the element only if it is not already in the list.
+In this case it is strongly recommended that the list is already sorted but not required; the function will fall back to an inefficient algorithm when the list is not sorted.
 
 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.
@@ -160,17 +162,17 @@
 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).
 
-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 lower 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 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.
+> 
+> When used with sorted lists, the arrays passed to the functions must also be sorted according to the list's compare function.
+> Only when `cxListInsertUniqueArray()` is used with a list that is not sorted, the array does not need to be sorted.
+> 
+> The functions do not check if the passed arrays are sorted.
 > {style="note"}
 
 ## Access and Find

--- a/src/cx/list.h	Fri Oct 17 14:14:21 2025 +0200
+++ b/src/cx/list.h	Fri Oct 17 15:04:56 2025 +0200
@@ -421,9 +421,12 @@
 CX_EXPORT int cxListInsertSorted(CxList *list, const void *elem);
 
 /**
- * Inserts an item into a sorted list if it does not exist.
+ * Inserts an item into a list if it does not exist.
  *
- * If the list is not sorted already, the behavior is undefined.
+ * If the list is not sorted already, this function will check all elements
+ * and append the new element when it was not found.
+ * It is strongly recommended to use this function only on sorted lists, where
+ * the element, if it is not contained, is inserted at the correct position.
  *
  * @param list the list
  * @param elem a pointer to the element to add
@@ -478,7 +481,14 @@
 CX_EXPORT size_t cxListInsertSortedArray(CxList *list, const void *array, size_t n);
 
 /**
- * Inserts a sorted array into a sorted list, skipping duplicates.
+ * Inserts an array into a list, skipping duplicates.
+ *
+ * The @p list does not need to be sorted (in contrast to cxListInsertSortedArray()).
+ * But it is strongly recommended to use this function only on sorted lists,
+ * because otherwise it will fall back to an inefficient algorithm which inserts
+ * all elements one by one.
+ * If the @p list is not sorted, the @p array also does not need to be sorted.
+ * But when the @p list is sorted, the @p array must also be sorted.
  *
  * This method is usually more efficient than inserting each element separately
  * because consecutive chunks of sorted data are inserted in one pass.
@@ -495,9 +505,6 @@
  * 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.
- *
  * @param list the list
  * @param array a pointer to the elements to add
  * @param n the number of elements to add

--- a/src/list.c	Fri Oct 17 14:14:21 2025 +0200
+++ b/src/list.c	Fri Oct 17 15:04:56 2025 +0200
@@ -597,17 +597,24 @@
 }
 
 int cxListInsertSorted(CxList *list, const void *elem) {
-    assert(list->collection.sorted || list->collection.size == 0);
+    assert(cxCollectionSorted(list));
     list->collection.sorted = true;
     const void *data = list->collection.store_pointer ? &elem : elem;
     return list->cl->insert_sorted(list, data, 1) == 0;
 }
 
 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;
+    if (cxCollectionSorted(list)) {
+        list->collection.sorted = true;
+        const void *data = list->collection.store_pointer ? &elem : elem;
+        return list->cl->insert_unique(list, data, 1) == 0;
+    } else {
+        if (cxListContains(list, elem)) {
+            return 0;
+        } else {
+            return cxListAdd(list, elem);
+        }
+    }
 }
 
 size_t cxListInsertArray(CxList *list, size_t index, const void *array, size_t n) {
@@ -616,15 +623,30 @@
 }
 
 size_t cxListInsertSortedArray(CxList *list, const void *array, size_t n) {
-    assert(list->collection.sorted || list->collection.size == 0);
+    assert(cxCollectionSorted(list));
     list->collection.sorted = true;
     return list->cl->insert_sorted(list, array, n);
 }
 
 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);
+    if (cxCollectionSorted(list)) {
+        list->collection.sorted = true;
+        return list->cl->insert_unique(list, array, n);
+    } else {
+        const char *source = array;
+        for (size_t i = 0 ; i < n; i++) {
+            // note: this also checks elements added in a previous iteration
+            const void *data = list->collection.store_pointer ?
+                    *((const void**)source) : source;
+            if (!cxListContains(list, data)) {
+                if (cxListAdd(list, data)) {
+                    return i; // LCOV_EXCL_LINE
+                }
+            }
+            source += list->collection.elem_size;
+        }
+        return n;
+    }
 }
 
 int cxListInsertAfter(CxIterator *iter, const void *elem) {

--- a/tests/test_list.c	Fri Oct 17 14:14:21 2025 +0200
+++ b/tests/test_list.c	Fri Oct 17 15:04:56 2025 +0200
@@ -1814,6 +1814,67 @@
     }
 })
 
+roll_out_test_combos_with_defaulted_funcs(insert_unique_not_sorted, {
+    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(
+        50, 80, 60, 40, 70, 52, 54, 56, 62, 64,
+        75, 51, 57, 58, 65, 77, 78, 90, 67
+    );
+
+    // begin with an unsorted list!
+    CX_TEST_ASSERT(0 == cxListAdd(list, &d1));
+    CX_TEST_ASSERT(0 == cxListAdd(list, &d2));
+    CX_TEST_ASSERT(0 == cxListAdd(list, &d3));
+    CX_TEST_ASSERT(0 == cxListAdd(list, &d4));
+
+    // not start adding unique items
+    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]);
+    }
+})
+
 roll_out_test_combos(remove, {
     const size_t testdata_len = 32;
     int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len);
@@ -2554,6 +2615,8 @@
     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_insert_unique_not_sorted);
+    cx_test_register(suite, test_list_parl_insert_unique_not_sorted);
     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);
@@ -2611,6 +2674,8 @@
     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_insert_unique_not_sorted);
+    cx_test_register(suite, test_list_parlm_insert_unique_not_sorted);
     cx_test_register(suite, test_list_arlm_swap);
     cx_test_register(suite, test_list_parlm_swap);
     cx_test_register(suite, test_list_arlm_sort);
@@ -2666,6 +2731,8 @@
     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_insert_unique_not_sorted);
+    cx_test_register(suite, test_list_pll_insert_unique_not_sorted);
     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);
@@ -2722,6 +2789,8 @@
     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_insert_unique_not_sorted);
+    cx_test_register(suite, test_list_pllm_insert_unique_not_sorted);
     cx_test_register(suite, test_list_llm_swap);
     cx_test_register(suite, test_list_pllm_swap);
     cx_test_register(suite, test_list_llm_sort);
@@ -2750,6 +2819,8 @@
     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_insert_unique_not_sorted);
+    cx_test_register(suite, test_list_pkvl_insert_unique_not_sorted);
     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);