ucx: comparison src/array

-:f8ca6e6c0d48
+:3012e9b4214e
 // return successfully
 return CX_ARRAY_SUCCESS;
 }
+enum cx_array_result cx_array_insert_sorted(
+void **target,
+size_t *size,
+size_t *capacity,
+cx_compare_func cmp_func,
+void const *sorted_data,
+size_t elem_size,
+size_t elem_count,
+struct cx_array_reallocator_s *reallocator
+) {
+// assert pointers
+assert(target != NULL);
+assert(size != NULL);
+assert(capacity != NULL);
+assert(cmp_func != NULL);
+assert(sorted_data != NULL);
+assert(reallocator != NULL);
+// corner case
+if (elem_count == 0) return 0;
+// store some counts
+size_t old_size = *size;
+size_t needed_capacity = old_size + elem_count;
+// if we need more than we have, try a reallocation
+if (needed_capacity > *capacity) {
+size_t new_capacity = needed_capacity - (needed_capacity % 16) + 16;
+void *new_mem = reallocator->realloc(
+*target, new_capacity, elem_size, reallocator
+);
+if (new_mem == NULL) {
+// give it up right away, there is no contract
+// that requires us to insert as much as we can
+return CX_ARRAY_REALLOC_FAILED;
+}
+*target = new_mem;
+*capacity = new_capacity;
+}
+// now we have guaranteed that we can insert everything
+size_t new_size = old_size + elem_count;
+*size = new_size;
+// declare the source and destination indices/pointers
+size_t si = 0, di = 0;
+char const *src = sorted_data;
+char *dest = *target;
+// find the first insertion point
+while (di < old_size) {
+if (cmp_func(src, dest) < 0) {
+break;
+}
+di++;
+dest += 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;
+size_t bi = new_size - buf_size;
+char *bptr = ((char *) *target) + bi * elem_size;
+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
+size_t copy_len = 1;
+si++;
+char const *next_src = src + elem_size;
+while (si < elem_count) {
+if (cmp_func(bptr, next_src) < 0) {
+break;
+}
+copy_len++;
+si++;
+next_src += elem_size;
+}
+// copy the source elements
+memcpy(dest, src, copy_len * elem_size);
+dest += copy_len * elem_size;
+src = next_src;
+// determine how many buffered elements need to be restored
+copy_len = 1;
+bi++;
+char *next_bptr = bptr + elem_size;
+while (bi < new_size) {
+if (cmp_func(src, next_bptr) < 0) {
+break;
+}
+copy_len++;
+bi++;
+next_bptr += elem_size;
+}
+// restore the buffered elements
+memmove(dest, bptr, copy_len * elem_size);
+dest += copy_len * elem_size;
+bptr = next_bptr;
+}
+// still source elements left? simply append them
+if (si < elem_count) {
+memcpy(dest, src, elem_size * (elem_count - si));
+}
+// still buffer elements left?
+// don't worry, we already moved them to the correct place
+return CX_ARRAY_SUCCESS;
+}
 #ifndef CX_ARRAY_SWAP_SBO_SIZE
 #define CX_ARRAY_SWAP_SBO_SIZE 128
 #endif
 unsigned cx_array_swap_sbo_size = CX_ARRAY_SWAP_SBO_SIZE;
 static size_t cx_arl_insert_sorted(
 struct cx_list_s *list,
 void const *sorted_data,
 size_t n
 ) {
-// corner case
+// get a correctly typed pointer to the list
-if (n == 0) return 0;
-// define some handy pointers
 cx_array_list *arl = (cx_array_list *) list;
-cx_compare_func cmp = list->collection.cmpfunc;
+if (CX_ARRAY_SUCCESS == cx_array_insert_sorted(
-// store some counts
+&arl->data,
-size_t old_size = list->collection.size;
+&list->collection.size,
-size_t capacity = arl->capacity;
+&arl->capacity,
-size_t needed_capacity = old_size + n;
+list->collection.cmpfunc,
-size_t elem_size = list->collection.elem_size;
+sorted_data,
+list->collection.elem_size,
-// if we need more than we have, try a reallocation
+n,
-if (needed_capacity > capacity) {
+&arl->reallocator
-capacity = needed_capacity - (needed_capacity % 16) + 16;
+)) {
-if (0 != cxReallocate(list->collection.allocator,
+return n;
-&(arl->data),
+} else {
-capacity * elem_size)) {
+// array list implementation is "all or nothing"
-// give it up right away, there is no contract
+return 0;
-// that requires us to insert as much as we can
+}
-return 0;
-}
-arl->capacity = capacity;
-}
-// now we have guaranteed that we can insert everything
-size_t new_size = list->collection.size + n;
-list->collection.size = new_size;
-// declare the source and destination indices/pointers
-size_t si = 0, di = 0;
-char const *src = sorted_data;
-char *dest = arl->data;
-// find the first insertion point
-while (di < old_size) {
-if (cmp(src, dest) < 0) {
-break;
-}
-di++;
-dest += 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;
-size_t bi = new_size - buf_size;
-char *bptr = ((char *) arl->data) + bi * elem_size;
-memmove(bptr, dest, buf_size * elem_size);
-// while there are both source and buffered elements left,
-// copy them interleaving
-while (si < n && bi < new_size) {
-// determine how many source elements can be inserted
-size_t copy_len = 1;
-si++;
-char const *next_src = src + elem_size;
-while (si < n) {
-if (cmp(bptr, next_src) < 0) {
-break;
-}
-copy_len++;
-si++;
-next_src += elem_size;
-}
-// copy the source elements
-memcpy(dest, src, copy_len * elem_size);
-dest += copy_len * elem_size;
-src = next_src;
-// determine how many buffered elements need to be restored
-copy_len = 1;
-bi++;
-char *next_bptr = bptr + elem_size;
-while (bi < new_size) {
-if (cmp(src, next_bptr) < 0) {
-break;
-}
-copy_len++;
-bi++;
-next_bptr += elem_size;
-}
-// restore the buffered elements
-memmove(dest, bptr, copy_len * elem_size);
-dest += copy_len * elem_size;
-bptr = next_bptr;
-}
-// still source elements left? simply append them
-if (si < n) {
-memcpy(dest, src, elem_size * (n - si));
-}
-// still buffer elements left?
-// don't worry, we already moved them to the correct place
-return n;
 }
 static int cx_arl_insert_element(
 struct cx_list_s *list,
 size_t index,

comparison: src/array_list.c

src/array_list.c

Mercurial > hg > ucx / file comparison

comparison: src/array_list.c

src/array_list.c