Mon, 23 Jan 2023 20:34:18 +0100
temporarily remove pointer lists - see #234
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 * Finds the node at a certain index.
67 *
68 * This function can be used to start at an arbitrary position within the list.
69 * If the search index is large than the start index, \p loc_advance must denote
70 * the location of some sort of \c next pointer (i.e. a pointer to the next node).
71 * But it is also possible that the search index is smaller than the start index
72 * (e.g. in cases where traversing a list backwards is faster) in which case
73 * \p loc_advance must denote the location of some sort of \c prev pointer
74 * (i.e. a pointer to the previous node).
75 *
76 * @param start a pointer to the start node
77 * @param start_index the start index
78 * @param loc_advance the location of the pointer to advance
79 * @param index the search index
80 * @return the node found at the specified index
81 */
82 void *cx_linked_list_at(
83 void const *start,
84 size_t start_index,
85 ptrdiff_t loc_advance,
86 size_t index
87 ) __attribute__((__nonnull__));
89 /**
90 * Finds the index of an element within a linked list.
91 *
92 * @param start a pointer to the start node
93 * @param loc_advance the location of the pointer to advance
94 * @param loc_data the location of the \c data pointer within your node struct
95 * @param cmp_func a compare function to compare \p elem against the node data
96 * @param elem a pointer to the element to find
97 * @return the index of the element or a past-one index if the element could not be found
98 */
99 size_t cx_linked_list_find(
100 void const *start,
101 ptrdiff_t loc_advance,
102 ptrdiff_t loc_data,
103 CxListComparator cmp_func,
104 void const *elem
105 ) __attribute__((__nonnull__));
107 /**
108 * Finds the first node in a linked list.
109 *
110 * The function starts with the pointer denoted by \p node and traverses the list
111 * along a prev pointer whose location within the node struct is
112 * denoted by \p loc_prev.
113 *
114 * @param node a pointer to a node in the list
115 * @param loc_prev the location of the \c prev pointer
116 * @return a pointer to the first node
117 */
118 void *cx_linked_list_first(
119 void const *node,
120 ptrdiff_t loc_prev
121 ) __attribute__((__nonnull__));
123 /**
124 * Finds the last node in a linked list.
125 *
126 * The function starts with the pointer denoted by \p node and traverses the list
127 * along a next pointer whose location within the node struct is
128 * denoted by \p loc_next.
129 *
130 * @param node a pointer to a node in the list
131 * @param loc_next the location of the \c next pointer
132 * @return a pointer to the last node
133 */
134 void *cx_linked_list_last(
135 void const *node,
136 ptrdiff_t loc_next
137 ) __attribute__((__nonnull__));
139 /**
140 * Finds the predecessor of a node in case it is not linked.
141 *
142 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined.
143 *
144 * @param begin the node where to start the search
145 * @param loc_next the location of the \c next pointer
146 * @param node the successor of the node to find
147 * @return the node or \c NULL if \p node has no predecessor
148 */
149 void *cx_linked_list_prev(
150 void const *begin,
151 ptrdiff_t loc_next,
152 void const *node
153 ) __attribute__((__nonnull__));
155 /**
156 * Adds a new node to a linked list.
157 * The node must not be part of any list already.
158 *
159 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
160 *
161 * @param begin a pointer to the begin node pointer (if your list has one)
162 * @param end a pointer to the end node pointer (if your list has one)
163 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
164 * @param loc_next the location of a \c next pointer within your node struct (required)
165 * @param new_node a pointer to the node that shall be appended
166 */
167 void cx_linked_list_add(
168 void **begin,
169 void **end,
170 ptrdiff_t loc_prev,
171 ptrdiff_t loc_next,
172 void *new_node
173 ) __attribute__((__nonnull__(5)));
175 /**
176 * Prepends 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 prepended
186 */
187 void cx_linked_list_prepend(
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 * Links two nodes.
197 *
198 * @param left the new predecessor of \p right
199 * @param right the new successor of \p left
200 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
201 * @param loc_next the location of a \c next pointer within your node struct (required)
202 */
203 void cx_linked_list_link(
204 void *left,
205 void *right,
206 ptrdiff_t loc_prev,
207 ptrdiff_t loc_next
208 ) __attribute__((__nonnull__));
210 /**
211 * Unlinks two nodes.
212 *
213 * If right is not the successor of left, the behavior is undefined.
214 *
215 * @param left the predecessor of \p right
216 * @param right the successor of \p left
217 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
218 * @param loc_next the location of a \c next pointer within your node struct (required)
219 */
220 void cx_linked_list_unlink(
221 void *left,
222 void *right,
223 ptrdiff_t loc_prev,
224 ptrdiff_t loc_next
225 ) __attribute__((__nonnull__));
227 /**
228 * Inserts a new node after a given node of a linked list.
229 * The new node must not be part of any list already.
230 *
231 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
232 * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list.
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 node the node after which to insert (\c NULL if you want to prepend the node to the list)
239 * @param new_node a pointer to the node that shall be prepended
240 */
241 void cx_linked_list_insert(
242 void **begin,
243 void **end,
244 ptrdiff_t loc_prev,
245 ptrdiff_t loc_next,
246 void *node,
247 void *new_node
248 ) __attribute__((__nonnull__(6)));
250 /**
251 * Inserts a chain of nodes after a given node of a linked list.
252 * The chain must not be part of any list already.
253 *
254 * If you do not explicitly specify the end of the chain, it will be determined by traversing
255 * the \c next pointer.
256 *
257 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
258 * the \p end pointer to determine the start of the list. If only the \p end pointer is specified, you also need
259 * to provide a valid \p loc_prev location.
260 * Then the chain will be prepended to the list.
261 *
262 * @param begin a pointer to the begin node pointer (if your list has one)
263 * @param end a pointer to the end node pointer (if your list has one)
264 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
265 * @param loc_next the location of a \c next pointer within your node struct (required)
266 * @param node the node after which to insert (\c NULL to prepend the chain to the list)
267 * @param insert_begin a pointer to the first node of the chain that shall be inserted
268 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
269 */
270 void cx_linked_list_insert_chain(
271 void **begin,
272 void **end,
273 ptrdiff_t loc_prev,
274 ptrdiff_t loc_next,
275 void *node,
276 void *insert_begin,
277 void *insert_end
278 ) __attribute__((__nonnull__(6)));
280 /**
281 * Removes a node from the linked list.
282 *
283 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
284 * addresses are provided, the pointers are adjusted accordingly.
285 *
286 * The following combinations of arguments are valid (more arguments are optional):
287 * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
288 * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance)
289 *
290 * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used
291 * to traverse to a former adjacent node in the list.
292 *
293 * @param begin a pointer to the begin node pointer (optional)
294 * @param end a pointer to the end node pointer (optional)
295 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
296 * @param loc_next the location of a \c next pointer within your node struct (required)
297 * @param node the node to remove
298 */
299 void cx_linked_list_remove(
300 void **begin,
301 void **end,
302 ptrdiff_t loc_prev,
303 ptrdiff_t loc_next,
304 void *node
305 ) __attribute__((__nonnull__(5)));
308 /**
309 * Determines the size of a linked list starting with \p node.
310 * @param node the first node
311 * @param loc_next the location of the \c next pointer within the node struct
312 * @return the size of the list or zero if \p node is \c NULL
313 */
314 size_t cx_linked_list_size(
315 void const *node,
316 ptrdiff_t loc_next
317 );
319 /**
320 * Sorts a linked list based on a comparison function.
321 *
322 * This function can work with linked lists of the following structure:
323 * \code
324 * typedef struct node node;
325 * struct node {
326 * node* prev;
327 * node* next;
328 * my_payload data;
329 * }
330 * \endcode
331 *
332 * @note This is a recursive function with at most logarithmic recursion depth.
333 *
334 * @param begin a pointer to the begin node pointer (required)
335 * @param end a pointer to the end node pointer (optional)
336 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)
337 * @param loc_next the location of a \c next pointer within your node struct (required)
338 * @param loc_data the location of the \c data pointer within your node struct
339 * @param cmp_func the compare function defining the sort order
340 */
341 void cx_linked_list_sort(
342 void **begin,
343 void **end,
344 ptrdiff_t loc_prev,
345 ptrdiff_t loc_next,
346 ptrdiff_t loc_data,
347 CxListComparator cmp_func
348 ) __attribute__((__nonnull__(1, 6)));
351 /**
352 * Compares two lists element wise.
353 *
354 * \note Both list must have the same structure.
355 *
356 * @param begin_left the begin of the left list (\c NULL denotes an empty list)
357 * @param begin_right the begin of the right list (\c NULL denotes an empty list)
358 * @param loc_advance the location of the pointer to advance
359 * @param loc_data the location of the \c data pointer within your node struct
360 * @param cmp_func the function to compare the elements
361 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the
362 * right list, positive if the left list is larger than the right list, zero if both lists are equal.
363 */
364 int cx_linked_list_compare(
365 void const *begin_left,
366 void const *begin_right,
367 ptrdiff_t loc_advance,
368 ptrdiff_t loc_data,
369 CxListComparator cmp_func
370 ) __attribute__((__nonnull__(5)));
372 /**
373 * Reverses the order of the nodes in a linked list.
374 *
375 * @param begin a pointer to the begin node pointer (required)
376 * @param end a pointer to the end node pointer (optional)
377 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
378 * @param loc_next the location of a \c next pointer within your node struct (required)
379 */
380 void cx_linked_list_reverse(
381 void **begin,
382 void **end,
383 ptrdiff_t loc_prev,
384 ptrdiff_t loc_next
385 ) __attribute__((__nonnull__(1)));
387 #ifdef __cplusplus
388 } // extern "C"
389 #endif
391 #endif // UCX_LINKED_LIST_H