--- a/src/ucx/array_list.c Sun Nov 20 12:43:44 2022 +0100 +++ b/src/ucx/array_list.c Sat Nov 26 17:07:08 2022 +0100 @@ -31,7 +31,7 @@ #include <string.h> #include <stdint.h> -/* LOW LEVEL ARRAY LIST FUNCTIONS */ +// LOW LEVEL ARRAY LIST FUNCTIONS enum cx_array_copy_result cx_array_copy( void **target, @@ -43,35 +43,37 @@ size_t elem_count, struct cx_array_reallocator_s *reallocator ) { - /* assert pointers */ + // assert pointers assert(target != NULL); assert(size != NULL); assert(src != NULL); - /* determine capacity */ + // determine capacity size_t cap = capacity == NULL ? *size : *capacity; - /* check if resize is required */ - size_t newsize = index + elem_count; + // 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 */ + // reallocate if possible if (needrealloc) { - /* a reallocator and a capacity variable must be available */ + // 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 */ + // 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; - /* increase capacity linearly */ - cap += 16; + // calculate new capacity (next number divisible by 16) + cap = newsize - (newsize % 16) + 16; + assert(cap > newsize); - /* perform reallocation */ + // perform reallocation void *newmem = reallocator->realloc( *target, cap, elem_size, reallocator ); @@ -79,29 +81,68 @@ return CX_ARRAY_COPY_REALLOC_FAILED; } - /* repair src pointer, if necessary */ + // repair src pointer, if necessary if (repairsrc) { src = ((char *) newmem) + (srcaddr - targetaddr); } - /* store new pointer and capacity */ + // store new pointer and capacity *target = newmem; *capacity = cap; } - /* determine target pointer */ + // determine target pointer char *start = *target; start += index * elem_size; - /* copy elements and set new size */ + // copy elements and set new size memmove(start, src, elem_count * elem_size); *size = newsize; - /* return successfully */ + // return successfully return CX_ARRAY_COPY_SUCCESS; } -/* HIGH LEVEL ARRAY LIST FUNCTIONS */ +#define CX_ARRAY_SWAP_SBO_SIZE 512 + +void cx_array_swap( + void *arr, + size_t elem_size, + size_t idx1, + size_t idx2 +) { + // 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; @@ -115,10 +156,10 @@ size_t elem_size, struct cx_array_reallocator_s *alloc ) { - /* retrieve the pointer to the list allocator */ + // retrieve the pointer to the list allocator CxAllocator const *al = alloc->ptr1; - /* use the list allocator to reallocate the memory */ + // use the list allocator to reallocate the memory return cxRealloc(al, array, capacity * elem_size); } @@ -144,6 +185,29 @@ ); } +static size_t cx_arl_add_array( + struct cx_list_s *list, + void const *array, + size_t n +) { + cx_array_list *arl = (cx_array_list *) list; + if (CX_ARRAY_COPY_SUCCESS == cx_array_copy( + &arl->data, + &list->size, + &list->capacity, + list->size, + array, + list->itemsize, + n, + &arl->reallocator + )) { + return n; + } else { + // array list implementation is "all or nothing" + return 0; + } +} + static int cx_arl_insert( struct cx_list_s *list, size_t index, @@ -156,7 +220,7 @@ } else { cx_array_list *arl = (cx_array_list *) list; - /* move elements starting at index to the right */ + // move elements starting at index to the right if (cx_array_copy( &arl->data, &list->size, @@ -170,7 +234,7 @@ return 1; } - /* place the element */ + // place the element memcpy(((char *) arl->data) + index * list->itemsize, elem, list->itemsize); @@ -179,25 +243,46 @@ } static int cx_arl_insert_iter( - struct cx_iterator_s *iter, + struct cx_mut_iterator_s *iter, void const *elem, int prepend ) { - return 1; + struct cx_list_s *list = iter->src_handle; + if (iter->index < list->size) { + int result = cx_arl_insert( + list, + iter->index + 1 - prepend, + elem + ); + if (result == 0 && prepend != 0) { + iter->index++; + iter->elem_handle = ((char *) iter->elem_handle) + list->itemsize; + } + return result; + } else { + int result = cx_arl_add(list, elem); + iter->index = list->size; + return result; + } } static int cx_arl_remove( struct cx_list_s *list, size_t index ) { - /* out-of-bounds check */ + // out-of-bounds check if (index >= list->size) { return 1; } - cx_array_list *arl = (cx_array_list *) list; + // 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 */ + // just move the elements starting at index to the left + cx_array_list *arl = (cx_array_list *) list; int result = cx_array_copy( &arl->data, &list->size, @@ -205,11 +290,11 @@ index, ((char *) arl->data) + (index + 1) * list->itemsize, list->itemsize, - list->size - index, + list->size - index - 1, &arl->reallocator ); if (result == 0) { - /* decrease the size */ + // decrease the size list->size--; } return result; @@ -256,34 +341,70 @@ struct cx_list_s const *list, struct cx_list_s const *other ) { - + 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->itemsize; + right += other->itemsize; + } + 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->itemsize, i, list->size - 1 - i); + } } -static bool cx_arl_iter_valid(struct cx_iterator_s const *iter) { +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(struct cx_iterator_s const *iter) { +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(struct cx_iterator_s *iter) { - if (iter->remove) { - iter->remove = false; +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 = cx_arl_at(iter->src_handle, iter->index); + iter->elem_handle = + ((char *) iter->elem_handle) + + ((struct cx_list_s const *) iter->src_handle)->itemsize; + } +} + +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 *list, + struct cx_list_s const *list, size_t index ) { struct cx_iterator_s iter; @@ -291,17 +412,33 @@ iter.index = index; iter.src_handle = list; iter.elem_handle = cx_arl_at(list, index); - iter.valid = cx_arl_iter_valid; - iter.current = cx_arl_iter_current; - iter.next = cx_arl_iter_next; - iter.remove = false; + iter.base.valid = cx_arl_iter_valid; + iter.base.current = cx_arl_iter_current; + iter.base.next = cx_arl_iter_next; + iter.base.flag_removal = cx_arl_iter_flag_rm; + iter.base.remove = false; + iter.base.mutating = false; + + return iter; +} +static struct cx_mut_iterator_s cx_arl_mut_iterator( + struct cx_list_s *list, + size_t index +) { + CxIterator it = cx_arl_iterator(list, index); + it.base.mutating = true; + + // we know the iterators share the same memory layout + CxMutIterator iter; + memcpy(&iter, &it, sizeof(CxMutIterator)); return iter; } static cx_list_class cx_array_list_class = { cx_arl_destructor, cx_arl_add, + cx_arl_add_array, cx_arl_insert, cx_arl_insert_iter, cx_arl_remove, @@ -311,6 +448,7 @@ cx_arl_compare, cx_arl_reverse, cx_arl_iterator, + cx_arl_mut_iterator, }; CxList *cxArrayListCreate( @@ -334,7 +472,7 @@ list->base.itemsize = item_size; list->base.capacity = initial_capacity; - /* configure the reallocator */ + // configure the reallocator list->reallocator.realloc = cx_arl_realloc; list->reallocator.ptr1 = (void *) allocator;