Mercurial > hg > ucx / changeset

     1.1 --- a/configure.ac	Sat Aug 10 08:46:38 2019 +0200
     1.2 +++ b/configure.ac	Sat Oct 05 16:58:16 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 Oct 05 16:58:16 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 Oct 05 16:58:16 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&nbsp;Tree](#avl-tree)  [Buffer](#buffer)                [List](#list)
     3.9 -[Logging](#logging)     [Map](#map)                 [Memory&nbsp;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&nbsp;Pool](#memory-pool)     
    3.15 +[Array](#array)         [List](#list)           [Map](#map)                       [AVL&nbsp;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,61 @@
    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 +Arrays are in most cases much faster than linked list.
    3.34 +One can decide, whether to create a new array on the heap with `ucx_array_new()`
    3.35 +or to save one indirection by initializing a `UcxArray` structure on the stack
    3.36 +with `ucx_array_init()`.
    3.37 +
    3.38 +### Remove duplicates from an array of strings
    3.39 +
    3.40 +The following example shows, how a `UcxArray` can be built with
    3.41 +a standard dynamic C array (pointer+length) as basis.
    3.42 +
    3.43 +```C
    3.44 +#include <stdio.h>
    3.45 +#include <ucx/array.h>
    3.46 +#include <ucx/string.h>
    3.47 +#include <ucx/utils.h>
    3.48 +
    3.49 +UcxArray remove_duplicates(sstr_t* array, size_t arrlen) {
    3.50 +    // worst case is no duplicates, hence the capacity is set to arrlen
    3.51 +    UcxArray result = ucx_array_new(arrlen, sizeof(sstr_t));
    3.52 +    // only append elements, if they are not already present in the array
    3.53 +    for (size_t i = 0 ; i < arrlen ; ++i) {
    3.54 +        if (!ucx_array_contains(result, array+i, ucx_cmp_sstr, NULL)) {
    3.55 +            ucx_array_append(&result, array+i);
    3.56 +        }
    3.57 +    }
    3.58 +    // make the array as small as possible
    3.59 +    ucx_array_shrink(&result);
    3.60 +    return result;
    3.61 +}
    3.62 +
    3.63 +/* ... */
    3.64 +
    3.65 +sstr_t* array = /* some standard array of strings */
    3.66 +size_t arrlen = /* the length of the array */
    3.67 +
    3.68 +UcxArray result = remove_duplicates(array,arrlen);
    3.69 +
    3.70 +/* Iterate over the array and print the elements */
    3.71 +for (size_t i = 0 ; i < result.size ; i++) {
    3.72 +    sstr_t s = ucx_array_at_typed(sstr_t, result, i);
    3.73 +    printf("%" PRIsstr "\n", SFMT(s));
    3.74 +}
    3.75 +
    3.76 +/* Free the array. */
    3.77 +ucx_array_free(&result);
    3.78 +```
    3.79 +
    3.80  ## AVL Tree
    3.81  
    3.82  *Header file:* [avl.h](api/avl_8h.html)  
    3.83 @@ -195,6 +251,8 @@
    3.84  
    3.85  Assume you are given an array of `sstr_t` and want to create a list of these
    3.86  strings without duplicates.
    3.87 +This is a similar example to the one [above](#array), but here we are
    3.88 +using a `UcxList`.
    3.89  ```C
    3.90  #include <stdio.h>
    3.91  #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 Oct 05 16:58:16 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 Oct 05 16:58:16 2019 +0200
     5.3 @@ -0,0 +1,488 @@
     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 +#include <errno.h>
    5.42 +
    5.43 +#ifndef UCX_ARRAY_DISABLE_QSORT
    5.44 +#ifdef __GLIBC__
    5.45 +#if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)
    5.46 +#define ucx_array_sort_impl qsort_r
    5.47 +#endif /* glibc version >= 2.8 */
    5.48 +#elif /* not  __GLIBC__ */ defined(__APPLE__) || defined(__FreeBSD__)
    5.49 +#define ucx_array_sort_impl ucx_qsort_r
    5.50 +#define USE_UCX_QSORT_R
    5.51 +#elif /* not (__APPLE || __FreeBSD__) */ defined(__sun)
    5.52 +#if __STDC_VERSION__ >= 201112L
    5.53 +#define ucx_array_sort_impl qsort_s
    5.54 +#endif
    5.55 +#endif /* __GLIBC__, __APLE__, __FreeBSD__, __sun */
    5.56 +#endif /* UCX_ARRAY_DISABLE_QSORT */
    5.57 +
    5.58 +#ifndef ucx_array_sort_impl
    5.59 +#define ucx_array_sort_impl ucx_mergesort
    5.60 +#endif
    5.61 +
    5.62 +static int ucx_array_ensurecap(UcxArray *array, size_t reqcap) {
    5.63 +    size_t required_capacity = array->capacity;
    5.64 +    while (reqcap > required_capacity) {
    5.65 +        if (required_capacity * 2 < required_capacity)
    5.66 +            return 1;
    5.67 +        required_capacity <<= 1;
    5.68 +    }
    5.69 +    if (ucx_array_reserve(array, required_capacity)) {
    5.70 +        return 1;
    5.71 +    }
    5.72 +    return 0;
    5.73 +}
    5.74 +
    5.75 +int ucx_array_util_set_a(UcxAllocator* alloc, void** array, size_t* capacity,
    5.76 +    size_t elmsize, size_t index, ...) {
    5.77 +    
    5.78 +    if(!alloc || !capacity || !array) {
    5.79 +        errno = EINVAL;
    5.80 +        return 1;
    5.81 +    }
    5.82 +    
    5.83 +    size_t newcapacity = *capacity;
    5.84 +    while(index >= newcapacity) {
    5.85 +        if(ucx_szmul(newcapacity, 2, &newcapacity)) {
    5.86 +            errno = EOVERFLOW;
    5.87 +            return 1;
    5.88 +        }        
    5.89 +    }
    5.90 +
    5.91 +    size_t memlen, offset;
    5.92 +    if(ucx_szmul(newcapacity, elmsize, &memlen)) {
    5.93 +        errno = EOVERFLOW;
    5.94 +        return 1;
    5.95 +    }
    5.96 +    /* we don't need to check index*elmsize - it is smaller than memlen */
    5.97 +    
    5.98 +    
    5.99 +    void* newptr = alrealloc(alloc, *array, memlen);
   5.100 +    if(newptr == NULL) {
   5.101 +        errno = ENOMEM; /* we cannot assume that every allocator sets this */
   5.102 +        return 1;
   5.103 +    }
   5.104 +    *array = newptr;
   5.105 +    *capacity = newcapacity;
   5.106 +    
   5.107 +    
   5.108 +    char* dest = *array;
   5.109 +    dest += elmsize*index;
   5.110 +
   5.111 +    va_list ap;
   5.112 +    va_start(ap, index);
   5.113 +    int elem = va_arg(ap, int);    
   5.114 +    memcpy(dest, &elem, elmsize);
   5.115 +    va_end(ap);
   5.116 +    
   5.117 +    return 0;
   5.118 +}
   5.119 +
   5.120 +UcxArray* ucx_array_new(size_t capacity, size_t elemsize) {
   5.121 +    return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
   5.122 +}
   5.123 +
   5.124 +UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize,
   5.125 +        UcxAllocator* allocator) {
   5.126 +    UcxArray* array = almalloc(allocator, sizeof(UcxArray));
   5.127 +    if(array) {
   5.128 +        ucx_array_init_a(array, capacity, elemsize, allocator);
   5.129 +    }
   5.130 +    return array;
   5.131 +}
   5.132 +
   5.133 +void ucx_array_init(UcxArray* array, size_t capacity, size_t elemsize) {
   5.134 +    ucx_array_init_a(array, capacity, elemsize, ucx_default_allocator());
   5.135 +}
   5.136 +
   5.137 +void ucx_array_init_a(UcxArray* array, size_t capacity, size_t elemsize,
   5.138 +        UcxAllocator* allocator) {
   5.139 +    
   5.140 +    array->allocator = allocator;
   5.141 +    array->elemsize = elemsize;
   5.142 +    array->size = 0;
   5.143 +    array->data = alcalloc(allocator, capacity, elemsize);
   5.144 +    
   5.145 +    if (array->data) {
   5.146 +        array->capacity = capacity;
   5.147 +    } else {
   5.148 +        array->capacity = 0;
   5.149 +    }
   5.150 +}
   5.151 +
   5.152 +int ucx_array_clone(UcxArray* dest, UcxArray const* src) {
   5.153 +    if (ucx_array_ensurecap(dest, src->capacity)) {
   5.154 +        return 1;
   5.155 +    }
   5.156 +    
   5.157 +    dest->elemsize = src->elemsize;
   5.158 +    dest->size = src->size;
   5.159 +    
   5.160 +    if (dest->data) {
   5.161 +        memcpy(dest->data, src->data, src->size*src->elemsize);
   5.162 +    }
   5.163 +    
   5.164 +    return 0;
   5.165 +}
   5.166 +
   5.167 +int ucx_array_equals(UcxArray const *array1, UcxArray const *array2,
   5.168 +        cmp_func cmpfnc, void* data) {
   5.169 +    
   5.170 +    if (array1->size != array2->size || array1->elemsize != array2->elemsize) {
   5.171 +        return 0;
   5.172 +    } else {
   5.173 +        if (array1->size == 0)
   5.174 +            return 1;
   5.175 +        
   5.176 +        size_t elemsize;
   5.177 +        if (cmpfnc == NULL) {
   5.178 +            cmpfnc = ucx_cmp_mem;
   5.179 +            elemsize = array1->elemsize;
   5.180 +            data = &elemsize;
   5.181 +        }
   5.182 +        
   5.183 +        for (size_t i = 0 ; i < array1->size ; i++) {
   5.184 +            int r = cmpfnc(
   5.185 +                    ucx_array_at(array1, i),
   5.186 +                    ucx_array_at(array2, i),
   5.187 +                    data);
   5.188 +            if (r != 0)
   5.189 +                return 0;
   5.190 +        }
   5.191 +        return 1;
   5.192 +    }
   5.193 +}
   5.194 +
   5.195 +void ucx_array_destroy(UcxArray *array) {
   5.196 +    if(array->data)
   5.197 +        alfree(array->allocator, array->data);
   5.198 +    array->data = NULL;
   5.199 +    array->capacity = array->size = 0;
   5.200 +}
   5.201 +
   5.202 +void ucx_array_free(UcxArray *array) {
   5.203 +    ucx_array_destroy(array);
   5.204 +    alfree(array->allocator, array);
   5.205 +}
   5.206 +
   5.207 +int ucx_array_append_from(UcxArray *array, void *data, size_t count) {
   5.208 +    if (ucx_array_ensurecap(array, array->size + count))
   5.209 +        return 1;
   5.210 +    
   5.211 +    void* dest = ucx_array_at(array, array->size);
   5.212 +    if (data) {
   5.213 +        memcpy(dest, data, array->elemsize*count);
   5.214 +    } else {
   5.215 +        memset(dest, 0, array->elemsize*count);
   5.216 +    }
   5.217 +    array->size += count;
   5.218 +    
   5.219 +    return 0;
   5.220 +}
   5.221 +
   5.222 +int ucx_array_prepend_from(UcxArray *array, void *data, size_t count) {
   5.223 +    if (ucx_array_ensurecap(array, array->size + count))
   5.224 +        return 1;
   5.225 +    
   5.226 +    if (array->size > 0) {
   5.227 +        void *dest = ucx_array_at(array, count);
   5.228 +        memmove(dest, array->data, array->elemsize*array->size);
   5.229 +    }
   5.230 +    
   5.231 +    if (data) {
   5.232 +        memcpy(array->data, data, array->elemsize*count);
   5.233 +    } else {
   5.234 +        memset(array->data, 0, array->elemsize*count);
   5.235 +    }
   5.236 +    array->size += count;
   5.237 +        
   5.238 +    return 0;
   5.239 +}
   5.240 +
   5.241 +int ucx_array_set_from(UcxArray *array, size_t index,
   5.242 +        void *data, size_t count) {
   5.243 +    if (ucx_array_ensurecap(array, index + count))
   5.244 +        return 1;
   5.245 +    
   5.246 +    if (index+count > array->size) {
   5.247 +        array->size = index+count;
   5.248 +    }
   5.249 +    
   5.250 +    void *dest = ucx_array_at(array, index);
   5.251 +    if (data) {
   5.252 +        memcpy(dest, data, array->elemsize*count);
   5.253 +    } else {
   5.254 +        memset(dest, 0, array->elemsize*count);
   5.255 +    }
   5.256 +    
   5.257 +    return 0;
   5.258 +}
   5.259 +
   5.260 +int ucx_array_appendv(UcxArray *array, ...) {
   5.261 +    va_list ap;
   5.262 +    va_start(ap, array);
   5.263 +    int elem = va_arg(ap, int);
   5.264 +    int ret = ucx_array_append_from(array, &elem, 1);
   5.265 +    va_end(ap);
   5.266 +    return ret;
   5.267 +}
   5.268 +
   5.269 +int ucx_array_prependv(UcxArray *array, ...) {
   5.270 +    va_list ap;
   5.271 +    va_start(ap, array);
   5.272 +    int elem = va_arg(ap, int);
   5.273 +    int ret = ucx_array_prepend_from(array, &elem, 1);
   5.274 +    va_end(ap);
   5.275 +    return ret;
   5.276 +}
   5.277 +
   5.278 +int ucx_array_setv(UcxArray *array, size_t index, ...) {
   5.279 +    va_list ap;
   5.280 +    va_start(ap, index);
   5.281 +    int elem = va_arg(ap, int);
   5.282 +    int ret = ucx_array_set_from(array, index, &elem, 1);
   5.283 +    va_end(ap);
   5.284 +    return ret;
   5.285 +}
   5.286 +
   5.287 +int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {
   5.288 +    
   5.289 +    if (array1->elemsize != array2->elemsize)
   5.290 +        return 1;
   5.291 +    
   5.292 +    size_t capacity = array1->capacity+array2->capacity;
   5.293 +        
   5.294 +    if (array1->capacity < capacity) {
   5.295 +        if (ucx_array_reserve(array1, capacity)) {
   5.296 +            return 1;
   5.297 +        }
   5.298 +    }
   5.299 +    
   5.300 +    void* dest = ucx_array_at(array1, array1->size);
   5.301 +    memcpy(dest, array2->data, array2->size*array2->elemsize);
   5.302 +    
   5.303 +    array1->size += array2->size;
   5.304 +    
   5.305 +    return 0;
   5.306 +}
   5.307 +
   5.308 +void *ucx_array_at(UcxArray const *array, size_t index) {
   5.309 +    char* memory = array->data;
   5.310 +    char* loc = memory + index*array->elemsize;
   5.311 +    return loc;
   5.312 +}
   5.313 +
   5.314 +size_t ucx_array_find(UcxArray const *array, void *elem,
   5.315 +        cmp_func cmpfnc, void *data) {
   5.316 +    
   5.317 +    size_t elemsize;
   5.318 +    if (cmpfnc == NULL) {
   5.319 +        cmpfnc = ucx_cmp_mem;
   5.320 +        elemsize = array->elemsize;
   5.321 +        data = &elemsize;
   5.322 +    }
   5.323 +
   5.324 +    if (array->size > 0) {
   5.325 +        for (size_t i = 0 ; i < array->size ; i++) {
   5.326 +            void* ptr = ucx_array_at(array, i);
   5.327 +            if (cmpfnc(ptr, elem, data) == 0) {
   5.328 +                return i;
   5.329 +            }
   5.330 +        }
   5.331 +        return array->size;
   5.332 +    } else {
   5.333 +        return 0;
   5.334 +    }
   5.335 +}
   5.336 +
   5.337 +int ucx_array_contains(UcxArray const *array, void *elem,
   5.338 +        cmp_func cmpfnc, void *data) {
   5.339 +    return ucx_array_find(array, elem, cmpfnc, data) != array->size;
   5.340 +}
   5.341 +
   5.342 +static void ucx_mergesort_merge(void *arrdata,size_t elemsize,
   5.343 +        cmp_func cmpfnc, void *data,
   5.344 +        size_t start, size_t mid, size_t end) { 
   5.345 +    
   5.346 +    char* array = arrdata;
   5.347 +    
   5.348 +    size_t rightstart = mid + 1; 
   5.349 +  
   5.350 +    if (cmpfnc(array + mid*elemsize,
   5.351 +            array + rightstart*elemsize, data) <= 0) {
   5.352 +        /* already sorted */
   5.353 +        return;
   5.354 +    }
   5.355 +  
   5.356 +    /* we need memory for one element */
   5.357 +    void *value = malloc(elemsize);
   5.358 +    
   5.359 +    while (start <= mid && rightstart <= end) { 
   5.360 +        if (cmpfnc(array + start*elemsize,
   5.361 +                array + rightstart*elemsize, data) <= 0) { 
   5.362 +            start++; 
   5.363 +        } else {
   5.364 +            /* save the value from the right */
   5.365 +            memcpy(value, array + rightstart*elemsize, elemsize);
   5.366 +                        
   5.367 +            /* shift all left elements one element to the right */
   5.368 +            size_t shiftcount = rightstart-start;
   5.369 +            void *startptr = array + start*elemsize;
   5.370 +            void *dest = array + (start+1)*elemsize;
   5.371 +            memmove(dest, startptr, shiftcount*elemsize);
   5.372 +            
   5.373 +            /* bring the first value from the right to the left */
   5.374 +            memcpy(startptr, value, elemsize);
   5.375 +  
   5.376 +            start++; 
   5.377 +            mid++; 
   5.378 +            rightstart++; 
   5.379 +        }
   5.380 +    }
   5.381 +    
   5.382 +    /* free the temporary memory */
   5.383 +    free(value);
   5.384 +} 
   5.385 +  
   5.386 +static void ucx_mergesort_impl(void *arrdata, size_t elemsize,
   5.387 +        cmp_func cmpfnc, void *data, size_t l, size_t r) { 
   5.388 +    if (l < r) {
   5.389 +        size_t m = l + (r - l) / 2; 
   5.390 +  
   5.391 +        ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m); 
   5.392 +        ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r); 
   5.393 +        ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);
   5.394 +    } 
   5.395 +}
   5.396 +
   5.397 +static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,
   5.398 +        cmp_func cmpfnc, void *data) {
   5.399 +    
   5.400 +    ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);
   5.401 +}
   5.402 +
   5.403 +#ifdef USE_UCX_QSORT_R
   5.404 +struct cmpfnc_swapargs_info {
   5.405 +    cmp_func func;
   5.406 +    void *data;
   5.407 +};
   5.408 +
   5.409 +static int cmp_func_swap_args(void *data, const void *x, const void *y) {
   5.410 +    cmpfnc_swapargs_info* info = data;
   5.411 +    return info->func(x, y, info->data);
   5.412 +}
   5.413 +
   5.414 +static void ucx_qsort_r(void *array, size_t count, size_t elemsize,
   5.415 +		     cmp_func cmpfnc, void *data) {
   5.416 +    struct cmpfnc_swapargs_info info;
   5.417 +    info.func = cmpfnc;
   5.418 +    info.data = data;
   5.419 +    qsort_r(array, count, elemsize, &info, cmp_func_swap_args);
   5.420 +}
   5.421 +#endif /* USE_UCX_QSORT_R */
   5.422 +
   5.423 +void ucx_array_sort(UcxArray* array, cmp_func cmpfnc, void *data) {
   5.424 +    ucx_array_sort_impl(array->data, array->size, array->elemsize,
   5.425 +            cmpfnc, data);
   5.426 +}
   5.427 +
   5.428 +void ucx_array_remove(UcxArray *array, size_t index) {
   5.429 +    array->size--;
   5.430 +    if (index < array->size) {
   5.431 +        void* dest = ucx_array_at(array, index);
   5.432 +        void* src = ucx_array_at(array, index+1);
   5.433 +        memmove(dest, src, (array->size - index)*array->elemsize);
   5.434 +    }
   5.435 +}
   5.436 +
   5.437 +void ucx_array_remove_fast(UcxArray *array, size_t index) {
   5.438 +    array->size--;
   5.439 +    if (index < array->size) {       
   5.440 +        void* dest = ucx_array_at(array, index);
   5.441 +        void* src = ucx_array_at(array, array->size);
   5.442 +        memcpy(dest, src, array->elemsize);
   5.443 +    }
   5.444 +}
   5.445 +
   5.446 +int ucx_array_shrink(UcxArray* array) {
   5.447 +    void* newptr = alrealloc(array->allocator, array->data,
   5.448 +                array->size*array->elemsize);
   5.449 +    if (newptr) {
   5.450 +        array->data = newptr;
   5.451 +        array->capacity = array->size;
   5.452 +        return 0;
   5.453 +    } else {
   5.454 +        return 1;
   5.455 +    }
   5.456 +}
   5.457 +
   5.458 +int ucx_array_resize(UcxArray* array, size_t capacity) {
   5.459 +    if (array->capacity >= capacity) {
   5.460 +        void* newptr = alrealloc(array->allocator, array->data,
   5.461 +                capacity*array->elemsize);
   5.462 +        if (newptr) {
   5.463 +            array->data = newptr;
   5.464 +            array->capacity = capacity;
   5.465 +            if (array->size > array->capacity) {
   5.466 +                array->size = array->capacity;
   5.467 +            }
   5.468 +            return 0;
   5.469 +        } else {
   5.470 +            return 1;
   5.471 +        }
   5.472 +    } else {
   5.473 +        return ucx_array_reserve(array, capacity);
   5.474 +    }
   5.475 +}
   5.476 +
   5.477 +int ucx_array_reserve(UcxArray* array, size_t capacity) {
   5.478 +    if (array->capacity > capacity) {
   5.479 +        return 0;
   5.480 +    } else {
   5.481 +        void* newptr = alrealloc(array->allocator, array->data,
   5.482 +                capacity*array->elemsize);
   5.483 +        if (newptr) {
   5.484 +            array->data = newptr;
   5.485 +            array->capacity = capacity;
   5.486 +            return 0;
   5.487 +        } else {
   5.488 +            return 1;
   5.489 +        }
   5.490 +    }
   5.491 +}

     6.1 --- a/src/list.c	Sat Aug 10 08:46:38 2019 +0200
     6.2 +++ b/src/list.c	Sat Oct 05 16:58:16 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 Oct 05 16:58:16 2019 +0200
     7.3 @@ -0,0 +1,516 @@
     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 + * Sets an element in an arbitrary user defined array.
    7.77 + * 
    7.78 + * If the capacity is insufficient, the array is automatically reallocated and
    7.79 + * the possibly new pointer is stored in the <code>array</code> argument.
    7.80 + * 
    7.81 + * On reallocation the capacity of the array is doubled until it is sufficient.
    7.82 + * The new capacity is stored back to <code>capacity</code>.
    7.83 + *  
    7.84 + * @param array a pointer to location of the array pointer
    7.85 + * @param capacity a pointer to the capacity
    7.86 + * @param elmsize the size of each element
    7.87 + * @param idx the index of the element to set
    7.88 + * @param data the element data
    7.89 + * @return zero on success or non-zero on error (errno will be set)
    7.90 + */
    7.91 +#define ucx_array_util_set(array, capacity, elmsize, idx, data) \
    7.92 +    ucx_array_util_set_a(ucx_default_allocator(), (void**)(array), capacity, \
    7.93 +                         elmsize, idx, data)
    7.94 +
    7.95 +/**
    7.96 + * Convenience macro for ucx_array_util_set() which automatically computes
    7.97 + * <code>sizeof(data)</code>.
    7.98 + * 
    7.99 + * @param array a pointer to location of the array pointer
   7.100 + * @param capacity a pointer to the capacity
   7.101 + * @param idx the index of the element to set
   7.102 + * @param data the element data
   7.103 + * @return zero on success or non-zero on error (errno will be set)
   7.104 + * @see ucx_array_util_set()
   7.105 + */
   7.106 +#define UCX_ARRAY_UTIL_SET(array, capacity, idx, data) \
   7.107 +    ucx_array_util_set_a(ucx_default_allocator(), (void**)(array), capacity, \
   7.108 +                         sizeof(data), idx, data)
   7.109 +
   7.110 +/**
   7.111 + * Sets an element in an arbitrary user defined array.
   7.112 + * 
   7.113 + * If the capacity is insufficient, the array is automatically reallocated
   7.114 + * using the specified allocator and the possibly new pointer is stored in
   7.115 + * the <code>array</code> argument.
   7.116 + * 
   7.117 + * On reallocation the capacity of the array is doubled until it is sufficient.
   7.118 + * The new capacity is stored back to <code>capacity</code>. 
   7.119 + * 
   7.120 + * @param alloc the allocator that shall be used to reallocate the array
   7.121 + * @param array a pointer to location of the array pointer
   7.122 + * @param capacity a pointer to the capacity
   7.123 + * @param elmsize the size of each element
   7.124 + * @param idx the index of the element to set
   7.125 + * @param ... the element data
   7.126 + * @return zero on success or non-zero on error (errno will be set)
   7.127 + */
   7.128 +int ucx_array_util_set_a(UcxAllocator* alloc, void** array, size_t* capacity,
   7.129 +    size_t elmsize, size_t idx, ...);
   7.130 +
   7.131 +
   7.132 +/**
   7.133 + * Convenience macro for ucx_array_util_set_a() which automatically computes
   7.134 + * <code>sizeof(data)</code>.
   7.135 + * 
   7.136 + * @param alloc the allocator that shall be used to reallocate the array
   7.137 + * @param array a pointer to location of the array pointer
   7.138 + * @param capacity a pointer to the capacity
   7.139 + * @param idx the index of the element to set
   7.140 + * @param data the element data
   7.141 + * @return zero on success or non-zero on error (errno will be set)
   7.142 + * @see ucx_array_util_set_a()
   7.143 + */
   7.144 +#define UCX_ARRAY_UTIL_SET_A(alloc, array, capacity, idx, data) \
   7.145 +    ucx_array_util_set_a(alloc, capacity, sizeof(data), idx, data)
   7.146 +
   7.147 +/**
   7.148 + * Creates a new UCX array with the given capacity and element size.
   7.149 + * @param capacity the initial capacity
   7.150 + * @param elemsize the element size
   7.151 + * @return a pointer to a new UCX array structure
   7.152 + */
   7.153 +UcxArray* ucx_array_new(size_t capacity, size_t elemsize);
   7.154 +
   7.155 +/**
   7.156 + * Creates a new UCX array using the specified allocator.
   7.157 + * 
   7.158 + * @param capacity the initial capacity
   7.159 + * @param elemsize the element size
   7.160 + * @param allocator the allocator to use
   7.161 + * @return a pointer to new UCX array structure
   7.162 + */
   7.163 +UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize,
   7.164 +        UcxAllocator* allocator);
   7.165 +
   7.166 +/**
   7.167 + * Initializes a UCX array structure with the given capacity and element size.
   7.168 + * The structure must be uninitialized as the data pointer will be overwritten.
   7.169 + * 
   7.170 + * @param array the structure to initialize
   7.171 + * @param capacity the initial capacity
   7.172 + * @param elemsize the element size
   7.173 + */
   7.174 +void ucx_array_init(UcxArray* array, size_t capacity, size_t elemsize);
   7.175 +
   7.176 +/**
   7.177 + * Initializes a UCX array structure using the specified allocator.
   7.178 + * The structure must be uninitialized as the data pointer will be overwritten.
   7.179 + * 
   7.180 + * @param capacity the initial capacity
   7.181 + * @param elemsize the element size
   7.182 + * @param allocator the allocator to use
   7.183 + */
   7.184 +void ucx_array_init_a(UcxArray* array, size_t capacity, size_t elemsize,
   7.185 +        UcxAllocator* allocator);
   7.186 +
   7.187 +/**
   7.188 + * Creates an shallow copy of an array.
   7.189 + * 
   7.190 + * This function clones the specified array by using memcpy().
   7.191 + * If the destination capacity is insufficient, an automatic reallocation is
   7.192 + * attempted.
   7.193 + * 
   7.194 + * Note: if the destination array is uninitialized, the behavior is undefined.
   7.195 + * 
   7.196 + * @param dest the array to copy to
   7.197 + * @param src the array to copy from
   7.198 + * @return zero on success, non-zero on reallocation failure.
   7.199 + */
   7.200 +int ucx_array_clone(UcxArray* dest, UcxArray const* src);
   7.201 +
   7.202 +
   7.203 +/**
   7.204 + * Compares two UCX arrays element-wise by using a compare function.
   7.205 + *
   7.206 + * Elements of the two specified arrays are compared by using the specified
   7.207 + * compare function and the additional data. The type and content of this
   7.208 + * additional data depends on the cmp_func() used.
   7.209 + * 
   7.210 + * This function always returns zero, if the element sizes of the arrays do
   7.211 + * not match and performs no comparisons in this case.
   7.212 + * 
   7.213 + * @param array1 the first array
   7.214 + * @param array2 the second array
   7.215 + * @param cmpfnc the compare function
   7.216 + * @param data additional data for the compare function
   7.217 + * @return 1, if and only if the two arrays equal element-wise, 0 otherwise
   7.218 + */
   7.219 +int ucx_array_equals(UcxArray const *array1, UcxArray const *array2,
   7.220 +        cmp_func cmpfnc, void* data);
   7.221 +
   7.222 +/**
   7.223 + * Destroys the array.
   7.224 + * 
   7.225 + * The data is freed and both capacity and count are reset to zero.
   7.226 + * If the array structure itself has been dynamically allocated, it has to be
   7.227 + * freed separately.
   7.228 + * 
   7.229 + * @param array the array to destroy
   7.230 + */
   7.231 +void ucx_array_destroy(UcxArray *array);
   7.232 +
   7.233 +/**
   7.234 + * Destroys and frees the array.
   7.235 + * 
   7.236 + * @param array the array to free
   7.237 + */
   7.238 +void ucx_array_free(UcxArray *array);
   7.239 +
   7.240 +/**
   7.241 + * Inserts elements at the end of the array.
   7.242 + * 
   7.243 + * This is an O(1) operation.
   7.244 + * The array will automatically grow, if the capacity is exceeded.
   7.245 + * If a pointer to data is provided, the data is copied into the array with
   7.246 + * memcpy(). Otherwise the new elements are completely zeroed.
   7.247 + * 
   7.248 + * @param array a pointer the array where to append the data
   7.249 + * @param data a pointer to the data to insert (may be <code>NULL</code>)
   7.250 + * @param count number of elements to copy from data (if data is
   7.251 + * <code>NULL</code>, zeroed elements are appended)
   7.252 + * @return zero on success, non-zero if a reallocation was necessary but failed
   7.253 + * @see ucx_array_set_from()
   7.254 + * @see ucx_array_append()
   7.255 + */
   7.256 +int ucx_array_append_from(UcxArray *array, void *data, size_t count);
   7.257 +
   7.258 +
   7.259 +/**
   7.260 + * Inserts elements at the beginning of the array.
   7.261 + * 
   7.262 + * This is an expensive operation, because the contents must be moved.
   7.263 + * If there is no particular reason to prepend data, you should use
   7.264 + * ucx_array_append_from() instead.
   7.265 + * 
   7.266 + * @param array a pointer the array where to prepend the data
   7.267 + * @param data a pointer to the data to insert (may be <code>NULL</code>)
   7.268 + * @param count number of elements to copy from data (if data is
   7.269 + * <code>NULL</code>, zeroed elements are inserted)
   7.270 + * @return zero on success, non-zero if a reallocation was necessary but failed
   7.271 + * @see ucx_array_append_from()
   7.272 + * @see ucx_array_set_from()
   7.273 + * @see ucx_array_prepend()
   7.274 + */
   7.275 +int ucx_array_prepend_from(UcxArray *array, void *data, size_t count);
   7.276 +
   7.277 +
   7.278 +/**
   7.279 + * Sets elements starting at the specified index.
   7.280 + * 
   7.281 + * If the any index is out of bounds, the array automatically grows.
   7.282 + * The pointer to the data may be NULL, in which case the elements are zeroed. 
   7.283 + * 
   7.284 + * @param array a pointer the array where to set the data
   7.285 + * @param index the index of the element to set
   7.286 + * @param data a pointer to the data to insert (may be <code>NULL</code>)
   7.287 + * @param count number of elements to copy from data (if data is
   7.288 + * <code>NULL</code>, the memory in the array is zeroed)
   7.289 + * @return zero on success, non-zero if a reallocation was necessary but failed
   7.290 + * @see ucx_array_append_from()
   7.291 + * @see ucx_array_set()
   7.292 + */
   7.293 +int ucx_array_set_from(UcxArray *array, size_t index, void *data, size_t count);
   7.294 +
   7.295 +/**
   7.296 + * Inserts an element at the end of the array.
   7.297 + * 
   7.298 + * This is an O(1) operation.
   7.299 + * The array will automatically grow, if the capacity is exceeded.
   7.300 + * If the type of the argument has a different size than the element size of
   7.301 + * this array, the behavior is undefined.
   7.302 + * 
   7.303 + * @param array a pointer the array where to append the data
   7.304 + * @param elem the value to insert
   7.305 + * @return zero on success, non-zero if a reallocation was necessary but failed
   7.306 + * @see ucx_array_append_from()
   7.307 + * @see ucx_array_set()
   7.308 + */
   7.309 +#define ucx_array_append(array, elem) ucx_array_appendv(array, elem)
   7.310 +
   7.311 +/**
   7.312 + * For internal use.
   7.313 + * Use ucx_array_append()
   7.314 + * 
   7.315 + * @param array
   7.316 + * @param ... 
   7.317 + * @return 
   7.318 + * @see ucx_array_append()
   7.319 + */
   7.320 +int ucx_array_appendv(UcxArray *array, ...);
   7.321 +
   7.322 +
   7.323 +/**
   7.324 + * Inserts an element at the beginning of the array.
   7.325 + * 
   7.326 + * This is an expensive operation, because the contents must be moved.
   7.327 + * If there is no particular reason to prepend data, you should use
   7.328 + * ucx_array_append() instead.
   7.329 + * 
   7.330 + * @param array a pointer the array where to prepend the data
   7.331 + * @param elem the value to insert
   7.332 + * @return zero on success, non-zero if a reallocation was necessary but failed
   7.333 + * @see ucx_array_append()
   7.334 + * @see ucx_array_set_from()
   7.335 + * @see ucx_array_prepend_from()
   7.336 + */
   7.337 +#define ucx_array_prepend(array, elem) ucx_array_prependv(array, elem)
   7.338 +
   7.339 +/**
   7.340 + * For internal use.
   7.341 + * Use ucx_array_prepend()
   7.342 + * 
   7.343 + * @param array
   7.344 + * @param ... 
   7.345 + * @return 
   7.346 + * @see ucx_array_prepend()
   7.347 + */
   7.348 +int ucx_array_prependv(UcxArray *array, ...);
   7.349 +
   7.350 +
   7.351 +/**
   7.352 + * Sets an element at the specified index.
   7.353 + * 
   7.354 + * If the any index is out of bounds, the array automatically grows.
   7.355 + * 
   7.356 + * @param array a pointer the array where to set the data
   7.357 + * @param index the index of the element to set
   7.358 + * @param elem the value to set
   7.359 + * @return zero on success, non-zero if a reallocation was necessary but failed
   7.360 + * @see ucx_array_append()
   7.361 + * @see ucx_array_set_from()
   7.362 + */
   7.363 +#define ucx_array_set(array, index, elem) ucx_array_setv(array, index, elem)
   7.364 +
   7.365 +/**
   7.366 + * For internal use.
   7.367 + * Use ucx_array_set()
   7.368 + * 
   7.369 + * @param array
   7.370 + * @param index
   7.371 + * @param ... 
   7.372 + * @return 
   7.373 + * @see ucx_array_set()
   7.374 + */
   7.375 +int ucx_array_setv(UcxArray *array, size_t index, ...);
   7.376 +
   7.377 +/**
   7.378 + * Concatenates two arrays.
   7.379 + * 
   7.380 + * The contents of the second array are appended to the first array in one
   7.381 + * single operation. The second array is otherwise left untouched.
   7.382 + * 
   7.383 + * The first array may grow automatically. If this fails, both arrays remain
   7.384 + * unmodified.
   7.385 + * 
   7.386 + * @param array1 first array
   7.387 + * @param array2 second array
   7.388 + * @return zero on success, non-zero if reallocation was necessary but failed 
   7.389 + * or the element size does not match
   7.390 + */
   7.391 +int ucx_array_concat(UcxArray *array1, const UcxArray *array2);
   7.392 +
   7.393 +/**
   7.394 + * Returns a pointer to the array element at the specified index.
   7.395 + * 
   7.396 + * @param array the array to retrieve the element from
   7.397 + * @param index index of the element to return
   7.398 + * @return a pointer to the element at the specified index or <code>NULL</code>,
   7.399 + * if the index is greater than the array size
   7.400 + */
   7.401 +void *ucx_array_at(UcxArray const* array, size_t index);
   7.402 +
   7.403 +/**
   7.404 + * Returns the index of an element containing the specified data.
   7.405 + *
   7.406 + * This function uses a cmp_func() to compare the data of each list element
   7.407 + * with the specified data. If no cmp_func is provided, memcmp() is used.
   7.408 + * 
   7.409 + * If the array contains the data more than once, the index of the first
   7.410 + * occurrence is returned.
   7.411 + * If the array does not contain the data, the size of array is returned.
   7.412 + *  
   7.413 + * @param array the array where to search for the data
   7.414 + * @param elem the element data
   7.415 + * @param cmpfnc the compare function
   7.416 + * @param data additional data for the compare function
   7.417 + * @return the index of the element containing the specified data or the size of
   7.418 + * the array, if the data is not found in this array
   7.419 + */
   7.420 +size_t ucx_array_find(UcxArray const *array, void *elem,
   7.421 +    cmp_func cmpfnc, void *data);
   7.422 +
   7.423 +/**
   7.424 + * Checks, if an array contains a specific element.
   7.425 + * 
   7.426 + * An element is found, if ucx_array_find() returns a value less than the size.
   7.427 + * 
   7.428 + * @param array the array where to search for the data
   7.429 + * @param elem the element data
   7.430 + * @param cmpfnc the compare function
   7.431 + * @param data additional data for the compare function
   7.432 + * @return 1, if and only if the array contains the specified element data
   7.433 + * @see ucx_array_find()
   7.434 + */
   7.435 +int ucx_array_contains(UcxArray const *array, void *elem,
   7.436 +    cmp_func cmpfnc, void *data);
   7.437 +
   7.438 +/**
   7.439 + * Sorts a UcxArray with the best available sort algorithm.
   7.440 + * 
   7.441 + * The qsort_r() function is used, if available (glibc, FreeBSD or MacOS).
   7.442 + * The order of arguments is automatically adjusted for the FreeBSD and MacOS
   7.443 + * version of qsort_r().
   7.444 + * 
   7.445 + * If qsort_r() is not available, a merge sort algorithm is used, which is
   7.446 + * guaranteed to use no more additional memory than for exactly one element.
   7.447 + * 
   7.448 + * @param array the array to sort
   7.449 + * @param cmpfnc the function that shall be used to compare the element data
   7.450 + * @param data additional data for the cmp_func() or <code>NULL</code>
   7.451 + */
   7.452 +void ucx_array_sort(UcxArray* array, cmp_func cmpfnc, void *data);
   7.453 +
   7.454 +/**
   7.455 + * Removes an element from the array.
   7.456 + * 
   7.457 + * This is in general an expensive operation, because several elements may
   7.458 + * be moved. If the order of the elements is not relevant, use
   7.459 + * ucx_array_remove_fast() instead.
   7.460 + * 
   7.461 + * @param array pointer to the array from which the element shall be removed
   7.462 + * @param index the index of the element to remove
   7.463 + */
   7.464 +void ucx_array_remove(UcxArray *array, size_t index);
   7.465 +
   7.466 +/**
   7.467 + * Removes an element from the array.
   7.468 + * 
   7.469 + * This is an O(1) operation, but does not maintain the order of the elements.
   7.470 + * The last element in the array is moved to the location of the removed
   7.471 + * element.
   7.472 + * 
   7.473 + * @param array pointer to the array from which the element shall be removed
   7.474 + * @param index the index of the element to remove
   7.475 + */
   7.476 +void ucx_array_remove_fast(UcxArray *array, size_t index);
   7.477 +
   7.478 +/**
   7.479 + * Shrinks the memory to exactly fit the contents.
   7.480 + * 
   7.481 + * After this operation, the capacity equals the size.
   7.482 + * 
   7.483 + * @param array a pointer to the array
   7.484 + * @return zero on success, non-zero if reallocation failed
   7.485 + */
   7.486 +int ucx_array_shrink(UcxArray* array);
   7.487 +
   7.488 +/**
   7.489 + * Sets the capacity of the array.
   7.490 + * 
   7.491 + * If the new capacity is smaller than the size of the array, the elements
   7.492 + * are removed and the size is adjusted accordingly.
   7.493 + * 
   7.494 + * @param array a pointer to the array
   7.495 + * @param capacity the new capacity
   7.496 + * @return zero on success, non-zero if reallocation failed
   7.497 + */
   7.498 +int ucx_array_resize(UcxArray* array, size_t capacity);
   7.499 +
   7.500 +/**
   7.501 + * Resizes the array only, if the capacity is insufficient.
   7.502 + * 
   7.503 + * If the requested capacity is smaller than the current capacity, this
   7.504 + * function does nothing.
   7.505 + * 
   7.506 + * @param array a pointer to the array
   7.507 + * @param capacity the guaranteed capacity
   7.508 + * @return zero on success, non-zero if reallocation failed
   7.509 + */
   7.510 +int ucx_array_reserve(UcxArray* array, size_t capacity);
   7.511 +
   7.512 +
   7.513 +
   7.514 +#ifdef	__cplusplus
   7.515 +}
   7.516 +#endif
   7.517 +
   7.518 +#endif	/* UCX_ARRAY_H */
   7.519 +

     8.1 --- a/src/ucx/ucx.h	Sat Aug 10 08:46:38 2019 +0200
     8.2 +++ b/src/ucx/ucx.h	Sat Oct 05 16:58:16 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 Oct 05 16:58:16 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 Oct 05 16:58:16 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 Oct 05 16:58:16 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
   11.11 @@ -41,4 +42,5 @@
   11.12  ucxtest_SOURCES += logging_tests.c
   11.13  ucxtest_SOURCES += buffer_tests.c
   11.14  ucxtest_SOURCES += utils_tests.c
   11.15 +ucxtest_LDFLAGS = -static
   11.16  ucxtest_LDADD = ../src/libucx.la

    12.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    12.2 +++ b/test/array_tests.c	Sat Oct 05 16:58:16 2019 +0200
    12.3 @@ -0,0 +1,653 @@
    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_destroy) {
   12.36 +    UcxArray array;
   12.37 +    ucx_array_init(&array, 16, sizeof(int));
   12.38 +    
   12.39 +    UCX_TEST_BEGIN
   12.40 +    ucx_array_destroy(&array);
   12.41 +    UCX_TEST_ASSERT(array.data == NULL, "data pointer not NULL after destroy");
   12.42 +    UCX_TEST_ASSERT(array.size == 0, "size not zero after destroy");
   12.43 +    UCX_TEST_ASSERT(array.capacity == 0, "capacity not zero after destroy");
   12.44 +    UCX_TEST_ASSERT(array.allocator == ucx_default_allocator(),
   12.45 +            "allocator corrupted during destroy");
   12.46 +    UCX_TEST_END
   12.47 +}
   12.48 +
   12.49 +UCX_TEST(test_ucx_array_new) {
   12.50 +    UcxArray* array = ucx_array_new(16, 47);
   12.51 +    
   12.52 +    UCX_TEST_BEGIN
   12.53 +    UCX_TEST_ASSERT(array->data, "no memory allocated");
   12.54 +    UCX_TEST_ASSERT(array->size == 0, "size not initially zero");
   12.55 +    UCX_TEST_ASSERT(array->capacity == 16, "capacity not as requested");
   12.56 +    UCX_TEST_ASSERT(array->elemsize == 47, "element size not as requested");
   12.57 +    UCX_TEST_ASSERT(array->allocator == ucx_default_allocator(),
   12.58 +            "array not using the default allocator");
   12.59 +    UCX_TEST_END
   12.60 +    ucx_array_free(array);
   12.61 +}
   12.62 +
   12.63 +UCX_TEST(test_ucx_array_append_from) {
   12.64 +    UcxArray *array = ucx_array_new(16, sizeof(int));
   12.65 +    int *elements;
   12.66 +    
   12.67 +    int x = 42;
   12.68 +    ucx_array_append_from(array, &x, 1);
   12.69 +    UCX_TEST_BEGIN
   12.70 +    
   12.71 +    elements = array->data;
   12.72 +    UCX_TEST_ASSERT(elements[0] == 42, "failed");
   12.73 +    
   12.74 +    int y[2] = {13, 37};
   12.75 +    ucx_array_append_from(array, y, 2);
   12.76 +    
   12.77 +    elements = array->data;
   12.78 +    UCX_TEST_ASSERT(array->size == 3, "incorrect size after append");
   12.79 +    UCX_TEST_ASSERT(elements[1] == 13, "failed");
   12.80 +    UCX_TEST_ASSERT(elements[2] == 37, "failed");
   12.81 +    UCX_TEST_ASSERT(elements[0] == 42,
   12.82 +            "append corrupted previously inserted data");
   12.83 +    
   12.84 +    ucx_array_append_from(array, NULL, 2);
   12.85 +    
   12.86 +    elements = array->data;
   12.87 +    UCX_TEST_ASSERT(array->size == 5, "incorrect size after NULL append");
   12.88 +    UCX_TEST_ASSERT(elements[3] == 0, "element is not zeroed");
   12.89 +    UCX_TEST_ASSERT(elements[4] == 0, "element is not zeroed");
   12.90 +    UCX_TEST_ASSERT(elements[0] == 42,
   12.91 +            "NULL append corrupted previously inserted data");
   12.92 +    UCX_TEST_ASSERT(elements[1] == 13,
   12.93 +            "NULL append corrupted previously inserted data");
   12.94 +    UCX_TEST_ASSERT(elements[2] == 37,
   12.95 +            "NULL append corrupted previously inserted data");
   12.96 +    
   12.97 +    UCX_TEST_END
   12.98 +    
   12.99 +    ucx_array_free(array);
  12.100 +}
  12.101 +
  12.102 +UCX_TEST(test_ucx_array_prepend_from) {
  12.103 +    int *elems;
  12.104 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.105 +    
  12.106 +    int x = 42;
  12.107 +    ucx_array_prepend_from(array, &x, 1);
  12.108 +    UCX_TEST_BEGIN
  12.109 +    
  12.110 +    elems = array->data;
  12.111 +    UCX_TEST_ASSERT(elems[0] == 42, "failed");
  12.112 +    
  12.113 +    int y[2] = {13, 37};
  12.114 +    ucx_array_prepend_from(array, y, 2);
  12.115 +    
  12.116 +    elems = array->data;
  12.117 +    UCX_TEST_ASSERT(array->size == 3, "incorrect size after prepend");
  12.118 +    UCX_TEST_ASSERT(elems[0] == 13, "failed");
  12.119 +    UCX_TEST_ASSERT(elems[1] == 37, "failed");
  12.120 +    UCX_TEST_ASSERT(elems[2] == 42,
  12.121 +            "prepend corrupted previously inserted data");
  12.122 +    
  12.123 +    ucx_array_prepend_from(array, NULL, 2);
  12.124 +    
  12.125 +    elems = array->data;
  12.126 +    UCX_TEST_ASSERT(array->size == 5, "incorrect size after NULL prepend");
  12.127 +    UCX_TEST_ASSERT(elems[0] == 0, "element is not zeroed");
  12.128 +    UCX_TEST_ASSERT(elems[1] == 0, "element is not zeroed");
  12.129 +    UCX_TEST_ASSERT(elems[2] == 13,
  12.130 +            "NULL prepend corrupted previously inserted data");
  12.131 +    UCX_TEST_ASSERT(elems[3] == 37,
  12.132 +            "NULL prepend corrupted previously inserted data");
  12.133 +    UCX_TEST_ASSERT(elems[4] == 42,
  12.134 +            "NULL prepend corrupted previously inserted data");
  12.135 +    
  12.136 +    UCX_TEST_END
  12.137 +    
  12.138 +    ucx_array_free(array);
  12.139 +}
  12.140 +
  12.141 +UCX_TEST(test_ucx_array_set_from) {
  12.142 +    int *elems;
  12.143 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.144 +    
  12.145 +    int x = 42;
  12.146 +
  12.147 +    UCX_TEST_BEGIN
  12.148 +
  12.149 +    ucx_array_set_from(array, 7, &x, 1);
  12.150 +    
  12.151 +    elems = array->data;
  12.152 +    UCX_TEST_ASSERT(elems[7] == 42, "failed");
  12.153 +    UCX_TEST_ASSERT(array->size >= 8, "array not resized on set");
  12.154 +    UCX_TEST_ASSERT(array->capacity == 16, "capacity changed unnecessarily");
  12.155 +    
  12.156 +    int y[2] = {13, 37};
  12.157 +    ucx_array_set_from(array, 27, y, 2);
  12.158 +    
  12.159 +    elems = array->data;
  12.160 +    UCX_TEST_ASSERT(elems[27] == 13, "failed");
  12.161 +    UCX_TEST_ASSERT(elems[28] == 37, "failed");
  12.162 +    UCX_TEST_ASSERT(array->size == 29, "array not resized on set");
  12.163 +    UCX_TEST_ASSERT(array->capacity == 32, "capacity not grown");
  12.164 +    
  12.165 +    ucx_array_set_from(array, 7, NULL, 2);
  12.166 +    
  12.167 +    elems = array->data;
  12.168 +    UCX_TEST_ASSERT(elems[7] == 0, "not zeroed on NULL set");
  12.169 +    UCX_TEST_ASSERT(elems[8] == 0, "not zeroed on NULL set");
  12.170 +    
  12.171 +    UCX_TEST_END
  12.172 +    
  12.173 +    ucx_array_free(array);
  12.174 +}
  12.175 +
  12.176 +UCX_TEST(test_ucx_array_append) {
  12.177 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.178 +    int *elements;
  12.179 +    
  12.180 +    ucx_array_append(array, 42);
  12.181 +    UCX_TEST_BEGIN
  12.182 +    
  12.183 +    elements = array->data;
  12.184 +    UCX_TEST_ASSERT(elements[0] == 42, "failed");
  12.185 +    
  12.186 +    ucx_array_append(array, 13);
  12.187 +    ucx_array_append(array, 37);
  12.188 +    
  12.189 +    elements = array->data;
  12.190 +    UCX_TEST_ASSERT(array->size == 3, "incorrect size after append");
  12.191 +    UCX_TEST_ASSERT(elements[1] == 13, "failed");
  12.192 +    UCX_TEST_ASSERT(elements[2] == 37, "failed");
  12.193 +    UCX_TEST_ASSERT(elements[0] == 42,
  12.194 +            "append corrupted previously inserted data");
  12.195 +    
  12.196 +    UCX_TEST_END
  12.197 +    
  12.198 +    ucx_array_destroy(array);
  12.199 +}
  12.200 +
  12.201 +UCX_TEST(test_ucx_array_prepend) {
  12.202 +    int *elems;
  12.203 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.204 +    
  12.205 +    ucx_array_prepend(array, 42);
  12.206 +    UCX_TEST_BEGIN
  12.207 +    
  12.208 +    elems = array->data;
  12.209 +    UCX_TEST_ASSERT(elems[0] == 42, "failed");
  12.210 +    
  12.211 +    ucx_array_prepend(array, 37);
  12.212 +    ucx_array_prepend(array, 13);
  12.213 +    
  12.214 +    elems = array->data;
  12.215 +    UCX_TEST_ASSERT(array->size == 3, "incorrect size after prepend");
  12.216 +    UCX_TEST_ASSERT(elems[0] == 13, "failed");
  12.217 +    UCX_TEST_ASSERT(elems[1] == 37, "failed");
  12.218 +    UCX_TEST_ASSERT(elems[2] == 42,
  12.219 +            "prepend corrupted previously inserted data");
  12.220 +    
  12.221 +    UCX_TEST_END
  12.222 +    
  12.223 +    ucx_array_free(array);
  12.224 +}
  12.225 +
  12.226 +UCX_TEST(test_ucx_array_set) {
  12.227 +    int *elems;
  12.228 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.229 +
  12.230 +    UCX_TEST_BEGIN
  12.231 +
  12.232 +    ucx_array_set(array, 7, 42);
  12.233 +    
  12.234 +    elems = array->data;
  12.235 +    UCX_TEST_ASSERT(elems[7] == 42, "failed");
  12.236 +    UCX_TEST_ASSERT(array->size == 8, "array not resized on set");
  12.237 +    UCX_TEST_ASSERT(array->capacity == 16, "capacity changed unnecessarily");
  12.238 +    
  12.239 +    ucx_array_set(array, 27, 13);
  12.240 +    ucx_array_set(array, 28, 37);
  12.241 +    
  12.242 +    elems = array->data;
  12.243 +    UCX_TEST_ASSERT(elems[27] == 13, "failed");
  12.244 +    UCX_TEST_ASSERT(elems[28] == 37, "failed");
  12.245 +    UCX_TEST_ASSERT(array->size == 29, "array not resized on set");
  12.246 +    UCX_TEST_ASSERT(array->capacity == 32, "capacity not grown");
  12.247 +        
  12.248 +    UCX_TEST_END
  12.249 +    
  12.250 +    ucx_array_free(array);
  12.251 +}
  12.252 +
  12.253 +UCX_TEST(test_ucx_array_equals) {
  12.254 +    UcxArray *a1 = ucx_array_new(16, sizeof(int32_t));
  12.255 +    UcxArray *a2 = ucx_array_new(16, sizeof(int32_t));
  12.256 +    UcxArray *a3 = ucx_array_new(16, sizeof(int64_t));
  12.257 +    UcxArray *a4 = ucx_array_new(16, sizeof(int32_t));
  12.258 +    
  12.259 +    int32_t *intelems;
  12.260 +    int64_t *longintelems;
  12.261 +    
  12.262 +    a1->size = 5;
  12.263 +    intelems = a1->data;
  12.264 +    intelems[0] = 47;
  12.265 +    intelems[1] = 11;
  12.266 +    intelems[2] = 0;
  12.267 +    intelems[3] = 8;
  12.268 +    intelems[4] = 15;
  12.269 +    a2->size = 5;
  12.270 +    intelems = a2->data;
  12.271 +    intelems[0] = 47;
  12.272 +    intelems[1] = 11;
  12.273 +    intelems[2] = 0;
  12.274 +    intelems[3] = 8;
  12.275 +    intelems[4] = 15;
  12.276 +    a3->size = 5;
  12.277 +    longintelems = a3->data;
  12.278 +    longintelems[0] = 47;
  12.279 +    longintelems[1] = 11;
  12.280 +    longintelems[2] = 0;
  12.281 +    longintelems[3] = 8;
  12.282 +    longintelems[4] = 15;
  12.283 +    a4->size = 5;
  12.284 +    intelems = a4->data;
  12.285 +    intelems[0] = 47;
  12.286 +    intelems[1] = 11;
  12.287 +    intelems[2] = -6;
  12.288 +    intelems[3] = 8;
  12.289 +    intelems[4] = 15;
  12.290 +    
  12.291 +    UCX_TEST_BEGIN
  12.292 +    
  12.293 +    UCX_TEST_ASSERT(ucx_array_equals(a1, a2, ucx_cmp_int32, NULL), "failed");
  12.294 +    UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, ucx_cmp_int32, NULL), "failed");
  12.295 +    UCX_TEST_ASSERT(!ucx_array_equals(a4, a1, ucx_cmp_int32, NULL), "failed");
  12.296 +    UCX_TEST_ASSERT(!ucx_array_equals(a1, a3, ucx_cmp_int64, NULL),
  12.297 +            "comparing arrays of different element size shall fail");
  12.298 +    UCX_TEST_ASSERT(!ucx_array_equals(a3, a1, ucx_cmp_int64, NULL),
  12.299 +            "comparing arrays of different element size shall fail");
  12.300 +    
  12.301 +    UCX_TEST_ASSERT(ucx_array_equals(a1, a2, NULL, NULL),
  12.302 +            "compare using memcmp() failed");
  12.303 +    UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, NULL, NULL),
  12.304 +            "compare using memcmp() failed");
  12.305 +    
  12.306 +    UCX_TEST_END
  12.307 +    ucx_array_free(a1);
  12.308 +    ucx_array_free(a2);
  12.309 +    ucx_array_free(a3);
  12.310 +    ucx_array_free(a4);
  12.311 +}
  12.312 +
  12.313 +UCX_TEST(test_ucx_array_concat) {
  12.314 +    UcxArray *a1 = ucx_array_new(16, sizeof(int));
  12.315 +    UcxArray *a2 = ucx_array_new(16, sizeof(int));
  12.316 +    int *elems;
  12.317 +    
  12.318 +    a1->size = 2;
  12.319 +    elems = a1->data;
  12.320 +    elems[0] = 47;
  12.321 +    elems[1] = 11;
  12.322 +    a2->size = 3;
  12.323 +    elems = a2->data;
  12.324 +    elems[0] = 0;
  12.325 +    elems[1] = 8;
  12.326 +    elems[2] = 15;
  12.327 +    
  12.328 +    UCX_TEST_BEGIN
  12.329 +    
  12.330 +    UCX_TEST_ASSERT(!ucx_array_concat(a1, a2), "failed");
  12.331 +    UCX_TEST_ASSERT(a1->size == 5, "failed");
  12.332 +    elems = a1->data;
  12.333 +    UCX_TEST_ASSERT(elems[0] == 47, "failed");
  12.334 +    UCX_TEST_ASSERT(elems[1] == 11, "failed");
  12.335 +    UCX_TEST_ASSERT(elems[2] == 0, "failed");
  12.336 +    UCX_TEST_ASSERT(elems[3] == 8, "failed");
  12.337 +    UCX_TEST_ASSERT(elems[4] == 15, "failed");
  12.338 +    
  12.339 +    a1->elemsize *= 2;
  12.340 +    UCX_TEST_ASSERT(ucx_array_concat(a1, a2),
  12.341 +            "arrays of different element size must not be concatenated");
  12.342 +    UCX_TEST_ASSERT(a1->size == 5,
  12.343 +            "arrays of different element size must not be concatenated");
  12.344 +    
  12.345 +    UCX_TEST_END
  12.346 +    ucx_array_free(a1);
  12.347 +    ucx_array_free(a2);    
  12.348 +}
  12.349 +
  12.350 +UCX_TEST(test_ucx_array_at) {
  12.351 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.352 +    
  12.353 +    int x[3] = {42, 13, 5};
  12.354 +    ucx_array_append_from(array, x, 3);
  12.355 +    
  12.356 +    UCX_TEST_BEGIN
  12.357 +    
  12.358 +    UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 1) == 13, "failed");
  12.359 +    *(int*)ucx_array_at(array, 1) = 80;
  12.360 +    UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 1) == 80, "assignment failed");
  12.361 +    
  12.362 +    UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 0) == 42, "corrupted data");
  12.363 +    UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 2) == 5, "corrupted data");
  12.364 +    
  12.365 +    UCX_TEST_END
  12.366 +    
  12.367 +    ucx_array_free(array);
  12.368 +}
  12.369 +
  12.370 +UCX_TEST(test_ucx_array_find) {
  12.371 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.372 +    int *elems;
  12.373 +    
  12.374 +    array->size = 5;
  12.375 +    elems = array->data;
  12.376 +    elems[0] = 47;
  12.377 +    elems[1] = 11;
  12.378 +    elems[2] = 0;
  12.379 +    elems[3] = 8;
  12.380 +    elems[4] = 15;
  12.381 +    
  12.382 +    int x = 8;
  12.383 +    int y = 90;
  12.384 +    
  12.385 +    UCX_TEST_BEGIN
  12.386 +    
  12.387 +    UCX_TEST_ASSERT(ucx_array_find(array,(void*)&x,ucx_cmp_int,NULL) == 3,
  12.388 +        "doesn't find element");
  12.389 +    UCX_TEST_ASSERT(ucx_array_find(array,(void*)&y,ucx_cmp_int,NULL) == 5,
  12.390 +        "finds non-existing element");
  12.391 +    
  12.392 +    UCX_TEST_ASSERT(ucx_array_find(array,(void*)&x,NULL,NULL) == 3,
  12.393 +        "failed using memcmp()");
  12.394 +    UCX_TEST_ASSERT(ucx_array_find(array,(void*)&y,NULL,NULL) == 5,
  12.395 +        "failed using memcmp()");
  12.396 +    
  12.397 +    UCX_TEST_END
  12.398 +    ucx_array_free(array);
  12.399 +}
  12.400 +
  12.401 +UCX_TEST(test_ucx_array_contains) {
  12.402 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.403 +    int *elems;
  12.404 +    
  12.405 +    array->size = 5;
  12.406 +    elems = array->data;
  12.407 +    elems[0] = 47;
  12.408 +    elems[1] = 11;
  12.409 +    elems[2] = 0;
  12.410 +    elems[3] = 8;
  12.411 +    elems[4] = 15;
  12.412 +    
  12.413 +    int x = 8;
  12.414 +    int y = 90;
  12.415 +    
  12.416 +    UCX_TEST_BEGIN
  12.417 +    
  12.418 +    UCX_TEST_ASSERT(ucx_array_contains(array,(void*)&x,ucx_cmp_int,NULL),
  12.419 +        "false negative");
  12.420 +    UCX_TEST_ASSERT(!ucx_array_contains(array,(void*)&y,ucx_cmp_int,NULL),
  12.421 +        "false positive");
  12.422 +    
  12.423 +    UCX_TEST_ASSERT(ucx_array_contains(array,(void*)&x,NULL,NULL),
  12.424 +        "false negative using memcmp()");
  12.425 +    UCX_TEST_ASSERT(!ucx_array_contains(array,(void*)&y,NULL,NULL),
  12.426 +        "false positive using memcmp()");
  12.427 +    
  12.428 +    UCX_TEST_END
  12.429 +    ucx_array_free(array);
  12.430 +}
  12.431 +
  12.432 +UCX_TEST(test_ucx_array_remove) {
  12.433 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.434 +    int *elems;
  12.435 +    
  12.436 +    array->size = 5;
  12.437 +    elems = array->data;
  12.438 +    elems[0] = 47;
  12.439 +    elems[1] = 11;
  12.440 +    elems[2] = 0;
  12.441 +    elems[3] = 8;
  12.442 +    elems[4] = 15;
  12.443 +        
  12.444 +    UCX_TEST_BEGIN
  12.445 +    
  12.446 +    ucx_array_remove(array, 2);
  12.447 +    elems = array->data;
  12.448 +    UCX_TEST_ASSERT(
  12.449 +            elems[0] == 47 &&
  12.450 +            elems[1] == 11 &&
  12.451 +            elems[2] == 8 &&
  12.452 +            elems[3] == 15,
  12.453 +            "wrong contents after remove");
  12.454 +    UCX_TEST_ASSERT(array->size == 4, "wrong size after remove");
  12.455 +    
  12.456 +    ucx_array_remove_fast(array, 1);
  12.457 +    elems = array->data;
  12.458 +    UCX_TEST_ASSERT(
  12.459 +            elems[0] == 47 &&
  12.460 +            elems[1] == 15 &&
  12.461 +            elems[2] == 8,
  12.462 +            "wrong contents after fast remove");
  12.463 +    UCX_TEST_ASSERT(array->size == 3, "wrong size after fast remove");
  12.464 +    
  12.465 +    UCX_TEST_END
  12.466 +    ucx_array_free(array);
  12.467 +}
  12.468 +
  12.469 +UCX_TEST(test_ucx_array_clone) {
  12.470 +    UcxArray array;
  12.471 +    UcxArray copy;
  12.472 +    ucx_array_init(&array, 16, sizeof(int));
  12.473 +    ucx_array_init(&copy, 4, 2*sizeof(double));
  12.474 +    int *elems;
  12.475 +    
  12.476 +    array.size = 5;
  12.477 +    elems = array.data;
  12.478 +    elems[0] = 47;
  12.479 +    elems[1] = 11;
  12.480 +    elems[2] = 0;
  12.481 +    elems[3] = 8;
  12.482 +    elems[4] = 15;
  12.483 +    
  12.484 +    ucx_array_clone(&copy, &array);
  12.485 +    UCX_TEST_BEGIN
  12.486 +
  12.487 +    UCX_TEST_ASSERT(array.data != copy.data, "no true copy");
  12.488 +    UCX_TEST_ASSERT(array.size == copy.size, "size mismatch");
  12.489 +    UCX_TEST_ASSERT(array.capacity == copy.capacity, "capacity mismatch");
  12.490 +    UCX_TEST_ASSERT(array.elemsize == copy.elemsize, "element size mismatch");
  12.491 +    UCX_TEST_ASSERT(array.allocator == copy.allocator, "allocator mismatch");
  12.492 +    UCX_TEST_ASSERT(ucx_array_equals(&array, &copy, ucx_cmp_int, NULL),
  12.493 +            "contents do not match after clone");
  12.494 +    
  12.495 +    UCX_TEST_END
  12.496 +
  12.497 +    ucx_array_destroy(&array);
  12.498 +    ucx_array_destroy(&copy);
  12.499 +}
  12.500 +
  12.501 +static int ucx_cmp_int_reverse(const void* x, const void* y, void* data) {
  12.502 +    return -ucx_cmp_int(x,y,data);
  12.503 +}
  12.504 +
  12.505 +UCX_TEST(test_ucx_array_sort) {
  12.506 +    int *elems;
  12.507 +
  12.508 +    UcxArray *array = ucx_array_new(16, sizeof(int));    
  12.509 +    array->size = 5;
  12.510 +    elems = array->data;
  12.511 +    elems[0] = 47;
  12.512 +    elems[1] = 11;
  12.513 +    elems[2] = 0;
  12.514 +    elems[3] = 8;
  12.515 +    elems[4] = 15;
  12.516 +    
  12.517 +    UcxArray *expected = ucx_array_new(16, sizeof(int));
  12.518 +    expected->size = 5;
  12.519 +    elems = expected->data;
  12.520 +    elems[0] = 0;
  12.521 +    elems[1] = 8;
  12.522 +    elems[2] = 11;
  12.523 +    elems[3] = 15;
  12.524 +    elems[4] = 47;
  12.525 +    
  12.526 +    UcxArray *expectedrev = ucx_array_new(16, sizeof(int));
  12.527 +    expectedrev->size = 5;
  12.528 +    elems = expectedrev->data;
  12.529 +    elems[0] = 47;
  12.530 +    elems[1] = 15;
  12.531 +    elems[2] = 11;
  12.532 +    elems[3] = 8;
  12.533 +    elems[4] = 0;
  12.534 +    
  12.535 +
  12.536 +    UCX_TEST_BEGIN
  12.537 +    void* original_ptr = array->data;
  12.538 +    ucx_array_sort(array, ucx_cmp_int, NULL);
  12.539 +    UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL), "failed");
  12.540 +    UCX_TEST_ASSERT(array->size == 5, "size corrupted");
  12.541 +    UCX_TEST_ASSERT(array->data == original_ptr, "shall not reallocate");
  12.542 +    
  12.543 +    ucx_array_sort(array, ucx_cmp_int_reverse, NULL);
  12.544 +    UCX_TEST_ASSERT(ucx_array_equals(array, expectedrev, NULL, NULL), "failed");
  12.545 +
  12.546 +    ucx_array_reserve(array, 32);
  12.547 +    ucx_array_reserve(expected, 32);
  12.548 +    array->size = expected->size = 32;
  12.549 +    for (size_t i = 0 ; i < 32 ; i++) {
  12.550 +        ((int*)array->data)[i]= ((i%2==0)?-1:1) * ((int) i);
  12.551 +        ((int*)expected->data)[i] = (-30+2*i) - (i > 15 ? 1 : 0);
  12.552 +    }
  12.553 +    
  12.554 +    /* dummy third argument to trigger a possible fallback for qsort_s */
  12.555 +    ucx_array_sort(array, ucx_cmp_int, array->data);
  12.556 +    UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL),
  12.557 +            "failed for bigger arrays");
  12.558 +    UCX_TEST_END
  12.559 +
  12.560 +    ucx_array_free(expectedrev);
  12.561 +    ucx_array_free(expected);
  12.562 +    ucx_array_free(array);
  12.563 +}
  12.564 +
  12.565 +UCX_TEST(test_ucx_array_autogrow) {
  12.566 +    int *elems;
  12.567 +    UcxArray *array = ucx_array_new(4, sizeof(int));
  12.568 +    array->size = 3;
  12.569 +    elems = array->data;
  12.570 +    elems[0] = 47;
  12.571 +    elems[1] = 11;
  12.572 +    int x = 5;
  12.573 +    
  12.574 +    UCX_TEST_BEGIN
  12.575 +
  12.576 +    void* oldptr = array->data;
  12.577 +    
  12.578 +    ucx_array_append(array, 5);
  12.579 +    UCX_TEST_ASSERT(array->capacity == 4 && array->data == oldptr,
  12.580 +            "array should not grow too early");
  12.581 +    ucx_array_append(array, 5);
  12.582 +    elems = array->data;
  12.583 +    UCX_TEST_ASSERT(array->capacity == 8, "array did not grow");
  12.584 +    UCX_TEST_ASSERT(array->size == 5, "incorrect size after grow");
  12.585 +    UCX_TEST_ASSERT(elems[3] == 5 && elems[4] == 5, "corrupt data");
  12.586 +    
  12.587 +    UCX_TEST_END
  12.588 +    ucx_array_free(array);
  12.589 +}
  12.590 +
  12.591 +UCX_TEST(test_ucx_array_shrink) {
  12.592 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.593 +    array->size = 4;
  12.594 +    
  12.595 +    UCX_TEST_BEGIN
  12.596 +    UCX_TEST_ASSERT(!ucx_array_shrink(array), "failed");
  12.597 +    UCX_TEST_ASSERT(array->capacity == 4, "incorrect capacity after shrink");
  12.598 +    UCX_TEST_END
  12.599 +    ucx_array_free(array);
  12.600 +}
  12.601 +
  12.602 +UCX_TEST(test_ucx_array_resize) {
  12.603 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.604 +    array->size = 8;
  12.605 +    
  12.606 +    UCX_TEST_BEGIN
  12.607 +
  12.608 +    UCX_TEST_ASSERT(!ucx_array_resize(array, 32), "failed");
  12.609 +    UCX_TEST_ASSERT(array->capacity == 32, "incorrect capacity after resize");
  12.610 +    UCX_TEST_ASSERT(array->size == 8, "incorrect size after resize");
  12.611 +    
  12.612 +    UCX_TEST_ASSERT(!ucx_array_resize(array, 4), "failed");
  12.613 +    UCX_TEST_ASSERT(array->capacity == 4, "incorrect capacity after resize");
  12.614 +    UCX_TEST_ASSERT(array->size == 4, "incorrect size after resize");
  12.615 +    
  12.616 +    UCX_TEST_END
  12.617 +    ucx_array_free(array);
  12.618 +}
  12.619 +
  12.620 +UCX_TEST(test_ucx_array_reserve) {
  12.621 +    UcxArray *array = ucx_array_new(16, sizeof(int));
  12.622 +    
  12.623 +    UCX_TEST_BEGIN
  12.624 +
  12.625 +    UCX_TEST_ASSERT(!ucx_array_reserve(array, 4), "failed");
  12.626 +    UCX_TEST_ASSERT(array->capacity == 16, "reserve shall not shrink");
  12.627 +            
  12.628 +    UCX_TEST_ASSERT(!ucx_array_resize(array, 32), "failed");
  12.629 +    UCX_TEST_ASSERT(array->capacity == 32, "incorrect capacity after reserve");    
  12.630 +    
  12.631 +    UCX_TEST_END
  12.632 +    ucx_array_free(array);
  12.633 +}
  12.634 +
  12.635 +UCX_TEST(test_ucx_array_util_set) {
  12.636 +    size_t capacity = 16;
  12.637 +    int* array = malloc(sizeof(int)*capacity);
  12.638 +
  12.639 +    UCX_TEST_BEGIN
  12.640 +
  12.641 +    UCX_ARRAY_UTIL_SET(&array, &capacity, 7, 42);
  12.642 +    
  12.643 +    UCX_TEST_ASSERT(array[7] == 42, "failed");
  12.644 +    UCX_TEST_ASSERT(capacity == 16, "capacity changed unnecessarily");
  12.645 +    
  12.646 +    UCX_ARRAY_UTIL_SET(&array, &capacity, 37, 13);
  12.647 +    UCX_ARRAY_UTIL_SET(&array, &capacity, 38, 37);
  12.648 +    
  12.649 +    UCX_TEST_ASSERT(array[37] == 13, "failed");
  12.650 +    UCX_TEST_ASSERT(array[38] == 37, "failed");
  12.651 +    UCX_TEST_ASSERT(capacity == 64, "capacity not grown");
  12.652 +        
  12.653 +    UCX_TEST_END
  12.654 +    
  12.655 +    free(array);
  12.656 +}

    13.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    13.2 +++ b/test/array_tests.h	Sat Oct 05 16:58:16 2019 +0200
    13.3 @@ -0,0 +1,66 @@
    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_destroy);
   13.43 +UCX_TEST(test_ucx_array_new);
   13.44 +UCX_TEST(test_ucx_array_at);
   13.45 +UCX_TEST(test_ucx_array_append_from);
   13.46 +UCX_TEST(test_ucx_array_prepend_from);
   13.47 +UCX_TEST(test_ucx_array_set_from);
   13.48 +UCX_TEST(test_ucx_array_append);
   13.49 +UCX_TEST(test_ucx_array_prepend);
   13.50 +UCX_TEST(test_ucx_array_set);
   13.51 +UCX_TEST(test_ucx_array_autogrow);
   13.52 +UCX_TEST(test_ucx_array_equals);
   13.53 +UCX_TEST(test_ucx_array_concat);
   13.54 +UCX_TEST(test_ucx_array_find);
   13.55 +UCX_TEST(test_ucx_array_contains);
   13.56 +UCX_TEST(test_ucx_array_remove);
   13.57 +UCX_TEST(test_ucx_array_clone);
   13.58 +UCX_TEST(test_ucx_array_sort);
   13.59 +UCX_TEST(test_ucx_array_shrink);
   13.60 +UCX_TEST(test_ucx_array_resize);
   13.61 +UCX_TEST(test_ucx_array_reserve);
   13.62 +UCX_TEST(test_ucx_array_util_set);
   13.63 +
   13.64 +#ifdef	__cplusplus
   13.65 +}
   13.66 +#endif
   13.67 +
   13.68 +#endif	/* ARRAY_TESTS_H */
   13.69 +

    14.1 --- a/test/main.c	Sat Aug 10 08:46:38 2019 +0200
    14.2 +++ b/test/main.c	Sat Oct 05 16:58:16 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,29 @@
   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_destroy);
   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_from);
   14.20 +        ucx_test_register(suite, test_ucx_array_prepend_from);
   14.21 +        ucx_test_register(suite, test_ucx_array_set_from);
   14.22 +        ucx_test_register(suite, test_ucx_array_append);
   14.23 +        ucx_test_register(suite, test_ucx_array_prepend);
   14.24 +        ucx_test_register(suite, test_ucx_array_set);
   14.25 +        ucx_test_register(suite, test_ucx_array_autogrow);
   14.26 +        ucx_test_register(suite, test_ucx_array_equals);
   14.27 +        ucx_test_register(suite, test_ucx_array_concat);
   14.28 +        ucx_test_register(suite, test_ucx_array_find);
   14.29 +        ucx_test_register(suite, test_ucx_array_contains);
   14.30 +        ucx_test_register(suite, test_ucx_array_remove);
   14.31 +        ucx_test_register(suite, test_ucx_array_clone);
   14.32 +        ucx_test_register(suite, test_ucx_array_sort);
   14.33 +        ucx_test_register(suite, test_ucx_array_shrink);
   14.34 +        ucx_test_register(suite, test_ucx_array_resize);
   14.35 +        ucx_test_register(suite, test_ucx_array_reserve);
   14.36 +        ucx_test_register(suite, test_ucx_array_util_set);
   14.37 +        
   14.38          /* UcxList Tests */
   14.39          ucx_test_register(suite, test_ucx_list_append);
   14.40          ucx_test_register(suite, test_ucx_list_prepend);