UNIXworkcode

1 # Linked List 2 3 On top of implementing the list interface, this header also defines several low-level functions that 4 work with arbitrary structures. 5 6 The high-level [list interface](list.h.md) is documented on a separate page and explains how lists are used 7 that are created by one of the following functions. 8 9 ```C 10 #include <cx/linked_list.h> 11 12 typedef struct cx_linked_list_s cx_linked_list; 13 14 CxList *cxLinkedListCreate(const CxAllocator *allocator, 15 cx_compare_func comparator, size_t elem_size); 16 17 CxList *cxLinkedListCreateSimple(size_t elem_size); 18 ``` 19 20 If you are using high-level linked lists to implement your own list structure, 21 it might be necessary to store additional data in each node that does not belong to the elements. 22 For this purpose, there exists the following function. 23 24 ```C 25 void cx_linked_list_extra_data(cx_linked_list *list, size_t len); 26 ``` 27 28 It instructs the linked list to allocate `len` bytes of extra data when allocating a node. 29 The location offset of the extra data is stored in the `loc_extra` field of the linked list. 30 31 > The [key/value list](kv_list.h.md) uses this technique to store the `CxHashKey` as extra data in each node. 32 33 ## Basic Structure 34 35 This section and the remaining content of this page describe the low-level functions for linked lists. 36 37 Those work with nodes that have the following structure. 38 39 ```C 40 struct node { 41 node *next; 42 node *prev; // optional 43 // ... the element data goes here ... 44 }; 45 ``` 46 47 Each node must have at least one pointer that contains the address of the subsequent node. 48 Optionally, for doubly linked lists, there may be a second pointer that points to the predecessor. 49 50 The functions usually expect a `loc_prev` and a `loc_next` offset. 51 In the example structure from above you can obtain them with `offsetof(struct node, next)` and `offsetof(struct node, prev)`. 52 In all functions, `loc_prev` is optional in the sense, that when you do not have a `prev` pointer, you can specify a negative value. 53 When a function expects a `loc_advance` offset, you can freely choose if you want to pass the offset of the `next` or the `prev` pointer, 54 depending on what you want to do. 55 56 If a function expects a `void** begin` and a `void** end` pointer, they are usually both optional, unless otherwise specified. 57 If non-`NULL`, they point to the variables where the addresses of the first, or the last, node of a list are stored, respectively. 58 When a list operation results in a new first (or last) node, the addresses are overwritten. 59 In simple scenarios, you usually keep a pointer to the beginning of a list, and hence you would usually pass `NULL` to the `end` argument. 60 If you are designing a stack-like linked-list, it may happen that you only want to store the last node of a list (the top of stack), 61 hence passing `NULL` to the `begin` argument and the address of your top-of-stack pointer to the `end` argument. 62 Either way, most functions allow you a big deal of flexibility — please still read the documentation of each function carefully to learn which combinations are allowed. 63 64 When you are working with a singly linked list, it is still sometimes necessary to access the predecessor of a node. 65 In the absence of a `prev` pointer, the only chance is to start at the beginning of the list and search for that node. 66 This is exactly what `cx_linked_list_prev()` does. 67 ```C 68 #include <cx/linked_list.h> 69 70 void *cx_linked_list_prev(const void *begin, 71 ptrdiff_t loc_next, const void *node); 72 ``` 73 74 Starting with the `begin` node, the function checks if the next node is exactly the `node` (by pointer-comparison). 75 If true, the function terminates and returns the current node. 76 Otherwise, it moves on with the search. 77 If `begin` is already the searched `node`, this function immediately returns `NULL` as there is no predecessor. 78 Note carefully that the behavior of this function is not defined when `node` is not contained in the list that starts with `begin`. 79 80 > It is advisable to use the low-level functions inside own custom functions that you define particularly for your lists. 81 > Otherwise you will get a lot of boilerplate code when specifying the offsets to the pointers in your node structure in every call 82 > across your entire program. 83 84 ## Link and Unlink 85 86 ```C 87 #include <cx/linked_list.h> 88 89 void cx_linked_list_link(void *left, void *right, 90 ptrdiff_t loc_prev, ptrdiff_t loc_next); 91 92 void cx_linked_list_unlink(void *left, void *right, 93 ptrdiff_t loc_prev, ptrdiff_t loc_next); 94 ``` 95 96 When you have two nodes `left` and `right` you can link or unlink them with the functions shown above. 97 98 When linking `left` and `right` you should make sure that `left` as currently no successor and `right` has no predecessor, 99 because the pointers will be overwritten without unlinking possible existing links, first. 100 101 On the other hand, when unlinking `left` and `right`, they must actually be linked right now. 102 This is even asserted in debug builds. 103 104 Usually you should not need those functions when working with the [insert](#insert) and [remove](#remove) functions below. 105 106 ## Insert 107 108 ```C 109 #include <cx/linked_list.h> 110 111 void cx_linked_list_add(void **begin, void **end, 112 ptrdiff_t loc_prev, ptrdiff_t loc_next, 113 void *new_node); 114 115 void cx_linked_list_prepend(void **begin, void **end, 116 ptrdiff_t loc_prev, ptrdiff_t loc_next, 117 void *new_node); 118 119 void cx_linked_list_insert(void **begin, void **end, 120 ptrdiff_t loc_prev, ptrdiff_t loc_next, 121 void *node, void *new_node); 122 123 void cx_linked_list_insert_chain(void **begin, void **end, 124 ptrdiff_t loc_prev, ptrdiff_t loc_next, 125 void *node, void *insert_begin, void *insert_end); 126 127 void cx_linked_list_insert_sorted(void **begin, void **end, 128 ptrdiff_t loc_prev, ptrdiff_t loc_next, 129 void *new_node, cx_compare_func cmp_func); 130 131 void cx_linked_list_insert_sorted_chain(void **begin, void **end, 132 ptrdiff_t loc_prev, ptrdiff_t loc_next, 133 void *insert_begin, cx_compare_func cmp_func); 134 135 int cx_linked_list_insert_unique(void **begin, void **end, 136 ptrdiff_t loc_prev, ptrdiff_t loc_next, 137 void *new_node, cx_compare_func cmp_func); 138 139 void *cx_linked_list_insert_unique_chain(void **begin, void **end, 140 ptrdiff_t loc_prev, ptrdiff_t loc_next, 141 void *insert_begin, cx_compare_func cmp_func); 142 ``` 143 144 The above functions can be used to insert one or more elements into a linked list. 145 146 The functions `cx_linked_list_add()` and `cx_linked_list_prepend()` add the `new_node` to the beginning, or the end, of the list, respectively. 147 Either `begin` or `end` needs to be non-`NULL`. 148 If you pass `NULL` to `end` in `cx_linked_list_add()`, you have to specify `begin` and `loc_next`, instead. 149 On the other hand, if you pass `NULL` to `begin` in `cx_linked_list_prepend()`, you have to specify `end` and `loc_prev`, instead. 150 151 The function `cx_linked_list_insert()` behaves like `cx_linked_list_insert_chain()` where both 152 `insert_begin` and `insert_end` are set to `new_node`. 153 154 The function `cx_linked_list_insert_chain()` inserts the chain of nodes starting with `insert_begin` after the node `node`. 155 If `insert_end` is `NULL`, the end is automatically detected, in which case `loc_next` must be available. 156 If you pass `NULL` to `node`, the entire chain is prepended to the list, in which case either `begin` must be non-`NULL`, 157 or `end` must be non-`NULL` and `loc_prev` must be available to determine the start of the list. 158 159 The functions `cx_linked_list_insert_sorted()` and `cx_linked_list_insert_sorted_chain()` are equivalent, 160 except that `begin` and `loc_next` are always required, and the target list must already be sorted. 161 The order is determined by the `cmp_func` to which the pointers to the nodes are passed. 162 163 The functions `cx_linked_list_insert_unique()` and `cx_linked_list_insert_unique_chain()` are similar to 164 `cx_linked_list_insert_sorted()` and `cx_linked_list_insert_sorted_chain()`, except that they only insert the node 165 if it is not already contained in the list. 166 When a duplicate is found, `cx_linked_list_insert_unique()` returns non-zero and `cx_linked_list_insert_unique_chain()` 167 returns a pointer to a new chain starting with the first node that was not inserted. 168 169 > The `cx_linked_list_insert_sorted_chain()` function does not have an `insert_end` argument, because 170 > it cannot take advantage of simply inserting the entire chain as-is, as the chain might need to be broken 171 > to maintain the sort order. 172 173 ## Access and Find 174 175 ```C 176 #include <cx/linked_list.h> 177 178 void *cx_linked_list_first(const void *node, ptrdiff_t loc_prev); 179 180 void *cx_linked_list_last(const void *node, ptrdiff_t loc_next); 181 182 void *cx_linked_list_at(const void *start, 183 size_t start_index, ptrdiff_t loc_advance, size_t index); 184 185 void *cx_linked_list_find(const void *start, 186 ptrdiff_t loc_advance, ptrdiff_t loc_data, 187 cx_compare_func cmp_func, 188 const void *elem, size_t *found_index); 189 190 size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next); 191 ``` 192 193 The functions `cx_linked_list_first()` and `cx_linked_list_last()` can be used to find the first, or last, 194 node in your list in case you are not keeping track of them separately. 195 They can start at an arbitrary node within the list. 196 197 The function `cx_linked_list_at()` starts at an arbitrary node `start` which is _specified_ to have the index `start_index`, 198 and finds the node at `index`. 199 If `index` is larger than `start_index`, you must pass the offset of the `next` pointer to `loc_advanced`. 200 On the other hand, if `index` is smaller than `start_index`, you must pass the offset of the `prev` pointer. 201 If both indices match, the function simply returns `start`. 202 And if `index` is out-of-bounds, the function returns `NULL`. 203 204 The function `cx_linked_list_find()` starts a search at the `start` node and compares each element with `elem`. 205 If `loc_data` is non-zero, the data-type of `elem` must be a pointer to data which is compatible to the data located at the specified offset in the node. 206 If `loc_data` is zero, `elem` is expected to point to a node structure (which is usually artificially created for the sake of comparison and not contained in the list). 207 When the searched element is found, a pointer to the node is returned and the index (assuming `start` has index zero) is written to the optional `found_index`, if non-`NULL`. 208 209 The size of a list, or sub-list, can be determined with `cx_linked_list_size()` which may start at an arbitrary `node´ in the list. 210 211 > A creative way of using `cx_linked_list_size()` in doubly-linked lists is to use the offset of the `prev` pointer 212 > for `loc_next`, in which case the function will return the index of the node within the list plus one. 213 214 ## Remove 215 216 ```C 217 #include <cx/linked_list.h> 218 219 void cx_linked_list_remove(void **begin, void **end, 220 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node); 221 222 size_t cx_linked_list_remove_chain(void **begin, void **end, 223 ptrdiff_t loc_prev, ptrdiff_t loc_next, 224 void *node, size_t num); 225 ``` 226 227 You can either remove a single element or a specified number of subsequent elements from the list. 228 229 The function `cx_linked_list_remove()` is equivalent to `cx_linked_list_remove_chain()` where `num` is set to one. 230 231 The function `cx_linked_list_remove_chain()` removes up to `num` number of nodes from the list where `node` is contained, including `node` itself. 232 It returns the actual number of removed elements, which might be smaller when the list does not contain at least `num` elements. 233 234 The `prev` and `next` pointers of _all_ removed nodes are kept completely intact, allowing traversal within the removed chain, 235 as well as identifying the formerly adjacent nodes with the list from which the chain was removed. 236 237 > Both `begin` and `end` pointers are optional, if you specify both `loc_prev` and `loc_next`. 238 > In case your list does not have a `prev` pointer, specifying `begin` is mandatory (because there would be no other way to determine the predecessor of `node`). 239 >{style="note"} 240 241 > While specifying _only_ `loc_prev` and `end` is technically illegal, you can simply swap roles 242 > and use the offset of your `prev` pointer as `loc_next` and the address of your `end` pointer as `begin`. 243 > The list is then traversed backwards, but otherwise everything works as expected. 244 245 ## Reorder 246 247 ```C 248 #include <cx/linked_list.h> 249 250 void cx_linked_list_reverse(void **begin, void **end, 251 ptrdiff_t loc_prev, ptrdiff_t loc_next); 252 253 void cx_linked_list_sort(void **begin, void **end, 254 ptrdiff_t loc_prev, ptrdiff_t loc_next, 255 ptrdiff_t loc_data, cx_compare_func cmp_func); 256 ``` 257 258 The function `cx_linked_list_reverse()` swaps all links of all nodes in the specified list, effectively reversing the order of elements. 259 260 The function `cx_linked_list_sort()` uses a recursive _natural mergesort_ implementation to sort the list with respect to the specified `cmp_fnc`. 261 The non-negative `loc_data` offset is used to calculate the pointers that are passed to the compare function. 262 If you choose `loc_data` to be zero, the pointers to the nodes themselves are passed. 263 264 > The `begin` pointer is required in all of the above functions while the `end` pointer is still optional. 265 > {style="note"} 266 267 > Sorting uses [small buffer optimization](install.md#small-buffer-optimizations) for small list sizes. 268 > If a list contains no more than `CX_LINKED_LIST_SORT_SBO_SIZE` number of elements, no additional heap memory is allocated during the entire operation. 269 > Otherwise, merge operations still do not allocate extra memory as long as the length of the merged sub-list is not larger. 270 271 ## Compare 272 273 ```C 274 #include <cx/linked_list.h> 275 276 int cx_linked_list_compare( 277 const void *begin_left, const void *begin_right, 278 ptrdiff_t loc_advance, ptrdiff_t loc_data, 279 cx_compare_func cmp_func 280 ); 281 ``` 282 283 For comparing two linked list, you need to specify where to start, 284 and the offsets for the pointer to the next node and the data. 285 286 In the natural case, `begin_left` and `begin_right` point to the first node of either list, 287 and `loc_advance` is the offset of the `next` pointer. 288 But it is also possible to start with the _last_ node of both lists and use the `prev` pointer to compare them backwards. 289 290 The `loc_data` offset is used to calculate the pointer that is passed to the `cmp_fnc`. 291 This can either be the offset of a specific field in the struct or simply zero, in which case the pointers to the nodes themselves are passed to the compare function. 292 293 <seealso> 294 <category ref="apidoc"> 295 <a href="https://ucx.sourceforge.io/api/linked__list_8h.html">linked_list.h</a> 296 </category> 297 </seealso> 298