diff -r 809581724cc7 -r 0358f1d9c506 ucx/array_list.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ucx/array_list.c	Mon May 22 16:17:26 2023 +0200
@@ -0,0 +1,547 @@
+/*
+ * 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;
+}