universe@606: /*
universe@606:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@606:  *
universe@606:  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
universe@606:  *
universe@606:  * Redistribution and use in source and binary forms, with or without
universe@606:  * modification, are permitted provided that the following conditions are met:
universe@606:  *
universe@606:  *   1. Redistributions of source code must retain the above copyright
universe@606:  *      notice, this list of conditions and the following disclaimer.
universe@606:  *
universe@606:  *   2. Redistributions in binary form must reproduce the above copyright
universe@606:  *      notice, this list of conditions and the following disclaimer in the
universe@606:  *      documentation and/or other materials provided with the distribution.
universe@606:  *
universe@606:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@606:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@606:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@606:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@606:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@606:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@606:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@606:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@606:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@606:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@606:  * POSSIBILITY OF SUCH DAMAGE.
universe@606:  */
universe@606: 
universe@606: #include "cx/array_list.h"
universe@763: #include "cx/compare.h"
universe@610: #include <assert.h>
universe@610: #include <string.h>
universe@606: 
universe@817: // Default array reallocator
universe@817: 
universe@817: static void *cx_array_default_realloc(
universe@817:         void *array,
universe@817:         size_t capacity,
universe@817:         size_t elem_size,
universe@817:         __attribute__((__unused__)) struct cx_array_reallocator_s *alloc
universe@817: ) {
universe@817:     return realloc(array, capacity * elem_size);
universe@817: }
universe@817: 
universe@818: struct cx_array_reallocator_s cx_array_default_reallocator_impl = {
universe@817:         cx_array_default_realloc, NULL, NULL, 0, 0
universe@817: };
universe@817: 
universe@818: struct cx_array_reallocator_s *cx_array_default_reallocator = &cx_array_default_reallocator_impl;
universe@818: 
universe@628: // LOW LEVEL ARRAY LIST FUNCTIONS
universe@607: 
universe@819: enum cx_array_result cx_array_copy(
universe@610:         void **target,
universe@610:         size_t *size,
universe@610:         size_t *capacity,
universe@610:         size_t index,
universe@610:         void const *src,
universe@610:         size_t elem_size,
universe@610:         size_t elem_count,
universe@610:         struct cx_array_reallocator_s *reallocator
universe@610: ) {
universe@628:     // assert pointers
universe@610:     assert(target != NULL);
universe@610:     assert(size != NULL);
universe@610:     assert(src != NULL);
universe@607: 
universe@628:     // determine capacity
universe@610:     size_t cap = capacity == NULL ? *size : *capacity;
universe@610: 
universe@628:     // check if resize is required
universe@627:     size_t minsize = index + elem_count;
universe@627:     size_t newsize = *size < minsize ? minsize : *size;
universe@610:     bool needrealloc = newsize > cap;
universe@610: 
universe@628:     // reallocate if possible
universe@610:     if (needrealloc) {
universe@628:         // a reallocator and a capacity variable must be available
universe@610:         if (reallocator == NULL || capacity == NULL) {
universe@819:             return CX_ARRAY_REALLOC_NOT_SUPPORTED;
universe@610:         }
universe@610: 
universe@628:         // check, if we need to repair the src pointer
universe@611:         uintptr_t targetaddr = (uintptr_t) *target;
universe@611:         uintptr_t srcaddr = (uintptr_t) src;
universe@611:         bool repairsrc = targetaddr <= srcaddr
universe@611:                          && srcaddr < targetaddr + cap * elem_size;
universe@611: 
universe@628:         // calculate new capacity (next number divisible by 16)
universe@625:         cap = newsize - (newsize % 16) + 16;
universe@625:         assert(cap > newsize);
universe@610: 
universe@628:         // perform reallocation
universe@610:         void *newmem = reallocator->realloc(
universe@610:                 *target, cap, elem_size, reallocator
universe@610:         );
universe@610:         if (newmem == NULL) {
universe@819:             return CX_ARRAY_REALLOC_FAILED;
universe@610:         }
universe@610: 
universe@628:         // repair src pointer, if necessary
universe@611:         if (repairsrc) {
universe@611:             src = ((char *) newmem) + (srcaddr - targetaddr);
universe@611:         }
universe@611: 
universe@628:         // store new pointer and capacity
universe@610:         *target = newmem;
universe@610:         *capacity = cap;
universe@610:     }
universe@610: 
universe@628:     // determine target pointer
universe@610:     char *start = *target;
universe@610:     start += index * elem_size;
universe@610: 
universe@628:     // copy elements and set new size
universe@611:     memmove(start, src, elem_count * elem_size);
universe@610:     *size = newsize;
universe@610: 
universe@628:     // return successfully
universe@819:     return CX_ARRAY_SUCCESS;
universe@610: }
universe@607: 
universe@643: #ifndef CX_ARRAY_SWAP_SBO_SIZE
universe@735: #define CX_ARRAY_SWAP_SBO_SIZE 128
universe@643: #endif
universe@807: unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE;
universe@804: 
universe@623: void cx_array_swap(
universe@623:         void *arr,
universe@623:         size_t elem_size,
universe@623:         size_t idx1,
universe@623:         size_t idx2
universe@623: ) {
universe@660:     assert(arr != NULL);
universe@660: 
universe@628:     // short circuit
universe@623:     if (idx1 == idx2) return;
universe@623: 
universe@623:     char sbo_mem[CX_ARRAY_SWAP_SBO_SIZE];
universe@623:     void *tmp;
universe@623: 
universe@628:     // decide if we can use the local buffer
universe@807:     if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
universe@623:         tmp = malloc(elem_size);
universe@628:         // we don't want to enforce error handling
universe@623:         if (tmp == NULL) abort();
universe@623:     } else {
universe@623:         tmp = sbo_mem;
universe@623:     }
universe@623: 
universe@628:     // calculate memory locations
universe@623:     char *left = arr, *right = arr;
universe@623:     left += idx1 * elem_size;
universe@623:     right += idx2 * elem_size;
universe@623: 
universe@628:     // three-way swap
universe@623:     memcpy(tmp, left, elem_size);
universe@623:     memcpy(left, right, elem_size);
universe@623:     memcpy(right, tmp, elem_size);
universe@623: 
universe@628:     // free dynamic memory, if it was needed
universe@623:     if (tmp != sbo_mem) {
universe@623:         free(tmp);
universe@623:     }
universe@623: }
universe@623: 
universe@628: // HIGH LEVEL ARRAY LIST FUNCTIONS
universe@607: 
universe@607: typedef struct {
universe@607:     struct cx_list_s base;
universe@607:     void *data;
universe@677:     size_t capacity;
universe@610:     struct cx_array_reallocator_s reallocator;
universe@607: } cx_array_list;
universe@607: 
universe@610: static void *cx_arl_realloc(
universe@610:         void *array,
universe@610:         size_t capacity,
universe@610:         size_t elem_size,
universe@610:         struct cx_array_reallocator_s *alloc
universe@610: ) {
universe@628:     // retrieve the pointer to the list allocator
universe@610:     CxAllocator const *al = alloc->ptr1;
universe@610: 
universe@628:     // use the list allocator to reallocate the memory
universe@610:     return cxRealloc(al, array, capacity * elem_size);
universe@610: }
universe@610: 
universe@607: static void cx_arl_destructor(struct cx_list_s *list) {
universe@610:     cx_array_list *arl = (cx_array_list *) list;
universe@708: 
universe@708:     char *ptr = arl->data;
universe@708: 
universe@708:     if (list->simple_destructor) {
universe@708:         for (size_t i = 0; i < list->size; i++) {
universe@708:             cx_invoke_simple_destructor(list, ptr);
universe@708:             ptr += list->item_size;
universe@708:         }
universe@708:     }
universe@708:     if (list->advanced_destructor) {
universe@708:         for (size_t i = 0; i < list->size; i++) {
universe@708:             cx_invoke_advanced_destructor(list, ptr);
universe@708:             ptr += list->item_size;
universe@708:         }
universe@708:     }
universe@708: 
universe@607:     cxFree(list->allocator, arl->data);
universe@708:     cxFree(list->allocator, list);
universe@607: }
universe@607: 
universe@638: static size_t cx_arl_insert_array(
universe@629:         struct cx_list_s *list,
universe@638:         size_t index,
universe@629:         void const *array,
universe@629:         size_t n
universe@629: ) {
universe@638:     // out of bounds and special case check
universe@638:     if (index > list->size || n == 0) return 0;
universe@638: 
universe@638:     // get a correctly typed pointer to the list
universe@629:     cx_array_list *arl = (cx_array_list *) list;
universe@638: 
universe@638:     // do we need to move some elements?
universe@638:     if (index < list->size) {
universe@638:         char const *first_to_move = (char const *) arl->data;
universe@677:         first_to_move += index * list->item_size;
universe@638:         size_t elems_to_move = list->size - index;
universe@638:         size_t start_of_moved = index + n;
universe@638: 
universe@819:         if (CX_ARRAY_SUCCESS != cx_array_copy(
universe@638:                 &arl->data,
universe@638:                 &list->size,
universe@677:                 &arl->capacity,
universe@638:                 start_of_moved,
universe@638:                 first_to_move,
universe@677:                 list->item_size,
universe@638:                 elems_to_move,
universe@638:                 &arl->reallocator
universe@638:         )) {
universe@638:             // if moving existing elems is unsuccessful, abort
universe@638:             return 0;
universe@638:         }
universe@638:     }
universe@638: 
universe@638:     // note that if we had to move the elements, the following operation
universe@638:     // is guaranteed to succeed, because we have the memory already allocated
universe@638:     // therefore, it is impossible to leave this function with an invalid array
universe@638: 
universe@638:     // place the new elements
universe@819:     if (CX_ARRAY_SUCCESS == cx_array_copy(
universe@629:             &arl->data,
universe@629:             &list->size,
universe@677:             &arl->capacity,
universe@638:             index,
universe@629:             array,
universe@677:             list->item_size,
universe@629:             n,
universe@629:             &arl->reallocator
universe@629:     )) {
universe@629:         return n;
universe@629:     } else {
universe@629:         // array list implementation is "all or nothing"
universe@629:         return 0;
universe@629:     }
universe@629: }
universe@629: 
universe@641: static int cx_arl_insert_element(
universe@641:         struct cx_list_s *list,
universe@641:         size_t index,
universe@641:         void const *element
universe@641: ) {
universe@641:     return 1 != cx_arl_insert_array(list, index, element, 1);
universe@641: }
universe@641: 
universe@607: static int cx_arl_insert_iter(
universe@630:         struct cx_mut_iterator_s *iter,
universe@607:         void const *elem,
universe@607:         int prepend
universe@607: ) {
universe@619:     struct cx_list_s *list = iter->src_handle;
universe@619:     if (iter->index < list->size) {
universe@641:         int result = cx_arl_insert_element(
universe@619:                 list,
universe@619:                 iter->index + 1 - prepend,
universe@641:                 elem
universe@619:         );
universe@619:         if (result == 0 && prepend != 0) {
universe@619:             iter->index++;
universe@677:             iter->elem_handle = ((char *) iter->elem_handle) + list->item_size;
universe@619:         }
universe@619:         return result;
universe@619:     } else {
universe@641:         int result = cx_arl_insert_element(list, list->size, elem);
universe@619:         iter->index = list->size;
universe@619:         return result;
universe@619:     }
universe@607: }
universe@607: 
universe@607: static int cx_arl_remove(
universe@607:         struct cx_list_s *list,
universe@607:         size_t index
universe@607: ) {
universe@664:     cx_array_list *arl = (cx_array_list *) list;
universe@664: 
universe@628:     // out-of-bounds check
universe@613:     if (index >= list->size) {
universe@613:         return 1;
universe@613:     }
universe@613: 
universe@664:     // content destruction
universe@678:     cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size);
universe@664: 
universe@628:     // short-circuit removal of last element
universe@624:     if (index == list->size - 1) {
universe@624:         list->size--;
universe@624:         return 0;
universe@624:     }
universe@613: 
universe@628:     // just move the elements starting at index to the left
universe@613:     int result = cx_array_copy(
universe@613:             &arl->data,
universe@613:             &list->size,
universe@677:             &arl->capacity,
universe@613:             index,
universe@677:             ((char *) arl->data) + (index + 1) * list->item_size,
universe@677:             list->item_size,
universe@626:             list->size - index - 1,
universe@613:             &arl->reallocator
universe@613:     );
universe@820: 
universe@820:     // cx_array_copy cannot fail, array cannot grow
universe@820:     assert(result == 0);
universe@820: 
universe@820:     // decrease the size
universe@820:     list->size--;
universe@820: 
universe@820:     return 0;
universe@607: }
universe@607: 
universe@664: static void cx_arl_clear(struct cx_list_s *list) {
universe@664:     if (list->size == 0) return;
universe@664: 
universe@664:     cx_array_list *arl = (cx_array_list *) list;
universe@664:     char *ptr = arl->data;
universe@664: 
universe@677:     if (list->simple_destructor) {
universe@677:         for (size_t i = 0; i < list->size; i++) {
universe@677:             cx_invoke_simple_destructor(list, ptr);
universe@677:             ptr += list->item_size;
universe@664:         }
universe@677:     }
universe@677:     if (list->advanced_destructor) {
universe@677:         for (size_t i = 0; i < list->size; i++) {
universe@677:             cx_invoke_advanced_destructor(list, ptr);
universe@677:             ptr += list->item_size;
universe@664:         }
universe@664:     }
universe@666: 
universe@677:     memset(arl->data, 0, list->size * list->item_size);
universe@666:     list->size = 0;
universe@664: }
universe@664: 
universe@647: static int cx_arl_swap(
universe@647:         struct cx_list_s *list,
universe@647:         size_t i,
universe@647:         size_t j
universe@647: ) {
universe@647:     if (i >= list->size || j >= list->size) return 1;
universe@647:     cx_array_list *arl = (cx_array_list *) list;
universe@677:     cx_array_swap(arl->data, list->item_size, i, j);
universe@647:     return 0;
universe@647: }
universe@647: 
universe@610: static void *cx_arl_at(
universe@607:         struct cx_list_s const *list,
universe@607:         size_t index
universe@607: ) {
universe@610:     if (index < list->size) {
universe@610:         cx_array_list const *arl = (cx_array_list const *) list;
universe@610:         char *space = arl->data;
universe@677:         return space + index * list->item_size;
universe@610:     } else {
universe@610:         return NULL;
universe@610:     }
universe@607: }
universe@607: 
universe@764: static ssize_t cx_arl_find_remove(
universe@764:         struct cx_list_s *list,
universe@764:         void const *elem,
universe@764:         bool remove
universe@607: ) {
universe@660:     assert(list->cmpfunc != NULL);
universe@699:     assert(list->size < SIZE_MAX / 2);
universe@614:     char *cur = ((cx_array_list const *) list)->data;
universe@614: 
universe@699:     for (ssize_t i = 0; i < (ssize_t) list->size; i++) {
universe@614:         if (0 == list->cmpfunc(elem, cur)) {
universe@764:             if (remove) {
universe@764:                 if (0 == cx_arl_remove(list, i)) {
universe@764:                     return i;
universe@764:                 } else {
universe@764:                     return -1;
universe@764:                 }
universe@764:             } else {
universe@764:                 return i;
universe@764:             }
universe@614:         }
universe@677:         cur += list->item_size;
universe@614:     }
universe@614: 
universe@699:     return -1;
universe@607: }
universe@607: 
universe@607: static void cx_arl_sort(struct cx_list_s *list) {
universe@660:     assert(list->cmpfunc != NULL);
universe@615:     qsort(((cx_array_list *) list)->data,
universe@615:           list->size,
universe@677:           list->item_size,
universe@615:           list->cmpfunc
universe@615:     );
universe@607: }
universe@607: 
universe@607: static int cx_arl_compare(
universe@607:         struct cx_list_s const *list,
universe@607:         struct cx_list_s const *other
universe@607: ) {
universe@660:     assert(list->cmpfunc != NULL);
universe@622:     if (list->size == other->size) {
universe@622:         char const *left = ((cx_array_list const *) list)->data;
universe@622:         char const *right = ((cx_array_list const *) other)->data;
universe@622:         for (size_t i = 0; i < list->size; i++) {
universe@622:             int d = list->cmpfunc(left, right);
universe@622:             if (d != 0) {
universe@622:                 return d;
universe@622:             }
universe@677:             left += list->item_size;
universe@677:             right += other->item_size;
universe@622:         }
universe@622:         return 0;
universe@622:     } else {
universe@622:         return list->size < other->size ? -1 : 1;
universe@622:     }
universe@607: }
universe@607: 
universe@607: static void cx_arl_reverse(struct cx_list_s *list) {
universe@623:     if (list->size < 2) return;
universe@623:     void *data = ((cx_array_list const *) list)->data;
universe@623:     size_t half = list->size / 2;
universe@623:     for (size_t i = 0; i < half; i++) {
universe@677:         cx_array_swap(data, list->item_size, i, list->size - 1 - i);
universe@623:     }
universe@607: }
universe@607: 
universe@630: static bool cx_arl_iter_valid(void const *it) {
universe@630:     struct cx_iterator_s const *iter = it;
universe@616:     struct cx_list_s const *list = iter->src_handle;
universe@616:     return iter->index < list->size;
universe@616: }
universe@616: 
universe@630: static void *cx_arl_iter_current(void const *it) {
universe@630:     struct cx_iterator_s const *iter = it;
universe@616:     return iter->elem_handle;
universe@616: }
universe@616: 
universe@630: static void cx_arl_iter_next(void *it) {
universe@630:     struct cx_iterator_base_s *itbase = it;
universe@630:     if (itbase->remove) {
universe@630:         struct cx_mut_iterator_s *iter = it;
universe@630:         itbase->remove = false;
universe@616:         cx_arl_remove(iter->src_handle, iter->index);
universe@616:     } else {
universe@630:         struct cx_iterator_s *iter = it;
universe@616:         iter->index++;
universe@620:         iter->elem_handle =
universe@620:                 ((char *) iter->elem_handle)
universe@677:                 + ((struct cx_list_s const *) iter->src_handle)->item_size;
universe@616:     }
universe@616: }
universe@616: 
universe@655: static void cx_arl_iter_prev(void *it) {
universe@655:     struct cx_iterator_base_s *itbase = it;
universe@655:     struct cx_mut_iterator_s *iter = it;
universe@655:     cx_array_list *const list = iter->src_handle;
universe@655:     if (itbase->remove) {
universe@655:         itbase->remove = false;
universe@655:         cx_arl_remove(iter->src_handle, iter->index);
universe@655:     }
universe@655:     iter->index--;
universe@655:     if (iter->index < list->base.size) {
universe@655:         iter->elem_handle = ((char *) list->data)
universe@677:                             + iter->index * list->base.item_size;
universe@655:     }
universe@655: }
universe@655: 
universe@630: 
universe@607: static struct cx_iterator_s cx_arl_iterator(
universe@630:         struct cx_list_s const *list,
universe@655:         size_t index,
universe@655:         bool backwards
universe@607: ) {
universe@607:     struct cx_iterator_s iter;
universe@607: 
universe@616:     iter.index = index;
universe@616:     iter.src_handle = list;
universe@616:     iter.elem_handle = cx_arl_at(list, index);
universe@630:     iter.base.valid = cx_arl_iter_valid;
universe@630:     iter.base.current = cx_arl_iter_current;
universe@655:     iter.base.next = backwards ? cx_arl_iter_prev : cx_arl_iter_next;
universe@630:     iter.base.remove = false;
universe@630:     iter.base.mutating = false;
universe@616: 
universe@607:     return iter;
universe@607: }
universe@607: 
universe@607: static cx_list_class cx_array_list_class = {
universe@607:         cx_arl_destructor,
universe@641:         cx_arl_insert_element,
universe@638:         cx_arl_insert_array,
universe@607:         cx_arl_insert_iter,
universe@607:         cx_arl_remove,
universe@664:         cx_arl_clear,
universe@647:         cx_arl_swap,
universe@607:         cx_arl_at,
universe@764:         cx_arl_find_remove,
universe@607:         cx_arl_sort,
universe@607:         cx_arl_compare,
universe@607:         cx_arl_reverse,
universe@607:         cx_arl_iterator,
universe@607: };
universe@607: 
universe@670: CxList *cxArrayListCreate(
universe@606:         CxAllocator const *allocator,
universe@677:         cx_compare_func comparator,
universe@606:         size_t item_size,
universe@606:         size_t initial_capacity
universe@606: ) {
universe@670:     if (allocator == NULL) {
universe@670:         allocator = cxDefaultAllocator;
universe@670:     }
universe@670: 
universe@607:     cx_array_list *list = cxCalloc(allocator, 1, sizeof(cx_array_list));
universe@607:     if (list == NULL) return NULL;
universe@607: 
universe@607:     list->base.cl = &cx_array_list_class;
universe@607:     list->base.allocator = allocator;
universe@677:     list->capacity = initial_capacity;
universe@607: 
universe@667:     if (item_size > 0) {
universe@677:         list->base.item_size = item_size;
universe@763:         list->base.cmpfunc = comparator;
universe@667:     } else {
universe@678:         item_size = sizeof(void *);
universe@763:         list->base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator;
universe@667:         cxListStorePointers((CxList *) list);
universe@667:     }
universe@667: 
universe@676:     // allocate the array after the real item_size is known
universe@676:     list->data = cxCalloc(allocator, initial_capacity, item_size);
universe@676:     if (list->data == NULL) {
universe@676:         cxFree(allocator, list);
universe@676:         return NULL;
universe@676:     }
universe@676: 
universe@628:     // configure the reallocator
universe@610:     list->reallocator.realloc = cx_arl_realloc;
universe@610:     list->reallocator.ptr1 = (void *) allocator;
universe@610: 
universe@607:     return (CxList *) list;
universe@606: }