changeset
implements ucx_array_sort()
Thu, 04 Jul 2019 22:23:15 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Thu, 04 Jul 2019 22:23:15 +0200
- branch
- feature/array
- changeset 336
- 6d7aa8a1a3b3
- parent 335
- 872ae61c8945
- child 337
- f695ae118460
implements ucx_array_sort()
| src/array.c | file | annotate | diff | comparison | revisions | |
| src/ucx/array.h | file | annotate | diff | comparison | revisions | |
| test/array_tests.c | file | annotate | diff | comparison | revisions |
--- a/src/array.c Thu Jul 04 21:31:45 2019 +0200 +++ b/src/array.c Thu Jul 04 22:23:15 2019 +0200 @@ -27,7 +27,9 @@ */ #include "ucx/array.h" +#include "ucx/utils.h" +#include <string.h> UcxArray ucx_array_new(size_t capacity, size_t elemsize) { return ucx_array_new_a(capacity, elemsize, ucx_default_allocator()); @@ -37,71 +39,278 @@ UcxAllocator* allocator) { UcxArray array; + array.allocator = allocator; + array.elemsize = elemsize; + array.size = 0; + array.data = alcalloc(allocator, capacity, elemsize); + + if (array.data) { + array.capacity = capacity; + } else { + array.capacity = 0; + } + return array; } UcxArray ucx_array_clone(UcxArray array) { UcxArray clone; + clone.allocator = array.allocator; + clone.elemsize = array.elemsize; + clone.size = array.size; + clone.data = alcalloc(array.allocator, array.capacity, array.elemsize); + + if (clone.data) { + clone.capacity = array.capacity; + memcpy(clone.data, array.data, array.size*array.elemsize); + } else { + clone.capacity = clone.size = 0; + } + return clone; } int ucx_array_equals(UcxArray array1, UcxArray array2, cmp_func cmpfnc, void* data) { - return 1; + if (array1.size != array2.size || array1.elemsize != array2.elemsize) { + return 0; + } else { + if (array1.size == 0) + return 1; + + if (cmpfnc == NULL) { + cmpfnc = ucx_cmp_mem; + data = &array1.elemsize; + } + + for (size_t i = 0 ; i < array1.size ; i++) { + int r = cmpfnc( + ucx_array_at(array1, i), + ucx_array_at(array2, i), + data); + if (r != 0) + return 0; + } + return 1; + } } void ucx_array_free(UcxArray *array) { - + alfree(array->allocator, array->data); + array->data = NULL; + array->capacity = array->size = 0; } int ucx_array_append(UcxArray *array, void *data) { - return 1; + if (array->size == array->capacity) { + if (ucx_array_reserve(array, array->capacity*2)) { + return 1; + } + } + + void* dest = ucx_array_at(*array, array->size++); + if (data) { + memcpy(dest, data, array->elemsize); + } else { + memset(dest, 0, array->elemsize); + } + + return 0; } int ucx_array_prepend(UcxArray *array, void *data) { - return 1; + if (array->size == array->capacity) { + if (ucx_array_reserve(array, array->capacity*2)) { + return 1; + } + } + + array->size++; + + if (array->size > 1) { + void *dest = ucx_array_at(*array,1); + memmove(dest, array->data, array->elemsize*array->size); + } + + if (data) { + memcpy(array->data, data, array->elemsize); + } else { + memset(array->data, 0, array->elemsize); + } + + return 0; } int ucx_array_concat(UcxArray *array1, const UcxArray *array2) { - return 1; + + if (array1->elemsize != array2->elemsize) + return 1; + + size_t capacity = array1->capacity+array2->capacity; + + if (array1->capacity < capacity) { + if (ucx_array_reserve(array1, capacity)) { + return 1; + } + } + + void* dest = ucx_array_at(*array1, array1->size); + memcpy(dest, array2->data, array2->size*array2->elemsize); + + array1->size += array2->size; + + return 0; } void *ucx_array_at(UcxArray array, size_t index) { - return NULL; + char* memory = array.data; + char* loc = memory + index*array.elemsize; + return loc; } size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) { - return 0; + if (cmpfnc == NULL) { + cmpfnc = ucx_cmp_mem; + data = &array.elemsize; + } + + if (array.size > 0) { + for (size_t i = 0 ; i < array.size ; i++) { + void* ptr = ucx_array_at(array, i); + if (cmpfnc(ptr, elem, data) == 0) { + return i; + } + } + return array.size; + } else { + return 0; + } } int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) { return ucx_array_find(array, elem, cmpfnc, data) != array.size; } -int ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) { - return 1; +static void ucx_array_merge(UcxArray *array, cmp_func cmpfnc, void *data, + size_t start, size_t mid, size_t end) { + + size_t rightstart = mid + 1; + + if (cmpfnc(ucx_array_at(*array, mid), + ucx_array_at(*array, rightstart), data) <= 0) { + /* already sorted */ + return; + } + + // we need memory for one element + void *value = malloc(array->elemsize); + + while (start <= mid && rightstart <= end) { + if (cmpfnc(ucx_array_at(*array, start), + ucx_array_at(*array, rightstart), data) <= 0) { + start++; + } else { + // save the value from the right + memcpy(value, ucx_array_at(*array, rightstart), array->elemsize); + + // shift all left elements one element to the right + size_t shiftcount = rightstart-start; + void *startptr = ucx_array_at(*array, start); + void *dest = ucx_array_at(*array, start+1); + memmove(dest, startptr, shiftcount*array->elemsize); + + // bring the first value from the right to the left + memcpy(startptr, value, array->elemsize); + + start++; + mid++; + rightstart++; + } + } + + // free the temporary memory + free(value); +} + +static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data, + size_t l, size_t r) { + if (l < r) { + size_t m = l + (r - l) / 2; + + ucx_array_mergesort(array, cmpfnc, data, l, m); + ucx_array_mergesort(array, cmpfnc, data, m + 1, r); + ucx_array_merge(array, cmpfnc, data, l, m, r); + } +} + +void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) { + ucx_array_mergesort(&array, cmpfnc, data, 0, array.size-1); } void ucx_array_remove(UcxArray *array, size_t index) { - + array->size--; + if (index < array->size) { + void* dest = ucx_array_at(*array, index); + void* src = ucx_array_at(*array, index+1); + memmove(dest, src, (array->size - index)*array->elemsize); + } } void ucx_array_remove_fast(UcxArray *array, size_t index) { - + array->size--; + if (index < array->size) { + void* dest = ucx_array_at(*array, index); + void* src = ucx_array_at(*array, array->size); + memcpy(dest, src, array->elemsize); + } } int ucx_array_shrink(UcxArray* array) { - return 1; + void* newptr = alrealloc(array->allocator, array->data, + array->size*array->elemsize); + if (newptr) { + array->data = newptr; + array->capacity = array->size; + return 0; + } else { + return 1; + } } int ucx_array_resize(UcxArray* array, size_t capacity) { - return 1; + if (array->capacity >= capacity) { + void* newptr = alrealloc(array->allocator, array->data, + capacity*array->elemsize); + if (newptr) { + array->data = newptr; + array->capacity = capacity; + if (array->size > array->capacity) { + array->size = array->capacity; + } + return 0; + } else { + return 1; + } + } else { + return ucx_array_reserve(array, capacity); + } } int ucx_array_reserve(UcxArray* array, size_t capacity) { - return 1; + if (array->capacity > capacity) { + return 0; + } else { + void* newptr = alrealloc(array->allocator, array->data, + capacity*array->elemsize); + if (newptr) { + array->data = newptr; + array->capacity = capacity; + return 0; + } else { + return 1; + } + } } -
--- a/src/ucx/array.h Thu Jul 04 21:31:45 2019 +0200 +++ b/src/ucx/array.h Thu Jul 04 22:23:15 2019 +0200 @@ -276,17 +276,15 @@ int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data); /** - * Sorts a UcxArray with natural merge sort. + * Sorts a UcxArray with an almost in-place merge sort. * - * This function uses O(n) additional temporary memory for merge operations - * that is automatically freed after each merge. + * This function uses additional memory for exactly one element. * * @param the array to sort * @param cmpfnc the function that shall be used to compare the element data * @param data additional data for the cmp_func() - * @return zero on success, non-zero if allocation of temporary memory failed */ -int ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data); +void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data); /** * Removes an element from the array.
--- a/test/array_tests.c Thu Jul 04 21:31:45 2019 +0200 +++ b/test/array_tests.c Thu Jul 04 22:23:15 2019 +0200 @@ -151,19 +151,17 @@ UCX_TEST_BEGIN - UCX_TEST_ASSERT(ucx_array_equals(a1, a2, ucx_cmp_int, NULL) == 0, "failed"); - UCX_TEST_ASSERT(ucx_array_equals(a1, a4, ucx_cmp_int, NULL) > 0, "failed"); - UCX_TEST_ASSERT(ucx_array_equals(a4, a1, ucx_cmp_int, NULL) < 0, "failed"); - UCX_TEST_ASSERT(ucx_array_equals(a1, a3, ucx_cmp_int, NULL) < 0, - "comparing arrays of different element size failed"); - UCX_TEST_ASSERT(ucx_array_equals(a3, a1, ucx_cmp_int, NULL) > 0, - "comparing arrays of different element size failed"); + UCX_TEST_ASSERT(ucx_array_equals(a1, a2, ucx_cmp_int, NULL), "failed"); + UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, ucx_cmp_int, NULL), "failed"); + UCX_TEST_ASSERT(!ucx_array_equals(a4, a1, ucx_cmp_int, NULL), "failed"); + UCX_TEST_ASSERT(!ucx_array_equals(a1, a3, ucx_cmp_int, NULL), + "comparing arrays of different element size shall fail"); + UCX_TEST_ASSERT(!ucx_array_equals(a3, a1, ucx_cmp_int, NULL), + "comparing arrays of different element size shall fail"); - UCX_TEST_ASSERT(ucx_array_equals(a1, a2, NULL, NULL) == 0, + UCX_TEST_ASSERT(ucx_array_equals(a1, a2, NULL, NULL), "compare using memcmp() failed"); - UCX_TEST_ASSERT(ucx_array_equals(a1, a4, NULL, NULL) > 0, - "compare using memcmp() failed"); - UCX_TEST_ASSERT(ucx_array_equals(a4, a1, NULL, NULL) < 0, + UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, NULL, NULL), "compare using memcmp() failed"); UCX_TEST_END @@ -337,11 +335,11 @@ UCX_TEST_BEGIN UCX_TEST_ASSERT(array.data != copy.data, "no true copy"); - UCX_TEST_ASSERT(ucx_array_equals(array, copy, ucx_cmp_int, NULL), "failed"); UCX_TEST_ASSERT(array.size == copy.size, "size mismatch"); UCX_TEST_ASSERT(array.capacity == copy.capacity, "capacity mismatch"); UCX_TEST_ASSERT(array.elemsize == copy.elemsize, "element size mismatch"); UCX_TEST_ASSERT(array.allocator == copy.allocator, "allocator mismatch"); + UCX_TEST_ASSERT(ucx_array_equals(array, copy, ucx_cmp_int, NULL), "failed"); UCX_TEST_END @@ -369,10 +367,22 @@ UCX_TEST_BEGIN void* original_ptr = array.data; - UCX_TEST_ASSERT(!ucx_array_sort(array, ucx_cmp_int, NULL), "failed"); - UCX_TEST_ASSERT(!ucx_array_equals(array, expected, NULL, NULL), "failed"); + ucx_array_sort(array, ucx_cmp_int, NULL); + UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL), "failed"); UCX_TEST_ASSERT(array.size == 5, "size corrupted"); UCX_TEST_ASSERT(array.data == original_ptr, "shall not reallocate"); + + ucx_array_reserve(&array, 32); + ucx_array_reserve(&expected, 32); + array.size = expected.size = 32; + for (size_t i = 0 ; i < 32 ; i++) { + ucx_array_at_int(array, i) = ((i%2==0)?-1:1) * ((int) i); + ucx_array_at_int(expected, i) = (-30+2*i) - (i > 15 ? 1 : 0); + } + + ucx_array_sort(array, ucx_cmp_int, NULL); + UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL), + "failed for bigger arrays"); UCX_TEST_END ucx_array_free(&expected);
