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@610: #include <assert.h>
universe@610: #include <string.h>
universe@611: #include <stdint.h>
universe@606: 
universe@607: /* LOW LEVEL ARRAY LIST FUNCTIONS */
universe@607: 
universe@612: enum cx_array_copy_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@610:     /* assert pointers */
universe@610:     assert(target != NULL);
universe@610:     assert(size != NULL);
universe@610:     assert(src != NULL);
universe@607: 
universe@610:     /* determine capacity */
universe@610:     size_t cap = capacity == NULL ? *size : *capacity;
universe@610: 
universe@610:     /* check if resize is required */
universe@610:     size_t newsize = index + elem_count;
universe@610:     bool needrealloc = newsize > cap;
universe@610: 
universe@610:     /* reallocate if possible */
universe@610:     if (needrealloc) {
universe@610:         /* a reallocator and a capacity variable must be available */
universe@610:         if (reallocator == NULL || capacity == NULL) {
universe@610:             return CX_ARRAY_COPY_REALLOC_NOT_SUPPORTED;
universe@610:         }
universe@610: 
universe@611:         /* 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@625:         /* calculate new capacity (next number divisible by 16) */
universe@625:         cap = newsize - (newsize % 16) + 16;
universe@625:         assert(cap > newsize);
universe@610: 
universe@610:         /* perform reallocation */
universe@610:         void *newmem = reallocator->realloc(
universe@610:                 *target, cap, elem_size, reallocator
universe@610:         );
universe@610:         if (newmem == NULL) {
universe@610:             return CX_ARRAY_COPY_REALLOC_FAILED;
universe@610:         }
universe@610: 
universe@611:         /* repair src pointer, if necessary */
universe@611:         if (repairsrc) {
universe@611:             src = ((char *) newmem) + (srcaddr - targetaddr);
universe@611:         }
universe@611: 
universe@610:         /* store new pointer and capacity */
universe@610:         *target = newmem;
universe@610:         *capacity = cap;
universe@610:     }
universe@610: 
universe@610:     /* determine target pointer */
universe@610:     char *start = *target;
universe@610:     start += index * elem_size;
universe@610: 
universe@610:     /* copy elements and set new size */
universe@611:     memmove(start, src, elem_count * elem_size);
universe@610:     *size = newsize;
universe@610: 
universe@610:     /* return successfully */
universe@610:     return CX_ARRAY_COPY_SUCCESS;
universe@610: }
universe@607: 
universe@623: #define CX_ARRAY_SWAP_SBO_SIZE 512
universe@623: 
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@623:     /* 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@623:     /* decide if we can use the local buffer */
universe@623:     if (elem_size > CX_ARRAY_SWAP_SBO_SIZE) {
universe@623:         tmp = malloc(elem_size);
universe@623:         /* 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@623:     /* 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@623:     /* 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@623:     /* free dynamic memory, if it was needed */
universe@623:     if (tmp != sbo_mem) {
universe@623:         free(tmp);
universe@623:     }
universe@623: }
universe@623: 
universe@607: /* HIGH LEVEL ARRAY LIST FUNCTIONS */
universe@607: 
universe@607: typedef struct {
universe@607:     struct cx_list_s base;
universe@607:     void *data;
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@610:     /* retrieve the pointer to the list allocator */
universe@610:     CxAllocator const *al = alloc->ptr1;
universe@610: 
universe@610:     /* 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@607:     cxFree(list->allocator, arl->data);
universe@607: }
universe@607: 
universe@607: static int cx_arl_add(
universe@607:         struct cx_list_s *list,
universe@607:         void const *elem
universe@607: ) {
universe@610:     cx_array_list *arl = (cx_array_list *) list;
universe@610:     return cx_array_copy(
universe@610:             &arl->data,
universe@610:             &list->size,
universe@610:             &list->capacity,
universe@610:             list->size,
universe@610:             elem,
universe@610:             list->itemsize,
universe@610:             1,
universe@610:             &arl->reallocator
universe@610:     );
universe@607: }
universe@607: 
universe@607: static int cx_arl_insert(
universe@607:         struct cx_list_s *list,
universe@607:         size_t index,
universe@607:         void const *elem
universe@607: ) {
universe@611:     if (index > list->size) {
universe@611:         return 1;
universe@611:     } else if (index == list->size) {
universe@611:         return cx_arl_add(list, elem);
universe@611:     } else {
universe@611:         cx_array_list *arl = (cx_array_list *) list;
universe@611: 
universe@611:         /* move elements starting at index to the right */
universe@611:         if (cx_array_copy(
universe@611:                 &arl->data,
universe@611:                 &list->size,
universe@611:                 &list->capacity,
universe@611:                 index + 1,
universe@611:                 ((char *) arl->data) + index * list->itemsize,
universe@611:                 list->itemsize,
universe@611:                 list->size - index,
universe@611:                 &arl->reallocator
universe@611:         )) {
universe@611:             return 1;
universe@611:         }
universe@611: 
universe@611:         /* place the element */
universe@611:         memcpy(((char *) arl->data) + index * list->itemsize,
universe@611:                elem, list->itemsize);
universe@611: 
universe@611:         return 0;
universe@611:     }
universe@607: }
universe@607: 
universe@607: static int cx_arl_insert_iter(
universe@607:         struct cx_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@619:         int result = cx_arl_insert(
universe@619:                 list,
universe@619:                 iter->index + 1 - prepend,
universe@619:                 elem
universe@619:         );
universe@619:         if (result == 0 && prepend != 0) {
universe@619:             iter->index++;
universe@619:             iter->elem_handle = ((char *) iter->elem_handle) + list->itemsize;
universe@619:         }
universe@619:         return result;
universe@619:     } else {
universe@619:         int result = cx_arl_add(list, 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@613:     /* out-of-bounds check */
universe@613:     if (index >= list->size) {
universe@613:         return 1;
universe@613:     }
universe@613: 
universe@624:     /* 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@613:     /* just move the elements starting at index to the left */
universe@624:     cx_array_list *arl = (cx_array_list *) list;
universe@613:     int result = cx_array_copy(
universe@613:             &arl->data,
universe@613:             &list->size,
universe@613:             &list->capacity,
universe@613:             index,
universe@613:             ((char *) arl->data) + (index + 1) * list->itemsize,
universe@613:             list->itemsize,
universe@613:             list->size - index,
universe@613:             &arl->reallocator
universe@613:     );
universe@613:     if (result == 0) {
universe@613:         /* decrease the size */
universe@613:         list->size--;
universe@613:     }
universe@613:     return result;
universe@607: }
universe@607: 
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@610:         return space + index * list->itemsize;
universe@610:     } else {
universe@610:         return NULL;
universe@610:     }
universe@607: }
universe@607: 
universe@607: static size_t cx_arl_find(
universe@607:         struct cx_list_s const *list,
universe@607:         void const *elem
universe@607: ) {
universe@614:     char *cur = ((cx_array_list const *) list)->data;
universe@614: 
universe@614:     for (size_t i = 0; i < list->size; i++) {
universe@614:         if (0 == list->cmpfunc(elem, cur)) {
universe@614:             return i;
universe@614:         }
universe@614:         cur += list->itemsize;
universe@614:     }
universe@614: 
universe@614:     return list->size;
universe@607: }
universe@607: 
universe@607: static void cx_arl_sort(struct cx_list_s *list) {
universe@615:     qsort(((cx_array_list *) list)->data,
universe@615:           list->size,
universe@615:           list->itemsize,
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@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@622:             left += list->itemsize;
universe@622:             right += other->itemsize;
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@623:         cx_array_swap(data, list->itemsize, i, list->size - 1 - i);
universe@623:     }
universe@607: }
universe@607: 
universe@616: static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) {
universe@616:     struct cx_list_s const *list = iter->src_handle;
universe@616:     return iter->index < list->size;
universe@616: }
universe@616: 
universe@616: static void *cx_arl_iter_current(struct cx_iterator_s const *iter) {
universe@616:     return iter->elem_handle;
universe@616: }
universe@616: 
universe@616: static void cx_arl_iter_next(struct cx_iterator_s *iter) {
universe@616:     if (iter->remove) {
universe@616:         iter->remove = false;
universe@616:         cx_arl_remove(iter->src_handle, iter->index);
universe@616:     } else {
universe@616:         iter->index++;
universe@620:         iter->elem_handle =
universe@620:                 ((char *) iter->elem_handle)
universe@620:                 + ((struct cx_list_s const *) iter->src_handle)->itemsize;
universe@616:     }
universe@616: }
universe@616: 
universe@607: static struct cx_iterator_s cx_arl_iterator(
universe@607:         struct cx_list_s *list,
universe@607:         size_t index
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@616:     iter.valid = cx_arl_iter_valid;
universe@616:     iter.current = cx_arl_iter_current;
universe@616:     iter.next = cx_arl_iter_next;
universe@616:     iter.remove = 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@607:         cx_arl_add,
universe@607:         cx_arl_insert,
universe@607:         cx_arl_insert_iter,
universe@607:         cx_arl_remove,
universe@607:         cx_arl_at,
universe@607:         cx_arl_find,
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@606: CxList *cxArrayListCreate(
universe@606:         CxAllocator const *allocator,
universe@606:         CxListComparator comparator,
universe@606:         size_t item_size,
universe@606:         size_t initial_capacity
universe@606: ) {
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->data = cxCalloc(allocator, initial_capacity, item_size);
universe@607:     if (list->data == NULL) {
universe@607:         cxFree(allocator, list);
universe@607:         return NULL;
universe@607:     }
universe@607: 
universe@607:     list->base.cl = &cx_array_list_class;
universe@607:     list->base.allocator = allocator;
universe@607:     list->base.cmpfunc = comparator;
universe@607:     list->base.itemsize = item_size;
universe@607:     list->base.capacity = initial_capacity;
universe@607: 
universe@610:     /* 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: }