Mercurial > hg > ucx / file revision

 /*

  * 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()

  */

 #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

  * @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

  */

 enum cx_array_result cx_array_copy(

         void **target,

         size_t *size,

         size_t *capacity,

         size_t index,

         void const *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.

  *

  * @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

  */

 #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)

  */

 #define cx_array_simple_add(array, elem) \

     cx_array_simple_copy(array, array##_size, &(elem), 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

  */

 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 item_size bytes each.

  *

  * If \p item_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 item_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(

         CxAllocator const *allocator,

         cx_compare_func comparator,

         size_t item_size,

         size_t initial_capacity

 );

 /**

  * Allocates an array list for storing elements with \p item_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 item_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 item_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(item_size, initial_capacity) \

     cxArrayListCreate(NULL, NULL, item_size, initial_capacity)

 #ifdef __cplusplus

 } // extern "C"

 #endif

 #endif // UCX_ARRAY_LIST_H