Tue, 29 Oct 2024 11:25:32 +0100
fix generic file icon (GTK)
174 | 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 | * \copyright 2-Clause BSD License | |
35 | */ | |
36 | ||
37 | #ifndef UCX_LINKED_LIST_H | |
38 | #define UCX_LINKED_LIST_H | |
39 | ||
40 | #include "common.h" | |
41 | #include "list.h" | |
42 | ||
43 | #ifdef __cplusplus | |
44 | extern "C" { | |
45 | #endif | |
46 | ||
47 | /** | |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
48 | * The maximum item size that uses SBO swap instead of relinking. |
174 | 49 | */ |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
50 | extern unsigned cx_linked_list_swap_sbo_size; |
174 | 51 | |
52 | /** | |
324 | 53 | * Allocates a linked list for storing elements with \p elem_size bytes each. |
174 | 54 | * |
324 | 55 | * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
56 | * cxListStorePointers() was called immediately after creation and the compare |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
57 | * function will be automatically set to cx_cmp_ptr(), if none is given. |
174 | 58 | * |
59 | * @param allocator the allocator for allocating the list nodes | |
60 | * (if \c NULL the cxDefaultAllocator will be used) | |
61 | * @param comparator the comparator for the elements | |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
62 | * (if \c NULL, and the list is not storing pointers, sort and find |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
63 | * functions will not work) |
324 | 64 | * @param elem_size the size of each element in bytes |
174 | 65 | * @return the created list |
66 | */ | |
67 | CxList *cxLinkedListCreate( | |
324 | 68 | const CxAllocator *allocator, |
174 | 69 | cx_compare_func comparator, |
324 | 70 | size_t elem_size |
174 | 71 | ); |
72 | ||
73 | /** | |
324 | 74 | * Allocates a linked list for storing elements with \p elem_size bytes each. |
174 | 75 | * |
76 | * The list will use cxDefaultAllocator and no comparator function. If you want | |
77 | * to call functions that need a comparator, you must either set one immediately | |
78 | * after list creation or use cxLinkedListCreate(). | |
79 | * | |
324 | 80 | * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
81 | * cxListStorePointers() was called immediately after creation and the compare |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
82 | * function will be automatically set to cx_cmp_ptr(). |
174 | 83 | * |
324 | 84 | * @param elem_size the size of each element in bytes |
174 | 85 | * @return the created list |
86 | */ | |
324 | 87 | #define cxLinkedListCreateSimple(elem_size) \ |
88 | cxLinkedListCreate(NULL, NULL, elem_size) | |
174 | 89 | |
90 | /** | |
91 | * Finds the node at a certain index. | |
92 | * | |
93 | * This function can be used to start at an arbitrary position within the list. | |
94 | * If the search index is large than the start index, \p loc_advance must denote | |
95 | * the location of some sort of \c next pointer (i.e. a pointer to the next node). | |
96 | * But it is also possible that the search index is smaller than the start index | |
97 | * (e.g. in cases where traversing a list backwards is faster) in which case | |
98 | * \p loc_advance must denote the location of some sort of \c prev pointer | |
99 | * (i.e. a pointer to the previous node). | |
100 | * | |
101 | * @param start a pointer to the start node | |
102 | * @param start_index the start index | |
103 | * @param loc_advance the location of the pointer to advance | |
104 | * @param index the search index | |
105 | * @return the node found at the specified index | |
106 | */ | |
324 | 107 | __attribute__((__nonnull__)) |
174 | 108 | void *cx_linked_list_at( |
324 | 109 | const void *start, |
174 | 110 | size_t start_index, |
111 | ptrdiff_t loc_advance, | |
112 | size_t index | |
324 | 113 | ); |
174 | 114 | |
115 | /** | |
116 | * Finds the index of an element within a linked list. | |
117 | * | |
118 | * @param start a pointer to the start node | |
119 | * @param loc_advance the location of the pointer to advance | |
120 | * @param loc_data the location of the \c data pointer within your node struct | |
121 | * @param cmp_func a compare function to compare \p elem against the node data | |
122 | * @param elem a pointer to the element to find | |
123 | * @return the index of the element or a negative value if it could not be found | |
124 | */ | |
324 | 125 | __attribute__((__nonnull__)) |
174 | 126 | ssize_t cx_linked_list_find( |
324 | 127 | const void *start, |
174 | 128 | ptrdiff_t loc_advance, |
129 | ptrdiff_t loc_data, | |
130 | cx_compare_func cmp_func, | |
324 | 131 | const void *elem |
132 | ); | |
174 | 133 | |
134 | /** | |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
135 | * Finds the node containing an element within a linked list. |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
136 | * |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
137 | * @param result a pointer to the memory where the node pointer (or \c NULL if the element |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
138 | * could not be found) shall be stored to |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
139 | * @param start a pointer to the start node |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
140 | * @param loc_advance the location of the pointer to advance |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
141 | * @param loc_data the location of the \c data pointer within your node struct |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
142 | * @param cmp_func a compare function to compare \p elem against the node data |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
143 | * @param elem a pointer to the element to find |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
144 | * @return the index of the element or a negative value if it could not be found |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
145 | */ |
324 | 146 | __attribute__((__nonnull__)) |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
147 | ssize_t cx_linked_list_find_node( |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
148 | void **result, |
324 | 149 | const void *start, |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
150 | ptrdiff_t loc_advance, |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
151 | ptrdiff_t loc_data, |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
152 | cx_compare_func cmp_func, |
324 | 153 | const void *elem |
154 | ); | |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
155 | |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
174
diff
changeset
|
156 | /** |
174 | 157 | * Finds the first node in a linked list. |
158 | * | |
159 | * The function starts with the pointer denoted by \p node and traverses the list | |
160 | * along a prev pointer whose location within the node struct is | |
161 | * denoted by \p loc_prev. | |
162 | * | |
163 | * @param node a pointer to a node in the list | |
164 | * @param loc_prev the location of the \c prev pointer | |
165 | * @return a pointer to the first node | |
166 | */ | |
324 | 167 | __attribute__((__nonnull__)) |
174 | 168 | void *cx_linked_list_first( |
324 | 169 | const void *node, |
174 | 170 | ptrdiff_t loc_prev |
324 | 171 | ); |
174 | 172 | |
173 | /** | |
174 | * Finds the last node in a linked list. | |
175 | * | |
176 | * The function starts with the pointer denoted by \p node and traverses the list | |
177 | * along a next pointer whose location within the node struct is | |
178 | * denoted by \p loc_next. | |
179 | * | |
180 | * @param node a pointer to a node in the list | |
181 | * @param loc_next the location of the \c next pointer | |
182 | * @return a pointer to the last node | |
183 | */ | |
324 | 184 | __attribute__((__nonnull__)) |
174 | 185 | void *cx_linked_list_last( |
324 | 186 | const void *node, |
174 | 187 | ptrdiff_t loc_next |
324 | 188 | ); |
174 | 189 | |
190 | /** | |
191 | * Finds the predecessor of a node in case it is not linked. | |
192 | * | |
193 | * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined. | |
194 | * | |
195 | * @param begin the node where to start the search | |
196 | * @param loc_next the location of the \c next pointer | |
197 | * @param node the successor of the node to find | |
198 | * @return the node or \c NULL if \p node has no predecessor | |
199 | */ | |
324 | 200 | __attribute__((__nonnull__)) |
174 | 201 | void *cx_linked_list_prev( |
324 | 202 | const void *begin, |
174 | 203 | ptrdiff_t loc_next, |
324 | 204 | const void *node |
205 | ); | |
174 | 206 | |
207 | /** | |
208 | * Adds a new node to a linked list. | |
209 | * The node must not be part of any list already. | |
210 | * | |
211 | * \remark One of the pointers \p begin or \p end may be \c NULL, but not both. | |
212 | * | |
213 | * @param begin a pointer to the begin node pointer (if your list has one) | |
214 | * @param end a pointer to the end node pointer (if your list has one) | |
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 | * @param new_node a pointer to the node that shall be appended | |
218 | */ | |
324 | 219 | __attribute__((__nonnull__(5))) |
174 | 220 | void cx_linked_list_add( |
221 | void **begin, | |
222 | void **end, | |
223 | ptrdiff_t loc_prev, | |
224 | ptrdiff_t loc_next, | |
225 | void *new_node | |
324 | 226 | ); |
174 | 227 | |
228 | /** | |
229 | * Prepends a new node to a linked list. | |
230 | * The node must not be part of any list already. | |
231 | * | |
232 | * \remark One of the pointers \p begin or \p end may be \c NULL, but not both. | |
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 new_node a pointer to the node that shall be prepended | |
239 | */ | |
324 | 240 | __attribute__((__nonnull__(5))) |
174 | 241 | void cx_linked_list_prepend( |
242 | void **begin, | |
243 | void **end, | |
244 | ptrdiff_t loc_prev, | |
245 | ptrdiff_t loc_next, | |
246 | void *new_node | |
324 | 247 | ); |
174 | 248 | |
249 | /** | |
250 | * Links two nodes. | |
251 | * | |
252 | * @param left the new predecessor of \p right | |
253 | * @param right the new successor of \p left | |
254 | * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
255 | * @param loc_next the location of a \c next pointer within your node struct (required) | |
256 | */ | |
324 | 257 | __attribute__((__nonnull__)) |
174 | 258 | void cx_linked_list_link( |
259 | void *left, | |
260 | void *right, | |
261 | ptrdiff_t loc_prev, | |
262 | ptrdiff_t loc_next | |
324 | 263 | ); |
174 | 264 | |
265 | /** | |
266 | * Unlinks two nodes. | |
267 | * | |
268 | * If right is not the successor of left, the behavior is undefined. | |
269 | * | |
270 | * @param left the predecessor of \p right | |
271 | * @param right the successor of \p left | |
272 | * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
273 | * @param loc_next the location of a \c next pointer within your node struct (required) | |
274 | */ | |
324 | 275 | __attribute__((__nonnull__)) |
174 | 276 | void cx_linked_list_unlink( |
277 | void *left, | |
278 | void *right, | |
279 | ptrdiff_t loc_prev, | |
280 | ptrdiff_t loc_next | |
324 | 281 | ); |
174 | 282 | |
283 | /** | |
284 | * Inserts a new node after a given node of a linked list. | |
285 | * The new node must not be part of any list already. | |
286 | * | |
287 | * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or | |
288 | * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list. | |
289 | * | |
290 | * @param begin a pointer to the begin node pointer (if your list has one) | |
291 | * @param end a pointer to the end node pointer (if your list has one) | |
292 | * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
293 | * @param loc_next the location of a \c next pointer within your node struct (required) | |
294 | * @param node the node after which to insert (\c NULL if you want to prepend the node to the list) | |
324 | 295 | * @param new_node a pointer to the node that shall be inserted |
174 | 296 | */ |
324 | 297 | __attribute__((__nonnull__(6))) |
174 | 298 | void cx_linked_list_insert( |
299 | void **begin, | |
300 | void **end, | |
301 | ptrdiff_t loc_prev, | |
302 | ptrdiff_t loc_next, | |
303 | void *node, | |
304 | void *new_node | |
324 | 305 | ); |
174 | 306 | |
307 | /** | |
308 | * Inserts a chain of nodes after a given node of a linked list. | |
309 | * The chain must not be part of any list already. | |
310 | * | |
311 | * If you do not explicitly specify the end of the chain, it will be determined by traversing | |
312 | * the \c next pointer. | |
313 | * | |
314 | * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or | |
315 | * the \p end pointer to determine the start of the list. If only the \p end pointer is specified, you also need | |
316 | * to provide a valid \p loc_prev location. | |
317 | * Then the chain will be prepended to the list. | |
318 | * | |
319 | * @param begin a pointer to the begin node pointer (if your list has one) | |
320 | * @param end a pointer to the end node pointer (if your list has one) | |
321 | * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
322 | * @param loc_next the location of a \c next pointer within your node struct (required) | |
323 | * @param node the node after which to insert (\c NULL to prepend the chain to the list) | |
324 | * @param insert_begin a pointer to the first node of the chain that shall be inserted | |
325 | * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) | |
326 | */ | |
324 | 327 | __attribute__((__nonnull__(6))) |
174 | 328 | void cx_linked_list_insert_chain( |
329 | void **begin, | |
330 | void **end, | |
331 | ptrdiff_t loc_prev, | |
332 | ptrdiff_t loc_next, | |
333 | void *node, | |
334 | void *insert_begin, | |
335 | void *insert_end | |
324 | 336 | ); |
337 | ||
338 | /** | |
339 | * Inserts a node into a sorted linked list. | |
340 | * The new node must not be part of any list already. | |
341 | * | |
342 | * If the list starting with the node pointed to by \p begin is not sorted | |
343 | * already, the behavior is undefined. | |
344 | * | |
345 | * @param begin a pointer to the begin node pointer (required) | |
346 | * @param end a pointer to the end node pointer (if your list has one) | |
347 | * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
348 | * @param loc_next the location of a \c next pointer within your node struct (required) | |
349 | * @param new_node a pointer to the node that shall be inserted | |
350 | * @param cmp_func a compare function that will receive the node pointers | |
351 | */ | |
352 | __attribute__((__nonnull__(1, 5, 6))) | |
353 | void cx_linked_list_insert_sorted( | |
354 | void **begin, | |
355 | void **end, | |
356 | ptrdiff_t loc_prev, | |
357 | ptrdiff_t loc_next, | |
358 | void *new_node, | |
359 | cx_compare_func cmp_func | |
360 | ); | |
361 | ||
362 | /** | |
363 | * Inserts a chain of nodes into a sorted linked list. | |
364 | * The chain must not be part of any list already. | |
365 | * | |
366 | * If either the list starting with the node pointed to by \p begin or the list | |
367 | * starting with \p insert_begin is not sorted, the behavior is undefined. | |
368 | * | |
369 | * \attention In contrast to cx_linked_list_insert_chain(), the source chain | |
370 | * will be broken and inserted into the target list so that the resulting list | |
371 | * will be sorted according to \p cmp_func. That means, each node in the source | |
372 | * chain may be re-linked with nodes from the target list. | |
373 | * | |
374 | * @param begin a pointer to the begin node pointer (required) | |
375 | * @param end a pointer to the end node pointer (if your list has one) | |
376 | * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
377 | * @param loc_next the location of a \c next pointer within your node struct (required) | |
378 | * @param insert_begin a pointer to the first node of the chain that shall be inserted | |
379 | * @param cmp_func a compare function that will receive the node pointers | |
380 | */ | |
381 | __attribute__((__nonnull__(1, 5, 6))) | |
382 | void cx_linked_list_insert_sorted_chain( | |
383 | void **begin, | |
384 | void **end, | |
385 | ptrdiff_t loc_prev, | |
386 | ptrdiff_t loc_next, | |
387 | void *insert_begin, | |
388 | cx_compare_func cmp_func | |
389 | ); | |
174 | 390 | |
391 | /** | |
392 | * Removes a node from the linked list. | |
393 | * | |
394 | * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end) | |
395 | * addresses are provided, the pointers are adjusted accordingly. | |
396 | * | |
397 | * The following combinations of arguments are valid (more arguments are optional): | |
398 | * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance) | |
399 | * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance) | |
400 | * | |
401 | * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used | |
402 | * to traverse to a former adjacent node in the list. | |
403 | * | |
404 | * @param begin a pointer to the begin node pointer (optional) | |
405 | * @param end a pointer to the end node pointer (optional) | |
406 | * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
407 | * @param loc_next the location of a \c next pointer within your node struct (required) | |
408 | * @param node the node to remove | |
409 | */ | |
324 | 410 | __attribute__((__nonnull__(5))) |
174 | 411 | void cx_linked_list_remove( |
412 | void **begin, | |
413 | void **end, | |
414 | ptrdiff_t loc_prev, | |
415 | ptrdiff_t loc_next, | |
416 | void *node | |
324 | 417 | ); |
174 | 418 | |
419 | ||
420 | /** | |
421 | * Determines the size of a linked list starting with \p node. | |
422 | * @param node the first node | |
423 | * @param loc_next the location of the \c next pointer within the node struct | |
424 | * @return the size of the list or zero if \p node is \c NULL | |
425 | */ | |
426 | size_t cx_linked_list_size( | |
324 | 427 | const void *node, |
174 | 428 | ptrdiff_t loc_next |
429 | ); | |
430 | ||
431 | /** | |
432 | * Sorts a linked list based on a comparison function. | |
433 | * | |
434 | * This function can work with linked lists of the following structure: | |
435 | * \code | |
436 | * typedef struct node node; | |
437 | * struct node { | |
438 | * node* prev; | |
439 | * node* next; | |
440 | * my_payload data; | |
441 | * } | |
442 | * \endcode | |
443 | * | |
444 | * @note This is a recursive function with at most logarithmic recursion depth. | |
445 | * | |
446 | * @param begin a pointer to the begin node pointer (required) | |
447 | * @param end a pointer to the end node pointer (optional) | |
448 | * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present) | |
449 | * @param loc_next the location of a \c next pointer within your node struct (required) | |
450 | * @param loc_data the location of the \c data pointer within your node struct | |
451 | * @param cmp_func the compare function defining the sort order | |
452 | */ | |
324 | 453 | __attribute__((__nonnull__(1, 6))) |
174 | 454 | void cx_linked_list_sort( |
455 | void **begin, | |
456 | void **end, | |
457 | ptrdiff_t loc_prev, | |
458 | ptrdiff_t loc_next, | |
459 | ptrdiff_t loc_data, | |
460 | cx_compare_func cmp_func | |
324 | 461 | ); |
174 | 462 | |
463 | ||
464 | /** | |
465 | * Compares two lists element wise. | |
466 | * | |
467 | * \note Both list must have the same structure. | |
468 | * | |
469 | * @param begin_left the begin of the left list (\c NULL denotes an empty list) | |
470 | * @param begin_right the begin of the right list (\c NULL denotes an empty list) | |
471 | * @param loc_advance the location of the pointer to advance | |
472 | * @param loc_data the location of the \c data pointer within your node struct | |
473 | * @param cmp_func the function to compare the elements | |
474 | * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the | |
475 | * right list, positive if the left list is larger than the right list, zero if both lists are equal. | |
476 | */ | |
324 | 477 | __attribute__((__nonnull__(5))) |
174 | 478 | int cx_linked_list_compare( |
324 | 479 | const void *begin_left, |
480 | const void *begin_right, | |
174 | 481 | ptrdiff_t loc_advance, |
482 | ptrdiff_t loc_data, | |
483 | cx_compare_func cmp_func | |
324 | 484 | ); |
174 | 485 | |
486 | /** | |
487 | * Reverses the order of the nodes in a linked list. | |
488 | * | |
489 | * @param begin a pointer to the begin node pointer (required) | |
490 | * @param end a pointer to the end node pointer (optional) | |
491 | * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
492 | * @param loc_next the location of a \c next pointer within your node struct (required) | |
493 | */ | |
324 | 494 | __attribute__((__nonnull__(1))) |
174 | 495 | void cx_linked_list_reverse( |
496 | void **begin, | |
497 | void **end, | |
498 | ptrdiff_t loc_prev, | |
499 | ptrdiff_t loc_next | |
324 | 500 | ); |
174 | 501 | |
502 | #ifdef __cplusplus | |
503 | } // extern "C" | |
504 | #endif | |
505 | ||
506 | #endif // UCX_LINKED_LIST_H |