comparison: src/cx/array_list.h
src/cx/array_list.h
- changeset 985
- 68754c7de906
- parent 953
- 581ad4fd01e9
equal
deleted
inserted
replaced
| 984:e8f354a25ac8 | 985:68754c7de906 |
|---|---|
| 26 * POSSIBILITY OF SUCH DAMAGE. | 26 * POSSIBILITY OF SUCH DAMAGE. |
| 27 */ | 27 */ |
| 28 /** | 28 /** |
| 29 * \file array_list.h | 29 * \file array_list.h |
| 30 * \brief Array list implementation. | 30 * \brief Array list implementation. |
| 31 * \details Also provides several low-level functions for custom array list implementations. | |
| 32 * \author Mike Becker | 31 * \author Mike Becker |
| 33 * \author Olaf Wintermann | 32 * \author Olaf Wintermann |
| 34 * \copyright 2-Clause BSD License | 33 * \copyright 2-Clause BSD License |
| 35 */ | 34 */ |
| 36 | 35 |
| 43 #ifdef __cplusplus | 42 #ifdef __cplusplus |
| 44 extern "C" { | 43 extern "C" { |
| 45 #endif | 44 #endif |
| 46 | 45 |
| 47 /** | 46 /** |
| 48 * The maximum item size in an array list that fits into stack buffer when swapped. | 47 * The maximum item size in an array list that fits into stack buffer |
| 48 * when swapped. | |
| 49 */ | 49 */ |
| 50 extern const unsigned cx_array_swap_sbo_size; | 50 extern const unsigned cx_array_swap_sbo_size; |
| 51 | 51 |
| 52 /** | 52 /** |
| 53 * Declares variables for an array that can be used with the convenience macros. | 53 * Declares variables for an array that can be used with the convenience macros. |
| 92 * @param capacity the new capacity (number of elements) | 92 * @param capacity the new capacity (number of elements) |
| 93 * @param elem_size the size of each element | 93 * @param elem_size the size of each element |
| 94 * @param alloc a reference to this allocator | 94 * @param alloc a reference to this allocator |
| 95 * @return a pointer to the reallocated memory or \c NULL on failure | 95 * @return a pointer to the reallocated memory or \c NULL on failure |
| 96 */ | 96 */ |
| 97 cx_attr_nodiscard | |
| 98 cx_attr_nonnull_arg(4) | |
| 99 cx_attr_allocsize(2, 3) | |
| 97 void *(*realloc)( | 100 void *(*realloc)( |
| 98 void *array, | 101 void *array, |
| 99 size_t capacity, | 102 size_t capacity, |
| 100 size_t elem_size, | 103 size_t elem_size, |
| 101 struct cx_array_reallocator_s *alloc | 104 struct cx_array_reallocator_s *alloc |
| 182 * @param elem_count the number of elements to copy | 185 * @param elem_count the number of elements to copy |
| 183 * @param reallocator the array reallocator to use, or \c NULL | 186 * @param reallocator the array reallocator to use, or \c NULL |
| 184 * if reallocation shall not happen | 187 * if reallocation shall not happen |
| 185 * @return zero on success, non-zero error code on failure | 188 * @return zero on success, non-zero error code on failure |
| 186 */ | 189 */ |
| 187 __attribute__((__nonnull__(1, 2, 5))) | 190 cx_attr_nonnull_arg(1, 2, 5) |
| 188 enum cx_array_result cx_array_copy( | 191 enum cx_array_result cx_array_copy( |
| 189 void **target, | 192 void **target, |
| 190 size_t *size, | 193 size_t *size, |
| 191 size_t *capacity, | 194 size_t *capacity, |
| 192 size_t index, | 195 size_t index, |
| 260 * @param elem_size the size of one element | 263 * @param elem_size the size of one element |
| 261 * @param elem_count the number of elements to insert | 264 * @param elem_count the number of elements to insert |
| 262 * @param reallocator the array reallocator to use | 265 * @param reallocator the array reallocator to use |
| 263 * @return zero on success, non-zero error code on failure | 266 * @return zero on success, non-zero error code on failure |
| 264 */ | 267 */ |
| 265 __attribute__((__nonnull__)) | 268 cx_attr_nonnull |
| 266 enum cx_array_result cx_array_insert_sorted( | 269 enum cx_array_result cx_array_insert_sorted( |
| 267 void **target, | 270 void **target, |
| 268 size_t *size, | 271 size_t *size, |
| 269 size_t *capacity, | 272 size_t *capacity, |
| 270 cx_compare_func cmp_func, | 273 cx_compare_func cmp_func, |
| 340 * @param elem_size the size of one element | 343 * @param elem_size the size of one element |
| 341 * @param elem the element to find | 344 * @param elem the element to find |
| 342 * @param cmp_func the compare function | 345 * @param cmp_func the compare function |
| 343 * @return the index of the largest lower bound, or \p size | 346 * @return the index of the largest lower bound, or \p size |
| 344 */ | 347 */ |
| 345 __attribute__((__nonnull__)) | 348 cx_attr_nonnull |
| 346 size_t cx_array_binary_search_inf( | 349 size_t cx_array_binary_search_inf( |
| 347 const void *arr, | 350 const void *arr, |
| 348 size_t size, | 351 size_t size, |
| 349 size_t elem_size, | 352 size_t elem_size, |
| 350 const void *elem, | 353 const void *elem, |
| 363 * @param elem the element to find | 366 * @param elem the element to find |
| 364 * @param cmp_func the compare function | 367 * @param cmp_func the compare function |
| 365 * @return the index of the element in the array, or \p size if the element | 368 * @return the index of the element in the array, or \p size if the element |
| 366 * cannot be found | 369 * cannot be found |
| 367 */ | 370 */ |
| 368 __attribute__((__nonnull__)) | 371 cx_attr_nonnull |
| 369 static inline size_t cx_array_binary_search( | 372 size_t cx_array_binary_search( |
| 370 const void *arr, | 373 const void *arr, |
| 371 size_t size, | 374 size_t size, |
| 372 size_t elem_size, | 375 size_t elem_size, |
| 373 const void *elem, | 376 const void *elem, |
| 374 cx_compare_func cmp_func | 377 cx_compare_func cmp_func |
| 375 ) { | 378 ); |
| 376 size_t index = cx_array_binary_search_inf( | |
| 377 arr, size, elem_size, elem, cmp_func | |
| 378 ); | |
| 379 if (index < size && cmp_func(((const char *) arr) + index * elem_size, elem) == 0) { | |
| 380 return index; | |
| 381 } else { | |
| 382 return size; | |
| 383 } | |
| 384 } | |
| 385 | 379 |
| 386 /** | 380 /** |
| 387 * Searches the smallest upper bound in a sorted array. | 381 * Searches the smallest upper bound in a sorted array. |
| 388 * | 382 * |
| 389 * In other words, this function returns the index of the smallest element | 383 * In other words, this function returns the index of the smallest element |
| 401 * @param elem_size the size of one element | 395 * @param elem_size the size of one element |
| 402 * @param elem the element to find | 396 * @param elem the element to find |
| 403 * @param cmp_func the compare function | 397 * @param cmp_func the compare function |
| 404 * @return the index of the smallest upper bound, or \p size | 398 * @return the index of the smallest upper bound, or \p size |
| 405 */ | 399 */ |
| 406 __attribute__((__nonnull__)) | 400 cx_attr_nonnull |
| 407 static inline size_t cx_array_binary_search_sup( | 401 size_t cx_array_binary_search_sup( |
| 408 const void *arr, | 402 const void *arr, |
| 409 size_t size, | 403 size_t size, |
| 410 size_t elem_size, | 404 size_t elem_size, |
| 411 const void *elem, | 405 const void *elem, |
| 412 cx_compare_func cmp_func | 406 cx_compare_func cmp_func |
| 413 ) { | 407 ); |
| 414 size_t inf = cx_array_binary_search_inf(arr, size, elem_size, elem, cmp_func); | |
| 415 if (inf == size) { | |
| 416 // no infimum means, first element is supremum | |
| 417 return 0; | |
| 418 } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) { | |
| 419 return inf; | |
| 420 } else { | |
| 421 return inf + 1; | |
| 422 } | |
| 423 } | |
| 424 | 408 |
| 425 /** | 409 /** |
| 426 * Swaps two array elements. | 410 * Swaps two array elements. |
| 427 * | 411 * |
| 428 * @param arr the array | 412 * @param arr the array |
| 429 * @param elem_size the element size | 413 * @param elem_size the element size |
| 430 * @param idx1 index of first element | 414 * @param idx1 index of first element |
| 431 * @param idx2 index of second element | 415 * @param idx2 index of second element |
| 432 */ | 416 */ |
| 433 __attribute__((__nonnull__)) | 417 cx_attr_nonnull |
| 434 void cx_array_swap( | 418 void cx_array_swap( |
| 435 void *arr, | 419 void *arr, |
| 436 size_t elem_size, | 420 size_t elem_size, |
| 437 size_t idx1, | 421 size_t idx1, |
| 438 size_t idx2 | 422 size_t idx2 |
| 452 * functions will not work) | 436 * functions will not work) |
| 453 * @param elem_size the size of each element in bytes | 437 * @param elem_size the size of each element in bytes |
| 454 * @param initial_capacity the initial number of elements the array can store | 438 * @param initial_capacity the initial number of elements the array can store |
| 455 * @return the created list | 439 * @return the created list |
| 456 */ | 440 */ |
| 441 cx_attr_nodiscard | |
| 442 cx_attr_malloc | |
| 443 cx_attr_dealloc(cxListDestroy, 1) | |
| 457 CxList *cxArrayListCreate( | 444 CxList *cxArrayListCreate( |
| 458 const CxAllocator *allocator, | 445 const CxAllocator *allocator, |
| 459 cx_compare_func comparator, | 446 cx_compare_func comparator, |
| 460 size_t elem_size, | 447 size_t elem_size, |
| 461 size_t initial_capacity | 448 size_t initial_capacity |
