changeset
improves array append/prepend/set interface
Sat, 10 Aug 2019 11:12:49 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Sat, 10 Aug 2019 11:12:49 +0200
- branch
- feature/array
- changeset 354
- 7fd13b9f8f60
- parent 353
- 135ce35d5108
- child 355
- d315a068235a
improves array append/prepend/set interface
| 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 | |
| test/array_tests.h | file | annotate | diff | comparison | revisions | |
| test/main.c | file | annotate | diff | comparison | revisions |
--- a/src/array.c Sat Aug 10 09:47:59 2019 +0200 +++ b/src/array.c Sat Aug 10 11:12:49 2019 +0200 @@ -55,6 +55,18 @@ #define ucx_array_sort_impl ucx_mergesort #endif +static int ucx_array_ensurecap(UcxArray *array, size_t reqcap) { + size_t required_capacity = array->capacity; + while (reqcap > required_capacity) { + if (required_capacity * 2 < required_capacity) + return 1; + required_capacity <<= 1; + } + if (ucx_array_reserve(array, required_capacity)) { + return 1; + } +} + UcxArray ucx_array_new(size_t capacity, size_t elemsize) { return ucx_array_new_a(capacity, elemsize, ucx_default_allocator()); } @@ -127,62 +139,84 @@ array->capacity = array->size = 0; } -int ucx_array_append(UcxArray *array, void *data) { - if (array->size == array->capacity) { - if (ucx_array_reserve(array, array->capacity*2)) { - return 1; - } +int ucx_array_append_from(UcxArray *array, void *data, size_t count) { + if (ucx_array_ensurecap(array, array->size + count)) + return 1; + + void* dest = ucx_array_at(*array, array->size); + if (data) { + memcpy(dest, data, array->elemsize*count); + } else { + memset(dest, 0, array->elemsize*count); + } + array->size += count; + + return 0; +} + +int ucx_array_prepend_from(UcxArray *array, void *data, size_t count) { + if (ucx_array_ensurecap(array, array->size + count)) + return 1; + + if (array->size > 0) { + void *dest = ucx_array_at(*array, count); + memmove(dest, array->data, array->elemsize*array->size); } - void* dest = ucx_array_at(*array, array->size++); if (data) { - memcpy(dest, data, array->elemsize); + memcpy(array->data, data, array->elemsize*count); } else { - memset(dest, 0, array->elemsize); + memset(array->data, 0, array->elemsize*count); + } + array->size += count; + + return 0; +} + +int ucx_array_set_from(UcxArray *array, size_t index, + void *data, size_t count) { + if (ucx_array_ensurecap(array, index + count)) + return 1; + + if (index+count > array->size) { + array->size = index+count; + } + + void *dest = ucx_array_at(*array, index); + if (data) { + memcpy(dest, data, array->elemsize*count); + } else { + memset(dest, 0, array->elemsize*count); } return 0; } -int ucx_array_prepend(UcxArray *array, void *data) { - 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_appendv(UcxArray *array, ...) { + va_list ap; + va_start(ap, array); + int elem = va_arg(ap, int); + int ret = ucx_array_append_from(array, &elem, 1); + va_end(ap); + return ret; } -int ucx_array_set(UcxArray *array, size_t index, void *data) { - if (index >= array->size) { - if (ucx_array_reserve(array, index+1)) { - return 1; - } - array->size = index+1; - } - - void *dest = ucx_array_at(*array, index); - if (data) { - memcpy(dest, data, array->elemsize); - } else { - memset(dest, 0, array->elemsize); - } - - return 0; +int ucx_array_prependv(UcxArray *array, ...) { + va_list ap; + va_start(ap, array); + int elem = va_arg(ap, int); + int ret = ucx_array_prepend_from(array, &elem, 1); + va_end(ap); + return ret; +} + +int ucx_array_setv(UcxArray *array, size_t index, ...) { + va_list ap; + va_start(ap, index); + int elem = va_arg(ap, int); + int ret = ucx_array_set_from(array, index, &elem, 1); + va_end(ap); + return ret; } int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
--- a/src/ucx/array.h Sat Aug 10 09:47:59 2019 +0200 +++ b/src/ucx/array.h Sat Aug 10 11:12:49 2019 +0200 @@ -131,18 +131,86 @@ void ucx_array_destroy(UcxArray *array); /** - * Inserts an element at the end of the array. + * Inserts elements 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. + * memcpy(). Otherwise the new elements are completely zeroed. * * @param array a pointer the array where to append the data * @param data a pointer to the data to insert (may be <code>NULL</code>) + * @param count number of elements to copy from data (if data is + * <code>NULL</code>, zeroed elements are appended) * @return zero on success, non-zero if a reallocation was necessary but failed + * @see ucx_array_set_from() + * @see ucx_array_append() + */ +int ucx_array_append_from(UcxArray *array, void *data, size_t count); + + +/** + * Inserts elements 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_from() instead. + * + * @param array a pointer the array where to prepend the data + * @param data a pointer to the data to insert (may be <code>NULL</code>) + * @param count number of elements to copy from data (if data is + * <code>NULL</code>, zeroed elements are inserted) + * @return zero on success, non-zero if a reallocation was necessary but failed + * @see ucx_array_append_from() + * @see ucx_array_set_from() + * @see ucx_array_prepend() */ -int ucx_array_append(UcxArray *array, void *data); +int ucx_array_prepend_from(UcxArray *array, void *data, size_t count); + + +/** + * Sets elements starting at the specified index. + * + * If the any index is out of bounds, the array automatically grows. + * The pointer to the data may be NULL, in which case the elements are zeroed. + * + * @param array a pointer the array where to set the data + * @param index the index of the element to set + * @param data a pointer to the data to insert (may be <code>NULL</code>) + * @param count number of elements to copy from data (if data is + * <code>NULL</code>, the memory in the array is zeroed) + * @return zero on success, non-zero if a reallocation was necessary but failed + * @see ucx_array_append_from() + * @see ucx_array_set() + */ +int ucx_array_set_from(UcxArray *array, size_t index, void *data, size_t count); + +/** + * 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 the type of the argument has a different size than the element size of + * this array, the behavior is undefined. + * + * @param array a pointer the array where to append the data + * @param elem the value to insert + * @return zero on success, non-zero if a reallocation was necessary but failed + * @see ucx_array_append_from() + * @see ucx_array_set() + */ +#define ucx_array_append(array, elem) ucx_array_appendv(array, elem) + +/** + * For internal use. + * Use ucx_array_append() + * + * @param array + * @param ... + * @return + * @see ucx_array_append() + */ +int ucx_array_appendv(UcxArray *array, ...); /** @@ -153,24 +221,51 @@ * 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 <code>NULL</code>) + * @param elem the value to insert * @return zero on success, non-zero if a reallocation was necessary but failed + * @see ucx_array_append() + * @see ucx_array_set_from() + * @see ucx_array_prepend_from() */ -int ucx_array_prepend(UcxArray *array, void *data); +#define ucx_array_prepend(array, elem) ucx_array_prependv(array, elem) + +/** + * For internal use. + * Use ucx_array_prepend() + * + * @param array + * @param ... + * @return + * @see ucx_array_prepend() + */ +int ucx_array_prependv(UcxArray *array, ...); /** * Sets an element at the specified index. * - * If the index is out of bounds, the array automatically grows. - * The pointer to the data may be NULL, in which case the element is zeroed. + * If the any index is out of bounds, the array automatically grows. * * @param array a pointer the array where to set the data * @param index the index of the element to set - * @param data a pointer to the data to insert (may be <code>NULL</code>) + * @param elem the value to set * @return zero on success, non-zero if a reallocation was necessary but failed + * @see ucx_array_append() + * @see ucx_array_set_from() */ -int ucx_array_set(UcxArray *array, size_t index, void *data); +#define ucx_array_set(array, index, elem) ucx_array_setv(array, index, elem) + +/** + * For internal use. + * Use ucx_array_set() + * + * @param array + * @param index + * @param ... + * @return + * @see ucx_array_set() + */ +int ucx_array_setv(UcxArray *array, size_t index, ...); /** * Concatenates two arrays.
--- a/test/array_tests.c Sat Aug 10 09:47:59 2019 +0200 +++ b/test/array_tests.c Sat Aug 10 11:12:49 2019 +0200 @@ -56,35 +56,138 @@ ucx_array_destroy(&array); } -UCX_TEST(test_ucx_array_append) { +UCX_TEST(test_ucx_array_append_from) { UcxArray array = ucx_array_new(16, sizeof(int)); int *elements; int x = 42; - ucx_array_append(&array, &x); + ucx_array_append_from(&array, &x, 1); UCX_TEST_BEGIN elements = array.data; UCX_TEST_ASSERT(elements[0] == 42, "failed"); - x = 13; - ucx_array_append(&array, &x); + int y[2] = {13, 37}; + ucx_array_append_from(&array, y, 2); elements = array.data; - UCX_TEST_ASSERT(array.size == 2, "incorrect size after append"); + UCX_TEST_ASSERT(array.size == 3, "incorrect size after append"); UCX_TEST_ASSERT(elements[1] == 13, "failed"); + UCX_TEST_ASSERT(elements[2] == 37, "failed"); UCX_TEST_ASSERT(elements[0] == 42, "append corrupted previously inserted data"); - ucx_array_append(&array, NULL); + ucx_array_append_from(&array, NULL, 2); elements = array.data; - UCX_TEST_ASSERT(array.size == 3, "incorrect size after NULL append"); - UCX_TEST_ASSERT(elements[2] == 0, "element is not zeroed"); + UCX_TEST_ASSERT(array.size == 5, "incorrect size after NULL append"); + UCX_TEST_ASSERT(elements[3] == 0, "element is not zeroed"); + UCX_TEST_ASSERT(elements[4] == 0, "element is not zeroed"); UCX_TEST_ASSERT(elements[0] == 42, "NULL append corrupted previously inserted data"); UCX_TEST_ASSERT(elements[1] == 13, "NULL append corrupted previously inserted data"); + UCX_TEST_ASSERT(elements[2] == 37, + "NULL append corrupted previously inserted data"); + + UCX_TEST_END + + ucx_array_destroy(&array); +} + +UCX_TEST(test_ucx_array_prepend_from) { + int *elems; + UcxArray array = ucx_array_new(16, sizeof(int)); + + int x = 42; + ucx_array_prepend_from(&array, &x, 1); + UCX_TEST_BEGIN + + elems = array.data; + UCX_TEST_ASSERT(elems[0] == 42, "failed"); + + int y[2] = {13, 37}; + ucx_array_prepend_from(&array, y, 2); + + elems = array.data; + UCX_TEST_ASSERT(array.size == 3, "incorrect size after prepend"); + UCX_TEST_ASSERT(elems[0] == 13, "failed"); + UCX_TEST_ASSERT(elems[1] == 37, "failed"); + UCX_TEST_ASSERT(elems[2] == 42, + "prepend corrupted previously inserted data"); + + ucx_array_prepend_from(&array, NULL, 2); + + elems = array.data; + UCX_TEST_ASSERT(array.size == 5, "incorrect size after NULL prepend"); + UCX_TEST_ASSERT(elems[0] == 0, "element is not zeroed"); + UCX_TEST_ASSERT(elems[1] == 0, "element is not zeroed"); + UCX_TEST_ASSERT(elems[2] == 13, + "NULL prepend corrupted previously inserted data"); + UCX_TEST_ASSERT(elems[3] == 37, + "NULL prepend corrupted previously inserted data"); + UCX_TEST_ASSERT(elems[4] == 42, + "NULL prepend corrupted previously inserted data"); + + UCX_TEST_END + + ucx_array_destroy(&array); +} + +UCX_TEST(test_ucx_array_set_from) { + int *elems; + UcxArray array = ucx_array_new(16, sizeof(int)); + + int x = 42; + + UCX_TEST_BEGIN + + ucx_array_set_from(&array, 7, &x, 1); + + 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"); + + int y[2] = {13, 37}; + ucx_array_set_from(&array, 27, y, 2); + + elems = array.data; + UCX_TEST_ASSERT(elems[27] == 13, "failed"); + UCX_TEST_ASSERT(elems[28] == 37, "failed"); + UCX_TEST_ASSERT(array.size == 29, "array not resized on set"); + UCX_TEST_ASSERT(array.capacity == 32, "capacity not grown"); + + ucx_array_set_from(&array, 7, NULL, 2); + + elems = array.data; + UCX_TEST_ASSERT(elems[7] == 0, "not zeroed on NULL set"); + UCX_TEST_ASSERT(elems[8] == 0, "not zeroed on NULL set"); + + UCX_TEST_END + + ucx_array_destroy(&array); +} + +UCX_TEST(test_ucx_array_append) { + UcxArray array = ucx_array_new(16, sizeof(int)); + int *elements; + + ucx_array_append(&array, 42); + UCX_TEST_BEGIN + + elements = array.data; + UCX_TEST_ASSERT(elements[0] == 42, "failed"); + + ucx_array_append(&array, 13); + ucx_array_append(&array, 37); + + elements = array.data; + UCX_TEST_ASSERT(array.size == 3, "incorrect size after append"); + UCX_TEST_ASSERT(elements[1] == 13, "failed"); + UCX_TEST_ASSERT(elements[2] == 37, "failed"); + UCX_TEST_ASSERT(elements[0] == 42, + "append corrupted previously inserted data"); UCX_TEST_END @@ -95,32 +198,22 @@ int *elems; UcxArray array = ucx_array_new(16, sizeof(int)); - int x = 42; - ucx_array_prepend(&array, &x); + ucx_array_prepend(&array, 42); UCX_TEST_BEGIN elems = array.data; UCX_TEST_ASSERT(elems[0] == 42, "failed"); - x = 13; - ucx_array_prepend(&array, &x); + ucx_array_prepend(&array, 37); + ucx_array_prepend(&array, 13); elems = array.data; - UCX_TEST_ASSERT(array.size == 2, "incorrect size after prepend"); + UCX_TEST_ASSERT(array.size == 3, "incorrect size after prepend"); UCX_TEST_ASSERT(elems[0] == 13, "failed"); - UCX_TEST_ASSERT(elems[1] == 42, + UCX_TEST_ASSERT(elems[1] == 37, "failed"); + UCX_TEST_ASSERT(elems[2] == 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(elems[0] == 0, "element is not zeroed"); - UCX_TEST_ASSERT(elems[1] == 13, - "NULL prepend corrupted previously inserted data"); - UCX_TEST_ASSERT(elems[2] == 42, - "NULL prepend corrupted previously inserted data"); - UCX_TEST_END ucx_array_destroy(&array); @@ -129,32 +222,25 @@ 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_array_set(&array, 7, 42); 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.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_array_set(&array, 27, 13); + ucx_array_set(&array, 28, 37); 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); - - elems = array.data; - UCX_TEST_ASSERT(elems[7] == 0, "not zeroed on NULL set"); - + UCX_TEST_ASSERT(elems[28] == 37, "failed"); + UCX_TEST_ASSERT(array.size == 29, "array not resized on set"); + UCX_TEST_ASSERT(array.capacity == 32, "capacity not grown"); + UCX_TEST_END ucx_array_destroy(&array); @@ -260,12 +346,8 @@ 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); + int x[3] = {42, 13, 5}; + ucx_array_append_from(&array, x, 3); UCX_TEST_BEGIN @@ -484,10 +566,10 @@ void* oldptr = array.data; - ucx_array_append(&array, &x); + ucx_array_append(&array, 5); UCX_TEST_ASSERT(array.capacity == 4 && array.data == oldptr, "array should not grow too early"); - ucx_array_append(&array, &x); + ucx_array_append(&array, 5); elems = array.data; UCX_TEST_ASSERT(array.capacity == 8, "array did not grow"); UCX_TEST_ASSERT(array.size == 5, "incorrect size after grow");
--- a/test/array_tests.h Sat Aug 10 09:47:59 2019 +0200 +++ b/test/array_tests.h Sat Aug 10 11:12:49 2019 +0200 @@ -39,6 +39,9 @@ UCX_TEST(test_ucx_array_free); UCX_TEST(test_ucx_array_new); UCX_TEST(test_ucx_array_at); +UCX_TEST(test_ucx_array_append_from); +UCX_TEST(test_ucx_array_prepend_from); +UCX_TEST(test_ucx_array_set_from); UCX_TEST(test_ucx_array_append); UCX_TEST(test_ucx_array_prepend); UCX_TEST(test_ucx_array_set);
--- a/test/main.c Sat Aug 10 09:47:59 2019 +0200 +++ b/test/main.c Sat Aug 10 11:12:49 2019 +0200 @@ -146,6 +146,9 @@ 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_from); + ucx_test_register(suite, test_ucx_array_prepend_from); + ucx_test_register(suite, test_ucx_array_set_from); ucx_test_register(suite, test_ucx_array_append); ucx_test_register(suite, test_ucx_array_prepend); ucx_test_register(suite, test_ucx_array_set);
