changeset
update ucx
Sun, 06 Oct 2024 12:00:31 +0200
- author
- Olaf Wintermann <olaf.wintermann@gmail.com>
- date
- Sun, 06 Oct 2024 12:00:31 +0200
- branch
- newapi
- changeset 324
- ce13a778654a
- parent 323
- 38cb8e3992e8
- child 325
- 99a93a9250c4
update ucx
--- a/ucx/Makefile Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/Makefile Sun Oct 06 12:00:31 2024 +0200 @@ -43,6 +43,8 @@ SRC += printf.c SRC += string.c SRC += utils.c +SRC += tree.c +SRC += iterator.c OBJ = $(SRC:%.c=../build/ucx/%$(OBJ_EXT))
--- a/ucx/allocator.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/allocator.c Sun Oct 06 12:00:31 2024 +0200 @@ -92,14 +92,14 @@ // IMPLEMENTATION OF HIGH LEVEL API void *cxMalloc( - CxAllocator const *allocator, + const CxAllocator *allocator, size_t n ) { return allocator->cl->malloc(allocator->data, n); } void *cxRealloc( - CxAllocator const *allocator, + const CxAllocator *allocator, void *mem, size_t n ) { @@ -107,7 +107,7 @@ } int cxReallocate( - CxAllocator const *allocator, + const CxAllocator *allocator, void **mem, size_t n ) { @@ -121,7 +121,7 @@ } void *cxCalloc( - CxAllocator const *allocator, + const CxAllocator *allocator, size_t nelem, size_t n ) { @@ -129,7 +129,7 @@ } void cxFree( - CxAllocator const *allocator, + const CxAllocator *allocator, void *mem ) { allocator->cl->free(allocator->data, mem);
--- a/ucx/array_list.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/array_list.c Sun Oct 06 12:00:31 2024 +0200 @@ -55,7 +55,7 @@ size_t *size, size_t *capacity, size_t index, - void const *src, + const void *src, size_t elem_size, size_t elem_count, struct cx_array_reallocator_s *reallocator @@ -120,6 +120,173 @@ return CX_ARRAY_SUCCESS; } +enum cx_array_result cx_array_insert_sorted( + void **target, + size_t *size, + size_t *capacity, + cx_compare_func cmp_func, + const void *sorted_data, + size_t elem_size, + size_t elem_count, + struct cx_array_reallocator_s *reallocator +) { + // assert pointers + assert(target != NULL); + assert(size != NULL); + assert(capacity != NULL); + assert(cmp_func != NULL); + assert(sorted_data != NULL); + assert(reallocator != NULL); + + // corner case + if (elem_count == 0) return 0; + + // store some counts + size_t old_size = *size; + size_t needed_capacity = old_size + elem_count; + + // if we need more than we have, try a reallocation + if (needed_capacity > *capacity) { + size_t new_capacity = needed_capacity - (needed_capacity % 16) + 16; + void *new_mem = reallocator->realloc( + *target, new_capacity, elem_size, reallocator + ); + if (new_mem == NULL) { + // give it up right away, there is no contract + // that requires us to insert as much as we can + return CX_ARRAY_REALLOC_FAILED; + } + *target = new_mem; + *capacity = new_capacity; + } + + // now we have guaranteed that we can insert everything + size_t new_size = old_size + elem_count; + *size = new_size; + + // declare the source and destination indices/pointers + size_t si = 0, di = 0; + const char *src = sorted_data; + char *dest = *target; + + // find the first insertion point + di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func); + dest += di * elem_size; + + // move the remaining elements in the array completely to the right + // we will call it the "buffer" for parked elements + size_t buf_size = old_size - di; + size_t bi = new_size - buf_size; + char *bptr = ((char *) *target) + bi * elem_size; + memmove(bptr, dest, buf_size * elem_size); + + // while there are both source and buffered elements left, + // copy them interleaving + while (si < elem_count && bi < new_size) { + // determine how many source elements can be inserted + size_t copy_len, bytes_copied; + copy_len = cx_array_binary_search_sup( + src, + elem_count - si, + elem_size, + bptr, + cmp_func + ); + + // copy the source elements + bytes_copied = copy_len * elem_size; + memcpy(dest, src, bytes_copied); + dest += bytes_copied; + src += bytes_copied; + si += copy_len; + + // when all source elements are in place, we are done + if (si >= elem_count) break; + + // determine how many buffered elements need to be restored + copy_len = cx_array_binary_search_sup( + bptr, + new_size - bi, + elem_size, + src, + cmp_func + ); + + // restore the buffered elements + bytes_copied = copy_len * elem_size; + memmove(dest, bptr, bytes_copied); + dest += bytes_copied; + bptr += bytes_copied; + bi += copy_len; + } + + // still source elements left? simply append them + if (si < elem_count) { + memcpy(dest, src, elem_size * (elem_count - si)); + } + + // still buffer elements left? + // don't worry, we already moved them to the correct place + + return CX_ARRAY_SUCCESS; +} + +size_t cx_array_binary_search_inf( + const void *arr, + size_t size, + size_t elem_size, + const void *elem, + cx_compare_func cmp_func +) { + // special case: empty array + if (size == 0) return 0; + + // declare a variable that will contain the compare results + int result; + + // cast the array pointer to something we can use offsets with + const char *array = arr; + + // check the first array element + result = cmp_func(elem, array); + if (result < 0) { + return size; + } else if (result == 0) { + return 0; + } + + // check the last array element + result = cmp_func(elem, array + elem_size * (size - 1)); + if (result >= 0) { + return size - 1; + } + + // the element is now guaranteed to be somewhere in the list + // so start the binary search + size_t left_index = 1; + size_t right_index = size - 1; + size_t pivot_index; + + while (left_index <= right_index) { + pivot_index = left_index + (right_index - left_index) / 2; + const char *arr_elem = array + pivot_index * elem_size; + result = cmp_func(elem, arr_elem); + if (result == 0) { + // found it! + return pivot_index; + } else if (result < 0) { + // element is smaller than pivot, continue search left + right_index = pivot_index - 1; + } else { + // element is larger than pivot, continue search right + left_index = pivot_index + 1; + } + } + + // report the largest upper bound + return result < 0 ? (pivot_index - 1) : pivot_index; +} + #ifndef CX_ARRAY_SWAP_SBO_SIZE #define CX_ARRAY_SWAP_SBO_SIZE 128 #endif @@ -180,7 +347,7 @@ struct cx_array_reallocator_s *alloc ) { // retrieve the pointer to the list allocator - CxAllocator const *al = alloc->ptr1; + const CxAllocator *al = alloc->ptr1; // use the list allocator to reallocate the memory return cxRealloc(al, array, capacity * elem_size); @@ -191,49 +358,49 @@ char *ptr = arl->data; - if (list->simple_destructor) { - for (size_t i = 0; i < list->size; i++) { + if (list->collection.simple_destructor) { + for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_simple_destructor(list, ptr); - ptr += list->item_size; + ptr += list->collection.elem_size; } } - if (list->advanced_destructor) { - for (size_t i = 0; i < list->size; i++) { + if (list->collection.advanced_destructor) { + for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_advanced_destructor(list, ptr); - ptr += list->item_size; + ptr += list->collection.elem_size; } } - cxFree(list->allocator, arl->data); - cxFree(list->allocator, list); + 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, + const void *array, size_t n ) { // out of bounds and special case check - if (index > list->size || n == 0) return 0; + 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->size) { - char const *first_to_move = (char const *) arl->data; - first_to_move += index * list->item_size; - size_t elems_to_move = list->size - index; + if (index < list->collection.size) { + const char *first_to_move = (const char *) 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->size, + &list->collection.size, &arl->capacity, start_of_moved, first_to_move, - list->item_size, + list->collection.elem_size, elems_to_move, &arl->reallocator )) { @@ -249,11 +416,36 @@ // place the new elements if (CX_ARRAY_SUCCESS == cx_array_copy( &arl->data, - &list->size, + &list->collection.size, &arl->capacity, index, array, - list->item_size, + list->collection.elem_size, + n, + &arl->reallocator + )) { + return n; + } else { + // array list implementation is "all or nothing" + return 0; + } +} + +static size_t cx_arl_insert_sorted( + struct cx_list_s *list, + const void *sorted_data, + size_t n +) { + // get a correctly typed pointer to the list + cx_array_list *arl = (cx_array_list *) list; + + if (CX_ARRAY_SUCCESS == cx_array_insert_sorted( + &arl->data, + &list->collection.size, + &arl->capacity, + list->collection.cmpfunc, + sorted_data, + list->collection.elem_size, n, &arl->reallocator )) { @@ -267,31 +459,37 @@ static int cx_arl_insert_element( struct cx_list_s *list, size_t index, - void const *element + const void *element ) { return 1 != cx_arl_insert_array(list, index, element, 1); } static int cx_arl_insert_iter( - struct cx_mut_iterator_s *iter, - void const *elem, + struct cx_iterator_s *iter, + const void *elem, int prepend ) { - struct cx_list_s *list = iter->src_handle; - if (iter->index < list->size) { + 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->item_size; + if (result == 0) { + iter->elem_count++; + if (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->size, elem); - iter->index = list->size; + int result = cx_arl_insert_element(list, list->collection.size, elem); + if (result == 0) { + iter->elem_count++; + iter->index = list->collection.size; + } return result; } } @@ -303,28 +501,28 @@ cx_array_list *arl = (cx_array_list *) list; // out-of-bounds check - if (index >= list->size) { + if (index >= list->collection.size) { return 1; } // content destruction - cx_invoke_destructor(list, ((char *) arl->data) + index * list->item_size); + cx_invoke_destructor(list, ((char *) arl->data) + index * list->collection.elem_size); // short-circuit removal of last element - if (index == list->size - 1) { - list->size--; + 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->size, + &list->collection.size, &arl->capacity, index, - ((char *) arl->data) + (index + 1) * list->item_size, - list->item_size, - list->size - index - 1, + ((char *) arl->data) + (index + 1) * list->collection.elem_size, + list->collection.elem_size, + list->collection.size - index - 1, &arl->reallocator ); @@ -332,32 +530,32 @@ assert(result == 0); // decrease the size - list->size--; + list->collection.size--; return 0; } static void cx_arl_clear(struct cx_list_s *list) { - if (list->size == 0) return; + if (list->collection.size == 0) return; cx_array_list *arl = (cx_array_list *) list; char *ptr = arl->data; - if (list->simple_destructor) { - for (size_t i = 0; i < list->size; i++) { + if (list->collection.simple_destructor) { + for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_simple_destructor(list, ptr); - ptr += list->item_size; + ptr += list->collection.elem_size; } } - if (list->advanced_destructor) { - for (size_t i = 0; i < list->size; i++) { + if (list->collection.advanced_destructor) { + for (size_t i = 0; i < list->collection.size; i++) { cx_invoke_advanced_destructor(list, ptr); - ptr += list->item_size; + ptr += list->collection.elem_size; } } - memset(arl->data, 0, list->size * list->item_size); - list->size = 0; + memset(arl->data, 0, list->collection.size * list->collection.elem_size); + list->collection.size = 0; } static int cx_arl_swap( @@ -365,20 +563,20 @@ size_t i, size_t j ) { - if (i >= list->size || j >= list->size) return 1; + 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->item_size, i, j); + cx_array_swap(arl->data, list->collection.elem_size, i, j); return 0; } static void *cx_arl_at( - struct cx_list_s const *list, + const struct cx_list_s *list, size_t index ) { - if (index < list->size) { - cx_array_list const *arl = (cx_array_list const *) list; + if (index < list->collection.size) { + const cx_array_list *arl = (const cx_array_list *) list; char *space = arl->data; - return space + index * list->item_size; + return space + index * list->collection.elem_size; } else { return NULL; } @@ -386,15 +584,15 @@ static ssize_t cx_arl_find_remove( struct cx_list_s *list, - void const *elem, + const void *elem, bool remove ) { - assert(list->cmpfunc != NULL); - assert(list->size < SIZE_MAX / 2); - char *cur = ((cx_array_list const *) list)->data; + assert(list->collection.cmpfunc != NULL); + assert(list->collection.size < SIZE_MAX / 2); + char *cur = ((const cx_array_list *) list)->data; - for (ssize_t i = 0; i < (ssize_t) list->size; i++) { - if (0 == list->cmpfunc(elem, cur)) { + 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; @@ -405,117 +603,106 @@ return i; } } - cur += list->item_size; + cur += list->collection.elem_size; } return -1; } static void cx_arl_sort(struct cx_list_s *list) { - assert(list->cmpfunc != NULL); + assert(list->collection.cmpfunc != NULL); qsort(((cx_array_list *) list)->data, - list->size, - list->item_size, - list->cmpfunc + 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 + const struct cx_list_s *list, + const struct cx_list_s *other ) { - assert(list->cmpfunc != NULL); - 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); + assert(list->collection.cmpfunc != NULL); + if (list->collection.size == other->collection.size) { + const char *left = ((const cx_array_list *) list)->data; + const char *right = ((const cx_array_list *) 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->item_size; - right += other->item_size; + left += list->collection.elem_size; + right += other->collection.elem_size; } return 0; } else { - return list->size < other->size ? -1 : 1; + return list->collection.size < other->collection.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; + if (list->collection.size < 2) return; + void *data = ((const cx_array_list *) list)->data; + size_t half = list->collection.size / 2; for (size_t i = 0; i < half; i++) { - cx_array_swap(data, list->item_size, i, list->size - 1 - 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; - return iter->index < list->size; +static bool cx_arl_iter_valid(const void *it) { + const struct cx_iterator_s *iter = it; + const struct cx_list_s *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; +static void *cx_arl_iter_current(const void *it) { + const struct cx_iterator_s *iter = it; return iter->elem_handle; } 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); + struct cx_iterator_s *iter = it; + if (iter->base.remove) { + iter->base.remove = false; + cx_arl_remove(iter->src_handle.m, iter->index); } else { - struct cx_iterator_s *iter = it; iter->index++; iter->elem_handle = ((char *) iter->elem_handle) - + ((struct cx_list_s const *) iter->src_handle)->item_size; + + ((const struct cx_list_s *) iter->src_handle.c)->collection.elem_size; } } static void cx_arl_iter_prev(void *it) { - struct cx_iterator_base_s *itbase = it; - struct cx_mut_iterator_s *iter = it; - cx_array_list *const list = iter->src_handle; - if (itbase->remove) { - itbase->remove = false; - cx_arl_remove(iter->src_handle, iter->index); + struct cx_iterator_s *iter = it; + const cx_array_list *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.size) { + if (iter->index < list->base.collection.size) { iter->elem_handle = ((char *) list->data) - + iter->index * list->base.item_size; + + iter->index * list->base.collection.elem_size; } } -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 const *list, + const struct cx_list_s *list, size_t index, bool backwards ) { struct cx_iterator_s iter; iter.index = index; - iter.src_handle = list; + 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.flag_removal = cx_arl_iter_flag_rm; iter.base.remove = false; iter.base.mutating = false; @@ -526,6 +713,7 @@ cx_arl_destructor, cx_arl_insert_element, cx_arl_insert_array, + cx_arl_insert_sorted, cx_arl_insert_iter, cx_arl_remove, cx_arl_clear, @@ -539,9 +727,9 @@ }; CxList *cxArrayListCreate( - CxAllocator const *allocator, + const CxAllocator *allocator, cx_compare_func comparator, - size_t item_size, + size_t elem_size, size_t initial_capacity ) { if (allocator == NULL) { @@ -552,20 +740,20 @@ if (list == NULL) return NULL; list->base.cl = &cx_array_list_class; - list->base.allocator = allocator; + list->base.collection.allocator = allocator; list->capacity = initial_capacity; - if (item_size > 0) { - list->base.item_size = item_size; - list->base.cmpfunc = comparator; + if (elem_size > 0) { + list->base.collection.elem_size = elem_size; + list->base.collection.cmpfunc = comparator; } else { - item_size = sizeof(void *); - list->base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; + elem_size = sizeof(void *); + list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; cxListStorePointers((CxList *) list); } - // allocate the array after the real item_size is known - list->data = cxCalloc(allocator, initial_capacity, item_size); + // 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;
--- a/ucx/buffer.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/buffer.c Sun Oct 06 12:00:31 2024 +0200 @@ -36,7 +36,7 @@ CxBuffer *buffer, void *space, size_t capacity, - CxAllocator const *allocator, + const CxAllocator *allocator, int flags ) { if (allocator == NULL) allocator = cxDefaultAllocator; @@ -73,7 +73,7 @@ CxBuffer *cxBufferCreate( void *space, size_t capacity, - CxAllocator const *allocator, + const CxAllocator *allocator, int flags ) { CxBuffer *buf = cxMalloc(allocator, sizeof(CxBuffer)); @@ -140,7 +140,7 @@ buffer->pos = 0; } -int cxBufferEof(CxBuffer const *buffer) { +int cxBufferEof(const CxBuffer *buffer) { return buffer->pos >= buffer->size; } @@ -172,7 +172,7 @@ */ static size_t cx_buffer_write_flush_helper( CxBuffer *buffer, - unsigned char const *space, + const unsigned char *space, size_t size, size_t nitems ) { @@ -197,7 +197,7 @@ } size_t cxBufferWrite( - void const *ptr, + const void *ptr, size_t size, size_t nitems, CxBuffer *buffer @@ -273,7 +273,7 @@ items_keep = nitems - items_flush; if (items_keep > 0) { // try again with the remaining stuff - unsigned char const *new_ptr = ptr; + const unsigned char *new_ptr = ptr; new_ptr += items_flush * size; // report the directly flushed items as written plus the remaining stuff return items_flush + cxBufferWrite(new_ptr, size, items_keep, buffer);
--- a/ucx/compare.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/compare.c Sun Oct 06 12:00:31 2024 +0200 @@ -30,7 +30,7 @@ #include <math.h> -int cx_cmp_int(void const *i1, void const *i2) { +int cx_cmp_int(const void *i1, const void *i2) { int a = *((const int *) i1); int b = *((const int *) i2); if (a == b) { @@ -40,7 +40,7 @@ } } -int cx_cmp_longint(void const *i1, void const *i2) { +int cx_cmp_longint(const void *i1, const void *i2) { long int a = *((const long int *) i1); long int b = *((const long int *) i2); if (a == b) { @@ -50,7 +50,7 @@ } } -int cx_cmp_longlong(void const *i1, void const *i2) { +int cx_cmp_longlong(const void *i1, const void *i2) { long long a = *((const long long *) i1); long long b = *((const long long *) i2); if (a == b) { @@ -60,7 +60,7 @@ } } -int cx_cmp_int16(void const *i1, void const *i2) { +int cx_cmp_int16(const void *i1, const void *i2) { int16_t a = *((const int16_t *) i1); int16_t b = *((const int16_t *) i2); if (a == b) { @@ -70,7 +70,7 @@ } } -int cx_cmp_int32(void const *i1, void const *i2) { +int cx_cmp_int32(const void *i1, const void *i2) { int32_t a = *((const int32_t *) i1); int32_t b = *((const int32_t *) i2); if (a == b) { @@ -80,7 +80,7 @@ } } -int cx_cmp_int64(void const *i1, void const *i2) { +int cx_cmp_int64(const void *i1, const void *i2) { int64_t a = *((const int64_t *) i1); int64_t b = *((const int64_t *) i2); if (a == b) { @@ -90,7 +90,7 @@ } } -int cx_cmp_uint(void const *i1, void const *i2) { +int cx_cmp_uint(const void *i1, const void *i2) { unsigned int a = *((const unsigned int *) i1); unsigned int b = *((const unsigned int *) i2); if (a == b) { @@ -100,7 +100,7 @@ } } -int cx_cmp_ulongint(void const *i1, void const *i2) { +int cx_cmp_ulongint(const void *i1, const void *i2) { unsigned long int a = *((const unsigned long int *) i1); unsigned long int b = *((const unsigned long int *) i2); if (a == b) { @@ -110,7 +110,7 @@ } } -int cx_cmp_ulonglong(void const *i1, void const *i2) { +int cx_cmp_ulonglong(const void *i1, const void *i2) { unsigned long long a = *((const unsigned long long *) i1); unsigned long long b = *((const unsigned long long *) i2); if (a == b) { @@ -120,7 +120,7 @@ } } -int cx_cmp_uint16(void const *i1, void const *i2) { +int cx_cmp_uint16(const void *i1, const void *i2) { uint16_t a = *((const uint16_t *) i1); uint16_t b = *((const uint16_t *) i2); if (a == b) { @@ -130,7 +130,7 @@ } } -int cx_cmp_uint32(void const *i1, void const *i2) { +int cx_cmp_uint32(const void *i1, const void *i2) { uint32_t a = *((const uint32_t *) i1); uint32_t b = *((const uint32_t *) i2); if (a == b) { @@ -140,7 +140,7 @@ } } -int cx_cmp_uint64(void const *i1, void const *i2) { +int cx_cmp_uint64(const void *i1, const void *i2) { uint64_t a = *((const uint64_t *) i1); uint64_t b = *((const uint64_t *) i2); if (a == b) { @@ -150,7 +150,7 @@ } } -int cx_cmp_float(void const *f1, void const *f2) { +int cx_cmp_float(const void *f1, const void *f2) { float a = *((const float *) f1); float b = *((const float *) f2); if (fabsf(a - b) < 1e-6f) { @@ -161,8 +161,8 @@ } int cx_cmp_double( - void const *d1, - void const *d2 + const void *d1, + const void *d2 ) { double a = *((const double *) d1); double b = *((const double *) d2); @@ -174,8 +174,8 @@ } int cx_cmp_intptr( - void const *ptr1, - void const *ptr2 + const void *ptr1, + const void *ptr2 ) { intptr_t p1 = *(const intptr_t *) ptr1; intptr_t p2 = *(const intptr_t *) ptr2; @@ -187,8 +187,8 @@ } int cx_cmp_uintptr( - void const *ptr1, - void const *ptr2 + const void *ptr1, + const void *ptr2 ) { uintptr_t p1 = *(const uintptr_t *) ptr1; uintptr_t p2 = *(const uintptr_t *) ptr2; @@ -200,8 +200,8 @@ } int cx_cmp_ptr( - void const *ptr1, - void const *ptr2 + const void *ptr1, + const void *ptr2 ) { uintptr_t p1 = (uintptr_t) ptr1; uintptr_t p2 = (uintptr_t) ptr2;
--- a/ucx/cx/allocator.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/allocator.h Sun Oct 06 12:00:31 2024 +0200 @@ -54,12 +54,12 @@ /** * The allocator's realloc() implementation. */ + __attribute__((__warn_unused_result__)) void *(*realloc)( void *data, void *mem, size_t n - ) - __attribute__((__warn_unused_result__)); + ); /** * The allocator's calloc() implementation. @@ -73,11 +73,11 @@ /** * The allocator's free() implementation. */ + __attribute__((__nonnull__)) void (*free)( void *data, void *mem - ) - __attribute__((__nonnull__)); + ); } cx_allocator_class; /** @@ -114,7 +114,8 @@ * * @param memory a pointer to the object to destruct */ -typedef void (*cx_destructor_func)(void *memory) __attribute__((__nonnull__)); +__attribute__((__nonnull__)) +typedef void (*cx_destructor_func)(void *memory); /** * Function pointer type for destructor functions. @@ -127,10 +128,11 @@ * @param data an optional pointer to custom data * @param memory a pointer to the object to destruct */ +__attribute__((__nonnull__(2))) typedef void (*cx_destructor_func2)( void *data, void *memory -) __attribute__((__nonnull__(2))); +); /** * Re-allocate a previously allocated block and changes the pointer in-place, if necessary. @@ -142,11 +144,11 @@ * @param n the new size in bytes * @return zero on success, non-zero on failure */ +__attribute__((__nonnull__)) int cx_reallocate( void **mem, size_t n -) -__attribute__((__nonnull__)); +); /** * Allocate \p n bytes of memory. @@ -155,12 +157,12 @@ * @param n the number of bytes * @return a pointer to the allocated memory */ +__attribute__((__malloc__)) +__attribute__((__alloc_size__(2))) void *cxMalloc( - CxAllocator const *allocator, + const CxAllocator *allocator, size_t n -) -__attribute__((__malloc__)) -__attribute__((__alloc_size__(2))); +); /** * Re-allocate the previously allocated block in \p mem, making the new block \p n bytes long. @@ -174,13 +176,13 @@ * @param n the new size in bytes * @return a pointer to the re-allocated memory */ +__attribute__((__warn_unused_result__)) +__attribute__((__alloc_size__(3))) void *cxRealloc( - CxAllocator const *allocator, + const CxAllocator *allocator, void *mem, size_t n -) -__attribute__((__warn_unused_result__)) -__attribute__((__alloc_size__(3))); +); /** * Re-allocate a previously allocated block and changes the pointer in-place, if necessary. @@ -196,12 +198,12 @@ * @param n the new size in bytes * @return zero on success, non-zero on failure */ +__attribute__((__nonnull__)) int cxReallocate( - CxAllocator const *allocator, + const CxAllocator *allocator, void **mem, size_t n -) -__attribute__((__nonnull__)); +); /** * Allocate \p nelem elements of \p n bytes each, all initialized to zero. @@ -211,13 +213,13 @@ * @param n the size of each element in bytes * @return a pointer to the allocated memory */ +__attribute__((__malloc__)) +__attribute__((__alloc_size__(2, 3))) void *cxCalloc( - CxAllocator const *allocator, + const CxAllocator *allocator, size_t nelem, size_t n -) -__attribute__((__malloc__)) -__attribute__((__alloc_size__(2, 3))); +); /** * Free a block allocated by this allocator. @@ -227,11 +229,11 @@ * @param allocator the allocator * @param mem a pointer to the block to free */ +__attribute__((__nonnull__)) void cxFree( - CxAllocator const *allocator, + const CxAllocator *allocator, void *mem -) -__attribute__((__nonnull__)); +); #ifdef __cplusplus } // extern "C"
--- a/ucx/cx/array_list.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/array_list.h Sun Oct 06 12:00:31 2024 +0200 @@ -50,14 +50,40 @@ extern unsigned cx_array_swap_sbo_size; /** + * Declares variables for an array that can be used with the convenience macros. + * + * @see cx_array_simple_add() + * @see cx_array_simple_copy() + * @see cx_array_initialize() + * @see cx_array_simple_add_sorted() + * @see cx_array_simple_insert_sorted() + */ +#define CX_ARRAY_DECLARE(type, name) \ + type * name; \ + size_t name##_size; \ + size_t name##_capacity + +/** + * Initializes an array declared with CX_ARRAY_DECLARE(). + * + * The memory for the array is allocated with stdlib malloc(). + * @param array the array + * @param capacity the initial capacity + */ +#define cx_array_initialize(array, capacity) \ + array##_capacity = capacity; \ + array##_size = 0; \ + array = malloc(sizeof(array[0]) * capacity) + +/** * Defines a reallocation mechanism for arrays. */ struct cx_array_reallocator_s { /** - * Re-allocates space for the given array. + * Reallocates space for the given array. * * Implementations are not required to free the original array. - * This allows re-allocation of static memory by allocating heap memory + * This allows reallocation of static memory by allocating heap memory * and copying the array contents. The information in the custom fields of * the referenced allocator can be used to track the state of the memory * or to transport other additional data. @@ -120,28 +146,43 @@ * attempt is made, unless the \p reallocator is set to \c NULL, in which case * this function ultimately returns a failure. * - * @param target the target array + * @param target a pointer to the target array * @param size a pointer to the size of the target array * @param capacity a pointer to the target array's capacity - - * \c NULL if only the size shall be used to bound the array + * \c NULL if only the size shall be used to bound the array (reallocations + * will NOT be supported in that case) * @param index the index where the copied elements shall be placed * @param src the source array * @param elem_size the size of one element * @param elem_count the number of elements to copy - * @param reallocator the array re-allocator to use, or \c NULL - * if re-allocation shall not happen + * @param reallocator the array reallocator to use, or \c NULL + * if reallocation shall not happen * @return zero on success, non-zero error code on failure */ +__attribute__((__nonnull__(1, 2, 5))) enum cx_array_result cx_array_copy( void **target, size_t *size, size_t *capacity, size_t index, - void const *src, + const void *src, size_t elem_size, size_t elem_count, struct cx_array_reallocator_s *reallocator -) __attribute__((__nonnull__(1, 2, 5))); +); + +/** + * Convenience macro that uses cx_array_copy() with a default layout and the default reallocator. + * + * @param array the name of the array (NOT a pointer to the array) + * @param index the index where the copied elements shall be placed + * @param src the source array + * @param count the number of elements to copy + * @see CX_ARRAY_DECLARE() + */ +#define cx_array_simple_copy(array, index, src, count) \ + cx_array_copy((void**)&(array), &(array##_size), &(array##_capacity), \ + index, src, sizeof((array)[0]), count, cx_array_default_reallocator) /** * Adds an element to an array with the possibility of allocating more space. @@ -154,19 +195,209 @@ * \p reallocator is not \c NULL, an attempt increase the \p capacity is made * and the new capacity is written back. * - * @param target the target array + * @param target a pointer to the target array * @param size a pointer to the size of the target array * @param capacity a pointer to the target array's capacity - must not be \c NULL * @param elem_size the size of one element - * @param elem the element to add - * @param reallocator the array re-allocator to use, or \c NULL - * if re-allocation shall not happen + * @param elem a pointer to the element to add + * @param reallocator the array reallocator to use, or \c NULL if reallocation shall not happen * @return zero on success, non-zero error code on failure */ #define cx_array_add(target, size, capacity, elem_size, elem, reallocator) \ cx_array_copy((void**)(target), size, capacity, *(size), elem, elem_size, 1, reallocator) /** + * Convenience macro that uses cx_array_add() with a default layout and + * the default reallocator. + * + * @param array the name of the array (NOT a pointer to the array) + * @param elem the element to add (NOT a pointer, address is automatically taken) + * @see CX_ARRAY_DECLARE() + */ +#define cx_array_simple_add(array, elem) \ + cx_array_simple_copy(array, array##_size, &(elem), 1) + + +/** + * Inserts a sorted array into another sorted array. + * + * If either the target or the source array is not already sorted with respect + * to the specified \p cmp_func, the behavior is undefined. + * + * If the capacity is insufficient to hold the new data, a reallocation + * attempt is made. + * + * @param target a pointer to the target array + * @param size a pointer to the size of the target array + * @param capacity a pointer to the target array's capacity + * @param cmp_func the compare function for the elements + * @param src the source array + * @param elem_size the size of one element + * @param elem_count the number of elements to insert + * @param reallocator the array reallocator to use + * @return zero on success, non-zero error code on failure + */ +__attribute__((__nonnull__)) +enum cx_array_result cx_array_insert_sorted( + void **target, + size_t *size, + size_t *capacity, + cx_compare_func cmp_func, + const void *src, + size_t elem_size, + size_t elem_count, + struct cx_array_reallocator_s *reallocator +); + +/** + * Inserts an element into a sorted array. + * + * If the target array is not already sorted with respect + * to the specified \p cmp_func, the behavior is undefined. + * + * If the capacity is insufficient to hold the new data, a reallocation + * attempt is made. + * + * @param target a pointer to the target array + * @param size a pointer to the size of the target array + * @param capacity a pointer to the target array's capacity + * @param elem_size the size of one element + * @param elem a pointer to the element to add + * @param reallocator the array reallocator to use + * @return zero on success, non-zero error code on failure + */ +#define cx_array_add_sorted(target, size, capacity, elem_size, elem, cmp_func, reallocator) \ + cx_array_insert_sorted((void**)(target), size, capacity, cmp_func, elem, elem_size, 1, reallocator) + +/** + * Convenience macro for cx_array_add_sorted() with a default + * layout and the default reallocator. + * + * @param array the name of the array (NOT a pointer to the array) + * @param elem the element to add (NOT a pointer, address is automatically taken) + * @param cmp_func the compare function for the elements + * @see CX_ARRAY_DECLARE() + */ +#define cx_array_simple_add_sorted(array, elem, cmp_func) \ + cx_array_add_sorted(&array, &(array##_size), &(array##_capacity), \ + sizeof((array)[0]), &(elem), cmp_func, cx_array_default_reallocator) + +/** + * Convenience macro for cx_array_insert_sorted() with a default + * layout and the default reallocator. + * + * @param array the name of the array (NOT a pointer to the array) + * @param src pointer to the source array + * @param n number of elements in the source array + * @param cmp_func the compare function for the elements + * @see CX_ARRAY_DECLARE() + */ +#define cx_array_simple_insert_sorted(array, src, n, cmp_func) \ + cx_array_insert_sorted((void**)(&array), &(array##_size), &(array##_capacity), \ + cmp_func, src, sizeof((array)[0]), n, cx_array_default_reallocator) + + +/** + * Searches the largest lower bound in a sorted array. + * + * In other words, this function returns the index of the largest element + * in \p arr that is less or equal to \p elem with respect to \p cmp_func. + * When no such element exists, \p size is returned. + * + * If \p elem is contained in the array, this is identical to + * #cx_array_binary_search(). + * + * If the array is not sorted with respect to the \p cmp_func, the behavior + * is undefined. + * + * @param arr the array to search + * @param size the size of the array + * @param elem_size the size of one element + * @param elem the element to find + * @param cmp_func the compare function + * @return the index of the largest lower bound, or \p size + */ +__attribute__((__nonnull__)) +size_t cx_array_binary_search_inf( + const void *arr, + size_t size, + size_t elem_size, + const void *elem, + cx_compare_func cmp_func +); + +/** + * Searches an item in a sorted array. + * + * If the array is not sorted with respect to the \p cmp_func, the behavior + * is undefined. + * + * @param arr the array to search + * @param size the size of the array + * @param elem_size the size of one element + * @param elem the element to find + * @param cmp_func the compare function + * @return the index of the element in the array, or \p size if the element + * cannot be found + */ +__attribute__((__nonnull__)) +static inline size_t cx_array_binary_search( + const void *arr, + size_t size, + size_t elem_size, + const void *elem, + cx_compare_func cmp_func +) { + size_t index = cx_array_binary_search_inf( + arr, size, elem_size, elem, cmp_func + ); + if (index < size && cmp_func(((const char *) arr) + index * elem_size, elem) == 0) { + return index; + } else { + return size; + } +} + +/** + * Searches the smallest upper bound in a sorted array. + * + * In other words, this function returns the index of the smallest element + * in \p arr that is greater or equal to \p elem with respect to \p cmp_func. + * When no such element exists, \p size is returned. + * + * If \p elem is contained in the array, this is identical to + * #cx_array_binary_search(). + * + * If the array is not sorted with respect to the \p cmp_func, the behavior + * is undefined. + * + * @param arr the array to search + * @param size the size of the array + * @param elem_size the size of one element + * @param elem the element to find + * @param cmp_func the compare function + * @return the index of the smallest upper bound, or \p size + */ +__attribute__((__nonnull__)) +static inline size_t cx_array_binary_search_sup( + const void *arr, + size_t size, + size_t elem_size, + const void *elem, + cx_compare_func cmp_func +) { + size_t inf = cx_array_binary_search_inf(arr, size, elem_size, elem, cmp_func); + if (inf == size) { + // no infimum means, first element is supremum + return 0; + } else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) { + return inf; + } else { + return inf + 1; + } +} + +/** * Swaps two array elements. * * @param arr the array @@ -174,17 +405,18 @@ * @param idx1 index of first element * @param idx2 index of second element */ +__attribute__((__nonnull__)) void cx_array_swap( void *arr, size_t elem_size, size_t idx1, size_t idx2 -) __attribute__((__nonnull__)); +); /** - * Allocates an array list for storing elements with \p item_size bytes each. + * Allocates an array list for storing elements with \p elem_size bytes each. * - * If \p item_size is CX_STORE_POINTERS, the created list will be created as if + * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if * cxListStorePointers() was called immediately after creation and the compare * function will be automatically set to cx_cmp_ptr(), if none is given. * @@ -193,34 +425,34 @@ * @param comparator the comparator for the elements * (if \c NULL, and the list is not storing pointers, sort and find * functions will not work) - * @param item_size the size of each element in bytes + * @param elem_size the size of each element in bytes * @param initial_capacity the initial number of elements the array can store * @return the created list */ CxList *cxArrayListCreate( - CxAllocator const *allocator, + const CxAllocator *allocator, cx_compare_func comparator, - size_t item_size, + size_t elem_size, size_t initial_capacity ); /** - * Allocates an array list for storing elements with \p item_size bytes each. + * Allocates an array list for storing elements with \p elem_size bytes each. * * The list will use the cxDefaultAllocator and \em NO compare function. * If you want to call functions that need a compare function, you have to * set it immediately after creation or use cxArrayListCreate(). * - * If \p item_size is CX_STORE_POINTERS, the created list will be created as if + * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if * cxListStorePointers() was called immediately after creation and the compare * function will be automatically set to cx_cmp_ptr(). * - * @param item_size the size of each element in bytes + * @param elem_size the size of each element in bytes * @param initial_capacity the initial number of elements the array can store * @return the created list */ -#define cxArrayListCreateSimple(item_size, initial_capacity) \ - cxArrayListCreate(NULL, NULL, item_size, initial_capacity) +#define cxArrayListCreateSimple(elem_size, initial_capacity) \ + cxArrayListCreate(NULL, NULL, elem_size, initial_capacity) #ifdef __cplusplus } // extern "C"
--- a/ucx/cx/buffer.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/buffer.h Sun Oct 06 12:00:31 2024 +0200 @@ -82,7 +82,7 @@ unsigned char *bytes; }; /** The allocator to use for automatic memory management. */ - CxAllocator const *allocator; + const CxAllocator *allocator; /** Current position of the buffer. */ size_t pos; /** Current capacity (i.e. maximum size) of the buffer. */ @@ -158,7 +158,7 @@ CxBuffer *buffer, void *space, size_t capacity, - CxAllocator const *allocator, + const CxAllocator *allocator, int flags ); @@ -180,7 +180,7 @@ CxBuffer *cxBufferCreate( void *space, size_t capacity, - CxAllocator const *allocator, + const CxAllocator *allocator, int flags ); @@ -339,7 +339,7 @@ * byte of the buffer's contents. */ __attribute__((__nonnull__)) -int cxBufferEof(CxBuffer const *buffer); +int cxBufferEof(const CxBuffer *buffer); /** @@ -385,7 +385,7 @@ */ __attribute__((__nonnull__)) size_t cxBufferWrite( - void const *ptr, + const void *ptr, size_t size, size_t nitems, CxBuffer *buffer
--- a/ucx/cx/collection.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/collection.h Sun Oct 06 12:00:31 2024 +0200 @@ -38,6 +38,7 @@ #include "allocator.h" #include "iterator.h" +#include "compare.h" #ifdef __cplusplus extern "C" { @@ -48,60 +49,74 @@ */ #define CX_STORE_POINTERS 0 -#ifndef CX_COMPARE_FUNC_DEFINED -#define CX_COMPARE_FUNC_DEFINED /** - * A comparator function comparing two collection elements. + * Base attributes of a collection. */ -typedef int(*cx_compare_func)( - void const *left, - void const *right -); -#endif // CX_COMPARE_FUNC_DEFINED +struct cx_collection_s { + /** + * The allocator to use. + */ + const CxAllocator *allocator; + /** + * The comparator function for the elements. + */ + cx_compare_func cmpfunc; + /** + * The size of each element. + */ + size_t elem_size; + /** + * The number of currently stored elements. + */ + size_t size; + /** + * An optional simple destructor for the collection's elements. + * + * @attention Read the documentation of the particular collection implementation + * whether this destructor shall only destroy the contents or also free the memory. + */ + cx_destructor_func simple_destructor; + /** + * An optional advanced destructor for the collection's elements. + * + * @attention Read the documentation of the particular collection implementation + * whether this destructor shall only destroy the contents or also free the memory. + */ + cx_destructor_func2 advanced_destructor; + /** + * The pointer to additional data that is passed to the advanced destructor. + */ + void *destructor_data; + /** + * Indicates if this list is supposed to store pointers + * instead of copies of the actual objects. + */ + bool store_pointer; +}; /** * Use this macro to declare common members for a collection structure. */ -#define CX_COLLECTION_MEMBERS \ - /** \ - * The allocator to use. \ - */ \ - CxAllocator const *allocator; \ - /** \ - * The comparator function for the elements. \ - */ \ - cx_compare_func cmpfunc; \ - /** \ - * The size of each element. \ - */ \ - size_t item_size; \ - /** \ - * The number of currently stored elements. \ - */ \ - size_t size; \ - /** \ - * An optional simple destructor for the collection's elements. \ - * \ - * @attention Read the documentation of the particular collection implementation \ - * whether this destructor shall only destroy the contents or also free the memory. \ - */ \ - cx_destructor_func simple_destructor; \ - /** \ - * An optional advanced destructor for the collection's elements. \ - * \ - * @attention Read the documentation of the particular collection implementation \ - * whether this destructor shall only destroy the contents or also free the memory. \ - */ \ - cx_destructor_func2 advanced_destructor; \ - /** \ - * The pointer to additional data that is passed to the advanced destructor. \ - */ \ - void *destructor_data; \ - /** \ - * Indicates if this instance of a collection is supposed to store pointers \ - * instead of copies of the actual objects. \ - */ \ - bool store_pointer; +#define CX_COLLECTION_BASE struct cx_collection_s collection + +/** + * Sets a simple destructor function for this collection. + * + * @param c the collection + * @param destr the destructor function + */ +#define cxDefineDestructor(c, destr) \ + (c)->collection.simple_destructor = (cx_destructor_func) destr + +/** + * Sets a simple destructor function for this collection. + * + * @param c the collection + * @param destr the destructor function + */ +#define cxDefineAdvancedDestructor(c, destr, data) \ + (c)->collection.advanced_destructor = (cx_destructor_func2) destr; \ + (c)->collection.destructor_data = data /** * Invokes the simple destructor function for a specific element. @@ -113,7 +128,7 @@ * @param e the element */ #define cx_invoke_simple_destructor(c, e) \ - (c)->simple_destructor((c)->store_pointer ? (*((void **) (e))) : (e)) + (c)->collection.simple_destructor((c)->collection.store_pointer ? (*((void **) (e))) : (e)) /** * Invokes the advanced destructor function for a specific element. @@ -125,8 +140,8 @@ * @param e the element */ #define cx_invoke_advanced_destructor(c, e) \ - (c)->advanced_destructor((c)->destructor_data, \ - (c)->store_pointer ? (*((void **) (e))) : (e)) + (c)->collection.advanced_destructor((c)->collection.destructor_data, \ + (c)->collection.store_pointer ? (*((void **) (e))) : (e)) /** @@ -139,8 +154,8 @@ * @param e the element */ #define cx_invoke_destructor(c, e) \ - if ((c)->simple_destructor) cx_invoke_simple_destructor(c,e); \ - if ((c)->advanced_destructor) cx_invoke_advanced_destructor(c,e) + if ((c)->collection.simple_destructor) cx_invoke_simple_destructor(c,e); \ + if ((c)->collection.advanced_destructor) cx_invoke_advanced_destructor(c,e) #ifdef __cplusplus } // extern "C"
--- a/ucx/cx/common.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/common.h Sun Oct 06 12:00:31 2024 +0200 @@ -101,7 +101,7 @@ * Function pointer compatible with fwrite-like functions. */ typedef size_t (*cx_write_func)( - void const *, + const void *, size_t, size_t, void *
--- a/ucx/cx/compare.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/compare.h Sun Oct 06 12:00:31 2024 +0200 @@ -48,8 +48,8 @@ * A comparator function comparing two collection elements. */ typedef int(*cx_compare_func)( - void const *left, - void const *right + const void *left, + const void *right ); #endif // CX_COMPARE_FUNC_DEFINED @@ -61,7 +61,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_int(void const *i1, void const *i2); +int cx_cmp_int(const void *i1, const void *i2); /** * Compares two integers of type long int. @@ -71,7 +71,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_longint(void const *i1, void const *i2); +int cx_cmp_longint(const void *i1, const void *i2); /** * Compares two integers of type long long. @@ -81,7 +81,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_longlong(void const *i1, void const *i2); +int cx_cmp_longlong(const void *i1, const void *i2); /** * Compares two integers of type int16_t. @@ -91,7 +91,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_int16(void const *i1, void const *i2); +int cx_cmp_int16(const void *i1, const void *i2); /** * Compares two integers of type int32_t. @@ -101,7 +101,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_int32(void const *i1, void const *i2); +int cx_cmp_int32(const void *i1, const void *i2); /** * Compares two integers of type int64_t. @@ -111,7 +111,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_int64(void const *i1, void const *i2); +int cx_cmp_int64(const void *i1, const void *i2); /** * Compares two integers of type unsigned int. @@ -121,7 +121,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_uint(void const *i1, void const *i2); +int cx_cmp_uint(const void *i1, const void *i2); /** * Compares two integers of type unsigned long int. @@ -131,7 +131,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_ulongint(void const *i1, void const *i2); +int cx_cmp_ulongint(const void *i1, const void *i2); /** * Compares two integers of type unsigned long long. @@ -141,7 +141,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_ulonglong(void const *i1, void const *i2); +int cx_cmp_ulonglong(const void *i1, const void *i2); /** * Compares two integers of type uint16_t. @@ -151,7 +151,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_uint16(void const *i1, void const *i2); +int cx_cmp_uint16(const void *i1, const void *i2); /** * Compares two integers of type uint32_t. @@ -161,7 +161,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_uint32(void const *i1, void const *i2); +int cx_cmp_uint32(const void *i1, const void *i2); /** * Compares two integers of type uint64_t. @@ -171,7 +171,7 @@ * @return -1, if *i1 is less than *i2, 0 if both are equal, * 1 if *i1 is greater than *i2 */ -int cx_cmp_uint64(void const *i1, void const *i2); +int cx_cmp_uint64(const void *i1, const void *i2); /** * Compares two real numbers of type float with precision 1e-6f. @@ -182,7 +182,7 @@ * 1 if *f1 is greater than *f2 */ -int cx_cmp_float(void const *f1, void const *f2); +int cx_cmp_float(const void *f1, const void *f2); /** * Compares two real numbers of type double with precision 1e-14. @@ -193,34 +193,34 @@ * 1 if *d1 is greater than *d2 */ int cx_cmp_double( - void const *d1, - void const *d2 + const void *d1, + const void *d2 ); /** * Compares the integer representation of two pointers. * - * @param ptr1 pointer to pointer one (intptr_t const*) - * @param ptr2 pointer to pointer two (intptr_t const*) + * @param ptr1 pointer to pointer one (const intptr_t*) + * @param ptr2 pointer to pointer two (const intptr_t*) * @return -1 if *ptr1 is less than *ptr2, 0 if both are equal, * 1 if *ptr1 is greater than *ptr2 */ int cx_cmp_intptr( - void const *ptr1, - void const *ptr2 + const void *ptr1, + const void *ptr2 ); /** * Compares the unsigned integer representation of two pointers. * - * @param ptr1 pointer to pointer one (uintptr_t const*) - * @param ptr2 pointer to pointer two (uintptr_t const*) + * @param ptr1 pointer to pointer one (const uintptr_t*) + * @param ptr2 pointer to pointer two (const uintptr_t*) * @return -1 if *ptr1 is less than *ptr2, 0 if both are equal, * 1 if *ptr1 is greater than *ptr2 */ int cx_cmp_uintptr( - void const *ptr1, - void const *ptr2 + const void *ptr1, + const void *ptr2 ); /** @@ -232,8 +232,8 @@ * 1 if ptr1 is greater than ptr2 */ int cx_cmp_ptr( - void const *ptr1, - void const *ptr2 + const void *ptr1, + const void *ptr2 ); #ifdef __cplusplus
--- a/ucx/cx/hash_key.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/hash_key.h Sun Oct 06 12:00:31 2024 +0200 @@ -46,7 +46,7 @@ /** Internal structure for a key within a hash map. */ struct cx_hash_key_s { /** The key data. */ - void const *data; + const void *data; /** * The key data length. */ @@ -81,7 +81,7 @@ * @return the hash key */ __attribute__((__warn_unused_result__)) -CxHashKey cx_hash_key_str(char const *str); +CxHashKey cx_hash_key_str(const char *str); /** * Computes a hash key from a byte array. @@ -92,7 +92,7 @@ */ __attribute__((__warn_unused_result__)) CxHashKey cx_hash_key_bytes( - unsigned char const *bytes, + const unsigned char *bytes, size_t len ); @@ -109,7 +109,7 @@ */ __attribute__((__warn_unused_result__)) CxHashKey cx_hash_key( - void const *obj, + const void *obj, size_t len );
--- a/ucx/cx/hash_map.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/hash_map.h Sun Oct 06 12:00:31 2024 +0200 @@ -69,7 +69,7 @@ * * If \p buckets is zero, an implementation defined default will be used. * - * If \p item_size is CX_STORE_POINTERS, the created map will be created as if + * If \p elem_size is CX_STORE_POINTERS, the created map will be created as if * cxMapStorePointers() was called immediately after creation. * * @note Iterators provided by this hash map implementation provide the remove operation. @@ -83,7 +83,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) CxMap *cxHashMapCreate( - CxAllocator const *allocator, + const CxAllocator *allocator, size_t itemsize, size_t buckets ); @@ -91,7 +91,7 @@ /** * Creates a new hash map with a default number of buckets. * - * If \p item_size is CX_STORE_POINTERS, the created map will be created as if + * If \p elem_size is CX_STORE_POINTERS, the created map will be created as if * cxMapStorePointers() was called immediately after creation. * * @note Iterators provided by this hash map implementation provide the remove operation.
--- a/ucx/cx/iterator.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/iterator.h Sun Oct 06 12:00:31 2024 +0200 @@ -38,15 +38,12 @@ #include "common.h" -/** - * The base of mutating and non-mutating iterators. - */ struct cx_iterator_base_s { /** * True iff the iterator points to valid data. */ __attribute__ ((__nonnull__)) - bool (*valid)(void const *); + bool (*valid)(const void *); /** * Returns a pointer to the current element. @@ -54,13 +51,13 @@ * When valid returns false, the behavior of this function is undefined. */ __attribute__ ((__nonnull__)) - void *(*current)(void const *); + void *(*current)(const void *); /** * Original implementation in case the function needs to be wrapped. */ __attribute__ ((__nonnull__)) - void *(*current_impl)(void const *); + void *(*current_impl)(const void *); /** * Advances the iterator. @@ -69,20 +66,10 @@ */ __attribute__ ((__nonnull__)) void (*next)(void *); - - /** - * Flag current element for removal, if possible. - * - * When valid returns false, the behavior of this function is undefined. - */ - __attribute__ ((__nonnull__)) - bool (*flag_removal)(void *); - /** * Indicates whether this iterator may remove elements. */ bool mutating; - /** * Internal flag for removing the current element when advancing. */ @@ -90,24 +77,35 @@ }; /** - * Internal iterator struct - use CxMutIterator. + * Declares base attributes for an iterator. + * Must be the first member of an iterator structure. */ -struct cx_mut_iterator_s { +#define CX_ITERATOR_BASE struct cx_iterator_base_s base + +/** + * Internal iterator struct - use CxIterator. + */ +struct cx_iterator_s { + CX_ITERATOR_BASE; /** - * The base properties of this iterator. - */ - struct cx_iterator_base_s base; - - /** - * Handle for the current element, if required. + * Handle for the current element. */ void *elem_handle; /** * Handle for the source collection, if any. */ - void *src_handle; + union { + /** + * Access for mutating iterators. + */ + void *m; + /** + * Access for normal iterators. + */ + const void *c; + } src_handle; /** * Field for storing a key-value pair. @@ -117,7 +115,7 @@ /** * A pointer to the key. */ - void const *key; + const void *key; /** * A pointer to the value. */ @@ -135,83 +133,29 @@ * Otherwise, this field is usually uninitialized. */ size_t index; + + /** + * The size of an individual element. + */ + size_t elem_size; + + /** + * May contain the total number of elements, if known. + * Shall be set to \c SIZE_MAX when the total number is unknown during iteration. + */ + size_t elem_count; }; /** - * Mutating iterator value type. - * - * An iterator points to a certain element in an (possibly unbounded) chain of elements. - * Iterators that are based on collections (which have a defined "first" element), are supposed - * to be "position-aware", which means that they keep track of the current index within the collection. - * - * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the - * iterator is based on a collection and the underlying collection is mutated by other means than this iterator - * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns) - * and MUST be re-obtained from the collection. + * Iterator type. * - * @see CxIterator - */ -typedef struct cx_mut_iterator_s CxMutIterator; - -/** - * Internal iterator struct - use CxIterator. - */ -struct cx_iterator_s { - - /** - * The base properties of this iterator. - */ - struct cx_iterator_base_s base; - - /** - * Handle for the current element, if required. - */ - void *elem_handle; - - /** - * Handle for the source collection, if any. - */ - void const *src_handle; - - /** - * Field for storing a key-value pair. - * May be used by iterators that iterate over k/v-collections. - */ - struct { - /** - * A pointer to the key. - */ - void const *key; - /** - * A pointer to the value. - */ - void *value; - } kv_data; - - /** - * Field for storing a slot number. - * May be used by iterators that iterate over multi-bucket collections. - */ - size_t slot; - - /** - * If the iterator is position-aware, contains the index of the element in the underlying collection. - * Otherwise, this field is usually uninitialized. - */ - size_t index; -}; - -/** - * Iterator value type. * An iterator points to a certain element in a (possibly unbounded) chain of elements. * Iterators that are based on collections (which have a defined "first" element), are supposed * to be "position-aware", which means that they keep track of the current index within the collection. * * @note Objects that are pointed to by an iterator are always mutable through that iterator. However, - * this iterator cannot mutate the collection itself (add or remove elements) and any mutation of the - * collection by other means makes this iterator invalid (regardless of what cxIteratorValid() returns). - * - * @see CxMutIterator + * any concurrent mutation of the collection other than by this iterator makes this iterator invalid + * and it must not be used anymore. */ typedef struct cx_iterator_s CxIterator; @@ -243,12 +187,20 @@ #define cxIteratorNext(iter) (iter).base.next(&iter) /** - * Flags the current element for removal. + * Flags the current element for removal, if this iterator is mutating. * * @param iter the iterator - * @return false if this iterator cannot remove the element */ -#define cxIteratorFlagRemoval(iter) (iter).base.flag_removal(&iter) +#define cxIteratorFlagRemoval(iter) (iter).base.remove |= (iter).base.mutating + +/** + * Obtains a reference to an arbitrary iterator. + * + * This is useful for APIs that expect some iterator as an argument. + * + * @param iter the iterator + */ +#define cxIteratorRef(iter) &((iter).base) /** * Loops over an iterator. @@ -259,4 +211,55 @@ #define cx_foreach(type, elem, iter) \ for (type elem; cxIteratorValid(iter) && (elem = (type)cxIteratorCurrent(iter)) != NULL ; cxIteratorNext(iter)) + +/** + * Creates an iterator for the specified plain array. + * + * The \p array can be \c NULL in which case the iterator will be immediately + * initialized such that #cxIteratorValid() returns \c false. + * + * + * @param array a pointer to the array (can be \c NULL) + * @param elem_size the size of one array element + * @param elem_count the number of elements in the array + * @return an iterator for the specified array + */ +__attribute__((__warn_unused_result__)) +CxIterator cxIterator( + const void *array, + size_t elem_size, + size_t elem_count +); + +/** + * Creates a mutating iterator for the specified plain array. + * + * While the iterator is in use, the array may only be altered by removing + * elements through #cxIteratorFlagRemoval(). Every other change to the array + * will bring this iterator to an undefined state. + * + * When \p remove_keeps_order is set to \c false, removing an element will only + * move the last element to the position of the removed element, instead of + * moving all subsequent elements by one. Usually, when the order of elements is + * not important, this parameter should be set to \c false. + * + * The \p array can be \c NULL in which case the iterator will be immediately + * initialized such that #cxIteratorValid() returns \c false. + * + * + * @param array a pointer to the array (can be \c NULL) + * @param elem_size the size of one array element + * @param elem_count the number of elements in the array + * @param remove_keeps_order \c true if the order of elements must be preserved + * when removing an element + * @return an iterator for the specified array + */ +__attribute__((__warn_unused_result__)) +CxIterator cxMutIterator( + void *array, + size_t elem_size, + size_t elem_count, + bool remove_keeps_order +); + #endif // UCX_ITERATOR_H
--- a/ucx/cx/linked_list.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/linked_list.h Sun Oct 06 12:00:31 2024 +0200 @@ -50,9 +50,9 @@ extern unsigned cx_linked_list_swap_sbo_size; /** - * Allocates a linked list for storing elements with \p item_size bytes each. + * Allocates a linked list for storing elements with \p elem_size bytes each. * - * If \p item_size is CX_STORE_POINTERS, the created list will be created as if + * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if * cxListStorePointers() was called immediately after creation and the compare * function will be automatically set to cx_cmp_ptr(), if none is given. * @@ -61,31 +61,31 @@ * @param comparator the comparator for the elements * (if \c NULL, and the list is not storing pointers, sort and find * functions will not work) - * @param item_size the size of each element in bytes + * @param elem_size the size of each element in bytes * @return the created list */ CxList *cxLinkedListCreate( - CxAllocator const *allocator, + const CxAllocator *allocator, cx_compare_func comparator, - size_t item_size + size_t elem_size ); /** - * Allocates a linked list for storing elements with \p item_size bytes each. + * Allocates a linked list for storing elements with \p elem_size bytes each. * * The list will use cxDefaultAllocator and no comparator function. If you want * to call functions that need a comparator, you must either set one immediately * after list creation or use cxLinkedListCreate(). * - * If \p item_size is CX_STORE_POINTERS, the created list will be created as if + * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if * cxListStorePointers() was called immediately after creation and the compare * function will be automatically set to cx_cmp_ptr(). * - * @param item_size the size of each element in bytes + * @param elem_size the size of each element in bytes * @return the created list */ -#define cxLinkedListCreateSimple(item_size) \ - cxLinkedListCreate(NULL, NULL, item_size) +#define cxLinkedListCreateSimple(elem_size) \ + cxLinkedListCreate(NULL, NULL, elem_size) /** * Finds the node at a certain index. @@ -104,12 +104,13 @@ * @param index the search index * @return the node found at the specified index */ +__attribute__((__nonnull__)) void *cx_linked_list_at( - void const *start, + const void *start, size_t start_index, ptrdiff_t loc_advance, size_t index -) __attribute__((__nonnull__)); +); /** * Finds the index of an element within a linked list. @@ -121,13 +122,14 @@ * @param elem a pointer to the element to find * @return the index of the element or a negative value if it could not be found */ +__attribute__((__nonnull__)) ssize_t cx_linked_list_find( - void const *start, + const void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func, - void const *elem -) __attribute__((__nonnull__)); + const void *elem +); /** * Finds the node containing an element within a linked list. @@ -141,14 +143,15 @@ * @param elem a pointer to the element to find * @return the index of the element or a negative value if it could not be found */ +__attribute__((__nonnull__)) ssize_t cx_linked_list_find_node( void **result, - void const *start, + const void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func, - void const *elem -) __attribute__((__nonnull__)); + const void *elem +); /** * Finds the first node in a linked list. @@ -161,10 +164,11 @@ * @param loc_prev the location of the \c prev pointer * @return a pointer to the first node */ +__attribute__((__nonnull__)) void *cx_linked_list_first( - void const *node, + const void *node, ptrdiff_t loc_prev -) __attribute__((__nonnull__)); +); /** * Finds the last node in a linked list. @@ -177,10 +181,11 @@ * @param loc_next the location of the \c next pointer * @return a pointer to the last node */ +__attribute__((__nonnull__)) void *cx_linked_list_last( - void const *node, + const void *node, ptrdiff_t loc_next -) __attribute__((__nonnull__)); +); /** * Finds the predecessor of a node in case it is not linked. @@ -192,11 +197,12 @@ * @param node the successor of the node to find * @return the node or \c NULL if \p node has no predecessor */ +__attribute__((__nonnull__)) void *cx_linked_list_prev( - void const *begin, + const void *begin, ptrdiff_t loc_next, - void const *node -) __attribute__((__nonnull__)); + const void *node +); /** * Adds a new node to a linked list. @@ -210,13 +216,14 @@ * @param loc_next the location of a \c next pointer within your node struct (required) * @param new_node a pointer to the node that shall be appended */ +__attribute__((__nonnull__(5))) void cx_linked_list_add( void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node -) __attribute__((__nonnull__(5))); +); /** * Prepends a new node to a linked list. @@ -230,13 +237,14 @@ * @param loc_next the location of a \c next pointer within your node struct (required) * @param new_node a pointer to the node that shall be prepended */ +__attribute__((__nonnull__(5))) void cx_linked_list_prepend( void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node -) __attribute__((__nonnull__(5))); +); /** * Links two nodes. @@ -246,12 +254,13 @@ * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) * @param loc_next the location of a \c next pointer within your node struct (required) */ +__attribute__((__nonnull__)) void cx_linked_list_link( void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next -) __attribute__((__nonnull__)); +); /** * Unlinks two nodes. @@ -263,12 +272,13 @@ * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) * @param loc_next the location of a \c next pointer within your node struct (required) */ +__attribute__((__nonnull__)) void cx_linked_list_unlink( void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next -) __attribute__((__nonnull__)); +); /** * Inserts a new node after a given node of a linked list. @@ -282,8 +292,9 @@ * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) * @param loc_next the location of a \c next pointer within your node struct (required) * @param node the node after which to insert (\c NULL if you want to prepend the node to the list) - * @param new_node a pointer to the node that shall be prepended + * @param new_node a pointer to the node that shall be inserted */ +__attribute__((__nonnull__(6))) void cx_linked_list_insert( void **begin, void **end, @@ -291,7 +302,7 @@ ptrdiff_t loc_next, void *node, void *new_node -) __attribute__((__nonnull__(6))); +); /** * Inserts a chain of nodes after a given node of a linked list. @@ -313,6 +324,7 @@ * @param insert_begin a pointer to the first node of the chain that shall be inserted * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) */ +__attribute__((__nonnull__(6))) void cx_linked_list_insert_chain( void **begin, void **end, @@ -321,7 +333,60 @@ void *node, void *insert_begin, void *insert_end -) __attribute__((__nonnull__(6))); +); + +/** + * Inserts a node into a sorted linked list. + * The new node must not be part of any list already. + * + * If the list starting with the node pointed to by \p begin is not sorted + * already, the behavior is undefined. + * + * @param begin a pointer to the begin node pointer (required) + * @param end a pointer to the end node pointer (if your list has one) + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) + * @param loc_next the location of a \c next pointer within your node struct (required) + * @param new_node a pointer to the node that shall be inserted + * @param cmp_func a compare function that will receive the node pointers + */ +__attribute__((__nonnull__(1, 5, 6))) +void cx_linked_list_insert_sorted( + void **begin, + void **end, + ptrdiff_t loc_prev, + ptrdiff_t loc_next, + void *new_node, + cx_compare_func cmp_func +); + +/** + * Inserts a chain of nodes into a sorted linked list. + * The chain must not be part of any list already. + * + * If either the list starting with the node pointed to by \p begin or the list + * starting with \p insert_begin is not sorted, the behavior is undefined. + * + * \attention In contrast to cx_linked_list_insert_chain(), the source chain + * will be broken and inserted into the target list so that the resulting list + * will be sorted according to \p cmp_func. That means, each node in the source + * chain may be re-linked with nodes from the target list. + * + * @param begin a pointer to the begin node pointer (required) + * @param end a pointer to the end node pointer (if your list has one) + * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) + * @param loc_next the location of a \c next pointer within your node struct (required) + * @param insert_begin a pointer to the first node of the chain that shall be inserted + * @param cmp_func a compare function that will receive the node pointers + */ +__attribute__((__nonnull__(1, 5, 6))) +void cx_linked_list_insert_sorted_chain( + void **begin, + void **end, + ptrdiff_t loc_prev, + ptrdiff_t loc_next, + void *insert_begin, + cx_compare_func cmp_func +); /** * Removes a node from the linked list. @@ -342,13 +407,14 @@ * @param loc_next the location of a \c next pointer within your node struct (required) * @param node the node to remove */ +__attribute__((__nonnull__(5))) void cx_linked_list_remove( void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node -) __attribute__((__nonnull__(5))); +); /** @@ -358,7 +424,7 @@ * @return the size of the list or zero if \p node is \c NULL */ size_t cx_linked_list_size( - void const *node, + const void *node, ptrdiff_t loc_next ); @@ -384,6 +450,7 @@ * @param loc_data the location of the \c data pointer within your node struct * @param cmp_func the compare function defining the sort order */ +__attribute__((__nonnull__(1, 6))) void cx_linked_list_sort( void **begin, void **end, @@ -391,7 +458,7 @@ ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func -) __attribute__((__nonnull__(1, 6))); +); /** @@ -407,13 +474,14 @@ * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the * right list, positive if the left list is larger than the right list, zero if both lists are equal. */ +__attribute__((__nonnull__(5))) int cx_linked_list_compare( - void const *begin_left, - void const *begin_right, + const void *begin_left, + const void *begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func -) __attribute__((__nonnull__(5))); +); /** * Reverses the order of the nodes in a linked list. @@ -423,12 +491,13 @@ * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) * @param loc_next the location of a \c next pointer within your node struct (required) */ +__attribute__((__nonnull__(1))) void cx_linked_list_reverse( void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next -) __attribute__((__nonnull__(1))); +); #ifdef __cplusplus } // extern "C"
--- a/ucx/cx/list.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/list.h Sun Oct 06 12:00:31 2024 +0200 @@ -52,15 +52,15 @@ * Structure for holding the base data of a list. */ struct cx_list_s { - CX_COLLECTION_MEMBERS + CX_COLLECTION_BASE; /** * The list class definition. */ - cx_list_class const *cl; + const cx_list_class *cl; /** * The actual implementation in case the list class is delegating. */ - cx_list_class const *climpl; + const cx_list_class *climpl; }; /** @@ -71,7 +71,7 @@ * Destructor function. * * Implementations SHALL invoke the content destructor functions if provided - * and SHALL deallocate the list memory, if an allocator is provided. + * and SHALL deallocate the list memory. */ void (*destructor)(struct cx_list_s *list); @@ -82,17 +82,29 @@ int (*insert_element)( struct cx_list_s *list, size_t index, - void const *data + const void *data ); /** * Member function for inserting multiple elements. * Implementors SHOULD see to performant implementations for corner cases. + * @see cx_list_default_insert_array() */ size_t (*insert_array)( struct cx_list_s *list, size_t index, - void const *data, + const void *data, + size_t n + ); + + /** + * Member function for inserting sorted elements into a sorted list. + * + * @see cx_list_default_insert_sorted() + */ + size_t (*insert_sorted)( + struct cx_list_s *list, + const void *sorted_data, size_t n ); @@ -100,8 +112,8 @@ * Member function for inserting an element relative to an iterator position. */ int (*insert_iter)( - struct cx_mut_iterator_s *iter, - void const *elem, + struct cx_iterator_s *iter, + const void *elem, int prepend ); @@ -120,6 +132,7 @@ /** * Member function for swapping two elements. + * @see cx_list_default_swap() */ int (*swap)( struct cx_list_s *list, @@ -131,7 +144,7 @@ * Member function for element lookup. */ void *(*at)( - struct cx_list_s const *list, + const struct cx_list_s *list, size_t index ); @@ -140,21 +153,24 @@ */ ssize_t (*find_remove)( struct cx_list_s *list, - void const *elem, + const void *elem, bool remove ); /** * Member function for sorting the list in-place. + * @see cx_list_default_sort() */ void (*sort)(struct cx_list_s *list); /** - * Member function for comparing this list to another list of the same type. + * Optional member function for comparing this list + * to another list of the same type. + * If set to \c NULL, comparison won't be optimized. */ int (*compare)( - struct cx_list_s const *list, - struct cx_list_s const *other + const struct cx_list_s *list, + const struct cx_list_s *other ); /** @@ -166,13 +182,87 @@ * Member function for returning an iterator pointing to the specified index. */ struct cx_iterator_s (*iterator)( - struct cx_list_s const *list, + const struct cx_list_s *list, size_t index, bool backward ); }; /** + * Default implementation of an array insert. + * + * This function uses the element insert function for each element of the array. + * + * Use this in your own list class if you do not want to implement an optimized + * version for your list. + * + * @param list the list + * @param index the index where to insert the data + * @param data a pointer to the array of data to insert + * @param n the number of elements to insert + * @return the number of elements actually inserted + */ +__attribute__((__nonnull__)) +size_t cx_list_default_insert_array( + struct cx_list_s *list, + size_t index, + const void *data, + size_t n +); + +/** + * Default implementation of a sorted insert. + * + * This function uses the array insert function to insert consecutive groups + * of sorted data. + * + * The source data \em must already be sorted wrt. the list's compare function. + * + * Use this in your own list class if you do not want to implement an optimized + * version for your list. + * + * @param list the list + * @param sorted_data a pointer to the array of pre-sorted data to insert + * @param n the number of elements to insert + * @return the number of elements actually inserted + */ +__attribute__((__nonnull__)) +size_t cx_list_default_insert_sorted( + struct cx_list_s *list, + const void *sorted_data, + size_t n +); + +/** + * Default unoptimized sort implementation. + * + * This function will copy all data to an array, sort the array with standard + * qsort, and then copy the data back to the list memory. + * + * Use this in your own list class if you do not want to implement an optimized + * version for your list. + * + * @param list the list that shall be sorted + */ +__attribute__((__nonnull__)) +void cx_list_default_sort(struct cx_list_s *list); + +/** + * Default unoptimized swap implementation. + * + * Use this in your own list class if you do not want to implement an optimized + * version for your list. + * + * @param list the list in which to swap + * @param i index of one element + * @param j index of the other element + * @return zero on success, non-zero when indices are out of bounds or memory + * allocation for the temporary buffer fails + */ +__attribute__((__nonnull__)) +int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j); + +/** * Common type for all list implementations. */ typedef struct cx_list_s CxList; @@ -212,8 +302,8 @@ * @see cxListStorePointers() */ __attribute__((__nonnull__)) -static inline bool cxListIsStoringPointers(CxList const *list) { - return list->store_pointer; +static inline bool cxListIsStoringPointers(const CxList *list) { + return list->collection.store_pointer; } /** @@ -223,8 +313,8 @@ * @return the number of currently stored elements */ __attribute__((__nonnull__)) -static inline size_t cxListSize(CxList const *list) { - return list->size; +static inline size_t cxListSize(const CxList *list) { + return list->collection.size; } /** @@ -238,9 +328,9 @@ __attribute__((__nonnull__)) static inline int cxListAdd( CxList *list, - void const *elem + const void *elem ) { - return list->cl->insert_element(list, list->size, elem); + return list->cl->insert_element(list, list->collection.size, elem); } /** @@ -262,10 +352,10 @@ __attribute__((__nonnull__)) static inline size_t cxListAddArray( CxList *list, - void const *array, + const void *array, size_t n ) { - return list->cl->insert_array(list, list->size, array, n); + return list->cl->insert_array(list, list->collection.size, array, n); } /** @@ -285,12 +375,28 @@ static inline int cxListInsert( CxList *list, size_t index, - void const *elem + const void *elem ) { return list->cl->insert_element(list, index, elem); } /** + * Inserts an item into a sorted list. + * + * @param list the list + * @param elem a pointer to the element to add + * @return zero on success, non-zero on memory allocation failure + */ +__attribute__((__nonnull__)) +static inline int cxListInsertSorted( + CxList *list, + const void *elem +) { + const void *data = list->collection.store_pointer ? &elem : elem; + return list->cl->insert_sorted(list, data, 1) == 0; +} + +/** * Inserts multiple items to the list at the specified index. * If \p index equals the list size, this is effectively cxListAddArray(). * @@ -313,13 +419,39 @@ static inline size_t cxListInsertArray( CxList *list, size_t index, - void const *array, + const void *array, size_t n ) { return list->cl->insert_array(list, index, array, n); } /** + * Inserts a sorted array into a sorted list. + * + * This method is usually more efficient than inserting each element separately, + * because consecutive chunks of sorted data are inserted in one pass. + * + * If there is not enough memory to add all elements, the returned value is + * less than \p n. + * + * If this list is storing pointers instead of objects \p array is expected to + * be an array of pointers. + * + * @param list the list + * @param array a pointer to the elements to add + * @param n the number of elements to add + * @return the number of added elements + */ +__attribute__((__nonnull__)) +static inline size_t cxListInsertSortedArray( + CxList *list, + const void *array, + size_t n +) { + return list->cl->insert_sorted(list, array, n); +} + +/** * Inserts an element after the current location of the specified iterator. * * The used iterator remains operational, but all other active iterators should @@ -336,10 +468,10 @@ */ __attribute__((__nonnull__)) static inline int cxListInsertAfter( - CxMutIterator *iter, - void const *elem + CxIterator *iter, + const void *elem ) { - return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0); + return ((struct cx_list_s *) iter->src_handle.m)->cl->insert_iter(iter, elem, 0); } /** @@ -359,10 +491,10 @@ */ __attribute__((__nonnull__)) static inline int cxListInsertBefore( - CxMutIterator *iter, - void const *elem + CxIterator *iter, + const void *elem ) { - return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1); + return ((struct cx_list_s *) iter->src_handle.m)->cl->insert_iter(iter, elem, 1); } /** @@ -444,7 +576,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline CxIterator cxListIteratorAt( - CxList const *list, + const CxList *list, size_t index ) { return list->cl->iterator(list, index, false); @@ -463,7 +595,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline CxIterator cxListBackwardsIteratorAt( - CxList const *list, + const CxList *list, size_t index ) { return list->cl->iterator(list, index, true); @@ -481,7 +613,7 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxListMutIteratorAt( +CxIterator cxListMutIteratorAt( CxList *list, size_t index ); @@ -499,7 +631,7 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxListMutBackwardsIteratorAt( +CxIterator cxListMutBackwardsIteratorAt( CxList *list, size_t index ); @@ -515,7 +647,7 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxListIterator(CxList const *list) { +static inline CxIterator cxListIterator(const CxList *list) { return list->cl->iterator(list, 0, false); } @@ -530,7 +662,7 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxListMutIterator(CxList *list) { +static inline CxIterator cxListMutIterator(CxList *list) { return cxListMutIteratorAt(list, 0); } @@ -546,8 +678,8 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxListBackwardsIterator(CxList const *list) { - return list->cl->iterator(list, list->size - 1, true); +static inline CxIterator cxListBackwardsIterator(const CxList *list) { + return list->cl->iterator(list, list->collection.size - 1, true); } /** @@ -561,8 +693,8 @@ * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) { - return cxListMutBackwardsIteratorAt(list, list->size - 1); +static inline CxIterator cxListMutBackwardsIterator(CxList *list) { + return cxListMutBackwardsIteratorAt(list, list->collection.size - 1); } /** @@ -577,8 +709,8 @@ */ __attribute__((__nonnull__)) static inline ssize_t cxListFind( - CxList const *list, - void const *elem + const CxList *list, + const void *elem ) { return list->cl->find_remove((CxList*)list, elem, false); } @@ -596,7 +728,7 @@ __attribute__((__nonnull__)) static inline ssize_t cxListFindRemove( CxList *list, - void const *elem + const void *elem ) { return list->cl->find_remove(list, elem, true); } @@ -636,8 +768,8 @@ */ __attribute__((__nonnull__)) int cxListCompare( - CxList const *list, - CxList const *other + const CxList *list, + const CxList *other ); /**
--- a/ucx/cx/map.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/map.h Sun Oct 06 12:00:31 2024 +0200 @@ -56,7 +56,10 @@ /** Structure for the UCX map. */ struct cx_map_s { - CX_COLLECTION_MEMBERS + /** + * Base attributes. + */ + CX_COLLECTION_BASE; /** The map class definition. */ cx_map_class *cl; }; @@ -110,7 +113,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) void *(*get)( - CxMap const *map, + const CxMap *map, CxHashKey key ); @@ -128,7 +131,7 @@ * Creates an iterator for this map. */ __attribute__((__nonnull__, __warn_unused_result__)) - CxIterator (*iterator)(CxMap const *map, enum cx_map_iterator_type type); + CxIterator (*iterator)(const CxMap *map, enum cx_map_iterator_type type); }; /** @@ -138,7 +141,7 @@ /** * A pointer to the key. */ - CxHashKey const *key; + const CxHashKey *key; /** * A pointer to the value. */ @@ -163,7 +166,7 @@ */ __attribute__((__nonnull__)) static inline void cxMapStoreObjects(CxMap *map) { - map->store_pointer = false; + map->collection.store_pointer = false; } /** @@ -180,10 +183,21 @@ */ __attribute__((__nonnull__)) static inline void cxMapStorePointers(CxMap *map) { - map->store_pointer = true; - map->item_size = sizeof(void *); + map->collection.store_pointer = true; + map->collection.elem_size = sizeof(void *); } +/** + * Returns true, if this map is storing pointers instead of the actual data. + * + * @param map + * @return true, if this map is storing pointers + * @see cxMapStorePointers() + */ +__attribute__((__nonnull__)) +static inline bool cxMapIsStoringPointers(const CxMap *map) { + return map->collection.store_pointer; +} /** * Deallocates the memory of the specified map. @@ -206,6 +220,17 @@ map->cl->clear(map); } +/** + * Returns the number of elements in this map. + * + * @param map the map + * @return the number of stored elements + */ +__attribute__((__nonnull__)) +static inline size_t cxMapSize(const CxMap *map) { + return map->collection.size; +} + // TODO: set-like map operations (union, intersect, difference) @@ -219,7 +244,7 @@ * @return an iterator for the currently stored values */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIteratorValues(CxMap const *map) { +static inline CxIterator cxMapIteratorValues(const CxMap *map) { return map->cl->iterator(map, CX_MAP_ITERATOR_VALUES); } @@ -235,7 +260,7 @@ * @return an iterator for the currently stored keys */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIteratorKeys(CxMap const *map) { +static inline CxIterator cxMapIteratorKeys(const CxMap *map) { return map->cl->iterator(map, CX_MAP_ITERATOR_KEYS); } @@ -253,7 +278,7 @@ * @see cxMapIteratorValues() */ __attribute__((__nonnull__, __warn_unused_result__)) -static inline CxIterator cxMapIterator(CxMap const *map) { +static inline CxIterator cxMapIterator(const CxMap *map) { return map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS); } @@ -268,7 +293,7 @@ * @return an iterator for the currently stored values */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxMapMutIteratorValues(CxMap *map); +CxIterator cxMapMutIteratorValues(CxMap *map); /** * Creates a mutating iterator over the keys of a map. @@ -282,7 +307,7 @@ * @return an iterator for the currently stored keys */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxMapMutIteratorKeys(CxMap *map); +CxIterator cxMapMutIteratorKeys(CxMap *map); /** * Creates a mutating iterator for a map. @@ -298,7 +323,7 @@ * @see cxMapMutIteratorValues() */ __attribute__((__nonnull__, __warn_unused_result__)) -CxMutIterator cxMapMutIterator(CxMap *map); +CxIterator cxMapMutIterator(CxMap *map); #ifdef __cplusplus } // end the extern "C" block here, because we want to start overloading @@ -366,7 +391,7 @@ __attribute__((__nonnull__)) static inline int cxMapPut( CxMap *map, - char const *key, + const char *key, void *value ) { return map->cl->put(map, cx_hash_key_str(key), value); @@ -381,7 +406,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline void *cxMapGet( - CxMap const *map, + const CxMap *map, CxHashKey const &key ) { return map->cl->get(map, key); @@ -396,7 +421,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline void *cxMapGet( - CxMap const *map, + const CxMap *map, cxstring const &key ) { return map->cl->get(map, cx_hash_key_cxstr(key)); @@ -411,7 +436,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline void *cxMapGet( - CxMap const *map, + const CxMap *map, cxmutstr const &key ) { return map->cl->get(map, cx_hash_key_cxstr(key)); @@ -426,8 +451,8 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline void *cxMapGet( - CxMap const *map, - char const *key + const CxMap *map, + const char *key ) { return map->cl->get(map, cx_hash_key_str(key)); } @@ -515,7 +540,7 @@ __attribute__((__nonnull__)) static inline void cxMapRemove( CxMap *map, - char const *key + const char *key ) { (void) map->cl->remove(map, cx_hash_key_str(key), true); } @@ -603,7 +628,7 @@ __attribute__((__nonnull__)) static inline void cxMapDetach( CxMap *map, - char const *key + const char *key ) { (void) map->cl->remove(map, cx_hash_key_str(key), false); } @@ -711,7 +736,7 @@ __attribute__((__nonnull__, __warn_unused_result__)) static inline void *cxMapRemoveAndGet( CxMap *map, - char const *key + const char *key ) { return map->cl->remove(map, cx_hash_key_str(key), !map->store_pointer); } @@ -780,7 +805,7 @@ __attribute__((__nonnull__)) static inline int cx_map_put_str( CxMap *map, - char const *key, + const char *key, void *value ) { return map->cl->put(map, cx_hash_key_str(key), value); @@ -799,7 +824,7 @@ cxstring: cx_map_put_cxstr, \ cxmutstr: cx_map_put_mustr, \ char*: cx_map_put_str, \ - char const*: cx_map_put_str) \ + const char*: cx_map_put_str) \ (map, key, value) /** @@ -811,7 +836,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline void *cx_map_get( - CxMap const *map, + const CxMap *map, CxHashKey key ) { return map->cl->get(map, key); @@ -826,7 +851,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline void *cx_map_get_cxstr( - CxMap const *map, + const CxMap *map, cxstring key ) { return map->cl->get(map, cx_hash_key_cxstr(key)); @@ -841,7 +866,7 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline void *cx_map_get_mustr( - CxMap const *map, + const CxMap *map, cxmutstr key ) { return map->cl->get(map, cx_hash_key_cxstr(key)); @@ -856,8 +881,8 @@ */ __attribute__((__nonnull__, __warn_unused_result__)) static inline void *cx_map_get_str( - CxMap const *map, - char const *key + const CxMap *map, + const char *key ) { return map->cl->get(map, cx_hash_key_str(key)); } @@ -874,7 +899,7 @@ cxstring: cx_map_get_cxstr, \ cxmutstr: cx_map_get_mustr, \ char*: cx_map_get_str, \ - char const*: cx_map_get_str) \ + const char*: cx_map_get_str) \ (map, key) /** @@ -928,7 +953,7 @@ __attribute__((__nonnull__)) static inline void cx_map_remove_str( CxMap *map, - char const *key + const char *key ) { (void) map->cl->remove(map, cx_hash_key_str(key), true); } @@ -952,7 +977,7 @@ cxstring: cx_map_remove_cxstr, \ cxmutstr: cx_map_remove_mustr, \ char*: cx_map_remove_str, \ - char const*: cx_map_remove_str) \ + const char*: cx_map_remove_str) \ (map, key) /** @@ -1010,7 +1035,7 @@ __attribute__((__nonnull__)) static inline void cx_map_detach_str( CxMap *map, - char const *key + const char *key ) { (void) map->cl->remove(map, cx_hash_key_str(key), false); } @@ -1034,7 +1059,7 @@ cxstring: cx_map_detach_cxstr, \ cxmutstr: cx_map_detach_mustr, \ char*: cx_map_detach_str, \ - char const*: cx_map_detach_str) \ + const char*: cx_map_detach_str) \ (map, key) /** @@ -1050,7 +1075,7 @@ CxMap *map, CxHashKey key ) { - return map->cl->remove(map, key, !map->store_pointer); + return map->cl->remove(map, key, !map->collection.store_pointer); } /** @@ -1066,7 +1091,7 @@ CxMap *map, cxstring key ) { - return map->cl->remove(map, cx_hash_key_cxstr(key), !map->store_pointer); + return map->cl->remove(map, cx_hash_key_cxstr(key), !map->collection.store_pointer); } /** @@ -1082,7 +1107,7 @@ CxMap *map, cxmutstr key ) { - return map->cl->remove(map, cx_hash_key_cxstr(key), !map->store_pointer); + return map->cl->remove(map, cx_hash_key_cxstr(key), !map->collection.store_pointer); } /** @@ -1096,9 +1121,9 @@ __attribute__((__nonnull__, __warn_unused_result__)) static inline void *cx_map_remove_and_get_str( CxMap *map, - char const *key + const char *key ) { - return map->cl->remove(map, cx_hash_key_str(key), !map->store_pointer); + return map->cl->remove(map, cx_hash_key_str(key), !map->collection.store_pointer); } /** @@ -1125,7 +1150,7 @@ cxstring: cx_map_remove_and_get_cxstr, \ cxmutstr: cx_map_remove_and_get_mustr, \ char*: cx_map_remove_and_get_str, \ - char const*: cx_map_remove_and_get_str) \ + const char*: cx_map_remove_and_get_str) \ (map, key) #endif // __cplusplus
--- a/ucx/cx/mempool.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/mempool.h Sun Oct 06 12:00:31 2024 +0200 @@ -52,7 +52,7 @@ */ struct cx_mempool_s { /** The provided allocator. */ - CxAllocator const *allocator; + const CxAllocator *allocator; /** * A destructor that shall be automatically registered for newly allocated memory.
--- a/ucx/cx/printf.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/printf.h Sun Oct 06 12:00:31 2024 +0200 @@ -64,7 +64,7 @@ int cx_fprintf( void *stream, cx_write_func wfc, - char const *fmt, + const char *fmt, ... ); @@ -83,7 +83,7 @@ int cx_vfprintf( void *stream, cx_write_func wfc, - char const *fmt, + const char *fmt, va_list ap ); @@ -101,8 +101,8 @@ */ __attribute__((__nonnull__(1, 2), __format__(printf, 2, 3))) cxmutstr cx_asprintf_a( - CxAllocator const *allocator, - char const *fmt, + const CxAllocator *allocator, + const char *fmt, ... ); @@ -134,8 +134,8 @@ */ __attribute__((__nonnull__)) cxmutstr cx_vasprintf_a( - CxAllocator const *allocator, - char const *fmt, + const CxAllocator *allocator, + const char *fmt, va_list ap ); @@ -168,12 +168,12 @@ /** * An \c sprintf like function which reallocates the string when the buffer is not large enough. * + * The size of the buffer will be updated in \p len when necessary. + * * \note The resulting string is guaranteed to be zero-terminated. - * That means, when the buffer needed to be reallocated, the new size of the buffer will be - * the length returned by this function plus one. * * @param str a pointer to the string buffer - * @param len the current length of the buffer + * @param len a pointer to the length of the buffer * @param fmt the format string * @param ... additional arguments * @return the length of produced string @@ -183,32 +183,32 @@ /** * An \c sprintf like function which reallocates the string when the buffer is not large enough. * + * The size of the buffer will be updated in \p len when necessary. + * * \note The resulting string is guaranteed to be zero-terminated. - * That means, when the buffer needed to be reallocated, the new size of the buffer will be - * the length returned by this function plus one. * * \attention The original buffer MUST have been allocated with the same allocator! * * @param alloc the allocator to use * @param str a pointer to the string buffer - * @param len the current length of the buffer + * @param len a pointer to the length of the buffer * @param fmt the format string * @param ... additional arguments * @return the length of produced string */ -__attribute__((__nonnull__(1, 2, 4), __format__(printf, 4, 5))) -int cx_sprintf_a(CxAllocator *alloc, char **str, size_t len, const char *fmt, ... ); +__attribute__((__nonnull__(1, 2, 3, 4), __format__(printf, 4, 5))) +int cx_sprintf_a(CxAllocator *alloc, char **str, size_t *len, const char *fmt, ... ); /** * An \c sprintf like function which reallocates the string when the buffer is not large enough. * + * The size of the buffer will be updated in \p len when necessary. + * * \note The resulting string is guaranteed to be zero-terminated. - * That means, when the buffer needed to be reallocated, the new size of the buffer will be - * the length returned by this function plus one. * * @param str a pointer to the string buffer - * @param len the current length of the buffer + * @param len a pointer to the length of the buffer * @param fmt the format string * @param ap argument list * @return the length of produced string @@ -218,38 +218,38 @@ /** * An \c sprintf like function which reallocates the string when the buffer is not large enough. * + * The size of the buffer will be updated in \p len when necessary. + * * \note The resulting string is guaranteed to be zero-terminated. - * That means, when the buffer needed to be reallocated, the new size of the buffer will be - * the length returned by this function plus one. * * \attention The original buffer MUST have been allocated with the same allocator! * * @param alloc the allocator to use * @param str a pointer to the string buffer - * @param len the current length of the buffer + * @param len a pointer to the length of the buffer * @param fmt the format string * @param ap argument list * @return the length of produced string */ __attribute__((__nonnull__)) -int cx_vsprintf_a(CxAllocator *alloc, char **str, size_t len, const char *fmt, va_list ap); +int cx_vsprintf_a(CxAllocator *alloc, char **str, size_t *len, const char *fmt, va_list ap); /** * An \c sprintf like function which allocates a new string when the buffer is not large enough. * + * The size of the buffer will be updated in \p len when necessary. + * * The location of the resulting string will \em always be stored to \p str. When the buffer * was sufficiently large, \p buf itself will be stored to the location of \p str. * * \note The resulting string is guaranteed to be zero-terminated. - * That means, when the buffer needed to be reallocated, the new size of the buffer will be - * the length returned by this function plus one. * * \remark When a new string needed to be allocated, the contents of \p buf will be * poisoned after the call, because this function tries to produce the string in \p buf, first. * * @param buf a pointer to the buffer - * @param len the length of the buffer + * @param len a pointer to the length of the buffer * @param str a pointer to the location * @param fmt the format string * @param ... additional arguments @@ -260,42 +260,42 @@ /** * An \c sprintf like function which allocates a new string when the buffer is not large enough. * + * The size of the buffer will be updated in \p len when necessary. + * * The location of the resulting string will \em always be stored to \p str. When the buffer * was sufficiently large, \p buf itself will be stored to the location of \p str. * * \note The resulting string is guaranteed to be zero-terminated. - * That means, when the buffer needed to be reallocated, the new size of the buffer will be - * the length returned by this function plus one. * * \remark When a new string needed to be allocated, the contents of \p buf will be * poisoned after the call, because this function tries to produce the string in \p buf, first. * * @param alloc the allocator to use * @param buf a pointer to the buffer - * @param len the length of the buffer + * @param len a pointer to the length of the buffer * @param str a pointer to the location * @param fmt the format string * @param ... additional arguments * @return the length of produced string */ __attribute__((__nonnull__(1, 2, 4, 5), __format__(printf, 5, 6))) -int cx_sprintf_sa(CxAllocator *alloc, char *buf, size_t len, char **str, const char *fmt, ... ); +int cx_sprintf_sa(CxAllocator *alloc, char *buf, size_t *len, char **str, const char *fmt, ... ); /** * An \c sprintf like function which allocates a new string when the buffer is not large enough. * + * The size of the buffer will be updated in \p len when necessary. + * * The location of the resulting string will \em always be stored to \p str. When the buffer * was sufficiently large, \p buf itself will be stored to the location of \p str. * * \note The resulting string is guaranteed to be zero-terminated. - * That means, when the buffer needed to be reallocated, the new size of the buffer will be - * the length returned by this function plus one. * * \remark When a new string needed to be allocated, the contents of \p buf will be * poisoned after the call, because this function tries to produce the string in \p buf, first. * * @param buf a pointer to the buffer - * @param len the length of the buffer + * @param len a pointer to the length of the buffer * @param str a pointer to the location * @param fmt the format string * @param ap argument list @@ -306,26 +306,26 @@ /** * An \c sprintf like function which allocates a new string when the buffer is not large enough. * + * The size of the buffer will be updated in \p len when necessary. + * * The location of the resulting string will \em always be stored to \p str. When the buffer * was sufficiently large, \p buf itself will be stored to the location of \p str. * * \note The resulting string is guaranteed to be zero-terminated. - * That means, when the buffer needed to be reallocated, the new size of the buffer will be - * the length returned by this function plus one. * * \remark When a new string needed to be allocated, the contents of \p buf will be * poisoned after the call, because this function tries to produce the string in \p buf, first. * * @param alloc the allocator to use * @param buf a pointer to the buffer - * @param len the length of the buffer + * @param len a pointer to the length of the buffer * @param str a pointer to the location * @param fmt the format string * @param ap argument list * @return the length of produced string */ __attribute__((__nonnull__)) -int cx_vsprintf_sa(CxAllocator *alloc, char *buf, size_t len, char **str, const char *fmt, va_list ap); +int cx_vsprintf_sa(CxAllocator *alloc, char *buf, size_t *len, char **str, const char *fmt, va_list ap); #ifdef __cplusplus
--- a/ucx/cx/string.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/string.h Sun Oct 06 12:00:31 2024 +0200 @@ -72,7 +72,7 @@ * \note The string is not necessarily \c NULL terminated. * Always use the length. */ - char const *ptr; + const char *ptr; /** The length of the string */ size_t length; }; @@ -97,7 +97,7 @@ /** * Optional array of more delimiters. */ - cxstring const *delim_more; + const cxstring *delim_more; /** * Length of the array containing more delimiters. */ @@ -213,7 +213,7 @@ * @see cx_strn() */ __attribute__((__warn_unused_result__, __nonnull__)) -cxstring cx_str(char const *cstring); +cxstring cx_str(const char *cstring); /** @@ -234,7 +234,7 @@ */ __attribute__((__warn_unused_result__)) cxstring cx_strn( - char const *cstring, + const char *cstring, size_t length ); @@ -257,8 +257,8 @@ * The pointer in the struct is set to \c NULL and the length is set to zero. * * \note There is no implementation for cxstring, because it is unlikely that - * you ever have a \c char \c const* you are really supposed to free. If you - * encounter such situation, you should double-check your code. + * you ever have a <code>const char*</code> you are really supposed to free. + * If you encounter such situation, you should double-check your code. * * @param str the string to free */ @@ -271,15 +271,15 @@ * The pointer in the struct is set to \c NULL and the length is set to zero. * * \note There is no implementation for cxstring, because it is unlikely that - * you ever have a \c char \c const* you are really supposed to free. If you - * encounter such situation, you should double-check your code. + * you ever have a <code>const char*</code> you are really supposed to free. + * If you encounter such situation, you should double-check your code. * * @param alloc the allocator * @param str the string to free */ __attribute__((__nonnull__)) void cx_strfree_a( - CxAllocator const *alloc, + const CxAllocator *alloc, cxmutstr *str ); @@ -319,7 +319,7 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) cxmutstr cx_strcat_ma( - CxAllocator const *alloc, + const CxAllocator *alloc, cxmutstr str, size_t count, ... @@ -629,7 +629,7 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) size_t cx_strsplit_a( - CxAllocator const *allocator, + const CxAllocator *allocator, cxstring string, cxstring delim, size_t limit, @@ -678,7 +678,7 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) size_t cx_strsplit_ma( - CxAllocator const *allocator, + const CxAllocator *allocator, cxmutstr string, cxstring delim, size_t limit, @@ -725,8 +725,8 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) int cx_strcmp_p( - void const *s1, - void const *s2 + const void *s1, + const void *s2 ); /** @@ -741,8 +741,8 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) int cx_strcasecmp_p( - void const *s1, - void const *s2 + const void *s1, + const void *s2 ); @@ -760,7 +760,7 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) cxmutstr cx_strdup_a( - CxAllocator const *allocator, + const CxAllocator *allocator, cxstring string ); @@ -928,7 +928,7 @@ */ __attribute__((__warn_unused_result__, __nonnull__)) cxmutstr cx_strreplacen_a( - CxAllocator const *allocator, + const CxAllocator *allocator, cxstring str, cxstring pattern, cxstring replacement, @@ -1070,7 +1070,7 @@ __attribute__((__nonnull__)) void cx_strtok_delim( CxStrtokCtx *ctx, - cxstring const *delim, + const cxstring *delim, size_t count );
--- a/ucx/cx/test.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/test.h Sun Oct 06 12:00:31 2024 +0200 @@ -96,7 +96,7 @@ * Function pointer compatible with fwrite-like functions. */ typedef size_t (*cx_write_func)( - void const *, + const void *, size_t, size_t, void * @@ -134,7 +134,7 @@ unsigned int failure; /** The optional name of this test suite. */ - char const *name; + const char *name; /** * Internal list of test cases. @@ -148,7 +148,7 @@ * @param name optional name of the suite * @return a new test suite */ -static inline CxTestSuite* cx_test_suite_new(char const *name) { +static inline CxTestSuite* cx_test_suite_new(const char *name) { CxTestSuite* suite = (CxTestSuite*) malloc(sizeof(CxTestSuite)); if (suite != NULL) { suite->name = name; @@ -276,7 +276,7 @@ * @param message the message that shall be printed out on failure */ #define CX_TEST_ASSERTM(condition,message) if (!(condition)) { \ - char const* _assert_msg_ = message; \ + const char *_assert_msg_ = message; \ _writefnc_(_assert_msg_, 1, strlen(_assert_msg_), _output_); \ _writefnc_(".\n", 1, 2, _output_); \ _suite_->failure++; \
--- a/ucx/cx/tree.h Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/cx/tree.h Sun Oct 06 12:00:31 2024 +0200 @@ -38,30 +38,1215 @@ #include "common.h" +#include "collection.h" + #ifdef __cplusplus extern "C" { #endif +/** + * A depth-first tree iterator. + * + * This iterator is not position-aware in a strict sense, as it does not assume + * a particular order of elements in the tree. However, the iterator keeps track + * of the number of nodes it has passed in a counter variable. + * Each node, regardless of the number of passes, is counted only once. + * + * @note Objects that are pointed to by an iterator are mutable through that + * iterator. However, if the + * underlying data structure is mutated by other means than this iterator (e.g. + * elements added or removed), the iterator becomes invalid (regardless of what + * cxIteratorValid() returns). + * + * @see CxIterator + */ +typedef struct cx_tree_iterator_s { + /** + * Base members. + */ + CX_ITERATOR_BASE; + /** + * Indicates whether the subtree below the current node shall be skipped. + */ + bool skip; + /** + * Set to true, when the iterator shall visit a node again + * when all it's children have been processed. + */ + bool visit_on_exit; + /** + * True, if this iterator is currently leaving the node. + */ + bool exiting; + /** + * Offset in the node struct for the children linked list. + */ + ptrdiff_t loc_children; + /** + * Offset in the node struct for the next pointer. + */ + ptrdiff_t loc_next; + /** + * The total number of distinct nodes that have been passed so far. + */ + size_t counter; + /** + * The currently observed node. + * + * This is the same what cxIteratorCurrent() would return. + */ + void *node; + /** + * Stores a copy of the next pointer of the visited node. + * Allows freeing a node on exit without corrupting the iteration. + */ + void *node_next; + /** + * Internal stack. + * Will be automatically freed once the iterator becomes invalid. + * + * If you want to discard the iterator before, you need to manually + * call cxTreeIteratorDispose(). + */ + void **stack; + /** + * Internal capacity of the stack. + */ + size_t stack_capacity; + union { + /** + * Internal stack size. + */ + size_t stack_size; + /** + * The current depth in the tree. + */ + size_t depth; + }; +} CxTreeIterator; +/** + * An element in a visitor queue. + */ +struct cx_tree_visitor_queue_s { + /** + * The tree node to visit. + */ + void *node; + /** + * The depth of the node. + */ + size_t depth; + /** + * The next element in the queue or \c NULL. + */ + struct cx_tree_visitor_queue_s *next; +}; + +/** + * A breadth-first tree iterator. + * + * This iterator needs to maintain a visitor queue that will be automatically + * freed once the iterator becomes invalid. + * If you want to discard the iterator before, you MUST manually call + * cxTreeVisitorDispose(). + * + * This iterator is not position-aware in a strict sense, as it does not assume + * a particular order of elements in the tree. However, the iterator keeps track + * of the number of nodes it has passed in a counter variable. + * Each node, regardless of the number of passes, is counted only once. + * + * @note Objects that are pointed to by an iterator are mutable through that + * iterator. However, if the + * underlying data structure is mutated by other means than this iterator (e.g. + * elements added or removed), the iterator becomes invalid (regardless of what + * cxIteratorValid() returns). + * + * @see CxIterator + */ +typedef struct cx_tree_visitor_s { + /** + * Base members. + */ + CX_ITERATOR_BASE; + /** + * Indicates whether the subtree below the current node shall be skipped. + */ + bool skip; + /** + * Offset in the node struct for the children linked list. + */ + ptrdiff_t loc_children; + /** + * Offset in the node struct for the next pointer. + */ + ptrdiff_t loc_next; + /** + * The total number of distinct nodes that have been passed so far. + */ + size_t counter; + /** + * The currently observed node. + * + * This is the same what cxIteratorCurrent() would return. + */ + void *node; + /** + * The current depth in the tree. + */ + size_t depth; + /** + * The next element in the visitor queue. + */ + struct cx_tree_visitor_queue_s *queue_next; + /** + * The last element in the visitor queue. + */ + struct cx_tree_visitor_queue_s *queue_last; +} CxTreeVisitor; + +/** + * Releases internal memory of the given tree iterator. + * @param iter the iterator + */ + __attribute__((__nonnull__)) +static inline void cxTreeIteratorDispose(CxTreeIterator *iter) { + free(iter->stack); + iter->stack = NULL; +} + +/** + * Releases internal memory of the given tree visitor. + * @param visitor the visitor + */ +__attribute__((__nonnull__)) +static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) { + struct cx_tree_visitor_queue_s *q = visitor->queue_next; + while (q != NULL) { + struct cx_tree_visitor_queue_s *next = q->next; + free(q); + q = next; + } +} + +/** + * Advises the iterator to skip the subtree below the current node and + * also continues the current loop. + * + * @param iterator the iterator + */ +#define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue + +/** + * Advises the visitor to skip the subtree below the current node and + * also continues the current loop. + * + * @param visitor the visitor + */ +#define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor) + +/** + * Links a node to a (new) parent. + * + * If the node has already a parent, it is unlinked, first. + * If the parent has children already, the node is \em appended to the list + * of all currently existing children. + * + * @param parent the parent node + * @param node the node that shall be linked + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_last_child optional offset in the node struct for the pointer to + * the last child in the linked list (negative if there is no such pointer) + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @see cx_tree_unlink() + */ __attribute__((__nonnull__)) void cx_tree_link( - void * restrict parent, - void * restrict node, + void *restrict parent, + void *restrict node, ptrdiff_t loc_parent, ptrdiff_t loc_children, + ptrdiff_t loc_last_child, ptrdiff_t loc_prev, ptrdiff_t loc_next ); +/** + * Unlinks a node from its parent. + * + * If the node has no parent, this function does nothing. + * + * @param node the node that shall be unlinked from its parent + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_last_child optional offset in the node struct for the pointer to + * the last child in the linked list (negative if there is no such pointer) + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @see cx_tree_link() + */ __attribute__((__nonnull__)) void cx_tree_unlink( void *node, ptrdiff_t loc_parent, ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +); + +/** + * Function pointer for a search function. + * + * A function of this kind shall check if the specified \p node + * contains the given \p data or if one of the children might contain + * the data. + * + * The function should use the returned integer to indicate how close the + * match is, where a negative number means that it does not match at all. + * + * For example if a tree stores file path information, a node that is + * describing a parent directory of a filename that is searched, shall + * return a positive number to indicate that a child node might contain the + * searched item. On the other hand, if the node denotes a path that is not a + * prefix of the searched filename, the function would return -1 to indicate + * that the search does not need to be continued in that branch. + * + * @param node the node that is currently investigated + * @param data the data that is searched for + * + * @return 0 if the node contains the data, + * positive if one of the children might contain the data, + * negative if neither the node, nor the children contains the data + */ +typedef int (*cx_tree_search_data_func)(const void *node, const void *data); + + +/** + * Function pointer for a search function. + * + * A function of this kind shall check if the specified \p node + * contains the same \p data as \p new_node or if one of the children might + * contain the data. + * + * The function should use the returned integer to indicate how close the + * match is, where a negative number means that it does not match at all. + * + * For example if a tree stores file path information, a node that is + * describing a parent directory of a filename that is searched, shall + * return a positive number to indicate that a child node might contain the + * searched item. On the other hand, if the node denotes a path that is not a + * prefix of the searched filename, the function would return -1 to indicate + * that the search does not need to be continued in that branch. + * + * @param node the node that is currently investigated + * @param new_node a new node with the information which is searched + * + * @return 0 if \p node contains the same data as \p new_node, + * positive if one of the children might contain the data, + * negative if neither the node, nor the children contains the data + */ +typedef int (*cx_tree_search_func)(const void *node, const void *new_node); + +/** + * Searches for data in a tree. + * + * When the data cannot be found exactly, the search function might return a + * closest result which might be a good starting point for adding a new node + * to the tree (see also #cx_tree_add()). + * + * Depending on the tree structure it is not necessarily guaranteed that the + * "closest" match is uniquely defined. This function will search for a node + * with the best match according to the \p sfunc (meaning: the return value of + * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary + * node matching the criteria is returned. + * + * @param root the root node + * @param data the data to search for + * @param sfunc the search function + * @param result where the result shall be stored + * @param loc_children offset in the node struct for the children linked list + * @param loc_next offset in the node struct for the next pointer + * @return zero if the node was found exactly, positive if a node was found that + * could contain the node (but doesn't right now), negative if the tree does not + * contain any node that might be related to the searched data + */ +__attribute__((__nonnull__)) +int cx_tree_search_data( + const void *root, + const void *data, + cx_tree_search_data_func sfunc, + void **result, + ptrdiff_t loc_children, + ptrdiff_t loc_next +); + +/** + * Searches for a node in a tree. + * + * When no node with the same data can be found, the search function might + * return a closest result which might be a good starting point for adding the + * new node to the tree (see also #cx_tree_add()). + * + * Depending on the tree structure it is not necessarily guaranteed that the + * "closest" match is uniquely defined. This function will search for a node + * with the best match according to the \p sfunc (meaning: the return value of + * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary + * node matching the criteria is returned. + * + * @param root the root node + * @param node the node to search for + * @param sfunc the search function + * @param result where the result shall be stored + * @param loc_children offset in the node struct for the children linked list + * @param loc_next offset in the node struct for the next pointer + * @return zero if the node was found exactly, positive if a node was found that + * could contain the node (but doesn't right now), negative if the tree does not + * contain any node that might be related to the searched data + */ +__attribute__((__nonnull__)) +int cx_tree_search( + const void *root, + const void *node, + cx_tree_search_func sfunc, + void **result, + ptrdiff_t loc_children, + ptrdiff_t loc_next +); + +/** + * Creates a depth-first iterator for a tree with the specified root node. + * + * @note A tree iterator needs to maintain a stack of visited nodes, which is + * allocated using stdlib malloc(). + * When the iterator becomes invalid, this memory is automatically released. + * However, if you wish to cancel the iteration before the iterator becomes + * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release + * the memory. + * + * @remark The returned iterator does not support cxIteratorFlagRemoval(). + * + * @param root the root node + * @param visit_on_exit set to true, when the iterator shall visit a node again + * after processing all children + * @param loc_children offset in the node struct for the children linked list + * @param loc_next offset in the node struct for the next pointer + * @return the new tree iterator + * @see cxTreeIteratorDispose() + */ +CxTreeIterator cx_tree_iterator( + void *root, + bool visit_on_exit, + ptrdiff_t loc_children, + ptrdiff_t loc_next +); + +/** + * Creates a breadth-first iterator for a tree with the specified root node. + * + * @note A tree visitor needs to maintain a queue of to be visited nodes, which + * is allocated using stdlib malloc(). + * When the visitor becomes invalid, this memory is automatically released. + * However, if you wish to cancel the iteration before the visitor becomes + * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release + * the memory. + * + * @remark The returned iterator does not support cxIteratorFlagRemoval(). + * + * @param root the root node + * @param loc_children offset in the node struct for the children linked list + * @param loc_next offset in the node struct for the next pointer + * @return the new tree visitor + * @see cxTreeVisitorDispose() + */ +CxTreeVisitor cx_tree_visitor( + void *root, + ptrdiff_t loc_children, + ptrdiff_t loc_next +); + +/** + * Describes a function that creates a tree node from the specified data. + * The first argument points to the data the node shall contain and + * the second argument may be used for additional data (e.g. an allocator). + * Functions of this type shall either return a new pointer to a newly + * created node or \c NULL when allocation fails. + * + * \note the function may leave the node pointers in the struct uninitialized. + * The caller is responsible to set them according to the intended use case. + */ +typedef void *(*cx_tree_node_create_func)(const void *, void *); + +/** + * The local search depth for a new subtree when adding multiple elements. + * The default value is 3. + * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to + * implement optimized insertion of multiple elements into a tree. + */ +extern unsigned int cx_tree_add_look_around_depth; + +/** + * Adds multiple elements efficiently to a tree. + * + * Once an element cannot be added to the tree, this function returns, leaving + * the iterator in a valid state pointing to the element that could not be + * added. + * Also, the pointer of the created node will be stored to \p failed. + * The integer returned by this function denotes the number of elements obtained + * from the \p iter that have been successfully processed. + * When all elements could be processed, a \c NULL pointer will be written to + * \p failed. + * + * The advantage of this function compared to multiple invocations of + * #cx_tree_add() is that the search for the insert locations is not always + * started from the root node. + * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes + * of the current insert location before starting from the root node again. + * When the variable is set to zero, only the last found location is checked + * again. + * + * Refer to the documentation of #cx_tree_add() for more details. + * + * @param iter a pointer to an arbitrary iterator + * @param num the maximum number of elements to obtain from the iterator + * @param sfunc a search function + * @param cfunc a node creation function + * @param cdata optional additional data + * @param root the root node of the tree + * @param failed location where the pointer to a failed node shall be stored + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_last_child optional offset in the node struct for the pointer to + * the last child in the linked list (negative if there is no such pointer) + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @return the number of nodes created and added + * @see cx_tree_add() + */ +__attribute__((__nonnull__(1, 3, 4, 6, 7))) +size_t cx_tree_add_iter( + struct cx_iterator_base_s *iter, + size_t num, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **failed, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +); + +/** + * Adds multiple elements efficiently to a tree. + * + * Once an element cannot be added to the tree, this function returns, storing + * the pointer of the created node to \p failed. + * The integer returned by this function denotes the number of elements from + * the \p src array that have been successfully processed. + * When all elements could be processed, a \c NULL pointer will be written to + * \p failed. + * + * The advantage of this function compared to multiple invocations of + * #cx_tree_add() is that the search for the insert locations is not always + * started from the root node. + * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes + * of the current insert location before starting from the root node again. + * When the variable is set to zero, only the last found location is checked + * again. + * + * Refer to the documentation of #cx_tree_add() for more details. + * + * @param src a pointer to the source data array + * @param num the number of elements in the \p src array + * @param elem_size the size of each element in the \p src array + * @param sfunc a search function + * @param cfunc a node creation function + * @param cdata optional additional data + * @param failed location where the pointer to a failed node shall be stored + * @param root the root node of the tree + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_last_child optional offset in the node struct for the pointer to + * the last child in the linked list (negative if there is no such pointer) + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @return the number of array elements successfully processed + * @see cx_tree_add() + */ +__attribute__((__nonnull__(1, 4, 5, 7, 8))) +size_t cx_tree_add_array( + const void *src, + size_t num, + size_t elem_size, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **failed, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +); + +/** + * Adds data to a tree. + * + * An adequate location where to add the new tree node is searched with the + * specified \p sfunc. + * + * When a location is found, the \p cfunc will be invoked with \p cdata. + * + * The node returned by \p cfunc will be linked into the tree. + * When \p sfunc returned a positive integer, the new node will be linked as a + * child. The other children (now siblings of the new node) are then checked + * with \p sfunc, whether they could be children of the new node and re-linked + * accordingly. + * + * When \p sfunc returned zero and the found node has a parent, the new + * node will be added as sibling - otherwise, the new node will be added + * as a child. + * + * When \p sfunc returned a negative value, the new node will not be added to + * the tree and this function returns a non-zero value. + * The caller should check if \p cnode contains a node pointer and deal with the + * node that could not be added. + * + * This function also returns a non-zero value when \p cfunc tries to allocate + * a new node but fails to do so. In that case, the pointer stored to \p cnode + * will be \c NULL. + * + * Multiple elements can be added more efficiently with + * #cx_tree_add_array() or #cx_tree_add_iter(). + * + * @param src a pointer to the data + * @param sfunc a search function + * @param cfunc a node creation function + * @param cdata optional additional data + * @param cnode the location where a pointer to the new node is stored + * @param root the root node of the tree + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_last_child optional offset in the node struct for the pointer to + * the last child in the linked list (negative if there is no such pointer) + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @return zero when a new node was created and added to the tree, + * non-zero otherwise + */ +__attribute__((__nonnull__(1, 2, 3, 5, 6))) +int cx_tree_add( + const void *src, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **cnode, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, ptrdiff_t loc_prev, ptrdiff_t loc_next ); + +/** + * Tree class type. + */ +typedef struct cx_tree_class_s cx_tree_class; + +/** + * Base structure that can be used for tree nodes in a #CxTree. + */ +struct cx_tree_node_base_s { + /** + * Pointer to the parent. + */ + struct cx_tree_node_base_s *parent; + /** + * Pointer to the first child. + */ + struct cx_tree_node_base_s *children; + /** + * Pointer to the last child. + */ + struct cx_tree_node_base_s *last_child; + /** + * Pointer to the previous sibling. + */ + struct cx_tree_node_base_s *prev; + /** + * Pointer to the next sibling. + */ + struct cx_tree_node_base_s *next; +}; + +/** + * Structure for holding the base data of a tree. + */ +struct cx_tree_s { + /** + * The tree class definition. + */ + const cx_tree_class *cl; + + /** + * Allocator to allocate new nodes. + */ + const CxAllocator *allocator; + + /** + * A pointer to the root node. + * + * Will be \c NULL when \c size is 0. + */ + void *root; + + /** + * A function to create new nodes. + * + * Invocations to this function will receive a pointer to this tree + * structure as second argument. + * + * Nodes MAY use #cx_tree_node_base_s as base layout, but do not need to. + */ + cx_tree_node_create_func node_create; + + /** + * An optional simple destructor for the tree nodes. + */ + cx_destructor_func simple_destructor; + + /** + * An optional advanced destructor for the tree nodes. + */ + cx_destructor_func2 advanced_destructor; + + /** + * The pointer to additional data that is passed to the advanced destructor. + */ + void *destructor_data; + + /** + * A function to compare two nodes. + */ + cx_tree_search_func search; + + /** + * A function to compare a node with data. + */ + cx_tree_search_data_func search_data; + + /** + * The number of currently stored elements. + */ + size_t size; + + /** + * Offset in the node struct for the parent pointer. + */ + ptrdiff_t loc_parent; + + /** + * Offset in the node struct for the children linked list. + */ + ptrdiff_t loc_children; + + /** + * Optional offset in the node struct for the pointer to the last child + * in the linked list (negative if there is no such pointer). + */ + ptrdiff_t loc_last_child; + + /** + * Offset in the node struct for the previous sibling pointer. + */ + ptrdiff_t loc_prev; + + /** + * Offset in the node struct for the next sibling pointer. + */ + ptrdiff_t loc_next; +}; + +/** + * Macro to roll out the #cx_tree_node_base_s structure with a custom + * node type. + */ +#define CX_TREE_NODE_BASE(type) \ + type *parent; \ + type *children;\ + type *last_child;\ + type *prev;\ + type *next + +/** + * Macro for specifying the layout of a base node tree. + */ +#define cx_tree_node_base_layout \ + offsetof(struct cx_tree_node_base_s, parent),\ + offsetof(struct cx_tree_node_base_s, children),\ + offsetof(struct cx_tree_node_base_s, last_child),\ + offsetof(struct cx_tree_node_base_s, prev), \ + offsetof(struct cx_tree_node_base_s, next) + +/** + * Macro for obtaining the node pointer layout for a specific tree. + */ +#define cx_tree_node_layout(tree) \ + (tree)->loc_parent,\ + (tree)->loc_children,\ + (tree)->loc_last_child,\ + (tree)->loc_prev, \ + (tree)->loc_next + +/** + * The class definition for arbitrary trees. + */ +struct cx_tree_class_s { + /** + * Destructor function. + * + * Implementations SHALL invoke the node destructor functions if provided + * and SHALL deallocate the tree memory. + */ + void (*destructor)(struct cx_tree_s *); + + /** + * Member function for inserting a single element. + * + * Implementations SHALL NOT simply invoke \p insert_many as this comes + * with too much overhead. + */ + int (*insert_element)( + struct cx_tree_s *tree, + const void *data + ); + + /** + * Member function for inserting multiple elements. + * + * Implementations SHALL avoid to perform a full search in the tree for + * every element even though the source data MAY be unsorted. + */ + size_t (*insert_many)( + struct cx_tree_s *tree, + struct cx_iterator_base_s *iter, + size_t n + ); + + /** + * Member function for finding a node. + */ + void *(*find)( + struct cx_tree_s *tree, + const void *subtree, + const void *data + ); + + /** + * Member function for creating an iterator for the tree. + */ + CxTreeIterator (*iterator)( + struct cx_tree_s *tree, + bool visit_on_exit + ); + + /** + * Member function for creating a visitor for the tree. + */ + CxTreeVisitor (*visitor)(struct cx_tree_s *tree); +}; + +/** + * Common type for all tree implementations. + */ +typedef struct cx_tree_s CxTree; + +/** + * Creates a new tree structure based on the specified layout. + * + * The specified \p allocator will be used for creating the tree struct + * and SHALL be used by \p create_func to allocate memory for the nodes. + * + * \note This function will also register an advanced destructor which + * will free the nodes with the allocator's free() method. + * + * @param allocator the allocator that shall be used + * @param create_func a function that creates new nodes + * @param search_func a function that compares two nodes + * @param search_data_func a function that compares a node with data + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_last_child optional offset in the node struct for the pointer to + * the last child in the linked list (negative if there is no such pointer) + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @return the new tree + * @see cxTreeCreateSimple() + * @see cxTreeCreateWrapped() + */ +__attribute__((__nonnull__, __warn_unused_result__)) +CxTree *cxTreeCreate( + const CxAllocator *allocator, + cx_tree_node_create_func create_func, + cx_tree_search_func search_func, + cx_tree_search_data_func search_data_func, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +); + +/** + * Creates a new tree structure based on a default layout. + * + * Nodes created by \p create_func MUST contain #cx_tree_node_base_s as first + * member (or at least respect the default offsets specified in the tree + * struct) and they MUST be allocated with the specified allocator. + * + * \note This function will also register an advanced destructor which + * will free the nodes with the allocator's free() method. + * + * @param allocator the allocator that shall be used + * @param create_func a function that creates new nodes + * @param search_func a function that compares two nodes + * @param search_data_func a function that compares a node with data + * @return the new tree + * @see cxTreeCreate() + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxTree *cxTreeCreateSimple( + const CxAllocator *allocator, + cx_tree_node_create_func create_func, + cx_tree_search_func search_func, + cx_tree_search_data_func search_data_func +) { + return cxTreeCreate( + allocator, + create_func, + search_func, + search_data_func, + cx_tree_node_base_layout + ); +} + +/** + * Creates a new tree structure based on an existing tree. + * + * The specified \p allocator will be used for creating the tree struct. + * + * \attention This function will create an incompletely defined tree structure + * where neither the create function, the search function, nor a destructor + * will be set. If you wish to use any of this functionality for the wrapped + * tree, you need to specify those functions afterwards. + * + * @param root the root node of the tree that shall be wrapped + * @param loc_parent offset in the node struct for the parent pointer + * @param loc_children offset in the node struct for the children linked list + * @param loc_last_child optional offset in the node struct for the pointer to + * the last child in the linked list (negative if there is no such pointer) + * @param loc_prev offset in the node struct for the prev pointer + * @param loc_next offset in the node struct for the next pointer + * @return the new tree + * @see cxTreeCreate() + */ +__attribute__((__nonnull__, __warn_unused_result__)) +CxTree *cxTreeCreateWrapped( + const CxAllocator *allocator, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +); + +/** + * Destroys the tree structure. + * + * \attention This function will only invoke the destructor functions + * on the nodes, if specified. + * It will NOT additionally free the nodes with the tree's allocator, because + * that would cause a double-free in most scenarios. + * + * @param tree the tree to destroy + */ +__attribute__((__nonnull__)) +static inline void cxTreeDestroy(CxTree *tree) { + tree->cl->destructor(tree); +} + +/** + * Inserts data into the tree. + * + * \remark For this function to work, the tree needs specified search and + * create functions, which might not be available for wrapped trees + * (see #cxTreeCreateWrapped()). + * + * @param tree the tree + * @param data the data to insert + * @return zero on success, non-zero on failure + */ +__attribute__((__nonnull__)) +static inline int cxTreeInsert( + CxTree *tree, + const void *data +) { + return tree->cl->insert_element(tree, data); +} + +/** + * Inserts elements provided by an iterator efficiently into the tree. + * + * \remark For this function to work, the tree needs specified search and + * create functions, which might not be available for wrapped trees + * (see #cxTreeCreateWrapped()). + * + * @param tree the tree + * @param iter the iterator providing the elements + * @param n the maximum number of elements to insert + * @return the number of elements that could be successfully inserted + */ +__attribute__((__nonnull__)) +static inline size_t cxTreeInsertIter( + CxTree *tree, + struct cx_iterator_base_s *iter, + size_t n +) { + return tree->cl->insert_many(tree, iter, n); +} + +/** + * Inserts an array of data efficiently into the tree. + * + * \remark For this function to work, the tree needs specified search and + * create functions, which might not be available for wrapped trees + * (see #cxTreeCreateWrapped()). + * + * @param tree the tree + * @param data the array of data to insert + * @param elem_size the size of each element in the array + * @param n the number of elements in the array + * @return the number of elements that could be successfully inserted + */ +__attribute__((__nonnull__)) +static inline size_t cxTreeInsertArray( + CxTree *tree, + const void *data, + size_t elem_size, + size_t n +) { + if (n == 0) return 0; + if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0; + CxIterator iter = cxIterator(data, elem_size, n); + return cxTreeInsertIter(tree, cxIteratorRef(iter), n); +} + +/** + * Searches the data in the specified tree. + * + * \remark For this function to work, the tree needs a specified \c search_data + * function, which might not be available wrapped trees + * (see #cxTreeCreateWrapped()). + * + * @param tree the tree + * @param data the data to search for + * @return the first matching node, or \c NULL when the data cannot be found + */ +__attribute__((__nonnull__)) +static inline void *cxTreeFind( + CxTree *tree, + const void *data +) { + return tree->cl->find(tree, tree->root, data); +} + +/** + * Searches the data in the specified subtree. + * + * \note When \p subtree_root is not part of the \p tree, the behavior is + * undefined. + * + * \remark For this function to work, the tree needs a specified \c search_data + * function, which might not be the case for wrapped trees + * (see #cxTreeCreateWrapped()). + * + * @param tree the tree + * @param data the data to search for + * @param subtree_root the node where to start + * @return the first matching node, or \c NULL when the data cannot be found + */ +__attribute__((__nonnull__)) +static inline void *cxTreeFindInSubtree( + CxTree *tree, + const void *data, + void *subtree_root +) { + return tree->cl->find(tree, subtree_root, data); +} + +/** + * Determines the size of the specified subtree. + * + * @param tree the tree + * @param subtree_root the root node of the subtree + * @return the number of nodes in the specified subtree + */ +__attribute__((__nonnull__)) +size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root); + +/** + * Determines the depth of the specified subtree. + * + * @param tree the tree + * @param subtree_root the root node of the subtree + * @return the tree depth including the \p subtree_root + */ +__attribute__((__nonnull__)) +size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root); + +/** + * Determines the depth of the entire tree. + * + * @param tree the tree + * @return the tree depth, counting the root as one + */ +__attribute__((__nonnull__)) +size_t cxTreeDepth(CxTree *tree); + +/** + * Creates a depth-first iterator for the specified tree. + * + * @param tree the tree to iterate + * @param visit_on_exit true, if the iterator shall visit a node again when + * leaving the sub-tree + * @return a tree iterator (depth-first) + * @see cxTreeVisitor() + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxTreeIterator cxTreeIterator( + CxTree *tree, + bool visit_on_exit +) { + return tree->cl->iterator(tree, visit_on_exit); +} + +/** + * Creates a breadth-first iterator for the specified tree. + * + * @param tree the tree to iterate + * @return a tree visitor (a.k.a. breadth-first iterator) + * @see cxTreeIterator() + */ +__attribute__((__nonnull__, __warn_unused_result__)) +static inline CxTreeVisitor cxTreeVisitor(CxTree *tree) { + return tree->cl->visitor(tree); +} + +/** + * Adds a new node to the tree. + * + * \attention The node may be externally created, but MUST obey the same rules + * as if it was created by the tree itself with #cxTreeAddChild() (e.g. use + * the same allocator). + * + * @param tree the tree + * @param parent the parent of the node to add + * @param child the node to add + */ +__attribute__((__nonnull__)) +static inline void cxTreeAddChildNode( + CxTree *tree, + void *parent, + void *child) { + cx_tree_link(parent, child, cx_tree_node_layout(tree)); + tree->size++; +} + +/** + * Creates a new node and adds it to the tree. + * + * With this function you can decide where exactly the new node shall be added. + * If you specified an appropriate search function, you may want to consider + * leaving this task to the tree by using #cxTreeInsert(). + * + * Be aware that adding nodes at arbitrary locations in the tree might cause + * wrong or undesired results when subsequently invoking #cxTreeInsert() and + * the invariant imposed by the search function does not hold any longer. + * + * @param tree the tree + * @param parent the parent node of the new node + * @param data the data that will be submitted to the create function + * @return zero when the new node was created, non-zero on allocation failure + * @see cxTreeInsert() + */ +__attribute__((__nonnull__)) +int cxTreeAddChild( + CxTree *tree, + void *parent, + const void *data +); + +/** + * A function that is invoked when a node needs to be re-linked to a new parent. + * + * When a node is re-linked, sometimes the contents need to be updated. + * This callback is invoked by #cxTreeRemove() so that those updates can be + * applied when re-linking the children of the removed node. + * + * @param node the affected node + * @param old_parent the old parent of the node + * @param new_parent the new parent of the node + */ +typedef void (*cx_tree_relink_func)( + void *node, + const void *old_parent, + const void *new_parent +); + +/** + * Removes a node and re-links its children to its former parent. + * + * If the node is not part of the tree, the behavior is undefined. + * + * \note The destructor function, if any, will \em not be invoked. That means + * you will need to free the removed node by yourself, eventually. + * + * @param tree the tree + * @param node the node to remove (must not be the root node) + * @param relink_func optional callback to update the content of each re-linked + * node + * @return zero on success, non-zero if \p node is the root node of the tree + */ +__attribute__((__nonnull__(1,2))) +int cxTreeRemove( + CxTree *tree, + void *node, + cx_tree_relink_func relink_func +); + +/** + * Removes a node and it's subtree from the tree. + * + * If the node is not part of the tree, the behavior is undefined. + * + * \note The destructor function, if any, will \em not be invoked. That means + * you will need to free the removed subtree by yourself, eventually. + * + * @param tree the tree + * @param node the node to remove + */ +__attribute__((__nonnull__)) +void cxTreeRemoveSubtree(CxTree *tree, void *node); + #ifdef __cplusplus } // extern "C" #endif
--- a/ucx/hash_key.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/hash_key.c Sun Oct 06 12:00:31 2024 +0200 @@ -30,7 +30,7 @@ #include <string.h> void cx_hash_murmur(CxHashKey *key) { - unsigned char const *data = key->data; + const unsigned char *data = key->data; if (data == NULL) { // extension: special value for NULL key->hash = 1574210520u; @@ -81,7 +81,7 @@ key->hash = h; } -CxHashKey cx_hash_key_str(char const *str) { +CxHashKey cx_hash_key_str(const char *str) { CxHashKey key; key.data = str; key.len = str == NULL ? 0 : strlen(str); @@ -90,7 +90,7 @@ } CxHashKey cx_hash_key_bytes( - unsigned char const *bytes, + const unsigned char *bytes, size_t len ) { CxHashKey key; @@ -101,7 +101,7 @@ } CxHashKey cx_hash_key( - void const *obj, + const void *obj, size_t len ) { CxHashKey key;
--- a/ucx/hash_map.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/hash_map.c Sun Oct 06 12:00:31 2024 +0200 @@ -53,9 +53,9 @@ // invoke the destructor cx_invoke_destructor(map, elem->data); // free the key data - cxFree(map->allocator, (void *) elem->key.data); + cxFree(map->collection.allocator, (void *) elem->key.data); // free the node - cxFree(map->allocator, elem); + cxFree(map->collection.allocator, elem); // proceed elem = next; } while (elem != NULL); @@ -64,7 +64,7 @@ hash_map->buckets[i] = NULL; } } - map->size = 0; + map->collection.size = 0; } static void cx_hash_map_destructor(struct cx_map_s *map) { @@ -72,10 +72,10 @@ // free the buckets cx_hash_map_clear(map); - cxFree(map->allocator, hash_map->buckets); + cxFree(map->collection.allocator, hash_map->buckets); // free the map structure - cxFree(map->allocator, map); + cxFree(map->collection.allocator, map); } static int cx_hash_map_put( @@ -84,7 +84,7 @@ void *value ) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; - CxAllocator const *allocator = map->allocator; + const CxAllocator *allocator = map->collection.allocator; unsigned hash = key.hash; if (hash == 0) { @@ -104,26 +104,26 @@ if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && memcmp(elm->key.data, key.data, key.len) == 0) { // overwrite existing element - if (map->store_pointer) { + if (map->collection.store_pointer) { memcpy(elm->data, &value, sizeof(void *)); } else { - memcpy(elm->data, value, map->item_size); + memcpy(elm->data, value, map->collection.elem_size); } } else { // allocate new element struct cx_hash_map_element_s *e = cxMalloc( allocator, - sizeof(struct cx_hash_map_element_s) + map->item_size + sizeof(struct cx_hash_map_element_s) + map->collection.elem_size ); if (e == NULL) { return -1; } // write the value - if (map->store_pointer) { + if (map->collection.store_pointer) { memcpy(e->data, &value, sizeof(void *)); } else { - memcpy(e->data, value, map->item_size); + memcpy(e->data, value, map->collection.elem_size); } // copy the key @@ -145,7 +145,7 @@ e->next = elm; // increase the size - map->size++; + map->collection.size++; } return 0; @@ -164,10 +164,10 @@ prev->next = elm->next; } // free element - cxFree(hash_map->base.allocator, (void *) elm->key.data); - cxFree(hash_map->base.allocator, elm); + cxFree(hash_map->base.collection.allocator, (void *) elm->key.data); + cxFree(hash_map->base.collection.allocator, elm); // decrease size - hash_map->base.size--; + hash_map->base.collection.size--; } /** @@ -203,7 +203,7 @@ if (destroy) { cx_invoke_destructor(map, elm->data); } else { - if (map->store_pointer) { + if (map->collection.store_pointer) { data = *(void **) elm->data; } else { data = elm->data; @@ -223,7 +223,7 @@ } static void *cx_hash_map_get( - CxMap const *map, + const CxMap *map, CxHashKey key ) { // we can safely cast, because we know the map stays untouched @@ -238,43 +238,41 @@ return cx_hash_map_get_remove(map, key, true, destroy); } -static void *cx_hash_map_iter_current_entry(void const *it) { - struct cx_iterator_s const *iter = it; +static void *cx_hash_map_iter_current_entry(const void *it) { + const struct cx_iterator_s *iter = it; // struct has to have a compatible signature return (struct cx_map_entry_s *) &(iter->kv_data); } -static void *cx_hash_map_iter_current_key(void const *it) { - struct cx_iterator_s const *iter = it; +static void *cx_hash_map_iter_current_key(const void *it) { + const struct cx_iterator_s *iter = it; struct cx_hash_map_element_s *elm = iter->elem_handle; return &elm->key; } -static void *cx_hash_map_iter_current_value(void const *it) { - struct cx_iterator_s const *iter = it; - struct cx_hash_map_s const *map = iter->src_handle; +static void *cx_hash_map_iter_current_value(const void *it) { + const struct cx_iterator_s *iter = it; + const struct cx_hash_map_s *map = iter->src_handle.c; struct cx_hash_map_element_s *elm = iter->elem_handle; - if (map->base.store_pointer) { + if (map->base.collection.store_pointer) { return *(void **) elm->data; } else { return elm->data; } } -static bool cx_hash_map_iter_valid(void const *it) { - struct cx_iterator_s const *iter = it; +static bool cx_hash_map_iter_valid(const void *it) { + const struct cx_iterator_s *iter = it; return iter->elem_handle != NULL; } static void cx_hash_map_iter_next(void *it) { struct cx_iterator_s *iter = it; struct cx_hash_map_element_s *elm = iter->elem_handle; + struct cx_hash_map_s *map = iter->src_handle.m; // remove current element, if asked if (iter->base.remove) { - // obtain mutable pointer to the map - struct cx_mut_iterator_s *miter = it; - struct cx_hash_map_s *map = miter->src_handle; // clear the flag iter->base.remove = false; @@ -306,7 +304,6 @@ } // search the next bucket, if required - struct cx_hash_map_s const *map = iter->src_handle; while (elm == NULL && ++iter->slot < map->bucket_count) { elm = map->buckets[iter->slot]; } @@ -318,7 +315,7 @@ iter->kv_data.value = NULL; } else { iter->kv_data.key = &elm->key; - if (map->base.store_pointer) { + if (map->base.collection.store_pointer) { iter->kv_data.value = *(void **) elm->data; } else { iter->kv_data.value = elm->data; @@ -326,48 +323,41 @@ } } -static bool cx_hash_map_iter_flag_rm(void *it) { - struct cx_iterator_base_s *iter = it; - if (iter->mutating) { - iter->remove = true; - return true; - } else { - return false; - } -} - static CxIterator cx_hash_map_iterator( - CxMap const *map, + const CxMap *map, enum cx_map_iterator_type type ) { CxIterator iter; - iter.src_handle = map; - iter.base.valid = cx_hash_map_iter_valid; - iter.base.next = cx_hash_map_iter_next; + iter.src_handle.c = map; + iter.elem_count = map->collection.size; switch (type) { case CX_MAP_ITERATOR_PAIRS: + iter.elem_size = sizeof(CxMapEntry); iter.base.current = cx_hash_map_iter_current_entry; break; case CX_MAP_ITERATOR_KEYS: + iter.elem_size = sizeof(CxHashKey); iter.base.current = cx_hash_map_iter_current_key; break; case CX_MAP_ITERATOR_VALUES: + iter.elem_size = map->collection.elem_size; iter.base.current = cx_hash_map_iter_current_value; break; default: assert(false); } - iter.base.flag_removal = cx_hash_map_iter_flag_rm; + iter.base.valid = cx_hash_map_iter_valid; + iter.base.next = cx_hash_map_iter_next; iter.base.remove = false; iter.base.mutating = false; iter.slot = 0; iter.index = 0; - if (map->size > 0) { + if (map->collection.size > 0) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; struct cx_hash_map_element_s *elm = hash_map->buckets[0]; while (elm == NULL) { @@ -375,7 +365,7 @@ } iter.elem_handle = elm; iter.kv_data.key = &elm->key; - if (map->store_pointer) { + if (map->collection.store_pointer) { iter.kv_data.value = *(void **) elm->data; } else { iter.kv_data.value = elm->data; @@ -399,7 +389,7 @@ }; CxMap *cxHashMapCreate( - CxAllocator const *allocator, + const CxAllocator *allocator, size_t itemsize, size_t buckets ) { @@ -423,14 +413,14 @@ // initialize base members map->base.cl = &cx_hash_map_class; - map->base.allocator = allocator; + map->base.collection.allocator = allocator; if (itemsize > 0) { - map->base.store_pointer = false; - map->base.item_size = itemsize; + map->base.collection.store_pointer = false; + map->base.collection.elem_size = itemsize; } else { - map->base.store_pointer = true; - map->base.item_size = sizeof(void *); + map->base.collection.store_pointer = true; + map->base.collection.elem_size = sizeof(void *); } return (CxMap *) map; @@ -438,11 +428,11 @@ int cxMapRehash(CxMap *map) { struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; - if (map->size > ((hash_map->bucket_count * 3) >> 2)) { + if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) { - size_t new_bucket_count = (map->size * 5) >> 1; + size_t new_bucket_count = (map->collection.size * 5) >> 1; struct cx_hash_map_element_s **new_buckets = cxCalloc( - map->allocator, + map->collection.allocator, new_bucket_count, sizeof(struct cx_hash_map_element_s *) ); @@ -482,7 +472,7 @@ // assign result to the map hash_map->bucket_count = new_bucket_count; - cxFree(map->allocator, hash_map->buckets); + cxFree(map->collection.allocator, hash_map->buckets); hash_map->buckets = new_buckets; } return 0;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/ucx/iterator.c Sun Oct 06 12:00:31 2024 +0200 @@ -0,0 +1,112 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2024 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/iterator.h" + +#include <string.h> + +static bool cx_iter_valid(const void *it) { + const struct cx_iterator_s *iter = it; + return iter->index < iter->elem_count; +} + +static void *cx_iter_current(const void *it) { + const struct cx_iterator_s *iter = it; + return iter->elem_handle; +} + +static void cx_iter_next_fast(void *it) { + struct cx_iterator_s *iter = it; + if (iter->base.remove) { + iter->base.remove = false; + iter->elem_count--; + // only move the last element when we are not currently aiming + // at the last element already + if (iter->index < iter->elem_count) { + void *last = ((char *) iter->src_handle.m) + + iter->elem_count * iter->elem_size; + memcpy(iter->elem_handle, last, iter->elem_size); + } + } else { + iter->index++; + iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size; + } +} + +static void cx_iter_next_slow(void *it) { + struct cx_iterator_s *iter = it; + if (iter->base.remove) { + iter->base.remove = false; + iter->elem_count--; + + // number of elements to move + size_t remaining = iter->elem_count - iter->index; + if (remaining > 0) { + memmove( + iter->elem_handle, + ((char *) iter->elem_handle) + iter->elem_size, + remaining * iter->elem_size + ); + } + } else { + iter->index++; + iter->elem_handle = ((char *) iter->elem_handle) + iter->elem_size; + } +} + +CxIterator cxMutIterator( + void *array, + size_t elem_size, + size_t elem_count, + bool remove_keeps_order +) { + CxIterator iter; + + iter.index = 0; + iter.src_handle.m = array; + iter.elem_handle = array; + iter.elem_size = elem_size; + iter.elem_count = array == NULL ? 0 : elem_count; + iter.base.valid = cx_iter_valid; + iter.base.current = cx_iter_current; + iter.base.next = remove_keeps_order ? cx_iter_next_slow : cx_iter_next_fast; + iter.base.remove = false; + iter.base.mutating = true; + + return iter; +} + +CxIterator cxIterator( + const void *array, + size_t elem_size, + size_t elem_count +) { + CxIterator iter = cxMutIterator((void*)array, elem_size, elem_count, false); + iter.base.mutating = false; + return iter; +}
--- a/ucx/linked_list.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/linked_list.c Sun Oct 06 12:00:31 2024 +0200 @@ -41,7 +41,7 @@ #define ll_data(node) (((char*)(node))+loc_data) void *cx_linked_list_at( - void const *start, + const void *start, size_t start_index, ptrdiff_t loc_advance, size_t index @@ -49,7 +49,7 @@ assert(start != NULL); assert(loc_advance >= 0); size_t i = start_index; - void const *cur = start; + const void *cur = start; while (i != index && cur != NULL) { cur = ll_advance(cur); i < index ? i++ : i--; @@ -58,11 +58,11 @@ } ssize_t cx_linked_list_find( - void const *start, + const void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func, - void const *elem + const void *elem ) { void *dummy; return cx_linked_list_find_node( @@ -74,11 +74,11 @@ ssize_t cx_linked_list_find_node( void **result, - void const *start, + const void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func, - void const *elem + const void *elem ) { assert(result != NULL); assert(start != NULL); @@ -86,7 +86,7 @@ assert(loc_data >= 0); assert(cmp_func); - void const *node = start; + const void *node = start; ssize_t index = 0; do { void *current = ll_data(node); @@ -102,21 +102,21 @@ } void *cx_linked_list_first( - void const *node, + const void *node, ptrdiff_t loc_prev ) { return cx_linked_list_last(node, loc_prev); } void *cx_linked_list_last( - void const *node, + const void *node, ptrdiff_t loc_next ) { assert(node != NULL); assert(loc_next >= 0); - void const *cur = node; - void const *last; + const void *cur = node; + const void *last; do { last = cur; } while ((cur = ll_next(cur)) != NULL); @@ -125,16 +125,16 @@ } void *cx_linked_list_prev( - void const *begin, + const void *begin, ptrdiff_t loc_next, - void const *node + const void *node ) { assert(begin != NULL); assert(node != NULL); assert(loc_next >= 0); if (begin == node) return NULL; - void const *cur = begin; - void const *next; + const void *cur = begin; + const void *next; while (1) { next = ll_next(cur); if (next == node) return (void *) cur; @@ -247,6 +247,95 @@ } } +void cx_linked_list_insert_sorted( + void **begin, + void **end, + ptrdiff_t loc_prev, + ptrdiff_t loc_next, + void *new_node, + cx_compare_func cmp_func +) { + assert(ll_next(new_node) == NULL); + cx_linked_list_insert_sorted_chain( + begin, end, loc_prev, loc_next, new_node, cmp_func); +} + +void cx_linked_list_insert_sorted_chain( + void **begin, + void **end, + ptrdiff_t loc_prev, + ptrdiff_t loc_next, + void *insert_begin, + cx_compare_func cmp_func +) { + assert(begin != NULL); + assert(loc_next >= 0); + assert(insert_begin != NULL); + + // track currently observed nodes + void *dest_prev = NULL; + void *dest = *begin; + void *src = insert_begin; + + // special case: list is empty + if (dest == NULL) { + *begin = src; + if (end != NULL) { + *end = cx_linked_list_last(src, loc_next); + } + return; + } + + // search the list for insertion points + while (dest != NULL && src != NULL) { + // compare current list node with source node + // if less or equal, skip + if (cmp_func(dest, src) <= 0) { + dest_prev = dest; + dest = ll_next(dest); + continue; + } + + // determine chain of elements that can be inserted + void *end_of_chain = src; + void *next_in_chain = ll_next(src); + while (next_in_chain != NULL) { + // once we become larger than the list elem, break + if (cmp_func(dest, next_in_chain) <= 0) { + break; + } + // otherwise, we can insert one more + end_of_chain = next_in_chain; + next_in_chain = ll_next(next_in_chain); + } + + // insert the elements + if (dest_prev == NULL) { + // new begin + *begin = src; + } else { + cx_linked_list_link(dest_prev, src, loc_prev, loc_next); + } + cx_linked_list_link(end_of_chain, dest, loc_prev, loc_next); + + // continue with next + src = next_in_chain; + dest_prev = dest; + dest = ll_next(dest); + } + + // insert remaining items + if (src != NULL) { + cx_linked_list_link(dest_prev, src, loc_prev, loc_next); + } + + // determine new end of list, if requested + if (end != NULL) { + *end = cx_linked_list_last( + dest != NULL ? dest : dest_prev, loc_next); + } +} + void cx_linked_list_remove( void **begin, void **end, @@ -287,7 +376,7 @@ } size_t cx_linked_list_size( - void const *node, + const void *node, ptrdiff_t loc_next ) { assert(loc_next >= 0); @@ -425,17 +514,17 @@ } int cx_linked_list_compare( - void const *begin_left, - void const *begin_right, + const void *begin_left, + const void *begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func ) { - void const *left = begin_left, *right = begin_right; + const void *left = begin_left, *right = begin_right; while (left != NULL && right != NULL) { - void const *left_data = ll_data(left); - void const *right_data = ll_data(right); + const void *left_data = ll_data(left); + const void *right_data = ll_data(right); int result = cmp_func(left_data, right_data); if (result != 0) return result; left = ll_advance(left); @@ -498,34 +587,38 @@ } cx_linked_list; static cx_linked_list_node *cx_ll_node_at( - cx_linked_list const *list, + const cx_linked_list *list, size_t index ) { - if (index >= list->base.size) { + if (index >= list->base.collection.size) { return NULL; - } else if (index > list->base.size / 2) { - return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); + } else if (index > list->base.collection.size / 2) { + return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index); } else { return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); } } +static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) { + return cxMalloc(list->collection.allocator, + sizeof(cx_linked_list_node) + list->collection.elem_size); +} + static int cx_ll_insert_at( struct cx_list_s *list, cx_linked_list_node *node, - void const *elem + const void *elem ) { // create the new new_node - cx_linked_list_node *new_node = cxMalloc(list->allocator, - sizeof(cx_linked_list_node) + list->item_size); + cx_linked_list_node *new_node = cx_ll_malloc_node(list); // sortir if failed if (new_node == NULL) return 1; // initialize new new_node new_node->prev = new_node->next = NULL; - memcpy(new_node->payload, elem, list->item_size); + memcpy(new_node->payload, elem, list->collection.elem_size); // insert cx_linked_list *ll = (cx_linked_list *) list; @@ -536,18 +629,18 @@ ); // increase the size and return - list->size++; + list->collection.size++; return 0; } static size_t cx_ll_insert_array( struct cx_list_s *list, size_t index, - void const *array, + const void *array, size_t n ) { // out-of bounds and corner case check - if (index > list->size || n == 0) return 0; + if (index > list->collection.size || n == 0) return 0; // find position efficiently cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); @@ -563,10 +656,10 @@ // we now know exactly where we are node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; - // we can add the remaining nodes and immedately advance to the inserted node - char const *source = array; + // we can add the remaining nodes and immediately advance to the inserted node + const char *source = array; for (size_t i = 1; i < n; i++) { - source += list->item_size; + source += list->collection.elem_size; if (0 != cx_ll_insert_at(list, node, source)) { return i; } @@ -578,11 +671,68 @@ static int cx_ll_insert_element( struct cx_list_s *list, size_t index, - void const *element + const void *element ) { return 1 != cx_ll_insert_array(list, index, element, 1); } +static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; + +static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { + const cx_linked_list_node *left = l; + const cx_linked_list_node *right = r; + return cx_ll_insert_sorted_cmp_func(left->payload, right->payload); +} + +static size_t cx_ll_insert_sorted( + struct cx_list_s *list, + const void *array, + size_t n +) { + // special case + if (n == 0) return 0; + + // create a new chain of nodes + cx_linked_list_node *chain = cx_ll_malloc_node(list); + if (chain == NULL) return 0; + + memcpy(chain->payload, array, list->collection.elem_size); + chain->prev = NULL; + chain->next = NULL; + + // add all elements from the array to that chain + cx_linked_list_node *prev = chain; + const char *src = array; + size_t inserted = 1; + for (; inserted < n; inserted++) { + cx_linked_list_node *next = cx_ll_malloc_node(list); + if (next == NULL) break; + src += list->collection.elem_size; + memcpy(next->payload, src, list->collection.elem_size); + prev->next = next; + next->prev = prev; + prev = next; + } + prev->next = NULL; + + // invoke the low level function + cx_linked_list *ll = (cx_linked_list *) list; + cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; + cx_linked_list_insert_sorted_chain( + (void **) &ll->begin, + (void **) &ll->end, + CX_LL_LOC_PREV, + CX_LL_LOC_NEXT, + chain, + cx_ll_insert_sorted_cmp_helper + ); + + // adjust the list metadata + list->collection.size += inserted; + + return inserted; +} + static int cx_ll_remove( struct cx_list_s *list, size_t index @@ -601,27 +751,27 @@ CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); // adjust size - list->size--; + list->collection.size--; // free and return - cxFree(list->allocator, node); + cxFree(list->collection.allocator, node); return 0; } static void cx_ll_clear(struct cx_list_s *list) { - if (list->size == 0) return; + if (list->collection.size == 0) return; cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_node *node = ll->begin; while (node != NULL) { cx_invoke_destructor(list, node->payload); cx_linked_list_node *next = node->next; - cxFree(list->allocator, node); + cxFree(list->collection.allocator, node); node = next; } ll->begin = ll->end = NULL; - list->size = 0; + list->collection.size = 0; } #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE @@ -634,12 +784,12 @@ size_t i, size_t j ) { - if (i >= list->size || j >= list->size) return 1; + if (i >= list->collection.size || j >= list->collection.size) return 1; if (i == j) return 0; // perform an optimized search that finds both elements in one run cx_linked_list *ll = (cx_linked_list *) list; - size_t mid = list->size / 2; + size_t mid = list->collection.size / 2; size_t left, right; if (i < j) { left = i; @@ -671,7 +821,7 @@ // chose the closest to begin / end size_t closest; size_t other; - size_t diff2boundary = list->size - right - 1; + size_t diff2boundary = list->collection.size - right - 1; if (left <= diff2boundary) { closest = left; other = right; @@ -707,7 +857,7 @@ } } - if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE) { + if (list->collection.elem_size > CX_LINKED_LIST_SWAP_SBO_SIZE) { cx_linked_list_node *prev = nleft->prev; cx_linked_list_node *next = nright->next; cx_linked_list_node *midstart = nleft->next; @@ -739,16 +889,16 @@ } else { // swap payloads to avoid relinking char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; - memcpy(buf, nleft->payload, list->item_size); - memcpy(nleft->payload, nright->payload, list->item_size); - memcpy(nright->payload, buf, list->item_size); + memcpy(buf, nleft->payload, list->collection.elem_size); + memcpy(nleft->payload, nright->payload, list->collection.elem_size); + memcpy(nright->payload, buf, list->collection.elem_size); } return 0; } static void *cx_ll_at( - struct cx_list_s const *list, + const struct cx_list_s *list, size_t index ) { cx_linked_list *ll = (cx_linked_list *) list; @@ -758,7 +908,7 @@ static ssize_t cx_ll_find_remove( struct cx_list_s *list, - void const *elem, + const void *elem, bool remove ) { if (remove) { @@ -768,21 +918,21 @@ (void **) &node, ll->begin, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - list->cmpfunc, elem + list->collection.cmpfunc, elem ); if (node != NULL) { cx_invoke_destructor(list, node->payload); cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); - list->size--; - cxFree(list->allocator, node); + list->collection.size--; + cxFree(list->collection.allocator, node); } return index; } else { return cx_linked_list_find( ((cx_linked_list *) list)->begin, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - list->cmpfunc, elem + list->collection.cmpfunc, elem ); } } @@ -791,7 +941,7 @@ cx_linked_list *ll = (cx_linked_list *) list; cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - list->cmpfunc); + list->collection.cmpfunc); } static void cx_ll_reverse(struct cx_list_s *list) { @@ -800,37 +950,35 @@ } static int cx_ll_compare( - struct cx_list_s const *list, - struct cx_list_s const *other + const struct cx_list_s *list, + const struct cx_list_s *other ) { cx_linked_list *left = (cx_linked_list *) list; cx_linked_list *right = (cx_linked_list *) other; return cx_linked_list_compare(left->begin, right->begin, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, - list->cmpfunc); + list->collection.cmpfunc); } -static bool cx_ll_iter_valid(void const *it) { - struct cx_iterator_s const *iter = it; +static bool cx_ll_iter_valid(const void *it) { + const struct cx_iterator_s *iter = it; return iter->elem_handle != NULL; } static void cx_ll_iter_next(void *it) { - struct cx_iterator_base_s *itbase = it; - if (itbase->remove) { - itbase->remove = false; - struct cx_mut_iterator_s *iter = it; - struct cx_list_s *list = iter->src_handle; - cx_linked_list *ll = iter->src_handle; + struct cx_iterator_s *iter = it; + if (iter->base.remove) { + iter->base.remove = false; + struct cx_list_s *list = iter->src_handle.m; + cx_linked_list *ll = iter->src_handle.m; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->next; cx_invoke_destructor(list, node->payload); cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); - list->size--; - cxFree(list->allocator, node); + list->collection.size--; + cxFree(list->collection.allocator, node); } else { - struct cx_iterator_s *iter = it; iter->index++; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->next; @@ -838,78 +986,75 @@ } static void cx_ll_iter_prev(void *it) { - struct cx_iterator_base_s *itbase = it; - if (itbase->remove) { - itbase->remove = false; - struct cx_mut_iterator_s *iter = it; - struct cx_list_s *list = iter->src_handle; - cx_linked_list *ll = iter->src_handle; + struct cx_iterator_s *iter = it; + if (iter->base.remove) { + iter->base.remove = false; + struct cx_list_s *list = iter->src_handle.m; + cx_linked_list *ll = iter->src_handle.m; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->prev; iter->index--; cx_invoke_destructor(list, node->payload); cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); - list->size--; - cxFree(list->allocator, node); + list->collection.size--; + cxFree(list->collection.allocator, node); } else { - struct cx_iterator_s *iter = it; iter->index--; cx_linked_list_node *node = iter->elem_handle; iter->elem_handle = node->prev; } } -static void *cx_ll_iter_current(void const *it) { - struct cx_iterator_s const *iter = it; +static void *cx_ll_iter_current(const void *it) { + const struct cx_iterator_s *iter = it; cx_linked_list_node *node = iter->elem_handle; return node->payload; } -static bool cx_ll_iter_flag_rm(void *it) { - struct cx_iterator_base_s *iter = it; - if (iter->mutating) { - iter->remove = true; - return true; - } else { - return false; - } -} - static CxIterator cx_ll_iterator( - struct cx_list_s const *list, + const struct cx_list_s *list, size_t index, bool backwards ) { CxIterator iter; iter.index = index; - iter.src_handle = list; - iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); + iter.src_handle.c = list; + iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index); + iter.elem_size = list->collection.elem_size; + iter.elem_count = list->collection.size; iter.base.valid = cx_ll_iter_valid; iter.base.current = cx_ll_iter_current; iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; - iter.base.flag_removal = cx_ll_iter_flag_rm; iter.base.mutating = false; iter.base.remove = false; return iter; } static int cx_ll_insert_iter( - CxMutIterator *iter, - void const *elem, + CxIterator *iter, + const void *elem, int prepend ) { - struct cx_list_s *list = iter->src_handle; + struct cx_list_s *list = iter->src_handle.m; cx_linked_list_node *node = iter->elem_handle; if (node != NULL) { assert(prepend >= 0 && prepend <= 1); cx_linked_list_node *choice[2] = {node, node->prev}; int result = cx_ll_insert_at(list, choice[prepend], elem); - iter->index += prepend * (0 == result); + if (result == 0) { + iter->elem_count++; + if (prepend) { + iter->index++; + } + } return result; } else { - int result = cx_ll_insert_element(list, list->size, elem); - iter->index = list->size; + int result = cx_ll_insert_element(list, list->collection.size, elem); + if (result == 0) { + iter->elem_count++; + iter->index = list->collection.size; + } return result; } } @@ -921,17 +1066,18 @@ while (node) { cx_invoke_destructor(list, node->payload); void *next = node->next; - cxFree(list->allocator, node); + cxFree(list->collection.allocator, node); node = next; } - cxFree(list->allocator, list); + cxFree(list->collection.allocator, list); } static cx_list_class cx_linked_list_class = { cx_ll_destructor, cx_ll_insert_element, cx_ll_insert_array, + cx_ll_insert_sorted, cx_ll_insert_iter, cx_ll_remove, cx_ll_clear, @@ -945,9 +1091,9 @@ }; CxList *cxLinkedListCreate( - CxAllocator const *allocator, + const CxAllocator *allocator, cx_compare_func comparator, - size_t item_size + size_t elem_size ) { if (allocator == NULL) { allocator = cxDefaultAllocator; @@ -957,13 +1103,13 @@ if (list == NULL) return NULL; list->base.cl = &cx_linked_list_class; - list->base.allocator = allocator; + list->base.collection.allocator = allocator; - if (item_size > 0) { - list->base.item_size = item_size; - list->base.cmpfunc = comparator; + if (elem_size > 0) { + list->base.collection.elem_size = elem_size; + list->base.collection.cmpfunc = comparator; } else { - list->base.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; + list->base.collection.cmpfunc = comparator == NULL ? cx_cmp_ptr : comparator; cxListStorePointers((CxList *) list); }
--- a/ucx/list.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/list.c Sun Oct 06 12:00:31 2024 +0200 @@ -35,26 +35,26 @@ static _Thread_local cx_compare_func cx_pl_cmpfunc_impl; static int cx_pl_cmpfunc( - void const *l, - void const *r + const void *l, + const void *r ) { void *const *lptr = l; void *const *rptr = r; - void const *left = lptr == NULL ? NULL : *lptr; - void const *right = rptr == NULL ? NULL : *rptr; + const void *left = lptr == NULL ? NULL : *lptr; + const void *right = rptr == NULL ? NULL : *rptr; return cx_pl_cmpfunc_impl(left, right); } -static void cx_pl_hack_cmpfunc(struct cx_list_s const *list) { +static void cx_pl_hack_cmpfunc(const struct cx_list_s *list) { // cast away const - this is the hacky thing - struct cx_list_s *l = (struct cx_list_s *) list; + struct cx_collection_s *l = (struct cx_collection_s*) &list->collection; cx_pl_cmpfunc_impl = l->cmpfunc; l->cmpfunc = cx_pl_cmpfunc; } -static void cx_pl_unhack_cmpfunc(struct cx_list_s const *list) { +static void cx_pl_unhack_cmpfunc(const struct cx_list_s *list) { // cast away const - this is the hacky thing - struct cx_list_s *l = (struct cx_list_s *) list; + struct cx_collection_s *l = (struct cx_collection_s*) &list->collection; l->cmpfunc = cx_pl_cmpfunc_impl; } @@ -65,7 +65,7 @@ static int cx_pl_insert_element( struct cx_list_s *list, size_t index, - void const *element + const void *element ) { return list->climpl->insert_element(list, index, &element); } @@ -73,18 +73,29 @@ static size_t cx_pl_insert_array( struct cx_list_s *list, size_t index, - void const *array, + const void *array, size_t n ) { return list->climpl->insert_array(list, index, array, n); } +static size_t cx_pl_insert_sorted( + struct cx_list_s *list, + const void *array, + size_t n +) { + cx_pl_hack_cmpfunc(list); + size_t result = list->climpl->insert_sorted(list, array, n); + cx_pl_unhack_cmpfunc(list); + return result; +} + static int cx_pl_insert_iter( - struct cx_mut_iterator_s *iter, - void const *elem, + struct cx_iterator_s *iter, + const void *elem, int prepend ) { - struct cx_list_s *list = iter->src_handle; + struct cx_list_s *list = iter->src_handle.m; return list->climpl->insert_iter(iter, &elem, prepend); } @@ -108,7 +119,7 @@ } static void *cx_pl_at( - struct cx_list_s const *list, + const struct cx_list_s *list, size_t index ) { void **ptr = list->climpl->at(list, index); @@ -117,7 +128,7 @@ static ssize_t cx_pl_find_remove( struct cx_list_s *list, - void const *elem, + const void *elem, bool remove ) { cx_pl_hack_cmpfunc(list); @@ -133,8 +144,8 @@ } static int cx_pl_compare( - struct cx_list_s const *list, - struct cx_list_s const *other + const struct cx_list_s *list, + const struct cx_list_s *other ) { cx_pl_hack_cmpfunc(list); int ret = list->climpl->compare(list, other); @@ -146,14 +157,14 @@ list->climpl->reverse(list); } -static void *cx_pl_iter_current(void const *it) { - struct cx_iterator_s const *iter = it; +static void *cx_pl_iter_current(const void *it) { + const struct cx_iterator_s *iter = it; void **ptr = iter->base.current_impl(it); return ptr == NULL ? NULL : *ptr; } static struct cx_iterator_s cx_pl_iterator( - struct cx_list_s const *list, + const struct cx_list_s *list, size_t index, bool backwards ) { @@ -167,6 +178,7 @@ cx_pl_destructor, cx_pl_insert_element, cx_pl_insert_array, + cx_pl_insert_sorted, cx_pl_insert_iter, cx_pl_remove, cx_pl_clear, @@ -180,7 +192,7 @@ }; void cxListStoreObjects(CxList *list) { - list->store_pointer = false; + list->collection.store_pointer = false; if (list->climpl != NULL) { list->cl = list->climpl; list->climpl = NULL; @@ -188,8 +200,8 @@ } void cxListStorePointers(CxList *list) { - list->item_size = sizeof(void *); - list->store_pointer = true; + list->collection.elem_size = sizeof(void *); + list->collection.store_pointer = true; list->climpl = list->cl; list->cl = &cx_pointer_list_class; } @@ -203,7 +215,7 @@ } static void *cx_emptyl_at( - __attribute__((__unused__)) struct cx_list_s const *list, + __attribute__((__unused__)) const struct cx_list_s *list, __attribute__((__unused__)) size_t index ) { return NULL; @@ -211,31 +223,23 @@ static ssize_t cx_emptyl_find_remove( __attribute__((__unused__)) struct cx_list_s *list, - __attribute__((__unused__)) void const *elem, + __attribute__((__unused__)) const void *elem, __attribute__((__unused__)) bool remove ) { return -1; } -static int cx_emptyl_compare( - __attribute__((__unused__)) struct cx_list_s const *list, - struct cx_list_s const *other -) { - if (other->size == 0) return 0; - return -1; -} - -static bool cx_emptyl_iter_valid(__attribute__((__unused__)) void const *iter) { +static bool cx_emptyl_iter_valid(__attribute__((__unused__)) const void *iter) { return false; } static CxIterator cx_emptyl_iterator( - struct cx_list_s const *list, + const struct cx_list_s *list, size_t index, __attribute__((__unused__)) bool backwards ) { CxIterator iter = {0}; - iter.src_handle = list; + iter.src_handle.c = list; iter.index = index; iter.base.valid = cx_emptyl_iter_valid; return iter; @@ -247,25 +251,28 @@ NULL, NULL, NULL, + NULL, cx_emptyl_noop, NULL, cx_emptyl_at, cx_emptyl_find_remove, cx_emptyl_noop, - cx_emptyl_compare, + NULL, cx_emptyl_noop, cx_emptyl_iterator, }; CxList cx_empty_list = { - NULL, - NULL, - 0, - 0, - NULL, - NULL, - NULL, - false, + { + NULL, + NULL, + 0, + 0, + NULL, + NULL, + NULL, + false + }, &cx_empty_list_class, NULL }; @@ -274,33 +281,177 @@ // </editor-fold> +#define invoke_list_func(name, list, ...) \ + ((list)->climpl == NULL ? (list)->cl->name : (list)->climpl->name) \ + (list, __VA_ARGS__) + +size_t cx_list_default_insert_array( + struct cx_list_s *list, + size_t index, + const void *data, + size_t n +) { + size_t elem_size = list->collection.elem_size; + const char *src = data; + size_t i = 0; + for (; i < n; i++) { + if (0 != invoke_list_func(insert_element, + list, index + i, src + (i * elem_size))) { + return i; + } + } + return i; +} + +size_t cx_list_default_insert_sorted( + struct cx_list_s *list, + const void *sorted_data, + size_t n +) { + // corner case + if (n == 0) return 0; + + size_t elem_size = list->collection.elem_size; + cx_compare_func cmp = list->collection.cmpfunc; + const char *src = sorted_data; + + // track indices and number of inserted items + size_t di = 0, si = 0, inserted = 0; + + // search the list for insertion points + for (; di < list->collection.size; di++) { + const void *list_elm = invoke_list_func(at, list, di); + + // compare current list element with first source element + // if less or equal, skip + if (cmp(list_elm, src) <= 0) { + continue; + } + + // determine number of consecutive elements that can be inserted + size_t ins = 1; + const char *next = src; + while (++si < n) { + next += elem_size; + // once we become larger than the list elem, break + if (cmp(list_elm, next) <= 0) { + break; + } + // otherwise, we can insert one more + ins++; + } + + // insert the elements at location si + if (ins == 1) { + if (0 != invoke_list_func(insert_element, + list, di, src)) + return inserted; + } else { + size_t r = invoke_list_func(insert_array, list, di, src, ins); + if (r < ins) return inserted + r; + } + inserted += ins; + di += ins; + + // everything inserted? + if (inserted == n) return inserted; + src = next; + } + + // insert remaining items + if (si < n) { + inserted += invoke_list_func(insert_array, list, di, src, n - si); + } + + return inserted; +} + +void cx_list_default_sort(struct cx_list_s *list) { + size_t elem_size = list->collection.elem_size; + size_t list_size = list->collection.size; + void *tmp = malloc(elem_size * list_size); + if (tmp == NULL) abort(); + + // copy elements from source array + char *loc = tmp; + for (size_t i = 0; i < list_size; i++) { + void *src = invoke_list_func(at, list, i); + memcpy(loc, src, elem_size); + loc += elem_size; + } + + // qsort + qsort(tmp, list_size, elem_size, + list->collection.cmpfunc); + + // copy elements back + loc = tmp; + for (size_t i = 0; i < list_size; i++) { + void *dest = invoke_list_func(at, list, i); + memcpy(dest, loc, elem_size); + loc += elem_size; + } + + free(tmp); +} + +int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j) { + if (i == j) return 0; + if (i >= list->collection.size) return 1; + if (j >= list->collection.size) return 1; + + size_t elem_size = list->collection.elem_size; + + void *tmp = malloc(elem_size); + if (tmp == NULL) return 1; + + void *ip = invoke_list_func(at, list, i); + void *jp = invoke_list_func(at, list, j); + + memcpy(tmp, ip, elem_size); + memcpy(ip, jp, elem_size); + memcpy(jp, tmp, elem_size); + + free(tmp); + + return 0; +} + void cxListDestroy(CxList *list) { list->cl->destructor(list); } int cxListCompare( - CxList const *list, - CxList const *other + const CxList *list, + const CxList *other ) { - if ( - // if one is storing pointers but the other is not - (list->store_pointer ^ other->store_pointer) || + bool cannot_optimize = false; + + // if one is storing pointers but the other is not + cannot_optimize |= list->collection.store_pointer ^ other->collection.store_pointer; + + // if one class is wrapped but the other is not + cannot_optimize |= (list->climpl == NULL) ^ (other->climpl == NULL); - // if one class is wrapped but the other is not - ((list->climpl == NULL) ^ (other->climpl == NULL)) || + // if the compare functions do not match or both are NULL + if (!cannot_optimize) { + cx_compare_func list_cmp = (cx_compare_func) (list->climpl != NULL ? + list->climpl->compare : list->cl->compare); + cx_compare_func other_cmp = (cx_compare_func) (other->climpl != NULL ? + other->climpl->compare : other->cl->compare); + cannot_optimize |= list_cmp != other_cmp; + cannot_optimize |= list_cmp == NULL; + } - // if the resolved compare functions are not the same - ((list->climpl != NULL ? list->climpl->compare : list->cl->compare) != - (other->climpl != NULL ? other->climpl->compare : other->cl->compare)) - ) { + if (cannot_optimize) { // lists are definitely different - cannot use internal compare function - if (list->size == other->size) { + if (list->collection.size == other->collection.size) { CxIterator left = list->cl->iterator(list, 0, false); CxIterator right = other->cl->iterator(other, 0, false); - for (size_t i = 0; i < list->size; i++) { + for (size_t i = 0; i < list->collection.size; i++) { void *leftValue = cxIteratorCurrent(left); void *rightValue = cxIteratorCurrent(right); - int d = list->cmpfunc(leftValue, rightValue); + int d = list->collection.cmpfunc(leftValue, rightValue); if (d != 0) { return d; } @@ -309,7 +460,7 @@ } return 0; } else { - return list->size < other->size ? -1 : 1; + return list->collection.size < other->collection.size ? -1 : 1; } } else { // lists are compatible @@ -317,28 +468,20 @@ } } -CxMutIterator cxListMutIteratorAt( +CxIterator cxListMutIteratorAt( CxList *list, size_t index ) { CxIterator it = list->cl->iterator(list, index, false); it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; + return it; } -CxMutIterator cxListMutBackwardsIteratorAt( +CxIterator cxListMutBackwardsIteratorAt( CxList *list, size_t index ) { CxIterator it = list->cl->iterator(list, index, true); it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; + return it; }
--- a/ucx/map.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/map.c Sun Oct 06 12:00:31 2024 +0200 @@ -36,22 +36,22 @@ } static void *cx_empty_map_get( - __attribute__((__unused__)) CxMap const *map, + __attribute__((__unused__)) const CxMap *map, __attribute__((__unused__)) CxHashKey key ) { return NULL; } -static bool cx_empty_map_iter_valid(__attribute__((__unused__)) void const *iter) { +static bool cx_empty_map_iter_valid(__attribute__((__unused__)) const void *iter) { return false; } static CxIterator cx_empty_map_iterator( - struct cx_map_s const *map, + const struct cx_map_s *map, __attribute__((__unused__)) enum cx_map_iterator_type type ) { CxIterator iter = {0}; - iter.src_handle = map; + iter.src_handle.c = map; iter.base.valid = cx_empty_map_iter_valid; return iter; } @@ -66,14 +66,16 @@ }; CxMap cx_empty_map = { - NULL, - NULL, - 0, - 0, - NULL, - NULL, - NULL, - false, + { + NULL, + NULL, + 0, + 0, + NULL, + NULL, + NULL, + false + }, &cx_empty_map_class }; @@ -81,32 +83,20 @@ // </editor-fold> -CxMutIterator cxMapMutIteratorValues(CxMap *map) { +CxIterator cxMapMutIteratorValues(CxMap *map) { CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_VALUES); it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; + return it; } -CxMutIterator cxMapMutIteratorKeys(CxMap *map) { +CxIterator cxMapMutIteratorKeys(CxMap *map) { CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_KEYS); it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; + return it; } -CxMutIterator cxMapMutIterator(CxMap *map) { +CxIterator cxMapMutIterator(CxMap *map) { CxIterator it = map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS); it.base.mutating = true; - - // we know the iterators share the same memory layout - CxMutIterator iter; - memcpy(&iter, &it, sizeof(CxMutIterator)); - return iter; + return it; }
--- a/ucx/printf.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/printf.c Sun Oct 06 12:00:31 2024 +0200 @@ -39,7 +39,7 @@ int cx_fprintf( void *stream, cx_write_func wfc, - char const *fmt, + const char *fmt, ... ) { int ret; @@ -53,7 +53,7 @@ int cx_vfprintf( void *stream, cx_write_func wfc, - char const *fmt, + const char *fmt, va_list ap ) { char buf[CX_PRINTF_SBO_SIZE]; @@ -85,8 +85,8 @@ } cxmutstr cx_asprintf_a( - CxAllocator const *allocator, - char const *fmt, + const CxAllocator *allocator, + const char *fmt, ... ) { va_list ap; @@ -97,8 +97,8 @@ } cxmutstr cx_vasprintf_a( - CxAllocator const *a, - char const *fmt, + const CxAllocator *a, + const char *fmt, va_list ap ) { cxmutstr s; @@ -132,7 +132,7 @@ return s; } -int cx_sprintf_a(CxAllocator *alloc, char **str, size_t len, const char *fmt, ... ) { +int cx_sprintf_a(CxAllocator *alloc, char **str, size_t *len, const char *fmt, ... ) { va_list ap; va_start(ap, fmt); int ret = cx_vsprintf_a(alloc, str, len, fmt, ap); @@ -140,11 +140,11 @@ return ret; } -int cx_vsprintf_a(CxAllocator *alloc, char **str, size_t len, const char *fmt, va_list ap) { +int cx_vsprintf_a(CxAllocator *alloc, char **str, size_t *len, const char *fmt, va_list ap) { va_list ap2; va_copy(ap2, ap); - int ret = vsnprintf(*str, len, fmt, ap); - if ((unsigned) ret >= len) { + int ret = vsnprintf(*str, *len, fmt, ap); + if ((unsigned) ret >= *len) { unsigned newlen = ret + 1; char *ptr = cxRealloc(alloc, *str, newlen); if (ptr) { @@ -152,6 +152,7 @@ if (newret < 0) { cxFree(alloc, ptr); } else { + *len = newlen; *str = ptr; ret = newret; } @@ -161,7 +162,7 @@ return ret; } -int cx_sprintf_sa(CxAllocator *alloc, char *buf, size_t len, char **str, const char *fmt, ... ) { +int cx_sprintf_sa(CxAllocator *alloc, char *buf, size_t *len, char **str, const char *fmt, ... ) { va_list ap; va_start(ap, fmt); int ret = cx_vsprintf_sa(alloc, buf, len, str, fmt, ap); @@ -169,12 +170,12 @@ return ret; } -int cx_vsprintf_sa(CxAllocator *alloc, char *buf, size_t len, char **str, const char *fmt, va_list ap) { +int cx_vsprintf_sa(CxAllocator *alloc, char *buf, size_t *len, char **str, const char *fmt, va_list ap) { va_list ap2; va_copy(ap2, ap); - int ret = vsnprintf(buf, len, fmt, ap); + int ret = vsnprintf(buf, *len, fmt, ap); *str = buf; - if ((unsigned) ret >= len) { + if ((unsigned) ret >= *len) { unsigned newlen = ret + 1; char *ptr = cxMalloc(alloc, newlen); if (ptr) { @@ -182,6 +183,7 @@ if (newret < 0) { cxFree(alloc, ptr); } else { + *len = newlen; *str = ptr; ret = newret; }
--- a/ucx/string.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/string.c Sun Oct 06 12:00:31 2024 +0200 @@ -72,7 +72,7 @@ } void cx_strfree_a( - CxAllocator const *alloc, + const CxAllocator *alloc, cxmutstr *str ) { cxFree(alloc, str->ptr); @@ -99,7 +99,7 @@ } cxmutstr cx_strcat_ma( - CxAllocator const *alloc, + const CxAllocator *alloc, cxmutstr str, size_t count, ... @@ -377,7 +377,7 @@ } size_t cx_strsplit_a( - CxAllocator const *allocator, + const CxAllocator *allocator, cxstring string, cxstring delim, size_t limit, @@ -419,7 +419,7 @@ } size_t cx_strsplit_ma( - CxAllocator const *allocator, + const CxAllocator *allocator, cxmutstr string, cxstring delim, size_t limit, @@ -460,25 +460,25 @@ } int cx_strcmp_p( - void const *s1, - void const *s2 + const void *s1, + const void *s2 ) { - cxstring const *left = s1; - cxstring const *right = s2; + const cxstring *left = s1; + const cxstring *right = s2; return cx_strcmp(*left, *right); } int cx_strcasecmp_p( - void const *s1, - void const *s2 + const void *s1, + const void *s2 ) { - cxstring const *left = s1; - cxstring const *right = s2; + const cxstring *left = s1; + const cxstring *right = s2; return cx_strcasecmp(*left, *right); } cxmutstr cx_strdup_a( - CxAllocator const *allocator, + const CxAllocator *allocator, cxstring string ) { cxmutstr result = { @@ -587,7 +587,7 @@ } cxmutstr cx_strreplacen_a( - CxAllocator const *allocator, + const CxAllocator *allocator, cxstring str, cxstring pattern, cxstring replacement, @@ -778,7 +778,7 @@ void cx_strtok_delim( CxStrtokCtx *ctx, - cxstring const *delim, + const cxstring *delim, size_t count ) { ctx->delim_more = delim;
--- a/ucx/szmul.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/szmul.c Sun Oct 06 12:00:31 2024 +0200 @@ -43,4 +43,4 @@ *result = 0; return 1; } -} \ No newline at end of file +}
--- a/ucx/tree.c Thu Oct 03 18:54:19 2024 +0200 +++ b/ucx/tree.c Sun Oct 06 12:00:31 2024 +0200 @@ -28,37 +28,72 @@ #include "cx/tree.h" +#include "cx/array_list.h" + #include <assert.h> #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) -#define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) #define tree_parent(node) CX_TREE_PTR(node, loc_parent) #define tree_children(node) CX_TREE_PTR(node, loc_children) +#define tree_last_child(node) CX_TREE_PTR(node, loc_last_child) #define tree_prev(node) CX_TREE_PTR(node, loc_prev) #define tree_next(node) CX_TREE_PTR(node, loc_next) +#define cx_tree_ptr_locations \ + loc_parent, loc_children, loc_last_child, loc_prev, loc_next + +static void cx_tree_zero_pointers( + void *node, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + tree_parent(node) = NULL; + tree_prev(node) = NULL; + tree_next(node) = NULL; + tree_children(node) = NULL; + if (loc_last_child >= 0) { + tree_last_child(node) = NULL; + } +} + void cx_tree_link( void *restrict parent, void *restrict node, ptrdiff_t loc_parent, ptrdiff_t loc_children, + ptrdiff_t loc_last_child, ptrdiff_t loc_prev, ptrdiff_t loc_next ) { void *current_parent = tree_parent(node); if (current_parent == parent) return; if (current_parent != NULL) { - cx_tree_unlink(node, loc_parent, loc_children, - loc_prev, loc_next); + cx_tree_unlink(node, cx_tree_ptr_locations); } if (tree_children(parent) == NULL) { tree_children(parent) = node; + if (loc_last_child >= 0) { + tree_last_child(parent) = node; + } } else { - void *children = tree_children(parent); - tree_prev(children) = node; - tree_next(node) = children; - tree_children(parent) = node; + if (loc_last_child >= 0) { + void *child = tree_last_child(parent); + tree_prev(node) = child; + tree_next(child) = node; + tree_last_child(parent) = node; + } else { + void *child = tree_children(parent); + void *next; + while ((next = tree_next(child)) != NULL) { + child = next; + } + tree_prev(node) = child; + tree_next(child) = node; + } } tree_parent(node) = parent; } @@ -67,6 +102,7 @@ void *node, ptrdiff_t loc_parent, ptrdiff_t loc_children, + ptrdiff_t loc_last_child, ptrdiff_t loc_prev, ptrdiff_t loc_next ) { @@ -74,14 +110,849 @@ void *left = tree_prev(node); void *right = tree_next(node); - assert(left == NULL || tree_children(tree_parent(node)) != node); + void *parent = tree_parent(node); + assert(left == NULL || tree_children(parent) != node); + assert(right == NULL || loc_last_child < 0 || + tree_last_child(parent) != node); + if (left == NULL) { - tree_children(tree_parent(node)) = right; + tree_children(parent) = right; } else { tree_next(left) = right; } - if (right != NULL) tree_prev(right) = left; + if (right == NULL) { + if (loc_last_child >= 0) { + tree_last_child(parent) = left; + } + } else { + tree_prev(right) = left; + } + tree_parent(node) = NULL; tree_prev(node) = NULL; tree_next(node) = NULL; } + +int cx_tree_search( + const void *root, + const void *node, + cx_tree_search_func sfunc, + void **result, + ptrdiff_t loc_children, + ptrdiff_t loc_next +) { + int ret; + *result = NULL; + + // shortcut: compare root before doing anything else + ret = sfunc(root, node); + if (ret < 0) { + return ret; + } else if (ret == 0 || tree_children(root) == NULL) { + *result = (void*)root; + return ret; + } + + // create a working stack + CX_ARRAY_DECLARE(const void *, work); + cx_array_initialize(work, 32); + + // add the children of root to the working stack + { + void *c = tree_children(root); + while (c != NULL) { + cx_array_simple_add(work, c); + c = tree_next(c); + } + } + + // remember a candidate for adding the data + // also remember the exact return code from sfunc + void *candidate = (void *) root; + int ret_candidate = ret; + + // process the working stack + while (work_size > 0) { + // pop element + const void *elem = work[--work_size]; + + // apply the search function + ret = sfunc(elem, node); + + if (ret == 0) { + // if found, exit the search + *result = (void *) elem; + work_size = 0; + break; + } else if (ret > 0) { + // if children might contain the data, add them to the stack + void *c = tree_children(elem); + while (c != NULL) { + cx_array_simple_add(work, c); + c = tree_next(c); + } + + // remember this node in case no child is suitable + if (ret < ret_candidate) { + candidate = (void *) elem; + ret_candidate = ret; + } + } + } + + // not found, but was there a candidate? + if (ret != 0 && candidate != NULL) { + ret = ret_candidate; + *result = candidate; + } + + // free the working queue and return + free(work); + return ret; +} + +int cx_tree_search_data( + const void *root, + const void *data, + cx_tree_search_data_func sfunc, + void **result, + ptrdiff_t loc_children, + ptrdiff_t loc_next +) { + // it is basically the same implementation + return cx_tree_search( + root, data, + (cx_tree_search_func) sfunc, + result, + loc_children, loc_next); +} + +static bool cx_tree_iter_valid(const void *it) { + const struct cx_tree_iterator_s *iter = it; + return iter->node != NULL; +} + +static void *cx_tree_iter_current(const void *it) { + const struct cx_tree_iterator_s *iter = it; + return iter->node; +} + +static void cx_tree_iter_next(void *it) { + struct cx_tree_iterator_s *iter = it; + ptrdiff_t const loc_next = iter->loc_next; + ptrdiff_t const loc_children = iter->loc_children; + // protect us from misuse + if (!iter->base.valid(iter)) return; + + void *children; + + // check if we are currently exiting or entering nodes + if (iter->exiting) { + children = NULL; + // skipping on exit is pointless, just clear the flag + iter->skip = false; + } else { + if (iter->skip) { + // skip flag is set, pretend that there are no children + iter->skip = false; + children = NULL; + } else { + // try to enter the children (if any) + children = tree_children(iter->node); + } + } + + if (children == NULL) { + // search for the next node + void *next; + cx_tree_iter_search_next: + // check if there is a sibling + if (iter->exiting) { + next = iter->node_next; + } else { + next = tree_next(iter->node); + iter->node_next = next; + } + if (next == NULL) { + // no sibling, we are done with this node and exit + if (iter->visit_on_exit && !iter->exiting) { + // iter is supposed to visit the node again + iter->exiting = true; + } else { + iter->exiting = false; + if (iter->depth == 1) { + // there is no parent - we have iterated the entire tree + // invalidate the iterator and free the node stack + iter->node = iter->node_next = NULL; + iter->stack_capacity = iter->depth = 0; + free(iter->stack); + iter->stack = NULL; + } else { + // the parent node can be obtained from the top of stack + // this way we can avoid the loc_parent in the iterator + iter->depth--; + iter->node = iter->stack[iter->depth - 1]; + // retry with the parent node to find a sibling + goto cx_tree_iter_search_next; + } + } + } else { + if (iter->visit_on_exit && !iter->exiting) { + // iter is supposed to visit the node again + iter->exiting = true; + } else { + iter->exiting = false; + // move to the sibling + iter->counter++; + iter->node = next; + // new top of stack is the sibling + iter->stack[iter->depth - 1] = next; + } + } + } else { + // node has children, push the first child onto the stack and enter it + cx_array_simple_add(iter->stack, children); + iter->node = children; + iter->counter++; + } +} + +CxTreeIterator cx_tree_iterator( + void *root, + bool visit_on_exit, + ptrdiff_t loc_children, + ptrdiff_t loc_next +) { + CxTreeIterator iter; + iter.loc_children = loc_children; + iter.loc_next = loc_next; + iter.visit_on_exit = visit_on_exit; + + // initialize members + iter.node_next = NULL; + iter.exiting = false; + iter.skip = false; + + // assign base iterator functions + iter.base.mutating = false; + iter.base.remove = false; + iter.base.current_impl = NULL; + iter.base.valid = cx_tree_iter_valid; + iter.base.next = cx_tree_iter_next; + iter.base.current = cx_tree_iter_current; + + // visit the root node + iter.node = root; + if (root != NULL) { + iter.stack_capacity = 16; + iter.stack = malloc(sizeof(void *) * 16); + iter.stack[0] = root; + iter.counter = 1; + iter.depth = 1; + } else { + iter.stack_capacity = 0; + iter.stack = NULL; + iter.counter = 0; + iter.depth = 0; + } + + return iter; +} + +static bool cx_tree_visitor_valid(const void *it) { + const struct cx_tree_visitor_s *iter = it; + return iter->node != NULL; +} + +static void *cx_tree_visitor_current(const void *it) { + const struct cx_tree_visitor_s *iter = it; + return iter->node; +} + +__attribute__((__nonnull__)) +static void cx_tree_visitor_enqueue_siblings( + struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) { + node = tree_next(node); + while (node != NULL) { + struct cx_tree_visitor_queue_s *q; + q = malloc(sizeof(struct cx_tree_visitor_queue_s)); + q->depth = iter->queue_last->depth; + q->node = node; + iter->queue_last->next = q; + iter->queue_last = q; + node = tree_next(node); + } + iter->queue_last->next = NULL; +} + +static void cx_tree_visitor_next(void *it) { + struct cx_tree_visitor_s *iter = it; + // protect us from misuse + if (!iter->base.valid(iter)) return; + + ptrdiff_t const loc_next = iter->loc_next; + ptrdiff_t const loc_children = iter->loc_children; + + // add the children of the current node to the queue + // unless the skip flag is set + void *children; + if (iter->skip) { + iter->skip = false; + children = NULL; + } else { + children = tree_children(iter->node); + } + if (children != NULL) { + struct cx_tree_visitor_queue_s *q; + q = malloc(sizeof(struct cx_tree_visitor_queue_s)); + q->depth = iter->depth + 1; + q->node = children; + if (iter->queue_last == NULL) { + assert(iter->queue_next == NULL); + iter->queue_next = q; + } else { + iter->queue_last->next = q; + } + iter->queue_last = q; + cx_tree_visitor_enqueue_siblings(iter, children, loc_next); + } + + // check if there is a next node + if (iter->queue_next == NULL) { + iter->node = NULL; + return; + } + + // dequeue the next node + iter->node = iter->queue_next->node; + iter->depth = iter->queue_next->depth; + { + struct cx_tree_visitor_queue_s *q = iter->queue_next; + iter->queue_next = q->next; + if (iter->queue_next == NULL) { + assert(iter->queue_last == q); + iter->queue_last = NULL; + } + free(q); + } + + // increment the node counter + iter->counter++; +} + +CxTreeVisitor cx_tree_visitor( + void *root, + ptrdiff_t loc_children, + ptrdiff_t loc_next +) { + CxTreeVisitor iter; + iter.loc_children = loc_children; + iter.loc_next = loc_next; + + // initialize members + iter.skip = false; + iter.queue_next = NULL; + iter.queue_last = NULL; + + // assign base iterator functions + iter.base.mutating = false; + iter.base.remove = false; + iter.base.current_impl = NULL; + iter.base.valid = cx_tree_visitor_valid; + iter.base.next = cx_tree_visitor_next; + iter.base.current = cx_tree_visitor_current; + + // visit the root node + iter.node = root; + if (root != NULL) { + iter.counter = 1; + iter.depth = 1; + } else { + iter.counter = 0; + iter.depth = 0; + } + + return iter; +} + +static void cx_tree_add_link_duplicate( + void *original, void *duplicate, + ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, ptrdiff_t loc_next +) { + void *shared_parent = tree_parent(original); + if (shared_parent == NULL) { + cx_tree_link(original, duplicate, cx_tree_ptr_locations); + } else { + cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations); + } +} + +static void cx_tree_add_link_new( + void *parent, void *node, cx_tree_search_func sfunc, + ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, ptrdiff_t loc_next +) { + // check the current children one by one, + // if they could be children of the new node + void *child = tree_children(parent); + while (child != NULL) { + void *next = tree_next(child); + + if (sfunc(node, child) > 0) { + // the sibling could be a child -> re-link + cx_tree_link(node, child, cx_tree_ptr_locations); + } + + child = next; + } + + // add new node as new child + cx_tree_link(parent, node, cx_tree_ptr_locations); +} + +int cx_tree_add( + const void *src, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **cnode, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + *cnode = cfunc(src, cdata); + if (*cnode == NULL) return 1; + cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations); + + void *match = NULL; + int result = cx_tree_search( + root, + *cnode, + sfunc, + &match, + loc_children, + loc_next + ); + + if (result < 0) { + // node does not fit into the tree - return non-zero value + return 1; + } else if (result == 0) { + // data already found in the tree, link duplicate + cx_tree_add_link_duplicate(match, *cnode, cx_tree_ptr_locations); + } else { + // closest match found, add new node + cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations); + } + + return 0; +} + +unsigned int cx_tree_add_look_around_depth = 3; + +size_t cx_tree_add_iter( + struct cx_iterator_base_s *iter, + size_t num, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **failed, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + // erase the failed pointer + *failed = NULL; + + // iter not valid? cancel... + if (!iter->valid(iter)) return 0; + + size_t processed = 0; + void *current_node = root; + const void *elem; + + for (void **eptr; processed < num && + iter->valid(iter) && (eptr = iter->current(iter)) != NULL; + iter->next(iter)) { + elem = *eptr; + + // create the new node + void *new_node = cfunc(elem, cdata); + if (new_node == NULL) return processed; + cx_tree_zero_pointers(new_node, cx_tree_ptr_locations); + + // start searching from current node + void *match; + int result; + unsigned int look_around_retries = cx_tree_add_look_around_depth; + cx_tree_add_look_around_retry: + result = cx_tree_search( + current_node, + new_node, + sfunc, + &match, + loc_children, + loc_next + ); + + if (result < 0) { + // traverse upwards and try to find better parents + void *parent = tree_parent(current_node); + if (parent != NULL) { + if (look_around_retries > 0) { + look_around_retries--; + current_node = parent; + } else { + // look around retries exhausted, start from the root + current_node = root; + } + goto cx_tree_add_look_around_retry; + } else { + // no parents. so we failed + *failed = new_node; + return processed; + } + } else if (result == 0) { + // data already found in the tree, link duplicate + cx_tree_add_link_duplicate(match, new_node, cx_tree_ptr_locations); + // but stick with the original match, in case we needed a new root + current_node = match; + } else { + // closest match found, add new node as child + cx_tree_add_link_new(match, new_node, sfunc, + cx_tree_ptr_locations); + current_node = match; + } + + processed++; + } + return processed; +} + +size_t cx_tree_add_array( + const void *src, + size_t num, + size_t elem_size, + cx_tree_search_func sfunc, + cx_tree_node_create_func cfunc, + void *cdata, + void **failed, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + // erase failed pointer + *failed = NULL; + + // super special case: zero elements + if (num == 0) { + return 0; + } + + // special case: one element does not need an iterator + if (num == 1) { + void *node; + if (0 == cx_tree_add( + src, sfunc, cfunc, cdata, &node, root, + loc_parent, loc_children, loc_last_child, + loc_prev, loc_next)) { + return 1; + } else { + *failed = node; + return 0; + } + } + + // otherwise, create iterator and hand over to other function + CxIterator iter = cxIterator(src, elem_size, num); + return cx_tree_add_iter(cxIteratorRef(iter), num, sfunc, + cfunc, cdata, failed, root, + loc_parent, loc_children, loc_last_child, + loc_prev, loc_next); +} + +static void cx_tree_default_destructor(CxTree *tree) { + if (tree->simple_destructor != NULL || tree->advanced_destructor != NULL) { + CxTreeIterator iter = tree->cl->iterator(tree, true); + cx_foreach(void *, node, iter) { + if (iter.exiting) { + if (tree->simple_destructor) { + tree->simple_destructor(node); + } + if (tree->advanced_destructor) { + tree->advanced_destructor(tree->destructor_data, node); + } + } + } + } + cxFree(tree->allocator, tree); +} + +static CxTreeIterator cx_tree_default_iterator( + CxTree *tree, + bool visit_on_exit +) { + return cx_tree_iterator( + tree->root, visit_on_exit, + tree->loc_children, tree->loc_next + ); +} + +static CxTreeVisitor cx_tree_default_visitor(CxTree *tree) { + return cx_tree_visitor(tree->root, tree->loc_children, tree->loc_next); +} + +static int cx_tree_default_insert_element( + CxTree *tree, + const void *data +) { + void *node; + if (tree->root == NULL) { + node = tree->node_create(data, tree); + if (node == NULL) return 1; + cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); + tree->root = node; + tree->size = 1; + return 0; + } + int result = cx_tree_add(data, tree->search, tree->node_create, + tree, &node, tree->root, cx_tree_node_layout(tree)); + if (0 == result) { + tree->size++; + } else { + cxFree(tree->allocator, node); + } + return result; +} + +static size_t cx_tree_default_insert_many( + CxTree *tree, + struct cx_iterator_base_s *iter, + size_t n +) { + size_t ins = 0; + if (!iter->valid(iter)) return 0; + if (tree->root == NULL) { + // use the first element from the iter to create the root node + void **eptr = iter->current(iter); + void *node = tree->node_create(*eptr, tree); + if (node == NULL) return 0; + cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); + tree->root = node; + ins = 1; + iter->next(iter); + } + void *failed; + ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create, + tree, &failed, tree->root, cx_tree_node_layout(tree)); + tree->size += ins; + if (ins < n) { + cxFree(tree->allocator, failed); + } + return ins; +} + +static void *cx_tree_default_find( + CxTree *tree, + const void *subtree, + const void *data +) { + if (tree->root == NULL) return NULL; + + void *found; + if (0 == cx_tree_search_data( + subtree, + data, + tree->search_data, + &found, + tree->loc_children, + tree->loc_next + )) { + return found; + } else { + return NULL; + } +} + +static cx_tree_class cx_tree_default_class = { + cx_tree_default_destructor, + cx_tree_default_insert_element, + cx_tree_default_insert_many, + cx_tree_default_find, + cx_tree_default_iterator, + cx_tree_default_visitor +}; + +CxTree *cxTreeCreate( + const CxAllocator *allocator, + cx_tree_node_create_func create_func, + cx_tree_search_func search_func, + cx_tree_search_data_func search_data_func, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); + if (tree == NULL) return NULL; + + tree->cl = &cx_tree_default_class; + tree->allocator = allocator; + tree->node_create = create_func; + tree->search = search_func; + tree->search_data = search_data_func; + tree->advanced_destructor = (cx_destructor_func2) cxFree; + tree->destructor_data = (void *) allocator; + tree->loc_parent = loc_parent; + tree->loc_children = loc_children; + tree->loc_last_child = loc_last_child; + tree->loc_prev = loc_prev; + tree->loc_next = loc_next; + tree->root = NULL; + tree->size = 0; + + return tree; +} + +CxTree *cxTreeCreateWrapped( + const CxAllocator *allocator, + void *root, + ptrdiff_t loc_parent, + ptrdiff_t loc_children, + ptrdiff_t loc_last_child, + ptrdiff_t loc_prev, + ptrdiff_t loc_next +) { + CxTree *tree = cxMalloc(allocator, sizeof(CxTree)); + if (tree == NULL) return NULL; + + tree->cl = &cx_tree_default_class; + // set the allocator anyway, just in case... + tree->allocator = allocator; + tree->node_create = NULL; + tree->search = NULL; + tree->search_data = NULL; + tree->simple_destructor = NULL; + tree->advanced_destructor = NULL; + tree->destructor_data = NULL; + tree->loc_parent = loc_parent; + tree->loc_children = loc_children; + tree->loc_last_child = loc_last_child; + tree->loc_prev = loc_prev; + tree->loc_next = loc_next; + tree->root = root; + tree->size = cxTreeSubtreeSize(tree, root); + return tree; +} + +int cxTreeAddChild( + CxTree *tree, + void *parent, + const void *data) { + void *node = tree->node_create(data, tree); + if (node == NULL) return 1; + cx_tree_zero_pointers(node, cx_tree_node_layout(tree)); + cx_tree_link(parent, node, cx_tree_node_layout(tree)); + tree->size++; + return 0; +} + +size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) { + CxTreeVisitor visitor = cx_tree_visitor( + subtree_root, + tree->loc_children, + tree->loc_next + ); + while (cxIteratorValid(visitor)) { + cxIteratorNext(visitor); + } + return visitor.counter; +} + +size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root) { + CxTreeVisitor visitor = cx_tree_visitor( + subtree_root, + tree->loc_children, + tree->loc_next + ); + while (cxIteratorValid(visitor)) { + cxIteratorNext(visitor); + } + return visitor.depth; +} + +size_t cxTreeDepth(CxTree *tree) { + CxTreeVisitor visitor = tree->cl->visitor(tree); + while (cxIteratorValid(visitor)) { + cxIteratorNext(visitor); + } + return visitor.depth; +} + +int cxTreeRemove( + CxTree *tree, + void *node, + cx_tree_relink_func relink_func +) { + if (node == tree->root) return 1; + + // determine the new parent + ptrdiff_t loc_parent = tree->loc_parent; + void *new_parent = tree_parent(node); + + // first, unlink from the parent + cx_tree_unlink(node, cx_tree_node_layout(tree)); + + // then relink each child + ptrdiff_t loc_children = tree->loc_children; + ptrdiff_t loc_next = tree->loc_next; + void *child = tree_children(node); + while (child != NULL) { + // forcibly set the parent to NULL - we do not use the unlink function + // because that would unnecessarily modify the children linked list + tree_parent(child) = NULL; + + // update contents, if required + if (relink_func != NULL) { + relink_func(child, node, new_parent); + } + + // link to new parent + cx_tree_link(new_parent, child, cx_tree_node_layout(tree)); + + // proceed to next child + child = tree_next(child); + } + + // clear the linked list of the removed node + tree_children(node) = NULL; + ptrdiff_t loc_last_child = tree->loc_last_child; + if (loc_last_child >= 0) tree_last_child(node) = NULL; + + // the tree now has one member less + tree->size--; + + return 0; +} + +void cxTreeRemoveSubtree(CxTree *tree, void *node) { + if (node == tree->root) { + tree->root = NULL; + tree->size = 0; + return; + } + size_t subtree_size = cxTreeSubtreeSize(tree, node); + cx_tree_unlink(node, cx_tree_node_layout(tree)); + tree->size -= subtree_size; +}
