diff -r b1eac0878ce7 -r 18892c0a9adc ucx/array.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ucx/array.c	Sat Dec 05 11:54:58 2020 +0100
@@ -0,0 +1,467 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
+ *
+ * Copyright 2019 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.
+ */
+
+#define _GNU_SOURCE /* we want to use qsort_r(), if available */
+#define __STDC_WANT_LIB_EXT1__ 1 /* use qsort_s, if available */
+
+
+#include "ucx/array.h"
+#include "ucx/utils.h"
+
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+
+#ifndef UCX_ARRAY_DISABLE_QSORT
+#ifdef __GLIBC__
+#if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)
+#define ucx_array_sort_impl qsort_r
+#endif /* glibc version >= 2.8 */
+#elif /* not  __GLIBC__ */ defined(__APPLE__) || defined(__FreeBSD__)
+#define ucx_array_sort_impl ucx_qsort_r
+#define USE_UCX_QSORT_R
+#elif /* not (__APPLE || __FreeBSD__) */ defined(__sun)
+#if __STDC_VERSION__ >= 201112L
+#define ucx_array_sort_impl qsort_s
+#endif
+#endif /* __GLIBC__, __APLE__, __FreeBSD__, __sun */
+#endif /* UCX_ARRAY_DISABLE_QSORT */
+
+#ifndef ucx_array_sort_impl
+#define ucx_array_sort_impl ucx_mergesort
+#endif
+
+static int ucx_array_ensurecap(UcxArray *array, size_t reqcap) {
+    size_t required_capacity = array->capacity;
+    while (reqcap > required_capacity) {
+        if (required_capacity * 2 < required_capacity)
+            return 1;
+        required_capacity <<= 1;
+    }
+    if (ucx_array_reserve(array, required_capacity)) {
+        return 1;
+    }
+    return 0;
+}
+
+int ucx_array_util_set_a(UcxAllocator* alloc, void** array, size_t* capacity,
+    size_t elmsize, size_t index, void* data) {
+    
+    if(!alloc || !capacity || !array) {
+        errno = EINVAL;
+        return 1;
+    }
+    
+    size_t newcapacity = *capacity;
+    while(index >= newcapacity) {
+        if(ucx_szmul(newcapacity, 2, &newcapacity)) {
+            errno = EOVERFLOW;
+            return 1;
+        }        
+    }
+
+    size_t memlen, offset;
+    if(ucx_szmul(newcapacity, elmsize, &memlen)) {
+        errno = EOVERFLOW;
+        return 1;
+    }
+    /* we don't need to check index*elmsize - it is smaller than memlen */
+    
+    
+    void* newptr = alrealloc(alloc, *array, memlen);
+    if(newptr == NULL) {
+        errno = ENOMEM; /* we cannot assume that every allocator sets this */
+        return 1;
+    }
+    *array = newptr;
+    *capacity = newcapacity;
+    
+    
+    char* dest = *array;
+    dest += elmsize*index;
+    memcpy(dest, data, elmsize);
+    
+    return 0;
+}
+
+int ucx_array_util_setptr_a(UcxAllocator* alloc, void** array, size_t* capacity,
+    size_t index, void* data) {
+    
+    return ucx_array_util_set_a(alloc, array, capacity, sizeof(void*),
+            index, &data);
+}
+
+UcxArray* ucx_array_new(size_t capacity, size_t elemsize) {
+    return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
+}
+
+UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize,
+        UcxAllocator* allocator) {
+    UcxArray* array = almalloc(allocator, sizeof(UcxArray));
+    if(array) {
+        ucx_array_init_a(array, capacity, elemsize, allocator);
+    }
+    return array;
+}
+
+void ucx_array_init(UcxArray* array, size_t capacity, size_t elemsize) {
+    ucx_array_init_a(array, capacity, elemsize, ucx_default_allocator());
+}
+
+void ucx_array_init_a(UcxArray* array, size_t capacity, size_t elemsize,
+        UcxAllocator* allocator) {
+    
+    array->allocator = allocator;
+    array->elemsize = elemsize;
+    array->size = 0;
+    array->data = alcalloc(allocator, capacity, elemsize);
+    
+    if (array->data) {
+        array->capacity = capacity;
+    } else {
+        array->capacity = 0;
+    }
+}
+
+int ucx_array_clone(UcxArray* dest, UcxArray const* src) {
+    if (ucx_array_ensurecap(dest, src->capacity)) {
+        return 1;
+    }
+    
+    dest->elemsize = src->elemsize;
+    dest->size = src->size;
+    
+    if (dest->data) {
+        memcpy(dest->data, src->data, src->size*src->elemsize);
+    }
+    
+    return 0;
+}
+
+int ucx_array_equals(UcxArray const *array1, UcxArray const *array2,
+        cmp_func cmpfnc, void* data) {
+    
+    if (array1->size != array2->size || array1->elemsize != array2->elemsize) {
+        return 0;
+    } else {
+        if (array1->size == 0)
+            return 1;
+        
+        size_t elemsize;
+        if (cmpfnc == NULL) {
+            cmpfnc = ucx_cmp_mem;
+            elemsize = array1->elemsize;
+            data = &elemsize;
+        }
+        
+        for (size_t i = 0 ; i < array1->size ; i++) {
+            int r = cmpfnc(
+                    ucx_array_at(array1, i),
+                    ucx_array_at(array2, i),
+                    data);
+            if (r != 0)
+                return 0;
+        }
+        return 1;
+    }
+}
+
+void ucx_array_destroy(UcxArray *array) {
+    if(array->data)
+        alfree(array->allocator, array->data);
+    array->data = NULL;
+    array->capacity = array->size = 0;
+}
+
+void ucx_array_free(UcxArray *array) {
+    ucx_array_destroy(array);
+    alfree(array->allocator, array);
+}
+
+int ucx_array_append_from(UcxArray *array, void *data, size_t count) {
+    if (ucx_array_ensurecap(array, array->size + count))
+        return 1;
+    
+    void* dest = ucx_array_at(array, array->size);
+    if (data) {
+        memcpy(dest, data, array->elemsize*count);
+    } else {
+        memset(dest, 0, array->elemsize*count);
+    }
+    array->size += count;
+    
+    return 0;
+}
+
+int ucx_array_prepend_from(UcxArray *array, void *data, size_t count) {
+    if (ucx_array_ensurecap(array, array->size + count))
+        return 1;
+    
+    if (array->size > 0) {
+        void *dest = ucx_array_at(array, count);
+        memmove(dest, array->data, array->elemsize*array->size);
+    }
+    
+    if (data) {
+        memcpy(array->data, data, array->elemsize*count);
+    } else {
+        memset(array->data, 0, array->elemsize*count);
+    }
+    array->size += count;
+        
+    return 0;
+}
+
+int ucx_array_set_from(UcxArray *array, size_t index,
+        void *data, size_t count) {
+    if (ucx_array_ensurecap(array, index + count))
+        return 1;
+    
+    if (index+count > array->size) {
+        array->size = index+count;
+    }
+    
+    void *dest = ucx_array_at(array, index);
+    if (data) {
+        memcpy(dest, data, array->elemsize*count);
+    } else {
+        memset(dest, 0, array->elemsize*count);
+    }
+    
+    return 0;
+}
+
+int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
+    
+    if (array1->elemsize != array2->elemsize)
+        return 1;
+    
+    size_t capacity = array1->capacity+array2->capacity;
+        
+    if (array1->capacity < capacity) {
+        if (ucx_array_reserve(array1, capacity)) {
+            return 1;
+        }
+    }
+    
+    void* dest = ucx_array_at(array1, array1->size);
+    memcpy(dest, array2->data, array2->size*array2->elemsize);
+    
+    array1->size += array2->size;
+    
+    return 0;
+}
+
+void *ucx_array_at(UcxArray const *array, size_t index) {
+    char* memory = array->data;
+    char* loc = memory + index*array->elemsize;
+    return loc;
+}
+
+size_t ucx_array_find(UcxArray const *array, void *elem,
+        cmp_func cmpfnc, void *data) {
+    
+    size_t elemsize;
+    if (cmpfnc == NULL) {
+        cmpfnc = ucx_cmp_mem;
+        elemsize = array->elemsize;
+        data = &elemsize;
+    }
+
+    if (array->size > 0) {
+        for (size_t i = 0 ; i < array->size ; i++) {
+            void* ptr = ucx_array_at(array, i);
+            if (cmpfnc(ptr, elem, data) == 0) {
+                return i;
+            }
+        }
+        return array->size;
+    } else {
+        return 0;
+    }
+}
+
+int ucx_array_contains(UcxArray const *array, void *elem,
+        cmp_func cmpfnc, void *data) {
+    return ucx_array_find(array, elem, cmpfnc, data) != array->size;
+}
+
+static void ucx_mergesort_merge(void *arrdata,size_t elemsize,
+        cmp_func cmpfnc, void *data,
+        size_t start, size_t mid, size_t end) { 
+    
+    char* array = arrdata;
+    
+    size_t rightstart = mid + 1; 
+  
+    if (cmpfnc(array + mid*elemsize,
+            array + rightstart*elemsize, data) <= 0) {
+        /* already sorted */
+        return;
+    }
+  
+    /* we need memory for one element */
+    void *value = malloc(elemsize);
+    
+    while (start <= mid && rightstart <= end) { 
+        if (cmpfnc(array + start*elemsize,
+                array + rightstart*elemsize, data) <= 0) { 
+            start++; 
+        } else {
+            /* save the value from the right */
+            memcpy(value, array + rightstart*elemsize, elemsize);
+                        
+            /* shift all left elements one element to the right */
+            size_t shiftcount = rightstart-start;
+            void *startptr = array + start*elemsize;
+            void *dest = array + (start+1)*elemsize;
+            memmove(dest, startptr, shiftcount*elemsize);
+            
+            /* bring the first value from the right to the left */
+            memcpy(startptr, value, elemsize);
+  
+            start++; 
+            mid++; 
+            rightstart++; 
+        }
+    }
+    
+    /* free the temporary memory */
+    free(value);
+} 
+  
+static void ucx_mergesort_impl(void *arrdata, size_t elemsize,
+        cmp_func cmpfnc, void *data, size_t l, size_t r) { 
+    if (l < r) {
+        size_t m = l + (r - l) / 2; 
+  
+        ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m); 
+        ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r); 
+        ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);
+    } 
+}
+
+static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,
+        cmp_func cmpfnc, void *data) {
+    
+    ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);
+}
+
+#ifdef USE_UCX_QSORT_R
+struct cmpfnc_swapargs_info {
+    cmp_func func;
+    void *data;
+};
+
+static int cmp_func_swap_args(void *data, const void *x, const void *y) {
+    struct cmpfnc_swapargs_info* info = data;
+    return info->func(x, y, info->data);
+}
+
+static void ucx_qsort_r(void *array, size_t count, size_t elemsize,
+		     cmp_func cmpfnc, void *data) {
+    struct cmpfnc_swapargs_info info;
+    info.func = cmpfnc;
+    info.data = data;
+    qsort_r(array, count, elemsize, &info, cmp_func_swap_args);
+}
+#endif /* USE_UCX_QSORT_R */
+
+void ucx_array_sort(UcxArray* array, cmp_func cmpfnc, void *data) {
+    ucx_array_sort_impl(array->data, array->size, array->elemsize,
+            cmpfnc, data);
+}
+
+void ucx_array_remove(UcxArray *array, size_t index) {
+    array->size--;
+    if (index < array->size) {
+        void* dest = ucx_array_at(array, index);
+        void* src = ucx_array_at(array, index+1);
+        memmove(dest, src, (array->size - index)*array->elemsize);
+    }
+}
+
+void ucx_array_remove_fast(UcxArray *array, size_t index) {
+    array->size--;
+    if (index < array->size) {       
+        void* dest = ucx_array_at(array, index);
+        void* src = ucx_array_at(array, array->size);
+        memcpy(dest, src, array->elemsize);
+    }
+}
+
+int ucx_array_shrink(UcxArray* array) {
+    void* newptr = alrealloc(array->allocator, array->data,
+                array->size*array->elemsize);
+    if (newptr) {
+        array->data = newptr;
+        array->capacity = array->size;
+        return 0;
+    } else {
+        return 1;
+    }
+}
+
+int ucx_array_resize(UcxArray* array, size_t capacity) {
+    if (array->capacity >= capacity) {
+        void* newptr = alrealloc(array->allocator, array->data,
+                capacity*array->elemsize);
+        if (newptr) {
+            array->data = newptr;
+            array->capacity = capacity;
+            if (array->size > array->capacity) {
+                array->size = array->capacity;
+            }
+            return 0;
+        } else {
+            return 1;
+        }
+    } else {
+        return ucx_array_reserve(array, capacity);
+    }
+}
+
+int ucx_array_reserve(UcxArray* array, size_t capacity) {
+    if (array->capacity > capacity) {
+        return 0;
+    } else {
+        void* newptr = alrealloc(array->allocator, array->data,
+                capacity*array->elemsize);
+        if (newptr) {
+            array->data = newptr;
+            array->capacity = capacity;
+            return 0;
+        } else {
+            return 1;
+        }
+    }
+}
+
+int ucx_array_grow(UcxArray* array, size_t count) {
+    return ucx_array_reserve(array, array->size+count);
+}