diff -r 81c4f73236a4 -r c3f2f16fa4b8 ucx/list.c --- a/ucx/list.c Sat Oct 04 14:54:25 2025 +0200 +++ b/ucx/list.c Sun Oct 19 21:20:08 2025 +0200 @@ -38,10 +38,18 @@ const void *l, const void *r ) { + // l and r are guaranteed to be non-NULL pointing to the list's memory void *const *lptr = l; void *const *rptr = r; - const void *left = lptr == NULL ? NULL : *lptr; - const void *right = rptr == NULL ? NULL : *rptr; + const void *left = *lptr; + const void *right = *rptr; + if (left == NULL) { + // NULL is smaller than any value except NULL + return right == NULL ? 0 : -1; + } else if (right == NULL) { + // any value is larger than NULL + return 1; + } return cx_pl_cmpfunc_impl(left, right); } @@ -90,6 +98,17 @@ return result; } +static size_t cx_pl_insert_unique( + struct cx_list_s *list, + const void *array, + size_t n +) { + cx_pl_hack_cmpfunc(list); + size_t result = list->climpl->insert_unique(list, array, n); + cx_pl_unhack_cmpfunc(list); + return result; +} + static int cx_pl_insert_iter( struct cx_iterator_s *iter, const void *elem, @@ -181,6 +200,7 @@ cx_pl_insert_element, cx_pl_insert_array, cx_pl_insert_sorted, + cx_pl_insert_unique, cx_pl_insert_iter, cx_pl_remove, cx_pl_clear, @@ -238,6 +258,7 @@ NULL, NULL, NULL, + NULL, cx_emptyl_noop, NULL, cx_emptyl_at, @@ -284,15 +305,19 @@ for (; i < n; i++) { if (NULL == invoke_list_func( insert_element, list, index + i, - src + (i * elem_size))) return i; + src + i * elem_size) + ) { + return i; // LCOV_EXCL_LINE + } } return i; } -size_t cx_list_default_insert_sorted( +static size_t cx_list_default_insert_sorted_impl( struct cx_list_s *list, const void *sorted_data, - size_t n + size_t n, + bool allow_duplicates ) { // corner case if (n == 0) return 0; @@ -302,22 +327,54 @@ const char *src = sorted_data; // track indices and number of inserted items - size_t di = 0, si = 0, inserted = 0; + size_t di = 0, si = 0, processed = 0; // search the list for insertion points - for (; di < list->collection.size; di++) { + while (di < list->collection.size) { 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; + // compare the current list element with the first source element + // if less, skip the list elements + // if equal, skip the list elements and optionally the source elements + { + int d = cmp(list_elm, src); + if (d <= 0) { + if (!allow_duplicates && d == 0) { + src += elem_size; + si++; + processed++; // we also count duplicates for the return value + while (si < n && cmp(list_elm, src) == 0) { + src += elem_size; + si++; + processed++; + } + if (processed == n) { + return processed; + } + } + di++; + continue; + } } - // determine number of consecutive elements that can be inserted - size_t ins = 1; + // determine the number of consecutive elements that can be inserted + size_t ins = 1, skip = 0; const char *next = src; while (++si < n) { + if (!allow_duplicates) { + // skip duplicates within the source + if (cmp(next, next + elem_size) == 0) { + next += elem_size; + skip++; + continue; + } else { + if (skip > 0) { + // if we had to skip something, we must wait for the next run + next += elem_size; + break; + } + } + } next += elem_size; // once we become larger than the list elem, break if (cmp(list_elm, next) <= 0) { @@ -329,33 +386,70 @@ // insert the elements at location si if (ins == 1) { - if (NULL == invoke_list_func( - insert_element, list, di, src)) return inserted; + if (NULL == invoke_list_func(insert_element, list, di, src)) { + return processed; // LCOV_EXCL_LINE + } } else { size_t r = invoke_list_func(insert_array, list, di, src, ins); - if (r < ins) return inserted + r; + if (r < ins) { + return processed + r; // LCOV_EXCL_LINE + } } - inserted += ins; + processed += ins + skip; di += ins; // everything inserted? - if (inserted == n) return inserted; + if (processed == n) { + return processed; + } src = next; } // insert remaining items if (si < n) { - inserted += invoke_list_func(insert_array, list, di, src, n - si); + if (allow_duplicates) { + processed += invoke_list_func(insert_array, list, di, src, n - si); + } else { + const void *last = di == 0 ? NULL : invoke_list_func(at, list, di - 1); + for (; si < n; si++) { + // skip duplicates within the source + if (last == NULL || cmp(last, src) != 0) { + if (NULL == invoke_list_func(insert_element, list, di, src)) { + return processed; // LCOV_EXCL_LINE + } + last = src; + di++; + } + processed++; + src += elem_size; + } + } } - return inserted; + return processed; +} + +size_t cx_list_default_insert_sorted( + struct cx_list_s *list, + const void *sorted_data, + size_t n +) { + return cx_list_default_insert_sorted_impl(list, sorted_data, n, true); +} + +size_t cx_list_default_insert_unique( + struct cx_list_s *list, + const void *sorted_data, + size_t n +) { + return cx_list_default_insert_sorted_impl(list, sorted_data, n, false); } 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 = cxMallocDefault(elem_size * list_size); - if (tmp == NULL) abort(); + if (tmp == NULL) abort(); // LCOV_EXCL_LINE // copy elements from source array char *loc = tmp; @@ -388,7 +482,7 @@ size_t elem_size = list->collection.elem_size; void *tmp = cxMallocDefault(elem_size); - if (tmp == NULL) return 1; + if (tmp == NULL) return 1; // LCOV_EXCL_LINE void *ip = invoke_list_func(at, list, i); void *jp = invoke_list_func(at, list, j); @@ -476,6 +570,7 @@ CxList *list, size_t index ) { + if (list == NULL) list = cxEmptyList; CxIterator it = list->cl->iterator(list, index, false); it.base.mutating = true; return it; @@ -485,6 +580,7 @@ CxList *list, size_t index ) { + if (list == NULL) list = cxEmptyList; CxIterator it = list->cl->iterator(list, index, true); it.base.mutating = true; return it;