# HG changeset patch
# User Olaf Wintermann <olaf.wintermann@gmail.com>
# Date 1728208831 -7200
# Node ID ce13a778654a6e45bd6af29b89ec1be22921fe44
# Parent  38cb8e3992e88e3ec2762afc7d9d02711b619bea
update ucx

diff -r 38cb8e3992e8 -r ce13a778654a ucx/Makefile
--- 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))
 
diff -r 38cb8e3992e8 -r ce13a778654a ucx/allocator.c
--- 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);
diff -r 38cb8e3992e8 -r ce13a778654a ucx/array_list.c
--- 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;
diff -r 38cb8e3992e8 -r ce13a778654a ucx/buffer.c
--- 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);
diff -r 38cb8e3992e8 -r ce13a778654a ucx/compare.c
--- 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;
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/allocator.h
--- 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"
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/array_list.h
--- 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"
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/buffer.h
--- 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
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/collection.h
--- 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"
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/common.h
--- 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 *
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/compare.h
--- 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
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/hash_key.h
--- 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
 );
 
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/hash_map.h
--- 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.
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/iterator.h
--- 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
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/linked_list.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"
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/list.h
--- 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
 );
 
 /**
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/map.h
--- 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
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/mempool.h
--- 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.
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/printf.h
--- 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
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/string.h
--- 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
 );
 
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/test.h
--- 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++; \
diff -r 38cb8e3992e8 -r ce13a778654a ucx/cx/tree.h
--- 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
diff -r 38cb8e3992e8 -r ce13a778654a ucx/hash_key.c
--- 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;
diff -r 38cb8e3992e8 -r ce13a778654a ucx/hash_map.c
--- 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;
diff -r 38cb8e3992e8 -r ce13a778654a ucx/iterator.c
--- /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;
+}
diff -r 38cb8e3992e8 -r ce13a778654a ucx/linked_list.c
--- 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);
     }
 
diff -r 38cb8e3992e8 -r ce13a778654a ucx/list.c
--- 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;
 }
diff -r 38cb8e3992e8 -r ce13a778654a ucx/map.c
--- 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;
 }
diff -r 38cb8e3992e8 -r ce13a778654a ucx/printf.c
--- 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;
             }
diff -r 38cb8e3992e8 -r ce13a778654a ucx/string.c
--- 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;
diff -r 38cb8e3992e8 -r ce13a778654a ucx/szmul.c
--- 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
+}
diff -r 38cb8e3992e8 -r ce13a778654a ucx/tree.c
--- 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;
+}