ucx: src/array.c@d315a068235a

     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;

   124     array.allocator = allocator;

   125     array.elemsize = elemsize;

   126     array.size = 0;

   127     array.data = alcalloc(allocator, capacity, elemsize);

   129     if (array.data) {

   130         array.capacity = capacity;

   131     } else {

   132         array.capacity = 0;

   133     }

   135     return array;

   136 }

   138 UcxArray ucx_array_clone(UcxArray array) {

   139     UcxArray clone;

   141     clone.allocator = array.allocator;

   142     clone.elemsize = array.elemsize;

   143     clone.size = array.size;

   144     clone.data = alcalloc(array.allocator, array.capacity, array.elemsize);

   146     if (clone.data) {

   147         clone.capacity = array.capacity;

   148         memcpy(clone.data, array.data, array.size*array.elemsize);

   149     } else {

   150         clone.capacity = clone.size = 0;

   151     }

   153     return clone;

   154 }

   156 int ucx_array_equals(UcxArray array1, UcxArray array2,

   157         cmp_func cmpfnc, void* data) {

   159     if (array1.size != array2.size || array1.elemsize != array2.elemsize) {

   160         return 0;

   161     } else {

   162         if (array1.size == 0)

   163             return 1;

   165         if (cmpfnc == NULL) {

   166             cmpfnc = ucx_cmp_mem;

   167             data = &array1.elemsize;

   168         }

   170         for (size_t i = 0 ; i < array1.size ; i++) {

   171             int r = cmpfnc(

   172                     ucx_array_at(array1, i),

   173                     ucx_array_at(array2, i),

   174                     data);

   175             if (r != 0)

   176                 return 0;

   177         }

   178         return 1;

   179     }

   180 }

   182 void ucx_array_destroy(UcxArray *array) {

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

   184     array->data = NULL;

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

   186 }

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

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

   190         return 1;

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

   193     if (data) {

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

   195     } else {

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

   197     }

   198     array->size += count;

   200     return 0;

   201 }

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

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

   205         return 1;

   207     if (array->size > 0) {

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

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

   210     }

   212     if (data) {

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

   214     } else {

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

   216     }

   217     array->size += count;

   219     return 0;

   220 }

   222 int ucx_array_set_from(UcxArray *array, size_t index,

   223         void *data, size_t count) {

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

   225         return 1;

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

   228         array->size = index+count;

   229     }

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

   232     if (data) {

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

   234     } else {

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

   236     }

   238     return 0;

   239 }

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

   242     va_list ap;

   243     va_start(ap, array);

   244     int elem = va_arg(ap, int);

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

   246     va_end(ap);

   247     return ret;

   248 }

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

   251     va_list ap;

   252     va_start(ap, array);

   253     int elem = va_arg(ap, int);

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

   255     va_end(ap);

   256     return ret;

   257 }

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

   260     va_list ap;

   261     va_start(ap, index);

   262     int elem = va_arg(ap, int);

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

   264     va_end(ap);

   265     return ret;

   266 }

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

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

   271         return 1;

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

   275     if (array1->capacity < capacity) {

   276         if (ucx_array_reserve(array1, capacity)) {

   277             return 1;

   278         }

   279     }

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

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

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

   286     return 0;

   287 }

   289 void *ucx_array_at(UcxArray array, size_t index) {

   290     char* memory = array.data;

   291     char* loc = memory + index*array.elemsize;

   292     return loc;

   293 }

   295 size_t ucx_array_find(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {

   297     if (cmpfnc == NULL) {

   298         cmpfnc = ucx_cmp_mem;

   299         data = &array.elemsize;

   300     }

   302     if (array.size > 0) {

   303         for (size_t i = 0 ; i < array.size ; i++) {

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

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

   306                 return i;

   307             }

   308         }

   309         return array.size;

   310     } else {

   311         return 0;

   312     }

   313 }

   315 int ucx_array_contains(UcxArray array, void *elem, cmp_func cmpfnc, void *data) {

   316     return ucx_array_find(array, elem, cmpfnc, data) != array.size;

   317 }

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

   320         cmp_func cmpfnc, void *data,

   321         size_t start, size_t mid, size_t end) {

   323     char* array = arrdata;

   325     size_t rightstart = mid + 1;

   327     if (cmpfnc(array + mid*elemsize,

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

   329         /* already sorted */

   330         return;

   331     }

   333     /* we need memory for one element */

   334     void *value = malloc(elemsize);

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

   337         if (cmpfnc(array + start*elemsize,

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

   339             start++;

   340         } else {

   341             /* save the value from the right */

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

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

   345             size_t shiftcount = rightstart-start;

   346             void *startptr = array + start*elemsize;

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

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

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

   351             memcpy(startptr, value, elemsize);

   353             start++;

   354             mid++;

   355             rightstart++;

   356         }

   357     }

   359     /* free the temporary memory */

   360     free(value);

   361 }

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

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

   365     if (l < r) {

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

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

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

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

   371     }

   372 }

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

   375         cmp_func cmpfnc, void *data) {

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

   378 }

   380 #ifdef USE_UCX_QSORT_R

   381 struct cmpfnc_swapargs_info {

   382     cmp_func func;

   383     void *data;

   384 };

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

   387     cmpfnc_swapargs_info* info = data;

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

   389 }

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

   392 		     cmp_func cmpfnc, void *data) {

   393     struct cmpfnc_swapargs_info info;

   394     info.func = cmpfnc;

   395     info.data = data;

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

   397 }

   398 #endif /* USE_UCX_QSORT_R */

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

   401     ucx_array_sort_impl(array.data, array.size, array.elemsize, cmpfnc, data);

   402 }

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

   405     array->size--;

   406     if (index < array->size) {

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

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

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

   410     }

   411 }

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

   414     array->size--;

   415     if (index < array->size) {

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

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

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

   419     }

   420 }

   422 int ucx_array_shrink(UcxArray* array) {

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

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

   425     if (newptr) {

   426         array->data = newptr;

   427         array->capacity = array->size;

   428         return 0;

   429     } else {

   430         return 1;

   431     }

   432 }

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

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

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

   437                 capacity*array->elemsize);

   438         if (newptr) {

   439             array->data = newptr;

   440             array->capacity = capacity;

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

   442                 array->size = array->capacity;

   443             }

   444             return 0;

   445         } else {

   446             return 1;

   447         }

   448     } else {

   449         return ucx_array_reserve(array, capacity);

   450     }

   451 }

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

   454     if (array->capacity > capacity) {

   455         return 0;

   456     } else {

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

   458                 capacity*array->elemsize);

   459         if (newptr) {

   460             array->data = newptr;

   461             array->capacity = capacity;

   462             return 0;

   463         } else {

   464             return 1;

   465         }

   466     }

   467 }

Mercurial > hg > ucx / file revision

src/array.c@d315a068235a

src/array.c