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