idav: comparison ucx/array

-:81c4f73236a4
+:c3f2f16fa4b8
 // perform reallocation
 void *newmem = reallocator->realloc(
 *target, oldcap, newcap, elem_size, reallocator
 );
 if (newmem == NULL) {
-return 1;
+return 1; // LCOV_EXCL_LINE
 }
 // repair src pointer, if necessary
 if (repairsrc) {
 src = ((char *) newmem) + (srcaddr - targetaddr);
 // return successfully
 return 0;
 }
-int cx_array_insert_sorted(
+static int cx_array_insert_sorted_impl(
 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,
-CxArrayReallocator *reallocator
+CxArrayReallocator *reallocator,
+bool allow_duplicates
 ) {
 // assert pointers
 assert(target != NULL);
 assert(size != NULL);
 assert(capacity != NULL);
 }
 // store some counts
 size_t old_size = *size;
 size_t old_capacity = *capacity;
+// the necessary capacity is the worst case assumption, including duplicates
 size_t needed_capacity = old_size + elem_count;
 // if we need more than we have, try a reallocation
 if (needed_capacity > old_capacity) {
 size_t new_capacity = cx_array_align_capacity(needed_capacity, 16, SIZE_MAX);
 elem_count - si,
 elem_size,
 bptr,
 cmp_func
 );
+// binary search gives us the smallest index;
+// we also want to include equal elements here
+while (si + copy_len < elem_count
+&& cmp_func(bptr, src+copy_len*elem_size) == 0) {
+copy_len++;
+}
 // copy the source elements
-bytes_copied = copy_len * elem_size;
+if (copy_len > 0) {
-memcpy(dest, src, bytes_copied);
+if (allow_duplicates) {
-dest += bytes_copied;
+// we can copy the entire chunk
-src += bytes_copied;
+bytes_copied = copy_len * elem_size;
-si += copy_len;
+memcpy(dest, src, bytes_copied);
+dest += bytes_copied;
+src += bytes_copied;
+si += copy_len;
+di += copy_len;
+} else {
+// first, check the end of the source chunk
+// for being a duplicate of the bptr
+const char *end_of_src = src + (copy_len - 1) * elem_size;
+size_t skip_len = 0;
+while (copy_len > 0 && cmp_func(bptr, end_of_src) == 0) {
+end_of_src -= elem_size;
+skip_len++;
+copy_len--;
+}
+char *last = dest == *target ? NULL : dest - elem_size;
+// then iterate through the source chunk
+// and skip all duplicates with the last element in the array
+size_t more_skipped = 0;
+for (unsigned j = 0; j < copy_len; j++) {
+if (last != NULL && cmp_func(last, src) == 0) {
+// duplicate - skip
+src += elem_size;
+si++;
+more_skipped++;
+} else {
+memcpy(dest, src, elem_size);
+src += elem_size;
+last = dest;
+dest += elem_size;
+si++;
+di++;
+}
+}
+// skip the previously identified elements as well
+src += skip_len * elem_size;
+si += skip_len;
+skip_len += more_skipped;
+// reduce the actual size by the number of skipped elements
+*size -= skip_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
 // restore the buffered elements
 bytes_copied = copy_len * elem_size;
 memmove(dest, bptr, bytes_copied);
 dest += bytes_copied;
 bptr += bytes_copied;
+di += copy_len;
 bi += copy_len;
 }
-// still source elements left? simply append them
+// still source elements left?
 if (si < elem_count) {
-memcpy(dest, src, elem_size * (elem_count - si));
+if (allow_duplicates) {
-}
+// duplicates allowed or nothing inserted yet: simply copy everything
+memcpy(dest, src, elem_size * (elem_count - si));
-// still buffer elements left?
+} else {
-// don't worry, we already moved them to the correct place
+if (dest != *target) {
+// skip all source elements that equal the last element
+char *last = dest - elem_size;
+while (si < elem_count) {
+if (last != NULL && cmp_func(last, src) == 0) {
+src += elem_size;
+si++;
+(*size)--;
+} else {
+break;
+}
+}
+}
+// we must check the elements in the chunk one by one
+while (si < elem_count) {
+// find a chain of elements that can be copied
+size_t copy_len = 1, skip_len = 0;
+{
+const char *left_src = src;
+while (si + copy_len < elem_count) {
+const char *right_src = left_src + elem_size;
+int d = cmp_func(left_src,  right_src);
+if (d < 0) {
+if (skip_len > 0) {
+// new larger element found;
+// handle it in the next cycle
+break;
+}
+left_src += elem_size;
+copy_len++;
+} else if (d == 0) {
+left_src += elem_size;
+skip_len++;
+} else {
+break;
+}
+}
+}
+size_t bytes_copied = copy_len * elem_size;
+memcpy(dest, src, bytes_copied);
+dest += bytes_copied;
+src += bytes_copied + skip_len * elem_size;
+si += copy_len + skip_len;
+di += copy_len;
+*size -= skip_len;
+}
+}
+}
+// buffered elements need to be moved when we skipped duplicates
+size_t total_skipped = new_size - *size;
+if (bi < new_size && total_skipped > 0) {
+// move the remaining buffer to the end of the array
+memmove(dest, bptr, elem_size * (new_size - bi));
+}
 return 0;
+}
+int 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,
+CxArrayReallocator *reallocator
+) {
+return cx_array_insert_sorted_impl(target, size, capacity,
+cmp_func, sorted_data, elem_size, elem_count, reallocator, true);
+}
+int cx_array_insert_unique(
+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,
+CxArrayReallocator *reallocator
+) {
+return cx_array_insert_sorted_impl(target, size, capacity,
+cmp_func, sorted_data, elem_size, elem_count, reallocator, false);
 }
 size_t cx_array_binary_search_inf(
 const void *arr,
 size_t size,
 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!
+// check previous elements;
+// when they are equal, report the smallest index
+arr_elem -= elem_size;
+while (pivot_index > 0 && cmp_func(elem, arr_elem) == 0) {
+pivot_index--;
+arr_elem -= elem_size;
+}
 return pivot_index;
 } else if (result < 0) {
 // element is smaller than pivot, continue search left
 right_index = pivot_index - 1;
 } else {
 } else {
 return n;
 }
 }
