src/cx/array_list.h

changeset 1426
3a89b31f0724
parent 1425
83284b289430
equal deleted inserted replaced
1425:83284b289430 1426:3a89b31f0724
45 45
46 /** 46 /**
47 * The maximum item size in an array list that fits into 47 * The maximum item size in an array list that fits into
48 * a stack buffer when swapped. 48 * a stack buffer when swapped.
49 */ 49 */
50 cx_attr_export 50 CX_EXPORT extern const unsigned cx_array_swap_sbo_size;
51 extern const unsigned cx_array_swap_sbo_size;
52 51
53 /** 52 /**
54 * 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.
55 * 54 *
56 * @par Examples 55 * @par Examples
181 * @param new_capacity the new number of elements 180 * @param new_capacity the new number of elements
182 * @param elem_size the size of each element 181 * @param elem_size the size of each element
183 * @param alloc a reference to this allocator 182 * @param alloc a reference to this allocator
184 * @return a pointer to the reallocated memory or @c NULL on failure 183 * @return a pointer to the reallocated memory or @c NULL on failure
185 */ 184 */
186 cx_attr_nodiscard 185 void *(*realloc)( void *array, size_t old_capacity, size_t new_capacity,
187 cx_attr_nonnull_arg(5) 186 size_t elem_size, struct cx_array_reallocator_s *alloc);
188 cx_attr_allocsize(3, 4)
189 void *(*realloc)(
190 void *array,
191 size_t old_capacity,
192 size_t new_capacity,
193 size_t elem_size,
194 struct cx_array_reallocator_s *alloc
195 );
196 187
197 /** 188 /**
198 * The allocator that shall be used for the reallocations. 189 * The allocator that shall be used for the reallocations.
199 */ 190 */
200 const CxAllocator *allocator; 191 const CxAllocator *allocator;
211 typedef struct cx_array_reallocator_s CxArrayReallocator; 202 typedef struct cx_array_reallocator_s CxArrayReallocator;
212 203
213 /** 204 /**
214 * A default array reallocator that is based on the cxDefaultAllocator. 205 * A default array reallocator that is based on the cxDefaultAllocator.
215 */ 206 */
216 cx_attr_export 207 CX_EXPORT extern CxArrayReallocator *cx_array_default_reallocator;
217 extern CxArrayReallocator *cx_array_default_reallocator;
218 208
219 /** 209 /**
220 * Creates a new array reallocator. 210 * Creates a new array reallocator.
221 * 211 *
222 * When @p allocator is @c NULL, the cxDefaultAllocator will be used. 212 * When @p allocator is @c NULL, the cxDefaultAllocator will be used.
232 * @param allocator the allocator this reallocator shall be based on 222 * @param allocator the allocator this reallocator shall be based on
233 * @param stack_ptr the address of the array when the array is initially located 223 * @param stack_ptr the address of the array when the array is initially located
234 * on the stack or shall not reallocate in place 224 * on the stack or shall not reallocate in place
235 * @return an array reallocator 225 * @return an array reallocator
236 */ 226 */
237 cx_attr_export 227 CX_EXPORT CxArrayReallocator cx_array_reallocator(
238 CxArrayReallocator cx_array_reallocator( 228 const struct cx_allocator_s *allocator, const void *stack_ptr);
239 const struct cx_allocator_s *allocator,
240 const void *stack_ptr
241 );
242 229
243 /** 230 /**
244 * Reserves memory for additional elements. 231 * Reserves memory for additional elements.
245 * 232 *
246 * This function checks if the @p capacity of the array is sufficient to hold 233 * This function checks if the @p capacity of the array is sufficient to hold
269 * @retval zero success 256 * @retval zero success
270 * @retval non-zero failure 257 * @retval non-zero failure
271 * @see cx_array_reallocator() 258 * @see cx_array_reallocator()
272 */ 259 */
273 cx_attr_nonnull_arg(1, 2, 3) 260 cx_attr_nonnull_arg(1, 2, 3)
274 cx_attr_export 261 CX_EXPORT int cx_array_reserve(void **array, void *size, void *capacity,
275 int cx_array_reserve( 262 unsigned width, size_t elem_size, size_t elem_count,
276 void **array, 263 CxArrayReallocator *reallocator);
277 void *size,
278 void *capacity,
279 unsigned width,
280 size_t elem_size,
281 size_t elem_count,
282 CxArrayReallocator *reallocator
283 );
284 264
285 /** 265 /**
286 * Copies elements from one array to another. 266 * Copies elements from one array to another.
287 * 267 *
288 * The elements are copied to the @p target array at the specified @p index, 268 * The elements are copied to the @p target array at the specified @p index,
313 * @retval zero success 293 * @retval zero success
314 * @retval non-zero failure 294 * @retval non-zero failure
315 * @see cx_array_reallocator() 295 * @see cx_array_reallocator()
316 */ 296 */
317 cx_attr_nonnull_arg(1, 2, 3, 6) 297 cx_attr_nonnull_arg(1, 2, 3, 6)
318 cx_attr_export 298 CX_EXPORT int cx_array_copy(void **target, void *size, void *capacity, unsigned width,
319 int cx_array_copy( 299 size_t index, const void *src, size_t elem_size, size_t elem_count,
320 void **target, 300 CxArrayReallocator *reallocator);
321 void *size,
322 void *capacity,
323 unsigned width,
324 size_t index,
325 const void *src,
326 size_t elem_size,
327 size_t elem_count,
328 CxArrayReallocator *reallocator
329 );
330 301
331 /** 302 /**
332 * Convenience macro that uses cx_array_copy() with a default layout and 303 * Convenience macro that uses cx_array_copy() with a default layout and
333 * the specified reallocator. 304 * the specified reallocator.
334 * 305 *
472 * (@c NULL defaults to #cx_array_default_reallocator) 443 * (@c NULL defaults to #cx_array_default_reallocator)
473 * @retval zero success 444 * @retval zero success
474 * @retval non-zero failure 445 * @retval non-zero failure
475 */ 446 */
476 cx_attr_nonnull_arg(1, 2, 3, 5) 447 cx_attr_nonnull_arg(1, 2, 3, 5)
477 cx_attr_export 448 CX_EXPORT int cx_array_insert_sorted(void **target, size_t *size, size_t *capacity,
478 int cx_array_insert_sorted( 449 cx_compare_func cmp_func, const void *src, size_t elem_size, size_t elem_count,
479 void **target, 450 CxArrayReallocator *reallocator);
480 size_t *size,
481 size_t *capacity,
482 cx_compare_func cmp_func,
483 const void *src,
484 size_t elem_size,
485 size_t elem_count,
486 CxArrayReallocator *reallocator
487 );
488 451
489 /** 452 /**
490 * Inserts an element into a sorted array. 453 * Inserts an element into a sorted array.
491 * 454 *
492 * If the target array is not already sorted with respect 455 * If the target array is not already sorted with respect
493 * to the specified @p cmp_func, the behavior is undefined. 456 * to the specified @p cmp_func, the behavior is undefined.
494 * 457 *
495 * If the capacity is insufficient to hold the new data, a reallocation 458 * If the capacity is not enough to hold the new data, a reallocation
496 * attempt is made. 459 * attempt is made.
497 * 460 *
498 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type. 461 * The \@ SIZE_TYPE is flexible and can be any unsigned integer type.
499 * It is important, however, that @p size and @p capacity are pointers to 462 * It is important, however, that @p size and @p capacity are pointers to
500 * variables of the same type. 463 * variables of the same type.
601 * (@c NULL defaults to #cx_array_default_reallocator) 564 * (@c NULL defaults to #cx_array_default_reallocator)
602 * @retval zero success 565 * @retval zero success
603 * @retval non-zero failure 566 * @retval non-zero failure
604 */ 567 */
605 cx_attr_nonnull_arg(1, 2, 3, 5) 568 cx_attr_nonnull_arg(1, 2, 3, 5)
606 cx_attr_export 569 CX_EXPORT int cx_array_insert_unique(void **target, size_t *size, size_t *capacity,
607 int cx_array_insert_unique( 570 cx_compare_func cmp_func, const void *src, size_t elem_size, size_t elem_count,
608 void **target, 571 CxArrayReallocator *reallocator);
609 size_t *size,
610 size_t *capacity,
611 cx_compare_func cmp_func,
612 const void *src,
613 size_t elem_size,
614 size_t elem_count,
615 CxArrayReallocator *reallocator
616 );
617 572
618 /** 573 /**
619 * Inserts an element into a sorted array if it does not exist. 574 * Inserts an element into a sorted array if it does not exist.
620 * 575 *
621 * If the target array is not already sorted with respect 576 * If the target array is not already sorted with respect
728 * @return the index of the largest lower bound, or @p size 683 * @return the index of the largest lower bound, or @p size
729 * @see cx_array_binary_search_sup() 684 * @see cx_array_binary_search_sup()
730 * @see cx_array_binary_search() 685 * @see cx_array_binary_search()
731 */ 686 */
732 cx_attr_nonnull 687 cx_attr_nonnull
733 cx_attr_export 688 CX_EXPORT size_t cx_array_binary_search_inf(const void *arr, size_t size,
734 size_t cx_array_binary_search_inf( 689 size_t elem_size, const void *elem, cx_compare_func cmp_func);
735 const void *arr,
736 size_t size,
737 size_t elem_size,
738 const void *elem,
739 cx_compare_func cmp_func
740 );
741 690
742 /** 691 /**
743 * Searches an item in a sorted array. 692 * Searches an item in a sorted array.
744 * 693 *
745 * If the array is not sorted with respect to the @p cmp_func, the behavior 694 * If the array is not sorted with respect to the @p cmp_func, the behavior
754 * cannot be found 703 * cannot be found
755 * @see cx_array_binary_search_inf() 704 * @see cx_array_binary_search_inf()
756 * @see cx_array_binary_search_sup() 705 * @see cx_array_binary_search_sup()
757 */ 706 */
758 cx_attr_nonnull 707 cx_attr_nonnull
759 cx_attr_export 708 CX_EXPORT size_t cx_array_binary_search(const void *arr, size_t size,
760 size_t cx_array_binary_search( 709 size_t elem_size, const void *elem, cx_compare_func cmp_func);
761 const void *arr,
762 size_t size,
763 size_t elem_size,
764 const void *elem,
765 cx_compare_func cmp_func
766 );
767 710
768 /** 711 /**
769 * Searches the smallest upper bound in a sorted array. 712 * Searches the smallest upper bound in a sorted array.
770 * 713 *
771 * In other words, this function returns the index of the smallest element 714 * In other words, this function returns the index of the smallest element
786 * @return the index of the smallest upper bound, or @p size 729 * @return the index of the smallest upper bound, or @p size
787 * @see cx_array_binary_search_inf() 730 * @see cx_array_binary_search_inf()
788 * @see cx_array_binary_search() 731 * @see cx_array_binary_search()
789 */ 732 */
790 cx_attr_nonnull 733 cx_attr_nonnull
791 cx_attr_export 734 CX_EXPORT size_t cx_array_binary_search_sup(const void *arr, size_t size,
792 size_t cx_array_binary_search_sup( 735 size_t elem_size, const void *elem, cx_compare_func cmp_func);
793 const void *arr,
794 size_t size,
795 size_t elem_size,
796 const void *elem,
797 cx_compare_func cmp_func
798 );
799 736
800 /** 737 /**
801 * Swaps two array elements. 738 * Swaps two array elements.
802 * 739 *
803 * @param arr the array 740 * @param arr the array
804 * @param elem_size the element size 741 * @param elem_size the element size
805 * @param idx1 index of the first element 742 * @param idx1 index of the first element
806 * @param idx2 index of the second element 743 * @param idx2 index of the second element
807 */ 744 */
808 cx_attr_nonnull 745 cx_attr_nonnull
809 cx_attr_export 746 CX_EXPORT void cx_array_swap(void *arr, size_t elem_size, size_t idx1, size_t idx2);
810 void cx_array_swap(
811 void *arr,
812 size_t elem_size,
813 size_t idx1,
814 size_t idx2
815 );
816 747
817 /** 748 /**
818 * Allocates an array list for storing elements with @p elem_size bytes each. 749 * Allocates an array list for storing elements with @p elem_size bytes each.
819 * 750 *
820 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of 751 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
831 * @return the created list 762 * @return the created list
832 */ 763 */
833 cx_attr_nodiscard 764 cx_attr_nodiscard
834 cx_attr_malloc 765 cx_attr_malloc
835 cx_attr_dealloc(cxListFree, 1) 766 cx_attr_dealloc(cxListFree, 1)
836 cx_attr_export 767 CX_EXPORT CxList *cxArrayListCreate(const CxAllocator *allocator,
837 CxList *cxArrayListCreate( 768 cx_compare_func comparator, size_t elem_size, size_t initial_capacity);
838 const CxAllocator *allocator,
839 cx_compare_func comparator,
840 size_t elem_size,
841 size_t initial_capacity
842 );
843 769
844 /** 770 /**
845 * Allocates an array list for storing elements with @p elem_size bytes each. 771 * Allocates an array list for storing elements with @p elem_size bytes each.
846 * 772 *
847 * The list will use the cxDefaultAllocator and @em NO compare function. 773 * The list will use the cxDefaultAllocator and @em NO compare function.

mercurial