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