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

-:b4b1f15d1866
+:c5924c781372
 # 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))
 that should cover most use cases.
 > When you create a list which is storing pointers and do not specify a compare function, `cx_cmp_ptr` will be used by default.
 ## Example
-<warning>
+In the following example we create a linked-list of regular expressions for filtering data.
-TODO: add example how to work with lists
-</warning>
+```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(&regex, 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, &regex);
+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.
 > 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.
 The function `cxListAdd()` appends the element `elem` to the list and returns zero on success or non-zero when allocating the memory for the element fails.
 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.
 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.
 or any of the destructor functions deallocates the memory.
 Otherwise, there is a risk of a memory leak.
 ## Implement own List Structures
-<warning>
+If you want to create your own list implementation, this is extremely easy.
-TODO: add documentation
-</warning>
+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">
 <a href="https://ucx.sourceforge.io/api/list_8h.html">list.h</a>
 </category>

Mercurial > hg > ucx / file comparison

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

docs/Writerside/topics/list.h.md