UNIXworkcode

/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. * * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ /** * @file array_list.h * @brief Array list implementation. * @author Mike Becker * @author Olaf Wintermann * @copyright 2-Clause BSD License */ #ifndef UCX_ARRAY_LIST_H #define UCX_ARRAY_LIST_H #include "list.h" #ifdef __cplusplus extern "C" { #endif /** * The maximum item size in an array list that fits into stack buffer * when swapped. */ extern const unsigned cx_array_swap_sbo_size; /** * Declares variables for an array that can be used with the convenience macros. * * @par Examples * @code * // integer array with at most 255 elements * CX_ARRAY_DECLARE_SIZED(int, myarray, uint8_t) * * // array of MyObject* pointers where size and capacity are stored as unsigned int * CX_ARRAY_DECLARE_SIZED(MyObject*, objects, unsigned int) * * // initializing code * cx_array_initialize(myarray, 16); // reserve space for 16 * cx_array_initialize(objects, 100); // reserve space for 100 * @endcode * * @param type the type of the data * @param name the name of the array * @param size_type the type of the size (should be uint8_t, uint16_t, uint32_t, or size_t) * * @see cx_array_initialize() * @see cx_array_simple_add() * @see cx_array_simple_copy() * @see cx_array_simple_add_sorted() * @see cx_array_simple_insert_sorted() */ #define CX_ARRAY_DECLARE_SIZED(type, name, size_type) \ type * name; \ /** Array size. */ size_type name##_size; \ /** Array capacity. */ size_type name##_capacity /** * Declares variables for an array that can be used with the convenience macros. * * The size and capacity variables will have @c size_t type. * Use #CX_ARRAY_DECLARE_SIZED() to specify a different type. * * @par Examples * @code * // int array * CX_ARRAY_DECLARE(int, myarray) * * // initializing code * cx_array_initialize(myarray, 32); // reserve space for 32 * @endcode * * @param type the type of the data * @param name the name of the array * * @see cx_array_initialize() * @see cx_array_simple_add() * @see cx_array_simple_copy() * @see cx_array_simple_add_sorted() * @see cx_array_simple_insert_sorted() */ #define CX_ARRAY_DECLARE(type, name) CX_ARRAY_DECLARE_SIZED(type, name, size_t) /** * Initializes an array with the given capacity. * * The type of the capacity depends on the type used during declaration. * * @par Examples * @code * CX_ARRAY_DECLARE_SIZED(int, arr1, uint8_t) * CX_ARRAY_DECLARE(int, arr2) // size and capacity are implicitly size_t * * // initializing code * cx_array_initialize(arr1, 500); // error: maximum for uint8_t is 255 * cx_array_initialize(arr2, 500); // OK * @endcode * * * The memory for the array is allocated with stdlib malloc(). * @param array the name of the array * @param capacity the initial capacity * @see cx_array_initialize_a() * @see CX_ARRAY_DECLARE_SIZED() * @see CX_ARRAY_DECLARE() */ #define cx_array_initialize(array, capacity) \ array##_capacity = capacity; \ array##_size = 0; \ array = malloc(sizeof(array[0]) * capacity) /** * Initializes an array with the given capacity using the specified allocator. * * @par Example * @code * CX_ARRAY_DECLARE(int, myarray) * * * const CxAllocator *al = // ... * cx_array_initialize_a(al, myarray, 128); * // ... * cxFree(al, myarray); // don't forget to free with same allocator * @endcode * * The memory for the array is allocated with stdlib malloc(). * @param allocator (@c CxAllocator*) the allocator * @param array the name of the array * @param capacity the initial capacity * @see cx_array_initialize() * @see CX_ARRAY_DECLARE_SIZED() * @see CX_ARRAY_DECLARE() */ #define cx_array_initialize_a(allocator, array, capacity) \ array##_capacity = capacity; \ array##_size = 0; \ array = cxMalloc(allocator, sizeof(array[0]) * capacity) /** * Defines a reallocation mechanism for arrays. * You can create your own, use cx_array_reallocator(), or * use the #cx_array_default_reallocator. */ struct cx_array_reallocator_s { /** * Reallocates space for the given array. * * Implementations are not required to free the original array. * This allows reallocation of static memory by allocating heap memory * and copying the array contents. The information in the custom fields of * the referenced allocator can be used to track the state of the memory * or to transport other additional data. * * @param array the array to reallocate * @param capacity the new capacity (number of elements) * @param elem_size the size of each element * @param alloc a reference to this allocator * @return a pointer to the reallocated memory or @c NULL on failure */ cx_attr_nodiscard cx_attr_nonnull_arg(4) cx_attr_allocsize(2, 3) void *(*realloc)( void *array, size_t capacity, size_t elem_size, struct cx_array_reallocator_s *alloc ); /** * Custom data pointer. */ void *ptr1; /** * Custom data pointer. */ void *ptr2; /** * Custom data integer. */ size_t int1; /** * Custom data integer. */ size_t int2; }; /** * Typedef for the array reallocator struct. */ typedef struct cx_array_reallocator_s CxArrayReallocator; /** * A default stdlib-based array reallocator. */ extern CxArrayReallocator *cx_array_default_reallocator; /** * Creates a new array reallocator. * * When @p allocator is @c NULL, the stdlib default allocator will be used. * * When @p stackmem is not @c NULL, the reallocator is supposed to be used * @em only for the specific array that is initially located at @p stackmem. * When reallocation is needed, the reallocator checks, if the array is * still located at @p stackmem and copies the contents to the heap. * * @note Invoking this function with both arguments @c NULL will return a * reallocator that behaves like #cx_array_default_reallocator. * * @param allocator the allocator this reallocator shall be based on * @param stackmem the address of the array when the array is initially located * on the stack or shall not reallocated in place * @return an array reallocator */ CxArrayReallocator cx_array_reallocator( const struct cx_allocator_s *allocator, const void *stackmem ); /** * Reserves memory for additional elements. * * This function checks if the @p capacity of the array is sufficient to hold * at least @p size plus @p elem_count elements. If not, a reallocation is * performed with the specified @p reallocator. * You can create your own reallocator by hand, use #cx_array_default_reallocator, * or use the convenience function cx_array_reallocator() to create a custom reallocator. * * This function can be useful to replace subsequent calls to cx_array_copy() * with one single cx_array_reserve() and then - after guaranteeing a * sufficient capacity - use simple memmove() or memcpy(). * * The @p width in bytes refers to the size and capacity. * Both must have the same width. * Supported are 0, 1, 2, and 4, as well as 8 if running on a 64 bit * architecture. If set to zero, the native word width is used. * * @param array a pointer to the target array * @param size a pointer to the size of the array * @param capacity a pointer to the capacity of the array * @param width the width in bytes for the @p size and @p capacity or zero for default * @param elem_size the size of one element * @param elem_count the number of expected additional elements * @param reallocator the array reallocator to use * (@c NULL defaults to #cx_array_default_reallocator) * @retval zero success * @retval non-zero failure * @see cx_array_reallocator() */ cx_attr_nonnull_arg(1, 2, 3) int cx_array_reserve( void **array, void *size, void *capacity, unsigned width, size_t elem_size, size_t elem_count, CxArrayReallocator *reallocator ); /** * Copies elements from one array to another. * * The elements are copied to the @p target array at the specified @p index, * overwriting possible elements. The @p index does not need to be in range of * the current array @p size. If the new index plus the number of elements added * would extend the array's size, the remaining @p capacity is used. * * If the @p capacity is also insufficient to hold the new data, a reallocation * attempt is made with the specified @p reallocator. * You can create your own reallocator by hand, use #cx_array_default_reallocator, * or use the convenience function cx_array_reallocator() to create a custom reallocator. * * The @p width in bytes refers to the size and capacity. * Both must have the same width. * Supported are 0, 1, 2, and 4, as well as 8 if running on a 64 bit * architecture. If set to zero, the native word width is used. * * @param target a pointer to the target array * @param size a pointer to the size of the target array * @param capacity a pointer to the capacity of the target array * @param width the width in bytes for the @p size and @p capacity or zero for default * @param index the index where the copied elements shall be placed * @param src the source array * @param elem_size the size of one element * @param elem_count the number of elements to copy * @param reallocator the array reallocator to use * (@c NULL defaults to #cx_array_default_reallocator) * @retval zero success * @retval non-zero failure * @see cx_array_reallocator() */ cx_attr_nonnull_arg(1, 2, 3, 6) int cx_array_copy( void **target, void *size, void *capacity, unsigned width, size_t index, const void *src, size_t elem_size, size_t elem_count, CxArrayReallocator *reallocator ); /** * Convenience macro that uses cx_array_copy() with a default layout and * the specified reallocator. * * @param reallocator (@c CxArrayReallocator*) the array reallocator to use * @param array the name of the array (NOT a pointer or alias to the array) * @param index (@c size_t) the index where the copied elements shall be placed * @param src (@c void*) the source array * @param count (@c size_t) the number of elements to copy * @retval zero success * @retval non-zero failure * @see CX_ARRAY_DECLARE() * @see cx_array_simple_copy() */ #define cx_array_simple_copy_a(reallocator, array, index, src, count) \ cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ sizeof(array##_size), index, src, sizeof((array)[0]), count, \ reallocator) /** * Convenience macro that uses cx_array_copy() with a default layout and * the default reallocator. * * @param array the name of the array (NOT a pointer or alias to the array) * @param index (@c size_t) the index where the copied elements shall be placed * @param src (@c void*) the source array * @param count (@c size_t) the number of elements to copy * @retval zero success * @retval non-zero failure * @see CX_ARRAY_DECLARE() * @see cx_array_simple_copy_a() */ #define cx_array_simple_copy(array, index, src, count) \ cx_array_simple_copy_a(NULL, array, index, src, count) /** * Convenience macro that uses cx_array_reserve() with a default layout and * the specified reallocator. * * @param reallocator (@c CxArrayReallocator*) the array reallocator to use * @param array the name of the array (NOT a pointer or alias to the array) * @param count (@c size_t) the number of expected @em additional elements * @retval zero success * @retval non-zero failure * @see CX_ARRAY_DECLARE() * @see cx_array_simple_reserve() */ #define cx_array_simple_reserve_a(reallocator, array, count) \ cx_array_reserve((void**)&(array), &(array##_size), &(array##_capacity), \ sizeof(array##_size), sizeof((array)[0]), count, \ reallocator) /** * Convenience macro that uses cx_array_reserve() with a default layout and * the default reallocator. * * @param array the name of the array (NOT a pointer or alias to the array) * @param count (@c size_t) the number of expected additional elements * @retval zero success * @retval non-zero failure * @see CX_ARRAY_DECLARE() * @see cx_array_simple_reserve_a() */ #define cx_array_simple_reserve(array, count) \ cx_array_simple_reserve_a(NULL, array, count) /** * Adds an element to an array with the possibility of allocating more space. * * The element @p elem is added to the end of the @p target array which contains * @p size elements, already. The @p capacity must point to a variable denoting * the current maximum number of elements the array can hold. * * If the capacity is insufficient to hold the new element, an attempt to * increase the @p capacity is made and the new capacity is written back. * * The \@ SIZE_TYPE is flexible and can be any unsigned integer type. * It is important, however, that @p size and @p capacity are pointers to * variables of the same type. * * @param target (@c void**) a pointer to the target array * @param size (@c SIZE_TYPE*) a pointer to the size of the target array * @param capacity (@c SIZE_TYPE*) a pointer to the capacity of the target array * @param elem_size (@c size_t) the size of one element * @param elem (@c void*) a pointer to the element to add * @param reallocator (@c CxArrayReallocator*) the array reallocator to use * @retval zero success * @retval non-zero failure */ #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \ cx_array_copy((void**)(target), size, capacity, sizeof(*(size)), \ *(size), elem, elem_size, 1, reallocator) /** * Convenience macro that uses cx_array_add() with a default layout and * the specified reallocator. * * @param reallocator (@c CxArrayReallocator*) the array reallocator to use * @param array the name of the array (NOT a pointer or alias to the array) * @param elem the element to add (NOT a pointer, address is automatically taken) * @retval zero success * @retval non-zero failure * @see CX_ARRAY_DECLARE() * @see cx_array_simple_add() */ #define cx_array_simple_add_a(reallocator, array, elem) \ cx_array_simple_copy_a(reallocator, array, array##_size, &(elem), 1) /** * Convenience macro that uses cx_array_add() with a default layout and * the default reallocator. * * @param array the name of the array (NOT a pointer or alias to the array) * @param elem the element to add (NOT a pointer, address is automatically taken) * @retval zero success * @retval non-zero failure * @see CX_ARRAY_DECLARE() * @see cx_array_simple_add_a() */ #define cx_array_simple_add(array, elem) \ cx_array_simple_add_a(cx_array_default_reallocator, array, elem) /** * Inserts a sorted array into another sorted array. * * If either the target or the source array is not already sorted with respect * to the specified @p cmp_func, the behavior is undefined. * * If the capacity is insufficient to hold the new data, a reallocation * attempt is made. * You can create your own reallocator by hand, use #cx_array_default_reallocator, * or use the convenience function cx_array_reallocator() to create a custom reallocator. * * @param target a pointer to the target array * @param size a pointer to the size of the target array * @param capacity a pointer to the capacity of the target array * @param cmp_func the compare function for the elements * @param src the source array * @param elem_size the size of one element * @param elem_count the number of elements to insert * @param reallocator the array reallocator to use * (@c NULL defaults to #cx_array_default_reallocator) * @retval zero success * @retval non-zero failure */ cx_attr_nonnull_arg(1, 2, 3, 5) int cx_array_insert_sorted( void **target, size_t *size, size_t *capacity, cx_compare_func cmp_func, const void *src, size_t elem_size, size_t elem_count, CxArrayReallocator *reallocator ); /** * Inserts an element into a sorted array. * * If the target array is not already sorted with respect * to the specified @p cmp_func, the behavior is undefined. * * If the capacity is insufficient to hold the new data, a reallocation * attempt is made. * * The \@ SIZE_TYPE is flexible and can be any unsigned integer type. * It is important, however, that @p size and @p capacity are pointers to * variables of the same type. * * @param target (@c void**) a pointer to the target array * @param size (@c SIZE_TYPE*) a pointer to the size of the target array * @param capacity (@c SIZE_TYPE*) a pointer to the capacity of the target array * @param elem_size (@c size_t) the size of one element * @param elem (@c void*) a pointer to the element to add * @param cmp_func (@c cx_cmp_func) the compare function for the elements * @param reallocator (@c CxArrayReallocator*) the array reallocator to use * @retval zero success * @retval non-zero failure */ #define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \ cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator) /** * Convenience macro for cx_array_add_sorted() with a default * layout and the specified reallocator. * * @param reallocator (@c CxArrayReallocator*) the array reallocator to use * @param array the name of the array (NOT a pointer or alias to the array) * @param elem the element to add (NOT a pointer, address is automatically taken) * @param cmp_func (@c cx_cmp_func) the compare function for the elements * @retval zero success * @retval non-zero failure * @see CX_ARRAY_DECLARE() * @see cx_array_simple_add_sorted() */ #define cx_array_simple_add_sorted_a(reallocator, array, elem, cmp_func) \ cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \ sizeof((array)[0]), &(elem), cmp_func, reallocator) /** * Convenience macro for cx_array_add_sorted() with a default * layout and the default reallocator. * * @param array the name of the array (NOT a pointer or alias to the array) * @param elem the element to add (NOT a pointer, address is automatically taken) * @param cmp_func (@c cx_cmp_func) the compare function for the elements * @retval zero success * @retval non-zero failure * @see CX_ARRAY_DECLARE() * @see cx_array_simple_add_sorted_a() */ #define cx_array_simple_add_sorted(array, elem, cmp_func) \ cx_array_simple_add_sorted_a(NULL, array, elem, cmp_func) /** * Convenience macro for cx_array_insert_sorted() with a default * layout and the specified reallocator. * * @param reallocator (@c CxArrayReallocator*) the array reallocator to use * @param array the name of the array (NOT a pointer or alias to the array) * @param src (@c void*) pointer to the source array * @param n (@c size_t) number of elements in the source array * @param cmp_func (@c cx_cmp_func) the compare function for the elements * @retval zero success * @retval non-zero failure * @see CX_ARRAY_DECLARE() * @see cx_array_simple_insert_sorted() */ #define cx_array_simple_insert_sorted_a(reallocator, array, src, n, cmp_func) \ cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \ cmp_func, src, sizeof((array)[0]), n, reallocator) /** * Convenience macro for cx_array_insert_sorted() with a default * layout and the default reallocator. * * @param array the name of the array (NOT a pointer or alias to the array) * @param src (@c void*) pointer to the source array * @param n (@c size_t) number of elements in the source array * @param cmp_func (@c cx_cmp_func) the compare function for the elements * @retval zero success * @retval non-zero failure * @see CX_ARRAY_DECLARE() * @see cx_array_simple_insert_sorted_a() */ #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \ cx_array_simple_insert_sorted_a(NULL, array, src, n, cmp_func) /** * Searches the largest lower bound in a sorted array. * * In other words, this function returns the index of the largest element * in @p arr that is less or equal to @p elem with respect to @p cmp_func. * When no such element exists, @p size is returned. * * If @p elem is contained in the array, this is identical to * #cx_array_binary_search(). * * If the array is not sorted with respect to the @p cmp_func, the behavior * is undefined. * * @param arr the array to search * @param size the size of the array * @param elem_size the size of one element * @param elem the element to find * @param cmp_func the compare function * @return the index of the largest lower bound, or @p size * @see cx_array_binary_search_sup() * @see cx_array_binary_search() */ cx_attr_nonnull size_t cx_array_binary_search_inf( const void *arr, size_t size, size_t elem_size, const void *elem, cx_compare_func cmp_func ); /** * Searches an item in a sorted array. * * If the array is not sorted with respect to the @p cmp_func, the behavior * is undefined. * * @param arr the array to search * @param size the size of the array * @param elem_size the size of one element * @param elem the element to find * @param cmp_func the compare function * @return the index of the element in the array, or @p size if the element * cannot be found * @see cx_array_binary_search_inf() * @see cx_array_binary_search_sup() */ cx_attr_nonnull size_t cx_array_binary_search( const void *arr, size_t size, size_t elem_size, const void *elem, cx_compare_func cmp_func ); /** * Searches the smallest upper bound in a sorted array. * * In other words, this function returns the index of the smallest element * in @p arr that is greater or equal to @p elem with respect to @p cmp_func. * When no such element exists, @p size is returned. * * If @p elem is contained in the array, this is identical to * #cx_array_binary_search(). * * If the array is not sorted with respect to the @p cmp_func, the behavior * is undefined. * * @param arr the array to search * @param size the size of the array * @param elem_size the size of one element * @param elem the element to find * @param cmp_func the compare function * @return the index of the smallest upper bound, or @p size * @see cx_array_binary_search_inf() * @see cx_array_binary_search() */ cx_attr_nonnull size_t cx_array_binary_search_sup( const void *arr, size_t size, size_t elem_size, const void *elem, cx_compare_func cmp_func ); /** * Swaps two array elements. * * @param arr the array * @param elem_size the element size * @param idx1 index of first element * @param idx2 index of second element */ cx_attr_nonnull void cx_array_swap( void *arr, size_t elem_size, size_t idx1, size_t idx2 ); /** * Allocates an array list for storing elements with @p elem_size bytes each. * * If @p elem_size is CX_STORE_POINTERS, the created list will be created as if * cxListStorePointers() was called immediately after creation and the compare * function will be automatically set to cx_cmp_ptr(), if none is given. * * @param allocator the allocator for allocating the list memory * (if @c NULL, a default stdlib allocator will be used) * @param comparator the comparator for the elements * (if @c NULL, and the list is not storing pointers, sort and find * functions will not work) * @param elem_size the size of each element in bytes * @param initial_capacity the initial number of elements the array can store * @return the created list */ cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxListFree, 1) CxList *cxArrayListCreate( const CxAllocator *allocator, cx_compare_func comparator, size_t elem_size, size_t initial_capacity ); /** * Allocates an array list for storing elements with @p elem_size bytes each. * * The list will use the cxDefaultAllocator and @em NO compare function. * If you want to call functions that need a compare function, you have to * set it immediately after creation or use cxArrayListCreate(). * * If @p elem_size is CX_STORE_POINTERS, the created list will be created as if * cxListStorePointers() was called immediately after creation and the compare * function will be automatically set to cx_cmp_ptr(). * * @param elem_size (@c size_t) the size of each element in bytes * @param initial_capacity (@c size_t) the initial number of elements the array can store * @return the created list */ #define cxArrayListCreateSimple(elem_size, initial_capacity) \ cxArrayListCreate(NULL, NULL, elem_size, initial_capacity) #ifdef __cplusplus } // extern "C" #endif #endif // UCX_ARRAY_LIST_H