Mercurial > hg > toolkit / file comparison

comparison: ucx/cx/linked_list.h

ucx/cx/linked_list.h

changeset 1016
ccde46662db7
parent 943
9b5948aa5b90
equal deleted inserted replaced
1015:b459361d98ad 1016:ccde46662db7
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
452 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);
453 451
454 /** 452 /**
455 * Sorts a linked list based on a comparison function. 453 * Sorts a linked list based on a comparison function.
456 * 454 *
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. 455 * @note This is a recursive function with at most logarithmic recursion depth.
468 * 456 *
469 * @param begin a pointer to the beginning node pointer (required) 457 * @param begin a pointer to the beginning node pointer (required)
470 * @param end a pointer to the end node pointer (optional) 458 * @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) 459 * @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 462 * @param cmp_func the compare function defining the sort order
475 */ 463 */
476 cx_attr_nonnull_arg(1, 6) 464 cx_attr_nonnull_arg(1, 6)
477 CX_EXPORT void cx_linked_list_sort(void **begin, void **end, 465 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); 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);
479 484
480 485
481 /** 486 /**
482 * Compares two lists element wise. 487 * Compares two lists element wise.
483 * 488 *
494 cx_attr_nonnull_arg(5) 499 cx_attr_nonnull_arg(5)
495 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,
496 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);
497 502
498 /** 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 /**
499 * Reverses the order of the nodes in a linked list. 521 * Reverses the order of the nodes in a linked list.
500 * 522 *
501 * @param begin a pointer to the beginning node pointer (required) 523 * @param begin a pointer to the beginning node pointer (required)
502 * @param end a pointer to the end node pointer (optional) 524 * @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) 525 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)

Mercurial Repository: toolkit

mercurial