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;
 }