Wed, 23 Nov 2022 22:40:55 +0100
#224 add cxListAddArray()
This also replaces cxLinkedListFromArray().
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 * @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__));
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__));
82 /**
83 * Finds the node at a certain index.
84 *
85 * This function can be used to start at an arbitrary position within the list.
86 * If the search index is large than the start index, \p loc_advance must denote
87 * the location of some sort of \c next pointer (i.e. a pointer to the next node).
88 * But it is also possible that the search index is smaller than the start index
89 * (e.g. in cases where traversing a list backwards is faster) in which case
90 * \p loc_advance must denote the location of some sort of \c prev pointer
91 * (i.e. a pointer to the previous node).
92 *
93 * @param start a pointer to the start node
94 * @param start_index the start index
95 * @param loc_advance the location of the pointer to advance
96 * @param index the search index
97 * @return the node found at the specified index
98 */
99 void *cx_linked_list_at(
100 void const *start,
101 size_t start_index,
102 ptrdiff_t loc_advance,
103 size_t index
104 ) __attribute__((__nonnull__));
106 /**
107 * Finds the index of an element within a linked list.
108 *
109 * @param start a pointer to the start node
110 * @param loc_advance the location of the pointer to advance
111 * @param loc_data the location of the \c data pointer within your node struct
112 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
113 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
114 * @param cmp_func a compare function to compare \p elem against the node data
115 * @param elem a pointer to the element to find
116 * @return the index of the element or a past-one index if the element could not be found
117 */
118 size_t cx_linked_list_find(
119 void const *start,
120 ptrdiff_t loc_advance,
121 ptrdiff_t loc_data,
122 bool follow_ptr,
123 CxListComparator cmp_func,
124 void const *elem
125 ) __attribute__((__nonnull__));
127 /**
128 * Finds the first node in a linked list.
129 *
130 * The function starts with the pointer denoted by \p node and traverses the list
131 * along a prev pointer whose location within the node struct is
132 * denoted by \p loc_prev.
133 *
134 * @param node a pointer to a node in the list
135 * @param loc_prev the location of the \c prev pointer
136 * @return a pointer to the first node
137 */
138 void *cx_linked_list_first(
139 void const *node,
140 ptrdiff_t loc_prev
141 ) __attribute__((__nonnull__));
143 /**
144 * Finds the last node in a linked list.
145 *
146 * The function starts with the pointer denoted by \p node and traverses the list
147 * along a next pointer whose location within the node struct is
148 * denoted by \p loc_next.
149 *
150 * @param node a pointer to a node in the list
151 * @param loc_next the location of the \c next pointer
152 * @return a pointer to the last node
153 */
154 void *cx_linked_list_last(
155 void const *node,
156 ptrdiff_t loc_next
157 ) __attribute__((__nonnull__));
159 /**
160 * Finds the predecessor of a node in case it is not linked.
161 *
162 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined.
163 *
164 * @param begin the node where to start the search
165 * @param loc_next the location of the \c next pointer
166 * @param node the successor of the node to find
167 * @return the node or \c NULL if \p node has no predecessor
168 */
169 void *cx_linked_list_prev(
170 void const *begin,
171 ptrdiff_t loc_next,
172 void const *node
173 ) __attribute__((__nonnull__));
175 /**
176 * Adds a new node to a linked list.
177 * The node must not be part of any list already.
178 *
179 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
180 *
181 * @param begin a pointer to the begin node pointer (if your list has one)
182 * @param end a pointer to the end node pointer (if your list has one)
183 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
184 * @param loc_next the location of a \c next pointer within your node struct (required)
185 * @param new_node a pointer to the node that shall be appended
186 */
187 void cx_linked_list_add(
188 void **begin,
189 void **end,
190 ptrdiff_t loc_prev,
191 ptrdiff_t loc_next,
192 void *new_node
193 ) __attribute__((__nonnull__(5)));
195 /**
196 * Prepends a new node to a linked list.
197 * The node must not be part of any list already.
198 *
199 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
200 *
201 * @param begin a pointer to the begin node pointer (if your list has one)
202 * @param end a pointer to the end node pointer (if your list has one)
203 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
204 * @param loc_next the location of a \c next pointer within your node struct (required)
205 * @param new_node a pointer to the node that shall be prepended
206 */
207 void cx_linked_list_prepend(
208 void **begin,
209 void **end,
210 ptrdiff_t loc_prev,
211 ptrdiff_t loc_next,
212 void *new_node
213 ) __attribute__((__nonnull__(5)));
215 /**
216 * Links two nodes.
217 *
218 * @param left the new predecessor of \p right
219 * @param right the new successor of \p left
220 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
221 * @param loc_next the location of a \c next pointer within your node struct (required)
222 */
223 void cx_linked_list_link(
224 void *left,
225 void *right,
226 ptrdiff_t loc_prev,
227 ptrdiff_t loc_next
228 ) __attribute__((__nonnull__));
230 /**
231 * Unlinks two nodes.
232 *
233 * If right is not the successor of left, the behavior is undefined.
234 *
235 * @param left the predecessor of \p right
236 * @param right the successor of \p left
237 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
238 * @param loc_next the location of a \c next pointer within your node struct (required)
239 */
240 void cx_linked_list_unlink(
241 void *left,
242 void *right,
243 ptrdiff_t loc_prev,
244 ptrdiff_t loc_next
245 ) __attribute__((__nonnull__));
247 /**
248 * Inserts a new node after a given node of a linked list.
249 * The new node must not be part of any list already.
250 *
251 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
252 * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list.
253 *
254 * @param begin a pointer to the begin node pointer (if your list has one)
255 * @param end a pointer to the end node pointer (if your list has one)
256 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
257 * @param loc_next the location of a \c next pointer within your node struct (required)
258 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list)
259 * @param new_node a pointer to the node that shall be prepended
260 */
261 void cx_linked_list_insert(
262 void **begin,
263 void **end,
264 ptrdiff_t loc_prev,
265 ptrdiff_t loc_next,
266 void *node,
267 void *new_node
268 ) __attribute__((__nonnull__(6)));
270 /**
271 * Inserts a chain of nodes after a given node of a linked list.
272 * The chain must not be part of any list already.
273 *
274 * If you do not explicitly specify the end of the chain, it will be determined by traversing
275 * the \c next pointer.
276 *
277 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
278 * the \p end pointer to determine the start of the list. If only the \p end pointer is specified, you also need
279 * to provide a valid \p loc_prev location.
280 * Then the chain will be prepended to the list.
281 *
282 * @param begin a pointer to the begin node pointer (if your list has one)
283 * @param end a pointer to the end node pointer (if your list has one)
284 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
285 * @param loc_next the location of a \c next pointer within your node struct (required)
286 * @param node the node after which to insert (\c NULL to prepend the chain to the list)
287 * @param insert_begin a pointer to the first node of the chain that shall be inserted
288 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
289 */
290 void cx_linked_list_insert_chain(
291 void **begin,
292 void **end,
293 ptrdiff_t loc_prev,
294 ptrdiff_t loc_next,
295 void *node,
296 void *insert_begin,
297 void *insert_end
298 ) __attribute__((__nonnull__(6)));
300 /**
301 * Removes a node from the linked list.
302 *
303 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
304 * addresses are provided, the pointers are adjusted accordingly.
305 *
306 * The following combinations of arguments are valid (more arguments are optional):
307 * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
308 * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance)
309 *
310 * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used
311 * to traverse to a former adjacent node in the list.
312 *
313 * @param begin a pointer to the begin node pointer (optional)
314 * @param end a pointer to the end node pointer (optional)
315 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
316 * @param loc_next the location of a \c next pointer within your node struct (required)
317 * @param node the node to remove
318 */
319 void cx_linked_list_remove(
320 void **begin,
321 void **end,
322 ptrdiff_t loc_prev,
323 ptrdiff_t loc_next,
324 void *node
325 ) __attribute__((__nonnull__(5)));
328 /**
329 * Determines the size of a linked list starting with \p node.
330 * @param node the first node
331 * @param loc_next the location of the \c next pointer within the node struct
332 * @return the size of the list or zero if \p node is \c NULL
333 */
334 size_t cx_linked_list_size(
335 void const *node,
336 ptrdiff_t loc_next
337 );
339 /**
340 * Sorts a linked list based on a comparison function.
341 *
342 * This function can work with linked lists of the following structures:
343 * \code
344 * typedef struct node node;
345 * struct node {
346 * node* prev;
347 * node* next;
348 * my_payload data; // in this case set follow_ptr = 0
349 * }
350 *
351 * typedef struct ptr_node ptr_node;
352 * struct ptr_node {
353 * ptr_node* prev;
354 * ptr_node* next;
355 * my_payload* data; // in this case set follow_ptr = 1
356 * }
357 * \endcode
358 *
359 * @note This is a recursive function with at most logarithmic recursion depth.
360 *
361 * @param begin a pointer to the begin node pointer (required)
362 * @param end a pointer to the end node pointer (optional)
363 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)
364 * @param loc_next the location of a \c next pointer within your node struct (required)
365 * @param loc_data the location of the \c data pointer within your node struct
366 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func.
367 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
368 * @param cmp_func the compare function defining the sort order
369 */
370 void cx_linked_list_sort(
371 void **begin,
372 void **end,
373 ptrdiff_t loc_prev,
374 ptrdiff_t loc_next,
375 ptrdiff_t loc_data,
376 bool follow_ptr,
377 CxListComparator cmp_func
378 ) __attribute__((__nonnull__(1, 7)));
381 /**
382 * Compares two lists element wise.
383 *
384 * The \c follow_ptr flags have the following meaning: if \c false, the pointer denoted by \p loc_data shall
385 * directly be passed to the \p cmp_func.
386 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func.
387 *
388 * \note Both list must have the same structure.
389 *
390 * @param begin_left the begin of the left list (\c NULL denotes an empty list)
391 * @param begin_right the begin of the right list (\c NULL denotes an empty list)
392 * @param loc_advance the location of the pointer to advance
393 * @param loc_data the location of the \c data pointer within your node struct
394 * @param follow_ptr_left indicates whether pointers in the left list shall be dereferenced
395 * @param follow_ptr_right indicates whether pointers in the right list shall be dereferenced
396 * @param cmp_func the function to compare the elements
397 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the
398 * right list, positive if the left list is larger than the right list, zero if both lists are equal.
399 */
400 int cx_linked_list_compare(
401 void const *begin_left,
402 void const *begin_right,
403 ptrdiff_t loc_advance,
404 ptrdiff_t loc_data,
405 bool follow_ptr_left,
406 bool follow_ptr_right,
407 CxListComparator cmp_func
408 ) __attribute__((__nonnull__(7)));
410 /**
411 * Reverses the order of the nodes in a linked list.
412 *
413 * @param begin a pointer to the begin node pointer (required)
414 * @param end a pointer to the end node pointer (optional)
415 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
416 * @param loc_next the location of a \c next pointer within your node struct (required)
417 */
418 void cx_linked_list_reverse(
419 void **begin,
420 void **end,
421 ptrdiff_t loc_prev,
422 ptrdiff_t loc_next
423 ) __attribute__((__nonnull__(1)));
425 #ifdef __cplusplus
426 } // extern "C"
427 #endif
429 #endif // UCX_LINKED_LIST_H