ucx: comparison docs/Writerside/topics/list.h.md

-:14ae6a039af7
+:5c3e6477aab4
 The `list.h` header defines a common interface for all list implementations.
 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>
 CxList *cxLinkedListCreate(const CxAllocator *allocator,
 #include <cx/array_list.h>
 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.
 > You still need to make sure that the placeholder is replaced with an actual list before inserting elements.
 #include <cx/linked_list.h>
 #include <regex.h>
 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
 cxSetDestructor(list, regfree);
 > the iterator will iterate only over the elements that have been successfully allocated.
 > The `elem_count` attribute of the iterator will be set to the number of successfully allocated elements.
 > 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
+> Inserting sorted or unique elements requires a [comparator function](collection.h.md#comparator-functions).
-with `cxListInsertBefore()` or `cxListInsertAfter()`, respectively.
+> 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.
-If the list is storing pointers (cf. `cxCollectionStoresPointers()`), the pointer `elem` is directly added to the list.
+> They might be enough to determine uniqueness, but are usually not capable of determining a reasonable sort order.
-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.
+>
+> It is strongly recommended to set a comparator function (e.g., one of those defined in [compare.h](compare.h.md))
-On the other hand, the `array` argument for `cxListAddArray()`, `cxListInsertArray()`, `cxListInsertSortedArray()`, and `cxListInsertUniqueArray()`
+> with `cxSetCompareFunc()` after creating the list, when you intend to use functions that need to compare elements.
+> {style="note"}
+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()`,
 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.
 >
-> When used with sorted lists, the arrays passed to the functions must also be sorted according to the list's compare function.
+> When the `list` is sorted, the `array` 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.
+> 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.
-> The functions do not check if the passed arrays are sorted.
+> 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>
 void *cxListAt(const CxList *list, size_t index);
 This will _also_ call destructor functions, if specified, so take special care when you continue to use `elem`, or when the list is storing pointers and the element appears more than once in the list.
 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
 ```C
 #include <cx/list.h>
 The function `cxListRemoveArray()` removes `num` elements starting at `index` and returns the number of elements that have been removed.
 For each removed element, the [destructor functions](collection.h.md#destructor-functions) are called.
 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.
 > Note that when the list was initialized with `CX_STORE_POINTERS`,
 > An invocation of `cxListSort` sets the `sorted` flag of the [collection](collection.h.md).
 > Implementations usually make use of this flag to optimize search operations, if possible.
 > 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
 #include <cx/list.h>
 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.
 ## Clone

Mercurial > hg > ucx / file comparison

comparison: docs/Writerside/topics/list.h.md

docs/Writerside/topics/list.h.md