Sat, 22 Jan 2022 10:29:48 +0100
hide __attribute__ from compilers that may not support it
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 */
38 #ifndef UCX_LINKED_LIST_H
39 #define UCX_LINKED_LIST_H
41 #include "common.h"
42 #include "list.h"
44 #ifdef __cplusplus
45 extern "C" {
46 #endif
48 /**
49 * Allocates a linked list for storing elements with \p item_size bytes each.
50 *
51 * Elements added to the list are copied.
52 *
53 * @param allocator the allocator for allocating the list nodes
54 * @param comparator the comparator for the elements
55 * @param item_size the size of each element in bytes
56 * @return the created list
57 */
58 CxList cxLinkedListCreate(
59 CxAllocator allocator,
60 CxListComparator comparator,
61 size_t item_size
62 ) __attribute__((__nonnull__));
64 /**
65 * Allocates a linked list for storing pointers.
66 *
67 * If you want to store the elements directly in this list, use cxLinkedListCreate().
68 *
69 * @param allocator the allocator for allocating the list nodes
70 * @param comparator the comparator for the elements
71 * @return the created list
72 */
73 CxList cxPointerLinkedListCreate(
74 CxAllocator allocator,
75 CxListComparator comparator
76 ) __attribute__((__nonnull__));
78 /**
79 * Creates a linked list using the data from an array.
80 *
81 * @param allocator the allocator for allocating the list nodes
82 * @param comparator the comparator for the elements
83 * @param item_size the size of one item in the array
84 * @param num_items the number of items
85 * @param array the array data
86 * @return the created list
87 */
88 CxList cxLinkedListFromArray(
89 CxAllocator allocator,
90 CxListComparator comparator,
91 size_t item_size,
92 size_t num_items,
93 void const *array
94 ) __attribute__((__nonnull__));
96 /**
97 * Deallocates the memory of the entire list.
98 *
99 * \attention If this is a pointer list, the memory the pointers are referring to is \em not freed.
100 *
101 * @param list the list
102 */
103 void cxLinkedListDestroy(CxList list) __attribute__((__nonnull__));
105 /**
106 * Finds the node at a certain index.
107 *
108 * This function can be used to start at an arbitrary position within the list.
109 * If the search index is large than the start index, \p loc_advance must denote
110 * the location of some sort of \c next pointer (i.e. a pointer to the next node).
111 * But it is also possible that the search index is smaller than the start index
112 * (e.g. in cases where traversing a list backwards is faster) in which case
113 * \p loc_advance must denote the location of some sort of \c prev pointer
114 * (i.e. a pointer to the previous node).
115 *
116 * @param start a pointer to the start node
117 * @param start_index the start index
118 * @param loc_advance the location of the pointer to advance
119 * @param index the search index
120 * @return the node found at the specified index
121 */
122 void *cx_linked_list_at(
123 void *start,
124 size_t start_index,
125 ptrdiff_t loc_advance,
126 size_t index
127 ) __attribute__((__nonnull__));
129 /**
130 * Finds the index of an element within a linked list.
131 *
132 * @param start a pointer to the start node
133 * @param loc_advance the location of the pointer to advance
134 * @param loc_data the location of the \c data pointer within your node struct
135 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
136 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
137 * @param cmp_func a compare function to compare \p elem against the node data
138 * @param elem a pointer to the element to find
139 * @return the index of the element or a past-one index if the element could not be found
140 */
141 size_t cx_linked_list_find(
142 void const *start,
143 ptrdiff_t loc_advance,
144 ptrdiff_t loc_data,
145 bool follow_ptr,
146 CxListComparator cmp_func,
147 void const *elem
148 ) __attribute__((__nonnull__));
150 /**
151 * Finds the first node in a linked list.
152 *
153 * The function starts with the pointer denoted by \p node and traverses the list
154 * along a prev pointer whose location within the node struct is
155 * denoted by \p loc_prev.
156 *
157 * @param node a pointer to a node in the list
158 * @param loc_prev the location of the \c prev pointer
159 * @return a pointer to the first node
160 */
161 void *cx_linked_list_first(
162 void *node,
163 ptrdiff_t loc_prev
164 ) __attribute__((__nonnull__));
166 /**
167 * Finds the last node in a linked list.
168 *
169 * The function starts with the pointer denoted by \p node and traverses the list
170 * along a next pointer whose location within the node struct is
171 * denoted by \p loc_next.
172 *
173 * @param node a pointer to a node in the list
174 * @param loc_next the location of the \c next pointer
175 * @return a pointer to the last node
176 */
177 void *cx_linked_list_last(
178 void *node,
179 ptrdiff_t loc_next
180 ) __attribute__((__nonnull__));
182 /**
183 * Finds the predecessor of a node in case it is not linked.
184 *
185 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined.
186 *
187 * @param begin the node where to start the search
188 * @param loc_next the location of the \c next pointer
189 * @param node the successor of the node to find
190 * @return the node or \c NULL if \p node has no predecessor
191 */
192 void *cx_linked_list_prev(
193 void *begin,
194 ptrdiff_t loc_next,
195 void *node
196 ) __attribute__((__nonnull__));
198 /**
199 * Adds a new node to a linked list.
200 * The node must not be part of any list already.
201 *
202 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
203 *
204 * @param begin a pointer to the begin node pointer (if your list has one)
205 * @param end a pointer to the end node pointer (if your list has one)
206 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
207 * @param loc_next the location of a \c next pointer within your node struct (required)
208 * @param new_node a pointer to the node that shall be appended
209 */
210 void cx_linked_list_add(
211 void **begin,
212 void **end,
213 ptrdiff_t loc_prev,
214 ptrdiff_t loc_next,
215 void *new_node
216 ) __attribute__((__nonnull__(5)));
218 /**
219 * Prepends a new node to a linked list.
220 * The node must not be part of any list already.
221 *
222 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
223 *
224 * @param begin a pointer to the begin node pointer (if your list has one)
225 * @param end a pointer to the end node pointer (if your list has one)
226 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
227 * @param loc_next the location of a \c next pointer within your node struct (required)
228 * @param new_node a pointer to the node that shall be prepended
229 */
230 void cx_linked_list_prepend(
231 void **begin,
232 void **end,
233 ptrdiff_t loc_prev,
234 ptrdiff_t loc_next,
235 void *new_node
236 ) __attribute__((__nonnull__(5)));
238 /**
239 * Links two nodes.
240 *
241 * @param left the new predecessor of \p right
242 * @param right the new successor of \p left
243 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
244 * @param loc_next the location of a \c next pointer within your node struct (required)
245 */
246 void cx_linked_list_link(
247 void *left,
248 void *right,
249 ptrdiff_t loc_prev,
250 ptrdiff_t loc_next
251 ) __attribute__((__nonnull__));
253 /**
254 * Unlinks two nodes.
255 *
256 * If right is not the successor of left, the behavior is undefined.
257 *
258 * @param left the predecessor of \p right
259 * @param right the successor of \p left
260 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
261 * @param loc_next the location of a \c next pointer within your node struct (required)
262 */
263 void cx_linked_list_unlink(
264 void *left,
265 void *right,
266 ptrdiff_t loc_prev,
267 ptrdiff_t loc_next
268 ) __attribute__((__nonnull__));
270 /**
271 * Inserts a new node after a given node of a linked list.
272 * The new node must not be part of any list already.
273 *
274 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
275 * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list.
276 *
277 * @param begin a pointer to the begin node pointer (if your list has one)
278 * @param end a pointer to the end node pointer (if your list has one)
279 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
280 * @param loc_next the location of a \c next pointer within your node struct (required)
281 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list)
282 * @param new_node a pointer to the node that shall be prepended
283 */
284 void cx_linked_list_insert(
285 void **begin,
286 void **end,
287 ptrdiff_t loc_prev,
288 ptrdiff_t loc_next,
289 void *node,
290 void *new_node
291 ) __attribute__((__nonnull__(6)));
293 /**
294 * Inserts a chain of nodes after a given node of a linked list.
295 * The chain must not be part of any list already.
296 *
297 * If you do not explicitly specify the end of the chain, it will be determined by traversing
298 * the \c next pointer.
299 *
300 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
301 * the \p end pointer to determine the start of the list. If only the \p end pointer is specified, you also need
302 * to provide a valid \p loc_prev location.
303 * Then the chain will be prepended to the list.
304 *
305 * @param begin a pointer to the begin node pointer (if your list has one)
306 * @param end a pointer to the end node pointer (if your list has one)
307 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
308 * @param loc_next the location of a \c next pointer within your node struct (required)
309 * @param node the node after which to insert (\c NULL to prepend the chain to the list)
310 * @param insert_begin a pointer to the first node of the chain that shall be inserted
311 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
312 */
313 void cx_linked_list_insert_chain(
314 void **begin,
315 void **end,
316 ptrdiff_t loc_prev,
317 ptrdiff_t loc_next,
318 void *node,
319 void *insert_begin,
320 void *insert_end
321 ) __attribute__((__nonnull__(6)));
323 /**
324 * Removes a node from the linked list.
325 *
326 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
327 * addresses are provided, the pointers are adjusted accordingly.
328 *
329 * The following combinations of arguments are valid (more arguments are optional):
330 * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
331 * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance)
332 *
333 * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used
334 * to traverse to a former adjacent node in the list.
335 *
336 * @param begin a pointer to the begin node pointer (optional)
337 * @param end a pointer to the end node pointer (optional)
338 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
339 * @param loc_next the location of a \c next pointer within your node struct (required)
340 * @param node the node to remove
341 */
342 void cx_linked_list_remove(
343 void **begin,
344 void **end,
345 ptrdiff_t loc_prev,
346 ptrdiff_t loc_next,
347 void *node
348 ) __attribute__((__nonnull__(5)));
351 /**
352 * Determines the size of a linked list starting with \p node.
353 * @param node the first node
354 * @param loc_next the location of the \c next pointer within the node struct
355 * @return the size of the list or zero if \p node is \c NULL
356 */
357 size_t cx_linked_list_size(
358 void const *node,
359 ptrdiff_t loc_next
360 );
362 /**
363 * Sorts a linked list based on a comparison function.
364 *
365 * This function can work with linked lists of the following structures:
366 * \code
367 * typedef struct node node;
368 * struct node {
369 * node* prev;
370 * node* next;
371 * my_payload data; // in this case set follow_ptr = 0
372 * }
373 *
374 * typedef struct ptr_node ptr_node;
375 * struct ptr_node {
376 * ptr_node* prev;
377 * ptr_node* next;
378 * my_payload* data; // in this case set follow_ptr = 1
379 * }
380 * \endcode
381 *
382 * @note This is a recursive function with at most logarithmic recursion depth.
383 *
384 * @param begin a pointer to the begin node pointer (required)
385 * @param end a pointer to the end node pointer (optional)
386 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)
387 * @param loc_next the location of a \c next pointer within your node struct (required)
388 * @param loc_data the location of the \c data pointer within your node struct
389 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
390 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
391 * @param cmp_func the compare function defining the sort order
392 */
393 void cx_linked_list_sort(
394 void **begin,
395 void **end,
396 ptrdiff_t loc_prev,
397 ptrdiff_t loc_next,
398 ptrdiff_t loc_data,
399 bool follow_ptr,
400 CxListComparator cmp_func
401 ) __attribute__((__nonnull__(1, 7)));
404 /**
405 * Compares two lists element wise.
406 *
407 * \note Both list must have the same structure.
408 *
409 * @param begin_left the begin of the left list (\c NULL denotes an empty list)
410 * @param begin_right the begin of the right list (\c NULL denotes an empty list)
411 * @param loc_advance the location of the pointer to advance
412 * @param loc_data the location of the \c data pointer within your node struct
413 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
414 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
415 * @param cmp_func the function to compare the elements
416 * @return
417 */
418 int cx_linked_list_compare(
419 void const *begin_left,
420 void const *begin_right,
421 ptrdiff_t loc_advance,
422 ptrdiff_t loc_data,
423 bool follow_ptr,
424 CxListComparator cmp_func
425 ) __attribute__((__nonnull__(6)));
427 /**
428 * Reverses the order of the nodes in a linked list.
429 *
430 * @param begin a pointer to the begin node pointer (required)
431 * @param end a pointer to the end node pointer (optional)
432 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
433 * @param loc_next the location of a \c next pointer within your node struct (required)
434 */
435 void cx_linked_list_reverse(
436 void **begin,
437 void **end,
438 ptrdiff_t loc_prev,
439 ptrdiff_t loc_next
440 ) __attribute__((__nonnull__(1)));
442 #ifdef __cplusplus
443 } /* extern "C" */
444 #endif
446 #endif /* UCX_LINKED_LIST_H */