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
1.1 --- a/configure.ac Sat Aug 10 08:46:38 2019 +0200 1.2 +++ b/configure.ac Sat Aug 10 08:47:25 2019 +0200 1.3 @@ -1,7 +1,7 @@ 1.4 # 1.5 # DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 1.6 # 1.7 -# Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. 1.8 +# Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. 1.9 # 1.10 # Redistribution and use in source and binary forms, with or without 1.11 # modification, are permitted provided that the following conditions are met: 1.12 @@ -28,8 +28,8 @@ 1.13 1.14 # the package version must match the macros in ucx.h 1.15 # the lib version must follow the libtool versioning convention 1.16 -AC_INIT([ucx], [2.0.0], [olaf.wintermann@gmail.com]) 1.17 -AC_SUBST([UCX_LIB_VERSION], [3:0:0]) 1.18 +AC_INIT([ucx], [2.1.0], [olaf.wintermann@gmail.com]) 1.19 +AC_SUBST([UCX_LIB_VERSION], [4:0:1]) 1.20 1.21 # don't place everything in the project root 1.22 AC_CONFIG_AUX_DIR([build-aux])
2.1 --- a/docs/src/header.html Sat Aug 10 08:46:38 2019 +0200 2.2 +++ b/docs/src/header.html Sat Aug 10 08:47:25 2019 +0200 2.3 @@ -21,6 +21,7 @@ 2.4 <li><a href="modules.html">Modules</a> 2.5 <ul> 2.6 <li><a href="modules.html#allocator">Allocator</a></li> 2.7 + <li><a href="modules.html#array">Array</a></li> 2.8 <li><a href="modules.html#avl-tree">AVL Tree</a></li> 2.9 <li><a href="modules.html#buffer">Buffer</a></li> 2.10 <li><a href="modules.html#list">List</a></li>
3.1 --- a/docs/src/modules.md Sat Aug 10 08:46:38 2019 +0200 3.2 +++ b/docs/src/modules.md Sat Aug 10 08:47:25 2019 +0200 3.3 @@ -15,11 +15,12 @@ 3.4 3.5 <div id="modules" align="center"> 3.6 3.7 ------------------------ ---------------------- ---------------------------- ------------------------- 3.8 -[Allocator](#allocator) [AVL Tree](#avl-tree) [Buffer](#buffer) [List](#list) 3.9 -[Logging](#logging) [Map](#map) [Memory Pool](#memory-pool) [Properties](#properties) 3.10 -[Stack](#stack) [String](#string) [Testing](#testing) [Utilities](#utilities) 3.11 ------------------------ ---------------------- ---------------------------- ------------------------- 3.12 +----------------------- ---------------------- -------------------------------- --------------------------- 3.13 +[String](#string) [Buffer](#buffer) 3.14 +[Allocator](#allocator) [Stack](#stack) [Memory Pool](#memory-pool) 3.15 +[Array](#array) [List](#list) [Map](#map) [AVL Tree](#avl-tree) 3.16 +[Logging](#logging) [Testing](#testing) [Utilities](#utilities) [Properties](#properties) 3.17 +----------------------- ---------------------- -------------------------------- --------------------------- 3.18 3.19 </div> 3.20 3.21 @@ -41,6 +42,60 @@ 3.22 can be provided to the memory management functions. One example is the 3.23 [UCX Memory Pool](#memory-pool). 3.24 3.25 +## Array 3.26 + 3.27 +*Header file:* [array.h](api/array_8h.html) 3.28 +*Required modules:* [Allocator](#allocator) 3.29 + 3.30 +The UCX Array is an implementation of a dynamic array with automatic 3.31 +reallocation. The array structure contains a capacity, the current size, 3.32 +the size of each element, the raw pointer to the memory area and an allocator. 3.33 +Unlike an [UcxList](#list), the array structure is typically passed by value, 3.34 +unless it is subjected to change. Arrays are in most cases much faster than 3.35 +linked list. 3.36 + 3.37 +### Remove duplicates from an array of strings 3.38 + 3.39 +The following example shows, how a `UcxArray` can be built with 3.40 +a standard dynamic C array (pointer+length) as basis. 3.41 + 3.42 +```C 3.43 +#include <stdio.h> 3.44 +#include <ucx/array.h> 3.45 +#include <ucx/string.h> 3.46 +#include <ucx/utils.h> 3.47 + 3.48 +UcxArray remove_duplicates(sstr_t* array, size_t arrlen) { 3.49 + // worst case is no duplicates, hence the capacity is set to arrlen 3.50 + UcxArray result = ucx_array_new(arrlen, sizeof(sstr_t)); 3.51 + // only append elements, if they are not already present in the array 3.52 + for (size_t i = 0 ; i < arrlen ; ++i) { 3.53 + if (!ucx_array_contains(result, array+i, ucx_cmp_sstr, NULL)) { 3.54 + ucx_array_append(&result, array+i); 3.55 + } 3.56 + } 3.57 + // make the array as small as possible 3.58 + ucx_array_shrink(&result); 3.59 + return result; 3.60 +} 3.61 + 3.62 +/* ... */ 3.63 + 3.64 +sstr_t* array = /* some standard array of strings */ 3.65 +size_t arrlen = /* the length of the array */ 3.66 + 3.67 +UcxArray result = remove_duplicates(array,arrlen); 3.68 + 3.69 +/* Iterate over the array and print the elements */ 3.70 +for (size_t i = 0 ; i < result.size ; i++) { 3.71 + sstr_t s = ucx_array_at_typed(sstr_t, result, i); 3.72 + printf("%" PRIsstr "\n", SFMT(s)); 3.73 +} 3.74 + 3.75 +/* Free the array. */ 3.76 +ucx_array_free(&result); 3.77 +``` 3.78 + 3.79 ## AVL Tree 3.80 3.81 *Header file:* [avl.h](api/avl_8h.html) 3.82 @@ -195,6 +250,8 @@ 3.83 3.84 Assume you are given an array of `sstr_t` and want to create a list of these 3.85 strings without duplicates. 3.86 +This is a similar example to the one [above](#array), but here we are 3.87 +using a `UcxList`. 3.88 ```C 3.89 #include <stdio.h> 3.90 #include <ucx/list.h>
4.1 --- a/src/Makefile.am Sat Aug 10 08:46:38 2019 +0200 4.2 +++ b/src/Makefile.am Sat Aug 10 08:47:25 2019 +0200 4.3 @@ -29,6 +29,7 @@ 4.4 lib_LTLIBRARIES = libucx.la 4.5 libucx_la_LDFLAGS = -version-info $(UCX_LIB_VERSION) 4.6 libucx_la_SOURCES = utils.c 4.7 +libucx_la_SOURCES += array.c 4.8 libucx_la_SOURCES += list.c 4.9 libucx_la_SOURCES += map.c 4.10 libucx_la_SOURCES += avl.c 4.11 @@ -44,6 +45,7 @@ 4.12 4.13 ucxdir = $(includedir)/ucx 4.14 ucx_HEADERS = ucx/allocator.h 4.15 +ucx_HEADERS += ucx/array.h 4.16 ucx_HEADERS += ucx/avl.h 4.17 ucx_HEADERS += ucx/buffer.h 4.18 ucx_HEADERS += ucx/list.h
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 5.2 +++ b/src/array.c Sat Aug 10 08:47:25 2019 +0200 5.3 @@ -0,0 +1,387 @@ 5.4 +/* 5.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 5.6 + * 5.7 + * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. 5.8 + * 5.9 + * Redistribution and use in source and binary forms, with or without 5.10 + * modification, are permitted provided that the following conditions are met: 5.11 + * 5.12 + * 1. Redistributions of source code must retain the above copyright 5.13 + * notice, this list of conditions and the following disclaimer. 5.14 + * 5.15 + * 2. Redistributions in binary form must reproduce the above copyright 5.16 + * notice, this list of conditions and the following disclaimer in the 5.17 + * documentation and/or other materials provided with the distribution. 5.18 + * 5.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 5.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 5.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 5.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 5.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 5.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 5.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 5.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 5.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 5.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 5.29 + * POSSIBILITY OF SUCH DAMAGE. 5.30 + */ 5.31 + 5.32 +#define _GNU_SOURCE /* we want to use qsort_r(), if available */ 5.33 +#define __STDC_WANT_LIB_EXT1__ 1 /* use qsort_s, if available */ 5.34 + 5.35 + 5.36 +#include "ucx/array.h" 5.37 +#include "ucx/utils.h" 5.38 + 5.39 +#include <string.h> 5.40 +#include <stdlib.h> 5.41 + 5.42 +#ifndef UCX_ARRAY_DISABLE_QSORT 5.43 +#ifdef __GLIBC__ 5.44 +#if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8) 5.45 +#define ucx_array_sort_impl qsort_r 5.46 +#endif /* glibc version >= 2.8 */ 5.47 +#elif /* not __GLIBC__ */ defined(__APPLE__) || defined(__FreeBSD__) 5.48 +#define ucx_array_sort_impl ucx_qsort_r 5.49 +#define USE_UCX_QSORT_R 5.50 +#elif /* not (__APPLE || __FreeBSD__) */ defined(__sun) 5.51 +#if __STDC_VERSION__ >= 201112L 5.52 +#define ucx_array_sort_impl qsort_s 5.53 +#endif 5.54 +#endif /* __GLIBC__, __APLE__, __FreeBSD__, __sun */ 5.55 +#endif /* UCX_ARRAY_DISABLE_QSORT */ 5.56 + 5.57 +#ifndef ucx_array_sort_impl 5.58 +#define ucx_array_sort_impl ucx_mergesort 5.59 +#endif 5.60 + 5.61 +UcxArray ucx_array_new(size_t capacity, size_t elemsize) { 5.62 + return ucx_array_new_a(capacity, elemsize, ucx_default_allocator()); 5.63 +} 5.64 + 5.65 +UcxArray ucx_array_new_a(size_t capacity, size_t elemsize, 5.66 + UcxAllocator* allocator) { 5.67 + UcxArray array; 5.68 + 5.69 + array.allocator = allocator; 5.70 + array.elemsize = elemsize; 5.71 + array.size = 0; 5.72 + array.data = alcalloc(allocator, capacity, elemsize); 5.73 + 5.74 + if (array.data) { 5.75 + array.capacity = capacity; 5.76 + } else { 5.77 + array.capacity = 0; 5.78 + } 5.79 + 5.80 + return array; 5.81 +} 5.82 + 5.83 +UcxArray ucx_array_clone(UcxArray array) { 5.84 + UcxArray clone; 5.85 + 5.86 + clone.allocator = array.allocator; 5.87 + clone.elemsize = array.elemsize; 5.88 + clone.size = array.size; 5.89 + clone.data = alcalloc(array.allocator, array.capacity, array.elemsize); 5.90 + 5.91 + if (clone.data) { 5.92 + clone.capacity = array.capacity; 5.93 + memcpy(clone.data, array.data, array.size*array.elemsize); 5.94 + } else { 5.95 + clone.capacity = clone.size = 0; 5.96 + } 5.97 + 5.98 + return clone; 5.99 +} 5.100 + 5.101 +int ucx_array_equals(UcxArray array1, UcxArray array2, 5.102 + cmp_func cmpfnc, void* data) { 5.103 + 5.104 + if (array1.size != array2.size || array1.elemsize != array2.elemsize) { 5.105 + return 0; 5.106 + } else { 5.107 + if (array1.size == 0) 5.108 + return 1; 5.109 + 5.110 + if (cmpfnc == NULL) { 5.111 + cmpfnc = ucx_cmp_mem; 5.112 + data = &array1.elemsize; 5.113 + } 5.114 + 5.115 + for (size_t i = 0 ; i < array1.size ; i++) { 5.116 + int r = cmpfnc( 5.117 + ucx_array_at(array1, i), 5.118 + ucx_array_at(array2, i), 5.119 + data); 5.120 + if (r != 0) 5.121 + return 0; 5.122 + } 5.123 + return 1; 5.124 + } 5.125 +} 5.126 + 5.127 +void ucx_array_free(UcxArray *array) { 5.128 + alfree(array->allocator, array->data); 5.129 + array->data = NULL; 5.130 + array->capacity = array->size = 0; 5.131 +} 5.132 + 5.133 +int ucx_array_append(UcxArray *array, void *data) { 5.134 + if (array->size == array->capacity) { 5.135 + if (ucx_array_reserve(array, array->capacity*2)) { 5.136 + return 1; 5.137 + } 5.138 + } 5.139 + 5.140 + void* dest = ucx_array_at(*array, array->size++); 5.141 + if (data) { 5.142 + memcpy(dest, data, array->elemsize); 5.143 + } else { 5.144 + memset(dest, 0, array->elemsize); 5.145 + } 5.146 + 5.147 + return 0; 5.148 +} 5.149 + 5.150 +int ucx_array_prepend(UcxArray *array, void *data) { 5.151 + if (array->size == array->capacity) { 5.152 + if (ucx_array_reserve(array, array->capacity*2)) { 5.153 + return 1; 5.154 + } 5.155 + } 5.156 + 5.157 + array->size++; 5.158 + 5.159 + if (array->size > 1) { 5.160 + void *dest = ucx_array_at(*array,1); 5.161 + memmove(dest, array->data, array->elemsize*array->size); 5.162 + } 5.163 + 5.164 + if (data) { 5.165 + memcpy(array->data, data, array->elemsize); 5.166 + } else { 5.167 + memset(array->data, 0, array->elemsize); 5.168 + } 5.169 + 5.170 + return 0; 5.171 +} 5.172 + 5.173 +int ucx_array_set(UcxArray *array, size_t index, void *data) { 5.174 + if (index >= array->size) { 5.175 + if (ucx_array_reserve(array, index+1)) { 5.176 + return 1; 5.177 + } 5.178 + array->size = index+1; 5.179 + } 5.180 + 5.181 + void *dest = ucx_array_at(*array, index); 5.182 + if (data) { 5.183 + memcpy(dest, data, array->elemsize); 5.184 + } else { 5.185 + memset(dest, 0, array->elemsize); 5.186 + } 5.187 + 5.188 + return 0; 5.189 +} 5.190 + 5.191 +int ucx_array_concat(UcxArray *array1, const UcxArray *array2) { 5.192 + 5.193 + if (array1->elemsize != array2->elemsize) 5.194 + return 1; 5.195 + 5.196 + size_t capacity = array1->capacity+array2->capacity; 5.197 + 5.198 + if (array1->capacity < capacity) { 5.199 + if (ucx_array_reserve(array1, capacity)) { 5.200 + return 1; 5.201 + } 5.202 + } 5.203 + 5.204 + void* dest = ucx_array_at(*array1, array1->size); 5.205 + memcpy(dest, array2->data, array2->size*array2->elemsize); 5.206 + 5.207 + array1->size += array2->size; 5.208 + 5.209 + return 0; 5.210 +} 5.211 + 5.212 +void *ucx_array_at(UcxArray array, size_t index) { 5.213 + char* memory = array.data; 5.214 + char* loc = memory + index*array.elemsize; 5.215 + return loc; 5.216 +} 5.217 + 5.218 +size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) { 5.219 + 5.220 + if (cmpfnc == NULL) { 5.221 + cmpfnc = ucx_cmp_mem; 5.222 + data = &array.elemsize; 5.223 + } 5.224 + 5.225 + if (array.size > 0) { 5.226 + for (size_t i = 0 ; i < array.size ; i++) { 5.227 + void* ptr = ucx_array_at(array, i); 5.228 + if (cmpfnc(ptr, elem, data) == 0) { 5.229 + return i; 5.230 + } 5.231 + } 5.232 + return array.size; 5.233 + } else { 5.234 + return 0; 5.235 + } 5.236 +} 5.237 + 5.238 +int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) { 5.239 + return ucx_array_find(array, elem, cmpfnc, data) != array.size; 5.240 +} 5.241 + 5.242 +static void ucx_mergesort_merge(void *arrdata,size_t elemsize, 5.243 + cmp_func cmpfnc, void *data, 5.244 + size_t start, size_t mid, size_t end) { 5.245 + 5.246 + char* array = arrdata; 5.247 + 5.248 + size_t rightstart = mid + 1; 5.249 + 5.250 + if (cmpfnc(array + mid*elemsize, 5.251 + array + rightstart*elemsize, data) <= 0) { 5.252 + /* already sorted */ 5.253 + return; 5.254 + } 5.255 + 5.256 + /* we need memory for one element */ 5.257 + void *value = malloc(elemsize); 5.258 + 5.259 + while (start <= mid && rightstart <= end) { 5.260 + if (cmpfnc(array + start*elemsize, 5.261 + array + rightstart*elemsize, data) <= 0) { 5.262 + start++; 5.263 + } else { 5.264 + /* save the value from the right */ 5.265 + memcpy(value, array + rightstart*elemsize, elemsize); 5.266 + 5.267 + /* shift all left elements one element to the right */ 5.268 + size_t shiftcount = rightstart-start; 5.269 + void *startptr = array + start*elemsize; 5.270 + void *dest = array + (start+1)*elemsize; 5.271 + memmove(dest, startptr, shiftcount*elemsize); 5.272 + 5.273 + /* bring the first value from the right to the left */ 5.274 + memcpy(startptr, value, elemsize); 5.275 + 5.276 + start++; 5.277 + mid++; 5.278 + rightstart++; 5.279 + } 5.280 + } 5.281 + 5.282 + /* free the temporary memory */ 5.283 + free(value); 5.284 +} 5.285 + 5.286 +static void ucx_mergesort_impl(void *arrdata, size_t elemsize, 5.287 + cmp_func cmpfnc, void *data, size_t l, size_t r) { 5.288 + if (l < r) { 5.289 + size_t m = l + (r - l) / 2; 5.290 + 5.291 + ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m); 5.292 + ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r); 5.293 + ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r); 5.294 + } 5.295 +} 5.296 + 5.297 +static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize, 5.298 + cmp_func cmpfnc, void *data) { 5.299 + 5.300 + ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1); 5.301 +} 5.302 + 5.303 +#ifdef USE_UCX_QSORT_R 5.304 +struct cmpfnc_swapargs_info { 5.305 + cmp_func func; 5.306 + void *data; 5.307 +}; 5.308 + 5.309 +static int cmp_func_swap_args(void *data, const void *x, const void *y) { 5.310 + cmpfnc_swapargs_info* info = data; 5.311 + return info->func(x, y, info->data); 5.312 +} 5.313 + 5.314 +static void ucx_qsort_r(void *array, size_t count, size_t elemsize, 5.315 + cmp_func cmpfnc, void *data) { 5.316 + struct cmpfnc_swapargs_info info; 5.317 + info.func = cmpfnc; 5.318 + info.data = data; 5.319 + qsort_r(array, count, elemsize, &info, cmp_func_swap_args); 5.320 +} 5.321 +#endif /* USE_UCX_QSORT_R */ 5.322 + 5.323 +void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) { 5.324 + ucx_array_sort_impl(array.data, array.size, array.elemsize, cmpfnc, data); 5.325 +} 5.326 + 5.327 +void ucx_array_remove(UcxArray *array, size_t index) { 5.328 + array->size--; 5.329 + if (index < array->size) { 5.330 + void* dest = ucx_array_at(*array, index); 5.331 + void* src = ucx_array_at(*array, index+1); 5.332 + memmove(dest, src, (array->size - index)*array->elemsize); 5.333 + } 5.334 +} 5.335 + 5.336 +void ucx_array_remove_fast(UcxArray *array, size_t index) { 5.337 + array->size--; 5.338 + if (index < array->size) { 5.339 + void* dest = ucx_array_at(*array, index); 5.340 + void* src = ucx_array_at(*array, array->size); 5.341 + memcpy(dest, src, array->elemsize); 5.342 + } 5.343 +} 5.344 + 5.345 +int ucx_array_shrink(UcxArray* array) { 5.346 + void* newptr = alrealloc(array->allocator, array->data, 5.347 + array->size*array->elemsize); 5.348 + if (newptr) { 5.349 + array->data = newptr; 5.350 + array->capacity = array->size; 5.351 + return 0; 5.352 + } else { 5.353 + return 1; 5.354 + } 5.355 +} 5.356 + 5.357 +int ucx_array_resize(UcxArray* array, size_t capacity) { 5.358 + if (array->capacity >= capacity) { 5.359 + void* newptr = alrealloc(array->allocator, array->data, 5.360 + capacity*array->elemsize); 5.361 + if (newptr) { 5.362 + array->data = newptr; 5.363 + array->capacity = capacity; 5.364 + if (array->size > array->capacity) { 5.365 + array->size = array->capacity; 5.366 + } 5.367 + return 0; 5.368 + } else { 5.369 + return 1; 5.370 + } 5.371 + } else { 5.372 + return ucx_array_reserve(array, capacity); 5.373 + } 5.374 +} 5.375 + 5.376 +int ucx_array_reserve(UcxArray* array, size_t capacity) { 5.377 + if (array->capacity > capacity) { 5.378 + return 0; 5.379 + } else { 5.380 + void* newptr = alrealloc(array->allocator, array->data, 5.381 + capacity*array->elemsize); 5.382 + if (newptr) { 5.383 + array->data = newptr; 5.384 + array->capacity = capacity; 5.385 + return 0; 5.386 + } else { 5.387 + return 1; 5.388 + } 5.389 + } 5.390 +}
6.1 --- a/src/list.c Sat Aug 10 08:46:38 2019 +0200 6.2 +++ b/src/list.c Sat Aug 10 08:47:25 2019 +0200 6.3 @@ -206,7 +206,7 @@ 6.4 return s; 6.5 } 6.6 6.7 -static UcxList *ucx_list_sort_merge(int length, 6.8 +static UcxList *ucx_list_sort_merge(size_t length, 6.9 UcxList* ls, UcxList* le, UcxList* re, 6.10 cmp_func fnc, void* data) { 6.11 6.12 @@ -214,7 +214,7 @@ 6.13 UcxList *rc, *lc; 6.14 6.15 lc = ls; rc = le; 6.16 - int n = 0; 6.17 + size_t n = 0; 6.18 while (lc && lc != le && rc != re) { 6.19 if (fnc(lc->data, rc->data, data) <= 0) { 6.20 sorted[n] = lc; 6.21 @@ -255,7 +255,7 @@ 6.22 } 6.23 6.24 UcxList *lc; 6.25 - int ln = 1; 6.26 + size_t ln = 1; 6.27 6.28 UcxList *ls = l, *le, *re; 6.29 6.30 @@ -271,7 +271,7 @@ 6.31 return l; // this list is already sorted :) 6.32 } else { 6.33 UcxList *rc; 6.34 - int rn = 1; 6.35 + size_t rn = 1; 6.36 rc = le; 6.37 // skip already sorted elements 6.38 while (rc->next != NULL && fnc(rc->next->data, rc->data, data) > 0) {
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 7.2 +++ b/src/ucx/array.h Sat Aug 10 08:47:25 2019 +0200 7.3 @@ -0,0 +1,315 @@ 7.4 +/* 7.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 7.6 + * 7.7 + * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. 7.8 + * 7.9 + * Redistribution and use in source and binary forms, with or without 7.10 + * modification, are permitted provided that the following conditions are met: 7.11 + * 7.12 + * 1. Redistributions of source code must retain the above copyright 7.13 + * notice, this list of conditions and the following disclaimer. 7.14 + * 7.15 + * 2. Redistributions in binary form must reproduce the above copyright 7.16 + * notice, this list of conditions and the following disclaimer in the 7.17 + * documentation and/or other materials provided with the distribution. 7.18 + * 7.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 7.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 7.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 7.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 7.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 7.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 7.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 7.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 7.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 7.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 7.29 + * POSSIBILITY OF SUCH DAMAGE. 7.30 + */ 7.31 +/** 7.32 + * Dynamically allocated array implementation. 7.33 + * 7.34 + * @file array.h 7.35 + * @author Mike Becker 7.36 + * @author Olaf Wintermann 7.37 + */ 7.38 + 7.39 +#ifndef UCX_ARRAY_H 7.40 +#define UCX_ARRAY_H 7.41 + 7.42 +#include "ucx.h" 7.43 +#include "allocator.h" 7.44 + 7.45 +#ifdef __cplusplus 7.46 +extern "C" { 7.47 +#endif 7.48 + 7.49 +/** 7.50 + * UCX array type. 7.51 + */ 7.52 +typedef struct { 7.53 + /** 7.54 + * The current capacity of the array. 7.55 + */ 7.56 + size_t capacity; 7.57 + /** 7.58 + * The actual number of elements in the array. 7.59 + */ 7.60 + size_t size; 7.61 + /** 7.62 + * The size of an individual element in bytes. 7.63 + */ 7.64 + size_t elemsize; 7.65 + /** 7.66 + * A pointer to the data. 7.67 + */ 7.68 + void* data; 7.69 + /** 7.70 + * The allocator used for the data. 7.71 + */ 7.72 + UcxAllocator* allocator; 7.73 +} UcxArray; 7.74 + 7.75 + 7.76 +/** 7.77 + * Creates a new UCX array with the given capacity and element size. 7.78 + * @param capacity the initial capacity 7.79 + * @param elemsize the element size 7.80 + * @return a new UCX array structure 7.81 + */ 7.82 +UcxArray ucx_array_new(size_t capacity, size_t elemsize); 7.83 + 7.84 +/** 7.85 + * Creates a new UCX array using the specified allocator. 7.86 + * 7.87 + * @param capacity the initial capacity 7.88 + * @param elemsize the element size 7.89 + * @param allocator the allocator to use 7.90 + * @return a new UCX array structure 7.91 + */ 7.92 +UcxArray ucx_array_new_a(size_t capacity, size_t elemsize, 7.93 + UcxAllocator* allocator); 7.94 + 7.95 +/** 7.96 + * Creates an shallow copy of an array. 7.97 + * 7.98 + * This function clones the specified array by using memcpy(). 7.99 + * 7.100 + * @param array the array to copy 7.101 + * @return the copy (may be an empty array on allocation errors) 7.102 + */ 7.103 +UcxArray ucx_array_clone(UcxArray array); 7.104 + 7.105 + 7.106 +/** 7.107 + * Compares two UCX arrays element-wise by using a compare function. 7.108 + * 7.109 + * Elements of the two specified arrays are compared by using the specified 7.110 + * compare function and the additional data. The type and content of this 7.111 + * additional data depends on the cmp_func() used. 7.112 + * 7.113 + * This function always returns zero, if the element sizes of the arrays do 7.114 + * not match and performs no comparisons in this case. 7.115 + * 7.116 + * @param array1 the first array 7.117 + * @param array2 the second array 7.118 + * @param cmpfnc the compare function 7.119 + * @param data additional data for the compare function 7.120 + * @return 1, if and only if the two arrays equal element-wise, 0 otherwise 7.121 + */ 7.122 +int ucx_array_equals(UcxArray array1, UcxArray array2, 7.123 + cmp_func cmpfnc, void* data); 7.124 + 7.125 +/** 7.126 + * Destroys the array. 7.127 + * 7.128 + * The data is freed and both capacity and count are reset to zero. 7.129 + * If the array structure itself has been dynamically allocated, it has to be 7.130 + * freed separately. 7.131 + * 7.132 + * @param array the array to free 7.133 + */ 7.134 +void ucx_array_free(UcxArray *array); 7.135 + 7.136 +/** 7.137 + * Inserts an element at the end of the array. 7.138 + * 7.139 + * This is an O(1) operation. 7.140 + * The array will automatically grow, if the capacity is exceeded. 7.141 + * If a pointer to data is provided, the data is copied into the array with 7.142 + * memcpy(). Otherwise the new element is completely zeroed. 7.143 + * 7.144 + * @param array a pointer the array where to append the data 7.145 + * @param data a pointer to the data to insert (may be <code>NULL</code>) 7.146 + * @return zero on success, non-zero if a reallocation was necessary but failed 7.147 + */ 7.148 +int ucx_array_append(UcxArray *array, void *data); 7.149 + 7.150 + 7.151 +/** 7.152 + * Inserts an element at the beginning of the array. 7.153 + * 7.154 + * This is an expensive operation, because the contents must be moved. 7.155 + * If there is no particular reason to prepend data, you should use 7.156 + * ucx_array_append() instead. 7.157 + * 7.158 + * @param array a pointer the array where to prepend the data 7.159 + * @param data a pointer to the data to insert (may be <code>NULL</code>) 7.160 + * @return zero on success, non-zero if a reallocation was necessary but failed 7.161 + */ 7.162 +int ucx_array_prepend(UcxArray *array, void *data); 7.163 + 7.164 + 7.165 +/** 7.166 + * Sets an element at the specified index. 7.167 + * 7.168 + * If the index is out of bounds, the array automatically grows. 7.169 + * The pointer to the data may be NULL, in which case the element is zeroed. 7.170 + * 7.171 + * @param array a pointer the array where to set the data 7.172 + * @param index the index of the element to set 7.173 + * @param data a pointer to the data to insert (may be <code>NULL</code>) 7.174 + * @return zero on success, non-zero if a reallocation was necessary but failed 7.175 + */ 7.176 +int ucx_array_set(UcxArray *array, size_t index, void *data); 7.177 + 7.178 +/** 7.179 + * Concatenates two arrays. 7.180 + * 7.181 + * The contents of the second array are appended to the first array in one 7.182 + * single operation. The second array is otherwise left untouched. 7.183 + * 7.184 + * The first array may grow automatically. If this fails, both arrays remain 7.185 + * unmodified. 7.186 + * 7.187 + * @param array1 first array 7.188 + * @param array2 second array 7.189 + * @return zero on success, non-zero if reallocation was necessary but failed 7.190 + * or the element size does not match 7.191 + */ 7.192 +int ucx_array_concat(UcxArray *array1, const UcxArray *array2); 7.193 + 7.194 +/** 7.195 + * Returns a pointer to the array element at the specified index. 7.196 + * 7.197 + * @param array the array to retrieve the element from 7.198 + * @param index index of the element to return 7.199 + * @return a pointer to the element at the specified index or <code>NULL</code>, 7.200 + * if the index is greater than the array size 7.201 + */ 7.202 +void *ucx_array_at(UcxArray array, size_t index); 7.203 + 7.204 +/** 7.205 + * Returns the index of an element containing the specified data. 7.206 + * 7.207 + * This function uses a cmp_func() to compare the data of each list element 7.208 + * with the specified data. If no cmp_func is provided, memcmp() is used. 7.209 + * 7.210 + * If the array contains the data more than once, the index of the first 7.211 + * occurrence is returned. 7.212 + * If the array does not contain the data, the size of array is returned. 7.213 + * 7.214 + * @param array the array where to search for the data 7.215 + * @param elem the element data 7.216 + * @param cmpfnc the compare function 7.217 + * @param data additional data for the compare function 7.218 + * @return the index of the element containing the specified data or the size of 7.219 + * the array, if the data is not found in this array 7.220 + */ 7.221 +size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data); 7.222 + 7.223 +/** 7.224 + * Checks, if an array contains a specific element. 7.225 + * 7.226 + * An element is found, if ucx_array_find() returns a value less than the size. 7.227 + * 7.228 + * @param array the array where to search for the data 7.229 + * @param elem the element data 7.230 + * @param cmpfnc the compare function 7.231 + * @param data additional data for the compare function 7.232 + * @return 1, if and only if the array contains the specified element data 7.233 + * @see ucx_array_find() 7.234 + */ 7.235 +int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data); 7.236 + 7.237 +/** 7.238 + * Sorts a UcxArray with the best available sort algorithm. 7.239 + * 7.240 + * The qsort_r() function is used, if available (glibc, FreeBSD or MacOS). 7.241 + * The order of arguments is automatically adjusted for the FreeBSD and MacOS 7.242 + * version of qsort_r(). 7.243 + * 7.244 + * If qsort_r() is not available, a merge sort algorithm is used, which is 7.245 + * guaranteed to use no more additional memory than for exactly one element. 7.246 + * 7.247 + * @param array the array to sort 7.248 + * @param cmpfnc the function that shall be used to compare the element data 7.249 + * @param data additional data for the cmp_func() or <code>NULL</code> 7.250 + */ 7.251 +void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data); 7.252 + 7.253 +/** 7.254 + * Removes an element from the array. 7.255 + * 7.256 + * This is in general an expensive operation, because several elements may 7.257 + * be moved. If the order of the elements is not relevant, use 7.258 + * ucx_array_remove_fast() instead. 7.259 + * 7.260 + * @param array pointer to the array from which the element shall be removed 7.261 + * @param index the index of the element to remove 7.262 + */ 7.263 +void ucx_array_remove(UcxArray *array, size_t index); 7.264 + 7.265 +/** 7.266 + * Removes an element from the array. 7.267 + * 7.268 + * This is an O(1) operation, but does not maintain the order of the elements. 7.269 + * The last element in the array is moved to the location of the removed 7.270 + * element. 7.271 + * 7.272 + * @param array pointer to the array from which the element shall be removed 7.273 + * @param index the index of the element to remove 7.274 + */ 7.275 +void ucx_array_remove_fast(UcxArray *array, size_t index); 7.276 + 7.277 +/** 7.278 + * Shrinks the memory to exactly fit the contents. 7.279 + * 7.280 + * After this operation, the capacity equals the size. 7.281 + * 7.282 + * @param array a pointer to the array 7.283 + * @return zero on success, non-zero if reallocation failed 7.284 + */ 7.285 +int ucx_array_shrink(UcxArray* array); 7.286 + 7.287 +/** 7.288 + * Sets the capacity of the array. 7.289 + * 7.290 + * If the new capacity is smaller than the size of the array, the elements 7.291 + * are removed and the size is adjusted accordingly. 7.292 + * 7.293 + * @param array a pointer to the array 7.294 + * @param capacity the new capacity 7.295 + * @return zero on success, non-zero if reallocation failed 7.296 + */ 7.297 +int ucx_array_resize(UcxArray* array, size_t capacity); 7.298 + 7.299 +/** 7.300 + * Resizes the array only, if the capacity is insufficient. 7.301 + * 7.302 + * If the requested capacity is smaller than the current capacity, this 7.303 + * function does nothing. 7.304 + * 7.305 + * @param array a pointer to the array 7.306 + * @param capacity the guaranteed capacity 7.307 + * @return zero on success, non-zero if reallocation failed 7.308 + */ 7.309 +int ucx_array_reserve(UcxArray* array, size_t capacity); 7.310 + 7.311 + 7.312 + 7.313 +#ifdef __cplusplus 7.314 +} 7.315 +#endif 7.316 + 7.317 +#endif /* UCX_ARRAY_H */ 7.318 +
8.1 --- a/src/ucx/ucx.h Sat Aug 10 08:46:38 2019 +0200 8.2 +++ b/src/ucx/ucx.h Sat Aug 10 08:47:25 2019 +0200 8.3 @@ -1,7 +1,7 @@ 8.4 /* 8.5 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 8.6 * 8.7 - * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved. 8.8 + * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. 8.9 * 8.10 * Redistribution and use in source and binary forms, with or without 8.11 * modification, are permitted provided that the following conditions are met: 8.12 @@ -40,7 +40,7 @@ 8.13 #define UCX_VERSION_MAJOR 2 8.14 8.15 /** Minor UCX version as integer constant. */ 8.16 -#define UCX_VERSION_MINOR 0 8.17 +#define UCX_VERSION_MINOR 1 8.18 8.19 /** Version constant which ensures to increase monotonically. */ 8.20 #define UCX_VERSION (((UCX_VERSION_MAJOR)<<16)|UCX_VERSION_MINOR)
9.1 --- a/src/ucx/utils.h Sat Aug 10 08:46:38 2019 +0200 9.2 +++ b/src/ucx/utils.h Sat Aug 10 08:47:25 2019 +0200 9.3 @@ -184,6 +184,105 @@ 9.4 */ 9.5 int ucx_cmp_longint(const void *i1, const void *i2, void *data); 9.6 9.7 +/** 9.8 + * Compares two integers of type long long. 9.9 + * @param i1 pointer to long long one 9.10 + * @param i2 pointer to long long two 9.11 + * @param data omitted 9.12 + * @return -1, if *i1 is less than *i2, 0 if both are equal, 9.13 + * 1 if *i1 is greater than *i2 9.14 + */ 9.15 +int ucx_cmp_longlong(const void *i1, const void *i2, void *data); 9.16 + 9.17 +/** 9.18 + * Compares two integers of type int16_t. 9.19 + * @param i1 pointer to int16_t one 9.20 + * @param i2 pointer to int16_t two 9.21 + * @param data omitted 9.22 + * @return -1, if *i1 is less than *i2, 0 if both are equal, 9.23 + * 1 if *i1 is greater than *i2 9.24 + */ 9.25 +int ucx_cmp_int16(const void *i1, const void *i2, void *data); 9.26 + 9.27 +/** 9.28 + * Compares two integers of type int32_t. 9.29 + * @param i1 pointer to int32_t one 9.30 + * @param i2 pointer to int32_t two 9.31 + * @param data omitted 9.32 + * @return -1, if *i1 is less than *i2, 0 if both are equal, 9.33 + * 1 if *i1 is greater than *i2 9.34 + */ 9.35 +int ucx_cmp_int32(const void *i1, const void *i2, void *data); 9.36 + 9.37 +/** 9.38 + * Compares two integers of type int64_t. 9.39 + * @param i1 pointer to int64_t one 9.40 + * @param i2 pointer to int64_t two 9.41 + * @param data omitted 9.42 + * @return -1, if *i1 is less than *i2, 0 if both are equal, 9.43 + * 1 if *i1 is greater than *i2 9.44 + */ 9.45 +int ucx_cmp_int64(const void *i1, const void *i2, void *data); 9.46 + 9.47 +/** 9.48 + * Compares two integers of type unsigned int. 9.49 + * @param i1 pointer to unsigned integer one 9.50 + * @param i2 pointer to unsigned integer two 9.51 + * @param data omitted 9.52 + * @return -1, if *i1 is less than *i2, 0 if both are equal, 9.53 + * 1 if *i1 is greater than *i2 9.54 + */ 9.55 +int ucx_cmp_uint(const void *i1, const void *i2, void *data); 9.56 + 9.57 +/** 9.58 + * Compares two integers of type unsigned long int. 9.59 + * @param i1 pointer to unsigned long integer one 9.60 + * @param i2 pointer to unsigned long integer two 9.61 + * @param data omitted 9.62 + * @return -1, if *i1 is less than *i2, 0 if both are equal, 9.63 + * 1 if *i1 is greater than *i2 9.64 + */ 9.65 +int ucx_cmp_ulongint(const void *i1, const void *i2, void *data); 9.66 + 9.67 +/** 9.68 + * Compares two integers of type unsigned long long. 9.69 + * @param i1 pointer to unsigned long long one 9.70 + * @param i2 pointer to unsigned long long two 9.71 + * @param data omitted 9.72 + * @return -1, if *i1 is less than *i2, 0 if both are equal, 9.73 + * 1 if *i1 is greater than *i2 9.74 + */ 9.75 +int ucx_cmp_ulonglong(const void *i1, const void *i2, void *data); 9.76 + 9.77 +/** 9.78 + * Compares two integers of type uint16_t. 9.79 + * @param i1 pointer to uint16_t one 9.80 + * @param i2 pointer to uint16_t two 9.81 + * @param data omitted 9.82 + * @return -1, if *i1 is less than *i2, 0 if both are equal, 9.83 + * 1 if *i1 is greater than *i2 9.84 + */ 9.85 +int ucx_cmp_uint16(const void *i1, const void *i2, void *data); 9.86 + 9.87 +/** 9.88 + * Compares two integers of type uint32_t. 9.89 + * @param i1 pointer to uint32_t one 9.90 + * @param i2 pointer to uint32_t two 9.91 + * @param data omitted 9.92 + * @return -1, if *i1 is less than *i2, 0 if both are equal, 9.93 + * 1 if *i1 is greater than *i2 9.94 + */ 9.95 +int ucx_cmp_uint32(const void *i1, const void *i2, void *data); 9.96 + 9.97 +/** 9.98 + * Compares two integers of type uint64_t. 9.99 + * @param i1 pointer to uint64_t one 9.100 + * @param i2 pointer to uint64_t two 9.101 + * @param data omitted 9.102 + * @return -1, if *i1 is less than *i2, 0 if both are equal, 9.103 + * 1 if *i1 is greater than *i2 9.104 + */ 9.105 +int ucx_cmp_uint64(const void *i1, const void *i2, void *data); 9.106 9.107 /** 9.108 * Distance function for integers of type int. 9.109 @@ -204,6 +303,96 @@ 9.110 intmax_t ucx_dist_longint(const void *i1, const void *i2, void *data); 9.111 9.112 /** 9.113 + * Distance function for integers of type long long. 9.114 + * @param i1 pointer to long long one 9.115 + * @param i2 pointer to long long two 9.116 + * @param data omitted 9.117 + * @return i1 minus i2 9.118 + */ 9.119 +intmax_t ucx_dist_longlong(const void *i1, const void *i2, void *data); 9.120 + 9.121 +/** 9.122 + * Distance function for integers of type int16_t. 9.123 + * @param i1 pointer to int16_t one 9.124 + * @param i2 pointer to int16_t two 9.125 + * @param data omitted 9.126 + * @return i1 minus i2 9.127 + */ 9.128 +intmax_t ucx_dist_int16(const void *i1, const void *i2, void *data); 9.129 + 9.130 +/** 9.131 + * Distance function for integers of type int32_t. 9.132 + * @param i1 pointer to int32_t one 9.133 + * @param i2 pointer to int32_t two 9.134 + * @param data omitted 9.135 + * @return i1 minus i2 9.136 + */ 9.137 +intmax_t ucx_dist_int32(const void *i1, const void *i2, void *data); 9.138 + 9.139 +/** 9.140 + * Distance function for integers of type int64_t. 9.141 + * @param i1 pointer to int64_t one 9.142 + * @param i2 pointer to int64_t two 9.143 + * @param data omitted 9.144 + * @return i1 minus i2 9.145 + */ 9.146 +intmax_t ucx_dist_int64(const void *i1, const void *i2, void *data); 9.147 + 9.148 +/** 9.149 + * Distance function for integers of type unsigned int. 9.150 + * @param i1 pointer to unsigned integer one 9.151 + * @param i2 pointer to unsigned integer two 9.152 + * @param data omitted 9.153 + * @return i1 minus i2 9.154 + */ 9.155 +intmax_t ucx_dist_uint(const void *i1, const void *i2, void *data); 9.156 + 9.157 +/** 9.158 + * Distance function for integers of type unsigned long int. 9.159 + * @param i1 pointer to unsigned long integer one 9.160 + * @param i2 pointer to unsigned long integer two 9.161 + * @param data omitted 9.162 + * @return i1 minus i2 9.163 + */ 9.164 +intmax_t ucx_dist_ulongint(const void *i1, const void *i2, void *data); 9.165 + 9.166 +/** 9.167 + * Distance function for integers of type unsigned long long. 9.168 + * @param i1 pointer to unsigned long long one 9.169 + * @param i2 pointer to unsigned long long two 9.170 + * @param data omitted 9.171 + * @return i1 minus i2 9.172 + */ 9.173 +intmax_t ucx_dist_ulonglong(const void *i1, const void *i2, void *data); 9.174 + 9.175 +/** 9.176 + * Distance function for integers of type uint16_t. 9.177 + * @param i1 pointer to uint16_t one 9.178 + * @param i2 pointer to uint16_t two 9.179 + * @param data omitted 9.180 + * @return i1 minus i2 9.181 + */ 9.182 +intmax_t ucx_dist_uint16(const void *i1, const void *i2, void *data); 9.183 + 9.184 +/** 9.185 + * Distance function for integers of type uint32_t. 9.186 + * @param i1 pointer to uint32_t one 9.187 + * @param i2 pointer to uint32_t two 9.188 + * @param data omitted 9.189 + * @return i1 minus i2 9.190 + */ 9.191 +intmax_t ucx_dist_uint32(const void *i1, const void *i2, void *data); 9.192 + 9.193 +/** 9.194 + * Distance function for integers of type uint64_t. 9.195 + * @param i1 pointer to uint64_t one 9.196 + * @param i2 pointer to uint64_t two 9.197 + * @param data omitted 9.198 + * @return i1 minus i2 9.199 + */ 9.200 +intmax_t ucx_dist_uint64(const void *i1, const void *i2, void *data); 9.201 + 9.202 +/** 9.203 * Compares two real numbers of type float. 9.204 * @param f1 pointer to float one 9.205 * @param f2 pointer to float two
10.1 --- a/src/utils.c Sat Aug 10 08:46:38 2019 +0200 10.2 +++ b/src/utils.c Sat Aug 10 08:47:25 2019 +0200 10.3 @@ -113,8 +113,108 @@ 10.4 } 10.5 10.6 int ucx_cmp_longint(const void *i1, const void *i2, void *data) { 10.7 - int a = *((const long int*) i1); 10.8 - int b = *((const long int*) i2); 10.9 + long int a = *((const long int*) i1); 10.10 + long int b = *((const long int*) i2); 10.11 + if (a == b) { 10.12 + return 0; 10.13 + } else { 10.14 + return a < b ? -1 : 1; 10.15 + } 10.16 +} 10.17 + 10.18 +int ucx_cmp_longlong(const void *i1, const void *i2, void *data) { 10.19 + long long a = *((const long long*) i1); 10.20 + long long b = *((const long long*) i2); 10.21 + if (a == b) { 10.22 + return 0; 10.23 + } else { 10.24 + return a < b ? -1 : 1; 10.25 + } 10.26 +} 10.27 + 10.28 +int ucx_cmp_int16(const void *i1, const void *i2, void *data) { 10.29 + int16_t a = *((const int16_t*) i1); 10.30 + int16_t b = *((const int16_t*) i2); 10.31 + if (a == b) { 10.32 + return 0; 10.33 + } else { 10.34 + return a < b ? -1 : 1; 10.35 + } 10.36 +} 10.37 + 10.38 +int ucx_cmp_int32(const void *i1, const void *i2, void *data) { 10.39 + int32_t a = *((const int32_t*) i1); 10.40 + int32_t b = *((const int32_t*) i2); 10.41 + if (a == b) { 10.42 + return 0; 10.43 + } else { 10.44 + return a < b ? -1 : 1; 10.45 + } 10.46 +} 10.47 + 10.48 +int ucx_cmp_int64(const void *i1, const void *i2, void *data) { 10.49 + int64_t a = *((const int64_t*) i1); 10.50 + int64_t b = *((const int64_t*) i2); 10.51 + if (a == b) { 10.52 + return 0; 10.53 + } else { 10.54 + return a < b ? -1 : 1; 10.55 + } 10.56 +} 10.57 + 10.58 +int ucx_cmp_uint(const void *i1, const void *i2, void *data) { 10.59 + unsigned int a = *((const unsigned int*) i1); 10.60 + unsigned int b = *((const unsigned int*) i2); 10.61 + if (a == b) { 10.62 + return 0; 10.63 + } else { 10.64 + return a < b ? -1 : 1; 10.65 + } 10.66 +} 10.67 + 10.68 +int ucx_cmp_ulongint(const void *i1, const void *i2, void *data) { 10.69 + unsigned long int a = *((const unsigned long int*) i1); 10.70 + unsigned long int b = *((const unsigned long int*) i2); 10.71 + if (a == b) { 10.72 + return 0; 10.73 + } else { 10.74 + return a < b ? -1 : 1; 10.75 + } 10.76 +} 10.77 + 10.78 +int ucx_cmp_ulonglong(const void *i1, const void *i2, void *data) { 10.79 + unsigned long long a = *((const unsigned long long*) i1); 10.80 + unsigned long long b = *((const unsigned long long*) i2); 10.81 + if (a == b) { 10.82 + return 0; 10.83 + } else { 10.84 + return a < b ? -1 : 1; 10.85 + } 10.86 +} 10.87 + 10.88 +int ucx_cmp_uint16(const void *i1, const void *i2, void *data) { 10.89 + uint16_t a = *((const uint16_t*) i1); 10.90 + uint16_t b = *((const uint16_t*) i2); 10.91 + if (a == b) { 10.92 + return 0; 10.93 + } else { 10.94 + return a < b ? -1 : 1; 10.95 + } 10.96 +} 10.97 + 10.98 +int ucx_cmp_uint32(const void *i1, const void *i2, void *data) { 10.99 + uint32_t a = *((const uint32_t*) i1); 10.100 + uint32_t b = *((const uint32_t*) i2); 10.101 + if (a == b) { 10.102 + return 0; 10.103 + } else { 10.104 + return a < b ? -1 : 1; 10.105 + } 10.106 +} 10.107 + 10.108 +int ucx_cmp_uint64(const void *i1, const void *i2, void *data) { 10.109 + uint64_t a = *((const uint64_t*) i1); 10.110 + uint64_t b = *((const uint64_t*) i2); 10.111 if (a == b) { 10.112 return 0; 10.113 } else { 10.114 @@ -134,6 +234,66 @@ 10.115 return a - b; 10.116 } 10.117 10.118 +intmax_t ucx_dist_longlong(const void *i1, const void *i2, void *data) { 10.119 + intmax_t a = *((const long long*) i1); 10.120 + intmax_t b = *((const long long*) i2); 10.121 + return a - b; 10.122 +} 10.123 + 10.124 +intmax_t ucx_dist_int16(const void *i1, const void *i2, void *data) { 10.125 + intmax_t a = *((const int16_t*) i1); 10.126 + intmax_t b = *((const int16_t*) i2); 10.127 + return a - b; 10.128 +} 10.129 + 10.130 +intmax_t ucx_dist_int32(const void *i1, const void *i2, void *data) { 10.131 + intmax_t a = *((const int32_t*) i1); 10.132 + intmax_t b = *((const int32_t*) i2); 10.133 + return a - b; 10.134 +} 10.135 + 10.136 +intmax_t ucx_dist_int64(const void *i1, const void *i2, void *data) { 10.137 + intmax_t a = *((const int64_t*) i1); 10.138 + intmax_t b = *((const int64_t*) i2); 10.139 + return a - b; 10.140 +} 10.141 + 10.142 +intmax_t ucx_dist_uint(const void *i1, const void *i2, void *data) { 10.143 + uintmax_t a = *((const unsigned int*) i1); 10.144 + uintmax_t b = *((const unsigned int*) i2); 10.145 + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); 10.146 +} 10.147 + 10.148 +intmax_t ucx_dist_ulongint(const void *i1, const void *i2, void *data) { 10.149 + uintmax_t a = *((const unsigned long int*) i1); 10.150 + uintmax_t b = *((const unsigned long int*) i2); 10.151 + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); 10.152 +} 10.153 + 10.154 +intmax_t ucx_dist_ulonglong(const void *i1, const void *i2, void *data) { 10.155 + uintmax_t a = *((const unsigned long long*) i1); 10.156 + uintmax_t b = *((const unsigned long long*) i2); 10.157 + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); 10.158 +} 10.159 + 10.160 +intmax_t ucx_dist_uint16(const void *i1, const void *i2, void *data) { 10.161 + uintmax_t a = *((const uint16_t*) i1); 10.162 + uintmax_t b = *((const uint16_t*) i2); 10.163 + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); 10.164 +} 10.165 + 10.166 +intmax_t ucx_dist_uint32(const void *i1, const void *i2, void *data) { 10.167 + uintmax_t a = *((const uint32_t*) i1); 10.168 + uintmax_t b = *((const uint32_t*) i2); 10.169 + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); 10.170 +} 10.171 + 10.172 +intmax_t ucx_dist_uint64(const void *i1, const void *i2, void *data) { 10.173 + uintmax_t a = *((const uint64_t*) i1); 10.174 + uintmax_t b = *((const uint64_t*) i2); 10.175 + return a > b ? (intmax_t)(a - b) : -(intmax_t)(b - a); 10.176 +} 10.177 + 10.178 int ucx_cmp_float(const void *f1, const void *f2, void *epsilon) { 10.179 float a = *((const float*) f1); 10.180 float b = *((const float*) f2);
11.1 --- a/test/Makefile.am Sat Aug 10 08:46:38 2019 +0200 11.2 +++ b/test/Makefile.am Sat Aug 10 08:47:25 2019 +0200 11.3 @@ -31,6 +31,7 @@ 11.4 ucxtest_CFLAGS = -I$(top_srcdir)/src 11.5 ucxtest_SOURCES = main.c 11.6 ucxtest_SOURCES += allocator_tests.c 11.7 +ucxtest_SOURCES += array_tests.c 11.8 ucxtest_SOURCES += list_tests.c 11.9 ucxtest_SOURCES += avl_tests.c 11.10 ucxtest_SOURCES += mpool_tests.c
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 12.2 +++ b/test/array_tests.c Sat Aug 10 08:47:25 2019 +0200 12.3 @@ -0,0 +1,542 @@ 12.4 +/* 12.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 12.6 + * 12.7 + * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. 12.8 + * 12.9 + * Redistribution and use in source and binary forms, with or without 12.10 + * modification, are permitted provided that the following conditions are met: 12.11 + * 12.12 + * 1. Redistributions of source code must retain the above copyright 12.13 + * notice, this list of conditions and the following disclaimer. 12.14 + * 12.15 + * 2. Redistributions in binary form must reproduce the above copyright 12.16 + * notice, this list of conditions and the following disclaimer in the 12.17 + * documentation and/or other materials provided with the distribution. 12.18 + * 12.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 12.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 12.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 12.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 12.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 12.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 12.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 12.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 12.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 12.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 12.29 + * POSSIBILITY OF SUCH DAMAGE. 12.30 + */ 12.31 + 12.32 +#include "array_tests.h" 12.33 +#include <ucx/utils.h> 12.34 + 12.35 +UCX_TEST(test_ucx_array_free) { 12.36 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.37 + 12.38 + UCX_TEST_BEGIN 12.39 + ucx_array_free(&array); 12.40 + UCX_TEST_ASSERT(array.data == NULL, "data pointer not NULL after free"); 12.41 + UCX_TEST_ASSERT(array.size == 0, "size not zero after free"); 12.42 + UCX_TEST_ASSERT(array.capacity == 0, "capacity not zero after free"); 12.43 + UCX_TEST_ASSERT(array.allocator == ucx_default_allocator(), 12.44 + "allocator corrupted during free"); 12.45 + UCX_TEST_END 12.46 +} 12.47 + 12.48 +UCX_TEST(test_ucx_array_new) { 12.49 + UcxArray array = ucx_array_new(16, 47); 12.50 + 12.51 + UCX_TEST_BEGIN 12.52 + UCX_TEST_ASSERT(array.data, "no memory allocated"); 12.53 + UCX_TEST_ASSERT(array.size == 0, "size not initially zero"); 12.54 + UCX_TEST_ASSERT(array.capacity == 16, "capacity not as requested"); 12.55 + UCX_TEST_ASSERT(array.elemsize == 47, "element size not as requested"); 12.56 + UCX_TEST_ASSERT(array.allocator == ucx_default_allocator(), 12.57 + "array not using the default allocator"); 12.58 + UCX_TEST_END 12.59 + ucx_array_free(&array); 12.60 +} 12.61 + 12.62 +UCX_TEST(test_ucx_array_append) { 12.63 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.64 + int *elements; 12.65 + 12.66 + int x = 42; 12.67 + ucx_array_append(&array, &x); 12.68 + UCX_TEST_BEGIN 12.69 + 12.70 + elements = array.data; 12.71 + UCX_TEST_ASSERT(elements[0] == 42, "failed"); 12.72 + 12.73 + x = 13; 12.74 + ucx_array_append(&array, &x); 12.75 + 12.76 + elements = array.data; 12.77 + UCX_TEST_ASSERT(array.size == 2, "incorrect size after append"); 12.78 + UCX_TEST_ASSERT(elements[1] == 13, "failed"); 12.79 + UCX_TEST_ASSERT(elements[0] == 42, 12.80 + "append corrupted previously inserted data"); 12.81 + 12.82 + ucx_array_append(&array, NULL); 12.83 + 12.84 + elements = array.data; 12.85 + UCX_TEST_ASSERT(array.size == 3, "incorrect size after NULL append"); 12.86 + UCX_TEST_ASSERT(elements[2] == 0, "element is not zeroed"); 12.87 + UCX_TEST_ASSERT(elements[0] == 42, 12.88 + "NULL append corrupted previously inserted data"); 12.89 + UCX_TEST_ASSERT(elements[1] == 13, 12.90 + "NULL append corrupted previously inserted data"); 12.91 + 12.92 + UCX_TEST_END 12.93 + 12.94 + ucx_array_free(&array); 12.95 +} 12.96 + 12.97 +UCX_TEST(test_ucx_array_prepend) { 12.98 + int *elems; 12.99 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.100 + 12.101 + int x = 42; 12.102 + ucx_array_prepend(&array, &x); 12.103 + UCX_TEST_BEGIN 12.104 + 12.105 + elems = array.data; 12.106 + UCX_TEST_ASSERT(elems[0] == 42, "failed"); 12.107 + 12.108 + x = 13; 12.109 + ucx_array_prepend(&array, &x); 12.110 + 12.111 + elems = array.data; 12.112 + UCX_TEST_ASSERT(array.size == 2, "incorrect size after prepend"); 12.113 + UCX_TEST_ASSERT(elems[0] == 13, "failed"); 12.114 + UCX_TEST_ASSERT(elems[1] == 42, 12.115 + "prepend corrupted previously inserted data"); 12.116 + 12.117 + ucx_array_prepend(&array, NULL); 12.118 + 12.119 + elems = array.data; 12.120 + UCX_TEST_ASSERT(array.size == 3, "incorrect size after NULL prepend"); 12.121 + UCX_TEST_ASSERT(elems[0] == 0, "element is not zeroed"); 12.122 + UCX_TEST_ASSERT(elems[1] == 13, 12.123 + "NULL prepend corrupted previously inserted data"); 12.124 + UCX_TEST_ASSERT(elems[2] == 42, 12.125 + "NULL prepend corrupted previously inserted data"); 12.126 + 12.127 + UCX_TEST_END 12.128 + 12.129 + ucx_array_free(&array); 12.130 +} 12.131 + 12.132 +UCX_TEST(test_ucx_array_set) { 12.133 + int *elems; 12.134 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.135 + 12.136 + 12.137 + int x = 42; 12.138 + 12.139 + UCX_TEST_BEGIN 12.140 + 12.141 + ucx_array_set(&array, 7, &x); 12.142 + 12.143 + elems = array.data; 12.144 + UCX_TEST_ASSERT(elems[7] == 42, "failed"); 12.145 + UCX_TEST_ASSERT(array.size >= 8, "array not resized on set"); 12.146 + UCX_TEST_ASSERT(array.capacity == 16, "capacity changed unnecessarily"); 12.147 + 12.148 + x = 13; 12.149 + ucx_array_set(&array, 27, &x); 12.150 + 12.151 + elems = array.data; 12.152 + UCX_TEST_ASSERT(elems[27] == 13, "failed"); 12.153 + UCX_TEST_ASSERT(array.size == 28, "array not resized on set"); 12.154 + UCX_TEST_ASSERT(array.capacity == 28, "capacity not grown"); 12.155 + 12.156 + ucx_array_set(&array, 7, NULL); 12.157 + 12.158 + elems = array.data; 12.159 + UCX_TEST_ASSERT(elems[7] == 0, "not zeroed on NULL set"); 12.160 + 12.161 + UCX_TEST_END 12.162 + 12.163 + ucx_array_free(&array); 12.164 +} 12.165 + 12.166 +UCX_TEST(test_ucx_array_equals) { 12.167 + UcxArray a1 = ucx_array_new(16, sizeof(int32_t)); 12.168 + UcxArray a2 = ucx_array_new(16, sizeof(int32_t)); 12.169 + UcxArray a3 = ucx_array_new(16, sizeof(int64_t)); 12.170 + UcxArray a4 = ucx_array_new(16, sizeof(int32_t)); 12.171 + 12.172 + int32_t *intelems; 12.173 + int64_t *longintelems; 12.174 + 12.175 + a1.size = 5; 12.176 + intelems = a1.data; 12.177 + intelems[0] = 47; 12.178 + intelems[1] = 11; 12.179 + intelems[2] = 0; 12.180 + intelems[3] = 8; 12.181 + intelems[4] = 15; 12.182 + a2.size = 5; 12.183 + intelems = a2.data; 12.184 + intelems[0] = 47; 12.185 + intelems[1] = 11; 12.186 + intelems[2] = 0; 12.187 + intelems[3] = 8; 12.188 + intelems[4] = 15; 12.189 + a3.size = 5; 12.190 + longintelems = a3.data; 12.191 + longintelems[0] = 47; 12.192 + longintelems[1] = 11; 12.193 + longintelems[2] = 0; 12.194 + longintelems[3] = 8; 12.195 + longintelems[4] = 15; 12.196 + a4.size = 5; 12.197 + intelems = a4.data; 12.198 + intelems[0] = 47; 12.199 + intelems[1] = 11; 12.200 + intelems[2] = -6; 12.201 + intelems[3] = 8; 12.202 + intelems[4] = 15; 12.203 + 12.204 + UCX_TEST_BEGIN 12.205 + 12.206 + UCX_TEST_ASSERT(ucx_array_equals(a1, a2, ucx_cmp_int32, NULL), "failed"); 12.207 + UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, ucx_cmp_int32, NULL), "failed"); 12.208 + UCX_TEST_ASSERT(!ucx_array_equals(a4, a1, ucx_cmp_int32, NULL), "failed"); 12.209 + UCX_TEST_ASSERT(!ucx_array_equals(a1, a3, ucx_cmp_int64, NULL), 12.210 + "comparing arrays of different element size shall fail"); 12.211 + UCX_TEST_ASSERT(!ucx_array_equals(a3, a1, ucx_cmp_int64, NULL), 12.212 + "comparing arrays of different element size shall fail"); 12.213 + 12.214 + UCX_TEST_ASSERT(ucx_array_equals(a1, a2, NULL, NULL), 12.215 + "compare using memcmp() failed"); 12.216 + UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, NULL, NULL), 12.217 + "compare using memcmp() failed"); 12.218 + 12.219 + UCX_TEST_END 12.220 + ucx_array_free(&a1); 12.221 + ucx_array_free(&a2); 12.222 + ucx_array_free(&a3); 12.223 + ucx_array_free(&a4); 12.224 +} 12.225 + 12.226 +UCX_TEST(test_ucx_array_concat) { 12.227 + UcxArray a1 = ucx_array_new(16, sizeof(int)); 12.228 + UcxArray a2 = ucx_array_new(16, sizeof(int)); 12.229 + int *elems; 12.230 + 12.231 + a1.size = 2; 12.232 + elems = a1.data; 12.233 + elems[0] = 47; 12.234 + elems[1] = 11; 12.235 + a2.size = 3; 12.236 + elems = a2.data; 12.237 + elems[0] = 0; 12.238 + elems[1] = 8; 12.239 + elems[2] = 15; 12.240 + 12.241 + UCX_TEST_BEGIN 12.242 + 12.243 + UCX_TEST_ASSERT(!ucx_array_concat(&a1, &a2), "failed"); 12.244 + UCX_TEST_ASSERT(a1.size == 5, "failed"); 12.245 + elems = a1.data; 12.246 + UCX_TEST_ASSERT(elems[0] == 47, "failed"); 12.247 + UCX_TEST_ASSERT(elems[1] == 11, "failed"); 12.248 + UCX_TEST_ASSERT(elems[2] == 0, "failed"); 12.249 + UCX_TEST_ASSERT(elems[3] == 8, "failed"); 12.250 + UCX_TEST_ASSERT(elems[4] == 15, "failed"); 12.251 + 12.252 + a1.elemsize *= 2; 12.253 + UCX_TEST_ASSERT(ucx_array_concat(&a1, &a2), 12.254 + "arrays of different element size must not be concatenated"); 12.255 + UCX_TEST_ASSERT(a1.size == 5, 12.256 + "arrays of different element size must not be concatenated"); 12.257 + 12.258 + UCX_TEST_END 12.259 + ucx_array_free(&a1); 12.260 + ucx_array_free(&a2); 12.261 +} 12.262 + 12.263 +UCX_TEST(test_ucx_array_at) { 12.264 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.265 + 12.266 + int x = 42; 12.267 + ucx_array_append(&array, &x); 12.268 + x = 13; 12.269 + ucx_array_append(&array, &x); 12.270 + x = 5; 12.271 + ucx_array_append(&array, &x); 12.272 + 12.273 + UCX_TEST_BEGIN 12.274 + 12.275 + UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 1) == 13, "failed"); 12.276 + *(int*)ucx_array_at(array, 1) = 80; 12.277 + UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 1) == 80, "assignment failed"); 12.278 + 12.279 + UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 0) == 42, "corrupted data"); 12.280 + UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 2) == 5, "corrupted data"); 12.281 + 12.282 + UCX_TEST_END 12.283 + 12.284 + ucx_array_free(&array); 12.285 +} 12.286 + 12.287 +UCX_TEST(test_ucx_array_find) { 12.288 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.289 + int *elems; 12.290 + 12.291 + array.size = 5; 12.292 + elems = array.data; 12.293 + elems[0] = 47; 12.294 + elems[1] = 11; 12.295 + elems[2] = 0; 12.296 + elems[3] = 8; 12.297 + elems[4] = 15; 12.298 + 12.299 + int x = 8; 12.300 + int y = 90; 12.301 + 12.302 + UCX_TEST_BEGIN 12.303 + 12.304 + UCX_TEST_ASSERT(ucx_array_find(array,(void*)&x,ucx_cmp_int,NULL) == 3, 12.305 + "doesn't find element"); 12.306 + UCX_TEST_ASSERT(ucx_array_find(array,(void*)&y,ucx_cmp_int,NULL) == 5, 12.307 + "finds non-existing element"); 12.308 + 12.309 + UCX_TEST_ASSERT(ucx_array_find(array,(void*)&x,NULL,NULL) == 3, 12.310 + "failed using memcmp()"); 12.311 + UCX_TEST_ASSERT(ucx_array_find(array,(void*)&y,NULL,NULL) == 5, 12.312 + "failed using memcmp()"); 12.313 + 12.314 + UCX_TEST_END 12.315 + ucx_array_free(&array); 12.316 +} 12.317 + 12.318 +UCX_TEST(test_ucx_array_contains) { 12.319 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.320 + int *elems; 12.321 + 12.322 + array.size = 5; 12.323 + elems = array.data; 12.324 + elems[0] = 47; 12.325 + elems[1] = 11; 12.326 + elems[2] = 0; 12.327 + elems[3] = 8; 12.328 + elems[4] = 15; 12.329 + 12.330 + int x = 8; 12.331 + int y = 90; 12.332 + 12.333 + UCX_TEST_BEGIN 12.334 + 12.335 + UCX_TEST_ASSERT(ucx_array_contains(array,(void*)&x,ucx_cmp_int,NULL), 12.336 + "false negative"); 12.337 + UCX_TEST_ASSERT(!ucx_array_contains(array,(void*)&y,ucx_cmp_int,NULL), 12.338 + "false positive"); 12.339 + 12.340 + UCX_TEST_ASSERT(ucx_array_contains(array,(void*)&x,NULL,NULL), 12.341 + "false negative using memcmp()"); 12.342 + UCX_TEST_ASSERT(!ucx_array_contains(array,(void*)&y,NULL,NULL), 12.343 + "false positive using memcmp()"); 12.344 + 12.345 + UCX_TEST_END 12.346 + ucx_array_free(&array); 12.347 +} 12.348 + 12.349 +UCX_TEST(test_ucx_array_remove) { 12.350 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.351 + int *elems; 12.352 + 12.353 + array.size = 5; 12.354 + elems = array.data; 12.355 + elems[0] = 47; 12.356 + elems[1] = 11; 12.357 + elems[2] = 0; 12.358 + elems[3] = 8; 12.359 + elems[4] = 15; 12.360 + 12.361 + UCX_TEST_BEGIN 12.362 + 12.363 + ucx_array_remove(&array, 2); 12.364 + elems = array.data; 12.365 + UCX_TEST_ASSERT( 12.366 + elems[0] == 47 && 12.367 + elems[1] == 11 && 12.368 + elems[2] == 8 && 12.369 + elems[3] == 15, 12.370 + "wrong contents after remove"); 12.371 + UCX_TEST_ASSERT(array.size == 4, "wrong size after remove"); 12.372 + 12.373 + ucx_array_remove_fast(&array, 1); 12.374 + elems = array.data; 12.375 + UCX_TEST_ASSERT( 12.376 + elems[0] == 47 && 12.377 + elems[1] == 15 && 12.378 + elems[2] == 8, 12.379 + "wrong contents after fast remove"); 12.380 + UCX_TEST_ASSERT(array.size == 3, "wrong size after fast remove"); 12.381 + 12.382 + UCX_TEST_END 12.383 + ucx_array_free(&array); 12.384 +} 12.385 + 12.386 +UCX_TEST(test_ucx_array_clone) { 12.387 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.388 + int *elems; 12.389 + 12.390 + array.size = 5; 12.391 + elems = array.data; 12.392 + elems[0] = 47; 12.393 + elems[1] = 11; 12.394 + elems[2] = 0; 12.395 + elems[3] = 8; 12.396 + elems[4] = 15; 12.397 + 12.398 + UcxArray copy = ucx_array_clone(array); 12.399 + UCX_TEST_BEGIN 12.400 + 12.401 + UCX_TEST_ASSERT(array.data != copy.data, "no true copy"); 12.402 + UCX_TEST_ASSERT(array.size == copy.size, "size mismatch"); 12.403 + UCX_TEST_ASSERT(array.capacity == copy.capacity, "capacity mismatch"); 12.404 + UCX_TEST_ASSERT(array.elemsize == copy.elemsize, "element size mismatch"); 12.405 + UCX_TEST_ASSERT(array.allocator == copy.allocator, "allocator mismatch"); 12.406 + UCX_TEST_ASSERT(ucx_array_equals(array, copy, ucx_cmp_int, NULL), "failed"); 12.407 + 12.408 + UCX_TEST_END 12.409 + 12.410 + ucx_array_free(&array); 12.411 + ucx_array_free(©); 12.412 +} 12.413 + 12.414 +static int ucx_cmp_int_reverse(const void* x, const void* y, void* data) { 12.415 + return -ucx_cmp_int(x,y,data); 12.416 +} 12.417 + 12.418 +UCX_TEST(test_ucx_array_sort) { 12.419 + int *elems; 12.420 + 12.421 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.422 + array.size = 5; 12.423 + elems = array.data; 12.424 + elems[0] = 47; 12.425 + elems[1] = 11; 12.426 + elems[2] = 0; 12.427 + elems[3] = 8; 12.428 + elems[4] = 15; 12.429 + 12.430 + UcxArray expected = ucx_array_new(16, sizeof(int)); 12.431 + expected.size = 5; 12.432 + elems = expected.data; 12.433 + elems[0] = 0; 12.434 + elems[1] = 8; 12.435 + elems[2] = 11; 12.436 + elems[3] = 15; 12.437 + elems[4] = 47; 12.438 + 12.439 + UcxArray expectedrev = ucx_array_new(16, sizeof(int)); 12.440 + expectedrev.size = 5; 12.441 + elems = expectedrev.data; 12.442 + elems[0] = 47; 12.443 + elems[1] = 15; 12.444 + elems[2] = 11; 12.445 + elems[3] = 8; 12.446 + elems[4] = 0; 12.447 + 12.448 + 12.449 + UCX_TEST_BEGIN 12.450 + void* original_ptr = array.data; 12.451 + ucx_array_sort(array, ucx_cmp_int, NULL); 12.452 + UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL), "failed"); 12.453 + UCX_TEST_ASSERT(array.size == 5, "size corrupted"); 12.454 + UCX_TEST_ASSERT(array.data == original_ptr, "shall not reallocate"); 12.455 + 12.456 + ucx_array_sort(array, ucx_cmp_int_reverse, NULL); 12.457 + UCX_TEST_ASSERT(ucx_array_equals(array, expectedrev, NULL, NULL), "failed"); 12.458 + 12.459 + ucx_array_reserve(&array, 32); 12.460 + ucx_array_reserve(&expected, 32); 12.461 + array.size = expected.size = 32; 12.462 + for (size_t i = 0 ; i < 32 ; i++) { 12.463 + ((int*)array.data)[i]= ((i%2==0)?-1:1) * ((int) i); 12.464 + ((int*)expected.data)[i] = (-30+2*i) - (i > 15 ? 1 : 0); 12.465 + } 12.466 + 12.467 + /* dummy third argument to trigger a possible fallback for qsort_s */ 12.468 + ucx_array_sort(array, ucx_cmp_int, array.data); 12.469 + UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL), 12.470 + "failed for bigger arrays"); 12.471 + UCX_TEST_END 12.472 + 12.473 + ucx_array_free(&expected); 12.474 + ucx_array_free(&array); 12.475 +} 12.476 + 12.477 +UCX_TEST(test_ucx_array_autogrow) { 12.478 + int *elems; 12.479 + UcxArray array = ucx_array_new(4, sizeof(int)); 12.480 + array.size = 3; 12.481 + elems = array.data; 12.482 + elems[0] = 47; 12.483 + elems[1] = 11; 12.484 + int x = 5; 12.485 + 12.486 + UCX_TEST_BEGIN 12.487 + 12.488 + void* oldptr = array.data; 12.489 + 12.490 + ucx_array_append(&array, &x); 12.491 + UCX_TEST_ASSERT(array.capacity == 4 && array.data == oldptr, 12.492 + "array should not grow too early"); 12.493 + ucx_array_append(&array, &x); 12.494 + elems = array.data; 12.495 + UCX_TEST_ASSERT(array.capacity == 8, "array did not grow"); 12.496 + UCX_TEST_ASSERT(array.size == 5, "incorrect size after grow"); 12.497 + UCX_TEST_ASSERT(elems[3] == 5 && elems[4] == 5, "corrupt data"); 12.498 + 12.499 + UCX_TEST_END 12.500 + ucx_array_free(&array); 12.501 +} 12.502 + 12.503 +UCX_TEST(test_ucx_array_shrink) { 12.504 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.505 + array.size = 4; 12.506 + 12.507 + UCX_TEST_BEGIN 12.508 + UCX_TEST_ASSERT(!ucx_array_shrink(&array), "failed"); 12.509 + UCX_TEST_ASSERT(array.capacity == 4, "incorrect capacity after shrink"); 12.510 + UCX_TEST_END 12.511 + ucx_array_free(&array); 12.512 +} 12.513 + 12.514 +UCX_TEST(test_ucx_array_resize) { 12.515 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.516 + array.size = 8; 12.517 + 12.518 + UCX_TEST_BEGIN 12.519 + 12.520 + UCX_TEST_ASSERT(!ucx_array_resize(&array, 32), "failed"); 12.521 + UCX_TEST_ASSERT(array.capacity == 32, "incorrect capacity after resize"); 12.522 + UCX_TEST_ASSERT(array.size == 8, "incorrect size after resize"); 12.523 + 12.524 + UCX_TEST_ASSERT(!ucx_array_resize(&array, 4), "failed"); 12.525 + UCX_TEST_ASSERT(array.capacity == 4, "incorrect capacity after resize"); 12.526 + UCX_TEST_ASSERT(array.size == 4, "incorrect size after resize"); 12.527 + 12.528 + UCX_TEST_END 12.529 + ucx_array_free(&array); 12.530 +} 12.531 + 12.532 +UCX_TEST(test_ucx_array_reserve) { 12.533 + UcxArray array = ucx_array_new(16, sizeof(int)); 12.534 + 12.535 + UCX_TEST_BEGIN 12.536 + 12.537 + UCX_TEST_ASSERT(!ucx_array_reserve(&array, 4), "failed"); 12.538 + UCX_TEST_ASSERT(array.capacity == 16, "reserve shall not shrink"); 12.539 + 12.540 + UCX_TEST_ASSERT(!ucx_array_resize(&array, 32), "failed"); 12.541 + UCX_TEST_ASSERT(array.capacity == 32, "incorrect capacity after reserve"); 12.542 + 12.543 + UCX_TEST_END 12.544 + ucx_array_free(&array); 12.545 +}
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 13.2 +++ b/test/array_tests.h Sat Aug 10 08:47:25 2019 +0200 13.3 @@ -0,0 +1,62 @@ 13.4 +/* 13.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 13.6 + * 13.7 + * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved. 13.8 + * 13.9 + * Redistribution and use in source and binary forms, with or without 13.10 + * modification, are permitted provided that the following conditions are met: 13.11 + * 13.12 + * 1. Redistributions of source code must retain the above copyright 13.13 + * notice, this list of conditions and the following disclaimer. 13.14 + * 13.15 + * 2. Redistributions in binary form must reproduce the above copyright 13.16 + * notice, this list of conditions and the following disclaimer in the 13.17 + * documentation and/or other materials provided with the distribution. 13.18 + * 13.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 13.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 13.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 13.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 13.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 13.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 13.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 13.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 13.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 13.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 13.29 + * POSSIBILITY OF SUCH DAMAGE. 13.30 + */ 13.31 + 13.32 +#ifndef ARRAY_TESTS_H 13.33 +#define ARRAY_TESTS_H 13.34 + 13.35 +#include <ucx/array.h> 13.36 +#include <ucx/test.h> 13.37 + 13.38 +#ifdef __cplusplus 13.39 +extern "C" { 13.40 +#endif 13.41 + 13.42 +UCX_TEST(test_ucx_array_free); 13.43 +UCX_TEST(test_ucx_array_new); 13.44 +UCX_TEST(test_ucx_array_at); 13.45 +UCX_TEST(test_ucx_array_append); 13.46 +UCX_TEST(test_ucx_array_prepend); 13.47 +UCX_TEST(test_ucx_array_set); 13.48 +UCX_TEST(test_ucx_array_autogrow); 13.49 +UCX_TEST(test_ucx_array_equals); 13.50 +UCX_TEST(test_ucx_array_concat); 13.51 +UCX_TEST(test_ucx_array_find); 13.52 +UCX_TEST(test_ucx_array_contains); 13.53 +UCX_TEST(test_ucx_array_remove); 13.54 +UCX_TEST(test_ucx_array_clone); 13.55 +UCX_TEST(test_ucx_array_sort); 13.56 +UCX_TEST(test_ucx_array_shrink); 13.57 +UCX_TEST(test_ucx_array_resize); 13.58 +UCX_TEST(test_ucx_array_reserve); 13.59 + 13.60 +#ifdef __cplusplus 13.61 +} 13.62 +#endif 13.63 + 13.64 +#endif /* ARRAY_TESTS_H */ 13.65 +
14.1 --- a/test/main.c Sat Aug 10 08:46:38 2019 +0200 14.2 +++ b/test/main.c Sat Aug 10 08:47:25 2019 +0200 14.3 @@ -33,6 +33,7 @@ 14.4 14.5 #include "main.h" 14.6 14.7 +#include "array_tests.h" 14.8 #include "allocator_tests.h" 14.9 #include "logging_tests.h" 14.10 #include "list_tests.h" 14.11 @@ -141,6 +142,25 @@ 14.12 ucx_test_register(suite, test_ucx_logger_new); 14.13 ucx_test_register(suite, test_ucx_logger_log); 14.14 14.15 + /* UcxArray Tests */ 14.16 + ucx_test_register(suite, test_ucx_array_free); 14.17 + ucx_test_register(suite, test_ucx_array_new); 14.18 + ucx_test_register(suite, test_ucx_array_at); 14.19 + ucx_test_register(suite, test_ucx_array_append); 14.20 + ucx_test_register(suite, test_ucx_array_prepend); 14.21 + ucx_test_register(suite, test_ucx_array_set); 14.22 + ucx_test_register(suite, test_ucx_array_autogrow); 14.23 + ucx_test_register(suite, test_ucx_array_equals); 14.24 + ucx_test_register(suite, test_ucx_array_concat); 14.25 + ucx_test_register(suite, test_ucx_array_find); 14.26 + ucx_test_register(suite, test_ucx_array_contains); 14.27 + ucx_test_register(suite, test_ucx_array_remove); 14.28 + ucx_test_register(suite, test_ucx_array_clone); 14.29 + ucx_test_register(suite, test_ucx_array_sort); 14.30 + ucx_test_register(suite, test_ucx_array_shrink); 14.31 + ucx_test_register(suite, test_ucx_array_resize); 14.32 + ucx_test_register(suite, test_ucx_array_reserve); 14.33 + 14.34 /* UcxList Tests */ 14.35 ucx_test_register(suite, test_ucx_list_append); 14.36 ucx_test_register(suite, test_ucx_list_prepend);
