Mon, 03 Jul 2023 18:37:19 +0200
add documentation for the lists
docs/src/features.md | file | annotate | diff | comparison | revisions |
1.1 --- a/docs/src/features.md Sat Jul 01 14:29:16 2023 +0200 1.2 +++ b/docs/src/features.md Mon Jul 03 18:37:19 2023 +0200 1.3 @@ -209,14 +209,100 @@ 1.4 1.5 *Header file:* [list.h](api/list_8h.html) 1.6 1.7 +This header defines a common interface for all list implementations, which is basically as simple as the following 1.8 +structure. 1.9 +```c 1.10 +struct cx_list_s { 1.11 + CX_COLLECTION_MEMBERS // size, capacity, etc. 1.12 + cx_list_class const *cl; // The list class definition 1.13 +}; 1.14 +``` 1.15 +The actual structure contains one more class pointer that is used when wrapping a list into a pointer aware list 1.16 +with `cxListStorePointers()`. What this means, is that - if you want to implement your own list structure - you 1.17 +only need to cover the case where the list is storing copies of your objects. 1.18 + 1.19 +UCX comes with two common list implementations (linked list and array list) that should cover most use cases. 1.20 +But if you feel the need to implement an own list, the only thing you need to do is to define a struct where 1.21 +`struct cx_list_s`, and set an appropriate list class that implements the functionality. 1.22 +It is strongly recommended that this class is shared among all instances of the same list type, because otherwise 1.23 +the `cxListCompare` function cannot use the optimized implementation of your class and will instead fall back to 1.24 +using iterators to compare the contents element-wise. 1.25 + 1.26 ### Linked List 1.27 1.28 *Header file:* [linked_list.h](api/linked__list_8h.html) 1.29 1.30 +On top of implementing the list interface, this header also defines several low-level functions that 1.31 +work with arbitrary structures. 1.32 +Low-level functions, in contrast to the high-level list interface, can easily be recognized by their snake-casing. 1.33 +The function `cx_linked_list_at`, for example, implements a similar functionality like `cxListAt`, but operates 1.34 +on arbitrary structures. 1.35 +The following snippet shows how it is used. 1.36 +All other low-level functions work similarly. 1.37 +```c 1.38 +struct node { 1.39 + node *next; 1.40 + node *prev; 1.41 + int data; 1.42 +}; 1.43 + 1.44 +const ptrdiff_t loc_prev = offsetof(struct node, prev); 1.45 +const ptrdiff_t loc_next = offsetof(struct node, next); 1.46 +const ptrdiff_t loc_data = offsetof(struct node, data); 1.47 + 1.48 +struct node a = {0}, b = {0}, c = {0}, d = {0}; 1.49 +cx_linked_list_link(&a, &b, loc_prev, loc_next); 1.50 +cx_linked_list_link(&b, &c, loc_prev, loc_next); 1.51 +cx_linked_list_link(&c, &d, loc_prev, loc_next); 1.52 + 1.53 +cx_linked_list_at(&a, 0, loc_next, 2); // returns pointer to c 1.54 +``` 1.55 + 1.56 ### Array List 1.57 1.58 *Header file:* [array_list.h](api/array__list_8h.html) 1.59 1.60 +Since low-level array lists are just plain arrays, there is no need for such many low-level functions as for linked 1.61 +lists. 1.62 +However, there is one extremely powerful function that can be used for several complex tasks: `cx_array_copy`. 1.63 +The full signature is shown below: 1.64 +```c 1.65 +enum cx_array_copy_result cx_array_copy( 1.66 + void **target, 1.67 + size_t *size, 1.68 + size_t *capacity, // optional 1.69 + size_t index, 1.70 + void const *src, 1.71 + size_t elem_size, 1.72 + size_t elem_count, 1.73 + struct cx_array_reallocator_s *reallocator // optional 1.74 +); 1.75 +``` 1.76 +The `target` argument is a pointer to the target array pointer. 1.77 +The reason for this additional indirection is that - given that you provide a `reallocator` - this function writes 1.78 +back the pointer to the possibly reallocated array. 1.79 +THe next two arguments are pointers to the `size` and `capacity` of the target array. 1.80 +Tracking the capacity is optional. 1.81 +If you do not specify a pointer for the capacity, automatic reallocation of the array is entirely disabled (i.e. it 1.82 +does not make sense to specify a `reallocator` then). 1.83 +In this case, the function cannot copy more than `size-index` elements and if you try, it will return 1.84 +`CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED` and do nothing. 1.85 + 1.86 +On a successful invocation, the function copies `elem_count` number of elements, each of size `elem_size` from 1.87 +`src` to `*target` and uses the `reallocator` to extend the array when necessary. 1.88 +Finally, the size, capacity, and the pointer to the array are all updated and the function returns 1.89 +`CX_ARRAY_COPY_SUCCESS`. 1.90 + 1.91 +The third, but extremely rare, return code is `CX_ARRAY_COPY_REALLOC_FAILED` and speaks for itself. 1.92 + 1.93 +A few things to note: 1.94 +* `*target` and `src` can point to the same memory region, effectively copying elements within the array with `memmove` 1.95 +* `*target` does not need to point to the start of the array, but `size` and `capacity` always start counting from the 1.96 + position, `*target` points to - in this scenario, specifying a `reallocator` is forbidden for obvious reasons 1.97 +* `index` does not need to be within size of the current array, if `capacity` is specified 1.98 +* `index` does not even need to be within the capacity of the array, if `reallocator` is specified 1.99 + 1.100 + 1.101 ## Map 1.102 1.103 *Header file:* [map.h](api/map_8h.html)