Mercurial > hg > ucx / file comparison

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

docs/Writerside/topics/linked_list.h.md

changeset 1694
a2757c6427cc
parent 1639
5c3e6477aab4
equal deleted inserted replaced
1693:c2d05cf1a062 1694:a2757c6427cc
45 Each node must have at least one pointer that contains the address of the subsequent node. 45 Each node must have at least one pointer that contains the address of the subsequent node.
46 Optionally, for doubly linked lists, there may be a second pointer that points to the predecessor. 46 Optionally, for doubly linked lists, there may be a second pointer that points to the predecessor.
47 47
48 The functions usually expect a `loc_prev` and a `loc_next` offset. 48 The functions usually expect a `loc_prev` and a `loc_next` offset.
49 In the example structure from above you can obtain them with `offsetof(struct node, next)` and `offsetof(struct node, prev)`. 49 In the example structure from above you can obtain them with `offsetof(struct node, next)` and `offsetof(struct node, prev)`.
50 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. 50 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.
51 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, 51 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,
52 depending on what you want to do. 52 depending on what you want to do.
53 53
54 If a function expects a `void** begin` and a `void** end` pointer, they are usually both optional, unless otherwise specified. 54 If a function expects a `void** begin` and a `void** end` pointer, they are usually both optional, unless otherwise specified.
55 If non-`NULL`, they point to the variables where the addresses of the first, or the last, node of a list are stored, respectively. 55 If non-`NULL`, they point to the variables where the addresses of the first, or the last, node belonging to the list are stored, respectively.
56 When a list operation results in a new first (or last) node, the addresses are overwritten. 56 When a list operation results in a new first (or last) node, the addresses are overwritten.
57 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. 57 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.
58 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), 58 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),
59 hence passing `NULL` to the `begin` argument and the address of your top-of-stack pointer to the `end` argument. 59 hence passing `NULL` to the `begin` and the address of your top-of-stack pointer to the `end`.
60 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. 60 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.
61 61
62 When you are working with a singly linked list, it is still sometimes necessary to access the predecessor of a node. 62 When you are working with a singly linked list, it is still sometimes necessary to access the predecessor of a node.
63 In the absence of a `prev` pointer, the only chance is to start at the beginning of the list and search for that node. 63 In the absence of a `prev` pointer, the only chance is to start at the beginning of the list and search for that node.
64 This is exactly what `cx_linked_list_prev()` does. 64 This is exactly what `cx_linked_list_prev()` does.
89 89
90 void cx_linked_list_unlink(void *left, void *right, 90 void cx_linked_list_unlink(void *left, void *right,
91 ptrdiff_t loc_prev, ptrdiff_t loc_next); 91 ptrdiff_t loc_prev, ptrdiff_t loc_next);
92 ``` 92 ```
93 93
94 When you have two nodes `left` and `right` you can link or unlink them with the functions shown above. 94 When you have two nodes `left` and `right`, you can link or unlink them with the functions shown above.
95 95
96 When linking `left` and `right` you should make sure that `left` as currently no successor and `right` has no predecessor, 96 When linking `left` and `right` you should make sure that `left` as currently no successor and `right` has no predecessor,
97 because the pointers will be overwritten without unlinking possible existing links, first. 97 because the pointers will be overwritten without unlinking possible existing links, first.
98 98
99 On the other hand, when unlinking `left` and `right`, they must actually be linked right now. 99 On the other hand, when unlinking `left` and `right`, they must actually be linked right now.
182 182
183 > The `cx_linked_list_insert_sorted_chain()` function does not have an `insert_end` argument, because 183 > The `cx_linked_list_insert_sorted_chain()` function does not have an `insert_end` argument, because
184 > it cannot take advantage of simply inserting the entire chain as-is, as the chain might need to be broken 184 > it cannot take advantage of simply inserting the entire chain as-is, as the chain might need to be broken
185 > to maintain the sort order. 185 > to maintain the sort order.
186 186
187 The functions with the `_c` suffix are equivalent, except that they accept a `cx_compare_func2` with additional `context`. 187 The functions with the `_c` suffix are equivalent, except that they accept a `cx_compare_func2` with an additional `context`.
188 188
189 ## Access and Find 189 ## Access and Find
190 190
191 ```C 191 ```C
192 #include <cx/linked_list.h> 192 #include <cx/linked_list.h>
213 213
214 The functions `cx_linked_list_first()` and `cx_linked_list_last()` can be used to find the first, or last, 214 The functions `cx_linked_list_first()` and `cx_linked_list_last()` can be used to find the first, or last,
215 node in your list in case you are not keeping track of them separately. 215 node in your list in case you are not keeping track of them separately.
216 They can start at an arbitrary node within the list. 216 They can start at an arbitrary node within the list.
217 217
218 The function `cx_linked_list_at()` starts at an arbitrary node `start` which is _specified_ to have the index `start_index`, 218 The function `cx_linked_list_at()` starts at an arbitrary node `start`, which is _specified_ to have the index `start_index`,
219 and finds the node at `index`. 219 and finds the node at `index`.
220 If `index` is larger than `start_index`, you must pass the offset of the `next` pointer to `loc_advanced`. 220 If `index` is larger than `start_index`, you must pass the offset of the `next` pointer to `loc_advanced`.
221 On the other hand, if `index` is smaller than `start_index`, you must pass the offset of the `prev` pointer. 221 On the other hand, if `index` is smaller than `start_index`, you must pass the offset of the `prev` pointer.
222 If both indices match, the function simply returns `start`. 222 If both indices match, the function simply returns `start`.
223 And if `index` is out-of-bounds, the function returns `NULL`. 223 And if `index` is out-of-bounds, the function returns `NULL`.
224 224
225 The function `cx_linked_list_find()` starts a search at the `start` node and compares each element with `elem`. 225 The function `cx_linked_list_find()` starts a search at the `start` node and compares each element with `elem`.
226 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. 226 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.
227 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). 227 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).
228 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`. 228 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`.
229 229
230 The function `cx_linked_list_find_c()` allows additional `context` for the compare function. 230 The function `cx_linked_list_find_c()` allows additional `context` for the compare function.
231 231
232 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. 232 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.
233 233
234 > A creative way of using `cx_linked_list_size()` in doubly-linked lists is to use the offset of the `prev` pointer 234 > A creative way of using `cx_linked_list_size()` in doubly linked lists is to use the offset of the `prev` pointer
235 > for `loc_next`, in which case the function will return the index of the node within the list plus one. 235 > for `loc_next`, in which case the function will return the index of the node within the list plus one.
236 236
237 ## Remove 237 ## Remove
238 238
239 ```C 239 ```C
255 It returns the actual number of removed elements, which might be smaller when the list does not contain at least `num` elements. 255 It returns the actual number of removed elements, which might be smaller when the list does not contain at least `num` elements.
256 256
257 The `prev` and `next` pointers of _all_ removed nodes are kept completely intact, allowing traversal within the removed chain, 257 The `prev` and `next` pointers of _all_ removed nodes are kept completely intact, allowing traversal within the removed chain,
258 as well as identifying the formerly adjacent nodes with the list from which the chain was removed. 258 as well as identifying the formerly adjacent nodes with the list from which the chain was removed.
259 259
260 > Both `begin` and `end` pointers are optional, if you specify both `loc_prev` and `loc_next`. 260 > Both `begin` and `end` pointers are optional if you specify both `loc_prev` and `loc_next`.
261 > 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`). 261 > 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`).
262 >{style="note"} 262 >{style="note"}
263 263
264 > While specifying _only_ `loc_prev` and `end` is technically illegal, you can simply swap roles 264 > While specifying _only_ `loc_prev` and `end` is technically illegal, you can swap their roles
265 > and use the offset of your `prev` pointer as `loc_next` and the address of your `end` pointer as `begin`. 265 > and use the offset of your `prev` pointer as `loc_next` and the address of your `end` pointer as `begin`.
266 > The list is then traversed backwards, but otherwise everything works as expected. 266 > The list is then traversed backwards, but otherwise everything works as expected.
267 267
268 ## Reorder 268 ## Reorder
269 269
289 The non-negative `loc_data` offset is used to calculate the pointers that are passed to the compare function. 289 The non-negative `loc_data` offset is used to calculate the pointers that are passed to the compare function.
290 If you choose `loc_data` to be zero, the pointers to the nodes themselves are passed. 290 If you choose `loc_data` to be zero, the pointers to the nodes themselves are passed.
291 291
292 The function `cx_linked_list_sort_c()` allows additional `context` for the compare function. 292 The function `cx_linked_list_sort_c()` allows additional `context` for the compare function.
293 293
294 > The `begin` pointer is required in all of the above functions while the `end` pointer is still optional. 294 > The `begin` pointer is required in all the above functions, while the `end` pointer is still optional.
295 > {style="note"} 295 > {style="note"}
296 296
297 > Sorting uses [small buffer optimization](install.md#small-buffer-optimizations) for small list sizes. 297 > Sorting uses [small buffer optimization](install.md#small-buffer-optimizations) for small list sizes.
298 > 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. 298 > 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.
299 > Otherwise, merge operations still do not allocate extra memory as long as the length of the merged sub-list is not larger. 299 > Otherwise, merge operations still do not allocate extra memory as long as the length of the merged sub-list is not larger.
321 321
322 In the natural case, `begin_left` and `begin_right` point to the first node of either list, 322 In the natural case, `begin_left` and `begin_right` point to the first node of either list,
323 and `loc_advance` is the offset of the `next` pointer. 323 and `loc_advance` is the offset of the `next` pointer.
324 But it is also possible to start with the _last_ node of both lists and use the `prev` pointer to compare them backwards. 324 But it is also possible to start with the _last_ node of both lists and use the `prev` pointer to compare them backwards.
325 325
326 The `loc_data` offset is used to calculate the pointer that is passed to the `cmp_func`. 326 The `loc_data` offset is used to calculate the pointer passed to the `cmp_func`.
327 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. 327 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.
328 328
329 The function `cx_linked_list_compare_c()` allows additional `context` for the compare function. 329 The function `cx_linked_list_compare_c()` allows additional `context` for the compare function.
330 330
331 <seealso> 331 <seealso>

Mercurial Repository: ucx

mercurial