--- a/docs/Writerside/topics/list.h.md Thu Mar 06 20:28:34 2025 +0100
+++ b/docs/Writerside/topics/list.h.md Mon Mar 10 11:54:46 2025 +0100
@@ -1,9 +1,5 @@
# List Interface
-<warning>
-Outdated Section - will be updated soon!
-</warning>
-
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))
@@ -42,9 +38,69 @@
## Example
-<warning>
-TODO: add example how to work with lists
-</warning>
+In the following example we create a linked-list of regular expressions for filtering data.
+
+```C
+#include <cx/linked_list.h>
+#include <regex.h>
+
+CxList *create_pattern_list(void) {
+ // create a linked list to store patterns
+ CxList *list = cxLinkedListCreateSimple(sizeof(regex_t));
+
+ // automatically free the pattern when list gets destroyed
+ cxDefineDestructor(list, regfree);
+
+ return list;
+}
+
+int add_pattern(CxList *list, const char *value) {
+ // compile pattern and add it to the list, if successful
+ regex_t regex;
+ if (regcomp(®ex, value, REG_EXTENDED|REG_NOSUB)) {
+ return 1;
+ } else {
+ // take address of local variable
+ // since we are not storing pointers in this list,
+ // we get a copy of the data directly in the list
+ cxListAdd(list, ®ex);
+ return 0;
+ }
+}
+
+bool matches_any(CxList *list, const char *text) {
+ CxIterator iter = cxListIterator(list);
+ cx_foreach(regex_t*, pat, iter) {
+ if (regexec(pat, text, 0, NULL, 0) == 0) {
+ return true;
+ }
+ }
+ return false;
+}
+```
+
+If in the above example the list was created with `CX_STORE_POINTERS` instead of `sizeof(regex_t)`,
+the `add_pattern()` function would need to be changed as follows:
+
+```C
+int add_pattern(CxList *list, const char *value) {
+ // allocate memory here, because now we are storing pointers
+ regex_t *regex = malloc(sizeof(regex_t));
+ if (!regex || regcomp(regex, value, REG_EXTENDED|REG_NOSUB)) {
+ return 1;
+ } else {
+ cxListAdd(list, regex);
+ return 0;
+ }
+}
+```
+
+Also, just registering `regfree()` as destructor is not sufficient anymore, because the `regex_t` structure also needs to be freed.
+Therefore, we would need to wrap the calls to `regfree()` and `free()` into an own destructor, which we then register with the list.
+However, it should be clear by now that using `CX_STORE_POINTERS` is a bad choice for this use case to begin with.
+
+As a rule of thumb: if you allocate memory for an element that you immediately put into the list, consider storing the element directly.
+And if you are getting pointers to already allocated memory from somewhere else, and you just want to organize those elements in a list, then consider using `CX_STORE_POINTERS`.
> 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.
@@ -79,7 +135,7 @@
Similarly, `cxListInsert()` adds the element at the specified `index`,
and `cxListInsertSorted()` adds the element at the correct position so that the list remains sorted according to the list's compare function.
-When you are currently iterating through a list, you can insert items before or after the current position of the iterator
+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.
This _should_ be done with [mutating iterators](iterator.h.md#mutating-iterators) only, but is also defined for normal iterators.
@@ -261,9 +317,95 @@
## Implement own List Structures
-<warning>
-TODO: add documentation
-</warning>
+If you want to create your own list implementation, this is extremely easy.
+
+You just need to define a function for creating your list and assign a `cx_list_class` structure with the pointers to your implementation.
+Then you call the `cx_list_init()` helper function to initialize the collection sture.
+This also automatically adds support for `CX_STORE_POINTERS` to your list.
+
+```C
+// define the class with pointers to your functions
+static cx_list_class my_list_class = {
+ my_list_destructor,
+ my_list_insert_element,
+ my_list_insert_array,
+ my_list_insert_sorted,
+ my_list_insert_iter,
+ my_list_remove,
+ my_list_clear,
+ my_list_swap,
+ my_list_at,
+ my_list_find_remove,
+ my_list_sort,
+ my_list_compare,
+ my_list_reverse,
+ my_list_iterator,
+};
+
+typedef struct {
+ struct cx_list_s base;
+ // your custom list data goes here
+} my_list;
+
+CxList *my_list_create(
+ const CxAllocator *allocator,
+ cx_compare_func cmpfun,
+ size_t elem_size
+) {
+ if (allocator == NULL) {
+ allocator = cxDefaultAllocator;
+ }
+
+ my_list *list = cxCalloc(allocator, 1, sizeof(my_list));
+ if (list == NULL) return NULL;
+ cx_list_init((CxList*)list, &my_list_class,
+ allocator, cmpfun, elem_size);
+
+ // initialize your custom list data here
+
+ return (CxList *) list;
+}
+```
+
+The required behavior for the implementations is described in the following table.
+You can always look at the source code of the UCX implementations to get inspiration.
+
+| Function | Description |
+|------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
+| `clear` | Invoke destructor functions on all elements and remove them from the list. |
+| `destructor` | Invoke destructor functions on all elements and deallocate the entire list memory. |
+| `insert_element` | Insert a single element at the specified index. Return zero on success and non-zero on failure. |
+| `insert_array` | Insert an array of elements starting at the specified index. Return the number of elements inserted. |
+| `insert_sorted` | Insert an array of sorted elements into a sorted list. Return the number of elements inserted. |
+| `insert_iter` | Insert a single element depending on the iterator position. The third argument to this function is zero when the element shall be inserted after the iterator position and non-zero if it shall be inserted before the iterator position. The implementation is also responsible for adjusting the iterator, respectively. |
+| `remove` | Removes a multiple elements starting at the specified index. If a target buffer is specified, copy the elements to that buffer. Otherwise, invoke the destructor functions for the elements. Return the number of elements actually removed. |
+| `swap` | Swap two elements by index. Return zero on success or non-zero when any index was out-of-bounds. |
+| `at` | Return a pointer to the element at the specified index or `NULL` when the index is out-of-bounds. |
+| `find_remove` | Search for the specified element with the list's compare function and return the index if found. If the `remove` argument is true, invoke the destructor functions and remove the element. Return the list size if the element is not found. |
+| `sort` | Sort all elements in the list with respect to the list's compare function. |
+| `compare` | Only function pointer that may be `NULL`, in which case an unoptimized fallback is used. You can implement an optimized compare function that compares the list of another list of the same class. |
+| `reverse` | Reorders all elements in the list so that they appear in exactly the opposite order. |
+| `iterator` | Creates an iterator starting at the specified index. The Boolean argument indicates whether iteration is supposed to traverse backwards. |
+
+> If you initialize your list with `cx_list_init()` you do not have to worry about making a
+> difference between storing pointers and storing elements, because your implementation will
+> be automatically wrapped.
+> This means, you only have to handle the one single case described above.
+
+### Default Class Function Implementations
+
+If you are satisfied with some of the default implementations, you can use some pre-defined functions.
+Note, however, that those are not optimized for any specific list structure
+and just serve as a quick and convenient solution if performance does not matter for your use case.
+
+
+| Default Function | Description |
+|---------------------------------|-----------------------------------------------------------------------------------|
+| `cx_list_default_insert_array` | Falls back to multiple calls of `insert_element`. |
+| `cx_list_default_insert_sorted` | Uses linear search to find insertion points. |
+| `cx_list_default_sort` | Copies all elements to an array, applies `qsort()`, and copies the elements back. |
+| `cx_list_default_swap` | Uses a temporarily allocated buffer to perform a three-way-swap. |
+
<seealso>
<category ref="apidoc">