|
1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
|
3 * |
|
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. |
|
5 * |
|
6 * Redistribution and use in source and binary forms, with or without |
|
7 * modification, are permitted provided that the following conditions are met: |
|
8 * |
|
9 * 1. Redistributions of source code must retain the above copyright |
|
10 * notice, this list of conditions and the following disclaimer. |
|
11 * |
|
12 * 2. Redistributions in binary form must reproduce the above copyright |
|
13 * notice, this list of conditions and the following disclaimer in the |
|
14 * documentation and/or other materials provided with the distribution. |
|
15 * |
|
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
|
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
|
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
|
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
|
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
|
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
|
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
|
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
|
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
|
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
|
26 * POSSIBILITY OF SUCH DAMAGE. |
|
27 */ |
|
28 /** |
|
29 * \file linked_list.h |
|
30 * \brief Linked list implementation. |
|
31 * \details Also provides several low-level functions for custom linked list implementations. |
|
32 * \author Mike Becker |
|
33 * \author Olaf Wintermann |
|
34 * \version 3.0 |
|
35 * \copyright 2-Clause BSD License |
|
36 */ |
|
37 |
|
38 #ifndef UCX_LINKED_LIST_H |
|
39 #define UCX_LINKED_LIST_H |
|
40 |
|
41 #include "common.h" |
|
42 #include "list.h" |
|
43 |
|
44 #ifdef __cplusplus |
|
45 extern "C" { |
|
46 #endif |
|
47 |
|
48 /** |
|
49 * Allocates a linked list for storing elements with \p item_size bytes each. |
|
50 * |
|
51 * @remark Elements added to the list are copied, therefore a possible destructor |
|
52 * MUST NOT free the memory pointed to by its argument. |
|
53 * |
|
54 * @param allocator the allocator for allocating the list nodes |
|
55 * @param comparator the comparator for the elements |
|
56 * @param item_size the size of each element in bytes |
|
57 * @return the created list |
|
58 */ |
|
59 CxList *cxLinkedListCreate( |
|
60 CxAllocator const *allocator, |
|
61 CxListComparator comparator, |
|
62 size_t item_size |
|
63 ) __attribute__((__nonnull__)); |
|
64 |
|
65 /** |
|
66 * Allocates a linked list for storing pointers. |
|
67 * |
|
68 * If you want to store the elements directly in this list, use cxLinkedListCreate(). |
|
69 * |
|
70 * @remark Since only pointers are stored in this list, a possible destructor |
|
71 * MAY free the memory pointed to by its argument in order to prevent memory leaks. |
|
72 * |
|
73 * @param allocator the allocator for allocating the list nodes |
|
74 * @param comparator the comparator for the elements |
|
75 * @return the created list |
|
76 */ |
|
77 CxList *cxPointerLinkedListCreate( |
|
78 CxAllocator const *allocator, |
|
79 CxListComparator comparator |
|
80 ) __attribute__((__nonnull__)); |
|
81 |
|
82 /** |
|
83 * Creates a linked list using the data from an array. |
|
84 * |
|
85 * @remark Elements added to the list are copied, therefore a possible destructor |
|
86 * MUST NOT free the memory pointed to by its argument. |
|
87 * |
|
88 * @param allocator the allocator for allocating the list nodes |
|
89 * @param comparator the comparator for the elements |
|
90 * @param item_size the size of one item in the array |
|
91 * @param num_items the number of items |
|
92 * @param array the array data |
|
93 * @return the created list |
|
94 */ |
|
95 CxList *cxLinkedListFromArray( |
|
96 CxAllocator const *allocator, |
|
97 CxListComparator comparator, |
|
98 size_t item_size, |
|
99 size_t num_items, |
|
100 void const *array |
|
101 ) __attribute__((__nonnull__)); |
|
102 |
|
103 /** |
|
104 * Finds the node at a certain index. |
|
105 * |
|
106 * This function can be used to start at an arbitrary position within the list. |
|
107 * If the search index is large than the start index, \p loc_advance must denote |
|
108 * the location of some sort of \c next pointer (i.e. a pointer to the next node). |
|
109 * But it is also possible that the search index is smaller than the start index |
|
110 * (e.g. in cases where traversing a list backwards is faster) in which case |
|
111 * \p loc_advance must denote the location of some sort of \c prev pointer |
|
112 * (i.e. a pointer to the previous node). |
|
113 * |
|
114 * @param start a pointer to the start node |
|
115 * @param start_index the start index |
|
116 * @param loc_advance the location of the pointer to advance |
|
117 * @param index the search index |
|
118 * @return the node found at the specified index |
|
119 */ |
|
120 void *cx_linked_list_at( |
|
121 void const *start, |
|
122 size_t start_index, |
|
123 ptrdiff_t loc_advance, |
|
124 size_t index |
|
125 ) __attribute__((__nonnull__)); |
|
126 |
|
127 /** |
|
128 * Finds the index of an element within a linked list. |
|
129 * |
|
130 * @param start a pointer to the start node |
|
131 * @param loc_advance the location of the pointer to advance |
|
132 * @param loc_data the location of the \c data pointer within your node struct |
|
133 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. |
|
134 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. |
|
135 * @param cmp_func a compare function to compare \p elem against the node data |
|
136 * @param elem a pointer to the element to find |
|
137 * @return the index of the element or a past-one index if the element could not be found |
|
138 */ |
|
139 size_t cx_linked_list_find( |
|
140 void const *start, |
|
141 ptrdiff_t loc_advance, |
|
142 ptrdiff_t loc_data, |
|
143 bool follow_ptr, |
|
144 CxListComparator cmp_func, |
|
145 void const *elem |
|
146 ) __attribute__((__nonnull__)); |
|
147 |
|
148 /** |
|
149 * Finds the first node in a linked list. |
|
150 * |
|
151 * The function starts with the pointer denoted by \p node and traverses the list |
|
152 * along a prev pointer whose location within the node struct is |
|
153 * denoted by \p loc_prev. |
|
154 * |
|
155 * @param node a pointer to a node in the list |
|
156 * @param loc_prev the location of the \c prev pointer |
|
157 * @return a pointer to the first node |
|
158 */ |
|
159 void *cx_linked_list_first( |
|
160 void const *node, |
|
161 ptrdiff_t loc_prev |
|
162 ) __attribute__((__nonnull__)); |
|
163 |
|
164 /** |
|
165 * Finds the last node in a linked list. |
|
166 * |
|
167 * The function starts with the pointer denoted by \p node and traverses the list |
|
168 * along a next pointer whose location within the node struct is |
|
169 * denoted by \p loc_next. |
|
170 * |
|
171 * @param node a pointer to a node in the list |
|
172 * @param loc_next the location of the \c next pointer |
|
173 * @return a pointer to the last node |
|
174 */ |
|
175 void *cx_linked_list_last( |
|
176 void const *node, |
|
177 ptrdiff_t loc_next |
|
178 ) __attribute__((__nonnull__)); |
|
179 |
|
180 /** |
|
181 * Finds the predecessor of a node in case it is not linked. |
|
182 * |
|
183 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined. |
|
184 * |
|
185 * @param begin the node where to start the search |
|
186 * @param loc_next the location of the \c next pointer |
|
187 * @param node the successor of the node to find |
|
188 * @return the node or \c NULL if \p node has no predecessor |
|
189 */ |
|
190 void *cx_linked_list_prev( |
|
191 void const *begin, |
|
192 ptrdiff_t loc_next, |
|
193 void const *node |
|
194 ) __attribute__((__nonnull__)); |
|
195 |
|
196 /** |
|
197 * Adds a new node to a linked list. |
|
198 * The node must not be part of any list already. |
|
199 * |
|
200 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both. |
|
201 * |
|
202 * @param begin a pointer to the begin node pointer (if your list has one) |
|
203 * @param end a pointer to the end node pointer (if your list has one) |
|
204 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
|
205 * @param loc_next the location of a \c next pointer within your node struct (required) |
|
206 * @param new_node a pointer to the node that shall be appended |
|
207 */ |
|
208 void cx_linked_list_add( |
|
209 void **begin, |
|
210 void **end, |
|
211 ptrdiff_t loc_prev, |
|
212 ptrdiff_t loc_next, |
|
213 void *new_node |
|
214 ) __attribute__((__nonnull__(5))); |
|
215 |
|
216 /** |
|
217 * Prepends a new node to a linked list. |
|
218 * The node must not be part of any list already. |
|
219 * |
|
220 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both. |
|
221 * |
|
222 * @param begin a pointer to the begin node pointer (if your list has one) |
|
223 * @param end a pointer to the end node pointer (if your list has one) |
|
224 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
|
225 * @param loc_next the location of a \c next pointer within your node struct (required) |
|
226 * @param new_node a pointer to the node that shall be prepended |
|
227 */ |
|
228 void cx_linked_list_prepend( |
|
229 void **begin, |
|
230 void **end, |
|
231 ptrdiff_t loc_prev, |
|
232 ptrdiff_t loc_next, |
|
233 void *new_node |
|
234 ) __attribute__((__nonnull__(5))); |
|
235 |
|
236 /** |
|
237 * Links two nodes. |
|
238 * |
|
239 * @param left the new predecessor of \p right |
|
240 * @param right the new successor of \p left |
|
241 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
|
242 * @param loc_next the location of a \c next pointer within your node struct (required) |
|
243 */ |
|
244 void cx_linked_list_link( |
|
245 void *left, |
|
246 void *right, |
|
247 ptrdiff_t loc_prev, |
|
248 ptrdiff_t loc_next |
|
249 ) __attribute__((__nonnull__)); |
|
250 |
|
251 /** |
|
252 * Unlinks two nodes. |
|
253 * |
|
254 * If right is not the successor of left, the behavior is undefined. |
|
255 * |
|
256 * @param left the predecessor of \p right |
|
257 * @param right the successor of \p left |
|
258 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
|
259 * @param loc_next the location of a \c next pointer within your node struct (required) |
|
260 */ |
|
261 void cx_linked_list_unlink( |
|
262 void *left, |
|
263 void *right, |
|
264 ptrdiff_t loc_prev, |
|
265 ptrdiff_t loc_next |
|
266 ) __attribute__((__nonnull__)); |
|
267 |
|
268 /** |
|
269 * Inserts a new node after a given node of a linked list. |
|
270 * The new node must not be part of any list already. |
|
271 * |
|
272 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or |
|
273 * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list. |
|
274 * |
|
275 * @param begin a pointer to the begin node pointer (if your list has one) |
|
276 * @param end a pointer to the end node pointer (if your list has one) |
|
277 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
|
278 * @param loc_next the location of a \c next pointer within your node struct (required) |
|
279 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list) |
|
280 * @param new_node a pointer to the node that shall be prepended |
|
281 */ |
|
282 void cx_linked_list_insert( |
|
283 void **begin, |
|
284 void **end, |
|
285 ptrdiff_t loc_prev, |
|
286 ptrdiff_t loc_next, |
|
287 void *node, |
|
288 void *new_node |
|
289 ) __attribute__((__nonnull__(6))); |
|
290 |
|
291 /** |
|
292 * Inserts a chain of nodes after a given node of a linked list. |
|
293 * The chain must not be part of any list already. |
|
294 * |
|
295 * If you do not explicitly specify the end of the chain, it will be determined by traversing |
|
296 * the \c next pointer. |
|
297 * |
|
298 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or |
|
299 * the \p end pointer to determine the start of the list. If only the \p end pointer is specified, you also need |
|
300 * to provide a valid \p loc_prev location. |
|
301 * Then the chain will be prepended to the list. |
|
302 * |
|
303 * @param begin a pointer to the begin node pointer (if your list has one) |
|
304 * @param end a pointer to the end node pointer (if your list has one) |
|
305 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
|
306 * @param loc_next the location of a \c next pointer within your node struct (required) |
|
307 * @param node the node after which to insert (\c NULL to prepend the chain to the list) |
|
308 * @param insert_begin a pointer to the first node of the chain that shall be inserted |
|
309 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) |
|
310 */ |
|
311 void cx_linked_list_insert_chain( |
|
312 void **begin, |
|
313 void **end, |
|
314 ptrdiff_t loc_prev, |
|
315 ptrdiff_t loc_next, |
|
316 void *node, |
|
317 void *insert_begin, |
|
318 void *insert_end |
|
319 ) __attribute__((__nonnull__(6))); |
|
320 |
|
321 /** |
|
322 * Removes a node from the linked list. |
|
323 * |
|
324 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end) |
|
325 * addresses are provided, the pointers are adjusted accordingly. |
|
326 * |
|
327 * The following combinations of arguments are valid (more arguments are optional): |
|
328 * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance) |
|
329 * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance) |
|
330 * |
|
331 * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used |
|
332 * to traverse to a former adjacent node in the list. |
|
333 * |
|
334 * @param begin a pointer to the begin node pointer (optional) |
|
335 * @param end a pointer to the end node pointer (optional) |
|
336 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
|
337 * @param loc_next the location of a \c next pointer within your node struct (required) |
|
338 * @param node the node to remove |
|
339 */ |
|
340 void cx_linked_list_remove( |
|
341 void **begin, |
|
342 void **end, |
|
343 ptrdiff_t loc_prev, |
|
344 ptrdiff_t loc_next, |
|
345 void *node |
|
346 ) __attribute__((__nonnull__(5))); |
|
347 |
|
348 |
|
349 /** |
|
350 * Determines the size of a linked list starting with \p node. |
|
351 * @param node the first node |
|
352 * @param loc_next the location of the \c next pointer within the node struct |
|
353 * @return the size of the list or zero if \p node is \c NULL |
|
354 */ |
|
355 size_t cx_linked_list_size( |
|
356 void const *node, |
|
357 ptrdiff_t loc_next |
|
358 ); |
|
359 |
|
360 /** |
|
361 * Sorts a linked list based on a comparison function. |
|
362 * |
|
363 * This function can work with linked lists of the following structures: |
|
364 * \code |
|
365 * typedef struct node node; |
|
366 * struct node { |
|
367 * node* prev; |
|
368 * node* next; |
|
369 * my_payload data; // in this case set follow_ptr = 0 |
|
370 * } |
|
371 * |
|
372 * typedef struct ptr_node ptr_node; |
|
373 * struct ptr_node { |
|
374 * ptr_node* prev; |
|
375 * ptr_node* next; |
|
376 * my_payload* data; // in this case set follow_ptr = 1 |
|
377 * } |
|
378 * \endcode |
|
379 * |
|
380 * @note This is a recursive function with at most logarithmic recursion depth. |
|
381 * |
|
382 * @param begin a pointer to the begin node pointer (required) |
|
383 * @param end a pointer to the end node pointer (optional) |
|
384 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present) |
|
385 * @param loc_next the location of a \c next pointer within your node struct (required) |
|
386 * @param loc_data the location of the \c data pointer within your node struct |
|
387 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. |
|
388 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. |
|
389 * @param cmp_func the compare function defining the sort order |
|
390 */ |
|
391 void cx_linked_list_sort( |
|
392 void **begin, |
|
393 void **end, |
|
394 ptrdiff_t loc_prev, |
|
395 ptrdiff_t loc_next, |
|
396 ptrdiff_t loc_data, |
|
397 bool follow_ptr, |
|
398 CxListComparator cmp_func |
|
399 ) __attribute__((__nonnull__(1, 7))); |
|
400 |
|
401 |
|
402 /** |
|
403 * Compares two lists element wise. |
|
404 * |
|
405 * The \c follow_ptr flags have the following meaning: if \c false, the pointer denoted by \p loc_data shall |
|
406 * directly be passed to the \p cmp_func. |
|
407 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. |
|
408 * |
|
409 * \note Both list must have the same structure. |
|
410 * |
|
411 * @param begin_left the begin of the left list (\c NULL denotes an empty list) |
|
412 * @param begin_right the begin of the right list (\c NULL denotes an empty list) |
|
413 * @param loc_advance the location of the pointer to advance |
|
414 * @param loc_data the location of the \c data pointer within your node struct |
|
415 * @param follow_ptr_left indicates whether pointers in the left list shall be dereferenced |
|
416 * @param follow_ptr_right indicates whether pointers in the right list shall be dereferenced |
|
417 * @param cmp_func the function to compare the elements |
|
418 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the |
|
419 * right list, positive if the left list is larger than the right list, zero if both lists are equal. |
|
420 */ |
|
421 int cx_linked_list_compare( |
|
422 void const *begin_left, |
|
423 void const *begin_right, |
|
424 ptrdiff_t loc_advance, |
|
425 ptrdiff_t loc_data, |
|
426 bool follow_ptr_left, |
|
427 bool follow_ptr_right, |
|
428 CxListComparator cmp_func |
|
429 ) __attribute__((__nonnull__(7))); |
|
430 |
|
431 /** |
|
432 * Reverses the order of the nodes in a linked list. |
|
433 * |
|
434 * @param begin a pointer to the begin node pointer (required) |
|
435 * @param end a pointer to the end node pointer (optional) |
|
436 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
|
437 * @param loc_next the location of a \c next pointer within your node struct (required) |
|
438 */ |
|
439 void cx_linked_list_reverse( |
|
440 void **begin, |
|
441 void **end, |
|
442 ptrdiff_t loc_prev, |
|
443 ptrdiff_t loc_next |
|
444 ) __attribute__((__nonnull__(1))); |
|
445 |
|
446 #ifdef __cplusplus |
|
447 } /* extern "C" */ |
|
448 #endif |
|
449 |
|
450 #endif /* UCX_LINKED_LIST_H */ |