Sat, 10 Aug 2019 11:12:49 +0200
improves array append/prepend/set interface
universe@103 | 1 | /* |
universe@103 | 2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
universe@103 | 3 | * |
universe@334 | 4 | * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. |
universe@103 | 5 | * |
universe@103 | 6 | * Redistribution and use in source and binary forms, with or without |
universe@103 | 7 | * modification, are permitted provided that the following conditions are met: |
universe@103 | 8 | * |
universe@103 | 9 | * 1. Redistributions of source code must retain the above copyright |
universe@103 | 10 | * notice, this list of conditions and the following disclaimer. |
universe@103 | 11 | * |
universe@103 | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
universe@103 | 13 | * notice, this list of conditions and the following disclaimer in the |
universe@103 | 14 | * documentation and/or other materials provided with the distribution. |
universe@103 | 15 | * |
universe@103 | 16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
universe@103 | 17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
universe@103 | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
universe@103 | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
universe@103 | 20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
universe@103 | 21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
universe@103 | 22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
universe@103 | 23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
universe@103 | 24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
universe@103 | 25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
universe@103 | 26 | * POSSIBILITY OF SUCH DAMAGE. |
universe@4 | 27 | */ |
universe@123 | 28 | /** |
universe@334 | 29 | * Dynamically allocated array implementation. |
universe@123 | 30 | * |
universe@334 | 31 | * @file array.h |
universe@123 | 32 | * @author Mike Becker |
universe@123 | 33 | * @author Olaf Wintermann |
universe@123 | 34 | */ |
universe@4 | 35 | |
universe@334 | 36 | #ifndef UCX_ARRAY_H |
universe@334 | 37 | #define UCX_ARRAY_H |
universe@4 | 38 | |
universe@259 | 39 | #include "ucx.h" |
universe@259 | 40 | #include "allocator.h" |
universe@7 | 41 | |
universe@4 | 42 | #ifdef __cplusplus |
universe@4 | 43 | extern "C" { |
universe@4 | 44 | #endif |
universe@4 | 45 | |
universe@121 | 46 | /** |
universe@334 | 47 | * UCX array type. |
universe@121 | 48 | */ |
universe@334 | 49 | typedef struct { |
universe@334 | 50 | /** |
universe@334 | 51 | * The current capacity of the array. |
universe@334 | 52 | */ |
universe@334 | 53 | size_t capacity; |
universe@334 | 54 | /** |
universe@334 | 55 | * The actual number of elements in the array. |
universe@334 | 56 | */ |
universe@334 | 57 | size_t size; |
universe@334 | 58 | /** |
universe@334 | 59 | * The size of an individual element in bytes. |
universe@334 | 60 | */ |
universe@334 | 61 | size_t elemsize; |
universe@334 | 62 | /** |
universe@334 | 63 | * A pointer to the data. |
universe@334 | 64 | */ |
universe@334 | 65 | void* data; |
universe@334 | 66 | /** |
universe@334 | 67 | * The allocator used for the data. |
universe@334 | 68 | */ |
universe@334 | 69 | UcxAllocator* allocator; |
universe@334 | 70 | } UcxArray; |
universe@334 | 71 | |
universe@121 | 72 | |
universe@123 | 73 | /** |
universe@334 | 74 | * Creates a new UCX array with the given capacity and element size. |
universe@334 | 75 | * @param capacity the initial capacity |
universe@334 | 76 | * @param elemsize the element size |
universe@334 | 77 | * @return a new UCX array structure |
universe@123 | 78 | */ |
universe@334 | 79 | UcxArray ucx_array_new(size_t capacity, size_t elemsize); |
universe@146 | 80 | |
universe@129 | 81 | /** |
universe@334 | 82 | * Creates a new UCX array using the specified allocator. |
universe@334 | 83 | * |
universe@334 | 84 | * @param capacity the initial capacity |
universe@334 | 85 | * @param elemsize the element size |
universe@334 | 86 | * @param allocator the allocator to use |
universe@334 | 87 | * @return a new UCX array structure |
universe@129 | 88 | */ |
universe@334 | 89 | UcxArray ucx_array_new_a(size_t capacity, size_t elemsize, |
universe@334 | 90 | UcxAllocator* allocator); |
universe@4 | 91 | |
universe@128 | 92 | /** |
universe@334 | 93 | * Creates an shallow copy of an array. |
universe@128 | 94 | * |
universe@334 | 95 | * This function clones the specified array by using memcpy(). |
universe@128 | 96 | * |
universe@334 | 97 | * @param array the array to copy |
universe@334 | 98 | * @return the copy (may be an empty array on allocation errors) |
universe@128 | 99 | */ |
universe@334 | 100 | UcxArray ucx_array_clone(UcxArray array); |
universe@334 | 101 | |
universe@146 | 102 | |
universe@128 | 103 | /** |
universe@334 | 104 | * Compares two UCX arrays element-wise by using a compare function. |
universe@334 | 105 | * |
universe@334 | 106 | * Elements of the two specified arrays are compared by using the specified |
universe@123 | 107 | * compare function and the additional data. The type and content of this |
universe@123 | 108 | * additional data depends on the cmp_func() used. |
universe@123 | 109 | * |
universe@334 | 110 | * This function always returns zero, if the element sizes of the arrays do |
universe@334 | 111 | * not match and performs no comparisons in this case. |
universe@123 | 112 | * |
universe@334 | 113 | * @param array1 the first array |
universe@334 | 114 | * @param array2 the second array |
universe@123 | 115 | * @param cmpfnc the compare function |
universe@123 | 116 | * @param data additional data for the compare function |
universe@334 | 117 | * @return 1, if and only if the two arrays equal element-wise, 0 otherwise |
universe@123 | 118 | */ |
universe@334 | 119 | int ucx_array_equals(UcxArray array1, UcxArray array2, |
universe@123 | 120 | cmp_func cmpfnc, void* data); |
universe@4 | 121 | |
universe@123 | 122 | /** |
universe@334 | 123 | * Destroys the array. |
universe@123 | 124 | * |
universe@334 | 125 | * The data is freed and both capacity and count are reset to zero. |
universe@334 | 126 | * If the array structure itself has been dynamically allocated, it has to be |
universe@334 | 127 | * freed separately. |
universe@123 | 128 | * |
universe@353 | 129 | * @param array the array to destroy |
universe@123 | 130 | */ |
universe@353 | 131 | void ucx_array_destroy(UcxArray *array); |
universe@146 | 132 | |
universe@128 | 133 | /** |
universe@354 | 134 | * Inserts elements at the end of the array. |
universe@354 | 135 | * |
universe@354 | 136 | * This is an O(1) operation. |
universe@354 | 137 | * The array will automatically grow, if the capacity is exceeded. |
universe@354 | 138 | * If a pointer to data is provided, the data is copied into the array with |
universe@354 | 139 | * memcpy(). Otherwise the new elements are completely zeroed. |
universe@354 | 140 | * |
universe@354 | 141 | * @param array a pointer the array where to append the data |
universe@354 | 142 | * @param data a pointer to the data to insert (may be <code>NULL</code>) |
universe@354 | 143 | * @param count number of elements to copy from data (if data is |
universe@354 | 144 | * <code>NULL</code>, zeroed elements are appended) |
universe@354 | 145 | * @return zero on success, non-zero if a reallocation was necessary but failed |
universe@354 | 146 | * @see ucx_array_set_from() |
universe@354 | 147 | * @see ucx_array_append() |
universe@354 | 148 | */ |
universe@354 | 149 | int ucx_array_append_from(UcxArray *array, void *data, size_t count); |
universe@354 | 150 | |
universe@354 | 151 | |
universe@354 | 152 | /** |
universe@354 | 153 | * Inserts elements at the beginning of the array. |
universe@354 | 154 | * |
universe@354 | 155 | * This is an expensive operation, because the contents must be moved. |
universe@354 | 156 | * If there is no particular reason to prepend data, you should use |
universe@354 | 157 | * ucx_array_append_from() instead. |
universe@354 | 158 | * |
universe@354 | 159 | * @param array a pointer the array where to prepend the data |
universe@354 | 160 | * @param data a pointer to the data to insert (may be <code>NULL</code>) |
universe@354 | 161 | * @param count number of elements to copy from data (if data is |
universe@354 | 162 | * <code>NULL</code>, zeroed elements are inserted) |
universe@354 | 163 | * @return zero on success, non-zero if a reallocation was necessary but failed |
universe@354 | 164 | * @see ucx_array_append_from() |
universe@354 | 165 | * @see ucx_array_set_from() |
universe@354 | 166 | * @see ucx_array_prepend() |
universe@354 | 167 | */ |
universe@354 | 168 | int ucx_array_prepend_from(UcxArray *array, void *data, size_t count); |
universe@354 | 169 | |
universe@354 | 170 | |
universe@354 | 171 | /** |
universe@354 | 172 | * Sets elements starting at the specified index. |
universe@354 | 173 | * |
universe@354 | 174 | * If the any index is out of bounds, the array automatically grows. |
universe@354 | 175 | * The pointer to the data may be NULL, in which case the elements are zeroed. |
universe@354 | 176 | * |
universe@354 | 177 | * @param array a pointer the array where to set the data |
universe@354 | 178 | * @param index the index of the element to set |
universe@354 | 179 | * @param data a pointer to the data to insert (may be <code>NULL</code>) |
universe@354 | 180 | * @param count number of elements to copy from data (if data is |
universe@354 | 181 | * <code>NULL</code>, the memory in the array is zeroed) |
universe@354 | 182 | * @return zero on success, non-zero if a reallocation was necessary but failed |
universe@354 | 183 | * @see ucx_array_append_from() |
universe@354 | 184 | * @see ucx_array_set() |
universe@354 | 185 | */ |
universe@354 | 186 | int ucx_array_set_from(UcxArray *array, size_t index, void *data, size_t count); |
universe@354 | 187 | |
universe@354 | 188 | /** |
universe@334 | 189 | * Inserts an element at the end of the array. |
universe@128 | 190 | * |
universe@334 | 191 | * This is an O(1) operation. |
universe@334 | 192 | * The array will automatically grow, if the capacity is exceeded. |
universe@354 | 193 | * If the type of the argument has a different size than the element size of |
universe@354 | 194 | * this array, the behavior is undefined. |
universe@128 | 195 | * |
universe@334 | 196 | * @param array a pointer the array where to append the data |
universe@354 | 197 | * @param elem the value to insert |
universe@334 | 198 | * @return zero on success, non-zero if a reallocation was necessary but failed |
universe@354 | 199 | * @see ucx_array_append_from() |
universe@354 | 200 | * @see ucx_array_set() |
universe@128 | 201 | */ |
universe@354 | 202 | #define ucx_array_append(array, elem) ucx_array_appendv(array, elem) |
universe@354 | 203 | |
universe@354 | 204 | /** |
universe@354 | 205 | * For internal use. |
universe@354 | 206 | * Use ucx_array_append() |
universe@354 | 207 | * |
universe@354 | 208 | * @param array |
universe@354 | 209 | * @param ... |
universe@354 | 210 | * @return |
universe@354 | 211 | * @see ucx_array_append() |
universe@354 | 212 | */ |
universe@354 | 213 | int ucx_array_appendv(UcxArray *array, ...); |
universe@334 | 214 | |
universe@146 | 215 | |
universe@128 | 216 | /** |
universe@334 | 217 | * Inserts an element at the beginning of the array. |
universe@211 | 218 | * |
universe@334 | 219 | * This is an expensive operation, because the contents must be moved. |
universe@334 | 220 | * If there is no particular reason to prepend data, you should use |
universe@334 | 221 | * ucx_array_append() instead. |
universe@211 | 222 | * |
universe@334 | 223 | * @param array a pointer the array where to prepend the data |
universe@354 | 224 | * @param elem the value to insert |
universe@334 | 225 | * @return zero on success, non-zero if a reallocation was necessary but failed |
universe@354 | 226 | * @see ucx_array_append() |
universe@354 | 227 | * @see ucx_array_set_from() |
universe@354 | 228 | * @see ucx_array_prepend_from() |
universe@211 | 229 | */ |
universe@354 | 230 | #define ucx_array_prepend(array, elem) ucx_array_prependv(array, elem) |
universe@354 | 231 | |
universe@354 | 232 | /** |
universe@354 | 233 | * For internal use. |
universe@354 | 234 | * Use ucx_array_prepend() |
universe@354 | 235 | * |
universe@354 | 236 | * @param array |
universe@354 | 237 | * @param ... |
universe@354 | 238 | * @return |
universe@354 | 239 | * @see ucx_array_prepend() |
universe@354 | 240 | */ |
universe@354 | 241 | int ucx_array_prependv(UcxArray *array, ...); |
universe@211 | 242 | |
universe@337 | 243 | |
universe@337 | 244 | /** |
universe@337 | 245 | * Sets an element at the specified index. |
universe@337 | 246 | * |
universe@354 | 247 | * If the any index is out of bounds, the array automatically grows. |
universe@337 | 248 | * |
universe@337 | 249 | * @param array a pointer the array where to set the data |
universe@337 | 250 | * @param index the index of the element to set |
universe@354 | 251 | * @param elem the value to set |
universe@337 | 252 | * @return zero on success, non-zero if a reallocation was necessary but failed |
universe@354 | 253 | * @see ucx_array_append() |
universe@354 | 254 | * @see ucx_array_set_from() |
universe@337 | 255 | */ |
universe@354 | 256 | #define ucx_array_set(array, index, elem) ucx_array_setv(array, index, elem) |
universe@354 | 257 | |
universe@354 | 258 | /** |
universe@354 | 259 | * For internal use. |
universe@354 | 260 | * Use ucx_array_set() |
universe@354 | 261 | * |
universe@354 | 262 | * @param array |
universe@354 | 263 | * @param index |
universe@354 | 264 | * @param ... |
universe@354 | 265 | * @return |
universe@354 | 266 | * @see ucx_array_set() |
universe@354 | 267 | */ |
universe@354 | 268 | int ucx_array_setv(UcxArray *array, size_t index, ...); |
universe@337 | 269 | |
universe@211 | 270 | /** |
universe@334 | 271 | * Concatenates two arrays. |
universe@128 | 272 | * |
universe@334 | 273 | * The contents of the second array are appended to the first array in one |
universe@334 | 274 | * single operation. The second array is otherwise left untouched. |
universe@128 | 275 | * |
universe@334 | 276 | * The first array may grow automatically. If this fails, both arrays remain |
universe@334 | 277 | * unmodified. |
universe@334 | 278 | * |
universe@334 | 279 | * @param array1 first array |
universe@334 | 280 | * @param array2 second array |
universe@334 | 281 | * @return zero on success, non-zero if reallocation was necessary but failed |
universe@334 | 282 | * or the element size does not match |
universe@128 | 283 | */ |
universe@334 | 284 | int ucx_array_concat(UcxArray *array1, const UcxArray *array2); |
universe@146 | 285 | |
universe@128 | 286 | /** |
universe@334 | 287 | * Returns a pointer to the array element at the specified index. |
universe@128 | 288 | * |
universe@334 | 289 | * @param array the array to retrieve the element from |
universe@334 | 290 | * @param index index of the element to return |
universe@334 | 291 | * @return a pointer to the element at the specified index or <code>NULL</code>, |
universe@334 | 292 | * if the index is greater than the array size |
universe@128 | 293 | */ |
universe@334 | 294 | void *ucx_array_at(UcxArray array, size_t index); |
universe@291 | 295 | |
universe@291 | 296 | /** |
universe@128 | 297 | * Returns the index of an element containing the specified data. |
universe@128 | 298 | * |
universe@128 | 299 | * This function uses a cmp_func() to compare the data of each list element |
universe@334 | 300 | * with the specified data. If no cmp_func is provided, memcmp() is used. |
universe@128 | 301 | * |
universe@334 | 302 | * If the array contains the data more than once, the index of the first |
universe@128 | 303 | * occurrence is returned. |
universe@334 | 304 | * If the array does not contain the data, the size of array is returned. |
universe@128 | 305 | * |
universe@334 | 306 | * @param array the array where to search for the data |
universe@128 | 307 | * @param elem the element data |
universe@128 | 308 | * @param cmpfnc the compare function |
universe@128 | 309 | * @param data additional data for the compare function |
universe@334 | 310 | * @return the index of the element containing the specified data or the size of |
universe@334 | 311 | * the array, if the data is not found in this array |
universe@128 | 312 | */ |
universe@334 | 313 | size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data); |
universe@146 | 314 | |
universe@128 | 315 | /** |
universe@334 | 316 | * Checks, if an array contains a specific element. |
universe@128 | 317 | * |
universe@334 | 318 | * An element is found, if ucx_array_find() returns a value less than the size. |
universe@128 | 319 | * |
universe@334 | 320 | * @param array the array where to search for the data |
universe@128 | 321 | * @param elem the element data |
universe@128 | 322 | * @param cmpfnc the compare function |
universe@128 | 323 | * @param data additional data for the compare function |
universe@334 | 324 | * @return 1, if and only if the array contains the specified element data |
universe@334 | 325 | * @see ucx_array_find() |
universe@128 | 326 | */ |
universe@334 | 327 | int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data); |
universe@35 | 328 | |
universe@128 | 329 | /** |
universe@342 | 330 | * Sorts a UcxArray with the best available sort algorithm. |
universe@128 | 331 | * |
universe@345 | 332 | * The qsort_r() function is used, if available (glibc, FreeBSD or MacOS). |
universe@345 | 333 | * The order of arguments is automatically adjusted for the FreeBSD and MacOS |
universe@345 | 334 | * version of qsort_r(). |
universe@345 | 335 | * |
universe@345 | 336 | * If qsort_r() is not available, a merge sort algorithm is used, which is |
universe@345 | 337 | * guaranteed to use no more additional memory than for exactly one element. |
universe@128 | 338 | * |
universe@339 | 339 | * @param array the array to sort |
universe@128 | 340 | * @param cmpfnc the function that shall be used to compare the element data |
universe@343 | 341 | * @param data additional data for the cmp_func() or <code>NULL</code> |
universe@128 | 342 | */ |
universe@336 | 343 | void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data); |
universe@123 | 344 | |
universe@124 | 345 | /** |
universe@334 | 346 | * Removes an element from the array. |
universe@124 | 347 | * |
universe@334 | 348 | * This is in general an expensive operation, because several elements may |
universe@334 | 349 | * be moved. If the order of the elements is not relevant, use |
universe@334 | 350 | * ucx_array_remove_fast() instead. |
universe@124 | 351 | * |
universe@334 | 352 | * @param array pointer to the array from which the element shall be removed |
universe@334 | 353 | * @param index the index of the element to remove |
universe@124 | 354 | */ |
universe@334 | 355 | void ucx_array_remove(UcxArray *array, size_t index); |
universe@146 | 356 | |
universe@128 | 357 | /** |
universe@334 | 358 | * Removes an element from the array. |
universe@128 | 359 | * |
universe@334 | 360 | * This is an O(1) operation, but does not maintain the order of the elements. |
universe@334 | 361 | * The last element in the array is moved to the location of the removed |
universe@334 | 362 | * element. |
universe@128 | 363 | * |
universe@334 | 364 | * @param array pointer to the array from which the element shall be removed |
universe@334 | 365 | * @param index the index of the element to remove |
universe@128 | 366 | */ |
universe@334 | 367 | void ucx_array_remove_fast(UcxArray *array, size_t index); |
universe@334 | 368 | |
universe@334 | 369 | /** |
universe@334 | 370 | * Shrinks the memory to exactly fit the contents. |
universe@334 | 371 | * |
universe@334 | 372 | * After this operation, the capacity equals the size. |
universe@334 | 373 | * |
universe@334 | 374 | * @param array a pointer to the array |
universe@334 | 375 | * @return zero on success, non-zero if reallocation failed |
universe@334 | 376 | */ |
universe@334 | 377 | int ucx_array_shrink(UcxArray* array); |
universe@334 | 378 | |
universe@334 | 379 | /** |
universe@334 | 380 | * Sets the capacity of the array. |
universe@334 | 381 | * |
universe@334 | 382 | * If the new capacity is smaller than the size of the array, the elements |
universe@334 | 383 | * are removed and the size is adjusted accordingly. |
universe@334 | 384 | * |
universe@334 | 385 | * @param array a pointer to the array |
universe@334 | 386 | * @param capacity the new capacity |
universe@334 | 387 | * @return zero on success, non-zero if reallocation failed |
universe@334 | 388 | */ |
universe@334 | 389 | int ucx_array_resize(UcxArray* array, size_t capacity); |
universe@334 | 390 | |
universe@334 | 391 | /** |
universe@334 | 392 | * Resizes the array only, if the capacity is insufficient. |
universe@334 | 393 | * |
universe@334 | 394 | * If the requested capacity is smaller than the current capacity, this |
universe@334 | 395 | * function does nothing. |
universe@334 | 396 | * |
universe@334 | 397 | * @param array a pointer to the array |
universe@334 | 398 | * @param capacity the guaranteed capacity |
universe@334 | 399 | * @return zero on success, non-zero if reallocation failed |
universe@334 | 400 | */ |
universe@334 | 401 | int ucx_array_reserve(UcxArray* array, size_t capacity); |
universe@334 | 402 | |
universe@334 | 403 | |
universe@4 | 404 | |
universe@4 | 405 | #ifdef __cplusplus |
universe@4 | 406 | } |
universe@4 | 407 | #endif |
universe@4 | 408 | |
universe@334 | 409 | #endif /* UCX_ARRAY_H */ |
universe@4 | 410 |