Mercurial > hg > ucx / changeset

--- a/docs/Writerside/topics/collection.h.md	Fri Dec 19 18:31:26 2025 +0100
+++ b/docs/Writerside/topics/collection.h.md	Sat Dec 20 10:43:14 2025 +0100
@@ -60,10 +60,6 @@
 // the following two can be used to optimize loops
 cx_invoke_simple_compare_func(c, left, right) 
 cx_invoke_advanced_compare_func(c, left, right)
-
-// convenience macro for addressing and dereference elements in pointer collections
-cx_ref(c, elem) 
-cx_deref(c, elem) 
 ```
 
 If an advanced compare function is specified, `cx_invoke_compare_func()` will only invoke the advanced comparator.
@@ -77,7 +73,7 @@
 A typical use case would be this:
 
 ```C
-void *arg = // ... passed as argument, e.g. in cxListContains()
+void *arg = // ... passed as argument
 void *elem = // ... get a pointer to the element
 void *data;
 
@@ -88,11 +84,18 @@
     data = elem;
 }
 
-// ... or with the convenience macro
+// ... or with a convenience macro
 data = cx_deref(this_collection, elem);
 int result = cx_invoke_compare_func(this_collection, data, arg);
 ```
 
+> When you are implementing a custom `CxList`, the above handling of pointers vs. elements is implemented
+> by `cx_list_compare_wrapper`, a `cx_compare_func2` which takes the `list` as third argument.
+> It will do the dereferencing for you.
+> 
+> It is important that both arguments, left and right, for the compare function are either both pointers to pointers
+> or both pointers to elements, but never mixed.
+
 ## Destructor Functions
 
 For working with destructors, the following macros are defined:
@@ -121,6 +124,8 @@
 > If your collection is storing pointers (i.e. `cxCollectionStoresPointers()` returns `true`)
 > the `cx_invoke_destructor()` will make sure that the pointer to the element is dereferenced first,
 > so that the destructor functions are _always_ invoked with a pointer to the actual element.
+> 
+> This is different to how [comparator functions](#comparator-functions) work.
 {style="note"}
 
 <seealso>

--- a/docs/Writerside/topics/collections.md	Fri Dec 19 18:31:26 2025 +0100
+++ b/docs/Writerside/topics/collections.md	Sat Dec 20 10:43:14 2025 +0100
@@ -3,7 +3,7 @@
 UCX provides a [linked list](linked_list.h.md) and [array list](array_list.h.md) implementation over a common [list](list.h.md) interface,
 as well as a [hash nap](hash_map.h.md) implementation over a [map](map.h.md) interface, and a basic [tree](tree.h.md) implementation.
 
-Another special collection is the [key/value-list](kv_list.h.md) that combines both the list and the map interfaces.
+Another special collection is the [key/value list](kv_list.h.md) that combines both the list and the map interfaces.
 
 Additionally, UCX provides an abstraction for [iterators](iterator.h.md) that work with all collection types, and
 plain C arrays.

--- a/docs/Writerside/topics/kv_list.h.md	Fri Dec 19 18:31:26 2025 +0100
+++ b/docs/Writerside/topics/kv_list.h.md	Sat Dec 20 10:43:14 2025 +0100
@@ -79,3 +79,9 @@
 while the `cxKvListInsert()` function will insert the element at the specified index.
 
 > The effect of `cxKvListAdd()` using the list interface and `cxMapPut()` using the map interface is the same.
+
+<seealso>
+<category ref="apidoc">
+<a href="https://ucx.sourceforge.io/api/kv__list_8h.html">kv_list.h</a>
+</category>
+</seealso>

--- a/docs/Writerside/topics/linked_list.h.md	Fri Dec 19 18:31:26 2025 +0100
+++ b/docs/Writerside/topics/linked_list.h.md	Sat Dec 20 10:43:14 2025 +0100
@@ -137,6 +137,22 @@
 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);
+
+void cx_linked_list_insert_sorted_c(void **begin, void **end,
+        ptrdiff_t loc_prev, ptrdiff_t loc_next,
+        void *new_node, cx_compare_func2 cmp_func, void *context);
+
+void cx_linked_list_insert_sorted_chain_c(void **begin, void **end,
+        ptrdiff_t loc_prev, ptrdiff_t loc_next,
+        void *insert_begin, cx_compare_func2 cmp_func, void *context);
+        
+int cx_linked_list_insert_unique_c(void **begin, void **end,
+        ptrdiff_t loc_prev, ptrdiff_t loc_next,
+        void *new_node, cx_compare_func2 cmp_func, void *context);
+
+void *cx_linked_list_insert_unique_chain_c(void **begin, void **end,
+        ptrdiff_t loc_prev, ptrdiff_t loc_next,
+        void *insert_begin, cx_compare_func2 cmp_func, void *context);
 ```
 
 The above functions can be used to insert one or more elements into a linked list.
