Thu, 23 May 2024 23:24:37 +0200
close branch ucx-3.1
/* * 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 "cx/compare.h" #include <assert.h> #include <string.h> // Default array reallocator static void *cx_array_default_realloc( void *array, size_t capacity, size_t elem_size, __attribute__((__unused__)) struct cx_array_reallocator_s *alloc ) { return realloc(array, capacity * elem_size); } struct cx_array_reallocator_s cx_array_default_reallocator_impl = { cx_array_default_realloc, NULL, NULL, 0, 0 }; struct cx_array_reallocator_s *cx_array_default_reallocator = &cx_array_default_reallocator_impl; // LOW LEVEL ARRAY LIST FUNCTIONS enum cx_array_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_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_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_SUCCESS; } #ifndef CX_ARRAY_SWAP_SBO_SIZE #define CX_ARRAY_SWAP_SBO_SIZE 128 #endif unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE; 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->collection.simple_destructor) { for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_simple_destructor(list, ptr); ptr += list->collection.elem_size; } } if (list->collection.advanced_destructor) { for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_advanced_destructor(list, ptr); ptr += list->collection.elem_size; } } cxFree(list->collection.allocator, arl->data); cxFree(list->collection.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->collection.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->collection.size) { char const *first_to_move = (char const *) arl->data; first_to_move += index * list->collection.elem_size; size_t elems_to_move = list->collection.size - index; size_t start_of_moved = index + n; if (CX_ARRAY_SUCCESS != cx_array_copy( &arl->data, &list->collection.size, &arl->capacity, start_of_moved, first_to_move, list->collection.elem_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_SUCCESS == cx_array_copy( &arl->data, &list->collection.size, &arl->capacity, index, array, list->collection.elem_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_iterator_s *iter, void const *elem, int prepend ) { struct cx_list_s *list = iter->src_handle.m; if (iter->index < list->collection.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->collection.elem_size; } return result; } else { int result = cx_arl_insert_element(list, list->collection.size, elem); iter->index = list->collection.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->collection.size) { return 1; } // content destruction cx_invoke_destructor(list, ((char *) arl->data) + index * list->collection.elem_size); // short-circuit removal of last element if (index == list->collection.size - 1) { list->collection.size--; return 0; } // just move the elements starting at index to the left int result = cx_array_copy( &arl->data, &list->collection.size, &arl->capacity, index, ((char *) arl->data) + (index + 1) * list->collection.elem_size, list->collection.elem_size, list->collection.size - index - 1, &arl->reallocator ); // cx_array_copy cannot fail, array cannot grow assert(result == 0); // decrease the size list->collection.size--; return 0; } static void cx_arl_clear(struct cx_list_s *list) { if (list->collection.size == 0) return; cx_array_list *arl = (cx_array_list *) list; char *ptr = arl->data; if (list->collection.simple_destructor) { for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_simple_destructor(list, ptr); ptr += list->collection.elem_size; } } if (list->collection.advanced_destructor) { for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_advanced_destructor(list, ptr); ptr += list->collection.elem_size; } } memset(arl->data, 0, list->collection.size * list->collection.elem_size); list->collection.size = 0; } static int cx_arl_swap( struct cx_list_s *list, size_t i, size_t j ) { if (i >= list->collection.size || j >= list->collection.size) return 1; cx_array_list *arl = (cx_array_list *) list; cx_array_swap(arl->data, list->collection.elem_size, i, j); return 0; } static void *cx_arl_at( struct cx_list_s const *list, size_t index ) { if (index < list->collection.size) { cx_array_list const *arl = (cx_array_list const *) list; char *space = arl->data; return space + index * list->collection.elem_size; } else { return NULL; } } static ssize_t cx_arl_find_remove( struct cx_list_s *list, void const *elem, bool remove ) { assert(list->collection.cmpfunc != NULL); assert(list->collection.size < SIZE_MAX / 2); char *cur = ((cx_array_list const *) list)->data; for (ssize_t i = 0; i < (ssize_t) list->collection.size; i++) { if (0 == list->collection.cmpfunc(elem, cur)) { if (remove) { if (0 == cx_arl_remove(list, i)) { return i; } else { return -1; } } else { return i; } } cur += list->collection.elem_size; } return -1; } static void cx_arl_sort(struct cx_list_s *list) { assert(list->collection.cmpfunc != NULL); qsort(((cx_array_list *) list)->data, list->collection.size, list->collection.elem_size, list->collection.cmpfunc ); } static int cx_arl_compare( struct cx_list_s const *list, struct cx_list_s const *other ) { assert(list->collection.cmpfunc != NULL); if (list->collection.size == other->collection.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->collection.size; i++) { int d = list->collection.cmpfunc(left, right); if (d != 0) { return d; } left += list->collection.elem_size; right += other->collection.elem_size; } return 0; } else { return list->collection.size < other->collection.size ? -1 : 1; } } static void cx_arl_reverse(struct cx_list_s *list) { if (list->collection.size < 2) return; void *data = ((cx_array_list const *) list)->data; size_t half = list->collection.size / 2; for (size_t i = 0; i < half; i++) { cx_array_swap(data, list->collection.elem_size, i, list->collection.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.c; return iter->index < list->collection.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_s *iter = it; if (iter->base.remove) { iter->base.remove = false; cx_arl_remove(iter->src_handle.m, iter->index); } else { iter->index++; iter->elem_handle = ((char *) iter->elem_handle) + ((struct cx_list_s const *) iter->src_handle.c)->collection.elem_size; } } static void cx_arl_iter_prev(void *it) { struct cx_iterator_s *iter = it; cx_array_list const* list = iter->src_handle.c; if (iter->base.remove) { iter->base.remove = false; cx_arl_remove(iter->src_handle.m, iter->index); } iter->index--; if (iter->index < list->base.collection.size) { iter->elem_handle = ((char *) list->data) + iter->index * list->base.collection.elem_size; } } 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.c = list; iter.elem_handle = cx_arl_at(list, index); iter.elem_size = list->collection.elem_size; iter.elem_count = list->collection.size; 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.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_remove, cx_arl_sort, cx_arl_compare, cx_arl_reverse, cx_arl_iterator, }; CxList *cxArrayListCreate( CxAllocator const *allocator, cx_compare_func comparator, size_t elem_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.collection.allocator = allocator; list->capacity = initial_capacity; if (elem_size > 0) { list->base.collection.elem_size = elem_size; list->base.collection.cmpfunc = comparator; } else { elem_size = sizeof(void *); list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; cxListStorePointers((CxList *) list); } // allocate the array after the real elem_size is known list->data = cxCalloc(allocator, initial_capacity, elem_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; }