Sun, 29 Sep 2024 14:40:43 +0200
allow find() member function to start in an arbitrary subtree
relates to #166
/* * 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. * \details Also provides several low-level functions for custom array list implementations. * \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 unsigned cx_array_swap_sbo_size; /** * Declares variables for an array that can be used with the convenience macros. * * @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) \ type * name; \ size_t name##_size; \ size_t name##_capacity /** * Initializes an array declared with CX_ARRAY_DECLARE(). * * The memory for the array is allocated with stdlib malloc(). * @param array the array * @param capacity the initial capacity */ #define cx_array_initialize(array, capacity) \ array##_capacity = capacity; \ array##_size = 0; \ array = malloc(sizeof(array[0]) * capacity) /** * Defines a reallocation mechanism for arrays. */ 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 */ 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; }; /** * A default stdlib-based array reallocator. */ extern struct cx_array_reallocator_s *cx_array_default_reallocator; /** * Return codes for array functions. */ enum cx_array_result { CX_ARRAY_SUCCESS, CX_ARRAY_REALLOC_NOT_SUPPORTED, CX_ARRAY_REALLOC_FAILED, }; /** * 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 * capacity is used. * * If the capacity is insufficient to hold the new data, a reallocation * attempt is made, unless the \p reallocator is set to \c NULL, in which case * this function ultimately returns a failure. * * @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 - * \c NULL if only the size shall be used to bound the array (reallocations * will NOT be supported in that case) * @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 * if reallocation shall not happen * @return zero on success, non-zero error code on failure */ __attribute__((__nonnull__(1, 2, 5))) enum cx_array_result cx_array_copy( void **target, size_t *size, size_t *capacity, 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 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 * @see CX_ARRAY_DECLARE() */ #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 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 * @return zero on success, non-zero error code on failure */ #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \ cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator) /** * 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) * @see CX_ARRAY_DECLARE() */ #define cx_array_simple_add(array, elem) \ cx_array_simple_copy(array, array##_size, &(elem), 1) /** * 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 target array's capacity * @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 error code on failure */ __attribute__((__nonnull__)) enum cx_array_result 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, struct cx_array_reallocator_s *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. * * @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 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 error code on 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 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 * @see CX_ARRAY_DECLARE() */ #define cx_array_simple_add_sorted(array, elem, cmp_func) \ cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \ sizeof((array)[0]), &(elem), cmp_func, cx_array_default_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 * @see CX_ARRAY_DECLARE() */ #define cx_array_simple_insert_sorted(array, src, n, cmp_func) \ cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \ cmp_func, src, sizeof((array)[0]), n, cx_array_default_reallocator) /** * 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 */ __attribute__((__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 */ __attribute__((__nonnull__)) static inline size_t cx_array_binary_search( const void *arr, size_t size, size_t elem_size, const void *elem, cx_compare_func cmp_func ) { size_t index = cx_array_binary_search_inf( arr, size, elem_size, elem, cmp_func ); if (index < size && cmp_func(((const char *) arr) + index * elem_size, elem) == 0) { return index; } else { return size; } } /** * 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 */ __attribute__((__nonnull__)) static inline 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 ) { size_t inf = cx_array_binary_search_inf(arr, size, elem_size, elem, cmp_func); if (inf == size) { // no infimum means, first element is supremum return 0; } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) { return inf; } else { return inf + 1; } } /** * 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 */ __attribute__((__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 the cxDefaultAllocator 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 */ 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 the size of each element in bytes * @param initial_capacity 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