Mercurial > hg > ucx / file comparison

comparison: src/cx/linked_list.h

src/cx/linked_list.h

changeset 1675
36c0fb2b60b2
parent 1624
aab23807d562
equal deleted inserted replaced
1674:8b0f162ac88e 1675:36c0fb2b60b2
36 #ifndef UCX_LINKED_LIST_H 36 #ifndef UCX_LINKED_LIST_H
37 #define UCX_LINKED_LIST_H 37 #define UCX_LINKED_LIST_H
38 38
39 #include "common.h" 39 #include "common.h"
40 #include "list.h" 40 #include "list.h"
41
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45 41
46 /** 42 /**
47 * Metadata for a linked list. 43 * Metadata for a linked list.
48 */ 44 */
49 typedef struct cx_linked_list_s { 45 typedef struct cx_linked_list_s {
92 * @param allocator the allocator for allocating the list nodes 88 * @param allocator the allocator for allocating the list nodes
93 * (if @c NULL, the cxDefaultAllocator will be used) 89 * (if @c NULL, the cxDefaultAllocator will be used)
94 * @param elem_size the size of each element in bytes 90 * @param elem_size the size of each element in bytes
95 * @return the created list 91 * @return the created list
96 */ 92 */
97 cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxListFree, 1) 93 CX_EXTERN CX_NODISCARD CX_MALLOC CX_DEALLOC(cxListFree, 1)
98 CX_EXPORT CxList *cxLinkedListCreate(const CxAllocator *allocator, 94 CxList *cxLinkedListCreate(const CxAllocator *allocator,
99 size_t elem_size); 95 size_t elem_size);
100 96
101 /** 97 /**
102 * Instructs the linked list to reserve extra data in each node. 98 * Instructs the linked list to reserve extra data in each node.
103 * 99 *
110 * needs to store extra data in each node. 106 * needs to store extra data in each node.
111 * 107 *
112 * @param list the list (must be a linked list) 108 * @param list the list (must be a linked list)
113 * @param len the length of the extra data 109 * @param len the length of the extra data
114 */ 110 */
115 cx_attr_nonnull 111 CX_EXTERN CX_NONNULL
116 CX_EXPORT void cx_linked_list_extra_data(cx_linked_list *list, size_t len); 112 void cx_linked_list_extra_data(cx_linked_list *list, size_t len);
117 113
118 /** 114 /**
119 * Finds the node at a certain index. 115 * Finds the node at a certain index.
120 * 116 *
121 * This function can be used to start at an arbitrary position within the list. 117 * This function can be used to start at an arbitrary position within the list.
130 * @param start_index the start index 126 * @param start_index the start index
131 * @param loc_advance the location of the pointer to advance 127 * @param loc_advance the location of the pointer to advance
132 * @param index the search index 128 * @param index the search index
133 * @return the node found at the specified index 129 * @return the node found at the specified index
134 */ 130 */
135 cx_attr_nonnull cx_attr_nodiscard 131 CX_EXTERN CX_NONNULL CX_NODISCARD
136 CX_EXPORT void *cx_linked_list_at(const void *start,size_t start_index, 132 void *cx_linked_list_at(const void *start,size_t start_index,
137 ptrdiff_t loc_advance, size_t index); 133 ptrdiff_t loc_advance, size_t index);
138 134
139 /** 135 /**
140 * Finds the node containing an element within a linked list. 136 * Finds the node containing an element within a linked list.
141 * 137 *
146 * @param found_index an optional pointer where the index of the found node 142 * @param found_index an optional pointer where the index of the found node
147 * (given that @p start has index 0) is stored 143 * (given that @p start has index 0) is stored
148 * @param cmp_func a compare function to compare @p elem against the node data 144 * @param cmp_func a compare function to compare @p elem against the node data
149 * @return a pointer to the found node or @c NULL if no matching node was found 145 * @return a pointer to the found node or @c NULL if no matching node was found
150 */ 146 */
151 cx_attr_nonnull_arg(1, 4, 6) 147 CX_EXTERN CX_NONNULL_ARG(1, 4, 6)
152 CX_EXPORT void *cx_linked_list_find(const void *start, ptrdiff_t loc_advance, 148 void *cx_linked_list_find(const void *start, ptrdiff_t loc_advance,
153 ptrdiff_t loc_data, const void *elem, size_t *found_index, 149 ptrdiff_t loc_data, const void *elem, size_t *found_index,
154 cx_compare_func cmp_func); 150 cx_compare_func cmp_func);
155 151
156 /** 152 /**
157 * Finds the node containing an element within a linked list. 153 * Finds the node containing an element within a linked list.
164 * (given that @p start has index 0) is stored 160 * (given that @p start has index 0) is stored
165 * @param cmp_func a compare function to compare @p elem against the node data 161 * @param cmp_func a compare function to compare @p elem against the node data
166 * @param context additional context for the compare function 162 * @param context additional context for the compare function
167 * @return a pointer to the found node or @c NULL if no matching node was found 163 * @return a pointer to the found node or @c NULL if no matching node was found
168 */ 164 */
169 cx_attr_nonnull_arg(1, 4, 6) 165 CX_EXTERN CX_NONNULL_ARG(1, 4, 6)
170 CX_EXPORT void *cx_linked_list_find_c(const void *start, ptrdiff_t loc_advance, 166 void *cx_linked_list_find_c(const void *start, ptrdiff_t loc_advance,
171 ptrdiff_t loc_data, const void *elem, size_t *found_index, 167 ptrdiff_t loc_data, const void *elem, size_t *found_index,
172 cx_compare_func2 cmp_func, void *context); 168 cx_compare_func2 cmp_func, void *context);
173 169
174 /** 170 /**
175 * Finds the first node in a linked list. 171 * Finds the first node in a linked list.
180 * 176 *
181 * @param node a pointer to a node in the list 177 * @param node a pointer to a node in the list
182 * @param loc_prev the location of the @c prev pointer 178 * @param loc_prev the location of the @c prev pointer
183 * @return a pointer to the first node 179 * @return a pointer to the first node
184 */ 180 */
185 cx_attr_nonnull cx_attr_returns_nonnull 181 CX_EXTERN CX_NONNULL CX_RETURNS_NONNULL
186 CX_EXPORT void *cx_linked_list_first(const void *node, ptrdiff_t loc_prev); 182 void *cx_linked_list_first(const void *node, ptrdiff_t loc_prev);
187 183
188 /** 184 /**
189 * Finds the last node in a linked list. 185 * Finds the last node in a linked list.
190 * 186 *
191 * The function starts with the pointer denoted by @p node and traverses the list 187 * The function starts with the pointer denoted by @p node and traverses the list
194 * 190 *
195 * @param node a pointer to a node in the list 191 * @param node a pointer to a node in the list
196 * @param loc_next the location of the @c next pointer 192 * @param loc_next the location of the @c next pointer
197 * @return a pointer to the last node 193 * @return a pointer to the last node
198 */ 194 */
199 cx_attr_nonnull cx_attr_returns_nonnull 195 CX_EXTERN CX_NONNULL CX_RETURNS_NONNULL
200 CX_EXPORT void *cx_linked_list_last(const void *node, ptrdiff_t loc_next); 196 void *cx_linked_list_last(const void *node, ptrdiff_t loc_next);
201 197
202 /** 198 /**
203 * Finds the predecessor of a node in case it is not linked. 199 * Finds the predecessor of a node in case it is not linked.
204 * 200 *
205 * @remark If @p node is not contained in the list starting with @p begin, the behavior is undefined. 201 * @remark If @p node is not contained in the list starting with @p begin, the behavior is undefined.
207 * @param begin the node where to start the search 203 * @param begin the node where to start the search
208 * @param loc_next the location of the @c next pointer 204 * @param loc_next the location of the @c next pointer
209 * @param node the successor of the node to find 205 * @param node the successor of the node to find
210 * @return the node or @c NULL if @p node has no predecessor 206 * @return the node or @c NULL if @p node has no predecessor
211 */ 207 */
212 cx_attr_nonnull 208 CX_EXTERN CX_NONNULL
213 CX_EXPORT void *cx_linked_list_prev(const void *begin, ptrdiff_t loc_next, const void *node); 209 void *cx_linked_list_prev(const void *begin, ptrdiff_t loc_next, const void *node);
214 210
215 /** 211 /**
216 * Adds a new node to a linked list. 212 * Adds a new node to a linked list.
217 * The node must not be part of any list yet. 213 * The node must not be part of any list yet.
218 * 214 *
222 * @param end a pointer to the end node pointer (if your list has one) 218 * @param end a pointer to the end node pointer (if your list has one)
223 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 219 * @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) 220 * @param loc_next the location of a @c next pointer within your node struct (required)
225 * @param new_node a pointer to the node that shall be appended 221 * @param new_node a pointer to the node that shall be appended
226 */ 222 */
227 cx_attr_nonnull_arg(5) 223 CX_EXTERN CX_NONNULL_ARG(5)
228 CX_EXPORT void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node); 224 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
229 225
230 /** 226 /**
231 * Prepends a new node to a linked list. 227 * Prepends a new node to a linked list.
232 * The node must not be part of any list yet. 228 * The node must not be part of any list yet.
233 * 229 *
237 * @param end a pointer to the end node pointer (if your list has one) 233 * @param end a pointer to the end node pointer (if your list has one)
238 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 234 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
239 * @param loc_next the location of a @c next pointer within your node struct (required) 235 * @param loc_next the location of a @c next pointer within your node struct (required)
240 * @param new_node a pointer to the node that shall be prepended 236 * @param new_node a pointer to the node that shall be prepended
241 */ 237 */
242 cx_attr_nonnull_arg(5) 238 CX_EXTERN CX_NONNULL_ARG(5)
243 CX_EXPORT void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node); 239 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
244 240
245 /** 241 /**
246 * Links two nodes. 242 * Links two nodes.
247 * 243 *
248 * @param left the new predecessor of @p right 244 * @param left the new predecessor of @p right
249 * @param right the new successor of @p left 245 * @param right the new successor of @p left
250 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 246 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
251 * @param loc_next the location of a @c next pointer within your node struct (required) 247 * @param loc_next the location of a @c next pointer within your node struct (required)
252 */ 248 */
253 cx_attr_nonnull 249 CX_EXTERN CX_NONNULL
254 CX_EXPORT void cx_linked_list_link(void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next); 250 void cx_linked_list_link(void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next);
255 251
256 /** 252 /**
257 * Unlinks two nodes. 253 * Unlinks two nodes.
258 * 254 *
259 * If right is not the successor of left, the behavior is undefined. 255 * If right is not the successor of left, the behavior is undefined.
261 * @param left the predecessor of @p right 257 * @param left the predecessor of @p right
262 * @param right the successor of @p left 258 * @param right the successor of @p left
263 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 259 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
264 * @param loc_next the location of a @c next pointer within your node struct (required) 260 * @param loc_next the location of a @c next pointer within your node struct (required)
265 */ 261 */
266 cx_attr_nonnull 262 CX_EXTERN CX_NONNULL
267 CX_EXPORT void cx_linked_list_unlink(void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next); 263 void cx_linked_list_unlink(void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next);
268 264
269 /** 265 /**
270 * Inserts a new node after a given node of a linked list. 266 * Inserts a new node after a given node of a linked list.
271 * The new node must not be part of any list yet. 267 * The new node must not be part of any list yet.
272 * 268 *
278 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 274 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
279 * @param loc_next the location of a @c next pointer within your node struct (required) 275 * @param loc_next the location of a @c next pointer within your node struct (required)
280 * @param node the node after which to insert (@c NULL if you want to prepend the node to the list) 276 * @param node the node after which to insert (@c NULL if you want to prepend the node to the list)
281 * @param new_node a pointer to the node that shall be inserted 277 * @param new_node a pointer to the node that shall be inserted
282 */ 278 */
283 cx_attr_nonnull_arg(6) 279 CX_EXTERN CX_NONNULL_ARG(6)
284 CX_EXPORT void cx_linked_list_insert(void **begin, void **end, 280 void cx_linked_list_insert(void **begin, void **end,
285 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *new_node); 281 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *new_node);
286 282
287 /** 283 /**
288 * Inserts a chain of nodes after a given node of a linked list. 284 * Inserts a chain of nodes after a given node of a linked list.
289 * The chain must not be part of any list yet. 285 * The chain must not be part of any list yet.
302 * @param loc_next the location of a @c next pointer within your node struct (required) 298 * @param loc_next the location of a @c next pointer within your node struct (required)
303 * @param node the node after which to insert (@c NULL to prepend the chain to the list) 299 * @param node the node after which to insert (@c NULL to prepend the chain to the list)
304 * @param insert_begin a pointer to the first node of the chain that shall be inserted 300 * @param insert_begin a pointer to the first node of the chain that shall be inserted
305 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) 301 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
306 */ 302 */
307 cx_attr_nonnull_arg(6) 303 CX_EXTERN CX_NONNULL_ARG(6)
308 CX_EXPORT void cx_linked_list_insert_chain(void **begin, void **end, 304 void cx_linked_list_insert_chain(void **begin, void **end,
309 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *insert_begin, void *insert_end); 305 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *insert_begin, void *insert_end);
310 306
311 /** 307 /**
312 * Inserts a node into a sorted linked list. 308 * Inserts a node into a sorted linked list.
313 * The new node must not be part of any list yet. 309 * The new node must not be part of any list yet.
320 * @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_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
321 * @param loc_next the location of a @c next pointer within your node struct (required) 317 * @param loc_next the location of a @c next pointer within your node struct (required)
322 * @param new_node a pointer to the node that shall be inserted 318 * @param new_node a pointer to the node that shall be inserted
323 * @param cmp_func a compare function that will receive the node pointers 319 * @param cmp_func a compare function that will receive the node pointers
324 */ 320 */
325 cx_attr_nonnull_arg(1, 5, 6) 321 CX_EXTERN CX_NONNULL_ARG(1, 5, 6)
326 CX_EXPORT void cx_linked_list_insert_sorted(void **begin, void **end, 322 void cx_linked_list_insert_sorted(void **begin, void **end,
327 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func); 323 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func);
328 324
329 /** 325 /**
330 * Inserts a chain of nodes into a sorted linked list. 326 * Inserts a chain of nodes into a sorted linked list.
331 * The chain must not be part of any list yet. 327 * The chain must not be part of any list yet.
343 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 339 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
344 * @param loc_next the location of a @c next pointer within your node struct (required) 340 * @param loc_next the location of a @c next pointer within your node struct (required)
345 * @param insert_begin a pointer to the first node of the chain that shall be inserted 341 * @param insert_begin a pointer to the first node of the chain that shall be inserted
346 * @param cmp_func a compare function that will receive the node pointers 342 * @param cmp_func a compare function that will receive the node pointers
347 */ 343 */
348 cx_attr_nonnull_arg(1, 5, 6) 344 CX_EXTERN CX_NONNULL_ARG(1, 5, 6)
349 CX_EXPORT void cx_linked_list_insert_sorted_chain(void **begin, void **end, 345 void cx_linked_list_insert_sorted_chain(void **begin, void **end,
350 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func); 346 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func);
351 347
352 /** 348 /**
353 * Inserts a node into a sorted linked list if no other node with the same value already exists. 349 * Inserts a node into a sorted linked list if no other node with the same value already exists.
354 * The new node must not be part of any list yet. 350 * The new node must not be part of any list yet.
363 * @param new_node a pointer to the node that shall be inserted 359 * @param new_node a pointer to the node that shall be inserted
364 * @param cmp_func a compare function that will receive the node pointers 360 * @param cmp_func a compare function that will receive the node pointers
365 * @retval zero when the node was inserted 361 * @retval zero when the node was inserted
366 * @retval non-zero when a node with the same value already exists 362 * @retval non-zero when a node with the same value already exists
367 */ 363 */
368 cx_attr_nonnull_arg(1, 5, 6) 364 CX_EXTERN CX_NONNULL_ARG(1, 5, 6)
369 CX_EXPORT int cx_linked_list_insert_unique(void **begin, void **end, 365 int cx_linked_list_insert_unique(void **begin, void **end,
370 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func); 366 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func);
371 367
372 /** 368 /**
373 * Inserts a chain of nodes into a sorted linked list, avoiding duplicates. 369 * Inserts a chain of nodes into a sorted linked list, avoiding duplicates.
374 * The chain must not be part of any list yet. 370 * The chain must not be part of any list yet.
385 * @param loc_next the location of a @c next pointer within your node struct (required) 381 * @param loc_next the location of a @c next pointer within your node struct (required)
386 * @param insert_begin a pointer to the first node of the chain that shall be inserted 382 * @param insert_begin a pointer to the first node of the chain that shall be inserted
387 * @param cmp_func a compare function that will receive the node pointers 383 * @param cmp_func a compare function that will receive the node pointers
388 * @return a pointer to a new chain with all duplicates that were not inserted (or @c NULL when there were no duplicates) 384 * @return a pointer to a new chain with all duplicates that were not inserted (or @c NULL when there were no duplicates)
389 */ 385 */
390 cx_attr_nonnull_arg(1, 5, 6) cx_attr_nodiscard 386 CX_EXTERN CX_NONNULL_ARG(1, 5, 6) CX_NODISCARD
391 CX_EXPORT void *cx_linked_list_insert_unique_chain(void **begin, void **end, 387 void *cx_linked_list_insert_unique_chain(void **begin, void **end,
392 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func); 388 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func);
393 389
394 /** 390 /**
395 * Inserts a node into a sorted linked list. 391 * Inserts a node into a sorted linked list.
396 * The new node must not be part of any list yet. 392 * The new node must not be part of any list yet.
404 * @param loc_next the location of a @c next pointer within your node struct (required) 400 * @param loc_next the location of a @c next pointer within your node struct (required)
405 * @param new_node a pointer to the node that shall be inserted 401 * @param new_node a pointer to the node that shall be inserted
406 * @param cmp_func a compare function that will receive the node pointers 402 * @param cmp_func a compare function that will receive the node pointers
407 * @param context context for the compare function 403 * @param context context for the compare function
408 */ 404 */
409 cx_attr_nonnull_arg(1, 5, 6) 405 CX_EXTERN CX_NONNULL_ARG(1, 5, 6)
410 CX_EXPORT void cx_linked_list_insert_sorted_c(void **begin, void **end, 406 void cx_linked_list_insert_sorted_c(void **begin, void **end,
411 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func2 cmp_func, void *context); 407 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func2 cmp_func, void *context);
412 408
413 /** 409 /**
414 * Inserts a chain of nodes into a sorted linked list. 410 * Inserts a chain of nodes into a sorted linked list.
415 * The chain must not be part of any list yet. 411 * The chain must not be part of any list yet.
428 * @param loc_next the location of a @c next pointer within your node struct (required) 424 * @param loc_next the location of a @c next pointer within your node struct (required)
429 * @param insert_begin a pointer to the first node of the chain that shall be inserted 425 * @param insert_begin a pointer to the first node of the chain that shall be inserted
430 * @param cmp_func a compare function that will receive the node pointers 426 * @param cmp_func a compare function that will receive the node pointers
431 * @param context context for the compare function 427 * @param context context for the compare function
432 */ 428 */
433 cx_attr_nonnull_arg(1, 5, 6) 429 CX_EXTERN CX_NONNULL_ARG(1, 5, 6)
434 CX_EXPORT void cx_linked_list_insert_sorted_chain_c(void **begin, void **end, 430 void cx_linked_list_insert_sorted_chain_c(void **begin, void **end,
435 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func2 cmp_func, void *context); 431 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func2 cmp_func, void *context);
436 432
437 /** 433 /**
438 * Inserts a node into a sorted linked list if no other node with the same value already exists. 434 * Inserts a node into a sorted linked list if no other node with the same value already exists.
439 * The new node must not be part of any list yet. 435 * The new node must not be part of any list yet.
448 * @param new_node a pointer to the node that shall be inserted 444 * @param new_node a pointer to the node that shall be inserted
449 * @param cmp_func a compare function that will receive the node pointers 445 * @param cmp_func a compare function that will receive the node pointers
450 * @retval zero when the node was inserted 446 * @retval zero when the node was inserted
451 * @retval non-zero when a node with the same value already exists 447 * @retval non-zero when a node with the same value already exists
452 */ 448 */
453 cx_attr_nonnull_arg(1, 5, 6) 449 CX_EXTERN CX_NONNULL_ARG(1, 5, 6)
454 CX_EXPORT int cx_linked_list_insert_unique_c(void **begin, void **end, 450 int cx_linked_list_insert_unique_c(void **begin, void **end,
455 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func2 cmp_func, void *context); 451 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func2 cmp_func, void *context);
456 452
457 /** 453 /**
458 * Inserts a chain of nodes into a sorted linked list, avoiding duplicates. 454 * Inserts a chain of nodes into a sorted linked list, avoiding duplicates.
459 * The chain must not be part of any list yet. 455 * The chain must not be part of any list yet.
471 * @param insert_begin a pointer to the first node of the chain that shall be inserted 467 * @param insert_begin a pointer to the first node of the chain that shall be inserted
472 * @param cmp_func a compare function that will receive the node pointers 468 * @param cmp_func a compare function that will receive the node pointers
473 * @param context context for the compare function 469 * @param context context for the compare function
474 * @return a pointer to a new chain with all duplicates that were not inserted (or @c NULL when there were no duplicates) 470 * @return a pointer to a new chain with all duplicates that were not inserted (or @c NULL when there were no duplicates)
475 */ 471 */
476 cx_attr_nonnull_arg(1, 5, 6) cx_attr_nodiscard 472 CX_EXTERN CX_NONNULL_ARG(1, 5, 6) CX_NODISCARD
477 CX_EXPORT void *cx_linked_list_insert_unique_chain_c(void **begin, void **end, 473 void *cx_linked_list_insert_unique_chain_c(void **begin, void **end,
478 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func2 cmp_func, void *context); 474 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func2 cmp_func, void *context);
479 475
480 /** 476 /**
481 * Removes a chain of nodes from the linked list. 477 * Removes a chain of nodes from the linked list.
482 * 478 *
496 * @param loc_next the location of a @c next pointer within your node struct (required) 492 * @param loc_next the location of a @c next pointer within your node struct (required)
497 * @param node the start node of the chain 493 * @param node the start node of the chain
498 * @param num the number of nodes to remove 494 * @param num the number of nodes to remove
499 * @return the actual number of nodes that were removed (can be less when the list did not have enough nodes) 495 * @return the actual number of nodes that were removed (can be less when the list did not have enough nodes)
500 */ 496 */
501 cx_attr_nonnull_arg(5) 497 CX_EXTERN CX_NONNULL_ARG(5)
502 CX_EXPORT size_t cx_linked_list_remove_chain(void **begin, void **end, 498 size_t cx_linked_list_remove_chain(void **begin, void **end,
503 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, size_t num); 499 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, size_t num);
504 500
505 /** 501 /**
506 * Removes a node from the linked list. 502 * Removes a node from the linked list.
507 * 503 *
519 * @param end a pointer to the end node pointer (optional) 515 * @param end a pointer to the end node pointer (optional)
520 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 516 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
521 * @param loc_next the location of a @c next pointer within your node struct (required) 517 * @param loc_next the location of a @c next pointer within your node struct (required)
522 * @param node the node to remove 518 * @param node the node to remove
523 */ 519 */
524 cx_attr_nonnull_arg(5) 520 CX_EXTERN CX_NONNULL_ARG(5)
525 CX_EXPORT void cx_linked_list_remove(void **begin, void **end, 521 void cx_linked_list_remove(void **begin, void **end,
526 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node); 522 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node);
527 523
528 /** 524 /**
529 * Determines the size of a linked list starting with @p node. 525 * Determines the size of a linked list starting with @p node.
530 * 526 *
531 * @param node the first node 527 * @param node the first node
532 * @param loc_next the location of the @c next pointer within the node struct 528 * @param loc_next the location of the @c next pointer within the node struct
533 * @return the size of the list or zero if @p node is @c NULL 529 * @return the size of the list or zero if @p node is @c NULL
534 */ 530 */
535 cx_attr_nodiscard 531 CX_EXTERN CX_NODISCARD
536 CX_EXPORT size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next); 532 size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next);
537 533
538 /** 534 /**
539 * Sorts a linked list based on a comparison function. 535 * Sorts a linked list based on a comparison function.
540 * 536 *
541 * @note This is a recursive function with at most logarithmic recursion depth. 537 * @note This is a recursive function with at most logarithmic recursion depth.
545 * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present) 541 * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present)
546 * @param loc_next the location of a @c next pointer within your node struct (required) 542 * @param loc_next the location of a @c next pointer within your node struct (required)
547 * @param loc_data the location of the @c data pointer within your node struct 543 * @param loc_data the location of the @c data pointer within your node struct
548 * @param cmp_func the compare function defining the sort order 544 * @param cmp_func the compare function defining the sort order
549 */ 545 */
550 cx_attr_nonnull_arg(1, 6) 546 CX_EXTERN CX_NONNULL_ARG(1, 6)
551 CX_EXPORT void cx_linked_list_sort(void **begin, void **end, 547 void cx_linked_list_sort(void **begin, void **end,
552 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func); 548 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func);
553 549
554 /** 550 /**
555 * Sorts a linked list based on a comparison function. 551 * Sorts a linked list based on a comparison function.
556 * 552 *
562 * @param loc_next the location of a @c next pointer within your node struct (required) 558 * @param loc_next the location of a @c next pointer within your node struct (required)
563 * @param loc_data the location of the @c data pointer within your node struct 559 * @param loc_data the location of the @c data pointer within your node struct
564 * @param cmp_func the compare function defining the sort order 560 * @param cmp_func the compare function defining the sort order
565 * @param context additional context for the compare function 561 * @param context additional context for the compare function
566 */ 562 */
567 cx_attr_nonnull_arg(1, 6) 563 CX_EXTERN CX_NONNULL_ARG(1, 6)
568 CX_EXPORT void cx_linked_list_sort_c(void **begin, void **end, 564 void cx_linked_list_sort_c(void **begin, void **end,
569 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func2 cmp_func, void *context); 565 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func2 cmp_func, void *context);
570
571 566
572 /** 567 /**
573 * Compares two lists element wise. 568 * Compares two lists element wise.
574 * 569 *
575 * @attention Both lists must have the same structure. 570 * @attention Both lists must have the same structure.
580 * @param loc_data the location of the @c data pointer within your node struct 575 * @param loc_data the location of the @c data pointer within your node struct
581 * @param cmp_func the function to compare the elements 576 * @param cmp_func the function to compare the elements
582 * @return the first non-zero result of invoking @p cmp_func or: negative if the left list is smaller than the 577 * @return the first non-zero result of invoking @p cmp_func or: negative if the left list is smaller than the
583 * right list, positive if the left list is larger than the right list, zero if both lists are equal. 578 * right list, positive if the left list is larger than the right list, zero if both lists are equal.
584 */ 579 */
585 cx_attr_nonnull_arg(5) 580 CX_EXTERN CX_NONNULL_ARG(5)
586 CX_EXPORT int cx_linked_list_compare(const void *begin_left, const void *begin_right, 581 int cx_linked_list_compare(const void *begin_left, const void *begin_right,
587 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func); 582 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func);
588 583
589 /** 584 /**
590 * Compares two lists element wise. 585 * Compares two lists element wise.
591 * 586 *
597 * @param loc_data the location of the @c data pointer within your node struct 592 * @param loc_data the location of the @c data pointer within your node struct
598 * @param cmp_func the function to compare the elements 593 * @param cmp_func the function to compare the elements
599 * @return the first non-zero result of invoking @p cmp_func or: negative if the left list is smaller than the 594 * @return the first non-zero result of invoking @p cmp_func or: negative if the left list is smaller than the
600 * right list, positive if the left list is larger than the right list, zero if both lists are equal. 595 * right list, positive if the left list is larger than the right list, zero if both lists are equal.
601 */ 596 */
602 cx_attr_nonnull_arg(5) 597 CX_EXTERN CX_NONNULL_ARG(5)
603 CX_EXPORT int cx_linked_list_compare_c(const void *begin_left, const void *begin_right, 598 int cx_linked_list_compare_c(const void *begin_left, const void *begin_right,
604 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func2 cmp_func, void *context); 599 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func2 cmp_func, void *context);
605 600
606 /** 601 /**
607 * Reverses the order of the nodes in a linked list. 602 * Reverses the order of the nodes in a linked list.
608 * 603 *
609 * @param begin a pointer to the beginning node pointer (required) 604 * @param begin a pointer to the beginning node pointer (required)
610 * @param end a pointer to the end node pointer (optional) 605 * @param end a pointer to the end node pointer (optional)
611 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 606 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
612 * @param loc_next the location of a @c next pointer within your node struct (required) 607 * @param loc_next the location of a @c next pointer within your node struct (required)
613 */ 608 */
614 cx_attr_nonnull_arg(1) 609 CX_EXTERN CX_NONNULL_ARG(1)
615 CX_EXPORT void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next); 610 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next);
616
617 #ifdef __cplusplus
618 } // extern "C"
619 #endif
620 611
621 #endif // UCX_LINKED_LIST_H 612 #endif // UCX_LINKED_LIST_H

Mercurial Repository: ucx

mercurial