dbutils: comparison ucx/cx/array

-:80f9d007cb52
+:0aa8cbd7912e
 * POSSIBILITY OF SUCH DAMAGE.
 */
 /**
 * \file array_list.h
 * \brief Array list implementation.
-* \details Also provides several low-level functions for custom array list implementations.
 * \author Mike Becker
 * \author Olaf Wintermann
 * \copyright 2-Clause BSD License
 */
 #ifdef __cplusplus
 extern "C" {
 #endif
 /**
-* The maximum item size in an array list that fits into stack buffer when swapped.
+* The maximum item size in an array list that fits into stack buffer
-*/
+* when swapped.
-extern unsigned cx_array_swap_sbo_size;
+*/
+extern const unsigned cx_array_swap_sbo_size;
 /**
 * Declares variables for an array that can be used with the convenience macros.
+*
+* @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_simple_add()
 * @see cx_array_simple_copy()
 * @see cx_array_initialize()
-*/
+* @see cx_array_simple_add_sorted()
-#define CX_ARRAY_DECLARE(type, name) \
+* @see cx_array_simple_insert_sorted()
-type * name;                     \
+*/
-size_t name##_size;              \
+#define CX_ARRAY_DECLARE_SIZED(type, name, size_type) \
-size_t name##_capacity
+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 `size_t` type.
+* Use #CX_ARRAY_DECLARE_SIZED() to specify a different type.
+*
+* @param type the type of the data
+* @param name the name of the array
+*
+* @see cx_array_simple_add()
+* @see cx_array_simple_copy()
+* @see cx_array_initialize()
+* @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 declared with CX_ARRAY_DECLARE().
 *
 * The memory for the array is allocated with stdlib malloc().
 */
 #define cx_array_initialize(array, capacity) \
 array##_capacity = capacity; \
 array##_size = 0; \
 array = malloc(sizeof(array[0]) * capacity)
+/**
+* Initializes an array declared with CX_ARRAY_DECLARE().
+*
+* The memory for the array is allocated with the specified allocator.
+* @param allocator the allocator
+* @param array the array
+* @param capacity the initial capacity
+*/
+#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.
 */
 struct cx_array_reallocator_s {
 * @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
 */
 size_t int2;
 };
 /**
+* Typedef for the array reallocator struct.
+*/
+typedef struct cx_array_reallocator_s CxArrayReallocator;
+/**
 * A default stdlib-based array reallocator.
 */
 extern struct cx_array_reallocator_s *cx_array_default_reallocator;
 /**
-* Return codes for array functions.
+* Creates a new array reallocator.
-*/
+*
-enum cx_array_result {
+* When \p allocator is \c NULL, the stdlib default allocator will be used.
-CX_ARRAY_SUCCESS,
+*
-CX_ARRAY_REALLOC_NOT_SUPPORTED,
+* When \p stackmem is not \c NULL, the reallocator is supposed to be used
-CX_ARRAY_REALLOC_FAILED,
+* \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.
+*
+* @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
+* @return an array reallocator
+*/
+struct cx_array_reallocator_s 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.
+*
+* 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 refers to the size and capacity. Both must have the same width.
+* Supported are 0, 8, 16, and 32, as well as 64 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
+* @return zero on success, non-zero on failure
+*/
+cx_attr_nonnull
+int cx_array_reserve(
+void **array,
+void *size,
+void *capacity,
+unsigned width,
+size_t elem_size,
+size_t elem_count,
+struct cx_array_reallocator_s *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, and \p capacity is not \c NULL, the remaining
+* would extend the array's size, the remaining \p capacity is used.
-* capacity is used.
+*
-*
+* If the \p capacity is also insufficient to hold the new data, a reallocation
-* If the capacity is insufficient to hold the new data, a reallocation
+* attempt is made with the specified \p reallocator.
-* attempt is made, unless the \p reallocator is set to \c NULL, in which case
+*
-* this function ultimately returns a failure.
+* The \p width refers to the size and capacity. Both must have the same width.
+* Supported are 0, 8, 16, and 32, as well as 64 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 target array's capacity -
+* @param capacity a pointer to the capacity of the target array
-* \c NULL if only the size shall be used to bound the 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, or \c NULL
+* @param reallocator the array reallocator to use
-* if reallocation shall not happen
+* @return zero on success, non-zero on failure
-* @return zero on success, non-zero error code on failure
+*/
-*/
+cx_attr_nonnull
-enum cx_array_result cx_array_copy(
+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,
+struct cx_array_reallocator_s *reallocator
+);
+/**
+* Convenience macro that uses cx_array_copy() with a default layout and
+* the specified reallocator.
+*
+* @param reallocator the array reallocator to use
+* @param array the name of the array (NOT a pointer to the array)
+* @param index the index where the copied elements shall be placed
+* @param src the source array
+* @param count the number of elements to copy
+* @return zero on success, non-zero on 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), \
+8*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 to the array)
+* @param index the index where the copied elements shall be placed
+* @param src the source array
+* @param count the number of elements to copy
+* @return zero on success, non-zero on 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(cx_array_default_reallocator, \
+array, index, src, count)
+/**
+* Convenience macro that uses cx_array_reserve() with a default layout and
+* the specified reallocator.
+*
+* @param reallocator the array reallocator to use
+* @param array the name of the array (NOT a pointer to the array)
+* @param count the number of expected additional elements
+* @return zero on success, non-zero on 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), \
+8*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 to the array)
+* @param count the number of expected additional elements
+* @return zero on success, non-zero on failure
+* @see CX_ARRAY_DECLARE()
+* @see cx_array_simple_reserve_a()
+*/
+#define cx_array_simple_reserve(array, count) \
+cx_array_simple_reserve_a(cx_array_default_reallocator, \
+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.
+*
+* @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 elem_size the size of one element
+* @param elem a pointer to the element to add
+* @param reallocator the array reallocator to use
+* @return zero on success, non-zero on failure
+*/
+#define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \
+cx_array_copy((void**)(target), size, capacity, 8*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 the array reallocator to use
+* @param array the name of the array (NOT a pointer to the array)
+* @param elem the element to add (NOT a pointer, address is automatically taken)
+* @return zero on success, non-zero on 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 to the array)
+* @param elem the element to add (NOT a pointer, address is automatically taken)
+* @return zero on success, non-zero on 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.
+*
+* @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
+* @return zero on success, non-zero on failure
+*/
+cx_attr_nonnull
+int cx_array_insert_sorted(
 void **target,
 size_t *size,
 size_t *capacity,
-size_t index,
+cx_compare_func cmp_func,
-void const *src,
+const void *src,
 size_t elem_size,
 size_t elem_count,
 struct cx_array_reallocator_s *reallocator
-) __attribute__((__nonnull__(1, 2, 5)));
+);
 /**
-* Convenience macro that uses cx_array_copy() with a default layout and the default reallocator.
+* Inserts an element into a sorted array.
 *
-* @param array the name of the array (NOT a pointer to the array)
+* If the target array is not already sorted with respect
-* @param index the index where the copied elements shall be placed
+* to the specified \p cmp_func, the behavior is undefined.
-* @param src the source array
+*
-* @param count the number of elements to copy
+* If the capacity is insufficient to hold the new data, a reallocation
-*/
+* attempt is made.
-#define cx_array_simple_copy(array, index, src, count) \
-cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \
-index, src, sizeof((array)[0]), count, cx_array_default_reallocator)
-/**
-* 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 containing
-* \p size elements, already. The \p capacity must not be \c NULL and point a
-* variable holding the current maximum number of elements the array can hold.
-*
-* If the capacity is insufficient to hold the new element, and the optional
-* \p reallocator is not \c NULL, an attempt increase the \p capacity is made
-* and the new capacity is written back.
 *
 * @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 target array's capacity - must not be \c NULL
+* @param capacity a pointer to the capacity of the target array
 * @param elem_size the size of one element
 * @param elem a pointer to the element to add
-* @param reallocator the array reallocator to use, or \c NULL if reallocation shall not happen
+* @param reallocator the array reallocator to use
-* @return zero on success, non-zero error code on failure
+* @return zero on success, non-zero on failure
 */
-#define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \
+#define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \
-cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator)
+cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator)
 /**
-* Convenience macro that uses cx_array_add() with a default layout and the default reallocator.
+* Convenience macro for cx_array_add_sorted() with a default
-*
+* layout and the specified reallocator.
+*
+* @param reallocator the array reallocator to use
 * @param array the name of the array (NOT a pointer to the array)
 * @param elem the element to add (NOT a pointer, address is automatically taken)
-*/
+* @param cmp_func the compare function for the elements
-#define cx_array_simple_add(array, elem) \
+* @return zero on success, non-zero on failure
-cx_array_simple_copy(array, array##_size, &(elem), 1)
+* @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 to the array)
+* @param elem the element to add (NOT a pointer, address is automatically taken)
+* @param cmp_func the compare function for the elements
+* @return zero on success, non-zero on 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(cx_array_default_reallocator, array, elem, cmp_func)
+/**
+* Convenience macro for cx_array_insert_sorted() with a default
+* layout and the specified reallocator.
+*
+* @param reallocator the array reallocator to use
+* @param array the name of the array (NOT a pointer to the array)
+* @param src pointer to the source array
+* @param n number of elements in the source array
+* @param cmp_func the compare function for the elements
+* @return zero on success, non-zero on 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 to the array)
+* @param src pointer to the source array
+* @param n number of elements in the source array
+* @param cmp_func the compare function for the elements
+* @return zero on success, non-zero on 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(cx_array_default_reallocator, 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
+*/
+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
+*/
+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
+*/
+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
-) __attribute__((__nonnull__));
+);
 /**
 * 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 the cxDefaultAllocator will be used)
+* (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(
-CxAllocator const *allocator,
+const CxAllocator *allocator,
 cx_compare_func comparator,
 size_t elem_size,
 size_t initial_capacity
 );

comparison: ucx/cx/array_list.h

ucx/cx/array_list.h

Mercurial > hg > dbutils / file comparison

comparison: ucx/cx/array_list.h

ucx/cx/array_list.h