comparison: ucx/cx/linked_list.h
ucx/cx/linked_list.h
- changeset 31
- 287484519844
- parent 23
- b26390e77237
equal
deleted
inserted
replaced
| 30:d33eaaec15da | 31:287484519844 |
|---|---|
| 85 /** | 85 /** |
| 86 * Allocates a linked list for storing elements with @p elem_size bytes each. | 86 * Allocates a linked list for storing elements with @p elem_size bytes each. |
| 87 * | 87 * |
| 88 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of | 88 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of |
| 89 * copies of the added elements, and the compare function will be automatically set | 89 * copies of the added elements, and the compare function will be automatically set |
| 90 * to cx_cmp_ptr() if none is given. | 90 * to cx_cmp_ptr(). |
| 91 * | 91 * |
| 92 * @param allocator the allocator for allocating the list nodes | 92 * @param allocator the allocator for allocating the list nodes |
| 93 * (if @c NULL, the cxDefaultAllocator will be used) | 93 * (if @c NULL, the cxDefaultAllocator will be used) |
| 94 * @param comparator the comparator for the elements | |
| 95 * (if @c NULL, and the list is not storing pointers, sort and find | |
| 96 * functions will not work) | |
| 97 * @param elem_size the size of each element in bytes | 94 * @param elem_size the size of each element in bytes |
| 98 * @return the created list | 95 * @return the created list |
| 99 */ | 96 */ |
| 100 cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxListFree, 1) | 97 cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxListFree, 1) |
| 101 CX_EXPORT CxList *cxLinkedListCreate(const CxAllocator *allocator, | 98 CX_EXPORT CxList *cxLinkedListCreate(const CxAllocator *allocator, |
| 102 cx_compare_func comparator, size_t elem_size); | 99 size_t elem_size); |
| 103 | |
| 104 /** | |
| 105 * Allocates a linked list for storing elements with @p elem_size bytes each. | |
| 106 * | |
| 107 * The list will use cxDefaultAllocator and no comparator function. If you want | |
| 108 * to call functions that need a comparator, you must either set one immediately | |
| 109 * after list creation or use cxLinkedListCreate(). | |
| 110 * | |
| 111 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of | |
| 112 * copies of the added elements, and the compare function will be automatically set | |
| 113 * to cx_cmp_ptr(). | |
| 114 * | |
| 115 * @param elem_size (@c size_t) the size of each element in bytes | |
| 116 * @return (@c CxList*) the created list | |
| 117 */ | |
| 118 #define cxLinkedListCreateSimple(elem_size) \ | |
| 119 cxLinkedListCreate(NULL, NULL, elem_size) | |
| 120 | 100 |
| 121 /** | 101 /** |
| 122 * Instructs the linked list to reserve extra data in each node. | 102 * Instructs the linked list to reserve extra data in each node. |
| 123 * | 103 * |
| 124 * The extra data will be aligned and placed behind the element data. | 104 * The extra data will be aligned and placed behind the element data. |
| 160 * Finds the node containing an element within a linked list. | 140 * Finds the node containing an element within a linked list. |
| 161 * | 141 * |
| 162 * @param start a pointer to the start node | 142 * @param start a pointer to the start node |
| 163 * @param loc_advance the location of the pointer to advance | 143 * @param loc_advance the location of the pointer to advance |
| 164 * @param loc_data the location of the @c data pointer within your node struct | 144 * @param loc_data the location of the @c data pointer within your node struct |
| 165 * @param cmp_func a compare function to compare @p elem against the node data | |
| 166 * @param elem a pointer to the element to find | 145 * @param elem a pointer to the element to find |
| 167 * @param found_index an optional pointer where the index of the found node | 146 * @param found_index an optional pointer where the index of the found node |
| 168 * (given that @p start has index 0) is stored | 147 * (given that @p start has index 0) is stored |
| 148 * @param cmp_func a compare function to compare @p elem against the node data | |
| 169 * @return a pointer to the found node or @c NULL if no matching node was found | 149 * @return a pointer to the found node or @c NULL if no matching node was found |
| 170 */ | 150 */ |
| 171 cx_attr_nonnull_arg(1, 4, 5) | 151 cx_attr_nonnull_arg(1, 4, 6) |
| 172 CX_EXPORT void *cx_linked_list_find(const void *start, ptrdiff_t loc_advance, | 152 CX_EXPORT void *cx_linked_list_find(const void *start, ptrdiff_t loc_advance, |
| 173 ptrdiff_t loc_data, cx_compare_func cmp_func, const void *elem, | 153 ptrdiff_t loc_data, const void *elem, size_t *found_index, |
| 174 size_t *found_index); | 154 cx_compare_func cmp_func); |
| 155 | |
| 156 /** | |
| 157 * Finds the node containing an element within a linked list. | |
| 158 * | |
| 159 * @param start a pointer to the start node | |
| 160 * @param loc_advance the location of the pointer to advance | |
| 161 * @param loc_data the location of the @c data pointer within your node struct | |
| 162 * @param elem a pointer to the element to find | |
| 163 * @param found_index an optional pointer where the index of the found node | |
| 164 * (given that @p start has index 0) is stored | |
| 165 * @param cmp_func a compare function to compare @p elem against the node data | |
| 166 * @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 | |
| 168 */ | |
| 169 cx_attr_nonnull_arg(1, 4, 6) | |
| 170 CX_EXPORT 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, | |
| 172 cx_compare_func2 cmp_func, void *context); | |
| 175 | 173 |
| 176 /** | 174 /** |
| 177 * Finds the first node in a linked list. | 175 * Finds the first node in a linked list. |
| 178 * | 176 * |
| 179 * The function starts with the pointer denoted by @p node and traverses the list | 177 * The function starts with the pointer denoted by @p node and traverses the list |
| 392 cx_attr_nonnull_arg(1, 5, 6) cx_attr_nodiscard | 390 cx_attr_nonnull_arg(1, 5, 6) cx_attr_nodiscard |
| 393 CX_EXPORT void *cx_linked_list_insert_unique_chain(void **begin, void **end, | 391 CX_EXPORT void *cx_linked_list_insert_unique_chain(void **begin, void **end, |
| 394 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func); | 392 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func); |
| 395 | 393 |
| 396 /** | 394 /** |
| 395 * Inserts a node into a sorted linked list. | |
| 396 * The new node must not be part of any list yet. | |
| 397 * | |
| 398 * If the list starting with the node pointed to by @p begin is not sorted | |
| 399 * already, the behavior is undefined. | |
| 400 * | |
| 401 * @param begin a pointer to the beginning node pointer (required) | |
| 402 * @param end a pointer to the end node pointer (if your list has one) | |
| 403 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) | |
| 404 * @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 | |
| 406 * @param cmp_func a compare function that will receive the node pointers | |
| 407 * @param context context for the compare function | |
| 408 */ | |
| 409 cx_attr_nonnull_arg(1, 5, 6) | |
| 410 CX_EXPORT 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); | |
| 412 | |
| 413 /** | |
| 414 * Inserts a chain of nodes into a sorted linked list. | |
| 415 * The chain must not be part of any list yet. | |
| 416 * | |
| 417 * If either the list starting with the node pointed to by @p begin or the list | |
| 418 * starting with @p insert_begin is not sorted, the behavior is undefined. | |
| 419 * | |
| 420 * @attention In contrast to cx_linked_list_insert_chain(), the source chain | |
| 421 * will be broken and inserted into the target list so that the resulting list | |
| 422 * will be sorted according to @p cmp_func. That means each node in the source | |
| 423 * chain may be re-linked with nodes from the target list. | |
| 424 * | |
| 425 * @param begin a pointer to the beginning node pointer (required) | |
| 426 * @param end a pointer to the end node pointer (if your list has one) | |
| 427 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) | |
| 428 * @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 | |
| 430 * @param cmp_func a compare function that will receive the node pointers | |
| 431 * @param context context for the compare function | |
| 432 */ | |
| 433 cx_attr_nonnull_arg(1, 5, 6) | |
| 434 CX_EXPORT 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); | |
| 436 | |
| 437 /** | |
| 438 * 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. | |
| 440 * | |
| 441 * If the list starting with the node pointed to by @p begin is not sorted | |
| 442 * already, the behavior is undefined. | |
| 443 * | |
| 444 * @param begin a pointer to the beginning node pointer (required) | |
| 445 * @param end a pointer to the end node pointer (if your list has one) | |
| 446 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) | |
| 447 * @param loc_next the location of a @c next pointer within your node struct (required) | |
| 448 * @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 | |
| 450 * @retval zero when the node was inserted | |
| 451 * @retval non-zero when a node with the same value already exists | |
| 452 */ | |
| 453 cx_attr_nonnull_arg(1, 5, 6) | |
| 454 CX_EXPORT 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); | |
| 456 | |
| 457 /** | |
| 458 * Inserts a chain of nodes into a sorted linked list, avoiding duplicates. | |
| 459 * The chain must not be part of any list yet. | |
| 460 * | |
| 461 * If either the list starting with the node pointed to by @p begin or the list | |
| 462 * starting with @p insert_begin is not sorted, the behavior is undefined. | |
| 463 * | |
| 464 * @attention In contrast to cx_linked_list_insert_sorted(), not all nodes of the | |
| 465 * chain might be added. This function returns a new chain consisting of all the duplicates. | |
| 466 * | |
| 467 * @param begin a pointer to the beginning node pointer (required) | |
| 468 * @param end a pointer to the end node pointer (if your list has one) | |
| 469 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) | |
| 470 * @param loc_next the location of a @c next pointer within your node struct (required) | |
| 471 * @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 | |
| 473 * @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) | |
| 475 */ | |
| 476 cx_attr_nonnull_arg(1, 5, 6) cx_attr_nodiscard | |
| 477 CX_EXPORT 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); | |
| 479 | |
| 480 /** | |
| 397 * Removes a chain of nodes from the linked list. | 481 * Removes a chain of nodes from the linked list. |
| 398 * | 482 * |
| 399 * If one of the nodes to remove is the beginning (resp. end) node of the list, and if @p begin (resp. @p end) | 483 * If one of the nodes to remove is the beginning (resp. end) node of the list, and if @p begin (resp. @p end) |
| 400 * addresses are provided, the pointers are adjusted accordingly. | 484 * addresses are provided, the pointers are adjusted accordingly. |
| 401 * | 485 * |
| 452 CX_EXPORT size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next); | 536 CX_EXPORT size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next); |
| 453 | 537 |
| 454 /** | 538 /** |
| 455 * Sorts a linked list based on a comparison function. | 539 * Sorts a linked list based on a comparison function. |
| 456 * | 540 * |
| 457 * This function can work with linked lists of the following structure: | |
| 458 * @code | |
| 459 * typedef struct node node; | |
| 460 * struct node { | |
| 461 * node* prev; | |
| 462 * node* next; | |
| 463 * my_payload data; | |
| 464 * } | |
| 465 * @endcode | |
| 466 * | |
| 467 * @note This is a recursive function with at most logarithmic recursion depth. | 541 * @note This is a recursive function with at most logarithmic recursion depth. |
| 468 * | 542 * |
| 469 * @param begin a pointer to the beginning node pointer (required) | 543 * @param begin a pointer to the beginning node pointer (required) |
| 470 * @param end a pointer to the end node pointer (optional) | 544 * @param end a pointer to the end node pointer (optional) |
| 471 * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present) | 545 * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present) |
| 474 * @param cmp_func the compare function defining the sort order | 548 * @param cmp_func the compare function defining the sort order |
| 475 */ | 549 */ |
| 476 cx_attr_nonnull_arg(1, 6) | 550 cx_attr_nonnull_arg(1, 6) |
| 477 CX_EXPORT void cx_linked_list_sort(void **begin, void **end, | 551 CX_EXPORT void cx_linked_list_sort(void **begin, void **end, |
| 478 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func); | 552 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func); |
| 553 | |
| 554 /** | |
| 555 * Sorts a linked list based on a comparison function. | |
| 556 * | |
| 557 * @note This is a recursive function with at most logarithmic recursion depth. | |
| 558 * | |
| 559 * @param begin a pointer to the beginning node pointer (required) | |
| 560 * @param end a pointer to the end node pointer (optional) | |
| 561 * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present) | |
| 562 * @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 | |
| 564 * @param cmp_func the compare function defining the sort order | |
| 565 * @param context additional context for the compare function | |
| 566 */ | |
| 567 cx_attr_nonnull_arg(1, 6) | |
| 568 CX_EXPORT 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); | |
| 479 | 570 |
| 480 | 571 |
| 481 /** | 572 /** |
| 482 * Compares two lists element wise. | 573 * Compares two lists element wise. |
| 483 * | 574 * |
| 494 cx_attr_nonnull_arg(5) | 585 cx_attr_nonnull_arg(5) |
| 495 CX_EXPORT int cx_linked_list_compare(const void *begin_left, const void *begin_right, | 586 CX_EXPORT int cx_linked_list_compare(const void *begin_left, const void *begin_right, |
| 496 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func); | 587 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func); |
| 497 | 588 |
| 498 /** | 589 /** |
| 590 * Compares two lists element wise. | |
| 591 * | |
| 592 * @attention Both lists must have the same structure. | |
| 593 * | |
| 594 * @param begin_left the beginning of the left list (@c NULL denotes an empty list) | |
| 595 * @param begin_right the beginning of the right list (@c NULL denotes an empty list) | |
| 596 * @param loc_advance the location of the pointer to advance | |
| 597 * @param loc_data the location of the @c data pointer within your node struct | |
| 598 * @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 | |
| 600 * right list, positive if the left list is larger than the right list, zero if both lists are equal. | |
| 601 */ | |
| 602 cx_attr_nonnull_arg(5) | |
| 603 CX_EXPORT 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); | |
| 605 | |
| 606 /** | |
| 499 * Reverses the order of the nodes in a linked list. | 607 * Reverses the order of the nodes in a linked list. |
| 500 * | 608 * |
| 501 * @param begin a pointer to the beginning node pointer (required) | 609 * @param begin a pointer to the beginning node pointer (required) |
| 502 * @param end a pointer to the end node pointer (optional) | 610 * @param end a pointer to the end node pointer (optional) |
| 503 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) | 611 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) |
