Thu, 14 Mar 2024 22:07:19 +0100
fix another superfluous semicolon...
universe@606 | 1 | /* |
universe@606 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
universe@606 | 3 | * |
universe@606 | 4 | * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. |
universe@606 | 5 | * |
universe@606 | 6 | * Redistribution and use in source and binary forms, with or without |
universe@606 | 7 | * modification, are permitted provided that the following conditions are met: |
universe@606 | 8 | * |
universe@606 | 9 | * 1. Redistributions of source code must retain the above copyright |
universe@606 | 10 | * notice, this list of conditions and the following disclaimer. |
universe@606 | 11 | * |
universe@606 | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
universe@606 | 13 | * notice, this list of conditions and the following disclaimer in the |
universe@606 | 14 | * documentation and/or other materials provided with the distribution. |
universe@606 | 15 | * |
universe@606 | 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
universe@606 | 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
universe@606 | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
universe@606 | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
universe@606 | 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
universe@606 | 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
universe@606 | 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
universe@606 | 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
universe@606 | 24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
universe@606 | 25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
universe@606 | 26 | * POSSIBILITY OF SUCH DAMAGE. |
universe@606 | 27 | */ |
universe@606 | 28 | /** |
universe@606 | 29 | * \file array_list.h |
universe@606 | 30 | * \brief Array list implementation. |
universe@606 | 31 | * \details Also provides several low-level functions for custom array list implementations. |
universe@606 | 32 | * \author Mike Becker |
universe@606 | 33 | * \author Olaf Wintermann |
universe@606 | 34 | * \copyright 2-Clause BSD License |
universe@606 | 35 | */ |
universe@606 | 36 | |
universe@606 | 37 | |
universe@606 | 38 | #ifndef UCX_ARRAY_LIST_H |
universe@606 | 39 | #define UCX_ARRAY_LIST_H |
universe@606 | 40 | |
olaf@617 | 41 | #include "list.h" |
universe@606 | 42 | |
universe@606 | 43 | #ifdef __cplusplus |
universe@606 | 44 | extern "C" { |
universe@606 | 45 | #endif |
universe@606 | 46 | |
universe@606 | 47 | /** |
universe@807 | 48 | * The maximum item size in an array list that fits into stack buffer when swapped. |
universe@804 | 49 | */ |
universe@807 | 50 | extern unsigned cx_array_swap_sbo_size; |
universe@804 | 51 | |
universe@804 | 52 | /** |
universe@831 | 53 | * Declares variables for an array that can be used with the convenience macros. |
universe@831 | 54 | * |
universe@831 | 55 | * @see cx_array_simple_add() |
universe@831 | 56 | * @see cx_array_simple_copy() |
universe@834 | 57 | * @see cx_array_initialize() |
universe@831 | 58 | */ |
universe@834 | 59 | #define CX_ARRAY_DECLARE(type, name) \ |
universe@831 | 60 | type * name; \ |
universe@831 | 61 | size_t name##_size; \ |
universe@844 | 62 | size_t name##_capacity |
universe@831 | 63 | |
universe@831 | 64 | /** |
universe@834 | 65 | * Initializes an array declared with CX_ARRAY_DECLARE(). |
universe@832 | 66 | * |
universe@832 | 67 | * The memory for the array is allocated with stdlib malloc(). |
universe@832 | 68 | * @param array the array |
universe@832 | 69 | * @param capacity the initial capacity |
universe@832 | 70 | */ |
universe@832 | 71 | #define cx_array_initialize(array, capacity) \ |
universe@832 | 72 | array##_capacity = capacity; \ |
universe@832 | 73 | array##_size = 0; \ |
universe@843 | 74 | array = malloc(sizeof(array[0]) * capacity) |
universe@832 | 75 | |
universe@832 | 76 | /** |
universe@608 | 77 | * Defines a reallocation mechanism for arrays. |
universe@608 | 78 | */ |
universe@608 | 79 | struct cx_array_reallocator_s { |
universe@608 | 80 | /** |
universe@831 | 81 | * Reallocates space for the given array. |
universe@608 | 82 | * |
universe@608 | 83 | * Implementations are not required to free the original array. |
universe@831 | 84 | * This allows reallocation of static memory by allocating heap memory |
universe@795 | 85 | * and copying the array contents. The information in the custom fields of |
universe@795 | 86 | * the referenced allocator can be used to track the state of the memory |
universe@795 | 87 | * or to transport other additional data. |
universe@608 | 88 | * |
universe@608 | 89 | * @param array the array to reallocate |
universe@608 | 90 | * @param capacity the new capacity (number of elements) |
universe@608 | 91 | * @param elem_size the size of each element |
universe@609 | 92 | * @param alloc a reference to this allocator |
universe@608 | 93 | * @return a pointer to the reallocated memory or \c NULL on failure |
universe@608 | 94 | */ |
universe@608 | 95 | void *(*realloc)( |
universe@608 | 96 | void *array, |
universe@608 | 97 | size_t capacity, |
universe@608 | 98 | size_t elem_size, |
universe@609 | 99 | struct cx_array_reallocator_s *alloc |
universe@608 | 100 | ); |
universe@608 | 101 | |
universe@608 | 102 | /** |
universe@609 | 103 | * Custom data pointer. |
universe@608 | 104 | */ |
universe@609 | 105 | void *ptr1; |
universe@609 | 106 | /** |
universe@609 | 107 | * Custom data pointer. |
universe@609 | 108 | */ |
universe@609 | 109 | void *ptr2; |
universe@609 | 110 | /** |
universe@609 | 111 | * Custom data integer. |
universe@609 | 112 | */ |
universe@609 | 113 | size_t int1; |
universe@609 | 114 | /** |
universe@609 | 115 | * Custom data integer. |
universe@609 | 116 | */ |
universe@609 | 117 | size_t int2; |
universe@608 | 118 | }; |
universe@608 | 119 | |
universe@608 | 120 | /** |
universe@817 | 121 | * A default stdlib-based array reallocator. |
universe@817 | 122 | */ |
universe@818 | 123 | extern struct cx_array_reallocator_s *cx_array_default_reallocator; |
universe@817 | 124 | |
universe@817 | 125 | /** |
universe@819 | 126 | * Return codes for array functions. |
universe@610 | 127 | */ |
universe@819 | 128 | enum cx_array_result { |
universe@819 | 129 | CX_ARRAY_SUCCESS, |
universe@819 | 130 | CX_ARRAY_REALLOC_NOT_SUPPORTED, |
universe@819 | 131 | CX_ARRAY_REALLOC_FAILED, |
universe@610 | 132 | }; |
universe@610 | 133 | |
universe@610 | 134 | /** |
universe@608 | 135 | * Copies elements from one array to another. |
universe@608 | 136 | * |
universe@608 | 137 | * The elements are copied to the \p target array at the specified \p index, |
universe@637 | 138 | * overwriting possible elements. The \p index does not need to be in range of |
universe@637 | 139 | * the current array \p size. If the new index plus the number of elements added |
universe@637 | 140 | * would extend the array's size, and \p capacity is not \c NULL, the remaining |
universe@637 | 141 | * capacity is used. |
universe@608 | 142 | * |
universe@608 | 143 | * If the capacity is insufficient to hold the new data, a reallocation |
universe@818 | 144 | * attempt is made, unless the \p reallocator is set to \c NULL, in which case |
universe@608 | 145 | * this function ultimately returns a failure. |
universe@608 | 146 | * |
universe@831 | 147 | * @param target a pointer to the target array |
universe@608 | 148 | * @param size a pointer to the size of the target array |
universe@608 | 149 | * @param capacity a pointer to the target array's capacity - |
universe@608 | 150 | * \c NULL if only the size shall be used to bound the array |
universe@608 | 151 | * @param index the index where the copied elements shall be placed |
universe@608 | 152 | * @param src the source array |
universe@608 | 153 | * @param elem_size the size of one element |
universe@608 | 154 | * @param elem_count the number of elements to copy |
universe@831 | 155 | * @param reallocator the array reallocator to use, or \c NULL |
universe@831 | 156 | * if reallocation shall not happen |
universe@610 | 157 | * @return zero on success, non-zero error code on failure |
universe@608 | 158 | */ |
universe@819 | 159 | enum cx_array_result cx_array_copy( |
universe@608 | 160 | void **target, |
universe@608 | 161 | size_t *size, |
universe@608 | 162 | size_t *capacity, |
universe@608 | 163 | size_t index, |
universe@608 | 164 | void const *src, |
universe@608 | 165 | size_t elem_size, |
universe@608 | 166 | size_t elem_count, |
universe@610 | 167 | struct cx_array_reallocator_s *reallocator |
universe@608 | 168 | ) __attribute__((__nonnull__(1, 2, 5))); |
universe@608 | 169 | |
universe@818 | 170 | /** |
universe@831 | 171 | * Convenience macro that uses cx_array_copy() with a default layout and the default reallocator. |
universe@831 | 172 | * |
universe@831 | 173 | * @param array the name of the array (NOT a pointer to the array) |
universe@831 | 174 | * @param index the index where the copied elements shall be placed |
universe@831 | 175 | * @param src the source array |
universe@831 | 176 | * @param count the number of elements to copy |
universe@831 | 177 | */ |
universe@831 | 178 | #define cx_array_simple_copy(array, index, src, count) \ |
universe@831 | 179 | cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ |
universe@831 | 180 | index, src, sizeof((array)[0]), count, cx_array_default_reallocator) |
universe@831 | 181 | |
universe@831 | 182 | /** |
universe@818 | 183 | * Adds an element to an array with the possibility of allocating more space. |
universe@818 | 184 | * |
universe@818 | 185 | * The element \p elem is added to the end of the \p target array which containing |
universe@818 | 186 | * \p size elements, already. The \p capacity must not be \c NULL and point a |
universe@818 | 187 | * variable holding the current maximum number of elements the array can hold. |
universe@818 | 188 | * |
universe@818 | 189 | * If the capacity is insufficient to hold the new element, and the optional |
universe@818 | 190 | * \p reallocator is not \c NULL, an attempt increase the \p capacity is made |
universe@818 | 191 | * and the new capacity is written back. |
universe@818 | 192 | * |
universe@831 | 193 | * @param target a pointer to the target array |
universe@818 | 194 | * @param size a pointer to the size of the target array |
universe@818 | 195 | * @param capacity a pointer to the target array's capacity - must not be \c NULL |
universe@818 | 196 | * @param elem_size the size of one element |
universe@832 | 197 | * @param elem a pointer to the element to add |
universe@831 | 198 | * @param reallocator the array reallocator to use, or \c NULL if reallocation shall not happen |
universe@818 | 199 | * @return zero on success, non-zero error code on failure |
universe@818 | 200 | */ |
universe@818 | 201 | #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \ |
universe@818 | 202 | cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator) |
universe@623 | 203 | |
universe@623 | 204 | /** |
universe@831 | 205 | * Convenience macro that uses cx_array_add() with a default layout and the default reallocator. |
universe@831 | 206 | * |
universe@831 | 207 | * @param array the name of the array (NOT a pointer to the array) |
universe@832 | 208 | * @param elem the element to add (NOT a pointer, address is automatically taken) |
universe@831 | 209 | */ |
universe@831 | 210 | #define cx_array_simple_add(array, elem) \ |
universe@832 | 211 | cx_array_simple_copy(array, array##_size, &(elem), 1) |
universe@831 | 212 | |
universe@831 | 213 | /** |
universe@623 | 214 | * Swaps two array elements. |
universe@623 | 215 | * |
universe@623 | 216 | * @param arr the array |
universe@623 | 217 | * @param elem_size the element size |
universe@623 | 218 | * @param idx1 index of first element |
universe@623 | 219 | * @param idx2 index of second element |
universe@623 | 220 | */ |
universe@623 | 221 | void cx_array_swap( |
universe@623 | 222 | void *arr, |
universe@623 | 223 | size_t elem_size, |
universe@623 | 224 | size_t idx1, |
universe@623 | 225 | size_t idx2 |
universe@623 | 226 | ) __attribute__((__nonnull__)); |
universe@623 | 227 | |
universe@608 | 228 | /** |
universe@606 | 229 | * Allocates an array list for storing elements with \p item_size bytes each. |
universe@606 | 230 | * |
universe@669 | 231 | * If \p item_size is CX_STORE_POINTERS, the created list will be created as if |
universe@763 | 232 | * cxListStorePointers() was called immediately after creation and the compare |
universe@763 | 233 | * function will be automatically set to cx_cmp_ptr(), if none is given. |
universe@669 | 234 | * |
universe@606 | 235 | * @param allocator the allocator for allocating the list memory |
universe@670 | 236 | * (if \c NULL the cxDefaultAllocator will be used) |
universe@606 | 237 | * @param comparator the comparator for the elements |
universe@763 | 238 | * (if \c NULL, and the list is not storing pointers, sort and find |
universe@763 | 239 | * functions will not work) |
universe@606 | 240 | * @param item_size the size of each element in bytes |
universe@606 | 241 | * @param initial_capacity the initial number of elements the array can store |
universe@606 | 242 | * @return the created list |
universe@606 | 243 | */ |
universe@606 | 244 | CxList *cxArrayListCreate( |
universe@606 | 245 | CxAllocator const *allocator, |
universe@677 | 246 | cx_compare_func comparator, |
universe@606 | 247 | size_t item_size, |
universe@606 | 248 | size_t initial_capacity |
universe@670 | 249 | ); |
universe@606 | 250 | |
universe@662 | 251 | /** |
universe@662 | 252 | * Allocates an array list for storing elements with \p item_size bytes each. |
universe@662 | 253 | * |
universe@662 | 254 | * The list will use the cxDefaultAllocator and \em NO compare function. |
universe@662 | 255 | * If you want to call functions that need a compare function, you have to |
universe@662 | 256 | * set it immediately after creation or use cxArrayListCreate(). |
universe@662 | 257 | * |
universe@669 | 258 | * If \p item_size is CX_STORE_POINTERS, the created list will be created as if |
universe@763 | 259 | * cxListStorePointers() was called immediately after creation and the compare |
universe@763 | 260 | * function will be automatically set to cx_cmp_ptr(). |
universe@669 | 261 | * |
universe@662 | 262 | * @param item_size the size of each element in bytes |
universe@662 | 263 | * @param initial_capacity the initial number of elements the array can store |
universe@662 | 264 | * @return the created list |
universe@662 | 265 | */ |
universe@670 | 266 | #define cxArrayListCreateSimple(item_size, initial_capacity) \ |
universe@670 | 267 | cxArrayListCreate(NULL, NULL, item_size, initial_capacity) |
universe@606 | 268 | |
universe@606 | 269 | #ifdef __cplusplus |
universe@628 | 270 | } // extern "C" |
universe@606 | 271 | #endif |
universe@606 | 272 | |
universe@628 | 273 | #endif // UCX_ARRAY_LIST_H |