Mercurial > hg > dav / file comparison

comparison: ucx/cx/array_list.h

ucx/cx/array_list.h

branch
dav-2
changeset 894
e86049631677
parent 891
4d58cbcc9efa
equal deleted inserted replaced
893:38800d479cd4 894:e86049631677
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 *
402 * @param cmp_func the compare function 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, const void *sorted_data, size_t n, 405 size_t elem_size, const void *sorted_data, size_t n,
410 cx_compare_func cmp_func, 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.
559 * @param context additional context for the compare function 555 * @param context additional context for the compare function
560 * @param allow_duplicates @c false if duplicates shall be skipped during insertion 556 * @param allow_duplicates @c false if duplicates shall be skipped during insertion
561 * @retval zero success 557 * @retval zero success
562 * @retval non-zero a re-allocation was necessary but failed 558 * @retval non-zero a re-allocation was necessary but failed
563 */ 559 */
564 cx_attr_nonnull_arg(1, 2, 4, 6) 560 CX_EXTERN CX_NONNULL_ARG(1, 2, 4, 6)
565 CX_EXPORT int cx_array_insert_sorted_c_(const CxAllocator *allocator, CxArray *array, 561 int cx_array_insert_sorted_c_(const CxAllocator *allocator, CxArray *array,
566 size_t elem_size, const void *sorted_data, size_t n, 562 size_t elem_size, const void *sorted_data, size_t n,
567 cx_compare_func2 cmp_func, void *context, bool allow_duplicates); 563 cx_compare_func2 cmp_func, void *context, bool allow_duplicates);
568 564
569 /** 565 /**
570 * Inserts an element into a sorted array. 566 * Inserts an element into a sorted array.
579 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order 575 * @param cmp_func (@c cx_compare_func2) the compare function that establishes the order
580 * @param context (@c void*) additional context for the compare function 576 * @param context (@c void*) additional context for the compare function
581 * @retval zero success 577 * @retval zero success
582 * @retval non-zero a re-allocation was necessary but failed 578 * @retval non-zero a re-allocation was necessary but failed
583 */ 579 */
584 #define cx_array_insert_sorted_ca(allocator, array, element, cmp_func) \ 580 #define cx_array_insert_sorted_ca(allocator, array, element, cmp_func, context) \
585 cx_array_insert_sorted_c_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (void*)&(element), 1, cmp_func, context, true) 581 cx_array_insert_sorted_c_(allocator, (CxArray*)&(array), sizeof((array).data[0]), (void*)&(element), 1, cmp_func, context, true)
586 582
587 /** 583 /**
588 * Inserts an element into a sorted array. 584 * Inserts an element into a sorted array.
589 * 585 *
719 * @param nmemb the number of elements in the array 715 * @param nmemb the number of elements in the array
720 * @param size the size of one element 716 * @param size the size of one element
721 * @param fn the compare function 717 * @param fn the compare function
722 * @param context the context for the compare function 718 * @param context the context for the compare function
723 */ 719 */
724 CX_EXPORT void cx_array_qsort_c(void *array, size_t nmemb, size_t size, 720 CX_EXTERN CX_NONNULL
721 void cx_array_qsort_c(void *array, size_t nmemb, size_t size,
725 cx_compare_func2 fn, void *context); 722 cx_compare_func2 fn, void *context);
726 723
727 /** 724 /**
728 * Sorts an array. 725 * Sorts an array.
729 * 726 *
731 * 728 *
732 * @param array a pointer to the array structure 729 * @param array a pointer to the array structure
733 * @param elem_size the size of one element 730 * @param elem_size the size of one element
734 * @param fn the compare function 731 * @param fn the compare function
735 */ 732 */
736 CX_EXPORT void cx_array_sort_(CxArray *array, size_t elem_size, 733 CX_EXTERN CX_NONNULL
734 void cx_array_sort_(CxArray *array, size_t elem_size,
737 cx_compare_func fn); 735 cx_compare_func fn);
738 736
739 /** 737 /**
740 * Sorts an array. 738 * Sorts an array.
741 * 739 *
744 * @param array a pointer to the array structure 742 * @param array a pointer to the array structure
745 * @param elem_size the size of one element 743 * @param elem_size the size of one element
746 * @param fn the compare function 744 * @param fn the compare function
747 * @param context the context for the compare function 745 * @param context the context for the compare function
748 */ 746 */
749 CX_EXPORT void cx_array_sort_c_(CxArray *array, size_t elem_size, 747 CX_EXTERN CX_NONNULL
748 void cx_array_sort_c_(CxArray *array, size_t elem_size,
750 cx_compare_func2 fn, void *context); 749 cx_compare_func2 fn, void *context);
751 750
752 /** 751 /**
753 * Sorts an array. 752 * Sorts an array.
754 * 753 *
755 * @param array the name of the array 754 * @param array the name of the array
756 * @param fn (@c cx_compare_func) the compare function 755 * @param fn (@c cx_compare_func) the compare function
757 * @param context (@c void*) the context for the compare function
758 */ 756 */
759 #define cx_array_sort(array, fn) \ 757 #define cx_array_sort(array, fn) \
760 cx_array_sort_((CxArray*)&(array), sizeof((array).data[0]), fn) 758 cx_array_sort_((CxArray*)&(array), sizeof((array).data[0]), fn)
761 759
762 /** 760 /**
776 * 774 *
777 * @param array a pointer to the array structure 775 * @param array a pointer to the array structure
778 * @param elem_size the size of one element 776 * @param elem_size the size of one element
779 * @return an iterator over the elements 777 * @return an iterator over the elements
780 */ 778 */
781 cx_attr_nodiscard cx_attr_nonnull 779 CX_EXTERN CX_NODISCARD CX_NONNULL
782 CX_EXPORT CxIterator cx_array_iterator_(CxArray *array, size_t elem_size); 780 CxIterator cx_array_iterator_(CxArray *array, size_t elem_size);
783 781
784 /** 782 /**
785 * Creates an iterator over the elements of an array. 783 * Creates an iterator over the elements of an array.
786 * 784 *
787 * The iterator will yield pointers to the elements. 785 * The iterator will yield pointers to the elements.
802 * Internal function - do not use. 800 * Internal function - do not use.
803 * 801 *
804 * @param array the name of the array 802 * @param array the name of the array
805 * @return an iterator over the elements 803 * @return an iterator over the elements
806 */ 804 */
807 cx_attr_nodiscard cx_attr_nonnull 805 CX_EXTERN CX_NODISCARD CX_NONNULL
808 CX_EXPORT CxIterator cx_array_iterator_ptr_(CxArray *array); 806 CxIterator cx_array_iterator_ptr_(CxArray *array);
809 807
810 /** 808 /**
811 * Creates an iterator over the elements of an array containing pointers. 809 * Creates an iterator over the elements of an array containing pointers.
812 * 810 *
813 * The iterator will yield the elements themselves, which are supposed to 811 * The iterator will yield the elements themselves, which are supposed to
833 * @param elem_size the size of one element 831 * @param elem_size the size of one element
834 * @param index the index of the first element to remove 832 * @param index the index of the first element to remove
835 * @param n the number of elements to remove 833 * @param n the number of elements to remove
836 * @param fast indicates whether tail elements should be copied into the gap 834 * @param fast indicates whether tail elements should be copied into the gap
837 */ 835 */
838 cx_attr_nonnull 836 CX_EXTERN CX_NONNULL
839 CX_EXPORT void cx_array_remove_(CxArray *array, size_t elem_size, size_t index, size_t n, bool fast); 837 void cx_array_remove_(CxArray *array, size_t elem_size, size_t index, size_t n, bool fast);
840 838
841 /** 839 /**
842 * Removes one element from the array. 840 * Removes one element from the array.
843 * 841 *
844 * Tail elements are all moved by one. If you don't need a stable order 842 * Tail elements are all moved by one. If you don't need a stable order
910 * Internal function - do not use. 908 * Internal function - do not use.
911 * 909 *
912 * @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
913 * @param array a pointer to the array structure 911 * @param array a pointer to the array structure
914 */ 912 */
915 cx_attr_nonnull 913 CX_EXTERN CX_NONNULL
916 CX_EXPORT void cx_array_free_(const CxAllocator *allocator, CxArray *array); 914 void cx_array_free_(const CxAllocator *allocator, CxArray *array);
917 915
918 /** 916 /**
919 * Deallocates an array. 917 * Deallocates an array.
920 * 918 *
921 * 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
960 * @param cmp_func the compare function 958 * @param cmp_func the compare function
961 * @return the index of the largest lower bound, or @p size 959 * @return the index of the largest lower bound, or @p size
962 * @see cx_array_binary_search_sup() 960 * @see cx_array_binary_search_sup()
963 * @see cx_array_binary_search() 961 * @see cx_array_binary_search()
964 */ 962 */
965 cx_attr_nonnull 963 CX_EXTERN CX_NONNULL
966 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,
967 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);
968 966
969 /** 967 /**
970 * Searches an item in a sorted array. 968 * Searches an item in a sorted array.
971 * 969 *
983 * @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
984 * cannot be found 982 * cannot be found
985 * @see cx_array_binary_search_inf() 983 * @see cx_array_binary_search_inf()
986 * @see cx_array_binary_search_sup() 984 * @see cx_array_binary_search_sup()
987 */ 985 */
988 cx_attr_nonnull 986 CX_EXTERN CX_NONNULL
989 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,
990 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);
991 989
992 /** 990 /**
993 * Searches the smallest upper bound in a sorted array. 991 * Searches the smallest upper bound in a sorted array.
994 * 992 *
1012 * @param cmp_func the compare function 1010 * @param cmp_func the compare function
1013 * @return the index of the smallest upper bound, or @p size 1011 * @return the index of the smallest upper bound, or @p size
1014 * @see cx_array_binary_search_inf() 1012 * @see cx_array_binary_search_inf()
1015 * @see cx_array_binary_search() 1013 * @see cx_array_binary_search()
1016 */ 1014 */
1017 cx_attr_nonnull 1015 CX_EXTERN CX_NONNULL
1018 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,
1019 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);
1020 1018
1021 1019
1022 /** 1020 /**
1023 * Searches the largest lower bound in a sorted array. 1021 * Searches the largest lower bound in a sorted array.
1043 * @param context the context for the compare function 1041 * @param context the context for the compare function
1044 * @return the index of the largest lower bound, or @p size 1042 * @return the index of the largest lower bound, or @p size
1045 * @see cx_array_binary_search_sup() 1043 * @see cx_array_binary_search_sup()
1046 * @see cx_array_binary_search() 1044 * @see cx_array_binary_search()
1047 */ 1045 */
1048 cx_attr_nonnull 1046 CX_EXTERN CX_NONNULL
1049 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,
1050 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);
1051 1049
1052 /** 1050 /**
1053 * Searches an item in a sorted array. 1051 * Searches an item in a sorted array.
1054 * 1052 *
1067 * @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
1068 * cannot be found 1066 * cannot be found
1069 * @see cx_array_binary_search_inf() 1067 * @see cx_array_binary_search_inf()
1070 * @see cx_array_binary_search_sup() 1068 * @see cx_array_binary_search_sup()
1071 */ 1069 */
1072 cx_attr_nonnull 1070 CX_EXTERN CX_NONNULL
1073 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,
1074 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);
1075 1073
1076 /** 1074 /**
1077 * Searches the smallest upper bound in a sorted array. 1075 * Searches the smallest upper bound in a sorted array.
1078 * 1076 *
1097 * @param context the context for the compare function 1095 * @param context the context for the compare function
1098 * @return the index of the smallest upper bound, or @p size 1096 * @return the index of the smallest upper bound, or @p size
1099 * @see cx_array_binary_search_inf() 1097 * @see cx_array_binary_search_inf()
1100 * @see cx_array_binary_search() 1098 * @see cx_array_binary_search()
1101 */ 1099 */
1102 cx_attr_nonnull 1100 CX_EXTERN CX_NONNULL
1103 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,
1104 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);
1105 1103
1106 /** 1104 /**
1107 * Swaps two array elements. 1105 * Swaps two array elements.
1108 * 1106 *
1109 * @param arr the array 1107 * @param arr the array
1110 * @param elem_size the element size 1108 * @param elem_size the element size
1111 * @param idx1 index of the first element 1109 * @param idx1 index of the first element
1112 * @param idx2 index of the second element 1110 * @param idx2 index of the second element
1113 */ 1111 */
1114 cx_attr_nonnull 1112 CX_EXTERN CX_NONNULL
1115 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);
1116 1114
1117 /** 1115 /**
1118 * 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.
1119 * 1117 *
1120 * 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
1125 * (if @c NULL, the cxDefaultAllocator will be used) 1123 * (if @c NULL, the cxDefaultAllocator will be used)
1126 * @param elem_size the size of each element in bytes 1124 * @param elem_size the size of each element in bytes
1127 * @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
1128 * @return the created list 1126 * @return the created list
1129 */ 1127 */
1130 cx_attr_nodiscard 1128 CX_EXTERN CX_NODISCARD CX_MALLOC CX_DEALLOC(cxListFree, 1)
1131 cx_attr_malloc 1129 CxList *cxArrayListCreate(const CxAllocator *allocator,
1132 cx_attr_dealloc(cxListFree, 1)
1133 CX_EXPORT CxList *cxArrayListCreate(const CxAllocator *allocator,
1134 size_t elem_size, size_t initial_capacity); 1130 size_t elem_size, size_t initial_capacity);
1135 1131
1136 #ifdef __cplusplus
1137 } // extern "C"
1138 #endif
1139
1140 #endif // UCX_ARRAY_LIST_H 1132 #endif // UCX_ARRAY_LIST_H

Mercurial Repository: dav

mercurial