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 * @author Mike Becker
32 * @author Olaf Wintermann
33 * @copyright 2-Clause BSD License
34 */
35
36 #ifndef UCX_LINKED_LIST_H
37 #define UCX_LINKED_LIST_H
38
39 #include "common.h"
40 #include "list.h"
41
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45
46 /**
47 * Metadata for a linked list.
48 */
49 typedef struct cx_linked_list_s {
50 /** Base members. */
51 struct cx_list_s base;
52 /**
53 * Location of the prev pointer (mandatory).
54 */
55 off_t loc_prev;
56 /**
57 * Location of the next pointer (mandatory).
58 */
59 off_t loc_next;
60 /**
61 * Location of the payload (mandatory).
62 */
63 off_t loc_data;
64 /**
65 * Location of extra data (optional).
66 * Negative when no extra data is requested.
67 * @see cx_linked_list_extra_data()
68 */
69 off_t loc_extra;
70 /**
71 * Additional bytes to allocate @em behind the payload (e.g. for metadata).
72 * @see cx_linked_list_extra_data()
73 */
74 size_t extra_data_len;
75 /**
76 * Pointer to the first node.
77 */
78 void *begin;
79 /**
80 * Pointer to the last node.
81 */
82 void *end;
83 } cx_linked_list;
84
85 /**
86 * Allocates a linked list for storing elements with @p elem_size bytes each.
87 *
88 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
89 * copies of the added elements, and the compare function will be automatically set
90 * to cx_cmp_ptr() if none is given.
91 *
92 * @param allocator the allocator for allocating the list nodes
93 * (if @c NULL, the cxDefaultAllocator will be used)
94 * @param comparator the comparator for the elements
95 * (if @c NULL, and the list is not storing pointers, sort and find
96 * functions will not work)
97 * @param elem_size the size of each element in bytes
98 * @return the created list
99 */
100 cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxListFree, 1)
101 CX_EXPORT CxList *cxLinkedListCreate(const CxAllocator *allocator,
102 cx_compare_func comparator, size_t elem_size);
103
104 /**
105 * Allocates a linked list for storing elements with @p elem_size bytes each.
106 *
107 * The list will use cxDefaultAllocator and no comparator function. If you want
108 * to call functions that need a comparator, you must either set one immediately
109 * after list creation or use cxLinkedListCreate().
110 *
111 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
112 * copies of the added elements, and the compare function will be automatically set
113 * to cx_cmp_ptr().
114 *
115 * @param elem_size (@c size_t) the size of each element in bytes
116 * @return (@c CxList*) the created list
117 */
118 #define cxLinkedListCreateSimple(elem_size) \
119 cxLinkedListCreate(NULL, NULL, elem_size)
120
121 /**
122 * Instructs the linked list to reserve extra data in each node.
123 *
124 * The extra data will be aligned and placed behind the element data.
125 * The exact location in the node is stored in the @c loc_extra field
126 * of the linked list.
127 *
128 * You should usually not use this function except when you are creating an
129 * own linked-list implementation that is based on the UCX linked list and
130 * needs to store extra data in each node.
131 *
132 * @param list the list (must be a linked list)
133 * @param len the length of the extra data
134 */
135 cx_attr_nonnull
136 CX_EXPORT void cx_linked_list_extra_data(cx_linked_list *list, size_t len);
137
138 /**
139 * Finds the node at a certain index.
140 *
141 * This function can be used to start at an arbitrary position within the list.
142 * If the search index is larger than the start index, @p loc_advance must denote
143 * the location of a @c next pointer (i.e., a pointer to the next node).
144 * But it is also possible that the search index is smaller than the start index
145 * (e.g., in cases where traversing a list backwards is faster).
146 * In that case @p loc_advance must denote the location of a @c prev pointer
147 * (i.e., a pointer to the previous node).
148 *
149 * @param start a pointer to the start node
150 * @param start_index the start index
151 * @param loc_advance the location of the pointer to advance
152 * @param index the search index
153 * @return the node found at the specified index
154 */
155 cx_attr_nonnull cx_attr_nodiscard
156 CX_EXPORT void *cx_linked_list_at(const void *start,size_t start_index,
157 ptrdiff_t loc_advance, size_t index);
158
159 /**
160 * Finds the node containing an element within a linked list.
161 *
162 * @param start a pointer to the start node
163 * @param loc_advance the location of the pointer to advance
164 * @param loc_data the location of the @c data pointer within your node struct
165 * @param cmp_func a compare function to compare @p elem against the node data
166 * @param elem a pointer to the element to find
167 * @param found_index an optional pointer where the index of the found node
168 * (given that @p start has index 0) is stored
169 * @return a pointer to the found node or @c NULL if no matching node was found
170 */
171 cx_attr_nonnull_arg(1, 4, 5)
172 CX_EXPORT void *cx_linked_list_find(const void *start, ptrdiff_t loc_advance,
173 ptrdiff_t loc_data, cx_compare_func cmp_func, const void *elem,
174 size_t *found_index);
175
176 /**
177 * Finds the first node in a linked list.
178 *
179 * The function starts with the pointer denoted by @p node and traverses the list
180 * along a prev pointer whose location within the node struct is
181 * denoted by @p loc_prev.
182 *
183 * @param node a pointer to a node in the list
184 * @param loc_prev the location of the @c prev pointer
185 * @return a pointer to the first node
186 */
187 cx_attr_nonnull cx_attr_returns_nonnull
188 CX_EXPORT void *cx_linked_list_first(const void *node, ptrdiff_t loc_prev);
189
190 /**
191 * Finds the last node in a linked list.
192 *
193 * The function starts with the pointer denoted by @p node and traverses the list
194 * along a next pointer whose location within the node struct is
195 * denoted by @p loc_next.
196 *
197 * @param node a pointer to a node in the list
198 * @param loc_next the location of the @c next pointer
199 * @return a pointer to the last node
200 */
201 cx_attr_nonnull cx_attr_returns_nonnull
202 CX_EXPORT void *cx_linked_list_last(const void *node, ptrdiff_t loc_next);
203
204 /**
205 * Finds the predecessor of a node in case it is not linked.
206 *
207 * @remark If @p node is not contained in the list starting with @p begin, the behavior is undefined.
208 *
209 * @param begin the node where to start the search
210 * @param loc_next the location of the @c next pointer
211 * @param node the successor of the node to find
212 * @return the node or @c NULL if @p node has no predecessor
213 */
214 cx_attr_nonnull
215 CX_EXPORT void *cx_linked_list_prev(const void *begin, ptrdiff_t loc_next, const void *node);
216
217 /**
218 * Adds a new node to a linked list.
219 * The node must not be part of any list yet.
220 *
221 * @remark One of the pointers @p begin or @p end may be @c NULL, but not both.
222 *
223 * @param begin a pointer to the beginning node pointer (if your list has one)
224 * @param end a pointer to the end node pointer (if your list has one)
225 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
226 * @param loc_next the location of a @c next pointer within your node struct (required)
227 * @param new_node a pointer to the node that shall be appended
228 */
229 cx_attr_nonnull_arg(5)
230 CX_EXPORT void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
231
232 /**
233 * Prepends a new node to a linked list.
234 * The node must not be part of any list yet.
235 *
236 * @remark One of the pointers @p begin or @p end may be @c NULL, but not both.
237 *
238 * @param begin a pointer to the beginning node pointer (if your list has one)
239 * @param end a pointer to the end node pointer (if your list has one)
240 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
241 * @param loc_next the location of a @c next pointer within your node struct (required)
242 * @param new_node a pointer to the node that shall be prepended
243 */
244 cx_attr_nonnull_arg(5)
245 CX_EXPORT void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
246
247 /**
248 * Links two nodes.
249 *
250 * @param left the new predecessor of @p right
251 * @param right the new successor of @p left
252 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
253 * @param loc_next the location of a @c next pointer within your node struct (required)
254 */
255 cx_attr_nonnull
256 CX_EXPORT void cx_linked_list_link(void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next);
257
258 /**
259 * Unlinks two nodes.
260 *
261 * If right is not the successor of left, the behavior is undefined.
262 *
263 * @param left the predecessor of @p right
264 * @param right the successor of @p left
265 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
266 * @param loc_next the location of a @c next pointer within your node struct (required)
267 */
268 cx_attr_nonnull
269 CX_EXPORT void cx_linked_list_unlink(void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next);
270
271 /**
272 * Inserts a new node after a given node of a linked list.
273 * The new node must not be part of any list yet.
274 *
275 * @note If you specify @c NULL as the @p node to insert after, this function needs either the @p begin or
276 * the @p end pointer to determine the start of the list. Then the new node will be prepended to the list.
277 *
278 * @param begin a pointer to the beginning node pointer (if your list has one)
279 * @param end a pointer to the end node pointer (if your list has one)
280 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
281 * @param loc_next the location of a @c next pointer within your node struct (required)
282 * @param node the node after which to insert (@c NULL if you want to prepend the node to the list)
283 * @param new_node a pointer to the node that shall be inserted
284 */
285 cx_attr_nonnull_arg(6)
286 CX_EXPORT void cx_linked_list_insert(void **begin, void **end,
287 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *new_node);
288
289 /**
290 * Inserts a chain of nodes after a given node of a linked list.
291 * The chain must not be part of any list yet.
292 *
293 * If you do not explicitly specify the end of the chain, it will be determined by traversing
294 * the @c next pointer.
295 *
296 * @note If you specify @c NULL as the @p node to insert after, this function needs either the @p begin or
297 * the @p end pointer to determine the start of the list. If only the @p end pointer is specified, you also need
298 * to provide a valid @p loc_prev location.
299 * Then the chain will be prepended to the list.
300 *
301 * @param begin a pointer to the beginning node pointer (if your list has one)
302 * @param end a pointer to the end node pointer (if your list has one)
303 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
304 * @param loc_next the location of a @c next pointer within your node struct (required)
305 * @param node the node after which to insert (@c NULL to prepend the chain to the list)
306 * @param insert_begin a pointer to the first node of the chain that shall be inserted
307 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
308 */
309 cx_attr_nonnull_arg(6)
310 CX_EXPORT void cx_linked_list_insert_chain(void **begin, void **end,
311 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *insert_begin, void *insert_end);
312
313 /**
314 * Inserts a node into a sorted linked list.
315 * The new node must not be part of any list yet.
316 *
317 * If the list starting with the node pointed to by @p begin is not sorted
318 * already, the behavior is undefined.
319 *
320 * @param begin a pointer to the beginning node pointer (required)
321 * @param end a pointer to the end node pointer (if your list has one)
322 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
323 * @param loc_next the location of a @c next pointer within your node struct (required)
324 * @param new_node a pointer to the node that shall be inserted
325 * @param cmp_func a compare function that will receive the node pointers
326 */
327 cx_attr_nonnull_arg(1, 5, 6)
328 CX_EXPORT void cx_linked_list_insert_sorted(void **begin, void **end,
329 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func);
330
331 /**
332 * Inserts a chain of nodes into a sorted linked list.
333 * The chain must not be part of any list yet.
334 *
335 * If either the list starting with the node pointed to by @p begin or the list
336 * starting with @p insert_begin is not sorted, the behavior is undefined.
337 *
338 * @attention In contrast to cx_linked_list_insert_chain(), the source chain
339 * will be broken and inserted into the target list so that the resulting list
340 * will be sorted according to @p cmp_func. That means each node in the source
341 * chain may be re-linked with nodes from the target list.
342 *
343 * @param begin a pointer to the beginning node pointer (required)
344 * @param end a pointer to the end node pointer (if your list has one)
345 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
346 * @param loc_next the location of a @c next pointer within your node struct (required)
347 * @param insert_begin a pointer to the first node of the chain that shall be inserted
348 * @param cmp_func a compare function that will receive the node pointers
349 */
350 cx_attr_nonnull_arg(1, 5, 6)
351 CX_EXPORT void cx_linked_list_insert_sorted_chain(void **begin, void **end,
352 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func);
353
354 /**
355 * Inserts a node into a sorted linked list if no other node with the same value already exists.
356 * The new node must not be part of any list yet.
357 *
358 * If the list starting with the node pointed to by @p begin is not sorted
359 * already, the behavior is undefined.
360 *
361 * @param begin a pointer to the beginning node pointer (required)
362 * @param end a pointer to the end node pointer (if your list has one)
363 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
364 * @param loc_next the location of a @c next pointer within your node struct (required)
365 * @param new_node a pointer to the node that shall be inserted
366 * @param cmp_func a compare function that will receive the node pointers
367 * @retval zero when the node was inserted
368 * @retval non-zero when a node with the same value already exists
369 */
370 cx_attr_nonnull_arg(1, 5, 6)
371 CX_EXPORT int cx_linked_list_insert_unique(void **begin, void **end,
372 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func);
373
374 /**
375 * Inserts a chain of nodes into a sorted linked list, avoiding duplicates.
376 * The chain must not be part of any list yet.
377 *
378 * If either the list starting with the node pointed to by @p begin or the list
379 * starting with @p insert_begin is not sorted, the behavior is undefined.
380 *
381 * @attention In contrast to cx_linked_list_insert_sorted(), not all nodes of the
382 * chain might be added. This function returns a new chain consisting of all the duplicates.
383 *
384 * @param begin a pointer to the beginning node pointer (required)
385 * @param end a pointer to the end node pointer (if your list has one)
386 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
387 * @param loc_next the location of a @c next pointer within your node struct (required)
388 * @param insert_begin a pointer to the first node of the chain that shall be inserted
389 * @param cmp_func a compare function that will receive the node pointers
390 * @return a pointer to a new chain with all duplicates that were not inserted (or @c NULL when there were no duplicates)
391 */
392 cx_attr_nonnull_arg(1, 5, 6) cx_attr_nodiscard
393 CX_EXPORT void *cx_linked_list_insert_unique_chain(void **begin, void **end,
394 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func);
395
396 /**
397 * Removes a chain of nodes from the linked list.
398 *
399 * If one of the nodes to remove is the beginning (resp. end) node of the list, and if @p begin (resp. @p end)
400 * addresses are provided, the pointers are adjusted accordingly.
401 *
402 * The following combinations of arguments are valid (more arguments are optional):
403 * @li @p loc_next and @p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
404 * @li @p loc_next and @p begin (ancestor node is determined by list traversal, overall O(n) performance)
405 *
406 * @remark The @c next and @c prev pointers of the removed chain are not cleared by this function and may still be used
407 * to traverse to a former adjacent node in the list, or within the chain.
408 *
409 * @param begin a pointer to the beginning node pointer (optional)
410 * @param end a pointer to the end node pointer (optional)
411 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
412 * @param loc_next the location of a @c next pointer within your node struct (required)
413 * @param node the start node of the chain
414 * @param num the number of nodes to remove
415 * @return the actual number of nodes that were removed (can be less when the list did not have enough nodes)
416 */
417 cx_attr_nonnull_arg(5)
418 CX_EXPORT size_t cx_linked_list_remove_chain(void **begin, void **end,
419 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, size_t num);
420
421 /**
422 * Removes a node from the linked list.
423 *
424 * If the node to remove is the beginning (resp. end) node of the list, and if @p begin (resp. @p end)
425 * addresses are provided, the pointers are adjusted accordingly.
426 *
427 * The following combinations of arguments are valid (more arguments are optional):
428 * @li @p loc_next and @p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
429 * @li @p loc_next and @p begin (ancestor node is determined by list traversal, overall O(n) performance)
430 *
431 * @remark The @c next and @c prev pointers of the removed node are not cleared by this function and may still be used
432 * to traverse to a former adjacent node in the list.
433 *
434 * @param begin a pointer to the beginning node pointer (optional)
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 * @param node the node to remove
439 */
440 cx_attr_nonnull_arg(5)
441 CX_EXPORT void cx_linked_list_remove(void **begin, void **end,
442 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node);
443
444 /**
445 * Determines the size of a linked list starting with @p node.
446 *
447 * @param node the first node
448 * @param loc_next the location of the @c next pointer within the node struct
449 * @return the size of the list or zero if @p node is @c NULL
450 */
451 cx_attr_nodiscard
452 CX_EXPORT size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next);
453
454 /**
455 * Sorts a linked list based on a comparison function.
456 *
457 * This function can work with linked lists of the following structure:
458 * @code
459 * typedef struct node node;
460 * struct node {
461 * node* prev;
462 * node* next;
463 * my_payload data;
464 * }
465 * @endcode
466 *
467 * @note This is a recursive function with at most logarithmic recursion depth.
468 *
469 * @param begin a pointer to the beginning node pointer (required)
470 * @param end a pointer to the end node pointer (optional)
471 * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present)
472 * @param loc_next the location of a @c next pointer within your node struct (required)
473 * @param loc_data the location of the @c data pointer within your node struct
474 * @param cmp_func the compare function defining the sort order
475 */
476 cx_attr_nonnull_arg(1, 6)
477 CX_EXPORT void cx_linked_list_sort(void **begin, void **end,
478 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func);
479
480
481 /**
482 * Compares two lists element wise.
483 *
484 * @attention Both lists must have the same structure.
485 *
486 * @param begin_left the beginning of the left list (@c NULL denotes an empty list)
487 * @param begin_right the beginning of the right list (@c NULL denotes an empty list)
488 * @param loc_advance the location of the pointer to advance
489 * @param loc_data the location of the @c data pointer within your node struct
490 * @param cmp_func the function to compare the elements
491 * @return the first non-zero result of invoking @p cmp_func or: negative if the left list is smaller than the
492 * right list, positive if the left list is larger than the right list, zero if both lists are equal.
493 */
494 cx_attr_nonnull_arg(5)
495 CX_EXPORT int cx_linked_list_compare(const void *begin_left, const void *begin_right,
496 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func);
497
498 /**
499 * Reverses the order of the nodes in a linked list.
500 *
501 * @param begin a pointer to the beginning node pointer (required)
502 * @param end a pointer to the end node pointer (optional)
503 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
504 * @param loc_next the location of a @c next pointer within your node struct (required)
505 */
506 cx_attr_nonnull_arg(1)
507 CX_EXPORT void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next);
508
509 #ifdef __cplusplus
510 } // extern "C"
511 #endif
512
513 #endif // UCX_LINKED_LIST_H
514