ucx: comparison src/array

-:d4385f35f8b0
+:ef7cab6eb131
 array->size += n;
 return 0;
 }
-int cx_array_insert_sorted_(
+int cx_array_insert_sorted_s_(
 const CxAllocator *allocator,
 CxArray *array,
 size_t elem_size,
-cx_compare_func cmp_func,
 const void *sorted_data,
 size_t n,
-bool allow_duplicates
+bool allow_duplicates,
+cx_compare_func2 cmp_func,
+void *context
 ) {
 // assert pointers
 assert(allocator != NULL);
 assert(array != NULL);
 assert(cmp_func != NULL);
 size_t si = 0, di = 0;
 const char *src = sorted_data;
 char *dest = array->data;
 // find the first insertion point
-di = cx_array_binary_search_sup(dest, old_size, elem_size, src, cmp_func);
+di = cx_array_binary_search_sup_c(dest, old_size, elem_size, src, cmp_func, context);
 dest += di * elem_size;
 // move the remaining elements in the array completely to the right
 // we will call it the "buffer" for parked elements
 size_t buf_size = old_size - di;
 // - 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_inf(
+copy_len = cx_array_binary_search_inf_c(
-src, n - si, elem_size, bptr, cmp_func
+src, n - si, elem_size, bptr, cmp_func, context
 );
 copy_len++;
 // copy the source elements
 if (copy_len > 0) {
 } 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) {
+while (copy_len > 0 && cmp_func(bptr, end_of_src, context) == 0) {
 end_of_src -= elem_size;
 skip_len++;
 copy_len--;
 }
 char *last = dest == array->data ? 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) {
+if (last != NULL && cmp_func(last, src, context) == 0) {
 // duplicate - skip
 src += elem_size;
 si++;
 more_skipped++;
 } else {
 // when all source elements are in place, we are done
 if (si >= n) break;
 // determine how many buffered elements need to be restored
-copy_len = cx_array_binary_search_sup(
+copy_len = cx_array_binary_search_sup_c(
 bptr,
 new_size - bi,
 elem_size,
 src,
-cmp_func
+cmp_func,
+context
 );
 // restore the buffered elements
 bytes_copied = copy_len * elem_size;
 memmove(dest, bptr, bytes_copied);
 size_t copy_len = 1, skip_len = 0;
 {
 const char *left_src = src;
 while (si + copy_len + skip_len < n) {
 const char *right_src = left_src + elem_size;
-int d = cmp_func(left_src,  right_src);
+int d = cmp_func(left_src,  right_src, context);
 if (d < 0) {
 if (skip_len > 0) {
 // new larger element found;
 // handle it in the next cycle
 break;
 }
 return 0;
 }
+int cx_array_insert_sorted_(
+const CxAllocator *allocator,
+CxArray *array,
+size_t elem_size,
+cx_compare_func cmp_func,
+const void *sorted_data,
+size_t n,
+bool allow_duplicates
+) {
+cx_compare_func_wrapper wrapper = {cmp_func};
+return cx_array_insert_sorted_s_(allocator, array, elem_size, sorted_data,
+n, allow_duplicates, cx_acmp_wrap, &wrapper);
+}
 CxIterator cx_array_iterator_(CxArray *array, size_t elem_size) {
 return cxIterator(array->data, elem_size, array->size);
 }
 CxIterator cx_array_iterator_ptr_(CxArray *array) {
 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
+cx_compare_func2 cmp_func,
+void *context
 ) {
 // special case: empty array
 if (size == 0) return 0;
 // declare a variable that will contain the compare results
 // cast the array pointer to something we can use offsets with
 const char *array = arr;
 // check the first array element
-result = cmp_func(elem, array);
+result = cmp_func(elem, array, context);
 if (result < 0) {
 return size;
 } else if (result == 0) {
 return 0;
 }
 // special case: there is only one element and that is smaller
 if (size == 1) return 0;
 // check the last array element
-result = cmp_func(elem, array + elem_size * (size - 1));
+result = cmp_func(elem, array + elem_size * (size - 1), context);
 if (result >= 0) {
 return size - 1;
 }
 // the element is now guaranteed to be somewhere in the list
 // so start the binary search
 size_t left_index = 1;
 size_t right_index = size - 1;
-size_t pivot_index;
+size_t pivot_index = 0;
 while (left_index <= right_index) {
 pivot_index = left_index + (right_index - left_index) / 2;
 const char *arr_elem = array + pivot_index * elem_size;
-result = cmp_func(elem, arr_elem);
+result = cmp_func(elem, arr_elem, context);
 if (result == 0) {
 // found it!
 return pivot_index;
 } else if (result < 0) {
 // element is smaller than pivot, continue search left
 // report the largest upper bound
 return result < 0 ? (pivot_index - 1) : pivot_index;
 }
+size_t cx_array_binary_search_inf_c(
+const void *arr,
+size_t size,
+size_t elem_size,
+const void *elem,
+cx_compare_func2 cmp_func,
+void *context
+) {
+size_t index = cx_array_binary_search_inf_impl(
+arr, size, elem_size, elem, cmp_func, context);
+// 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, context) == 0) {
+e += elem_size;
+index++;
+}
+return index;
+}
+size_t cx_array_binary_search_c(
+const void *arr,
+size_t size,
+size_t elem_size,
+const void *elem,
+cx_compare_func2 cmp_func,
+void *context
+) {
+size_t index = cx_array_binary_search_inf_c(
+arr, size, elem_size, elem, cmp_func, context
+);
+if (index < size && cmp_func(((const char *) arr) + index * elem_size,
+elem, context) == 0) {
+return index;
+} else {
+return size;
+}
+}
+size_t cx_array_binary_search_sup_c(
+const void *arr,
+size_t size,
+size_t elem_size,
+const void *elem,
+cx_compare_func2 cmp_func,
+void *context
+) {
+size_t index = cx_array_binary_search_inf_impl(
+arr, size, elem_size, elem, cmp_func, context
+);
+const char *e = ((const char *) arr) + index * elem_size;
+if (index == size) {
+// no infimum means the first element is supremum
+return 0;
+} else if (cmp_func(e, elem, context) == 0) {
+// 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, context) == 0) {
+e -= elem_size;
+index--;
+}
+return index;
+} else {
+// 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;
+}
+}
 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(
+cx_compare_func_wrapper wrapper = {cmp_func};
-arr, size, elem_size, elem, cmp_func);
+return cx_array_binary_search_inf_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper);
-// 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 elem_size,
 const void *elem,
 cx_compare_func cmp_func
 ) {
-size_t index = cx_array_binary_search_inf(
+cx_compare_func_wrapper wrapper = {cmp_func};
-arr, size, elem_size, elem, cmp_func
+return cx_array_binary_search_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper);
-);
-if (index < size &&
-cmp_func(((const char *) arr) + index * elem_size, elem) == 0) {
-return index;
-} else {
-return size;
-}
 }
 size_t cx_array_binary_search_sup(
 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(
+cx_compare_func_wrapper wrapper = {cmp_func};
-arr, size, elem_size, elem, cmp_func
+return cx_array_binary_search_sup_c(arr, size, elem_size, elem, cx_acmp_wrap, &wrapper);
-);
-const char *e = ((const char *) arr) + index * elem_size;
-if (index == size) {
-// no infimum means the first element is supremum
-return 0;
-} else if (cmp_func(e, elem) == 0) {
-// 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 {
-// 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
 #endif
 cx_array_list *arl = (cx_array_list *) list;
 CxArray wrap = {
 arl->data, list->collection.size, arl->capacity
 };
-if (cx_array_insert_sorted_(
+if (cx_array_insert_sorted_s_(
 list->collection.allocator,
 &wrap,
 list->collection.elem_size,
-list->collection.cmpfunc,
 sorted_data,
 n,
-allow_duplicates
+allow_duplicates,
+cx_list_compare_wrapper,
+list
 )) {
 // array list implementation is "all or nothing"
 return 0;  // LCOV_EXCL_LINE
 }
 arl->data = wrap.data;
 struct cx_list_s *list,
 const void *elem,
 bool remove
 ) {
 assert(list != NULL);
-assert(list->collection.cmpfunc != NULL);
 if (list->collection.size == 0) return 0;
 char *cur = ((const cx_array_list *) list)->data;
 // optimize with binary search, when sorted
 if (list->collection.sorted) {
-size_t i = cx_array_binary_search(
+size_t i = cx_array_binary_search_c(
 cur,
 list->collection.size,
 list->collection.elem_size,
 elem,
-list->collection.cmpfunc
+cx_list_compare_wrapper,
+list
 );
 if (remove && i < list->collection.size) {
 cx_arl_remove(list, i, 1, NULL);
 }
 return i;
 }
 // fallback: linear search
 for (size_t i = 0; i < list->collection.size; i++) {
-if (0 == list->collection.cmpfunc(elem, cur)) {
+if (0 == cx_list_compare_wrapper(elem, cur, list)) {
 if (remove) {
 cx_arl_remove(list, i, 1, NULL);
 }
 return i;
 }
 cur += list->collection.elem_size;
 }
 return list->collection.size;
 }
+// TODO: remove this hack once we have a solution for qsort() / qsort_s()
+static _Thread_local CxList *cx_hack_for_qsort_list;
+static int cx_hack_cmp_for_qsort(const void *l, const void *r) {
+return cx_list_compare_wrapper(l, r, cx_hack_for_qsort_list);
+}
 static void cx_arl_sort(struct cx_list_s *list) {
-assert(list->collection.cmpfunc != NULL);
+// TODO: think about if we can somehow use qsort()_s
+cx_hack_for_qsort_list = list;
 qsort(((cx_array_list *) list)->data,
 list->collection.size,
 list->collection.elem_size,
-list->collection.cmpfunc
+cx_hack_cmp_for_qsort
 );
 }
 static int cx_arl_compare(
 const struct cx_list_s *list,
 const struct cx_list_s *other
 ) {
-assert(list->collection.cmpfunc != NULL);
 if (list->collection.size == other->collection.size) {
 const char *left = ((const cx_array_list *) list)->data;
 const char *right = ((const cx_array_list *) other)->data;
 for (size_t i = 0; i < list->collection.size; i++) {
-int d = list->collection.cmpfunc(left, right);
+int d = cx_list_compare_wrapper(left, right, (void*)list);
 if (d != 0) {
 return d;
 }
 left += list->collection.elem_size;
 right += other->collection.elem_size;

comparison: src/array_list.c

src/array_list.c

Mercurial > hg > ucx / file comparison

comparison: src/array_list.c

src/array_list.c