ucx/array_list.c

   1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   3  *
   4  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are met:
   8  *
   9  *   1. Redistributions of source code must retain the above copyright
  10  *      notice, this list of conditions and the following disclaimer.
  11  *
  12  *   2. Redistributions in binary form must reproduce the above copyright
  13  *      notice, this list of conditions and the following disclaimer in the
  14  *      documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26  * POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include "cx/array_list.h"
  30 #include <assert.h>
  31 #include <string.h>
  32
  33 // LOW LEVEL ARRAY LIST FUNCTIONS
  34
  35 enum cx_array_copy_result cx_array_copy(
  36         void **target,
  37         size_t *size,
  38         size_t *capacity,
  39         size_t index,
  40         void const *src,
  41         size_t elem_size,
  42         size_t elem_count,
  43         struct cx_array_reallocator_s *reallocator
  44 ) {
  45     // assert pointers
  46     assert(target != NULL);
  47     assert(size != NULL);
  48     assert(src != NULL);
  49
  50     // determine capacity
  51     size_t cap = capacity == NULL ? *size : *capacity;
  52
  53     // check if resize is required
  54     size_t minsize = index + elem_count;
  55     size_t newsize = *size < minsize ? minsize : *size;
  56     bool needrealloc = newsize > cap;
  57
  58     // reallocate if possible
  59     if (needrealloc) {
  60         // a reallocator and a capacity variable must be available
  61         if (reallocator == NULL || capacity == NULL) {
  62             return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED;
  63         }
  64
  65         // check, if we need to repair the src pointer
  66         uintptr_t targetaddr = (uintptr_t) *target;
  67         uintptr_t srcaddr = (uintptr_t) src;
  68         bool repairsrc = targetaddr <= srcaddr
  69                          && srcaddr < targetaddr + cap * elem_size;
  70
  71         // calculate new capacity (next number divisible by 16)
  72         cap = newsize - (newsize % 16) + 16;
  73         assert(cap > newsize);
  74
  75         // perform reallocation
  76         void *newmem = reallocator->realloc(
  77                 *target, cap, elem_size, reallocator
  78         );
  79         if (newmem == NULL) {
  80             return CX_ARRAY_COPY_REALLOC_FAILED;
  81         }
  82
  83         // repair src pointer, if necessary
  84         if (repairsrc) {
  85             src = ((char *) newmem) + (srcaddr - targetaddr);
  86         }
  87
  88         // store new pointer and capacity
  89         *target = newmem;
  90         *capacity = cap;
  91     }
  92
  93     // determine target pointer
  94     char *start = *target;
  95     start += index * elem_size;
  96
  97     // copy elements and set new size
  98     memmove(start, src, elem_count * elem_size);
  99     *size = newsize;
 100
 101     // return successfully
 102     return CX_ARRAY_COPY_SUCCESS;
 103 }
 104
 105 #ifndef CX_ARRAY_SWAP_SBO_SIZE
 106 #define CX_ARRAY_SWAP_SBO_SIZE 512
 107 #endif
 108
 109 void cx_array_swap(
 110         void *arr,
 111         size_t elem_size,
 112         size_t idx1,
 113         size_t idx2
 114 ) {
 115     assert(arr != NULL);
 116
 117     // short circuit
 118     if (idx1 == idx2) return;
 119
 120     char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
 121     void *tmp;
 122
 123     // decide if we can use the local buffer
 124     if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
 125         tmp = malloc(elem_size);
 126         // we don't want to enforce error handling
 127         if (tmp == NULL) abort();
 128     } else {
 129         tmp = sbo_mem;
 130     }
 131
 132     // calculate memory locations
 133     char *left = arr, *right = arr;
 134     left += idx1 * elem_size;
 135     right += idx2 * elem_size;
 136
 137     // three-way swap
 138     memcpy(tmp, left, elem_size);
 139     memcpy(left, right, elem_size);
 140     memcpy(right, tmp, elem_size);
 141
 142     // free dynamic memory, if it was needed
 143     if (tmp != sbo_mem) {
 144         free(tmp);
 145     }
 146 }
 147
 148 // HIGH LEVEL ARRAY LIST FUNCTIONS
 149
 150 typedef struct {
 151     struct cx_list_s base;
 152     void *data;
 153     struct cx_array_reallocator_s reallocator;
 154 } cx_array_list;
 155
 156 static void *cx_arl_realloc(
 157         void *array,
 158         size_t capacity,
 159         size_t elem_size,
 160         struct cx_array_reallocator_s *alloc
 161 ) {
 162     // retrieve the pointer to the list allocator
 163     CxAllocator const *al = alloc->ptr1;
 164
 165     // use the list allocator to reallocate the memory
 166     return cxRealloc(al, array, capacity * elem_size);
 167 }
 168
 169 static void cx_arl_destructor(struct cx_list_s *list) {
 170     cx_array_list *arl = (cx_array_list *) list;
 171     cxFree(list->allocator, arl->data);
 172 }
 173
 174 static size_t cx_arl_insert_array(
 175         struct cx_list_s *list,
 176         size_t index,
 177         void const *array,
 178         size_t n
 179 ) {
 180     // out of bounds and special case check
 181     if (index > list->size || n == 0) return 0;
 182
 183     // get a correctly typed pointer to the list
 184     cx_array_list *arl = (cx_array_list *) list;
 185
 186     // do we need to move some elements?
 187     if (index < list->size) {
 188         char const *first_to_move = (char const *) arl->data;
 189         first_to_move += index * list->itemsize;
 190         size_t elems_to_move = list->size - index;
 191         size_t start_of_moved = index + n;
 192
 193         if (CX_ARRAY_COPY_SUCCESS != cx_array_copy(
 194                 &arl->data,
 195                 &list->size,
 196                 &list->capacity,
 197                 start_of_moved,
 198                 first_to_move,
 199                 list->itemsize,
 200                 elems_to_move,
 201                 &arl->reallocator
 202         )) {
 203             // if moving existing elems is unsuccessful, abort
 204             return 0;
 205         }
 206     }
 207
 208     // note that if we had to move the elements, the following operation
 209     // is guaranteed to succeed, because we have the memory already allocated
 210     // therefore, it is impossible to leave this function with an invalid array
 211
 212     // place the new elements
 213     if (CX_ARRAY_COPY_SUCCESS == cx_array_copy(
 214             &arl->data,
 215             &list->size,
 216             &list->capacity,
 217             index,
 218             array,
 219             list->itemsize,
 220             n,
 221             &arl->reallocator
 222     )) {
 223         return n;
 224     } else {
 225         // array list implementation is "all or nothing"
 226         return 0;
 227     }
 228 }
 229
 230 static int cx_arl_insert_element(
 231         struct cx_list_s *list,
 232         size_t index,
 233         void const *element
 234 ) {
 235     return 1 != cx_arl_insert_array(list, index, element, 1);
 236 }
 237
 238 static int cx_arl_insert_iter(
 239         struct cx_mut_iterator_s *iter,
 240         void const *elem,
 241         int prepend
 242 ) {
 243     struct cx_list_s *list = iter->src_handle;
 244     if (iter->index < list->size) {
 245         int result = cx_arl_insert_element(
 246                 list,
 247                 iter->index + 1 - prepend,
 248                 elem
 249         );
 250         if (result == 0 && prepend != 0) {
 251             iter->index++;
 252             iter->elem_handle = ((char *) iter->elem_handle) + list->itemsize;
 253         }
 254         return result;
 255     } else {
 256         int result = cx_arl_insert_element(list, list->size, elem);
 257         iter->index = list->size;
 258         return result;
 259     }
 260 }
 261
 262 static int cx_arl_remove(
 263         struct cx_list_s *list,
 264         size_t index
 265 ) {
 266     cx_array_list *arl = (cx_array_list *) list;
 267
 268     // out-of-bounds check
 269     if (index >= list->size) {
 270         return 1;
 271     }
 272
 273     // content destruction
 274     if (list->content_destructor_type != CX_DESTRUCTOR_NONE) {
 275         char *ptr = arl->data;
 276         ptr += index * list->itemsize;
 277         cx_list_invoke_destructor(list, ptr);
 278     }
 279
 280     // short-circuit removal of last element
 281     if (index == list->size - 1) {
 282         list->size--;
 283         return 0;
 284     }
 285
 286     // just move the elements starting at index to the left
 287     int result = cx_array_copy(
 288             &arl->data,
 289             &list->size,
 290             &list->capacity,
 291             index,
 292             ((char *) arl->data) + (index + 1) * list->itemsize,
 293             list->itemsize,
 294             list->size - index - 1,
 295             &arl->reallocator
 296     );
 297     if (result == 0) {
 298         // decrease the size
 299         list->size--;
 300     }
 301     return result;
 302 }
 303
 304 static void cx_arl_clear(struct cx_list_s *list) {
 305     if (list->size == 0) return;
 306
 307     cx_array_list *arl = (cx_array_list *) list;
 308     char *ptr = arl->data;
 309
 310     switch (list->content_destructor_type) {
 311         case CX_DESTRUCTOR_SIMPLE: {
 312             for (size_t i = 0; i < list->size; i++) {
 313                 cx_list_invoke_simple_destructor(list, ptr);
 314                 ptr += list->itemsize;
 315             }
 316             break;
 317         }
 318         case CX_DESTRUCTOR_ADVANCED: {
 319             for (size_t i = 0; i < list->size; i++) {
 320                 cx_list_invoke_advanced_destructor(list, ptr);
 321                 ptr += list->itemsize;
 322             }
 323             break;
 324         }
 325         case CX_DESTRUCTOR_NONE:
 326             break; // nothing
 327     }
 328
 329     memset(arl->data, 0, list->size * list->itemsize);
 330     list->size = 0;
 331 }
 332
 333 static int cx_arl_swap(
 334         struct cx_list_s *list,
 335         size_t i,
 336         size_t j
 337 ) {
 338     if (i >= list->size || j >= list->size) return 1;
 339     cx_array_list *arl = (cx_array_list *) list;
 340     cx_array_swap(arl->data, list->itemsize, i, j);
 341     return 0;
 342 }
 343
 344 static void *cx_arl_at(
 345         struct cx_list_s const *list,
 346         size_t index
 347 ) {
 348     if (index < list->size) {
 349         cx_array_list const *arl = (cx_array_list const *) list;
 350         char *space = arl->data;
 351         return space + index * list->itemsize;
 352     } else {
 353         return NULL;
 354     }
 355 }
 356
 357 static size_t cx_arl_find(
 358         struct cx_list_s const *list,
 359         void const *elem
 360 ) {
 361     assert(list->cmpfunc != NULL);
 362     char *cur = ((cx_array_list const *) list)->data;
 363
 364     for (size_t i = 0; i < list->size; i++) {
 365         if (0 == list->cmpfunc(elem, cur)) {
 366             return i;
 367         }
 368         cur += list->itemsize;
 369     }
 370
 371     return list->size;
 372 }
 373
 374 static void cx_arl_sort(struct cx_list_s *list) {
 375     assert(list->cmpfunc != NULL);
 376     qsort(((cx_array_list *) list)->data,
 377           list->size,
 378           list->itemsize,
 379           list->cmpfunc
 380     );
 381 }
 382
 383 static int cx_arl_compare(
 384         struct cx_list_s const *list,
 385         struct cx_list_s const *other
 386 ) {
 387     assert(list->cmpfunc != NULL);
 388     if (list->size == other->size) {
 389         char const *left = ((cx_array_list const *) list)->data;
 390         char const *right = ((cx_array_list const *) other)->data;
 391         for (size_t i = 0; i < list->size; i++) {
 392             int d = list->cmpfunc(left, right);
 393             if (d != 0) {
 394                 return d;
 395             }
 396             left += list->itemsize;
 397             right += other->itemsize;
 398         }
 399         return 0;
 400     } else {
 401         return list->size < other->size ? -1 : 1;
 402     }
 403 }
 404
 405 static void cx_arl_reverse(struct cx_list_s *list) {
 406     if (list->size < 2) return;
 407     void *data = ((cx_array_list const *) list)->data;
 408     size_t half = list->size / 2;
 409     for (size_t i = 0; i < half; i++) {
 410         cx_array_swap(data, list->itemsize, i, list->size - 1 - i);
 411     }
 412 }
 413
 414 static bool cx_arl_iter_valid(void const *it) {
 415     struct cx_iterator_s const *iter = it;
 416     struct cx_list_s const *list = iter->src_handle;
 417     return iter->index < list->size;
 418 }
 419
 420 static void *cx_arl_iter_current(void const *it) {
 421     struct cx_iterator_s const *iter = it;
 422     return iter->elem_handle;
 423 }
 424
 425 static void cx_arl_iter_next(void *it) {
 426     struct cx_iterator_base_s *itbase = it;
 427     if (itbase->remove) {
 428         struct cx_mut_iterator_s *iter = it;
 429         itbase->remove = false;
 430         cx_arl_remove(iter->src_handle, iter->index);
 431     } else {
 432         struct cx_iterator_s *iter = it;
 433         iter->index++;
 434         iter->elem_handle =
 435                 ((char *) iter->elem_handle)
 436                 + ((struct cx_list_s const *) iter->src_handle)->itemsize;
 437     }
 438 }
 439
 440 static void cx_arl_iter_prev(void *it) {
 441     struct cx_iterator_base_s *itbase = it;
 442     struct cx_mut_iterator_s *iter = it;
 443     cx_array_list *const list = iter->src_handle;
 444     if (itbase->remove) {
 445         itbase->remove = false;
 446         cx_arl_remove(iter->src_handle, iter->index);
 447     }
 448     iter->index--;
 449     if (iter->index < list->base.size) {
 450         iter->elem_handle = ((char *) list->data)
 451                             + iter->index * list->base.itemsize;
 452     }
 453 }
 454
 455 static bool cx_arl_iter_flag_rm(void *it) {
 456     struct cx_iterator_base_s *iter = it;
 457     if (iter->mutating) {
 458         iter->remove = true;
 459         return true;
 460     } else {
 461         return false;
 462     }
 463 }
 464
 465 static struct cx_iterator_s cx_arl_iterator(
 466         struct cx_list_s const *list,
 467         size_t index,
 468         bool backwards
 469 ) {
 470     struct cx_iterator_s iter;
 471
 472     iter.index = index;
 473     iter.src_handle = list;
 474     iter.elem_handle = cx_arl_at(list, index);
 475     iter.base.valid = cx_arl_iter_valid;
 476     iter.base.current = cx_arl_iter_current;
 477     iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
 478     iter.base.flag_removal = cx_arl_iter_flag_rm;
 479     iter.base.remove = false;
 480     iter.base.mutating = false;
 481
 482     return iter;
 483 }
 484
 485 static cx_list_class cx_array_list_class = {
 486         cx_arl_destructor,
 487         cx_arl_insert_element,
 488         cx_arl_insert_array,
 489         cx_arl_insert_iter,
 490         cx_arl_remove,
 491         cx_arl_clear,
 492         cx_arl_swap,
 493         cx_arl_at,
 494         cx_arl_find,
 495         cx_arl_sort,
 496         cx_arl_compare,
 497         cx_arl_reverse,
 498         cx_arl_iterator,
 499 };
 500
 501 CxList *cxArrayListCreate(
 502         CxAllocator const *allocator,
 503         CxListComparator comparator,
 504         size_t item_size,
 505         size_t initial_capacity
 506 ) {
 507     if (allocator == NULL) {
 508         allocator = cxDefaultAllocator;
 509     }
 510
 511     cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
 512     if (list == NULL) return NULL;
 513
 514     list->data = cxCalloc(allocator, initial_capacity, item_size);
 515     if (list->data == NULL) {
 516         cxFree(allocator, list);
 517         return NULL;
 518     }
 519
 520     list->base.cl = &cx_array_list_class;
 521     list->base.allocator = allocator;
 522     list->base.cmpfunc = comparator;
 523     list->base.capacity = initial_capacity;
 524
 525     if (item_size > 0) {
 526         list->base.itemsize = item_size;
 527     } else {
 528         cxListStorePointers((CxList *) list);
 529     }
 530
 531     // configure the reallocator
 532     list->reallocator.realloc = cx_arl_realloc;
 533     list->reallocator.ptr1 = (void *) allocator;
 534
 535     return (CxList *) list;
 536 }