universe@103: /*
universe@103:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@103:  *
universe@334:  * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved.
universe@103:  *
universe@103:  * Redistribution and use in source and binary forms, with or without
universe@103:  * modification, are permitted provided that the following conditions are met:
universe@103:  *
universe@103:  *   1. Redistributions of source code must retain the above copyright
universe@103:  *      notice, this list of conditions and the following disclaimer.
universe@103:  *
universe@103:  *   2. Redistributions in binary form must reproduce the above copyright
universe@103:  *      notice, this list of conditions and the following disclaimer in the
universe@103:  *      documentation and/or other materials provided with the distribution.
universe@103:  *
universe@103:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@103:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@103:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@103:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@103:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@103:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@103:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@103:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@103:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@103:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@103:  * POSSIBILITY OF SUCH DAMAGE.
universe@103:  */
universe@103: 
universe@345: #define _GNU_SOURCE /* we want to use qsort_r(), if available */
olaf@348: #define __STDC_WANT_LIB_EXT1__ 1 /* use qsort_s, if available */
olaf@348: 
universe@345: 
universe@334: #include "ucx/array.h"
universe@336: #include "ucx/utils.h"
universe@4: 
universe@336: #include <string.h>
universe@345: #include <stdlib.h>
universe@355: #include <errno.h>
universe@345: 
universe@345: #ifndef UCX_ARRAY_DISABLE_QSORT
universe@346: #ifdef __GLIBC__
universe@345: #if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)
universe@345: #define ucx_array_sort_impl qsort_r
universe@345: #endif /* glibc version >= 2.8 */
universe@346: #elif /* not  __GLIBC__ */ defined(__APPLE__) || defined(__FreeBSD__)
universe@345: #define ucx_array_sort_impl ucx_qsort_r
universe@345: #define USE_UCX_QSORT_R
olaf@348: #elif /* not (__APPLE || __FreeBSD__) */ defined(__sun)
olaf@348: #if __STDC_VERSION__ >= 201112L
olaf@348: #define ucx_array_sort_impl qsort_s
olaf@348: #endif
olaf@348: #endif /* __GLIBC__, __APLE__, __FreeBSD__, __sun */
universe@345: #endif /* UCX_ARRAY_DISABLE_QSORT */
universe@345: 
universe@345: #ifndef ucx_array_sort_impl
universe@345: #define ucx_array_sort_impl ucx_mergesort
universe@345: #endif
universe@334: 
universe@354: static int ucx_array_ensurecap(UcxArray *array, size_t reqcap) {
universe@354:     size_t required_capacity = array->capacity;
universe@354:     while (reqcap > required_capacity) {
universe@354:         if (required_capacity * 2 < required_capacity)
universe@354:             return 1;
universe@354:         required_capacity <<= 1;
universe@354:     }
universe@354:     if (ucx_array_reserve(array, required_capacity)) {
universe@354:         return 1;
universe@354:     }
universe@354: }
universe@354: 
universe@355: int ucx_array_util_set_a(UcxAllocator* alloc, void** array, size_t* capacity,
universe@355:     size_t elmsize, size_t index, ...) {
universe@355:     
universe@355:     if(!alloc || !capacity || !array) {
universe@355:         errno = EINVAL;
universe@355:         return 1;
universe@355:     }
universe@355:     
universe@355:     size_t newcapacity = *capacity;
universe@355:     while(index >= newcapacity) {
universe@355:         if(ucx_szmul(newcapacity, 2, &newcapacity)) {
universe@355:             errno = EOVERFLOW;
universe@355:             return 1;
universe@355:         }        
universe@355:     }
universe@355: 
universe@355:     size_t memlen, offset;
universe@355:     if(ucx_szmul(newcapacity, elmsize, &memlen)) {
universe@355:         errno = EOVERFLOW;
universe@355:         return 1;
universe@355:     }
universe@355:     /* we don't need to check index*elmsize - it is smaller than memlen */
universe@355:     
universe@355:     
universe@355:     void* newptr = alrealloc(alloc, *array, memlen);
universe@355:     if(newptr == NULL) {
universe@355:         errno = ENOMEM; /* we cannot assume that every allocator sets this */
universe@355:         return 1;
universe@355:     }
universe@355:     *array = newptr;
universe@355:     *capacity = newcapacity;
universe@355:     
universe@355:     
universe@355:     char* dest = *array;
universe@355:     dest += elmsize*index;
universe@355: 
universe@355:     va_list ap;
universe@355:     va_start(ap, index);
universe@355:     int elem = va_arg(ap, int);    
universe@355:     memcpy(dest, &elem, elmsize);
universe@355:     va_end(ap);
universe@355:     
universe@355:     return 0;
universe@355: }
universe@355: 
universe@334: UcxArray ucx_array_new(size_t capacity, size_t elemsize) {
universe@334:     return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
universe@125: }
universe@125: 
universe@334: UcxArray ucx_array_new_a(size_t capacity, size_t elemsize,
universe@334:         UcxAllocator* allocator) {
universe@334:     UcxArray array;
universe@334:     
universe@336:     array.allocator = allocator;
universe@336:     array.elemsize = elemsize;
universe@336:     array.size = 0;
universe@336:     array.data = alcalloc(allocator, capacity, elemsize);
universe@336:     
universe@336:     if (array.data) {
universe@336:         array.capacity = capacity;
universe@336:     } else {
universe@336:         array.capacity = 0;
universe@336:     }
universe@336:     
universe@334:     return array;
universe@18: }
universe@18: 
universe@334: UcxArray ucx_array_clone(UcxArray array) {
universe@334:     UcxArray clone;
universe@18:     
universe@336:     clone.allocator = array.allocator;
universe@336:     clone.elemsize = array.elemsize;
universe@336:     clone.size = array.size;
universe@336:     clone.data = alcalloc(array.allocator, array.capacity, array.elemsize);
universe@336:     
universe@336:     if (clone.data) {
universe@336:         clone.capacity = array.capacity;
universe@336:         memcpy(clone.data, array.data, array.size*array.elemsize);
universe@336:     } else {
universe@336:         clone.capacity = clone.size = 0;
universe@336:     }
universe@336:     
universe@334:     return clone;
universe@18: }
universe@18: 
universe@334: int ucx_array_equals(UcxArray array1, UcxArray array2,
universe@334:         cmp_func cmpfnc, void* data) {
universe@334:     
universe@336:     if (array1.size != array2.size || array1.elemsize != array2.elemsize) {
universe@336:         return 0;
universe@336:     } else {
universe@336:         if (array1.size == 0)
universe@336:             return 1;
universe@336:         
universe@336:         if (cmpfnc == NULL) {
universe@336:             cmpfnc = ucx_cmp_mem;
universe@336:             data = &array1.elemsize;
universe@336:         }
universe@336:         
universe@336:         for (size_t i = 0 ; i < array1.size ; i++) {
universe@336:             int r = cmpfnc(
universe@336:                     ucx_array_at(array1, i),
universe@336:                     ucx_array_at(array2, i),
universe@336:                     data);
universe@336:             if (r != 0)
universe@336:                 return 0;
universe@336:         }
universe@336:         return 1;
universe@336:     }
universe@125: }
universe@125: 
universe@353: void ucx_array_destroy(UcxArray *array) {
universe@336:     alfree(array->allocator, array->data);
universe@336:     array->data = NULL;
universe@336:     array->capacity = array->size = 0;
universe@8: }
universe@8: 
universe@354: int ucx_array_append_from(UcxArray *array, void *data, size_t count) {
universe@354:     if (ucx_array_ensurecap(array, array->size + count))
universe@354:         return 1;
universe@354:     
universe@354:     void* dest = ucx_array_at(*array, array->size);
universe@354:     if (data) {
universe@354:         memcpy(dest, data, array->elemsize*count);
universe@354:     } else {
universe@354:         memset(dest, 0, array->elemsize*count);
universe@354:     }
universe@354:     array->size += count;
universe@354:     
universe@354:     return 0;
universe@354: }
universe@354: 
universe@354: int ucx_array_prepend_from(UcxArray *array, void *data, size_t count) {
universe@354:     if (ucx_array_ensurecap(array, array->size + count))
universe@354:         return 1;
universe@354:     
universe@354:     if (array->size > 0) {
universe@354:         void *dest = ucx_array_at(*array, count);
universe@354:         memmove(dest, array->data, array->elemsize*array->size);
universe@336:     }
universe@336:     
universe@336:     if (data) {
universe@354:         memcpy(array->data, data, array->elemsize*count);
universe@336:     } else {
universe@354:         memset(array->data, 0, array->elemsize*count);
universe@354:     }
universe@354:     array->size += count;
universe@354:         
universe@354:     return 0;
universe@354: }
universe@354: 
universe@354: int ucx_array_set_from(UcxArray *array, size_t index,
universe@354:         void *data, size_t count) {
universe@354:     if (ucx_array_ensurecap(array, index + count))
universe@354:         return 1;
universe@354:     
universe@354:     if (index+count > array->size) {
universe@354:         array->size = index+count;
universe@354:     }
universe@354:     
universe@354:     void *dest = ucx_array_at(*array, index);
universe@354:     if (data) {
universe@354:         memcpy(dest, data, array->elemsize*count);
universe@354:     } else {
universe@354:         memset(dest, 0, array->elemsize*count);
universe@336:     }
universe@336:     
universe@336:     return 0;
universe@211: }
universe@211: 
universe@354: int ucx_array_appendv(UcxArray *array, ...) {
universe@354:     va_list ap;
universe@354:     va_start(ap, array);
universe@354:     int elem = va_arg(ap, int);
universe@354:     int ret = ucx_array_append_from(array, &elem, 1);
universe@354:     va_end(ap);
universe@354:     return ret;
universe@125: }
universe@125: 
universe@354: int ucx_array_prependv(UcxArray *array, ...) {
universe@354:     va_list ap;
universe@354:     va_start(ap, array);
universe@354:     int elem = va_arg(ap, int);
universe@354:     int ret = ucx_array_prepend_from(array, &elem, 1);
universe@354:     va_end(ap);
universe@354:     return ret;
universe@354: }
universe@354: 
universe@354: int ucx_array_setv(UcxArray *array, size_t index, ...) {
universe@354:     va_list ap;
universe@354:     va_start(ap, index);
universe@354:     int elem = va_arg(ap, int);
universe@354:     int ret = ucx_array_set_from(array, index, &elem, 1);
universe@354:     va_end(ap);
universe@354:     return ret;
universe@337: }
universe@337: 
universe@334: int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
universe@336:     
universe@336:     if (array1->elemsize != array2->elemsize)
universe@336:         return 1;
universe@336:     
universe@336:     size_t capacity = array1->capacity+array2->capacity;
universe@336:         
universe@336:     if (array1->capacity < capacity) {
universe@336:         if (ucx_array_reserve(array1, capacity)) {
universe@336:             return 1;
universe@336:         }
universe@336:     }
universe@336:     
universe@336:     void* dest = ucx_array_at(*array1, array1->size);
universe@336:     memcpy(dest, array2->data, array2->size*array2->elemsize);
universe@336:     
universe@336:     array1->size += array2->size;
universe@336:     
universe@336:     return 0;
universe@7: }
universe@7: 
universe@334: void *ucx_array_at(UcxArray array, size_t index) {
universe@336:     char* memory = array.data;
universe@336:     char* loc = memory + index*array.elemsize;
universe@336:     return loc;
universe@125: }
universe@125: 
universe@334: size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
universe@7:     
universe@336:     if (cmpfnc == NULL) {
universe@336:         cmpfnc = ucx_cmp_mem;
universe@336:         data = &array.elemsize;
universe@336:     }
universe@336: 
universe@336:     if (array.size > 0) {
universe@336:         for (size_t i = 0 ; i < array.size ; i++) {
universe@336:             void* ptr = ucx_array_at(array, i);
universe@336:             if (cmpfnc(ptr, elem, data) == 0) {
universe@336:                 return i;
universe@336:             }
universe@336:         }
universe@336:         return array.size;
universe@336:     } else {
universe@336:         return 0;
universe@336:     }
universe@7: }
universe@7: 
universe@334: int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {
universe@334:     return ucx_array_find(array, elem, cmpfnc, data) != array.size;
universe@7: }
universe@7: 
universe@345: static void ucx_mergesort_merge(void *arrdata,size_t elemsize,
universe@345:         cmp_func cmpfnc, void *data,
universe@336:         size_t start, size_t mid, size_t end) { 
universe@336:     
universe@345:     char* array = arrdata;
universe@345:     
universe@336:     size_t rightstart = mid + 1; 
universe@336:   
universe@345:     if (cmpfnc(array + mid*elemsize,
universe@345:             array + rightstart*elemsize, data) <= 0) {
universe@336:         /* already sorted */
universe@336:         return;
universe@336:     }
universe@336:   
universe@342:     /* we need memory for one element */
universe@345:     void *value = malloc(elemsize);
universe@336:     
universe@336:     while (start <= mid && rightstart <= end) { 
universe@345:         if (cmpfnc(array + start*elemsize,
universe@345:                 array + rightstart*elemsize, data) <= 0) { 
universe@336:             start++; 
universe@336:         } else {
universe@342:             /* save the value from the right */
universe@345:             memcpy(value, array + rightstart*elemsize, elemsize);
universe@336:                         
universe@342:             /* shift all left elements one element to the right */
universe@336:             size_t shiftcount = rightstart-start;
universe@345:             void *startptr = array + start*elemsize;
universe@345:             void *dest = array + (start+1)*elemsize;
universe@345:             memmove(dest, startptr, shiftcount*elemsize);
universe@336:             
universe@342:             /* bring the first value from the right to the left */
universe@345:             memcpy(startptr, value, elemsize);
universe@336:   
universe@336:             start++; 
universe@336:             mid++; 
universe@336:             rightstart++; 
universe@336:         }
universe@336:     }
universe@336:     
universe@342:     /* free the temporary memory */
universe@336:     free(value);
universe@336: } 
universe@336:   
universe@345: static void ucx_mergesort_impl(void *arrdata, size_t elemsize,
universe@345:         cmp_func cmpfnc, void *data, size_t l, size_t r) { 
universe@336:     if (l < r) {
universe@336:         size_t m = l + (r - l) / 2; 
universe@336:   
universe@345:         ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m); 
universe@345:         ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r); 
universe@345:         ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);
universe@336:     } 
universe@336: }
universe@336: 
universe@345: static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,
universe@345:         cmp_func cmpfnc, void *data) {
universe@345:     
universe@345:     ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);
universe@345: }
universe@345: 
universe@345: #ifdef USE_UCX_QSORT_R
universe@345: struct cmpfnc_swapargs_info {
universe@345:     cmp_func func;
universe@345:     void *data;
universe@345: };
universe@345: 
universe@345: static int cmp_func_swap_args(void *data, const void *x, const void *y) {
olaf@348:     cmpfnc_swapargs_info* info = data;
universe@345:     return info->func(x, y, info->data);
universe@345: }
universe@345: 
universe@345: static void ucx_qsort_r(void *array, size_t count, size_t elemsize,
universe@345: 		     cmp_func cmpfnc, void *data) {
universe@345:     struct cmpfnc_swapargs_info info;
universe@345:     info.func = cmpfnc;
universe@345:     info.data = data;
universe@345:     qsort_r(array, count, elemsize, &info, cmp_func_swap_args);
universe@345: }
universe@345: #endif /* USE_UCX_QSORT_R */
universe@345: 
universe@345: void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {
universe@345:     ucx_array_sort_impl(array.data, array.size, array.elemsize, cmpfnc, data);
universe@7: }
universe@7: 
universe@334: void ucx_array_remove(UcxArray *array, size_t index) {
universe@336:     array->size--;
universe@336:     if (index < array->size) {
universe@336:         void* dest = ucx_array_at(*array, index);
universe@336:         void* src = ucx_array_at(*array, index+1);
universe@336:         memmove(dest, src, (array->size - index)*array->elemsize);
universe@336:     }
universe@123: }
universe@123: 
universe@334: void ucx_array_remove_fast(UcxArray *array, size_t index) {
universe@336:     array->size--;
universe@336:     if (index < array->size) {       
universe@336:         void* dest = ucx_array_at(*array, index);
universe@336:         void* src = ucx_array_at(*array, array->size);
universe@336:         memcpy(dest, src, array->elemsize);
universe@336:     }
universe@7: }
universe@7: 
universe@334: int ucx_array_shrink(UcxArray* array) {
universe@336:     void* newptr = alrealloc(array->allocator, array->data,
universe@336:                 array->size*array->elemsize);
universe@336:     if (newptr) {
universe@336:         array->data = newptr;
universe@336:         array->capacity = array->size;
universe@336:         return 0;
universe@336:     } else {
universe@336:         return 1;
universe@336:     }
universe@123: }
universe@123: 
universe@334: int ucx_array_resize(UcxArray* array, size_t capacity) {
universe@336:     if (array->capacity >= capacity) {
universe@336:         void* newptr = alrealloc(array->allocator, array->data,
universe@336:                 capacity*array->elemsize);
universe@336:         if (newptr) {
universe@336:             array->data = newptr;
universe@336:             array->capacity = capacity;
universe@336:             if (array->size > array->capacity) {
universe@336:                 array->size = array->capacity;
universe@336:             }
universe@336:             return 0;
universe@336:         } else {
universe@336:             return 1;
universe@336:         }
universe@336:     } else {
universe@336:         return ucx_array_reserve(array, capacity);
universe@336:     }
universe@87: }
universe@87: 
universe@334: int ucx_array_reserve(UcxArray* array, size_t capacity) {
universe@336:     if (array->capacity > capacity) {
universe@336:         return 0;
universe@336:     } else {
universe@336:         void* newptr = alrealloc(array->allocator, array->data,
universe@336:                 capacity*array->elemsize);
universe@336:         if (newptr) {
universe@336:             array->data = newptr;
universe@336:             array->capacity = capacity;
universe@336:             return 0;
universe@336:         } else {
universe@336:             return 1;
universe@336:         }
universe@336:     }
universe@7: }