# HG changeset patch # User Mike Becker # Date 1562263651 -7200 # Node ID bc81faa9afdaa0d5edf55854c046953ab4f608c2 # Parent b3ad9d1a20b79a2363e91709b830f2d1dd00fdf3 adds array interface and tests diff -r b3ad9d1a20b7 -r bc81faa9afda src/Makefile.am --- a/src/Makefile.am Fri Dec 28 17:20:23 2018 +0100 +++ b/src/Makefile.am Thu Jul 04 20:07:31 2019 +0200 @@ -29,6 +29,7 @@ lib_LTLIBRARIES = libucx.la libucx_la_LDFLAGS = -version-info $(UCX_LIB_VERSION) libucx_la_SOURCES = utils.c +libucx_la_SOURCES += array.c libucx_la_SOURCES += list.c libucx_la_SOURCES += map.c libucx_la_SOURCES += avl.c @@ -44,6 +45,7 @@ ucxdir = $(includedir)/ucx ucx_HEADERS = ucx/allocator.h +ucx_HEADERS += ucx/array.h ucx_HEADERS += ucx/avl.h ucx_HEADERS += ucx/buffer.h ucx_HEADERS += ucx/list.h diff -r b3ad9d1a20b7 -r bc81faa9afda src/array.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/array.c Thu Jul 04 20:07:31 2019 +0200 @@ -0,0 +1,107 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "ucx/array.h" + + +UcxArray ucx_array_new(size_t capacity, size_t elemsize) { + return ucx_array_new_a(capacity, elemsize, ucx_default_allocator()); +} + +UcxArray ucx_array_new_a(size_t capacity, size_t elemsize, + UcxAllocator* allocator) { + UcxArray array; + + return array; +} + +UcxArray ucx_array_clone(UcxArray array) { + UcxArray clone; + + return clone; +} + +int ucx_array_equals(UcxArray array1, UcxArray array2, + cmp_func cmpfnc, void* data) { + + return 1; +} + +void ucx_array_free(UcxArray *array) { + +} + +int ucx_array_append(UcxArray *array, void *data) { + return 1; +} + +int ucx_array_prepend(UcxArray *array, void *data) { + return 1; +} + +int ucx_array_concat(UcxArray *array1, const UcxArray *array2) { + return 1; +} + +void *ucx_array_at(UcxArray array, size_t index) { + return NULL; +} + +size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) { + + 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; +} + +void ucx_array_remove(UcxArray *array, size_t index) { + +} + +void ucx_array_remove_fast(UcxArray *array, size_t index) { + +} + +int ucx_array_shrink(UcxArray* array) { + return 1; +} + +int ucx_array_resize(UcxArray* array, size_t capacity) { + return 1; +} + +int ucx_array_reserve(UcxArray* array, size_t capacity) { + return 1; +} + diff -r b3ad9d1a20b7 -r bc81faa9afda src/ucx/array.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ucx/array.h Thu Jul 04 20:07:31 2019 +0200 @@ -0,0 +1,356 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +/** + * Dynamically allocated array implementation. + * + * @file array.h + * @author Mike Becker + * @author Olaf Wintermann + */ + +#ifndef UCX_ARRAY_H +#define UCX_ARRAY_H + +#include "ucx.h" +#include "allocator.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * UCX array type. + */ +typedef struct { + /** + * The current capacity of the array. + */ + size_t capacity; + /** + * The actual number of elements in the array. + */ + size_t size; + /** + * The size of an individual element in bytes. + */ + size_t elemsize; + /** + * A pointer to the data. + */ + void* data; + /** + * The allocator used for the data. + */ + UcxAllocator* allocator; +} UcxArray; + + +/** + * Creates a new UCX array with the given capacity and element size. + * @param capacity the initial capacity + * @param elemsize the element size + * @return a new UCX array structure + */ +UcxArray ucx_array_new(size_t capacity, size_t elemsize); + +/** + * Creates a new UCX array using the specified allocator. + * + * @param capacity the initial capacity + * @param elemsize the element size + * @param allocator the allocator to use + * @return a new UCX array structure + */ +UcxArray ucx_array_new_a(size_t capacity, size_t elemsize, + UcxAllocator* allocator); + +/** + * Creates an shallow copy of an array. + * + * This function clones the specified array by using memcpy(). + * + * @param array the array to copy + * @return the copy (may be an empty array on allocation errors) + */ +UcxArray ucx_array_clone(UcxArray array); + + +/** + * Compares two UCX arrays element-wise by using a compare function. + * + * Elements of the two specified arrays are compared by using the specified + * compare function and the additional data. The type and content of this + * additional data depends on the cmp_func() used. + * + * This function always returns zero, if the element sizes of the arrays do + * not match and performs no comparisons in this case. + * + * @param array1 the first array + * @param array2 the second array + * @param cmpfnc the compare function + * @param data additional data for the compare function + * @return 1, if and only if the two arrays equal element-wise, 0 otherwise + */ +int ucx_array_equals(UcxArray array1, UcxArray array2, + cmp_func cmpfnc, void* data); + +/** + * Destroys the array. + * + * The data is freed and both capacity and count are reset to zero. + * If the array structure itself has been dynamically allocated, it has to be + * freed separately. + * + * @param array the array to free + */ +void ucx_array_free(UcxArray *array); + +/** + * Inserts an element at the end of the array. + * + * This is an O(1) operation. + * The array will automatically grow, if the capacity is exceeded. + * If a pointer to data is provided, the data is copied into the array with + * memcpy(). Otherwise the new element is completely zeroed. + * + * @param array a pointer the array where to append the data + * @param data a pointer to the data to insert (may be NULL) + * @return zero on success, non-zero if a reallocation was necessary but failed + */ +int ucx_array_append(UcxArray *array, void *data); + + +/** + * Inserts an element at the beginning of the array. + * + * This is an expensive operation, because the contents must be moved. + * If there is no particular reason to prepend data, you should use + * ucx_array_append() instead. + * + * @param array a pointer the array where to prepend the data + * @param data a pointer to the data to insert (may be NULL) + * @return zero on success, non-zero if a reallocation was necessary but failed + */ +int ucx_array_prepend(UcxArray *array, void *data); + +/** + * Concatenates two arrays. + * + * The contents of the second array are appended to the first array in one + * single operation. The second array is otherwise left untouched. + * + * The first array may grow automatically. If this fails, both arrays remain + * unmodified. + * + * @param array1 first array + * @param array2 second array + * @return zero on success, non-zero if reallocation was necessary but failed + * or the element size does not match + */ +int ucx_array_concat(UcxArray *array1, const UcxArray *array2); + +/** + * Returns a pointer to the array element at the specified index. + * + * @param array the array to retrieve the element from + * @param index index of the element to return + * @return a pointer to the element at the specified index or NULL, + * if the index is greater than the array size + */ +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, arr, i) (((type*)((arr).data))[i]) + +/** + * 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 + * with the specified data. If no cmp_func is provided, memcmp() is used. + * + * If the array contains the data more than once, the index of the first + * occurrence is returned. + * If the array does not contain the data, the size of array is returned. + * + * @param array the array where to search for the data + * @param elem the element data + * @param cmpfnc the compare function + * @param data additional data for the compare function + * @return the index of the element containing the specified data or the size of + * the array, if the data is not found in this array + */ +size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data); + +/** + * Checks, if an array contains a specific element. + * + * An element is found, if ucx_array_find() returns a value less than the size. + * + * @param array the array where to search for the data + * @param elem the element data + * @param cmpfnc the compare function + * @param data additional data for the compare function + * @return 1, if and only if the array contains the specified element data + * @see ucx_array_find() + */ +int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data); + +/** + * Sorts a UcxArray with natural merge sort. + * + * This function uses O(n) additional temporary memory for merge operations + * that is automatically freed after each merge. + * + * @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); + +/** + * Removes an element from the array. + * + * This is in general an expensive operation, because several elements may + * be moved. If the order of the elements is not relevant, use + * ucx_array_remove_fast() instead. + * + * @param array pointer to the array from which the element shall be removed + * @param index the index of the element to remove + */ +void ucx_array_remove(UcxArray *array, size_t index); + +/** + * Removes an element from the array. + * + * This is an O(1) operation, but does not maintain the order of the elements. + * The last element in the array is moved to the location of the removed + * element. + * + * @param array pointer to the array from which the element shall be removed + * @param index the index of the element to remove + */ +void ucx_array_remove_fast(UcxArray *array, size_t index); + +/** + * Shrinks the memory to exactly fit the contents. + * + * After this operation, the capacity equals the size. + * + * @param array a pointer to the array + * @return zero on success, non-zero if reallocation failed + */ +int ucx_array_shrink(UcxArray* array); + +/** + * Sets the capacity of the array. + * + * If the new capacity is smaller than the size of the array, the elements + * are removed and the size is adjusted accordingly. + * + * @param array a pointer to the array + * @param capacity the new capacity + * @return zero on success, non-zero if reallocation failed + */ +int ucx_array_resize(UcxArray* array, size_t capacity); + +/** + * Resizes the array only, if the capacity is insufficient. + * + * If the requested capacity is smaller than the current capacity, this + * function does nothing. + * + * @param array a pointer to the array + * @param capacity the guaranteed capacity + * @return zero on success, non-zero if reallocation failed + */ +int ucx_array_reserve(UcxArray* array, size_t capacity); + + + +#ifdef __cplusplus +} +#endif + +#endif /* UCX_ARRAY_H */ + diff -r b3ad9d1a20b7 -r bc81faa9afda src/ucx/ucx.h --- a/src/ucx/ucx.h Fri Dec 28 17:20:23 2018 +0100 +++ b/src/ucx/ucx.h Thu Jul 04 20:07:31 2019 +0200 @@ -1,7 +1,7 @@ /* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. * - * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. + * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: @@ -40,7 +40,7 @@ #define UCX_VERSION_MAJOR 2 /** Minor UCX version as integer constant. */ -#define UCX_VERSION_MINOR 0 +#define UCX_VERSION_MINOR 1 /** Version constant which ensures to increase monotonically. */ #define UCX_VERSION (((UCX_VERSION_MAJOR)<<16)|UCX_VERSION_MINOR) diff -r b3ad9d1a20b7 -r bc81faa9afda test/Makefile.am --- a/test/Makefile.am Fri Dec 28 17:20:23 2018 +0100 +++ b/test/Makefile.am Thu Jul 04 20:07:31 2019 +0200 @@ -31,6 +31,7 @@ ucxtest_CFLAGS = -I$(top_srcdir)/src ucxtest_SOURCES = main.c ucxtest_SOURCES += allocator_tests.c +ucxtest_SOURCES += array_tests.c ucxtest_SOURCES += list_tests.c ucxtest_SOURCES += avl_tests.c ucxtest_SOURCES += mpool_tests.c diff -r b3ad9d1a20b7 -r bc81faa9afda test/array_tests.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/array_tests.c Thu Jul 04 20:07:31 2019 +0200 @@ -0,0 +1,448 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "array_tests.h" +#include + +UCX_TEST(test_ucx_array_free) { + UcxArray array = ucx_array_new(16, sizeof(int)); + + UCX_TEST_BEGIN + ucx_array_free(&array); + UCX_TEST_ASSERT(array.data == NULL, "data pointer not NULL after free"); + UCX_TEST_ASSERT(array.size == 0, "size not zero after free"); + UCX_TEST_ASSERT(array.capacity == 0, "capacity not zero after free"); + UCX_TEST_ASSERT(array.allocator == ucx_default_allocator(), + "allocator corrupted during free"); + UCX_TEST_END +} + +UCX_TEST(test_ucx_array_new) { + UcxArray array = ucx_array_new(16, 47); + + UCX_TEST_BEGIN + UCX_TEST_ASSERT(array.data, "no memory allocated"); + UCX_TEST_ASSERT(array.size == 0, "size not initially zero"); + UCX_TEST_ASSERT(array.capacity == 16, "capacity not as requested"); + UCX_TEST_ASSERT(array.elemsize == 47, "element size not as requested"); + UCX_TEST_ASSERT(array.allocator == ucx_default_allocator(), + "array not using the default allocator"); + UCX_TEST_END + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_append) { + UcxArray array = ucx_array_new(16, sizeof(int)); + + int x = 42; + ucx_array_append(&array, &x); + UCX_TEST_BEGIN + + UCX_TEST_ASSERT(ucx_array_at_int(array, 0) == 42, "failed"); + + x = 13; + ucx_array_append(&array, &x); + + 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, + "append corrupted previously inserted data"); + + ucx_array_append(&array, NULL); + + 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, + "NULL append corrupted previously inserted data"); + UCX_TEST_ASSERT(ucx_array_at_int(array, 1) == 13, + "NULL append corrupted previously inserted data"); + + UCX_TEST_END + + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_prepend) { + 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"); + + x = 13; + ucx_array_prepend(&array, &x); + + 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, + "prepend corrupted previously inserted data"); + + ucx_array_prepend(&array, NULL); + + 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, + "NULL prepend corrupted previously inserted data"); + UCX_TEST_ASSERT(ucx_array_at_int(array, 2) == 42, + "NULL prepend corrupted previously inserted data"); + + UCX_TEST_END + + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_equals) { + UcxArray a1 = ucx_array_new(16, sizeof(int)); + UcxArray a2 = ucx_array_new(16, sizeof(int)); + UcxArray a3 = ucx_array_new(16, sizeof(long int)); + UcxArray a4 = ucx_array_new(16, sizeof(int)); + + 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; + 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; + 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; + 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; + + 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, NULL, NULL) == 0, + "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, + "compare using memcmp() failed"); + + UCX_TEST_END + ucx_array_free(&a1); + ucx_array_free(&a2); + ucx_array_free(&a3); + ucx_array_free(&a4); +} + +UCX_TEST(test_ucx_array_concat) { + UcxArray a1 = ucx_array_new(16, sizeof(int)); + UcxArray a2 = ucx_array_new(16, sizeof(int)); + + a1.size = 2; + ucx_array_at_int(a1, 0) = 47; + ucx_array_at_int(a1, 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; + + 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"); + + a1.elemsize *= 2; + UCX_TEST_ASSERT(ucx_array_concat(&a1, &a2), + "arrays of different element size must not be concatenated"); + UCX_TEST_ASSERT(a1.size == 5, + "arrays of different element size must not be concatenated"); + + UCX_TEST_END + ucx_array_free(&a1); + 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)); + + 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; + + int x = 8; + int y = 90; + + UCX_TEST_BEGIN + + UCX_TEST_ASSERT(ucx_array_find(array,(void*)&x,ucx_cmp_int,NULL) == 3, + "doesn't find element"); + UCX_TEST_ASSERT(ucx_array_find(array,(void*)&y,ucx_cmp_int,NULL) == 5, + "finds non-existing element"); + + UCX_TEST_ASSERT(ucx_array_find(array,(void*)&x,NULL,NULL) == 3, + "failed using memcmp()"); + UCX_TEST_ASSERT(ucx_array_find(array,(void*)&y,NULL,NULL) == 5, + "failed using memcmp()"); + + UCX_TEST_END + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_contains) { + 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; + + int x = 8; + int y = 90; + + UCX_TEST_BEGIN + + UCX_TEST_ASSERT(ucx_array_contains(array,(void*)&x,ucx_cmp_int,NULL), + "false negative"); + UCX_TEST_ASSERT(!ucx_array_contains(array,(void*)&y,ucx_cmp_int,NULL), + "false positive"); + + UCX_TEST_ASSERT(ucx_array_contains(array,(void*)&x,NULL,NULL), + "false negative using memcmp()"); + UCX_TEST_ASSERT(!ucx_array_contains(array,(void*)&y,NULL,NULL), + "false positive using memcmp()"); + + UCX_TEST_END + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_remove) { + 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; + + UCX_TEST_BEGIN + + ucx_array_remove(&array, 2); + 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, + "wrong contents after remove"); + UCX_TEST_ASSERT(array.size == 4, "wrong size after remove"); + + ucx_array_remove_fast(&array, 1); + UCX_TEST_ASSERT( + ucx_array_at_int(array, 0) == 47 && + ucx_array_at_int(array, 1) == 15 && + ucx_array_at_int(array, 2) == 8, + "wrong contents after fast remove"); + UCX_TEST_ASSERT(array.size == 3, "wrong size after fast remove"); + + UCX_TEST_END + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_clone) { + + 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; + + UcxArray copy = ucx_array_clone(array); + 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_END + + ucx_array_free(&array); + ucx_array_free(©); +} + +UCX_TEST(test_ucx_array_sort) { + 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; + + 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; + + + 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_TEST_ASSERT(array.size == 5, "size corrupted"); + UCX_TEST_ASSERT(array.data == original_ptr, "shall not reallocate"); + UCX_TEST_END + + ucx_array_free(&expected); + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_autogrow) { + 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; + int x = 5; + + UCX_TEST_BEGIN + + void* oldptr = array.data; + + ucx_array_append(&array, &x); + UCX_TEST_ASSERT(array.capacity == 4 && array.data == oldptr, + "array should not grow too early"); + ucx_array_append(&array, &x); + 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_END + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_shrink) { + UcxArray array = ucx_array_new(16, sizeof(int)); + array.size = 4; + + UCX_TEST_BEGIN + UCX_TEST_ASSERT(!ucx_array_shrink(&array), "failed"); + UCX_TEST_ASSERT(array.capacity == 4, "incorrect capacity after shrink"); + UCX_TEST_END + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_resize) { + UcxArray array = ucx_array_new(16, sizeof(int)); + array.size = 8; + + UCX_TEST_BEGIN + + UCX_TEST_ASSERT(!ucx_array_resize(&array, 32), "failed"); + UCX_TEST_ASSERT(array.capacity == 32, "incorrect capacity after resize"); + UCX_TEST_ASSERT(array.size == 8, "incorrect size after resize"); + + UCX_TEST_ASSERT(!ucx_array_resize(&array, 4), "failed"); + UCX_TEST_ASSERT(array.capacity == 4, "incorrect capacity after resize"); + UCX_TEST_ASSERT(array.size == 4, "incorrect size after resize"); + + UCX_TEST_END + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_reserve) { + UcxArray array = ucx_array_new(16, sizeof(int)); + + UCX_TEST_BEGIN + + UCX_TEST_ASSERT(!ucx_array_reserve(&array, 4), "failed"); + UCX_TEST_ASSERT(array.capacity == 16, "reserve shall not shrink"); + + UCX_TEST_ASSERT(!ucx_array_resize(&array, 32), "failed"); + UCX_TEST_ASSERT(array.capacity == 32, "incorrect capacity after reserve"); + + UCX_TEST_END + ucx_array_free(&array); +} diff -r b3ad9d1a20b7 -r bc81faa9afda test/array_tests.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/array_tests.h Thu Jul 04 20:07:31 2019 +0200 @@ -0,0 +1,61 @@ +/* + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. + * + * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef ARRAY_TESTS_H +#define ARRAY_TESTS_H + +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif + +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_autogrow); +UCX_TEST(test_ucx_array_equals); +UCX_TEST(test_ucx_array_concat); +UCX_TEST(test_ucx_array_find); +UCX_TEST(test_ucx_array_contains); +UCX_TEST(test_ucx_array_remove); +UCX_TEST(test_ucx_array_clone); +UCX_TEST(test_ucx_array_sort); +UCX_TEST(test_ucx_array_shrink); +UCX_TEST(test_ucx_array_resize); +UCX_TEST(test_ucx_array_reserve); + +#ifdef __cplusplus +} +#endif + +#endif /* ARRAY_TESTS_H */ + diff -r b3ad9d1a20b7 -r bc81faa9afda test/main.c --- a/test/main.c Fri Dec 28 17:20:23 2018 +0100 +++ b/test/main.c Thu Jul 04 20:07:31 2019 +0200 @@ -33,6 +33,7 @@ #include "main.h" +#include "array_tests.h" #include "allocator_tests.h" #include "logging_tests.h" #include "list_tests.h" @@ -141,6 +142,24 @@ ucx_test_register(suite, test_ucx_logger_new); ucx_test_register(suite, test_ucx_logger_log); + /* 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_autogrow); + ucx_test_register(suite, test_ucx_array_equals); + ucx_test_register(suite, test_ucx_array_concat); + ucx_test_register(suite, test_ucx_array_find); + ucx_test_register(suite, test_ucx_array_contains); + ucx_test_register(suite, test_ucx_array_remove); + ucx_test_register(suite, test_ucx_array_clone); + ucx_test_register(suite, test_ucx_array_sort); + ucx_test_register(suite, test_ucx_array_shrink); + ucx_test_register(suite, test_ucx_array_resize); + ucx_test_register(suite, test_ucx_array_reserve); + /* UcxList Tests */ ucx_test_register(suite, test_ucx_list_append); ucx_test_register(suite, test_ucx_list_prepend);