@@ -168,6 +184,8 @@
 > 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.
 
+The functions with the `_c` suffix are equivalent, except that they accept a `cx_compare_func2` with additional `context`.
+
 ## Access and Find
 
 ```C
@@ -298,14 +316,14 @@
 );
 ```
 
-For comparing two linked list, you need to specify where to start,
+For comparing two linked lists, you need to specify where to start,
 and the offsets for the pointer to the next node and the data.
 
 In the natural case, `begin_left` and `begin_right` point to the first node of either list,
 and `loc_advance` is the offset of the `next` pointer.
 But it is also possible to start with the _last_ node of both lists and use the `prev` pointer to compare them backwards.
 
-The `loc_data` offset is used to calculate the pointer that is passed to the `cmp_fnc`.
+The `loc_data` offset is used to calculate the pointer that is passed to the `cmp_func`.
 This can either be the offset of a specific field in the struct or simply zero, in which case the pointers to the nodes themselves are passed to the compare function.
 
 The function `cx_linked_list_compare_c()` allows additional `context` for the compare function.

--- a/docs/Writerside/topics/list.h.md	Fri Dec 19 18:31:26 2025 +0100
+++ b/docs/Writerside/topics/list.h.md	Sat Dec 20 10:43:14 2025 +0100
@@ -4,7 +4,8 @@
 
 UCX already comes with two common list implementations ([linked list](linked_list.h.md) and [array list](array_list.h.md))
 that should cover most use cases.
