dbutils: comparison ucx/array

-:112b85020dc9
+:b26390e77237
 size_t new_capacity,
 size_t elem_size,
 cx_attr_unused CxArrayReallocator *alloc
 ) {
 size_t n;
+// LCOV_EXCL_START
 if (cx_szmul(new_capacity, elem_size, &n)) {
 errno = EOVERFLOW;
 return NULL;
-}
+} // LCOV_EXCL_STOP
 return cxReallocDefault(array, n);
 }
 CxArrayReallocator cx_array_default_reallocator_impl = {
 cx_array_default_realloc, NULL, NULL
 size_t elem_size,
 cx_attr_unused CxArrayReallocator *alloc
 ) {
 // check for overflow
 size_t n;
+// LCOV_EXCL_START
 if (cx_szmul(new_capacity, elem_size, &n)) {
 errno = EOVERFLOW;
 return NULL;
-}
+} // LCOV_EXCL_STOP
 // retrieve the pointer to the actual allocator
 const CxAllocator *al = alloc->allocator;
 // check if the array is still located on the stack
 * Intelligently calculates a new capacity, reserving some more
 * elements than required to prevent too many allocations.
 *
 * @param current_capacity the current capacity of the array
 * @param needed_capacity the required capacity of the array
-* @param maximum_capacity the maximum capacity (given by the data type)
 * @return the new capacity
 */
 static size_t cx_array_grow_capacity(
 size_t current_capacity,
-size_t needed_capacity,
+size_t needed_capacity
-size_t maximum_capacity
 ) {
 if (current_capacity >= needed_capacity) {
 return current_capacity;
 }
 size_t cap = needed_capacity;
 size_t alignment;
 if (cap < 128) alignment = 16;
 else if (cap < 1024) alignment = 64;
 else if (cap < 8192) alignment = 512;
 else alignment = 1024;
+return cap - (cap % alignment) + alignment;
-if (cap - 1 > maximum_capacity - alignment) {
-return maximum_capacity;
-} else {
-return cap - (cap % alignment) + alignment;
-}
 }
 int cx_array_reserve(
 void **array,
 void *size,
 // check if resize is required
 const size_t minsize = index + elem_count;
 const size_t newsize = oldsize < minsize ? minsize : oldsize;
 // reallocate if necessary
-const size_t newcap = cx_array_grow_capacity(oldcap, newsize, max_size);
+const size_t newcap = cx_array_grow_capacity(oldcap, newsize);
 if (newcap > oldcap) {
 // check if we need to repair the src pointer
 uintptr_t targetaddr = (uintptr_t) *target;
 uintptr_t srcaddr = (uintptr_t) src;
 bool repairsrc = targetaddr <= srcaddr
 // corner case
 if (elem_count == 0) return 0;
 // overflow check
+// LCOV_EXCL_START
 if (elem_count > SIZE_MAX - *size) {
 errno = EOVERFLOW;
 return 1;
 }
+// LCOV_EXCL_STOP
 // store some counts
 const size_t old_size = *size;
 const size_t old_capacity = *capacity;
 // the necessary capacity is the worst case assumption, including duplicates
-const size_t needed_capacity = cx_array_grow_capacity(old_capacity,
+const size_t needed_capacity = cx_array_grow_capacity(old_capacity, old_size + elem_count);
-old_size + elem_count, SIZE_MAX);
 // if we need more than we have, try a reallocation
 if (needed_capacity > old_capacity) {
 void *new_mem = reallocator->realloc(
 *target, old_capacity, needed_capacity, elem_size, reallocator
 memmove(bptr, dest, buf_size * elem_size);
 // while there are both source and buffered elements left,
 // copy them interleaving
 while (si < elem_count && bi < new_size) {
-// determine how many source elements can be inserted
+// determine how many source elements can be inserted.
+// the first element that shall not be inserted is the smallest element
+// that is strictly larger than the first buffered element
+// (located at the index of the infimum plus one).
+// the infimum is guaranteed to exist:
+// - if all src elements are larger,
+//   there is no buffer, and this loop is skipped
+// - if any src element is smaller or equal, the infimum exists
+// - when all src elements that are smaller are copied, the second part
+//   of this loop body will copy the remaining buffer (emptying it)
+// Therefore, the buffer can never contain an element that is smaller
+// than any element in the source and the infimum exists.
 size_t copy_len, bytes_copied;
-copy_len = cx_array_binary_search_sup(
+copy_len = cx_array_binary_search_inf(
-src,
+src, elem_count - si, elem_size, bptr, cmp_func
-elem_count - si,
-elem_size,
-bptr,
-cmp_func
 );
-// binary search gives us the smallest index;
+copy_len++;
-// 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
 if (copy_len > 0) {
 if (allow_duplicates) {
 // we can copy the entire chunk
 if (si < elem_count) {
 if (allow_duplicates) {
 // duplicates allowed or nothing inserted yet: simply copy everything
 memcpy(dest, src, elem_size * (elem_count - si));
 } else {
-if (dest != *target) {
+// we must check the remaining source elements one by one
-// skip all source elements that equal the last element
+// to skip the duplicates.
-char *last = dest - elem_size;
+// Note that no source element can equal the last element in the
-while (si < elem_count) {
+// destination, because that would have created an insertion point
-if (last != NULL && cmp_func(last, src) == 0) {
+// and a buffer, s.t. the above loop already handled the duplicates
-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) {
+while (si + copy_len + skip_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;
 ) {
 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(
+// implementation that finds ANY index
+static size_t cx_array_binary_search_inf_impl(
 const void *arr,
 size_t size,
 size_t elem_size,
 const void *elem,
 cx_compare_func cmp_func
 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 {
 }
 }
 // report the largest upper bound
 return result < 0 ? (pivot_index - 1) : pivot_index;
+}
+size_t cx_array_binary_search_inf(
+const void *arr,
+size_t size,
+size_t elem_size,
+const void *elem,
+cx_compare_func cmp_func
+) {
+size_t index = cx_array_binary_search_inf_impl(
+arr, size, elem_size, elem, cmp_func);
+// in case of equality, report the largest index
+const char *e = ((const char *) arr) + (index + 1) * elem_size;
+while (index + 1 < size && cmp_func(e, elem) == 0) {
+e += elem_size;
+index++;
+}
+return index;
 }
 size_t cx_array_binary_search(
 const void *arr,
 size_t size,
 size_t size,
 size_t elem_size,
 const void *elem,
 cx_compare_func cmp_func
 ) {
-size_t inf = cx_array_binary_search_inf(
+size_t index = cx_array_binary_search_inf_impl(
 arr, size, elem_size, elem, cmp_func
 );
-if (inf == size) {
+const char *e = ((const char *) arr) + index * elem_size;
-// no infimum means, first element is supremum
+if (index == size) {
+// no infimum means the first element is supremum
 return 0;
-} else if (cmp_func(((const char *) arr) + inf * elem_size, elem) == 0) {
+} else if (cmp_func(e, elem) == 0) {
-return inf;
+// found an equal element, search the smallest index
+e -= elem_size; // e now contains the element at index-1
+while (index > 0 && cmp_func(e, elem) == 0) {
+e -= elem_size;
+index--;
+}
+return index;
 } else {
-return inf + 1;
+// we already have the largest index of the infimum (by design)
+// the next element is the supremum (or there is no supremum)
+return index + 1;
 }
 }
 #ifndef CX_ARRAY_SWAP_SBO_SIZE
 #define CX_ARRAY_SWAP_SBO_SIZE 128
 // get a correctly typed pointer to the list
 cx_array_list *arl = (cx_array_list *) list;
 // guarantee enough capacity
 if (arl->capacity < list->collection.size + n) {
-const size_t new_capacity = cx_array_grow_capacity(arl->capacity,
+const size_t new_capacity = cx_array_grow_capacity(arl->capacity,list->collection.size + n);
-list->collection.size + n, SIZE_MAX);
 if (cxReallocateArray(
 list->collection.allocator,
 &arl->data, new_capacity,
 list->collection.elem_size)
 ) {
-return 0;
+return 0; // LCOV_EXCL_LINE
 }
 arl->capacity = new_capacity;
 }
 // determine insert position
 list->collection.elem_size,
 n,
 &arl->reallocator
 )) {
 // array list implementation is "all or nothing"
-return 0;
+return 0;  // LCOV_EXCL_LINE
 } else {
 return n;
 }
 }
 list->collection.elem_size,
 n,
 &arl->reallocator
 )) {
 // array list implementation is "all or nothing"
-return 0;
+return 0;  // LCOV_EXCL_LINE
 } else {
 return n;
 }
 }
 ) {
 struct cx_list_s *list = iter->src_handle;
 if (iter->index < list->collection.size) {
 if (cx_arl_insert_element(list,
 iter->index + 1 - prepend, elem) == NULL) {
-return 1;
+return 1; // LCOV_EXCL_LINE
 }
 iter->elem_count++;
 if (prepend != 0) {
 iter->index++;
 iter->elem_handle = ((char *) iter->elem_handle) + list->collection.elem_size;
 }
 return 0;
 } else {
 if (cx_arl_insert_element(list, list->collection.size, elem) == NULL) {
-return 1;
+return 1;  // LCOV_EXCL_LINE
 }
 iter->elem_count++;
 iter->index = list->collection.size;
 return 0;
 }

comparison: ucx/array_list.c

ucx/array_list.c

Mercurial > hg > dbutils / file comparison

comparison: ucx/array_list.c

ucx/array_list.c