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 128
 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     size_t capacity;
 154     struct cx_array_reallocator_s reallocator;
 155 } cx_array_list;
 156
 157 static void *cx_arl_realloc(
 158         void *array,
 159         size_t capacity,
 160         size_t elem_size,
 161         struct cx_array_reallocator_s *alloc
 162 ) {
 163     // retrieve the pointer to the list allocator
 164     CxAllocator const *al = alloc->ptr1;
 165
 166     // use the list allocator to reallocate the memory
 167     return cxRealloc(al, array, capacity * elem_size);
 168 }
 169
 170 static void cx_arl_destructor(struct cx_list_s *list) {
 171     cx_array_list *arl = (cx_array_list *) list;
 172
 173     char *ptr = arl->data;
 174
 175     if (list->simple_destructor) {
 176         for (size_t i = 0; i < list->size; i++) {
 177             cx_invoke_simple_destructor(list, ptr);
 178             ptr += list->item_size;
 179         }
 180     }
 181     if (list->advanced_destructor) {
 182         for (size_t i = 0; i < list->size; i++) {
 183             cx_invoke_advanced_destructor(list, ptr);
 184             ptr += list->item_size;
 185         }
 186     }
 187
 188     cxFree(list->allocator, arl->data);
 189     cxFree(list->allocator, list);
 190 }
 191
 192 static size_t cx_arl_insert_array(
 193         struct cx_list_s *list,
 194         size_t index,
 195         void const *array,
 196         size_t n
 197 ) {
 198     // out of bounds and special case check
 199     if (index > list->size || n == 0) return 0;
 200
 201     // get a correctly typed pointer to the list
 202     cx_array_list *arl = (cx_array_list *) list;
 203
 204     // do we need to move some elements?
 205     if (index < list->size) {
 206         char const *first_to_move = (char const *) arl->data;
 207         first_to_move += index * list->item_size;
 208         size_t elems_to_move = list->size - index;
 209         size_t start_of_moved = index + n;
 210
 211         if (CX_ARRAY_COPY_SUCCESS != cx_array_copy(
 212                 &arl->data,
 213                 &list->size,
 214                 &arl->capacity,
 215                 start_of_moved,
 216                 first_to_move,
 217                 list->item_size,
 218                 elems_to_move,
 219                 &arl->reallocator
 220         )) {
 221             // if moving existing elems is unsuccessful, abort
 222             return 0;
 223         }
 224     }
 225
 226     // note that if we had to move the elements, the following operation
 227     // is guaranteed to succeed, because we have the memory already allocated
 228     // therefore, it is impossible to leave this function with an invalid array
 229
 230     // place the new elements
 231     if (CX_ARRAY_COPY_SUCCESS == cx_array_copy(
 232             &arl->data,
 233             &list->size,
 234             &arl->capacity,
 235             index,
 236             array,
 237             list->item_size,
 238             n,
 239             &arl->reallocator
 240     )) {
 241         return n;
 242     } else {
 243         // array list implementation is "all or nothing"
 244         return 0;
 245     }
 246 }
 247
 248 static int cx_arl_insert_element(
 249         struct cx_list_s *list,
 250         size_t index,
 251         void const *element
 252 ) {
 253     return 1 != cx_arl_insert_array(list, index, element, 1);
 254 }
 255
 256 static int cx_arl_insert_iter(
 257         struct cx_mut_iterator_s *iter,
 258         void const *elem,
 259         int prepend
 260 ) {
 261     struct cx_list_s *list = iter->src_handle;
 262     if (iter->index < list->size) {
 263         int result = cx_arl_insert_element(
 264                 list,
 265                 iter->index + 1 - prepend,
 266                 elem
 267         );
 268         if (result == 0 && prepend != 0) {
 269             iter->index++;
 270             iter->elem_handle = ((char *) iter->elem_handle) + list->item_size;
 271         }
 272         return result;
 273     } else {
 274         int result = cx_arl_insert_element(list, list->size, elem);
 275         iter->index = list->size;
 276         return result;
 277     }
 278 }
 279
 280 static int cx_arl_remove(
 281         struct cx_list_s *list,
 282         size_t index
 283 ) {
 284     cx_array_list *arl = (cx_array_list *) list;
 285
 286     // out-of-bounds check
 287     if (index >= list->size) {
 288         return 1;
 289     }
 290
 291     // content destruction
 292     cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size);
 293
 294     // short-circuit removal of last element
 295     if (index == list->size - 1) {
 296         list->size--;
 297         return 0;
 298     }
 299
 300     // just move the elements starting at index to the left
 301     int result = cx_array_copy(
 302             &arl->data,
 303             &list->size,
 304             &arl->capacity,
 305             index,
 306             ((char *) arl->data) + (index + 1) * list->item_size,
 307             list->item_size,
 308             list->size - index - 1,
 309             &arl->reallocator
 310     );
 311     if (result == 0) {
 312         // decrease the size
 313         list->size--;
 314     }
 315     return result;
 316 }
 317
 318 static void cx_arl_clear(struct cx_list_s *list) {
 319     if (list->size == 0) return;
 320
 321     cx_array_list *arl = (cx_array_list *) list;
 322     char *ptr = arl->data;
 323
 324     if (list->simple_destructor) {
 325         for (size_t i = 0; i < list->size; i++) {
 326             cx_invoke_simple_destructor(list, ptr);
 327             ptr += list->item_size;
 328         }
 329     }
 330     if (list->advanced_destructor) {
 331         for (size_t i = 0; i < list->size; i++) {
 332             cx_invoke_advanced_destructor(list, ptr);
 333             ptr += list->item_size;
 334         }
 335     }
 336
 337     memset(arl->data, 0, list->size * list->item_size);
 338     list->size = 0;
 339 }
 340
 341 static int cx_arl_swap(
 342         struct cx_list_s *list,
 343         size_t i,
 344         size_t j
 345 ) {
 346     if (i >= list->size || j >= list->size) return 1;
 347     cx_array_list *arl = (cx_array_list *) list;
 348     cx_array_swap(arl->data, list->item_size, i, j);
 349     return 0;
 350 }
 351
 352 static void *cx_arl_at(
 353         struct cx_list_s const *list,
 354         size_t index
 355 ) {
 356     if (index < list->size) {
 357         cx_array_list const *arl = (cx_array_list const *) list;
 358         char *space = arl->data;
 359         return space + index * list->item_size;
 360     } else {
 361         return NULL;
 362     }
 363 }
 364
 365 static ssize_t cx_arl_find(
 366         struct cx_list_s const *list,
 367         void const *elem
 368 ) {
 369     assert(list->cmpfunc != NULL);
 370     assert(list->size < SIZE_MAX / 2);
 371     char *cur = ((cx_array_list const *) list)->data;
 372
 373     for (ssize_t i = 0; i < (ssize_t) list->size; i++) {
 374         if (0 == list->cmpfunc(elem, cur)) {
 375             return i;
 376         }
 377         cur += list->item_size;
 378     }
 379
 380     return -1;
 381 }
 382
 383 static void cx_arl_sort(struct cx_list_s *list) {
 384     assert(list->cmpfunc != NULL);
 385     qsort(((cx_array_list *) list)->data,
 386           list->size,
 387           list->item_size,
 388           list->cmpfunc
 389     );
 390 }
 391
 392 static int cx_arl_compare(
 393         struct cx_list_s const *list,
 394         struct cx_list_s const *other
 395 ) {
 396     assert(list->cmpfunc != NULL);
 397     if (list->size == other->size) {
 398         char const *left = ((cx_array_list const *) list)->data;
 399         char const *right = ((cx_array_list const *) other)->data;
 400         for (size_t i = 0; i < list->size; i++) {
 401             int d = list->cmpfunc(left, right);
 402             if (d != 0) {
 403                 return d;
 404             }
 405             left += list->item_size;
 406             right += other->item_size;
 407         }
 408         return 0;
 409     } else {
 410         return list->size < other->size ? -1 : 1;
 411     }
 412 }
 413
 414 static void cx_arl_reverse(struct cx_list_s *list) {
 415     if (list->size < 2) return;
 416     void *data = ((cx_array_list const *) list)->data;
 417     size_t half = list->size / 2;
 418     for (size_t i = 0; i < half; i++) {
 419         cx_array_swap(data, list->item_size, i, list->size - 1 - i);
 420     }
 421 }
 422
 423 static bool cx_arl_iter_valid(void const *it) {
 424     struct cx_iterator_s const *iter = it;
 425     struct cx_list_s const *list = iter->src_handle;
 426     return iter->index < list->size;
 427 }
 428
 429 static void *cx_arl_iter_current(void const *it) {
 430     struct cx_iterator_s const *iter = it;
 431     return iter->elem_handle;
 432 }
 433
 434 static void cx_arl_iter_next(void *it) {
 435     struct cx_iterator_base_s *itbase = it;
 436     if (itbase->remove) {
 437         struct cx_mut_iterator_s *iter = it;
 438         itbase->remove = false;
 439         cx_arl_remove(iter->src_handle, iter->index);
 440     } else {
 441         struct cx_iterator_s *iter = it;
 442         iter->index++;
 443         iter->elem_handle =
 444                 ((char *) iter->elem_handle)
 445                 + ((struct cx_list_s const *) iter->src_handle)->item_size;
 446     }
 447 }
 448
 449 static void cx_arl_iter_prev(void *it) {
 450     struct cx_iterator_base_s *itbase = it;
 451     struct cx_mut_iterator_s *iter = it;
 452     cx_array_list *const list = iter->src_handle;
 453     if (itbase->remove) {
 454         itbase->remove = false;
 455         cx_arl_remove(iter->src_handle, iter->index);
 456     }
 457     iter->index--;
 458     if (iter->index < list->base.size) {
 459         iter->elem_handle = ((char *) list->data)
 460                             + iter->index * list->base.item_size;
 461     }
 462 }
 463
 464 static bool cx_arl_iter_flag_rm(void *it) {
 465     struct cx_iterator_base_s *iter = it;
 466     if (iter->mutating) {
 467         iter->remove = true;
 468         return true;
 469     } else {
 470         return false;
 471     }
 472 }
 473
 474 static struct cx_iterator_s cx_arl_iterator(
 475         struct cx_list_s const *list,
 476         size_t index,
 477         bool backwards
 478 ) {
 479     struct cx_iterator_s iter;
 480
 481     iter.index = index;
 482     iter.src_handle = list;
 483     iter.elem_handle = cx_arl_at(list, index);
 484     iter.base.valid = cx_arl_iter_valid;
 485     iter.base.current = cx_arl_iter_current;
 486     iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
 487     iter.base.flag_removal = cx_arl_iter_flag_rm;
 488     iter.base.remove = false;
 489     iter.base.mutating = false;
 490
 491     return iter;
 492 }
 493
 494 static cx_list_class cx_array_list_class = {
 495         cx_arl_destructor,
 496         cx_arl_insert_element,
 497         cx_arl_insert_array,
 498         cx_arl_insert_iter,
 499         cx_arl_remove,
 500         cx_arl_clear,
 501         cx_arl_swap,
 502         cx_arl_at,
 503         cx_arl_find,
 504         cx_arl_sort,
 505         cx_arl_compare,
 506         cx_arl_reverse,
 507         cx_arl_iterator,
 508 };
 509
 510 CxList *cxArrayListCreate(
 511         CxAllocator const *allocator,
 512         cx_compare_func comparator,
 513         size_t item_size,
 514         size_t initial_capacity
 515 ) {
 516     if (allocator == NULL) {
 517         allocator = cxDefaultAllocator;
 518     }
 519
 520     cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
 521     if (list == NULL) return NULL;
 522
 523     list->base.cl = &cx_array_list_class;
 524     list->base.allocator = allocator;
 525     list->base.cmpfunc = comparator;
 526     list->capacity = initial_capacity;
 527
 528     if (item_size > 0) {
 529         list->base.item_size = item_size;
 530     } else {
 531         item_size = sizeof(void *);
 532         cxListStorePointers((CxList *) list);
 533     }
 534
 535     // allocate the array after the real item_size is known
 536     list->data = cxCalloc(allocator, initial_capacity, item_size);
 537     if (list->data == NULL) {
 538         cxFree(allocator, list);
 539         return NULL;
 540     }
 541
 542     // configure the reallocator
 543     list->reallocator.realloc = cx_arl_realloc;
 544     list->reallocator.ptr1 = (void *) allocator;
 545
 546     return (CxList *) list;
 547 }