changeset
merges master changes
Sat, 10 Aug 2019 08:47:25 +0200
- author
- Mike Becker <universe@uap-core.de>
- date
- Sat, 10 Aug 2019 08:47:25 +0200
- branch
- feature/array
- changeset 352
- 83888029778a
- parent 350
- 82a88d938108 (diff)
- parent 351
- 87c22ec6a0fd (current diff)
- child 353
- 135ce35d5108
merges master changes
--- a/configure.ac Sat Aug 10 08:46:38 2019 +0200 +++ b/configure.ac Sat Aug 10 08:47:25 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: @@ -28,8 +28,8 @@ # the package version must match the macros in ucx.h # the lib version must follow the libtool versioning convention -AC_INIT([ucx], [2.0.0], [olaf.wintermann@gmail.com]) -AC_SUBST([UCX_LIB_VERSION], [3:0:0]) +AC_INIT([ucx], [2.1.0], [olaf.wintermann@gmail.com]) +AC_SUBST([UCX_LIB_VERSION], [4:0:1]) # don't place everything in the project root AC_CONFIG_AUX_DIR([build-aux])
--- a/docs/src/header.html Sat Aug 10 08:46:38 2019 +0200 +++ b/docs/src/header.html Sat Aug 10 08:47:25 2019 +0200 @@ -21,6 +21,7 @@ <li><a href="modules.html">Modules</a> <ul> <li><a href="modules.html#allocator">Allocator</a></li> + <li><a href="modules.html#array">Array</a></li> <li><a href="modules.html#avl-tree">AVL Tree</a></li> <li><a href="modules.html#buffer">Buffer</a></li> <li><a href="modules.html#list">List</a></li>
--- a/docs/src/modules.md Sat Aug 10 08:46:38 2019 +0200 +++ b/docs/src/modules.md Sat Aug 10 08:47:25 2019 +0200 @@ -15,11 +15,12 @@ <div id="modules" align="center"> ------------------------ ---------------------- ---------------------------- ------------------------- -[Allocator](#allocator) [AVL Tree](#avl-tree) [Buffer](#buffer) [List](#list) -[Logging](#logging) [Map](#map) [Memory Pool](#memory-pool) [Properties](#properties) -[Stack](#stack) [String](#string) [Testing](#testing) [Utilities](#utilities) ------------------------ ---------------------- ---------------------------- ------------------------- +----------------------- ---------------------- -------------------------------- --------------------------- +[String](#string) [Buffer](#buffer) +[Allocator](#allocator) [Stack](#stack) [Memory Pool](#memory-pool) +[Array](#array) [List](#list) [Map](#map) [AVL Tree](#avl-tree) +[Logging](#logging) [Testing](#testing) [Utilities](#utilities) [Properties](#properties) +----------------------- ---------------------- -------------------------------- --------------------------- </div> @@ -41,6 +42,60 @@ can be provided to the memory management functions. One example is the [UCX Memory Pool](#memory-pool). +## Array + +*Header file:* [array.h](api/array_8h.html) +*Required modules:* [Allocator](#allocator) + +The UCX Array is an implementation of a dynamic array with automatic +reallocation. The array structure contains a capacity, the current size, +the size of each element, the raw pointer to the memory area and an allocator. +Unlike an [UcxList](#list), the array structure is typically passed by value, +unless it is subjected to change. Arrays are in most cases much faster than +linked list. + +### Remove duplicates from an array of strings + +The following example shows, how a `UcxArray` can be built with +a standard dynamic C array (pointer+length) as basis. + +```C +#include <stdio.h> +#include <ucx/array.h> +#include <ucx/string.h> +#include <ucx/utils.h> + +UcxArray remove_duplicates(sstr_t* array, size_t arrlen) { + // worst case is no duplicates, hence the capacity is set to arrlen + UcxArray result = ucx_array_new(arrlen, sizeof(sstr_t)); + // only append elements, if they are not already present in the array + for (size_t i = 0 ; i < arrlen ; ++i) { + if (!ucx_array_contains(result, array+i, ucx_cmp_sstr, NULL)) { + ucx_array_append(&result, array+i); + } + } + // make the array as small as possible + ucx_array_shrink(&result); + return result; +} + +/* ... */ + +sstr_t* array = /* some standard array of strings */ +size_t arrlen = /* the length of the array */ + +UcxArray result = remove_duplicates(array,arrlen); + +/* Iterate over the array and print the elements */ +for (size_t i = 0 ; i < result.size ; i++) { + sstr_t s = ucx_array_at_typed(sstr_t, result, i); + printf("%" PRIsstr "\n", SFMT(s)); +} + +/* Free the array. */ +ucx_array_free(&result); +``` + ## AVL Tree *Header file:* [avl.h](api/avl_8h.html) @@ -195,6 +250,8 @@ Assume you are given an array of `sstr_t` and want to create a list of these strings without duplicates. +This is a similar example to the one [above](#array), but here we are +using a `UcxList`. ```C #include <stdio.h> #include <ucx/list.h>
--- a/src/Makefile.am Sat Aug 10 08:46:38 2019 +0200 +++ b/src/Makefile.am Sat Aug 10 08:47:25 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
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/array.c Sat Aug 10 08:47:25 2019 +0200 @@ -0,0 +1,387 @@ +/* + * 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. + */ + +#define _GNU_SOURCE /* we want to use qsort_r(), if available */ +#define __STDC_WANT_LIB_EXT1__ 1 /* use qsort_s, if available */ + + +#include "ucx/array.h" +#include "ucx/utils.h" + +#include <string.h> +#include <stdlib.h> + +#ifndef UCX_ARRAY_DISABLE_QSORT +#ifdef __GLIBC__ +#if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8) +#define ucx_array_sort_impl qsort_r +#endif /* glibc version >= 2.8 */ +#elif /* not __GLIBC__ */ defined(__APPLE__) || defined(__FreeBSD__) +#define ucx_array_sort_impl ucx_qsort_r +#define USE_UCX_QSORT_R +#elif /* not (__APPLE || __FreeBSD__) */ defined(__sun) +#if __STDC_VERSION__ >= 201112L +#define ucx_array_sort_impl qsort_s +#endif +#endif /* __GLIBC__, __APLE__, __FreeBSD__, __sun */ +#endif /* UCX_ARRAY_DISABLE_QSORT */ + +#ifndef ucx_array_sort_impl +#define ucx_array_sort_impl ucx_mergesort +#endif + +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; + + 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) { + + 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) { + 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) { + 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_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_concat(UcxArray *array1, const UcxArray *array2) { + + 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) { + 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) { + + 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; +} + +static void ucx_mergesort_merge(void *arrdata,size_t elemsize, + cmp_func cmpfnc, void *data, + size_t start, size_t mid, size_t end) { + + char* array = arrdata; + + size_t rightstart = mid + 1; + + if (cmpfnc(array + mid*elemsize, + array + rightstart*elemsize, data) <= 0) { + /* already sorted */ + return; + } + + /* we need memory for one element */ + void *value = malloc(elemsize); + + while (start <= mid && rightstart <= end) { + if (cmpfnc(array + start*elemsize, + array + rightstart*elemsize, data) <= 0) { + start++; + } else { + /* save the value from the right */ + memcpy(value, array + rightstart*elemsize, elemsize); + + /* shift all left elements one element to the right */ + size_t shiftcount = rightstart-start; + void *startptr = array + start*elemsize; + void *dest = array + (start+1)*elemsize; + memmove(dest, startptr, shiftcount*elemsize); + + /* bring the first value from the right to the left */ + memcpy(startptr, value, elemsize); + + start++; + mid++; + rightstart++; + } + } + + /* free the temporary memory */ + free(value); +} + +static void ucx_mergesort_impl(void *arrdata, size_t elemsize, + cmp_func cmpfnc, void *data, size_t l, size_t r) { + if (l < r) { + size_t m = l + (r - l) / 2; + + ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m); + ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r); + ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r); + } +} + +static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize, + cmp_func cmpfnc, void *data) { + + ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1); +} + +#ifdef USE_UCX_QSORT_R +struct cmpfnc_swapargs_info { + cmp_func func; + void *data; +}; + +static int cmp_func_swap_args(void *data, const void *x, const void *y) { + cmpfnc_swapargs_info* info = data; + return info->func(x, y, info->data); +} + +static void ucx_qsort_r(void *array, size_t count, size_t elemsize, + cmp_func cmpfnc, void *data) { + struct cmpfnc_swapargs_info info; + info.func = cmpfnc; + info.data = data; + qsort_r(array, count, elemsize, &info, cmp_func_swap_args); +} +#endif /* USE_UCX_QSORT_R */ + +void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) { + ucx_array_sort_impl(array.data, array.size, array.elemsize, cmpfnc, data); +} + +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) { + 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) { + 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) { + 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/list.c Sat Aug 10 08:46:38 2019 +0200 +++ b/src/list.c Sat Aug 10 08:47:25 2019 +0200 @@ -206,7 +206,7 @@ return s; } -static UcxList *ucx_list_sort_merge(int length, +static UcxList *ucx_list_sort_merge(size_t length, UcxList* ls, UcxList* le, UcxList* re, cmp_func fnc, void* data) { @@ -214,7 +214,7 @@ UcxList *rc, *lc; lc = ls; rc = le; - int n = 0; + size_t n = 0; while (lc && lc != le && rc != re) { if (fnc(lc->data, rc->data, data) <= 0) { sorted[n] = lc; @@ -255,7 +255,7 @@ } UcxList *lc; - int ln = 1; + size_t ln = 1; UcxList *ls = l, *le, *re; @@ -271,7 +271,7 @@ return l; // this list is already sorted :) } else { UcxList *rc; - int rn = 1; + size_t rn = 1; rc = le; // skip already sorted elements while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/ucx/array.h Sat Aug 10 08:47:25 2019 +0200 @@ -0,0 +1,315 @@ +/* + * 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 <code>NULL</code>) + * @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 <code>NULL</code>) + * @return zero on success, non-zero if a reallocation was necessary but failed + */ +int ucx_array_prepend(UcxArray *array, void *data); + + +/** + * 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. + * + * @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>) + * @return zero on success, non-zero if a reallocation was necessary but failed + */ +int ucx_array_set(UcxArray *array, size_t index, 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 <code>NULL</code>, + * if the index is greater than the array size + */ +void *ucx_array_at(UcxArray array, size_t index); + +/** + * 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 the best available sort algorithm. + * + * The qsort_r() function is used, if available (glibc, FreeBSD or MacOS). + * The order of arguments is automatically adjusted for the FreeBSD and MacOS + * version of qsort_r(). + * + * If qsort_r() is not available, a merge sort algorithm is used, which is + * guaranteed to use no more additional memory than for exactly one element. + * + * @param array 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() or <code>NULL</code> + */ +void 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 */ +
--- a/src/ucx/ucx.h Sat Aug 10 08:46:38 2019 +0200 +++ b/src/ucx/ucx.h Sat Aug 10 08:47:25 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)
--- a/src/ucx/utils.h Sat Aug 10 08:46:38 2019 +0200 +++ b/src/ucx/utils.h Sat Aug 10 08:47:25 2019 +0200 @@ -184,6 +184,105 @@ */ int ucx_cmp_longint(const void *i1, const void *i2, void *data); +/** + * Compares two integers of type long long. + * @param i1 pointer to long long one + * @param i2 pointer to long long two + * @param data omitted + * @return -1, if *i1 is less than *i2, 0 if both are equal, + * 1 if *i1 is greater than *i2 + */ +int ucx_cmp_longlong(const void *i1, const void *i2, void *data); + +/** + * Compares two integers of type int16_t. + * @param i1 pointer to int16_t one + * @param i2 pointer to int16_t two + * @param data omitted + * @return -1, if *i1 is less than *i2, 0 if both are equal, + * 1 if *i1 is greater than *i2 + */ +int ucx_cmp_int16(const void *i1, const void *i2, void *data); + +/** + * Compares two integers of type int32_t. + * @param i1 pointer to int32_t one + * @param i2 pointer to int32_t two + * @param data omitted + * @return -1, if *i1 is less than *i2, 0 if both are equal, + * 1 if *i1 is greater than *i2 + */ +int ucx_cmp_int32(const void *i1, const void *i2, void *data); + +/** + * Compares two integers of type int64_t. + * @param i1 pointer to int64_t one + * @param i2 pointer to int64_t two + * @param data omitted + * @return -1, if *i1 is less than *i2, 0 if both are equal, + * 1 if *i1 is greater than *i2 + */ +int ucx_cmp_int64(const void *i1, const void *i2, void *data); + +/** + * Compares two integers of type unsigned int. + * @param i1 pointer to unsigned integer one + * @param i2 pointer to unsigned integer two + * @param data omitted + * @return -1, if *i1 is less than *i2, 0 if both are equal, + * 1 if *i1 is greater than *i2 + */ +int ucx_cmp_uint(const void *i1, const void *i2, void *data); + +/** + * Compares two integers of type unsigned long int. + * @param i1 pointer to unsigned long integer one + * @param i2 pointer to unsigned long integer two + * @param data omitted + * @return -1, if *i1 is less than *i2, 0 if both are equal, + * 1 if *i1 is greater than *i2 + */ +int ucx_cmp_ulongint(const void *i1, const void *i2, void *data); + +/** + * Compares two integers of type unsigned long long. + * @param i1 pointer to unsigned long long one + * @param i2 pointer to unsigned long long two + * @param data omitted + * @return -1, if *i1 is less than *i2, 0 if both are equal, + * 1 if *i1 is greater than *i2 + */ +int ucx_cmp_ulonglong(const void *i1, const void *i2, void *data); + +/** + * Compares two integers of type uint16_t. + * @param i1 pointer to uint16_t one + * @param i2 pointer to uint16_t two + * @param data omitted + * @return -1, if *i1 is less than *i2, 0 if both are equal, + * 1 if *i1 is greater than *i2 + */ +int ucx_cmp_uint16(const void *i1, const void *i2, void *data); + +/** + * Compares two integers of type uint32_t. + * @param i1 pointer to uint32_t one + * @param i2 pointer to uint32_t two + * @param data omitted + * @return -1, if *i1 is less than *i2, 0 if both are equal, + * 1 if *i1 is greater than *i2 + */ +int ucx_cmp_uint32(const void *i1, const void *i2, void *data); + +/** + * Compares two integers of type uint64_t. + * @param i1 pointer to uint64_t one + * @param i2 pointer to uint64_t two + * @param data omitted + * @return -1, if *i1 is less than *i2, 0 if both are equal, + * 1 if *i1 is greater than *i2 + */ +int ucx_cmp_uint64(const void *i1, const void *i2, void *data); /** * Distance function for integers of type int. @@ -204,6 +303,96 @@ intmax_t ucx_dist_longint(const void *i1, const void *i2, void *data); /** + * Distance function for integers of type long long. + * @param i1 pointer to long long one + * @param i2 pointer to long long two + * @param data omitted + * @return i1 minus i2 + */ +intmax_t ucx_dist_longlong(const void *i1, const void *i2, void *data); + +/** + * Distance function for integers of type int16_t. + * @param i1 pointer to int16_t one + * @param i2 pointer to int16_t two + * @param data omitted + * @return i1 minus i2 + */ +intmax_t ucx_dist_int16(const void *i1, const void *i2, void *data); + +/** + * Distance function for integers of type int32_t. + * @param i1 pointer to int32_t one + * @param i2 pointer to int32_t two + * @param data omitted + * @return i1 minus i2 + */ +intmax_t ucx_dist_int32(const void *i1, const void *i2, void *data); + +/** + * Distance function for integers of type int64_t. + * @param i1 pointer to int64_t one + * @param i2 pointer to int64_t two + * @param data omitted + * @return i1 minus i2 + */ +intmax_t ucx_dist_int64(const void *i1, const void *i2, void *data); + +/** + * Distance function for integers of type unsigned int. + * @param i1 pointer to unsigned integer one + * @param i2 pointer to unsigned integer two + * @param data omitted + * @return i1 minus i2 + */ +intmax_t ucx_dist_uint(const void *i1, const void *i2, void *data); + +/** + * Distance function for integers of type unsigned long int. + * @param i1 pointer to unsigned long integer one + * @param i2 pointer to unsigned long integer two + * @param data omitted + * @return i1 minus i2 + */ +intmax_t ucx_dist_ulongint(const void *i1, const void *i2, void *data); + +/** + * Distance function for integers of type unsigned long long. + * @param i1 pointer to unsigned long long one + * @param i2 pointer to unsigned long long two + * @param data omitted + * @return i1 minus i2 + */ +intmax_t ucx_dist_ulonglong(const void *i1, const void *i2, void *data); + +/** + * Distance function for integers of type uint16_t. + * @param i1 pointer to uint16_t one + * @param i2 pointer to uint16_t two + * @param data omitted + * @return i1 minus i2 + */ +intmax_t ucx_dist_uint16(const void *i1, const void *i2, void *data); + +/** + * Distance function for integers of type uint32_t. + * @param i1 pointer to uint32_t one + * @param i2 pointer to uint32_t two + * @param data omitted + * @return i1 minus i2 + */ +intmax_t ucx_dist_uint32(const void *i1, const void *i2, void *data); + +/** + * Distance function for integers of type uint64_t. + * @param i1 pointer to uint64_t one + * @param i2 pointer to uint64_t two + * @param data omitted + * @return i1 minus i2 + */ +intmax_t ucx_dist_uint64(const void *i1, const void *i2, void *data); + +/** * Compares two real numbers of type float. * @param f1 pointer to float one * @param f2 pointer to float two
--- a/src/utils.c Sat Aug 10 08:46:38 2019 +0200 +++ b/src/utils.c Sat Aug 10 08:47:25 2019 +0200 @@ -113,8 +113,108 @@ } int ucx_cmp_longint(const void *i1, const void *i2, void *data) { - int a = *((const long int*) i1); - int b = *((const long int*) i2); + long int a = *((const long int*) i1); + long int b = *((const long int*) i2); + if (a == b) { + return 0; + } else { + return a < b ? -1 : 1; + } +} + +int ucx_cmp_longlong(const void *i1, const void *i2, void *data) { + long long a = *((const long long*) i1); + long long b = *((const long long*) i2); + if (a == b) { + return 0; + } else { + return a < b ? -1 : 1; + } +} + +int ucx_cmp_int16(const void *i1, const void *i2, void *data) { + int16_t a = *((const int16_t*) i1); + int16_t b = *((const int16_t*) i2); + if (a == b) { + return 0; + } else { + return a < b ? -1 : 1; + } +} + +int ucx_cmp_int32(const void *i1, const void *i2, void *data) { + int32_t a = *((const int32_t*) i1); + int32_t b = *((const int32_t*) i2); + if (a == b) { + return 0; + } else { + return a < b ? -1 : 1; + } +} + +int ucx_cmp_int64(const void *i1, const void *i2, void *data) { + int64_t a = *((const int64_t*) i1); + int64_t b = *((const int64_t*) i2); + if (a == b) { + return 0; + } else { + return a < b ? -1 : 1; + } +} + +int ucx_cmp_uint(const void *i1, const void *i2, void *data) { + unsigned int a = *((const unsigned int*) i1); + unsigned int b = *((const unsigned int*) i2); + if (a == b) { + return 0; + } else { + return a < b ? -1 : 1; + } +} + +int ucx_cmp_ulongint(const void *i1, const void *i2, void *data) { + unsigned long int a = *((const unsigned long int*) i1); + unsigned long int b = *((const unsigned long int*) i2); + if (a == b) { + return 0; + } else { + return a < b ? -1 : 1; + } +} + +int ucx_cmp_ulonglong(const void *i1, const void *i2, void *data) { + unsigned long long a = *((const unsigned long long*) i1); + unsigned long long b = *((const unsigned long long*) i2); + if (a == b) { + return 0; + } else { + return a < b ? -1 : 1; + } +} + +int ucx_cmp_uint16(const void *i1, const void *i2, void *data) { + uint16_t a = *((const uint16_t*) i1); + uint16_t b = *((const uint16_t*) i2); + if (a == b) { + return 0; + } else { + return a < b ? -1 : 1; + } +} + +int ucx_cmp_uint32(const void *i1, const void *i2, void *data) { + uint32_t a = *((const uint32_t*) i1); + uint32_t b = *((const uint32_t*) i2); + if (a == b) { + return 0; + } else { + return a < b ? -1 : 1; + } +} + +int ucx_cmp_uint64(const void *i1, const void *i2, void *data) { + uint64_t a = *((const uint64_t*) i1); + uint64_t b = *((const uint64_t*) i2); if (a == b) { return 0; } else { @@ -134,6 +234,66 @@ return a - b; } +intmax_t ucx_dist_longlong(const void *i1, const void *i2, void *data) { + intmax_t a = *((const long long*) i1); + intmax_t b = *((const long long*) i2); + return a - b; +} + +intmax_t ucx_dist_int16(const void *i1, const void *i2, void *data) { + intmax_t a = *((const int16_t*) i1); + intmax_t b = *((const int16_t*) i2); + return a - b; +} + +intmax_t ucx_dist_int32(const void *i1, const void *i2, void *data) { + intmax_t a = *((const int32_t*) i1); + intmax_t b = *((const int32_t*) i2); + return a - b; +} + +intmax_t ucx_dist_int64(const void *i1, const void *i2, void *data) { + intmax_t a = *((const int64_t*) i1); + intmax_t b = *((const int64_t*) i2); + return a - b; +} + +intmax_t ucx_dist_uint(const void *i1, const void *i2, void *data) { + uintmax_t a = *((const unsigned int*) i1); + uintmax_t b = *((const unsigned int*) i2); + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); +} + +intmax_t ucx_dist_ulongint(const void *i1, const void *i2, void *data) { + uintmax_t a = *((const unsigned long int*) i1); + uintmax_t b = *((const unsigned long int*) i2); + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); +} + +intmax_t ucx_dist_ulonglong(const void *i1, const void *i2, void *data) { + uintmax_t a = *((const unsigned long long*) i1); + uintmax_t b = *((const unsigned long long*) i2); + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); +} + +intmax_t ucx_dist_uint16(const void *i1, const void *i2, void *data) { + uintmax_t a = *((const uint16_t*) i1); + uintmax_t b = *((const uint16_t*) i2); + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); +} + +intmax_t ucx_dist_uint32(const void *i1, const void *i2, void *data) { + uintmax_t a = *((const uint32_t*) i1); + uintmax_t b = *((const uint32_t*) i2); + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); +} + +intmax_t ucx_dist_uint64(const void *i1, const void *i2, void *data) { + uintmax_t a = *((const uint64_t*) i1); + uintmax_t b = *((const uint64_t*) i2); + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); +} + int ucx_cmp_float(const void *f1, const void *f2, void *epsilon) { float a = *((const float*) f1); float b = *((const float*) f2);
--- a/test/Makefile.am Sat Aug 10 08:46:38 2019 +0200 +++ b/test/Makefile.am Sat Aug 10 08:47:25 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
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/array_tests.c Sat Aug 10 08:47:25 2019 +0200 @@ -0,0 +1,542 @@ +/* + * 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/utils.h> + +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 *elements; + + int x = 42; + ucx_array_append(&array, &x); + UCX_TEST_BEGIN + + 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(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(elements[2] == 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_END + + ucx_array_free(&array); +} + +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 + + 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(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(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_free(&array); +} + +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); + + 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); + + 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_END + + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_equals) { + UcxArray a1 = ucx_array_new(16, sizeof(int32_t)); + UcxArray a2 = ucx_array_new(16, sizeof(int32_t)); + UcxArray a3 = ucx_array_new(16, sizeof(int64_t)); + UcxArray a4 = ucx_array_new(16, sizeof(int32_t)); + + int32_t *intelems; + int64_t *longintelems; + + a1.size = 5; + intelems = a1.data; + intelems[0] = 47; + intelems[1] = 11; + intelems[2] = 0; + intelems[3] = 8; + intelems[4] = 15; + a2.size = 5; + intelems = a2.data; + intelems[0] = 47; + intelems[1] = 11; + intelems[2] = 0; + intelems[3] = 8; + intelems[4] = 15; + a3.size = 5; + longintelems = a3.data; + longintelems[0] = 47; + longintelems[1] = 11; + longintelems[2] = 0; + longintelems[3] = 8; + longintelems[4] = 15; + a4.size = 5; + intelems = a4.data; + intelems[0] = 47; + intelems[1] = 11; + intelems[2] = -6; + intelems[3] = 8; + intelems[4] = 15; + + UCX_TEST_BEGIN + + UCX_TEST_ASSERT(ucx_array_equals(a1, a2, ucx_cmp_int32, NULL), "failed"); + UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, ucx_cmp_int32, NULL), "failed"); + UCX_TEST_ASSERT(!ucx_array_equals(a4, a1, ucx_cmp_int32, NULL), "failed"); + UCX_TEST_ASSERT(!ucx_array_equals(a1, a3, ucx_cmp_int64, NULL), + "comparing arrays of different element size shall fail"); + UCX_TEST_ASSERT(!ucx_array_equals(a3, a1, ucx_cmp_int64, NULL), + "comparing arrays of different element size shall fail"); + + UCX_TEST_ASSERT(ucx_array_equals(a1, a2, NULL, NULL), + "compare using memcmp() failed"); + UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, NULL, NULL), + "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)); + int *elems; + + a1.size = 2; + elems = a1.data; + elems[0] = 47; + elems[1] = 11; + a2.size = 3; + 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"); + 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), + "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(*(int*)ucx_array_at(array, 1) == 13, "failed"); + *(int*)ucx_array_at(array, 1) = 80; + UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 1) == 80, "assignment failed"); + + UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 0) == 42, "corrupted data"); + UCX_TEST_ASSERT(*(int*)ucx_array_at(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; + elems = array.data; + elems[0] = 47; + elems[1] = 11; + elems[2] = 0; + elems[3] = 8; + elems[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)); + int *elems; + + array.size = 5; + elems = array.data; + elems[0] = 47; + elems[1] = 11; + elems[2] = 0; + elems[3] = 8; + elems[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)); + int *elems; + + array.size = 5; + 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( + 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( + 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"); + + UCX_TEST_END + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_clone) { + UcxArray array = ucx_array_new(16, sizeof(int)); + int *elems; + + array.size = 5; + 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 + + UCX_TEST_ASSERT(array.data != copy.data, "no true copy"); + 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 + + ucx_array_free(&array); + 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) { + int *elems; + + UcxArray array = ucx_array_new(16, sizeof(int)); + array.size = 5; + 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; + 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 + void* original_ptr = array.data; + 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_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++) { + ((int*)array.data)[i]= ((i%2==0)?-1:1) * ((int) i); + ((int*)expected.data)[i] = (-30+2*i) - (i > 15 ? 1 : 0); + } + + /* 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 + + ucx_array_free(&expected); + ucx_array_free(&array); +} + +UCX_TEST(test_ucx_array_autogrow) { + int *elems; + UcxArray array = ucx_array_new(4, sizeof(int)); + array.size = 3; + elems = array.data; + elems[0] = 47; + elems[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); + 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(elems[3] == 5 && elems[4] == 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); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/array_tests.h Sat Aug 10 08:47:25 2019 +0200 @@ -0,0 +1,62 @@ +/* + * 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 <ucx/array.h> +#include <ucx/test.h> + +#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_set); +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 */ +
--- a/test/main.c Sat Aug 10 08:46:38 2019 +0200 +++ b/test/main.c Sat Aug 10 08:47:25 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,25 @@ 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_set); + 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);