-But if you feel the need to implement your own list, you will find the instructions [below](#implement-own-list-structures).
+A more advanced use case is implemented as a [key/value list](kv_list.h.md).
+If you feel the need to implement your own list, you will find the instructions [below](#implement-own-list-structures).
 
 ```C
 #include <cx/linked_list.h>
@@ -16,19 +17,27 @@
 
 CxList *cxArrayListCreate(const CxAllocator *allocator,
         size_t elem_size, size_t initial_capacity);
+
+#include <cx/kv_list.h>
+
+CxList *cxKvListCreate(const CxAllocator *allocator,
+        size_t elem_size);
+
+CxMap *cxKvListCreateAsMap(const CxAllocator *allocator,
+        size_t elem_size);
 ```
 
 The function `cxLinkedListCreate()` creates a new linked list with the specified `allocator` which stores elements of size `elem_size`.
-The elements are supposed to be compared with the specified `comparator` (cf. [](#access-and-find)).
 
 Array lists can be created with `cxArrayListCreate()` where the additional argument `initial_capacity` specifies for how many elements the underlying array shall be initially allocated.
 
+The key/value list implements both the list and the [map](map.h.md) interfaces and allows access to the elements via a key.
+Depending on the perspective, you can see a key/value list as an associative list or as an _ordered_ map.
+
 If `CX_STORE_POINTERS` is used as `elem_size`, the actual element size will be `sizeof(void*)` and the list will behave slightly differently when accessing elements.
 Lists that are storing pointers will always return the stored pointer directly, instead of returning a pointer into the list's memory, thus saving you from unnecessary dereferencing.
 Conversely, when adding elements to the list, the pointers you specify (e.g., in `cxListAdd()` or `cxListInsert()`) are directly added to the list, instead of copying the contents pointed to by the argument.
 
-> When you create a list which is storing pointers and do not specify a compare function, `cx_cmp_ptr` will be used by default.
-
 > If you want to lazy-initialize lists, you can use the global `cxEmptyList` symbol as a placeholder instead of using a `NULL`-pointer.
 > While you *must not* insert elements into that list, you can safely access this list or create iterators.
 > This allows you to write clean code without checking for `NULL`-pointer everywhere.
@@ -44,6 +53,7 @@
 
 CxList *create_pattern_list(void) {
     // create a linked list to store patterns
+    // NULL means, the cxDefaultAllocator will be used
     CxList *list = cxLinkedListCreate(NULL, sizeof(regex_t));
     
     // automatically free the pattern when list gets destroyed
@@ -151,19 +161,29 @@
 > And the `index` attribute will count from zero to `elem_count - 1`.
 > {style="note"}
 
+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.
+
+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.
+
 The function `cxListInsertSorted()` inserts the element at the correct position so that the list remains sorted according to the list's compare function.
 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.
+> Inserting sorted or unique elements requires a [comparator function](collection.h.md#comparator-functions).
+> If you haven't set one specifically, the list is using `cx_cmp_ptr` for pointer lists and
+> a `memcmp()`-based solution for non-pointer lists by default.
+> They might be enough to determine uniqueness, but are usually not capable of determining a reasonable sort order.
+>
+> It is strongly recommended to set a comparator function (e.g., one of those defined in [compare.h](compare.h.md))
+> with `cxSetCompareFunc()` after creating the list, when you intend to use functions that need to compare elements.
+> {style="note"}
 
-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()`, `cxListInsertSortedArray()`, and `cxListInsertUniqueArray()`
+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).
+Here, no auto-magic is implemented, depending on `cxCollectionStoresPointers()`.
 
 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()`,
@@ -172,15 +192,15 @@
 > 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.
 > 
-> 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.
+> When the `list` is sorted, the `array` passed to the functions must also be sorted according to the list's compare function.
+> As a special case, `cxListInsertUniqueArray()` also works with lists that are not sorted, in which case the `array` also does not need to be sorted.
+> However, it is strongly recommended to work with sorted arrays to avoid bugs that are caused by a failed assumption.
+> Plus, the functions do not check if the passed arrays are sorted!
 > {style="note"}
 
 ## Access and Find
 
-<link-summary>Functions for searching and accessing elements.</link-summary>
+Functions for searching and accessing elements.
 
 ```C
 #include <cx/list.h>
@@ -227,7 +247,13 @@
 The function `cxListContains()` returns `true` if and only if `cxListFind()` returns a valid index.
 
 With `cxListIndexValid()` you can check the index returned by `cxListFind()` or `cxListFindRemove()`,
-which is more convenient than comparing the return value if the return value of `cxListSize()`.  
+which is more convenient than comparing the return value with the return value of `cxListSize()`.  
+
+> The functions `cxListFind()`, `cxListFindRemove()`, and `cxListContains()` use the collections
+> [comparator function](collection.h.md#comparator-functions).
+> If you haven't set one specifically, the list is using `cx_cmp_ptr` for pointer lists and
+> a `memcmp()`-based solution for non-pointer lists by default.
+> {style="note"}
 
 ## Remove
 
@@ -263,6 +289,7 @@
 
 The function `cxListFindRemove()` finds the first element within the list that is equivalent to the element pointed to by `elem` and removes it from the list.
 This will _also_ call destructor functions, if specified, so take special care when you continue to use `elem`.
+This function needs a valid [comparator function](collection.h.md#comparator-functions).
 
 On the other hand, `cxListRemoveAndGet()` family of functions do not invoke the destructor functions
 and instead copy the elements into the `targetbuf`, which must be large enough to hold the removed elements.
@@ -326,6 +353,14 @@
 > For example, the [array list](array_list.h.md) implementation will use binary search
 > for `cxListFind()` and similar operations when the list is sorted.
 
+> The function `cxListSort()` uses the collections [comparator function](collection.h.md#comparator-functions).
+> If you haven't set one specifically, the list is using `cx_cmp_ptr` for pointer lists and
+> a `memcmp()`-based solution for non-pointer lists by default, which do not provide a reasonable order of the elements.
+> 
+> It is strongly recommended to set a comparator function (e.g., one of those defined in [compare.h](compare.h.md))
+> with `cxSetCompareFunc()` after creating the list, when you intend to use functions that need to compare elements.
+> {style="note"}
+
 ## Compare
 
 ```C
@@ -334,14 +369,19 @@
 int cxListCompare(const CxList *list, const CxList *other);
 ```
 
-Arbitrary lists can be compared element-wise with `cxListCompare()`, as long as the compare functions of both lists are equivalent.
+Arbitrary lists can be compared element-wise with `cxListCompare()`,
+as long as the [comparator functions](collection.h.md#comparator-functions) of both lists are equivalent.
 
 That means you can compare an UCX [array list](array_list.h.md) with a [linked list](linked_list.h.md),
 and you could even compare lists that are storing pointers with lists that are not storing pointers.
 
-However, the optimized list-internal compare implementation is only used when both the compare functions and the list classes are identical.
+However, the optimized list-internal compare implementation is only used when they are identical for both lists.
 Otherwise, `cxListCompare()` will behave as if you were iterating through both lists and manually comparing the elements.
 
+> Since the [key/value list](kv_list.h.md) is based on a [linked list](linked_list.h.md),
+> they share the same optimized implementation for `compare`.
+> That means comparing a key/value list with a normal linked list is as efficient as comparing two linked lists.
+
 The return value of `cxListCompare()` is zero if the lists are element-wise equivalent.
 If they are not, the non-zero return value equals the return value of the used compare function for the first pair of elements that are not equal.