+static size_t cx_arl_insert_unique(
+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_insert_unique(
+&arl->data,
+&list->collection.size,
+&arl->capacity,
+list->collection.cmpfunc,
+sorted_data,
+list->collection.elem_size,
+n,
+&arl->reallocator
+)) {
+// array list implementation is "all or nothing"
+return 0;
+} else {
+return n;
+}
+}
 static void *cx_arl_insert_element(
 struct cx_list_s *list,
 size_t index,
 const void *element
 ) {
 static void cx_arl_iter_next(void *it) {
 struct cx_iterator_s *iter = it;
 if (iter->base.remove) {
 iter->base.remove = false;
 cx_arl_remove(iter->src_handle.m, iter->index, 1, NULL);
+iter->elem_count--;
 } else {
 iter->index++;
 iter->elem_handle =
 ((char *) iter->elem_handle)
 + ((const struct cx_list_s *) iter->src_handle.c)->collection.elem_size;
 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, 1, NULL);
+iter->elem_count--;
 }
 iter->index--;
 if (iter->index < list->base.collection.size) {
 iter->elem_handle = ((char *) list->data)
 + iter->index * list->base.collection.elem_size;
 static cx_list_class cx_array_list_class = {
 cx_arl_destructor,
 cx_arl_insert_element,
 cx_arl_insert_array,
 cx_arl_insert_sorted,
+cx_arl_insert_unique,
 cx_arl_insert_iter,
 cx_arl_remove,
 cx_arl_clear,
 cx_arl_swap,
 cx_arl_at,

comparison: ucx/array_list.c

ucx/array_list.c

Mercurial > hg > idav / file comparison

comparison: ucx/array_list.c

ucx/array_list.c