comparison: ucx/cx/linked_list.h
ucx/cx/linked_list.h
- changeset 102
- 64ded9f6a6c6
- parent 101
- 7b3a3130be44
equal
deleted
inserted
replaced
| 101:7b3a3130be44 | 102:64ded9f6a6c6 |
|---|---|
| 42 #ifdef __cplusplus | 42 #ifdef __cplusplus |
| 43 extern "C" { | 43 extern "C" { |
| 44 #endif | 44 #endif |
| 45 | 45 |
| 46 /** | 46 /** |
| 47 * The maximum item size that uses SBO swap instead of relinking. | |
| 48 * | |
| 49 */ | |
| 50 extern const unsigned cx_linked_list_swap_sbo_size; | |
| 51 | |
| 52 /** | |
| 53 * Allocates a linked list for storing elements with @p elem_size bytes each. | 47 * Allocates a linked list for storing elements with @p elem_size bytes each. |
| 54 * | 48 * |
| 55 * If @p elem_size is CX_STORE_POINTERS, the created list will be created as if | 49 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of |
| 56 * cxListStorePointers() was called immediately after creation and the compare | 50 * copies of the added elements and the compare function will be automatically set |
| 57 * function will be automatically set to cx_cmp_ptr(), if none is given. | 51 * to cx_cmp_ptr(), if none is given. |
| 58 * | 52 * |
| 59 * @param allocator the allocator for allocating the list nodes | 53 * @param allocator the allocator for allocating the list nodes |
| 60 * (if @c NULL, a default stdlib allocator will be used) | 54 * (if @c NULL, a default stdlib allocator will be used) |
| 61 * @param comparator the comparator for the elements | 55 * @param comparator the comparator for the elements |
| 62 * (if @c NULL, and the list is not storing pointers, sort and find | 56 * (if @c NULL, and the list is not storing pointers, sort and find |
| 65 * @return the created list | 59 * @return the created list |
| 66 */ | 60 */ |
| 67 cx_attr_nodiscard | 61 cx_attr_nodiscard |
| 68 cx_attr_malloc | 62 cx_attr_malloc |
| 69 cx_attr_dealloc(cxListFree, 1) | 63 cx_attr_dealloc(cxListFree, 1) |
| 64 cx_attr_export | |
| 70 CxList *cxLinkedListCreate( | 65 CxList *cxLinkedListCreate( |
| 71 const CxAllocator *allocator, | 66 const CxAllocator *allocator, |
| 72 cx_compare_func comparator, | 67 cx_compare_func comparator, |
| 73 size_t elem_size | 68 size_t elem_size |
| 74 ); | 69 ); |
| 78 * | 73 * |
| 79 * The list will use cxDefaultAllocator and no comparator function. If you want | 74 * The list will use cxDefaultAllocator and no comparator function. If you want |
| 80 * to call functions that need a comparator, you must either set one immediately | 75 * to call functions that need a comparator, you must either set one immediately |
| 81 * after list creation or use cxLinkedListCreate(). | 76 * after list creation or use cxLinkedListCreate(). |
| 82 * | 77 * |
| 83 * If @p elem_size is CX_STORE_POINTERS, the created list will be created as if | 78 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of |
| 84 * cxListStorePointers() was called immediately after creation and the compare | 79 * copies of the added elements and the compare function will be automatically set |
| 85 * function will be automatically set to cx_cmp_ptr(). | 80 * to cx_cmp_ptr(), if none is given. |
| 86 * | 81 * |
| 87 * @param elem_size (@c size_t) the size of each element in bytes | 82 * @param elem_size (@c size_t) the size of each element in bytes |
| 88 * @return (@c CxList*) the created list | 83 * @return (@c CxList*) the created list |
| 89 */ | 84 */ |
| 90 #define cxLinkedListCreateSimple(elem_size) \ | 85 #define cxLinkedListCreateSimple(elem_size) \ |
| 107 * @param index the search index | 102 * @param index the search index |
| 108 * @return the node found at the specified index | 103 * @return the node found at the specified index |
| 109 */ | 104 */ |
| 110 cx_attr_nonnull | 105 cx_attr_nonnull |
| 111 cx_attr_nodiscard | 106 cx_attr_nodiscard |
| 107 cx_attr_export | |
| 112 void *cx_linked_list_at( | 108 void *cx_linked_list_at( |
| 113 const void *start, | 109 const void *start, |
| 114 size_t start_index, | 110 size_t start_index, |
| 115 ptrdiff_t loc_advance, | 111 ptrdiff_t loc_advance, |
| 116 size_t index | 112 size_t index |
| 117 ); | 113 ); |
| 118 | 114 |
| 119 /** | 115 /** |
| 120 * Finds the index of an element within a linked list. | 116 * Finds the node containing an element within a linked list. |
| 121 * | 117 * |
| 122 * @param start a pointer to the start node | 118 * @param start a pointer to the start node |
| 123 * @param loc_advance the location of the pointer to advance | 119 * @param loc_advance the location of the pointer to advance |
| 124 * @param loc_data the location of the @c data pointer within your node struct | 120 * @param loc_data the location of the @c data pointer within your node struct |
| 125 * @param cmp_func a compare function to compare @p elem against the node data | 121 * @param cmp_func a compare function to compare @p elem against the node data |
| 126 * @param elem a pointer to the element to find | 122 * @param elem a pointer to the element to find |
| 127 * @return the index of the element or a negative value if it could not be found | 123 * @param found_index an optional pointer where the index of the found node |
| 128 */ | 124 * (given that @p start has index 0) is stored |
| 129 cx_attr_nonnull | 125 * @return the index of the element, if found - unspecified if not found |
| 130 ssize_t cx_linked_list_find( | 126 */ |
| 127 cx_attr_nonnull_arg(1, 4, 5) | |
| 128 cx_attr_export | |
| 129 void *cx_linked_list_find( | |
| 131 const void *start, | 130 const void *start, |
| 132 ptrdiff_t loc_advance, | 131 ptrdiff_t loc_advance, |
| 133 ptrdiff_t loc_data, | 132 ptrdiff_t loc_data, |
| 134 cx_compare_func cmp_func, | 133 cx_compare_func cmp_func, |
| 135 const void *elem | 134 const void *elem, |
| 136 ); | 135 size_t *found_index |
| 137 | |
| 138 /** | |
| 139 * Finds the node containing an element within a linked list. | |
| 140 * | |
| 141 * @param result a pointer to the memory where the node pointer (or @c NULL if the element | |
| 142 * could not be found) shall be stored to | |
| 143 * @param start a pointer to the start node | |
| 144 * @param loc_advance the location of the pointer to advance | |
| 145 * @param loc_data the location of the @c data pointer within your node struct | |
| 146 * @param cmp_func a compare function to compare @p elem against the node data | |
| 147 * @param elem a pointer to the element to find | |
| 148 * @return the index of the element or a negative value if it could not be found | |
| 149 */ | |
| 150 cx_attr_nonnull | |
| 151 ssize_t cx_linked_list_find_node( | |
| 152 void **result, | |
| 153 const void *start, | |
| 154 ptrdiff_t loc_advance, | |
| 155 ptrdiff_t loc_data, | |
| 156 cx_compare_func cmp_func, | |
| 157 const void *elem | |
| 158 ); | 136 ); |
| 159 | 137 |
| 160 /** | 138 /** |
| 161 * Finds the first node in a linked list. | 139 * Finds the first node in a linked list. |
| 162 * | 140 * |
| 168 * @param loc_prev the location of the @c prev pointer | 146 * @param loc_prev the location of the @c prev pointer |
| 169 * @return a pointer to the first node | 147 * @return a pointer to the first node |
| 170 */ | 148 */ |
| 171 cx_attr_nonnull | 149 cx_attr_nonnull |
| 172 cx_attr_returns_nonnull | 150 cx_attr_returns_nonnull |
| 151 cx_attr_export | |
| 173 void *cx_linked_list_first( | 152 void *cx_linked_list_first( |
| 174 const void *node, | 153 const void *node, |
| 175 ptrdiff_t loc_prev | 154 ptrdiff_t loc_prev |
| 176 ); | 155 ); |
| 177 | 156 |
| 186 * @param loc_next the location of the @c next pointer | 165 * @param loc_next the location of the @c next pointer |
| 187 * @return a pointer to the last node | 166 * @return a pointer to the last node |
| 188 */ | 167 */ |
| 189 cx_attr_nonnull | 168 cx_attr_nonnull |
| 190 cx_attr_returns_nonnull | 169 cx_attr_returns_nonnull |
| 170 cx_attr_export | |
| 191 void *cx_linked_list_last( | 171 void *cx_linked_list_last( |
| 192 const void *node, | 172 const void *node, |
| 193 ptrdiff_t loc_next | 173 ptrdiff_t loc_next |
| 194 ); | 174 ); |
| 195 | 175 |
| 202 * @param loc_next the location of the @c next pointer | 182 * @param loc_next the location of the @c next pointer |
| 203 * @param node the successor of the node to find | 183 * @param node the successor of the node to find |
| 204 * @return the node or @c NULL if @p node has no predecessor | 184 * @return the node or @c NULL if @p node has no predecessor |
| 205 */ | 185 */ |
| 206 cx_attr_nonnull | 186 cx_attr_nonnull |
| 187 cx_attr_export | |
| 207 void *cx_linked_list_prev( | 188 void *cx_linked_list_prev( |
| 208 const void *begin, | 189 const void *begin, |
| 209 ptrdiff_t loc_next, | 190 ptrdiff_t loc_next, |
| 210 const void *node | 191 const void *node |
| 211 ); | 192 ); |
| 221 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) | 202 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) |
| 222 * @param loc_next the location of a @c next pointer within your node struct (required) | 203 * @param loc_next the location of a @c next pointer within your node struct (required) |
| 223 * @param new_node a pointer to the node that shall be appended | 204 * @param new_node a pointer to the node that shall be appended |
| 224 */ | 205 */ |
| 225 cx_attr_nonnull_arg(5) | 206 cx_attr_nonnull_arg(5) |
| 207 cx_attr_export | |
| 226 void cx_linked_list_add( | 208 void cx_linked_list_add( |
| 227 void **begin, | 209 void **begin, |
| 228 void **end, | 210 void **end, |
| 229 ptrdiff_t loc_prev, | 211 ptrdiff_t loc_prev, |
| 230 ptrdiff_t loc_next, | 212 ptrdiff_t loc_next, |
| 242 * @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_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) |
| 243 * @param loc_next the location of a @c next pointer within your node struct (required) | 225 * @param loc_next the location of a @c next pointer within your node struct (required) |
| 244 * @param new_node a pointer to the node that shall be prepended | 226 * @param new_node a pointer to the node that shall be prepended |
| 245 */ | 227 */ |
| 246 cx_attr_nonnull_arg(5) | 228 cx_attr_nonnull_arg(5) |
| 229 cx_attr_export | |
| 247 void cx_linked_list_prepend( | 230 void cx_linked_list_prepend( |
| 248 void **begin, | 231 void **begin, |
| 249 void **end, | 232 void **end, |
| 250 ptrdiff_t loc_prev, | 233 ptrdiff_t loc_prev, |
| 251 ptrdiff_t loc_next, | 234 ptrdiff_t loc_next, |
| 259 * @param right the new successor of @p left | 242 * @param right the new successor of @p left |
| 260 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) | 243 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) |
| 261 * @param loc_next the location of a @c next pointer within your node struct (required) | 244 * @param loc_next the location of a @c next pointer within your node struct (required) |
| 262 */ | 245 */ |
| 263 cx_attr_nonnull | 246 cx_attr_nonnull |
| 247 cx_attr_export | |
| 264 void cx_linked_list_link( | 248 void cx_linked_list_link( |
| 265 void *left, | 249 void *left, |
| 266 void *right, | 250 void *right, |
| 267 ptrdiff_t loc_prev, | 251 ptrdiff_t loc_prev, |
| 268 ptrdiff_t loc_next | 252 ptrdiff_t loc_next |
| 277 * @param right the successor of @p left | 261 * @param right the successor of @p left |
| 278 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) | 262 * @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) | 263 * @param loc_next the location of a @c next pointer within your node struct (required) |
| 280 */ | 264 */ |
| 281 cx_attr_nonnull | 265 cx_attr_nonnull |
| 266 cx_attr_export | |
| 282 void cx_linked_list_unlink( | 267 void cx_linked_list_unlink( |
| 283 void *left, | 268 void *left, |
| 284 void *right, | 269 void *right, |
| 285 ptrdiff_t loc_prev, | 270 ptrdiff_t loc_prev, |
| 286 ptrdiff_t loc_next | 271 ptrdiff_t loc_next |
| 299 * @param loc_next the location of a @c next pointer within your node struct (required) | 284 * @param loc_next the location of a @c next pointer within your node struct (required) |
| 300 * @param node the node after which to insert (@c NULL if you want to prepend the node to the list) | 285 * @param node the node after which to insert (@c NULL if you want to prepend the node to the list) |
| 301 * @param new_node a pointer to the node that shall be inserted | 286 * @param new_node a pointer to the node that shall be inserted |
| 302 */ | 287 */ |
| 303 cx_attr_nonnull_arg(6) | 288 cx_attr_nonnull_arg(6) |
| 289 cx_attr_export | |
| 304 void cx_linked_list_insert( | 290 void cx_linked_list_insert( |
| 305 void **begin, | 291 void **begin, |
| 306 void **end, | 292 void **end, |
| 307 ptrdiff_t loc_prev, | 293 ptrdiff_t loc_prev, |
| 308 ptrdiff_t loc_next, | 294 ptrdiff_t loc_next, |
| 329 * @param node the node after which to insert (@c NULL to prepend the chain to the list) | 315 * @param node the node after which to insert (@c NULL to prepend the chain to the list) |
| 330 * @param insert_begin a pointer to the first node of the chain that shall be inserted | 316 * @param insert_begin a pointer to the first node of the chain that shall be inserted |
| 331 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) | 317 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) |
| 332 */ | 318 */ |
| 333 cx_attr_nonnull_arg(6) | 319 cx_attr_nonnull_arg(6) |
| 320 cx_attr_export | |
| 334 void cx_linked_list_insert_chain( | 321 void cx_linked_list_insert_chain( |
| 335 void **begin, | 322 void **begin, |
| 336 void **end, | 323 void **end, |
| 337 ptrdiff_t loc_prev, | 324 ptrdiff_t loc_prev, |
| 338 ptrdiff_t loc_next, | 325 ptrdiff_t loc_next, |
| 354 * @param loc_next the location of a @c next pointer within your node struct (required) | 341 * @param loc_next the location of a @c next pointer within your node struct (required) |
| 355 * @param new_node a pointer to the node that shall be inserted | 342 * @param new_node a pointer to the node that shall be inserted |
| 356 * @param cmp_func a compare function that will receive the node pointers | 343 * @param cmp_func a compare function that will receive the node pointers |
| 357 */ | 344 */ |
| 358 cx_attr_nonnull_arg(1, 5, 6) | 345 cx_attr_nonnull_arg(1, 5, 6) |
| 346 cx_attr_export | |
| 359 void cx_linked_list_insert_sorted( | 347 void cx_linked_list_insert_sorted( |
| 360 void **begin, | 348 void **begin, |
| 361 void **end, | 349 void **end, |
| 362 ptrdiff_t loc_prev, | 350 ptrdiff_t loc_prev, |
| 363 ptrdiff_t loc_next, | 351 ptrdiff_t loc_next, |
| 383 * @param loc_next the location of a @c next pointer within your node struct (required) | 371 * @param loc_next the location of a @c next pointer within your node struct (required) |
| 384 * @param insert_begin a pointer to the first node of the chain that shall be inserted | 372 * @param insert_begin a pointer to the first node of the chain that shall be inserted |
| 385 * @param cmp_func a compare function that will receive the node pointers | 373 * @param cmp_func a compare function that will receive the node pointers |
| 386 */ | 374 */ |
| 387 cx_attr_nonnull_arg(1, 5, 6) | 375 cx_attr_nonnull_arg(1, 5, 6) |
| 376 cx_attr_export | |
| 388 void cx_linked_list_insert_sorted_chain( | 377 void cx_linked_list_insert_sorted_chain( |
| 389 void **begin, | 378 void **begin, |
| 390 void **end, | 379 void **end, |
| 391 ptrdiff_t loc_prev, | 380 ptrdiff_t loc_prev, |
| 392 ptrdiff_t loc_next, | 381 ptrdiff_t loc_next, |
| 414 * @param node the start node of the chain | 403 * @param node the start node of the chain |
| 415 * @param num the number of nodes to remove | 404 * @param num the number of nodes to remove |
| 416 * @return the actual number of nodes that were removed (can be less when the list did not have enough nodes) | 405 * @return the actual number of nodes that were removed (can be less when the list did not have enough nodes) |
| 417 */ | 406 */ |
| 418 cx_attr_nonnull_arg(5) | 407 cx_attr_nonnull_arg(5) |
| 408 cx_attr_export | |
| 419 size_t cx_linked_list_remove_chain( | 409 size_t cx_linked_list_remove_chain( |
| 420 void **begin, | 410 void **begin, |
| 421 void **end, | 411 void **end, |
| 422 ptrdiff_t loc_prev, | 412 ptrdiff_t loc_prev, |
| 423 ptrdiff_t loc_next, | 413 ptrdiff_t loc_next, |
| 460 * | 450 * |
| 461 * @param node the first node | 451 * @param node the first node |
| 462 * @param loc_next the location of the @c next pointer within the node struct | 452 * @param loc_next the location of the @c next pointer within the node struct |
| 463 * @return the size of the list or zero if @p node is @c NULL | 453 * @return the size of the list or zero if @p node is @c NULL |
| 464 */ | 454 */ |
| 455 cx_attr_nodiscard | |
| 456 cx_attr_export | |
| 465 size_t cx_linked_list_size( | 457 size_t cx_linked_list_size( |
| 466 const void *node, | 458 const void *node, |
| 467 ptrdiff_t loc_next | 459 ptrdiff_t loc_next |
| 468 ); | 460 ); |
| 469 | 461 |
| 488 * @param loc_next the location of a @c next pointer within your node struct (required) | 480 * @param loc_next the location of a @c next pointer within your node struct (required) |
| 489 * @param loc_data the location of the @c data pointer within your node struct | 481 * @param loc_data the location of the @c data pointer within your node struct |
| 490 * @param cmp_func the compare function defining the sort order | 482 * @param cmp_func the compare function defining the sort order |
| 491 */ | 483 */ |
| 492 cx_attr_nonnull_arg(1, 6) | 484 cx_attr_nonnull_arg(1, 6) |
| 485 cx_attr_export | |
| 493 void cx_linked_list_sort( | 486 void cx_linked_list_sort( |
| 494 void **begin, | 487 void **begin, |
| 495 void **end, | 488 void **end, |
| 496 ptrdiff_t loc_prev, | 489 ptrdiff_t loc_prev, |
| 497 ptrdiff_t loc_next, | 490 ptrdiff_t loc_next, |
| 512 * @param cmp_func the function to compare the elements | 505 * @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 | 506 * @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. | 507 * right list, positive if the left list is larger than the right list, zero if both lists are equal. |
| 515 */ | 508 */ |
| 516 cx_attr_nonnull_arg(5) | 509 cx_attr_nonnull_arg(5) |
| 510 cx_attr_export | |
| 517 int cx_linked_list_compare( | 511 int cx_linked_list_compare( |
| 518 const void *begin_left, | 512 const void *begin_left, |
| 519 const void *begin_right, | 513 const void *begin_right, |
| 520 ptrdiff_t loc_advance, | 514 ptrdiff_t loc_advance, |
| 521 ptrdiff_t loc_data, | 515 ptrdiff_t loc_data, |
| 529 * @param end a pointer to the end node pointer (optional) | 523 * @param end a pointer to the end node pointer (optional) |
| 530 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) | 524 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) |
| 531 * @param loc_next the location of a @c next pointer within your node struct (required) | 525 * @param loc_next the location of a @c next pointer within your node struct (required) |
| 532 */ | 526 */ |
| 533 cx_attr_nonnull_arg(1) | 527 cx_attr_nonnull_arg(1) |
| 528 cx_attr_export | |
| 534 void cx_linked_list_reverse( | 529 void cx_linked_list_reverse( |
| 535 void **begin, | 530 void **begin, |
| 536 void **end, | 531 void **end, |
| 537 ptrdiff_t loc_prev, | 532 ptrdiff_t loc_prev, |
| 538 ptrdiff_t loc_next | 533 ptrdiff_t loc_next |
