ucx: src/array.c@77efe51c6c9a

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    29 #define _GNU_SOURCE /* we want to use qsort_r(), if available */

    30 #define __STDC_WANT_LIB_EXT1__ 1 /* use qsort_s, if available */

    33 #include "ucx/array.h"

    34 #include "ucx/utils.h"

    36 #include <string.h>

    37 #include <stdlib.h>

    38 #include <errno.h>

    40 #ifndef UCX_ARRAY_DISABLE_QSORT

    41 #ifdef __GLIBC__

    42 #if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)

    43 #define ucx_array_sort_impl qsort_r

    44 #endif /* glibc version >= 2.8 */

    45 #elif /* not  __GLIBC__ */ defined(__APPLE__) || defined(__FreeBSD__)

    46 #define ucx_array_sort_impl ucx_qsort_r

    47 #define USE_UCX_QSORT_R

    48 #elif /* not (__APPLE || __FreeBSD__) */ defined(__sun)

    49 #if __STDC_VERSION__ >= 201112L

    50 #define ucx_array_sort_impl qsort_s

    51 #endif

    52 #endif /* __GLIBC__, __APLE__, __FreeBSD__, __sun */

    53 #endif /* UCX_ARRAY_DISABLE_QSORT */

    55 #ifndef ucx_array_sort_impl

    56 #define ucx_array_sort_impl ucx_mergesort

    57 #endif

    59 static int ucx_array_ensurecap(UcxArray *array, size_t reqcap) {

    60     size_t required_capacity = array->capacity;

    61     while (reqcap > required_capacity) {

    62         if (required_capacity * 2 < required_capacity)

    63             return 1;

    64         required_capacity <<= 1;

    65     }

    66     if (ucx_array_reserve(array, required_capacity)) {

    67         return 1;

    68     }

    69 }

    71 int ucx_array_util_set_a(UcxAllocator* alloc, void** array, size_t* capacity,

    72     size_t elmsize, size_t index, ...) {

    74     if(!alloc || !capacity || !array) {

    75         errno = EINVAL;

    76         return 1;

    77     }

    79     size_t newcapacity = *capacity;

    80     while(index >= newcapacity) {

    81         if(ucx_szmul(newcapacity, 2, &newcapacity)) {

    82             errno = EOVERFLOW;

    83             return 1;

    84         }

    85     }

    87     size_t memlen, offset;

    88     if(ucx_szmul(newcapacity, elmsize, &memlen)) {

    89         errno = EOVERFLOW;

    90         return 1;

    91     }

    92     /* we don't need to check index*elmsize - it is smaller than memlen */

    95     void* newptr = alrealloc(alloc, *array, memlen);

    96     if(newptr == NULL) {

    97         errno = ENOMEM; /* we cannot assume that every allocator sets this */

    98         return 1;

    99     }

   100     *array = newptr;

   101     *capacity = newcapacity;

   104     char* dest = *array;

   105     dest += elmsize*index;

   107     va_list ap;

   108     va_start(ap, index);

   109     int elem = va_arg(ap, int);

   110     memcpy(dest, &elem, elmsize);

   111     va_end(ap);

   113     return 0;

   114 }

   116 UcxArray* ucx_array_new(size_t capacity, size_t elemsize) {

   117     return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());

   118 }

   120 UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize,

   121         UcxAllocator* allocator) {

   122     UcxArray* array = almalloc(allocator, sizeof(UcxArray));

   123     if(array) {

   124         ucx_array_init_a(array, capacity, elemsize, allocator);

   125     }

   126     return array;

   127 }

   129 void ucx_array_init(UcxArray* array, size_t capacity, size_t elemsize) {

   130     ucx_array_init_a(array, capacity, elemsize, ucx_default_allocator());

   131 }

   133 void ucx_array_init_a(UcxArray* array, size_t capacity, size_t elemsize,

   134         UcxAllocator* allocator) {

   136     array->allocator = allocator;

   137     array->elemsize = elemsize;

   138     array->size = 0;

   139     array->data = alcalloc(allocator, capacity, elemsize);

   141     if (array->data) {

   142         array->capacity = capacity;

   143     } else {

   144         array->capacity = 0;

   145     }

   146 }

   148 int ucx_array_clone(UcxArray* dest, UcxArray const* src) {

   149     if (ucx_array_ensurecap(dest, src->capacity)) {

   150         return 1;

   151     }

   153     dest->elemsize = src->elemsize;

   154     dest->size = src->size;

   156     if (dest->data) {

   157         memcpy(dest->data, src->data, src->size*src->elemsize);

   158     }

   160     return 0;

   161 }

   163 int ucx_array_equals(UcxArray const *array1, UcxArray const *array2,

   164         cmp_func cmpfnc, void* data) {

   166     if (array1->size != array2->size || array1->elemsize != array2->elemsize) {

   167         return 0;

   168     } else {

   169         if (array1->size == 0)

   170             return 1;

   172         size_t elemsize;

   173         if (cmpfnc == NULL) {

   174             cmpfnc = ucx_cmp_mem;

   175             elemsize = array1->elemsize;

   176             data = &elemsize;

   177         }

   179         for (size_t i = 0 ; i < array1->size ; i++) {

   180             int r = cmpfnc(

   181                     ucx_array_at(array1, i),

   182                     ucx_array_at(array2, i),

   183                     data);

   184             if (r != 0)

   185                 return 0;

   186         }

   187         return 1;

   188     }

   189 }

   191 void ucx_array_destroy(UcxArray *array) {

   192     if(array->data)

   193         alfree(array->allocator, array->data);

   194     array->data = NULL;

   195     array->capacity = array->size = 0;

   196 }

   198 void ucx_array_free(UcxArray *array) {

   199     ucx_array_destroy(array);

   200     alfree(array->allocator, array);

   201 }

   203 int ucx_array_append_from(UcxArray *array, void *data, size_t count) {

   204     if (ucx_array_ensurecap(array, array->size + count))

   205         return 1;

   207     void* dest = ucx_array_at(array, array->size);

   208     if (data) {

   209         memcpy(dest, data, array->elemsize*count);

   210     } else {

   211         memset(dest, 0, array->elemsize*count);

   212     }

   213     array->size += count;

   215     return 0;

   216 }

   218 int ucx_array_prepend_from(UcxArray *array, void *data, size_t count) {

   219     if (ucx_array_ensurecap(array, array->size + count))

   220         return 1;

   222     if (array->size > 0) {

   223         void *dest = ucx_array_at(array, count);

   224         memmove(dest, array->data, array->elemsize*array->size);

   225     }

   227     if (data) {

   228         memcpy(array->data, data, array->elemsize*count);

   229     } else {

   230         memset(array->data, 0, array->elemsize*count);

   231     }

   232     array->size += count;

   234     return 0;

   235 }

   237 int ucx_array_set_from(UcxArray *array, size_t index,

   238         void *data, size_t count) {

   239     if (ucx_array_ensurecap(array, index + count))

   240         return 1;

   242     if (index+count > array->size) {

   243         array->size = index+count;

   244     }

   246     void *dest = ucx_array_at(array, index);

   247     if (data) {

   248         memcpy(dest, data, array->elemsize*count);

   249     } else {

   250         memset(dest, 0, array->elemsize*count);

   251     }

   253     return 0;

   254 }

   256 int ucx_array_appendv(UcxArray *array, ...) {

   257     va_list ap;

   258     va_start(ap, array);

   259     int elem = va_arg(ap, int);

   260     int ret = ucx_array_append_from(array, &elem, 1);

   261     va_end(ap);

   262     return ret;

   263 }

   265 int ucx_array_prependv(UcxArray *array, ...) {

   266     va_list ap;

   267     va_start(ap, array);

   268     int elem = va_arg(ap, int);

   269     int ret = ucx_array_prepend_from(array, &elem, 1);

   270     va_end(ap);

   271     return ret;

   272 }

   274 int ucx_array_setv(UcxArray *array, size_t index, ...) {

   275     va_list ap;

   276     va_start(ap, index);

   277     int elem = va_arg(ap, int);

   278     int ret = ucx_array_set_from(array, index, &elem, 1);

   279     va_end(ap);

   280     return ret;

   281 }

   283 int ucx_array_concat(UcxArray *array1, const UcxArray *array2) {

   285     if (array1->elemsize != array2->elemsize)

   286         return 1;

   288     size_t capacity = array1->capacity+array2->capacity;

   290     if (array1->capacity < capacity) {

   291         if (ucx_array_reserve(array1, capacity)) {

   292             return 1;

   293         }

   294     }

   296     void* dest = ucx_array_at(array1, array1->size);

   297     memcpy(dest, array2->data, array2->size*array2->elemsize);

   299     array1->size += array2->size;

   301     return 0;

   302 }

   304 void *ucx_array_at(UcxArray const *array, size_t index) {

   305     char* memory = array->data;

   306     char* loc = memory + index*array->elemsize;

   307     return loc;

   308 }

   310 size_t ucx_array_find(UcxArray const *array, void *elem,

   311         cmp_func cmpfnc, void *data) {

   313     size_t elemsize;

   314     if (cmpfnc == NULL) {

   315         cmpfnc = ucx_cmp_mem;

   316         elemsize = array->elemsize;

   317         data = &elemsize;

   318     }

   320     if (array->size > 0) {

   321         for (size_t i = 0 ; i < array->size ; i++) {

   322             void* ptr = ucx_array_at(array, i);

   323             if (cmpfnc(ptr, elem, data) == 0) {

   324                 return i;

   325             }

   326         }

   327         return array->size;

   328     } else {

   329         return 0;

   330     }

   331 }

   333 int ucx_array_contains(UcxArray const *array, void *elem,

   334         cmp_func cmpfnc, void *data) {

   335     return ucx_array_find(array, elem, cmpfnc, data) != array->size;

   336 }

   338 static void ucx_mergesort_merge(void *arrdata,size_t elemsize,

   339         cmp_func cmpfnc, void *data,

   340         size_t start, size_t mid, size_t end) {

   342     char* array = arrdata;

   344     size_t rightstart = mid + 1;

   346     if (cmpfnc(array + mid*elemsize,

   347             array + rightstart*elemsize, data) <= 0) {

   348         /* already sorted */

   349         return;

   350     }

   352     /* we need memory for one element */

   353     void *value = malloc(elemsize);

   355     while (start <= mid && rightstart <= end) {

   356         if (cmpfnc(array + start*elemsize,

   357                 array + rightstart*elemsize, data) <= 0) {

   358             start++;

   359         } else {

   360             /* save the value from the right */

   361             memcpy(value, array + rightstart*elemsize, elemsize);

   363             /* shift all left elements one element to the right */

   364             size_t shiftcount = rightstart-start;

   365             void *startptr = array + start*elemsize;

   366             void *dest = array + (start+1)*elemsize;

   367             memmove(dest, startptr, shiftcount*elemsize);

   369             /* bring the first value from the right to the left */

   370             memcpy(startptr, value, elemsize);

   372             start++;

   373             mid++;

   374             rightstart++;

   375         }

   376     }

   378     /* free the temporary memory */

   379     free(value);

   380 }

   382 static void ucx_mergesort_impl(void *arrdata, size_t elemsize,

   383         cmp_func cmpfnc, void *data, size_t l, size_t r) {

   384     if (l < r) {

   385         size_t m = l + (r - l) / 2;

   387         ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m);

   388         ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r);

   389         ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);

   390     }

   391 }

   393 static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,

   394         cmp_func cmpfnc, void *data) {

   396     ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);

   397 }

   399 #ifdef USE_UCX_QSORT_R

   400 struct cmpfnc_swapargs_info {

   401     cmp_func func;

   402     void *data;

   403 };

   405 static int cmp_func_swap_args(void *data, const void *x, const void *y) {

   406     cmpfnc_swapargs_info* info = data;

   407     return info->func(x, y, info->data);

   408 }

   410 static void ucx_qsort_r(void *array, size_t count, size_t elemsize,

   411 		     cmp_func cmpfnc, void *data) {

   412     struct cmpfnc_swapargs_info info;

   413     info.func = cmpfnc;

   414     info.data = data;

   415     qsort_r(array, count, elemsize, &info, cmp_func_swap_args);

   416 }

   417 #endif /* USE_UCX_QSORT_R */

   419 void ucx_array_sort(UcxArray* array, cmp_func cmpfnc, void *data) {

   420     ucx_array_sort_impl(array->data, array->size, array->elemsize,

   421             cmpfnc, data);

   422 }

   424 void ucx_array_remove(UcxArray *array, size_t index) {

   425     array->size--;

   426     if (index < array->size) {

   427         void* dest = ucx_array_at(array, index);

   428         void* src = ucx_array_at(array, index+1);

   429         memmove(dest, src, (array->size - index)*array->elemsize);

   430     }

   431 }

   433 void ucx_array_remove_fast(UcxArray *array, size_t index) {

   434     array->size--;

   435     if (index < array->size) {

   436         void* dest = ucx_array_at(array, index);

   437         void* src = ucx_array_at(array, array->size);

   438         memcpy(dest, src, array->elemsize);

   439     }

   440 }

   442 int ucx_array_shrink(UcxArray* array) {

   443     void* newptr = alrealloc(array->allocator, array->data,

   444                 array->size*array->elemsize);

   445     if (newptr) {

   446         array->data = newptr;

   447         array->capacity = array->size;

   448         return 0;

   449     } else {

   450         return 1;

   451     }

   452 }

   454 int ucx_array_resize(UcxArray* array, size_t capacity) {

   455     if (array->capacity >= capacity) {

   456         void* newptr = alrealloc(array->allocator, array->data,

   457                 capacity*array->elemsize);

   458         if (newptr) {

   459             array->data = newptr;

   460             array->capacity = capacity;

   461             if (array->size > array->capacity) {

   462                 array->size = array->capacity;

   463             }

   464             return 0;

   465         } else {

   466             return 1;

   467         }

   468     } else {

   469         return ucx_array_reserve(array, capacity);

   470     }

   471 }

   473 int ucx_array_reserve(UcxArray* array, size_t capacity) {

   474     if (array->capacity > capacity) {

   475         return 0;

   476     } else {

   477         void* newptr = alrealloc(array->allocator, array->data,

   478                 capacity*array->elemsize);

   479         if (newptr) {

   480             array->data = newptr;

   481             array->capacity = capacity;

   482             return 0;

   483         } else {

   484             return 1;

   485         }

   486     }

   487 }

Mercurial > hg > ucx / file revision

src/array.c@77efe51c6c9a

src/array.c