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