changeset
complete list.h documentation
Mon, 10 Mar 2025 11:54:46 +0100
- author
- Mike Becker <universe@uap-core.de>
- date
- Mon, 10 Mar 2025 11:54:46 +0100
- changeset 1240
- c5924c781372
- parent 1239
- b4b1f15d1866
- child 1241
- ebcc08023c33
complete list.h documentation
relates to #451
| docs/Writerside/topics/list.h.md | file | annotate | diff | comparison | revisions |
--- 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">
