diff -r ae61523bce20 -r 2f71f4ee247a ucx/linked_list.c
--- a/ucx/linked_list.c	Thu Oct 03 18:52:51 2024 +0200
+++ b/ucx/linked_list.c	Sun Oct 06 18:18:04 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);
     }