comparison: src/cx/linked_list.h
src/cx/linked_list.h
- changeset 1618
- ef7cab6eb131
- parent 1605
- 55b13f583356
equal
deleted
inserted
replaced
| 1617:d4385f35f8b0 | 1618:ef7cab6eb131 |
|---|---|
| 140 * Finds the node containing an element within a linked list. | 140 * Finds the node containing an element within a linked list. |
| 141 * | 141 * |
| 142 * @param start a pointer to the start node | 142 * @param start a pointer to the start node |
| 143 * @param loc_advance the location of the pointer to advance | 143 * @param loc_advance the location of the pointer to advance |
| 144 * @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 |
| 145 * @param cmp_func a compare function to compare @p elem against the node data | |
| 146 * @param elem a pointer to the element to find | 145 * @param elem a pointer to the element to find |
| 147 * @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 |
| 148 * (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 | |
| 149 * @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 |
| 150 */ | 150 */ |
| 151 cx_attr_nonnull_arg(1, 4, 5) | 151 cx_attr_nonnull_arg(1, 4, 6) |
| 152 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, |
| 153 ptrdiff_t loc_data, cx_compare_func cmp_func, const void *elem, | 153 ptrdiff_t loc_data, const void *elem, size_t *found_index, |
| 154 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); | |
| 155 | 173 |
| 156 /** | 174 /** |
| 157 * Finds the first node in a linked list. | 175 * Finds the first node in a linked list. |
| 158 * | 176 * |
| 159 * 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 |
| 432 CX_EXPORT size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next); | 450 CX_EXPORT size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next); |
| 433 | 451 |
| 434 /** | 452 /** |
| 435 * Sorts a linked list based on a comparison function. | 453 * Sorts a linked list based on a comparison function. |
| 436 * | 454 * |
| 437 * This function can work with linked lists of the following structure: | |
| 438 * @code | |
| 439 * typedef struct node node; | |
| 440 * struct node { | |
| 441 * node* prev; | |
| 442 * node* next; | |
| 443 * my_payload data; | |
| 444 * } | |
| 445 * @endcode | |
| 446 * | |
| 447 * @note This is a recursive function with at most logarithmic recursion depth. | 455 * @note This is a recursive function with at most logarithmic recursion depth. |
| 448 * | 456 * |
| 449 * @param begin a pointer to the beginning node pointer (required) | 457 * @param begin a pointer to the beginning node pointer (required) |
| 450 * @param end a pointer to the end node pointer (optional) | 458 * @param end a pointer to the end node pointer (optional) |
| 451 * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present) | 459 * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present) |
| 454 * @param cmp_func the compare function defining the sort order | 462 * @param cmp_func the compare function defining the sort order |
| 455 */ | 463 */ |
| 456 cx_attr_nonnull_arg(1, 6) | 464 cx_attr_nonnull_arg(1, 6) |
| 457 CX_EXPORT void cx_linked_list_sort(void **begin, void **end, | 465 CX_EXPORT void cx_linked_list_sort(void **begin, void **end, |
| 458 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func); | 466 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func); |
| 467 | |
| 468 /** | |
| 469 * Sorts a linked list based on a comparison function. | |
| 470 * | |
| 471 * @note This is a recursive function with at most logarithmic recursion depth. | |
| 472 * | |
| 473 * @param begin a pointer to the beginning node pointer (required) | |
| 474 * @param end a pointer to the end node pointer (optional) | |
| 475 * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present) | |
| 476 * @param loc_next the location of a @c next pointer within your node struct (required) | |
| 477 * @param loc_data the location of the @c data pointer within your node struct | |
| 478 * @param cmp_func the compare function defining the sort order | |
| 479 * @param context additional context for the compare function | |
| 480 */ | |
| 481 cx_attr_nonnull_arg(1, 6) | |
| 482 CX_EXPORT void cx_linked_list_sort_c(void **begin, void **end, | |
| 483 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func2 cmp_func, void *context); | |
| 459 | 484 |
| 460 | 485 |
| 461 /** | 486 /** |
| 462 * Compares two lists element wise. | 487 * Compares two lists element wise. |
| 463 * | 488 * |
| 474 cx_attr_nonnull_arg(5) | 499 cx_attr_nonnull_arg(5) |
| 475 CX_EXPORT int cx_linked_list_compare(const void *begin_left, const void *begin_right, | 500 CX_EXPORT int cx_linked_list_compare(const void *begin_left, const void *begin_right, |
| 476 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func); | 501 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func); |
| 477 | 502 |
| 478 /** | 503 /** |
| 504 * Compares two lists element wise. | |
| 505 * | |
| 506 * @attention Both lists must have the same structure. | |
| 507 * | |
| 508 * @param begin_left the beginning of the left list (@c NULL denotes an empty list) | |
| 509 * @param begin_right the beginning of the right list (@c NULL denotes an empty list) | |
| 510 * @param loc_advance the location of the pointer to advance | |
| 511 * @param loc_data the location of the @c data pointer within your node struct | |
| 512 * @param cmp_func the function to compare the elements | |
| 513 * @return the first non-zero result of invoking @p cmp_func or: negative if the left list is smaller than the | |
| 514 * right list, positive if the left list is larger than the right list, zero if both lists are equal. | |
| 515 */ | |
| 516 cx_attr_nonnull_arg(5) | |
| 517 CX_EXPORT int cx_linked_list_compare_c(const void *begin_left, const void *begin_right, | |
| 518 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func2 cmp_func, void *context); | |
| 519 | |
| 520 /** | |
| 479 * Reverses the order of the nodes in a linked list. | 521 * Reverses the order of the nodes in a linked list. |
| 480 * | 522 * |
| 481 * @param begin a pointer to the beginning node pointer (required) | 523 * @param begin a pointer to the beginning node pointer (required) |
| 482 * @param end a pointer to the end node pointer (optional) | 524 * @param end a pointer to the end node pointer (optional) |
| 483 * @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_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) |
