Mercurial > hg > ucx / file comparison

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

docs/Writerside/topics/linked_list.h.md

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

Mercurial Repository: ucx

mercurial