ucx: comparison src/array

-:5e1579713bcf
+:e46406fd1b3c
 // 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
 );
+// handle the identical elements
+size_t skip_len = 0;
+while (copy_len < elem_count - si
+&& cmp_func(bptr, src+copy_len*elem_size) == 0) {
+copy_len++;
+if (!allow_duplicates) {
+skip_len++;
+}
+}
+copy_len -= skip_len;
 // copy the source elements
 bytes_copied = copy_len * elem_size;
 memcpy(dest, src, bytes_copied);
 dest += bytes_copied;
 src += bytes_copied;
 si += copy_len;
+di += copy_len;
+// skip duplicates when they are not allowed
+src += skip_len * elem_size;
+si += skip_len;
+*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;
+// check if the last restored element is a duplicate of the next source
+if (!allow_duplicates && copy_len > 0) {
+char *last = dest - elem_size;
+while (si < elem_count && cmp_func(last, src) == 0) {
+src += elem_size;
+si++;
+(*size)--;
+}
+}
 }
 // still source elements left? simply append them
 if (si < elem_count) {
 memcpy(dest, src, elem_size * (elem_count - si));
 }
-// still buffer elements left?
+// buffered elements need to be moved when we skipped duplicates
-// don't worry, we already moved them to the correct place
+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 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: src/array_list.c

src/array_list.c

Mercurial > hg > ucx / file comparison

comparison: src/array_list.c

src/array_list.c