Fri, 05 Jul 2019 15:07:43 +0200
fixes doxygen doc
/* * 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. */ #include "ucx/array.h" #include "ucx/utils.h" #include <string.h> 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; 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; } return array; } UcxArray ucx_array_clone(UcxArray array) { UcxArray clone; clone.allocator = array.allocator; clone.elemsize = array.elemsize; clone.size = array.size; clone.data = alcalloc(array.allocator, array.capacity, array.elemsize); if (clone.data) { clone.capacity = array.capacity; memcpy(clone.data, array.data, array.size*array.elemsize); } else { clone.capacity = clone.size = 0; } return clone; } int ucx_array_equals(UcxArray array1, UcxArray array2, cmp_func cmpfnc, void* data) { if (array1.size != array2.size || array1.elemsize != array2.elemsize) { return 0; } else { if (array1.size == 0) return 1; if (cmpfnc == NULL) { cmpfnc = ucx_cmp_mem; data = &array1.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_free(UcxArray *array) { alfree(array->allocator, array->data); array->data = NULL; array->capacity = array->size = 0; } int ucx_array_append(UcxArray *array, void *data) { if (array->size == array->capacity) { if (ucx_array_reserve(array, array->capacity*2)) { return 1; } } void* dest = ucx_array_at(*array, array->size++); if (data) { memcpy(dest, data, array->elemsize); } else { memset(dest, 0, array->elemsize); } return 0; } int ucx_array_prepend(UcxArray *array, void *data) { if (array->size == array->capacity) { if (ucx_array_reserve(array, array->capacity*2)) { return 1; } } array->size++; if (array->size > 1) { void *dest = ucx_array_at(*array,1); memmove(dest, array->data, array->elemsize*array->size); } if (data) { memcpy(array->data, data, array->elemsize); } else { memset(array->data, 0, array->elemsize); } return 0; } int ucx_array_set(UcxArray *array, size_t index, void *data) { if (index >= array->size) { if (ucx_array_reserve(array, index+1)) { return 1; } array->size = index+1; } void *dest = ucx_array_at(*array, index); if (data) { memcpy(dest, data, array->elemsize); } else { memset(dest, 0, array->elemsize); } 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 array, size_t index) { char* memory = array.data; char* loc = memory + index*array.elemsize; return loc; } size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) { if (cmpfnc == NULL) { cmpfnc = ucx_cmp_mem; data = &array.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 array, void *elem, cmp_func cmpfnc, void *data) { return ucx_array_find(array, elem, cmpfnc, data) != array.size; } static void ucx_array_merge(UcxArray *array, cmp_func cmpfnc, void *data, size_t start, size_t mid, size_t end) { size_t rightstart = mid + 1; if (cmpfnc(ucx_array_at(*array, mid), ucx_array_at(*array, rightstart), data) <= 0) { /* already sorted */ return; } // we need memory for one element void *value = malloc(array->elemsize); while (start <= mid && rightstart <= end) { if (cmpfnc(ucx_array_at(*array, start), ucx_array_at(*array, rightstart), data) <= 0) { start++; } else { // save the value from the right memcpy(value, ucx_array_at(*array, rightstart), array->elemsize); // shift all left elements one element to the right size_t shiftcount = rightstart-start; void *startptr = ucx_array_at(*array, start); void *dest = ucx_array_at(*array, start+1); memmove(dest, startptr, shiftcount*array->elemsize); // bring the first value from the right to the left memcpy(startptr, value, array->elemsize); start++; mid++; rightstart++; } } // free the temporary memory free(value); } static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data, size_t l, size_t r) { if (l < r) { size_t m = l + (r - l) / 2; ucx_array_mergesort(array, cmpfnc, data, l, m); ucx_array_mergesort(array, cmpfnc, data, m + 1, r); ucx_array_merge(array, cmpfnc, data, l, m, r); } } void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) { ucx_array_mergesort(&array, cmpfnc, data, 0, array.size-1); } 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; } } }