Thu, 23 Feb 2023 22:43:13 +0100
add simple functions for creating lists
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 * Set this flag to true, if you want to disable the use of SBO for
50 * linked list swap operations.
51 */
52 extern bool CX_DISABLE_LINKED_LIST_SWAP_SBO;
54 /**
55 * Allocates a linked list for storing elements with \p item_size bytes each.
56 *
57 * @param allocator the allocator for allocating the list nodes
58 * @param comparator the comparator for the elements
59 * @param item_size the size of each element in bytes
60 * @return the created list
61 */
62 CxList *cxLinkedListCreate(
63 CxAllocator const *allocator,
64 CxListComparator comparator,
65 size_t item_size
66 ) __attribute__((__nonnull__));
68 /**
69 * Allocates a linked list for storing elements with \p item_size bytes each.
70 *
71 * The list will use cxDefaultAllocator and no comparator function. If you want
72 * to call functions that need a comparator, you must either set one immediately
73 * after list creation or use cxLinkedListCreate().
74 *
75 * @param item_size the size of each element in bytes
76 * @return the created list
77 */
78 CxList *cxLinkedListCreateSimple(size_t item_size);
80 /**
81 * Finds the node at a certain index.
82 *
83 * This function can be used to start at an arbitrary position within the list.
84 * If the search index is large than the start index, \p loc_advance must denote
85 * the location of some sort of \c next pointer (i.e. a pointer to the next node).
86 * But it is also possible that the search index is smaller than the start index
87 * (e.g. in cases where traversing a list backwards is faster) in which case
88 * \p loc_advance must denote the location of some sort of \c prev pointer
89 * (i.e. a pointer to the previous node).
90 *
91 * @param start a pointer to the start node
92 * @param start_index the start index
93 * @param loc_advance the location of the pointer to advance
94 * @param index the search index
95 * @return the node found at the specified index
96 */
97 void *cx_linked_list_at(
98 void const *start,
99 size_t start_index,
100 ptrdiff_t loc_advance,
101 size_t index
102 ) __attribute__((__nonnull__));
104 /**
105 * Finds the index of an element within a linked list.
106 *
107 * @param start a pointer to the start node
108 * @param loc_advance the location of the pointer to advance
109 * @param loc_data the location of the \c data pointer within your node struct
110 * @param cmp_func a compare function to compare \p elem against the node data
111 * @param elem a pointer to the element to find
112 * @return the index of the element or a past-one index if the element could not be found
113 */
114 size_t cx_linked_list_find(
115 void const *start,
116 ptrdiff_t loc_advance,
117 ptrdiff_t loc_data,
118 CxListComparator cmp_func,
119 void const *elem
120 ) __attribute__((__nonnull__));
122 /**
123 * Finds the first node in a linked list.
124 *
125 * The function starts with the pointer denoted by \p node and traverses the list
126 * along a prev pointer whose location within the node struct is
127 * denoted by \p loc_prev.
128 *
129 * @param node a pointer to a node in the list
130 * @param loc_prev the location of the \c prev pointer
131 * @return a pointer to the first node
132 */
133 void *cx_linked_list_first(
134 void const *node,
135 ptrdiff_t loc_prev
136 ) __attribute__((__nonnull__));
138 /**
139 * Finds the last node in a linked list.
140 *
141 * The function starts with the pointer denoted by \p node and traverses the list
142 * along a next pointer whose location within the node struct is
143 * denoted by \p loc_next.
144 *
145 * @param node a pointer to a node in the list
146 * @param loc_next the location of the \c next pointer
147 * @return a pointer to the last node
148 */
149 void *cx_linked_list_last(
150 void const *node,
151 ptrdiff_t loc_next
152 ) __attribute__((__nonnull__));
154 /**
155 * Finds the predecessor of a node in case it is not linked.
156 *
157 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined.
158 *
159 * @param begin the node where to start the search
160 * @param loc_next the location of the \c next pointer
161 * @param node the successor of the node to find
162 * @return the node or \c NULL if \p node has no predecessor
163 */
164 void *cx_linked_list_prev(
165 void const *begin,
166 ptrdiff_t loc_next,
167 void const *node
168 ) __attribute__((__nonnull__));
170 /**
171 * Adds a new node to a linked list.
172 * The node must not be part of any list already.
173 *
174 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
175 *
176 * @param begin a pointer to the begin node pointer (if your list has one)
177 * @param end a pointer to the end node pointer (if your list has one)
178 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
179 * @param loc_next the location of a \c next pointer within your node struct (required)
180 * @param new_node a pointer to the node that shall be appended
181 */
182 void cx_linked_list_add(
183 void **begin,
184 void **end,
185 ptrdiff_t loc_prev,
186 ptrdiff_t loc_next,
187 void *new_node
188 ) __attribute__((__nonnull__(5)));
190 /**
191 * Prepends a new node to a linked list.
192 * The node must not be part of any list already.
193 *
194 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
195 *
196 * @param begin a pointer to the begin node pointer (if your list has one)
197 * @param end a pointer to the end node pointer (if your list has one)
198 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
199 * @param loc_next the location of a \c next pointer within your node struct (required)
200 * @param new_node a pointer to the node that shall be prepended
201 */
202 void cx_linked_list_prepend(
203 void **begin,
204 void **end,
205 ptrdiff_t loc_prev,
206 ptrdiff_t loc_next,
207 void *new_node
208 ) __attribute__((__nonnull__(5)));
210 /**
211 * Links two nodes.
212 *
213 * @param left the new predecessor of \p right
214 * @param right the new successor of \p left
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 */
218 void cx_linked_list_link(
219 void *left,
220 void *right,
221 ptrdiff_t loc_prev,
222 ptrdiff_t loc_next
223 ) __attribute__((__nonnull__));
225 /**
226 * Unlinks two nodes.
227 *
228 * If right is not the successor of left, the behavior is undefined.
229 *
230 * @param left the predecessor of \p right
231 * @param right the successor of \p left
232 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
233 * @param loc_next the location of a \c next pointer within your node struct (required)
234 */
235 void cx_linked_list_unlink(
236 void *left,
237 void *right,
238 ptrdiff_t loc_prev,
239 ptrdiff_t loc_next
240 ) __attribute__((__nonnull__));
242 /**
243 * Inserts a new node after a given node of a linked list.
244 * The new node must not be part of any list already.
245 *
246 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
247 * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list.
248 *
249 * @param begin a pointer to the begin node pointer (if your list has one)
250 * @param end a pointer to the end node pointer (if your list has one)
251 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
252 * @param loc_next the location of a \c next pointer within your node struct (required)
253 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list)
254 * @param new_node a pointer to the node that shall be prepended
255 */
256 void cx_linked_list_insert(
257 void **begin,
258 void **end,
259 ptrdiff_t loc_prev,
260 ptrdiff_t loc_next,
261 void *node,
262 void *new_node
263 ) __attribute__((__nonnull__(6)));
265 /**
266 * Inserts a chain of nodes after a given node of a linked list.
267 * The chain must not be part of any list already.
268 *
269 * If you do not explicitly specify the end of the chain, it will be determined by traversing
270 * the \c next pointer.
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. If only the \p end pointer is specified, you also need
274 * to provide a valid \p loc_prev location.
275 * Then the chain 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 to prepend the chain to the list)
282 * @param insert_begin a pointer to the first node of the chain that shall be inserted
283 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
284 */
285 void cx_linked_list_insert_chain(
286 void **begin,
287 void **end,
288 ptrdiff_t loc_prev,
289 ptrdiff_t loc_next,
290 void *node,
291 void *insert_begin,
292 void *insert_end
293 ) __attribute__((__nonnull__(6)));
295 /**
296 * Removes a node from the linked list.
297 *
298 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
299 * addresses are provided, the pointers are adjusted accordingly.
300 *
301 * The following combinations of arguments are valid (more arguments are optional):
302 * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
303 * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance)
304 *
305 * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used
306 * to traverse to a former adjacent node in the list.
307 *
308 * @param begin a pointer to the begin node pointer (optional)
309 * @param end a pointer to the end node pointer (optional)
310 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
311 * @param loc_next the location of a \c next pointer within your node struct (required)
312 * @param node the node to remove
313 */
314 void cx_linked_list_remove(
315 void **begin,
316 void **end,
317 ptrdiff_t loc_prev,
318 ptrdiff_t loc_next,
319 void *node
320 ) __attribute__((__nonnull__(5)));
323 /**
324 * Determines the size of a linked list starting with \p node.
325 * @param node the first node
326 * @param loc_next the location of the \c next pointer within the node struct
327 * @return the size of the list or zero if \p node is \c NULL
328 */
329 size_t cx_linked_list_size(
330 void const *node,
331 ptrdiff_t loc_next
332 );
334 /**
335 * Sorts a linked list based on a comparison function.
336 *
337 * This function can work with linked lists of the following structure:
338 * \code
339 * typedef struct node node;
340 * struct node {
341 * node* prev;
342 * node* next;
343 * my_payload data;
344 * }
345 * \endcode
346 *
347 * @note This is a recursive function with at most logarithmic recursion depth.
348 *
349 * @param begin a pointer to the begin node pointer (required)
350 * @param end a pointer to the end node pointer (optional)
351 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)
352 * @param loc_next the location of a \c next pointer within your node struct (required)
353 * @param loc_data the location of the \c data pointer within your node struct
354 * @param cmp_func the compare function defining the sort order
355 */
356 void cx_linked_list_sort(
357 void **begin,
358 void **end,
359 ptrdiff_t loc_prev,
360 ptrdiff_t loc_next,
361 ptrdiff_t loc_data,
362 CxListComparator cmp_func
363 ) __attribute__((__nonnull__(1, 6)));
366 /**
367 * Compares two lists element wise.
368 *
369 * \note Both list must have the same structure.
370 *
371 * @param begin_left the begin of the left list (\c NULL denotes an empty list)
372 * @param begin_right the begin of the right list (\c NULL denotes an empty list)
373 * @param loc_advance the location of the pointer to advance
374 * @param loc_data the location of the \c data pointer within your node struct
375 * @param cmp_func the function to compare the elements
376 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the
377 * right list, positive if the left list is larger than the right list, zero if both lists are equal.
378 */
379 int cx_linked_list_compare(
380 void const *begin_left,
381 void const *begin_right,
382 ptrdiff_t loc_advance,
383 ptrdiff_t loc_data,
384 CxListComparator cmp_func
385 ) __attribute__((__nonnull__(5)));
387 /**
388 * Reverses the order of the nodes in a linked list.
389 *
390 * @param begin a pointer to the begin node pointer (required)
391 * @param end a pointer to the end node pointer (optional)
392 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
393 * @param loc_next the location of a \c next pointer within your node struct (required)
394 */
395 void cx_linked_list_reverse(
396 void **begin,
397 void **end,
398 ptrdiff_t loc_prev,
399 ptrdiff_t loc_next
400 ) __attribute__((__nonnull__(1)));
402 #ifdef __cplusplus
403 } // extern "C"
404 #endif
406 #endif // UCX_LINKED_LIST_H