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.

  */

 #include "cx/array_list.h"

 #include <assert.h>

 #include <string.h>

 // LOW LEVEL ARRAY LIST FUNCTIONS

 enum cx_array_copy_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

 ) {

     // assert pointers

     assert(target != NULL);

     assert(size != NULL);

     assert(src != NULL);

     // determine capacity

     size_t cap = capacity == NULL ? *size : *capacity;

     // check if resize is required

     size_t minsize = index + elem_count;

     size_t newsize = *size < minsize ? minsize : *size;

     bool needrealloc = newsize > cap;

     // reallocate if possible

     if (needrealloc) {

         // a reallocator and a capacity variable must be available

         if (reallocator == NULL || capacity == NULL) {

             return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED;

         }

         // check, if we need to repair the src pointer

         uintptr_t targetaddr = (uintptr_t) *target;

         uintptr_t srcaddr = (uintptr_t) src;

         bool repairsrc = targetaddr <= srcaddr

                          && srcaddr < targetaddr + cap * elem_size;

         // calculate new capacity (next number divisible by 16)

         cap = newsize - (newsize % 16) + 16;

         assert(cap > newsize);

         // perform reallocation

         void *newmem = reallocator->realloc(

                 *target, cap, elem_size, reallocator

         );

         if (newmem == NULL) {

             return CX_ARRAY_COPY_REALLOC_FAILED;

         }

         // repair src pointer, if necessary

         if (repairsrc) {

             src = ((char *) newmem) + (srcaddr - targetaddr);

         }

         // store new pointer and capacity

         *target = newmem;

         *capacity = cap;

     }

     // determine target pointer

     char *start = *target;

     start += index * elem_size;

     // copy elements and set new size

     memmove(start, src, elem_count * elem_size);

     *size = newsize;

     // return successfully

     return CX_ARRAY_COPY_SUCCESS;

 }

 #ifndef CX_ARRAY_SWAP_SBO_SIZE

 #define CX_ARRAY_SWAP_SBO_SIZE 512

 #endif

 void cx_array_swap(

         void *arr,

         size_t elem_size,

         size_t idx1,

         size_t idx2

 ) {

     assert(arr != NULL);

     // short circuit

     if (idx1 == idx2) return;

     char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];

     void *tmp;

     // decide if we can use the local buffer

     if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {

         tmp = malloc(elem_size);

         // we don't want to enforce error handling

         if (tmp == NULL) abort();

     } else {

         tmp = sbo_mem;

     }

     // calculate memory locations

     char *left = arr, *right = arr;

     left += idx1 * elem_size;

     right += idx2 * elem_size;

     // three-way swap

     memcpy(tmp, left, elem_size);

     memcpy(left, right, elem_size);

     memcpy(right, tmp, elem_size);

     // free dynamic memory, if it was needed

     if (tmp != sbo_mem) {

         free(tmp);

     }

 }

 // HIGH LEVEL ARRAY LIST FUNCTIONS

 typedef struct {

     struct cx_list_s base;

     void *data;

     size_t capacity;

     struct cx_array_reallocator_s reallocator;

 } cx_array_list;

 static void *cx_arl_realloc(

         void *array,

         size_t capacity,

         size_t elem_size,

         struct cx_array_reallocator_s *alloc

 ) {

     // retrieve the pointer to the list allocator

     CxAllocator const *al = alloc->ptr1;

     // use the list allocator to reallocate the memory

     return cxRealloc(al, array, capacity * elem_size);

 }

 static void cx_arl_destructor(struct cx_list_s *list) {

     cx_array_list *arl = (cx_array_list *) list;

     char *ptr = arl->data;

     if (list->simple_destructor) {

         for (size_t i = 0; i < list->size; i++) {

             cx_invoke_simple_destructor(list, ptr);

             ptr += list->item_size;

         }

     }

     if (list->advanced_destructor) {

         for (size_t i = 0; i < list->size; i++) {

             cx_invoke_advanced_destructor(list, ptr);

             ptr += list->item_size;

         }

     }

     cxFree(list->allocator, arl->data);

     cxFree(list->allocator, list);

 }

 static size_t cx_arl_insert_array(

         struct cx_list_s *list,

         size_t index,

         void const *array,

         size_t n

 ) {

     // out of bounds and special case check

     if (index > list->size || n == 0) return 0;

     // get a correctly typed pointer to the list

     cx_array_list *arl = (cx_array_list *) list;

     // do we need to move some elements?

     if (index < list->size) {

         char const *first_to_move = (char const *) arl->data;

         first_to_move += index * list->item_size;

         size_t elems_to_move = list->size - index;

         size_t start_of_moved = index + n;

         if (CX_ARRAY_COPY_SUCCESS != cx_array_copy(

                 &arl->data,

                 &list->size,

                 &arl->capacity,

                 start_of_moved,

                 first_to_move,

                 list->item_size,

                 elems_to_move,

                 &arl->reallocator

         )) {

             // if moving existing elems is unsuccessful, abort

             return 0;

         }

     }

     // note that if we had to move the elements, the following operation

     // is guaranteed to succeed, because we have the memory already allocated

     // therefore, it is impossible to leave this function with an invalid array

     // place the new elements

     if (CX_ARRAY_COPY_SUCCESS == cx_array_copy(

             &arl->data,

             &list->size,

             &arl->capacity,

             index,

             array,

             list->item_size,

             n,

             &arl->reallocator

     )) {

         return n;

     } else {

         // array list implementation is "all or nothing"

         return 0;

     }

 }

 static int cx_arl_insert_element(

         struct cx_list_s *list,

         size_t index,

         void const *element

 ) {

     return 1 != cx_arl_insert_array(list, index, element, 1);

 }

 static int cx_arl_insert_iter(

         struct cx_mut_iterator_s *iter,

         void const *elem,

         int prepend

 ) {

     struct cx_list_s *list = iter->src_handle;

     if (iter->index < list->size) {

         int result = cx_arl_insert_element(

                 list,

                 iter->index + 1 - prepend,

                 elem

         );

         if (result == 0 && prepend != 0) {

             iter->index++;

             iter->elem_handle = ((char *) iter->elem_handle) + list->item_size;

         }

         return result;

     } else {

         int result = cx_arl_insert_element(list, list->size, elem);

         iter->index = list->size;

         return result;

     }

 }

 static int cx_arl_remove(

         struct cx_list_s *list,

         size_t index

 ) {

     cx_array_list *arl = (cx_array_list *) list;

     // out-of-bounds check

     if (index >= list->size) {

         return 1;

     }

     // content destruction

     cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size);

     // short-circuit removal of last element

     if (index == list->size - 1) {

         list->size--;

         return 0;

     }

     // just move the elements starting at index to the left

     int result = cx_array_copy(

             &arl->data,

             &list->size,

             &arl->capacity,

             index,

             ((char *) arl->data) + (index + 1) * list->item_size,

             list->item_size,

             list->size - index - 1,

             &arl->reallocator

     );

     if (result == 0) {

         // decrease the size

         list->size--;

     }

     return result;

 }

 static void cx_arl_clear(struct cx_list_s *list) {

     if (list->size == 0) return;

     cx_array_list *arl = (cx_array_list *) list;

     char *ptr = arl->data;

     if (list->simple_destructor) {

         for (size_t i = 0; i < list->size; i++) {

             cx_invoke_simple_destructor(list, ptr);

             ptr += list->item_size;

         }

     }

     if (list->advanced_destructor) {

         for (size_t i = 0; i < list->size; i++) {

             cx_invoke_advanced_destructor(list, ptr);

             ptr += list->item_size;

         }

     }

     memset(arl->data, 0, list->size * list->item_size);

     list->size = 0;

 }

 static int cx_arl_swap(

         struct cx_list_s *list,

         size_t i,

         size_t j

 ) {

     if (i >= list->size || j >= list->size) return 1;

     cx_array_list *arl = (cx_array_list *) list;

     cx_array_swap(arl->data, list->item_size, i, j);

     return 0;

 }

 static void *cx_arl_at(

         struct cx_list_s const *list,

         size_t index

 ) {

     if (index < list->size) {

         cx_array_list const *arl = (cx_array_list const *) list;

         char *space = arl->data;

         return space + index * list->item_size;

     } else {

         return NULL;

     }

 }

 static ssize_t cx_arl_find(

         struct cx_list_s const *list,

         void const *elem

 ) {

     assert(list->cmpfunc != NULL);

     assert(list->size < SIZE_MAX / 2);

     char *cur = ((cx_array_list const *) list)->data;

     for (ssize_t i = 0; i < (ssize_t) list->size; i++) {

         if (0 == list->cmpfunc(elem, cur)) {

             return i;

         }

         cur += list->item_size;

     }

     return -1;

 }

 static void cx_arl_sort(struct cx_list_s *list) {

     assert(list->cmpfunc != NULL);

     qsort(((cx_array_list *) list)->data,

           list->size,

           list->item_size,

           list->cmpfunc

     );

 }

 static int cx_arl_compare(

         struct cx_list_s const *list,

         struct cx_list_s const *other

 ) {

     assert(list->cmpfunc != NULL);

     if (list->size == other->size) {

         char const *left = ((cx_array_list const *) list)->data;

         char const *right = ((cx_array_list const *) other)->data;

         for (size_t i = 0; i < list->size; i++) {

             int d = list->cmpfunc(left, right);

             if (d != 0) {

                 return d;

             }

             left += list->item_size;

             right += other->item_size;

         }

         return 0;

     } else {

         return list->size < other->size ? -1 : 1;

     }

 }

 static void cx_arl_reverse(struct cx_list_s *list) {

     if (list->size < 2) return;

     void *data = ((cx_array_list const *) list)->data;

     size_t half = list->size / 2;

     for (size_t i = 0; i < half; i++) {

         cx_array_swap(data, list->item_size, i, list->size - 1 - i);

     }

 }

 static bool cx_arl_iter_valid(void const *it) {

     struct cx_iterator_s const *iter = it;

     struct cx_list_s const *list = iter->src_handle;

     return iter->index < list->size;

 }

 static void *cx_arl_iter_current(void const *it) {

     struct cx_iterator_s const *iter = it;

     return iter->elem_handle;

 }

 static void cx_arl_iter_next(void *it) {

     struct cx_iterator_base_s *itbase = it;

     if (itbase->remove) {

         struct cx_mut_iterator_s *iter = it;

         itbase->remove = false;

         cx_arl_remove(iter->src_handle, iter->index);

     } else {

         struct cx_iterator_s *iter = it;

         iter->index++;

         iter->elem_handle =

                 ((char *) iter->elem_handle)

                 + ((struct cx_list_s const *) iter->src_handle)->item_size;

     }

 }

 static void cx_arl_iter_prev(void *it) {

     struct cx_iterator_base_s *itbase = it;

     struct cx_mut_iterator_s *iter = it;

     cx_array_list *const list = iter->src_handle;

     if (itbase->remove) {

         itbase->remove = false;

         cx_arl_remove(iter->src_handle, iter->index);

     }

     iter->index--;

     if (iter->index < list->base.size) {

         iter->elem_handle = ((char *) list->data)

                             + iter->index * list->base.item_size;

     }

 }

 static bool cx_arl_iter_flag_rm(void *it) {

     struct cx_iterator_base_s *iter = it;

     if (iter->mutating) {

         iter->remove = true;

         return true;

     } else {

         return false;

     }

 }

 static struct cx_iterator_s cx_arl_iterator(

         struct cx_list_s const *list,

         size_t index,

         bool backwards

 ) {

     struct cx_iterator_s iter;

     iter.index = index;

     iter.src_handle = list;

     iter.elem_handle = cx_arl_at(list, index);

     iter.base.valid = cx_arl_iter_valid;

     iter.base.current = cx_arl_iter_current;

     iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;

     iter.base.flag_removal = cx_arl_iter_flag_rm;

     iter.base.remove = false;

     iter.base.mutating = false;

     return iter;

 }

 static cx_list_class cx_array_list_class = {

         cx_arl_destructor,

         cx_arl_insert_element,

         cx_arl_insert_array,

         cx_arl_insert_iter,

         cx_arl_remove,

         cx_arl_clear,

         cx_arl_swap,

         cx_arl_at,

         cx_arl_find,

         cx_arl_sort,

         cx_arl_compare,

         cx_arl_reverse,

         cx_arl_iterator,

 };

 CxList *cxArrayListCreate(

         CxAllocator const *allocator,

         cx_compare_func comparator,

         size_t item_size,

         size_t initial_capacity

 ) {

     if (allocator == NULL) {

         allocator = cxDefaultAllocator;

     }

     cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));

     if (list == NULL) return NULL;

     list->base.cl = &cx_array_list_class;

     list->base.allocator = allocator;

     list->base.cmpfunc = comparator;

     list->capacity = initial_capacity;

     if (item_size > 0) {

         list->base.item_size = item_size;

     } else {

         item_size = sizeof(void *);

         cxListStorePointers((CxList *) list);

     }

     // allocate the array after the real item_size is known

     list->data = cxCalloc(allocator, initial_capacity, item_size);

     if (list->data == NULL) {

         cxFree(allocator, list);

         return NULL;

     }

     // configure the reallocator

     list->reallocator.realloc = cx_arl_realloc;

     list->reallocator.ptr1 = (void *) allocator;

     return (CxList *) list;

 }