# HG changeset patch # User Mike Becker # Date 1565101606 -7200 # Node ID 8f0a3c00d1d2be60a87dae84321f9b25dd54c8bf # Parent b9715d7317c1994e808f508cd31c779349e6fbde removes cumbersome array accessor macros diff -r b9715d7317c1 -r 8f0a3c00d1d2 src/array.c --- a/src/array.c Thu Jul 11 10:11:43 2019 +0200 +++ b/src/array.c Tue Aug 06 16:26:46 2019 +0200 @@ -223,7 +223,7 @@ return; } - // we need memory for one element + /* we need memory for one element */ void *value = malloc(array->elemsize); while (start <= mid && rightstart <= end) { @@ -231,16 +231,16 @@ ucx_array_at(*array, rightstart), data) <= 0) { start++; } else { - // save the value from the right + /* save the value from the right */ memcpy(value, ucx_array_at(*array, rightstart), array->elemsize); - // shift all left elements one element to the right + /* 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 + /* bring the first value from the right to the left */ memcpy(startptr, value, array->elemsize); start++; @@ -249,7 +249,7 @@ } } - // free the temporary memory + /* free the temporary memory */ free(value); } diff -r b9715d7317c1 -r 8f0a3c00d1d2 src/ucx/array.h --- a/src/ucx/array.h Thu Jul 11 10:11:43 2019 +0200 +++ b/src/ucx/array.h Tue Aug 06 16:26:46 2019 +0200 @@ -199,64 +199,6 @@ void *ucx_array_at(UcxArray array, size_t index); /** - * Returns an element of the specified type by value. - * - * This expression can also be assigned to. - * - * If sizeof(type) does not equal the array's element size, the - * behavior is undefined. - * If the index is out of bounds, the behavior is undefined. - * - * @param type the type of the element - * @param array the array to retrieve the element from - * @param index index of the element to return - * @return the requested element - * @see ucx_array_at() - */ -#define ucx_array_at_typed(type, array, index) (((type*)((array).data))[index]) - -/** - * Shorthand for ucx_array_at_typed(). - */ -#define ucx_array_at_int(arr, i) ucx_array_at_typed(int, arr, i) - -/** - * Shorthand for ucx_array_at_typed(). - */ -#define ucx_array_at_short(arr, i) ucx_array_at_typed(short, arr, i) - -/** - * Shorthand for ucx_array_at_typed(). - */ -#define ucx_array_at_longint(arr, i) ucx_array_at_typed(long int, arr, i) - -/** - * Shorthand for ucx_array_at_typed(). - */ -#define ucx_array_at_uint(arr, i) ucx_array_at_typed(unsigned int, arr, i) - -/** - * Shorthand for ucx_array_at_typed(). - */ -#define ucx_array_at_ushort(arr, i) ucx_array_at_typed(unsigned short, arr, i) - -/** - * Shorthand for ucx_array_at_typed(). - */ -#define ucx_array_at_ulongint(arr, i) \ - ucx_array_at_typed(unsigned long int, arr, i) - -/** - * Shorthand for ucx_array_get_typed(). - */ -#define ucx_array_get_float(arr, i) ucx_array_get_typed(float, arr, i) - -/** - * Shorthand for ucx_array_get_typed(). - */ -#define ucx_array_get_double(arr, i) ucx_array_get_typed(double, arr, i) - -/** * Returns the index of an element containing the specified data. * * This function uses a cmp_func() to compare the data of each list element @@ -290,9 +232,14 @@ int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data); /** - * Sorts a UcxArray with an almost in-place merge sort. + * Sorts a UcxArray with the best available sort algorithm. * - * This function uses additional memory for exactly one element. + * If present, qsort_s() will be used. Otherwise, if no additional data is + * specified, qsort() is used as a fall back. + * + * If qsort_s() is not available and data is not NULL, + * a custom almost in-place merge sort algorithm is used, which uses additional + * memory for exactly one element. * * @param array the array to sort * @param cmpfnc the function that shall be used to compare the element data diff -r b9715d7317c1 -r 8f0a3c00d1d2 test/array_tests.c --- a/test/array_tests.c Thu Jul 11 10:11:43 2019 +0200 +++ b/test/array_tests.c Tue Aug 06 16:26:46 2019 +0200 @@ -58,28 +58,32 @@ UCX_TEST(test_ucx_array_append) { UcxArray array = ucx_array_new(16, sizeof(int)); + int *elements; int x = 42; ucx_array_append(&array, &x); UCX_TEST_BEGIN - UCX_TEST_ASSERT(ucx_array_at_int(array, 0) == 42, "failed"); + elements = array.data; + UCX_TEST_ASSERT(elements[0] == 42, "failed"); x = 13; ucx_array_append(&array, &x); + elements = array.data; UCX_TEST_ASSERT(array.size == 2, "incorrect size after append"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 1) == 13, "failed"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 0) == 42, + UCX_TEST_ASSERT(elements[1] == 13, "failed"); + UCX_TEST_ASSERT(elements[0] == 42, "append corrupted previously inserted data"); ucx_array_append(&array, NULL); + elements = array.data; UCX_TEST_ASSERT(array.size == 3, "incorrect size after NULL append"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 2) == 0, "element is not zeroed"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 0) == 42, + UCX_TEST_ASSERT(elements[2] == 0, "element is not zeroed"); + UCX_TEST_ASSERT(elements[0] == 42, "NULL append corrupted previously inserted data"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 1) == 13, + UCX_TEST_ASSERT(elements[1] == 13, "NULL append corrupted previously inserted data"); UCX_TEST_END @@ -88,29 +92,33 @@ } UCX_TEST(test_ucx_array_prepend) { + int *elems; UcxArray array = ucx_array_new(16, sizeof(int)); int x = 42; ucx_array_prepend(&array, &x); UCX_TEST_BEGIN - UCX_TEST_ASSERT(ucx_array_at_int(array, 0) == 42, "failed"); + elems = array.data; + UCX_TEST_ASSERT(elems[0] == 42, "failed"); x = 13; ucx_array_prepend(&array, &x); + elems = array.data; UCX_TEST_ASSERT(array.size == 2, "incorrect size after prepend"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 0) == 13, "failed"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 1) == 42, + UCX_TEST_ASSERT(elems[0] == 13, "failed"); + UCX_TEST_ASSERT(elems[1] == 42, "prepend corrupted previously inserted data"); ucx_array_prepend(&array, NULL); + elems = array.data; UCX_TEST_ASSERT(array.size == 3, "incorrect size after NULL prepend"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 0) == 0, "element is not zeroed"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 1) == 13, + UCX_TEST_ASSERT(elems[0] == 0, "element is not zeroed"); + UCX_TEST_ASSERT(elems[1] == 13, "NULL prepend corrupted previously inserted data"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 2) == 42, + UCX_TEST_ASSERT(elems[2] == 42, "NULL prepend corrupted previously inserted data"); UCX_TEST_END @@ -119,27 +127,33 @@ } UCX_TEST(test_ucx_array_set) { + int *elems; UcxArray array = ucx_array_new(16, sizeof(int)); + int x = 42; UCX_TEST_BEGIN ucx_array_set(&array, 7, &x); - UCX_TEST_ASSERT(ucx_array_at_int(array, 7) == 42, "failed"); + + elems = array.data; + UCX_TEST_ASSERT(elems[7] == 42, "failed"); UCX_TEST_ASSERT(array.size >= 8, "array not resized on set"); UCX_TEST_ASSERT(array.capacity == 16, "capacity changed unnecessarily"); x = 13; ucx_array_set(&array, 27, &x); - UCX_TEST_ASSERT(ucx_array_at_int(array, 27) == 13, "failed"); + elems = array.data; + UCX_TEST_ASSERT(elems[27] == 13, "failed"); UCX_TEST_ASSERT(array.size == 28, "array not resized on set"); UCX_TEST_ASSERT(array.capacity == 28, "capacity not grown"); ucx_array_set(&array, 7, NULL); - UCX_TEST_ASSERT(ucx_array_at_int(array, 7) == 0, "not zeroed on NULL set"); + elems = array.data; + UCX_TEST_ASSERT(elems[7] == 0, "not zeroed on NULL set"); UCX_TEST_END @@ -152,30 +166,37 @@ UcxArray a3 = ucx_array_new(16, sizeof(long int)); UcxArray a4 = ucx_array_new(16, sizeof(int)); + int *intelems; + long int *longintelems; + a1.size = 5; - ucx_array_at_int(a1, 0) = 47; - ucx_array_at_int(a1, 1) = 11; - ucx_array_at_int(a1, 2) = 0; - ucx_array_at_int(a1, 3) = 8; - ucx_array_at_int(a1, 4) = 15; + intelems = a1.data; + intelems[0] = 47; + intelems[1] = 11; + intelems[2] = 0; + intelems[3] = 8; + intelems[4] = 15; a2.size = 5; - ucx_array_at_int(a2, 0) = 47; - ucx_array_at_int(a2, 1) = 11; - ucx_array_at_int(a2, 2) = 0; - ucx_array_at_int(a2, 3) = 8; - ucx_array_at_int(a2, 4) = 15; + intelems = a2.data; + intelems[0] = 47; + intelems[1] = 11; + intelems[2] = 0; + intelems[3] = 8; + intelems[4] = 15; a3.size = 5; - ucx_array_at_longint(a3, 0) = 47; - ucx_array_at_longint(a3, 1) = 11; - ucx_array_at_longint(a3, 2) = 0; - ucx_array_at_longint(a3, 3) = 8; - ucx_array_at_longint(a3, 4) = 15; + longintelems = a3.data; + longintelems[0] = 47; + longintelems[1] = 11; + longintelems[2] = 0; + longintelems[3] = 8; + longintelems[4] = 15; a4.size = 5; - ucx_array_at_int(a4, 0) = 47; - ucx_array_at_int(a4, 1) = 11; - ucx_array_at_int(a4, 2) = -6; - ucx_array_at_int(a4, 3) = 8; - ucx_array_at_int(a4, 4) = 15; + intelems = a4.data; + intelems[0] = 47; + intelems[1] = 11; + intelems[2] = -6; + intelems[3] = 8; + intelems[4] = 15; UCX_TEST_BEGIN @@ -202,24 +223,28 @@ UCX_TEST(test_ucx_array_concat) { UcxArray a1 = ucx_array_new(16, sizeof(int)); UcxArray a2 = ucx_array_new(16, sizeof(int)); + int *elems; a1.size = 2; - ucx_array_at_int(a1, 0) = 47; - ucx_array_at_int(a1, 1) = 11; + elems = a1.data; + elems[0] = 47; + elems[1] = 11; a2.size = 3; - ucx_array_at_int(a2, 0) = 0; - ucx_array_at_int(a2, 1) = 8; - ucx_array_at_int(a2, 2) = 15; + elems = a2.data; + elems[0] = 0; + elems[1] = 8; + elems[2] = 15; UCX_TEST_BEGIN UCX_TEST_ASSERT(!ucx_array_concat(&a1, &a2), "failed"); UCX_TEST_ASSERT(a1.size == 5, "failed"); - UCX_TEST_ASSERT(ucx_array_at_int(a1, 0) == 47, "failed"); - UCX_TEST_ASSERT(ucx_array_at_int(a1, 1) == 11, "failed"); - UCX_TEST_ASSERT(ucx_array_at_int(a1, 2) == 0, "failed"); - UCX_TEST_ASSERT(ucx_array_at_int(a1, 3) == 8, "failed"); - UCX_TEST_ASSERT(ucx_array_at_int(a1, 4) == 15, "failed"); + elems = a1.data; + UCX_TEST_ASSERT(elems[0] == 47, "failed"); + UCX_TEST_ASSERT(elems[1] == 11, "failed"); + UCX_TEST_ASSERT(elems[2] == 0, "failed"); + UCX_TEST_ASSERT(elems[3] == 8, "failed"); + UCX_TEST_ASSERT(elems[4] == 15, "failed"); a1.elemsize *= 2; UCX_TEST_ASSERT(ucx_array_concat(&a1, &a2), @@ -232,40 +257,17 @@ ucx_array_free(&a2); } -UCX_TEST(test_ucx_array_at) { - UcxArray array = ucx_array_new(16, sizeof(int)); - - int x = 42; - ucx_array_append(&array, &x); - x = 13; - ucx_array_append(&array, &x); - x = 5; - ucx_array_append(&array, &x); - - UCX_TEST_BEGIN - - UCX_TEST_ASSERT(ucx_array_at_int(array, 1) == 13, "failed"); - ucx_array_at_int(array, 1) = 80; - UCX_TEST_ASSERT(ucx_array_at_int(array, 1) == 80, "assignment failed"); - - - UCX_TEST_ASSERT(ucx_array_at_int(array, 0) == 42, "corrupted data"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 2) == 5, "corrupted data"); - - UCX_TEST_END - - ucx_array_free(&array); -} - UCX_TEST(test_ucx_array_find) { UcxArray array = ucx_array_new(16, sizeof(int)); + int *elems; array.size = 5; - ucx_array_at_int(array, 0) = 47; - ucx_array_at_int(array, 1) = 11; - ucx_array_at_int(array, 2) = 0; - ucx_array_at_int(array, 3) = 8; - ucx_array_at_int(array, 4) = 15; + elems = array.data; + elems[0] = 47; + elems[1] = 11; + elems[2] = 0; + elems[3] = 8; + elems[4] = 15; int x = 8; int y = 90; @@ -288,13 +290,15 @@ UCX_TEST(test_ucx_array_contains) { UcxArray array = ucx_array_new(16, sizeof(int)); + int *elems; array.size = 5; - ucx_array_at_int(array, 0) = 47; - ucx_array_at_int(array, 1) = 11; - ucx_array_at_int(array, 2) = 0; - ucx_array_at_int(array, 3) = 8; - ucx_array_at_int(array, 4) = 15; + elems = array.data; + elems[0] = 47; + elems[1] = 11; + elems[2] = 0; + elems[3] = 8; + elems[4] = 15; int x = 8; int y = 90; @@ -317,30 +321,34 @@ UCX_TEST(test_ucx_array_remove) { UcxArray array = ucx_array_new(16, sizeof(int)); + int *elems; array.size = 5; - ucx_array_at_int(array, 0) = 47; - ucx_array_at_int(array, 1) = 11; - ucx_array_at_int(array, 2) = 0; - ucx_array_at_int(array, 3) = 8; - ucx_array_at_int(array, 4) = 15; + elems = array.data; + elems[0] = 47; + elems[1] = 11; + elems[2] = 0; + elems[3] = 8; + elems[4] = 15; UCX_TEST_BEGIN ucx_array_remove(&array, 2); + elems = array.data; UCX_TEST_ASSERT( - ucx_array_at_int(array, 0) == 47 && - ucx_array_at_int(array, 1) == 11 && - ucx_array_at_int(array, 2) == 8 && - ucx_array_at_int(array, 3) == 15, + elems[0] == 47 && + elems[1] == 11 && + elems[2] == 8 && + elems[3] == 15, "wrong contents after remove"); UCX_TEST_ASSERT(array.size == 4, "wrong size after remove"); ucx_array_remove_fast(&array, 1); + elems = array.data; UCX_TEST_ASSERT( - ucx_array_at_int(array, 0) == 47 && - ucx_array_at_int(array, 1) == 15 && - ucx_array_at_int(array, 2) == 8, + elems[0] == 47 && + elems[1] == 15 && + elems[2] == 8, "wrong contents after fast remove"); UCX_TEST_ASSERT(array.size == 3, "wrong size after fast remove"); @@ -349,15 +357,16 @@ } UCX_TEST(test_ucx_array_clone) { - UcxArray array = ucx_array_new(16, sizeof(int)); + int *elems; array.size = 5; - ucx_array_at_int(array, 0) = 47; - ucx_array_at_int(array, 1) = 11; - ucx_array_at_int(array, 2) = 0; - ucx_array_at_int(array, 3) = 8; - ucx_array_at_int(array, 4) = 15; + elems = array.data; + elems[0] = 47; + elems[1] = 11; + elems[2] = 0; + elems[3] = 8; + elems[4] = 15; UcxArray copy = ucx_array_clone(array); UCX_TEST_BEGIN @@ -375,22 +384,39 @@ ucx_array_free(©); } +static int ucx_cmp_int_reverse(const void* x, const void* y, void* data) { + return -ucx_cmp_int(x,y,data); +} + UCX_TEST(test_ucx_array_sort) { - UcxArray array = ucx_array_new(16, sizeof(int)); + int *elems; + + UcxArray array = ucx_array_new(16, sizeof(int)); array.size = 5; - ucx_array_at_int(array, 0) = 47; - ucx_array_at_int(array, 1) = 11; - ucx_array_at_int(array, 2) = 0; - ucx_array_at_int(array, 3) = 8; - ucx_array_at_int(array, 4) = 15; + elems = array.data; + elems[0] = 47; + elems[1] = 11; + elems[2] = 0; + elems[3] = 8; + elems[4] = 15; UcxArray expected = ucx_array_new(16, sizeof(int)); expected.size = 5; - ucx_array_at_int(expected, 0) = 0; - ucx_array_at_int(expected, 1) = 8; - ucx_array_at_int(expected, 2) = 11; - ucx_array_at_int(expected, 3) = 15; - ucx_array_at_int(expected, 4) = 47; + elems = expected.data; + elems[0] = 0; + elems[1] = 8; + elems[2] = 11; + elems[3] = 15; + elems[4] = 47; + + UcxArray expectedrev = ucx_array_new(16, sizeof(int)); + expectedrev.size = 5; + elems = expectedrev.data; + elems[0] = 47; + elems[1] = 15; + elems[2] = 11; + elems[3] = 8; + elems[4] = 0; UCX_TEST_BEGIN @@ -399,16 +425,20 @@ 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_sort(array, ucx_cmp_int_reverse, NULL); + UCX_TEST_ASSERT(ucx_array_equals(array, expectedrev, NULL, NULL), "failed"); + 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); + ((int*)array.data)[i]= ((i%2==0)?-1:1) * ((int) i); + ((int*)expected.data)[i] = (-30+2*i) - (i > 15 ? 1 : 0); } - ucx_array_sort(array, ucx_cmp_int, NULL); + /* dummy third argument to trigger a possible fallback for qsort_s */ + ucx_array_sort(array, ucx_cmp_int, array.data); UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL), "failed for bigger arrays"); UCX_TEST_END @@ -418,10 +448,12 @@ } UCX_TEST(test_ucx_array_autogrow) { + int *elems; UcxArray array = ucx_array_new(4, sizeof(int)); array.size = 3; - ucx_array_at_int(array, 0) = 47; - ucx_array_at_int(array, 1) = 11; + elems = array.data; + elems[0] = 47; + elems[1] = 11; int x = 5; UCX_TEST_BEGIN @@ -432,10 +464,10 @@ UCX_TEST_ASSERT(array.capacity == 4 && array.data == oldptr, "array should not grow too early"); ucx_array_append(&array, &x); + elems = array.data; UCX_TEST_ASSERT(array.capacity == 8, "array did not grow"); UCX_TEST_ASSERT(array.size == 5, "incorrect size after grow"); - UCX_TEST_ASSERT(ucx_array_at_int(array, 3) == 5 && - ucx_array_at_int(array, 3) == 5, "corrupt data"); + UCX_TEST_ASSERT(elems[3] == 5 && elems[4] == 5, "corrupt data"); UCX_TEST_END ucx_array_free(&array); diff -r b9715d7317c1 -r 8f0a3c00d1d2 test/array_tests.h --- a/test/array_tests.h Thu Jul 11 10:11:43 2019 +0200 +++ b/test/array_tests.h Tue Aug 06 16:26:46 2019 +0200 @@ -38,7 +38,6 @@ UCX_TEST(test_ucx_array_free); UCX_TEST(test_ucx_array_new); -UCX_TEST(test_ucx_array_at); UCX_TEST(test_ucx_array_append); UCX_TEST(test_ucx_array_prepend); UCX_TEST(test_ucx_array_set); diff -r b9715d7317c1 -r 8f0a3c00d1d2 test/main.c --- a/test/main.c Thu Jul 11 10:11:43 2019 +0200 +++ b/test/main.c Tue Aug 06 16:26:46 2019 +0200 @@ -145,7 +145,6 @@ /* UcxArray Tests */ ucx_test_register(suite, test_ucx_array_free); ucx_test_register(suite, test_ucx_array_new); - ucx_test_register(suite, test_ucx_array_at); ucx_test_register(suite, test_ucx_array_append); ucx_test_register(suite, test_ucx_array_prepend); ucx_test_register(suite, test_ucx_array_set);