Mercurial > hg > toolkit / file comparison

comparison: ucx/cx/array_list.h

ucx/cx/array_list.h

changeset 1040
473d8cb58a6c
parent 1034
330b415910bd
equal deleted inserted replaced
1039:6691e007cef7 1040:473d8cb58a6c
37 #ifndef UCX_ARRAY_LIST_H 37 #ifndef UCX_ARRAY_LIST_H
38 #define UCX_ARRAY_LIST_H 38 #define UCX_ARRAY_LIST_H
39 39
40 #include "list.h" 40 #include "list.h"
41 41
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45
46 /** 42 /**
47 * The maximum item size in an array list that fits into 43 * The maximum item size in an array list that fits into
48 * a stack buffer when swapped. 44 * a stack buffer when swapped.
49 */ 45 */
50 CX_EXPORT extern const unsigned cx_array_swap_sbo_size; 46 CX_EXPORT extern const unsigned cx_array_swap_sbo_size;
86 * @param elem_size size of one element 82 * @param elem_size size of one element
87 * @param capacity the initial maximum number of elements 83 * @param capacity the initial maximum number of elements
88 * @retval zero allocation was successful 84 * @retval zero allocation was successful
89 * @retval non-zero allocation failed 85 * @retval non-zero allocation failed
90 */ 86 */
91 cx_attr_nonnull 87 CX_EXTERN CX_NONNULL
92 CX_EXPORT int cx_array_init_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity); 88 int cx_array_init_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity);
93 89
94 /** 90 /**
95 * Initializes an array by allocating memory. 91 * Initializes an array by allocating memory.
96 * 92 *
97 * The size is set to zero. 93 * The size is set to zero.
129 * @param array a pointer to the array structure 125 * @param array a pointer to the array structure
130 * @param data the fixed size array 126 * @param data the fixed size array
131 * @param capacity the capacity of the fixed size array 127 * @param capacity the capacity of the fixed size array
132 * @param size the number of initialized elements in the fixed size array 128 * @param size the number of initialized elements in the fixed size array
133 */ 129 */
134 cx_attr_nonnull 130 CX_EXTERN CX_NONNULL
135 CX_EXPORT void cx_array_init_fixed_(CxArray *array, const void *data, size_t capacity, size_t size); 131 void cx_array_init_fixed_(CxArray *array, const void *data, size_t capacity, size_t size);
136 132
137 /** 133 /**
138 * Initializes an array with fixed size memory. 134 * Initializes an array with fixed size memory.
139 * 135 *
140 * This is useful, for example, when you want to work with memory on the stack 136 * This is useful, for example, when you want to work with memory on the stack
171 * @param elem_size the size of one element 167 * @param elem_size the size of one element
172 * @param capacity the new capacity 168 * @param capacity the new capacity
173 * @retval zero allocation was successful 169 * @retval zero allocation was successful
174 * @retval non-zero allocation failed 170 * @retval non-zero allocation failed
175 */ 171 */
176 cx_attr_nonnull 172 CX_EXTERN CX_NONNULL
177 CX_EXPORT int cx_array_reserve_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity); 173 int cx_array_reserve_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity);
178 174
179 /** 175 /**
180 * Changes the capacity of an array. 176 * Changes the capacity of an array.
181 * 177 *
182 * If required, the size is reduced to fit into the new capacity. 178 * If required, the size is reduced to fit into the new capacity.
213 * @param elem_size the size of one element 209 * @param elem_size the size of one element
214 * @param capacity the new capacity 210 * @param capacity the new capacity
215 * @retval zero allocation was successful 211 * @retval zero allocation was successful
216 * @retval non-zero allocation failed 212 * @retval non-zero allocation failed
217 */ 213 */
218 cx_attr_nonnull 214 CX_EXTERN CX_NONNULL
219 CX_EXPORT int cx_array_copy_to_new_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity); 215 int cx_array_copy_to_new_(const CxAllocator *allocator, CxArray *array, size_t elem_size, size_t capacity);
220 216
221 /** 217 /**
222 * Copies the array to a new memory region. 218 * Copies the array to a new memory region.
223 * 219 *
224 * This is useful when you have initialized the array with a fixed size memory 220 * This is useful when you have initialized the array with a fixed size memory
267 * @param other a pointer to an array of data that shall be inserted 263 * @param other a pointer to an array of data that shall be inserted
268 * @param n the number of elements that shall be inserted 264 * @param n the number of elements that shall be inserted
269 * @retval zero success 265 * @retval zero success
270 * @retval non-zero a re-allocation was necessary but failed 266 * @retval non-zero a re-allocation was necessary but failed
271 */ 267 */
272 cx_attr_nonnull_arg(1, 2) 268 CX_EXTERN CX_NONNULL_ARG(1, 2)
273 CX_EXPORT int cx_array_insert_(const CxAllocator *allocator, CxArray *array, 269 int cx_array_insert_(const CxAllocator *allocator, CxArray *array,
274 size_t elem_size, size_t index, const void *other, size_t n); 270 size_t elem_size, size_t index, const void *other, size_t n);
275 271
276 /** 272 /**
277 * Appends an element to an array. 273 * Appends an element to an array.
278 * 274 *
395 * Internal function - do not use. 391 * Internal function - do not use.
396 * 392 *
397 * @param allocator the allocator to use for a possible reallocation 393 * @param allocator the allocator to use for a possible reallocation
398 * @param array a pointer to the array structure 394 * @param array a pointer to the array structure
399 * @param elem_size the size of one element 395 * @param elem_size the size of one element
400 * @param cmp_func
401 * @param sorted_data a pointer to an array of data that shall be inserted 396 * @param sorted_data a pointer to an array of data that shall be inserted
402 * @param n the number of elements that shall be inserted 397 * @param n the number of elements that shall be inserted
398 * @param cmp_func the compare function
403 * @param allow_duplicates @c false if duplicates shall be skipped during insertion 399 * @param allow_duplicates @c false if duplicates shall be skipped during insertion
404 * @retval zero success 400 * @retval zero success
405 * @retval non-zero a re-allocation was necessary but failed 401 * @retval non-zero a re-allocation was necessary but failed
406 */ 402 */
407 cx_attr_nonnull 403 CX_EXTERN CX_NONNULL
408 CX_EXPORT int cx_array_insert_sorted_(const CxAllocator *allocator, CxArray *array, 404 int cx_array_insert_sorted_(const CxAllocator *allocator, CxArray *array,
409 size_t elem_size, cx_compare_func cmp_func, const void *sorted_data, size_t n, 405 size_t elem_size, const void *sorted_data, size_t n,
410 bool allow_duplicates); 406 cx_compare_func cmp_func, bool allow_duplicates);
411 407
412 /** 408 /**
413 * Inserts an element into a sorted array. 409 * Inserts an element into a sorted array.
414 * 410 *
415 * When the capacity is not enough to hold the new element, a re-allocation is attempted. 411 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
416 * 412 *
417 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined. 413 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
418 * 414 *
419 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation 415 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
420 * @param array the name of the array where the elements shall be inserted 416 * @param array the name of the array where the elements shall be inserted
417 * @param element the element that shall be inserted
421 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order 418 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
422 * @param element (@c void*) a pointer to element that shall be inserted 419 * @retval zero success
423 * @retval zero success 420 * @retval non-zero a re-allocation was necessary but failed
424 * @retval non-zero a re-allocation was necessary but failed 421 */
425 */ 422 #define cx_array_insert_sorted_a(allocator, array, element, cmp_func) \
426 #define cx_array_insert_sorted_a(allocator, array, cmp_func, element) \ 423 cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (void*)&(element), 1, cmp_func, true)
427 cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), cmp_func, element, 1, true)
428 424
429 /** 425 /**
430 * Inserts an element into a sorted array. 426 * Inserts an element into a sorted array.
431 * 427 *
432 * When the capacity is not enough to hold the new element, a re-allocation is attempted. 428 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
433 * 429 *
434 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined. 430 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
435 * 431 *
436 * @param array the name of the array where the elements shall be inserted 432 * @param array the name of the array where the elements shall be inserted
433 * @param element the element that shall be inserted
437 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order 434 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
438 * @param element (@c void*) a pointer to element that shall be inserted 435 * @retval zero success
439 * @retval zero success 436 * @retval non-zero a re-allocation was necessary but failed
440 * @retval non-zero a re-allocation was necessary but failed 437 */
441 */ 438 #define cx_array_insert_sorted(array, element, cmp_func) \
442 #define cx_array_insert_sorted(array, cmp_func, element) \ 439 cx_array_insert_sorted_a(cxDefaultAllocator, array, element, cmp_func)
443 cx_array_insert_sorted_a(cxDefaultAllocator, array, cmp_func, element)
444 440
445 /** 441 /**
446 * Inserts sorted data into a sorted array. 442 * Inserts sorted data into a sorted array.
447 * 443 *
448 * When the capacity is not enough to hold the new elements, a re-allocation is attempted. 444 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
449 * 445 *
450 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined. 446 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
451 * 447 *
452 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation 448 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
453 * @param array the name of the array where the elements shall be inserted 449 * @param array the name of the array where the elements shall be inserted
454 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
455 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted 450 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
456 * @param n (@c size_t) the number of elements that shall be inserted 451 * @param n (@c size_t) the number of elements that shall be inserted
457 * @retval zero success 452 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
458 * @retval non-zero a re-allocation was necessary but failed 453 * @retval zero success
459 */ 454 * @retval non-zero a re-allocation was necessary but failed
460 #define cx_array_insert_sorted_array_a(allocator, array, cmp_func, sorted_data, n) \ 455 */
461 cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), cmp_func, sorted_data, n, true) 456 #define cx_array_insert_sorted_array_a(allocator, array, sorted_data, n, cmp_func) \
457 cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), sorted_data, n, cmp_func, true)
462 458
463 /** 459 /**
464 * Inserts sorted data into a sorted array. 460 * Inserts sorted data into a sorted array.
465 * 461 *
466 * When the capacity is not enough to hold the new elements, a re-allocation is attempted. 462 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
467 * 463 *
468 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined. 464 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
469 * 465 *
470 * @param array the name of the array where the elements shall be inserted 466 * @param array the name of the array where the elements shall be inserted
471 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
472 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted 467 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
473 * @param n (@c size_t) the number of elements that shall be inserted 468 * @param n (@c size_t) the number of elements that shall be inserted
474 * @retval zero success 469 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
475 * @retval non-zero a re-allocation was necessary but failed 470 * @retval zero success
476 */ 471 * @retval non-zero a re-allocation was necessary but failed
477 #define cx_array_insert_sorted_array(array, cmp_func, sorted_data, n) \ 472 */
478 cx_array_insert_sorted_array_a(cxDefaultAllocator, array, cmp_func, sorted_data, n) 473 #define cx_array_insert_sorted_array(array, sorted_data, n, cmp_func) \
474 cx_array_insert_sorted_array_a(cxDefaultAllocator, array, sorted_data, n, cmp_func)
479 475
480 /** 476 /**
481 * Inserts an element into a sorted array if it is not already contained. 477 * Inserts an element into a sorted array if it is not already contained.
482 * 478 *
483 * When the capacity is not enough to hold the new element, a re-allocation is attempted. 479 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
484 * 480 *
485 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined. 481 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
486 * 482 *
487 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation 483 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
488 * @param array the name of the array where the elements shall be inserted 484 * @param array the name of the array where the elements shall be inserted
485 * @param element the element that shall be inserted
489 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order 486 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
490 * @param element (@c void*) a pointer to element that shall be inserted 487 * @retval zero success
491 * @retval zero success 488 * @retval non-zero a re-allocation was necessary but failed
492 * @retval non-zero a re-allocation was necessary but failed 489 */
493 */ 490 #define cx_array_insert_unique_a(allocator, array, element, cmp_func) \
494 #define cx_array_insert_unique_a(allocator, array, cmp_func, element) \ 491 cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (void*)&(element), 1, cmp_func, false)
495 cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), cmp_func, element, 1, false)
496 492
497 /** 493 /**
498 * Inserts an element into a sorted array if it is not already contained. 494 * Inserts an element into a sorted array if it is not already contained.
499 * 495 *
500 * When the capacity is not enough to hold the new element, a re-allocation is attempted. 496 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
501 * 497 *
502 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined. 498 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
503 * 499 *
504 * @param array the name of the array where the elements shall be inserted 500 * @param array the name of the array where the elements shall be inserted
501 * @param element the element that shall be inserted
505 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order 502 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
506 * @param element (@c void*) a pointer to element that shall be inserted 503 * @retval zero success
507 * @retval zero success 504 * @retval non-zero a re-allocation was necessary but failed
508 * @retval non-zero a re-allocation was necessary but failed 505 */
509 */ 506 #define cx_array_insert_unique(array, element, cmp_func) \
510 #define cx_array_insert_unique(array, cmp_func, element) \ 507 cx_array_insert_unique_a(cxDefaultAllocator, array, element, cmp_func)
511 cx_array_insert_unique_a(cxDefaultAllocator, array, cmp_func, element)
512 508
513 /** 509 /**
514 * Inserts sorted data into a sorted array, skipping duplicates. 510 * Inserts sorted data into a sorted array, skipping duplicates.
515 * 511 *
516 * When the capacity is not enough to hold the new elements, a re-allocation is attempted. 512 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
517 * 513 *
518 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined. 514 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
519 * 515 *
520 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation 516 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
521 * @param array the name of the array where the elements shall be inserted 517 * @param array the name of the array where the elements shall be inserted
522 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
523 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted 518 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
524 * @param n (@c size_t) the number of elements that shall be inserted 519 * @param n (@c size_t) the number of elements that shall be inserted
525 * @retval zero success 520 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
526 * @retval non-zero a re-allocation was necessary but failed 521 * @retval zero success
527 */ 522 * @retval non-zero a re-allocation was necessary but failed
528 #define cx_array_insert_unique_array_a(allocator, array, cmp_func, sorted_data, n) \ 523 */
529 cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), cmp_func, sorted_data, n, false) 524 #define cx_array_insert_unique_array_a(allocator, array, sorted_data, n, cmp_func) \
525 cx_array_insert_sorted_(allocator, (CxArray*)&(array), sizeof((array).data[0]), sorted_data, n, cmp_func, false)
530 526
531 /** 527 /**
532 * Inserts sorted data into a sorted array, skipping duplicates. 528 * Inserts sorted data into a sorted array, skipping duplicates.
533 * 529 *
534 * When the capacity is not enough to hold the new elements, a re-allocation is attempted. 530 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
535 * 531 *
536 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined. 532 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
537 * 533 *
538 * @param array the name of the array where the elements shall be inserted 534 * @param array the name of the array where the elements shall be inserted
539 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
540 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted 535 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
541 * @param n (@c size_t) the number of elements that shall be inserted 536 * @param n (@c size_t) the number of elements that shall be inserted
542 * @retval zero success 537 * @param cmp_func (@c cx_compare_func) the compare function that establishes the order
543 * @retval non-zero a re-allocation was necessary but failed 538 * @retval zero success
544 */ 539 * @retval non-zero a re-allocation was necessary but failed
545 #define cx_array_insert_unique_array(array, cmp_func, sorted_data, n) \ 540 */
546 cx_array_insert_unique_array_a(cxDefaultAllocator, array, cmp_func, sorted_data, n) 541 #define cx_array_insert_unique_array(array, sorted_data, n, cmp_func) \
542 cx_array_insert_unique_array_a(cxDefaultAllocator, array, sorted_data, n, cmp_func)
543
544 /**
545 * Inserts sorted data into a sorted array.
546 *
547 * Internal function - do not use.
548 *
549 * @param allocator the allocator to use for a possible reallocation
550 * @param array a pointer to the array structure
551 * @param elem_size the size of one element
552 * @param sorted_data a pointer to an array of data that shall be inserted
553 * @param n the number of elements that shall be inserted
554 * @param cmp_func the compare function
555 * @param context additional context for the compare function
556 * @param allow_duplicates @c false if duplicates shall be skipped during insertion
557 * @retval zero success
558 * @retval non-zero a re-allocation was necessary but failed
559 */
560 CX_EXTERN CX_NONNULL_ARG(1, 2, 4, 6)
561 int cx_array_insert_sorted_c_(const CxAllocator *allocator, CxArray *array,
562 size_t elem_size, const void *sorted_data, size_t n,
563 cx_compare_func2 cmp_func, void *context, bool allow_duplicates);
564
565 /**
566 * Inserts an element into a sorted array.
567 *
568 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
569 *
570 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
571 *
572 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
573 * @param array the name of the array where the elements shall be inserted
574 * @param element the element that shall be inserted
575 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
576 * @param context (@c void*) additional context for the compare function
577 * @retval zero success
578 * @retval non-zero a re-allocation was necessary but failed
579 */
580 #define cx_array_insert_sorted_ca(allocator, array, element, cmp_func, context) \
581 cx_array_insert_sorted_c_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (void*)&(element), 1, cmp_func, context, true)
582
583 /**
584 * Inserts an element into a sorted array.
585 *
586 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
587 *
588 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
589 *
590 * @param array the name of the array where the elements shall be inserted
591 * @param element the element that shall be inserted
592 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
593 * @param context (@c void*) additional context for the compare function
594 * @retval zero success
595 * @retval non-zero a re-allocation was necessary but failed
596 */
597 #define cx_array_insert_sorted_c(array, element, cmp_func, context) \
598 cx_array_insert_sorted_ca(cxDefaultAllocator, array, element, cmp_func, context)
599
600 /**
601 * Inserts sorted data into a sorted array.
602 *
603 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
604 *
605 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
606 *
607 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
608 * @param array the name of the array where the elements shall be inserted
609 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
610 * @param n (@c size_t) the number of elements that shall be inserted
611 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
612 * @param context (@c void*) additional context for the compare function
613 * @retval zero success
614 * @retval non-zero a re-allocation was necessary but failed
615 */
616 #define cx_array_insert_sorted_array_ca(allocator, array, sorted_data, n, cmp_func, context) \
617 cx_array_insert_sorted_c_(allocator, (CxArray*)&(array), sizeof((array).data[0]), sorted_data, n, cmp_func, context, true)
618
619 /**
620 * Inserts sorted data into a sorted array.
621 *
622 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
623 *
624 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
625 *
626 * @param array the name of the array where the elements shall be inserted
627 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
628 * @param n (@c size_t) the number of elements that shall be inserted
629 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
630 * @param context (@c void*) additional context for the compare function
631 * @retval zero success
632 * @retval non-zero a re-allocation was necessary but failed
633 */
634 #define cx_array_insert_sorted_array_c(array, sorted_data, n, cmp_func, context) \
635 cx_array_insert_sorted_array_ca(cxDefaultAllocator, array, sorted_data, n, cmp_func, context)
636
637 /**
638 * Inserts an element into a sorted array if it is not already contained.
639 *
640 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
641 *
642 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
643 *
644 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
645 * @param array the name of the array where the elements shall be inserted
646 * @param element the element that shall be inserted
647 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
648 * @param context (@c void*) additional context for the compare function
649 * @retval zero success
650 * @retval non-zero a re-allocation was necessary but failed
651 */
652 #define cx_array_insert_unique_ca(allocator, array, element, cmp_func, context) \
653 cx_array_insert_sorted_c_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (void*)&(element), 1, cmp_func, context, false)
654
655 /**
656 * Inserts an element into a sorted array if it is not already contained.
657 *
658 * When the capacity is not enough to hold the new element, a re-allocation is attempted.
659 *
660 * @attention if the array is not sorted according to the specified @p cmp_func, the behavior is undefined.
661 *
662 * @param array the name of the array where the elements shall be inserted
663 * @param element the element that shall be inserted
664 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
665 * @param context (@c void*) additional context for the compare function
666 * @retval zero success
667 * @retval non-zero a re-allocation was necessary but failed
668 */
669 #define cx_array_insert_unique_c(array, element, cmp_func, context) \
670 cx_array_insert_unique_ca(cxDefaultAllocator, array, element, cmp_func, context)
671
672 /**
673 * Inserts sorted data into a sorted array, skipping duplicates.
674 *
675 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
676 *
677 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
678 *
679 * @param allocator (@c CxAllocator*) the allocator to use for a possible reallocation
680 * @param array the name of the array where the elements shall be inserted
681 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
682 * @param n (@c size_t) the number of elements that shall be inserted
683 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
684 * @param context (@c void*) additional context for the compare function
685 * @retval zero success
686 * @retval non-zero a re-allocation was necessary but failed
687 */
688 #define cx_array_insert_unique_array_ca(allocator, array, sorted_data, n, cmp_func, context) \
689 cx_array_insert_sorted_c_(allocator, (CxArray*)&(array), sizeof((array).data[0]), sorted_data, n, cmp_func, context, false)
690
691 /**
692 * Inserts sorted data into a sorted array, skipping duplicates.
693 *
694 * When the capacity is not enough to hold the new elements, a re-allocation is attempted.
695 *
696 * @attention if either array is not sorted according to the specified @p cmp_func, the behavior is undefined.
697 *
698 * @param array the name of the array where the elements shall be inserted
699 * @param sorted_data (@c void*) a pointer to an array of sorted data that shall be inserted
700 * @param n (@c size_t) the number of elements that shall be inserted
701 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
702 * @param context (@c void*) additional context for the compare function
703 * @retval zero success
704 * @retval non-zero a re-allocation was necessary but failed
705 */
706 #define cx_array_insert_unique_array_c(array, sorted_data, n, cmp_func, context) \
707 cx_array_insert_unique_array_ca(cxDefaultAllocator, array, sorted_data, n, cmp_func, context)
708
709 /**
710 * An alternative to qsort_r() when that is not available on your platform.
711 *
712 * If it is available, qsort_r() is used directly.
713 *
714 * @param array the array that shall be sorted
715 * @param nmemb the number of elements in the array
716 * @param size the size of one element
717 * @param fn the compare function
718 * @param context the context for the compare function
719 */
720 CX_EXTERN CX_NONNULL
721 void cx_array_qsort_c(void *array, size_t nmemb, size_t size,
722 cx_compare_func2 fn, void *context);
723
724 /**
725 * Sorts an array.
726 *
727 * Internal function - do not use.
728 *
729 * @param array a pointer to the array structure
730 * @param elem_size the size of one element
731 * @param fn the compare function
732 */
733 CX_EXTERN CX_NONNULL
734 void cx_array_sort_(CxArray *array, size_t elem_size,
735 cx_compare_func fn);
736
737 /**
738 * Sorts an array.
739 *
740 * Internal function - do not use.
741 *
742 * @param array a pointer to the array structure
743 * @param elem_size the size of one element
744 * @param fn the compare function
745 * @param context the context for the compare function
746 */
747 CX_EXTERN CX_NONNULL
748 void cx_array_sort_c_(CxArray *array, size_t elem_size,
749 cx_compare_func2 fn, void *context);
750
751 /**
752 * Sorts an array.
753 *
754 * @param array the name of the array
755 * @param fn (@c cx_compare_func) the compare function
756 */
757 #define cx_array_sort(array, fn) \
758 cx_array_sort_((CxArray*)&(array), sizeof((array).data[0]), fn)
759
760 /**
761 * Sorts an array.
762 *
763 * @param array the name of the array
764 * @param fn (@c cx_compare_func2) the compare function
765 * @param context (@c void*) the context for the compare function
766 */
767 #define cx_array_sort_c(array, fn, context) \
768 cx_array_sort_c_((CxArray*)&(array), sizeof((array).data[0]), fn, context)
547 769
548 /** 770 /**
549 * Creates an iterator over the elements of an array. 771 * Creates an iterator over the elements of an array.
550 * 772 *
551 * Internal function - do not use. 773 * Internal function - do not use.
552 * 774 *
553 * @param array a pointer to the array structure 775 * @param array a pointer to the array structure
554 * @param elem_size the size of one element 776 * @param elem_size the size of one element
555 * @return an iterator over the elements 777 * @return an iterator over the elements
556 */ 778 */
557 cx_attr_nodiscard cx_attr_nonnull 779 CX_EXTERN CX_NODISCARD CX_NONNULL
558 CX_EXPORT CxIterator cx_array_iterator_(CxArray *array, size_t elem_size); 780 CxIterator cx_array_iterator_(CxArray *array, size_t elem_size);
559 781
560 /** 782 /**
561 * Creates an iterator over the elements of an array. 783 * Creates an iterator over the elements of an array.
562 * 784 *
563 * The iterator will yield pointers to the elements. 785 * The iterator will yield pointers to the elements.
786 *
787 * This iterator cannot be used to remove elements
788 * because it does not get a modifiable reference to the array's size.
564 * 789 *
565 * @param array the name of the array 790 * @param array the name of the array
566 * @return an iterator over the elements 791 * @return an iterator over the elements
567 * @see cx_array_iterator_ptr() 792 * @see cx_array_iterator_ptr()
568 */ 793 */
575 * Internal function - do not use. 800 * Internal function - do not use.
576 * 801 *
577 * @param array the name of the array 802 * @param array the name of the array
578 * @return an iterator over the elements 803 * @return an iterator over the elements
579 */ 804 */
580 cx_attr_nodiscard cx_attr_nonnull 805 CX_EXTERN CX_NODISCARD CX_NONNULL
581 CX_EXPORT CxIterator cx_array_iterator_ptr_(CxArray *array); 806 CxIterator cx_array_iterator_ptr_(CxArray *array);
582 807
583 /** 808 /**
584 * Creates an iterator over the elements of an array containing pointers. 809 * Creates an iterator over the elements of an array containing pointers.
585 * 810 *
586 * The iterator will yield the elements themselves, which are supposed to 811 * The iterator will yield the elements themselves, which are supposed to
587 * be pointers. 812 * be pointers.
588 * 813 *
814 * This iterator cannot be used to remove elements
815 * because it does not get a modifiable reference to the array's size.
816 *
589 * @param array the name of the array 817 * @param array the name of the array
590 * @return an iterator over the elements 818 * @return an iterator over the elements
591 * @see cx_array_iterator() 819 * @see cx_array_iterator()
592 */ 820 */
593 #define cx_array_iterator_ptr(array) \ 821 #define cx_array_iterator_ptr(array) \
594 cx_array_iterator_ptr_((CxArray*)&(array)) 822 cx_array_iterator_ptr_((CxArray*)&(array))
595 823
824
825 /**
826 * Removes elements from the array.
827 *
828 * Internal function - do not use.
829 *
830 * @param array a pointer to the array structure
831 * @param elem_size the size of one element
832 * @param index the index of the first element to remove
833 * @param n the number of elements to remove
834 * @param fast indicates whether tail elements should be copied into the gap
835 */
836 CX_EXTERN CX_NONNULL
837 void cx_array_remove_(CxArray *array, size_t elem_size, size_t index, size_t n, bool fast);
838
839 /**
840 * Removes one element from the array.
841 *
842 * Tail elements are all moved by one. If you don't need a stable order
843 * in the array, consider using cx_array_remove_fast().
844 *
845 * If the index is out of bounds, this function does nothing.
846 *
847 * @param array the name of the array
848 * @param index (@c size_t) the index of the element to remove
849 * @see cx_array_remove_fast()
850 */
851 #define cx_array_remove(array, index) \
852 cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, 1, false)
853
854 /**
855 * Removes one element from the array.
856 *
857 * The gap will be filled with a copy of the last element in the array.
858 * This changes the order of elements. If you want a stable order,
859 * use cx_array_remove() instead.
860 *
861 * If the index is out of bounds, this function does nothing.
862 *
863 * @param array the name of the array
864 * @param index (@c size_t) the index of the element to remove
865 * @see cx_array_remove()
866 */
867 #define cx_array_remove_fast(array, index) \
868 cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, 1, true)
869
870 /**
871 * Removes multiple elements from the array.
872 *
873 * Tail elements are all moved to close the gap. If you don't need a stable
874 * order in the array, consider using cx_array_remove_array_fast().
875 *
876 * If the index is out of bounds, this function does nothing.
877 * If @n overflows the array, this function removes as many elements as it can.
878 *
879 * @param array the name of the array
880 * @param index (@c size_t) the index of the first element to remove
881 * @param n (@c size_t) the number of elements to remove
882 * @see cx_array_remove_array_fast()
883 */
884 #define cx_array_remove_array(array, index, n) \
885 cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, n, false)
886
887 /**
888 * Removes multiple elements from the array.
889 *
890 * Tail elements are copied into the gap. If you have more tail elements
891 * than the number of elements that are removed, this will change the order
892 * of elements. If you want a stable order, use cx_array_remove_array() instead.
893 *
894 * If the index is out of bounds, this function does nothing.
895 * If @n overflows the array, this function removes as many elements as it can.
896 *
897 * @param array the name of the array
898 * @param index (@c size_t) the index of the first element to remove
899 * @param n (@c size_t) the number of elements to remove
900 * @see cx_array_remove_array()
901 */
902 #define cx_array_remove_array_fast(array, index, n) \
903 cx_array_remove_((CxArray*)&(array), sizeof((array).data[0]), index, n, true)
904
596 /** 905 /**
597 * Deallocates an array. 906 * Deallocates an array.
598 * 907 *
599 * Internal function - do not use. 908 * Internal function - do not use.
600 * 909 *
601 * @param allocator (@c CxAllocator*) the allocator which was used to allocate the array 910 * @param allocator (@c CxAllocator*) the allocator which was used to allocate the array
602 * @param array a pointer to the array structure 911 * @param array a pointer to the array structure
603 */ 912 */
604 cx_attr_nonnull 913 CX_EXTERN CX_NONNULL
605 CX_EXPORT void cx_array_free_(const CxAllocator *allocator, CxArray *array); 914 void cx_array_free_(const CxAllocator *allocator, CxArray *array);
606 915
607 /** 916 /**
608 * Deallocates an array. 917 * Deallocates an array.
609 * 918 *
610 * The structure is reset to zero and can be re-initialized with 919 * The structure is reset to zero and can be re-initialized with
649 * @param cmp_func the compare function 958 * @param cmp_func the compare function
650 * @return the index of the largest lower bound, or @p size 959 * @return the index of the largest lower bound, or @p size
651 * @see cx_array_binary_search_sup() 960 * @see cx_array_binary_search_sup()
652 * @see cx_array_binary_search() 961 * @see cx_array_binary_search()
653 */ 962 */
654 cx_attr_nonnull 963 CX_EXTERN CX_NONNULL
655 CX_EXPORT size_t cx_array_binary_search_inf(const void *arr, size_t size, 964 size_t cx_array_binary_search_inf(const void *arr, size_t size,
656 size_t elem_size, const void *elem, cx_compare_func cmp_func); 965 size_t elem_size, const void *elem, cx_compare_func cmp_func);
657 966
658 /** 967 /**
659 * Searches an item in a sorted array. 968 * Searches an item in a sorted array.
660 * 969 *
672 * @return the index of the element in the array, or @p size if the element 981 * @return the index of the element in the array, or @p size if the element
673 * cannot be found 982 * cannot be found
674 * @see cx_array_binary_search_inf() 983 * @see cx_array_binary_search_inf()
675 * @see cx_array_binary_search_sup() 984 * @see cx_array_binary_search_sup()
676 */ 985 */
677 cx_attr_nonnull 986 CX_EXTERN CX_NONNULL
678 CX_EXPORT size_t cx_array_binary_search(const void *arr, size_t size, 987 size_t cx_array_binary_search(const void *arr, size_t size,
679 size_t elem_size, const void *elem, cx_compare_func cmp_func); 988 size_t elem_size, const void *elem, cx_compare_func cmp_func);
680 989
681 /** 990 /**
682 * Searches the smallest upper bound in a sorted array. 991 * Searches the smallest upper bound in a sorted array.
683 * 992 *
701 * @param cmp_func the compare function 1010 * @param cmp_func the compare function
702 * @return the index of the smallest upper bound, or @p size 1011 * @return the index of the smallest upper bound, or @p size
703 * @see cx_array_binary_search_inf() 1012 * @see cx_array_binary_search_inf()
704 * @see cx_array_binary_search() 1013 * @see cx_array_binary_search()
705 */ 1014 */
706 cx_attr_nonnull 1015 CX_EXTERN CX_NONNULL
707 CX_EXPORT size_t cx_array_binary_search_sup(const void *arr, size_t size, 1016 size_t cx_array_binary_search_sup(const void *arr, size_t size,
708 size_t elem_size, const void *elem, cx_compare_func cmp_func); 1017 size_t elem_size, const void *elem, cx_compare_func cmp_func);
709 1018
710 1019
711 /** 1020 /**
712 * Searches the largest lower bound in a sorted array. 1021 * Searches the largest lower bound in a sorted array.
732 * @param context the context for the compare function 1041 * @param context the context for the compare function
733 * @return the index of the largest lower bound, or @p size 1042 * @return the index of the largest lower bound, or @p size
734 * @see cx_array_binary_search_sup() 1043 * @see cx_array_binary_search_sup()
735 * @see cx_array_binary_search() 1044 * @see cx_array_binary_search()
736 */ 1045 */
737 cx_attr_nonnull 1046 CX_EXTERN CX_NONNULL
738 CX_EXPORT size_t cx_array_binary_search_inf_c(const void *arr, size_t size, 1047 size_t cx_array_binary_search_inf_c(const void *arr, size_t size,
739 size_t elem_size, const void *elem, cx_compare_func2 cmp_func, void *context); 1048 size_t elem_size, const void *elem, cx_compare_func2 cmp_func, void *context);
740 1049
741 /** 1050 /**
742 * Searches an item in a sorted array. 1051 * Searches an item in a sorted array.
743 * 1052 *
756 * @return the index of the element in the array, or @p size if the element 1065 * @return the index of the element in the array, or @p size if the element
757 * cannot be found 1066 * cannot be found
758 * @see cx_array_binary_search_inf() 1067 * @see cx_array_binary_search_inf()
759 * @see cx_array_binary_search_sup() 1068 * @see cx_array_binary_search_sup()
760 */ 1069 */
761 cx_attr_nonnull 1070 CX_EXTERN CX_NONNULL
762 CX_EXPORT size_t cx_array_binary_search_c(const void *arr, size_t size, 1071 size_t cx_array_binary_search_c(const void *arr, size_t size,
763 size_t elem_size, const void *elem, cx_compare_func2 cmp_func, void *context); 1072 size_t elem_size, const void *elem, cx_compare_func2 cmp_func, void *context);
764 1073
765 /** 1074 /**
766 * Searches the smallest upper bound in a sorted array. 1075 * Searches the smallest upper bound in a sorted array.
767 * 1076 *
786 * @param context the context for the compare function 1095 * @param context the context for the compare function
787 * @return the index of the smallest upper bound, or @p size 1096 * @return the index of the smallest upper bound, or @p size
788 * @see cx_array_binary_search_inf() 1097 * @see cx_array_binary_search_inf()
789 * @see cx_array_binary_search() 1098 * @see cx_array_binary_search()
790 */ 1099 */
791 cx_attr_nonnull 1100 CX_EXTERN CX_NONNULL
792 CX_EXPORT size_t cx_array_binary_search_sup_c(const void *arr, size_t size, 1101 size_t cx_array_binary_search_sup_c(const void *arr, size_t size,
793 size_t elem_size, const void *elem, cx_compare_func2 cmp_func, void *context); 1102 size_t elem_size, const void *elem, cx_compare_func2 cmp_func, void *context);
794 1103
795 /** 1104 /**
796 * Swaps two array elements. 1105 * Swaps two array elements.
797 * 1106 *
798 * @param arr the array 1107 * @param arr the array
799 * @param elem_size the element size 1108 * @param elem_size the element size
800 * @param idx1 index of the first element 1109 * @param idx1 index of the first element
801 * @param idx2 index of the second element 1110 * @param idx2 index of the second element
802 */ 1111 */
803 cx_attr_nonnull 1112 CX_EXTERN CX_NONNULL
804 CX_EXPORT void cx_array_swap(void *arr, size_t elem_size, size_t idx1, size_t idx2); 1113 void cx_array_swap(void *arr, size_t elem_size, size_t idx1, size_t idx2);
805 1114
806 /** 1115 /**
807 * Allocates an array list for storing elements with @p elem_size bytes each. 1116 * Allocates an array list for storing elements with @p elem_size bytes each.
808 * 1117 *
809 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of 1118 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
814 * (if @c NULL, the cxDefaultAllocator will be used) 1123 * (if @c NULL, the cxDefaultAllocator will be used)
815 * @param elem_size the size of each element in bytes 1124 * @param elem_size the size of each element in bytes
816 * @param initial_capacity the initial number of elements the array can store 1125 * @param initial_capacity the initial number of elements the array can store
817 * @return the created list 1126 * @return the created list
818 */ 1127 */
819 cx_attr_nodiscard 1128 CX_EXTERN CX_NODISCARD CX_MALLOC CX_DEALLOC(cxListFree, 1)
820 cx_attr_malloc 1129 CxList *cxArrayListCreate(const CxAllocator *allocator,
821 cx_attr_dealloc(cxListFree, 1)
822 CX_EXPORT CxList *cxArrayListCreate(const CxAllocator *allocator,
823 size_t elem_size, size_t initial_capacity); 1130 size_t elem_size, size_t initial_capacity);
824 1131
825 #ifdef __cplusplus
826 } // extern "C"
827 #endif
828
829 #endif // UCX_ARRAY_LIST_H 1132 #endif // UCX_ARRAY_LIST_H

Mercurial Repository: toolkit

mercurial