Mercurial > hg > ucx / file diff

--- 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.