ucx: src/array.c@7e0f19fe23ff

     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     return 0;

    70 }

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

    73     size_t elmsize, size_t index, ...) {

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

    76         errno = EINVAL;

    77         return 1;

    78     }

    80     size_t newcapacity = *capacity;

    81     while(index >= newcapacity) {

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

    83             errno = EOVERFLOW;

    84             return 1;

    85         }

    86     }

    88     size_t memlen, offset;

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

    90         errno = EOVERFLOW;

    91         return 1;

    92     }

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

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

    97     if(newptr == NULL) {

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

    99         return 1;

   100     }

   101     *array = newptr;

   102     *capacity = newcapacity;

   105     char* dest = *array;

   106     dest += elmsize*index;

   108     va_list ap;

   109     va_start(ap, index);

   110     int elem = va_arg(ap, int);

   111     memcpy(dest, &elem, elmsize);

   112     va_end(ap);

   114     return 0;

   115 }

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

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

   119 }

   121 UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize,

   122         UcxAllocator* allocator) {

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

   124     if(array) {

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

   126     }

   127     return array;

   128 }

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

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

   132 }

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

   135         UcxAllocator* allocator) {

   137     array->allocator = allocator;

   138     array->elemsize = elemsize;

   139     array->size = 0;

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

   142     if (array->data) {

   143         array->capacity = capacity;

   144     } else {

   145         array->capacity = 0;

   146     }

   147 }

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

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

   151         return 1;

   152     }

   154     dest->elemsize = src->elemsize;

   155     dest->size = src->size;

   157     if (dest->data) {

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

   159     }

   161     return 0;

   162 }

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

   165         cmp_func cmpfnc, void* data) {

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

   168         return 0;

   169     } else {

   170         if (array1->size == 0)

   171             return 1;

   173         size_t elemsize;

   174         if (cmpfnc == NULL) {

   175             cmpfnc = ucx_cmp_mem;

   176             elemsize = array1->elemsize;

   177             data = &elemsize;

   178         }

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

   181             int r = cmpfnc(

   182                     ucx_array_at(array1, i),

   183                     ucx_array_at(array2, i),

   184                     data);

   185             if (r != 0)

   186                 return 0;

   187         }

   188         return 1;

   189     }

   190 }

   192 void ucx_array_destroy(UcxArray *array) {

   193     if(array->data)

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

   195     array->data = NULL;

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

   197 }

   199 void ucx_array_free(UcxArray *array) {

   200     ucx_array_destroy(array);

   201     alfree(array->allocator, array);

   202 }

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

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

   206         return 1;

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

   209     if (data) {

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

   211     } else {

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

   213     }

   214     array->size += count;

   216     return 0;

   217 }

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

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

   221         return 1;

   223     if (array->size > 0) {

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

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

   226     }

   228     if (data) {

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

   230     } else {

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

   232     }

   233     array->size += count;

   235     return 0;

   236 }

   238 int ucx_array_set_from(UcxArray *array, size_t index,

   239         void *data, size_t count) {

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

   241         return 1;

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

   244         array->size = index+count;

   245     }

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

   248     if (data) {

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

   250     } else {

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

   252     }

   254     return 0;

   255 }

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

   258     va_list ap;

   259     va_start(ap, array);

   260     int elem = va_arg(ap, int);

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

   262     va_end(ap);

   263     return ret;

   264 }

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

   267     va_list ap;

   268     va_start(ap, array);

   269     int elem = va_arg(ap, int);

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

   271     va_end(ap);

   272     return ret;

   273 }

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

   276     va_list ap;

   277     va_start(ap, index);

   278     int elem = va_arg(ap, int);

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

   280     va_end(ap);

   281     return ret;

   282 }

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

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

   287         return 1;

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

   291     if (array1->capacity < capacity) {

   292         if (ucx_array_reserve(array1, capacity)) {

   293             return 1;

   294         }

   295     }

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

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

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

   302     return 0;

   303 }

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

   306     char* memory = array->data;

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

   308     return loc;

   309 }

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

   312         cmp_func cmpfnc, void *data) {

   314     size_t elemsize;

   315     if (cmpfnc == NULL) {

   316         cmpfnc = ucx_cmp_mem;

   317         elemsize = array->elemsize;

   318         data = &elemsize;

   319     }

   321     if (array->size > 0) {

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

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

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

   325                 return i;

   326             }

   327         }

   328         return array->size;

   329     } else {

   330         return 0;

   331     }

   332 }

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

   335         cmp_func cmpfnc, void *data) {

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

   337 }

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

   340         cmp_func cmpfnc, void *data,

   341         size_t start, size_t mid, size_t end) {

   343     char* array = arrdata;

   345     size_t rightstart = mid + 1;

   347     if (cmpfnc(array + mid*elemsize,

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

   349         /* already sorted */

   350         return;

   351     }

   353     /* we need memory for one element */

   354     void *value = malloc(elemsize);

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

   357         if (cmpfnc(array + start*elemsize,

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

   359             start++;

   360         } else {

   361             /* save the value from the right */

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

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

   365             size_t shiftcount = rightstart-start;

   366             void *startptr = array + start*elemsize;

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

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

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

   371             memcpy(startptr, value, elemsize);

   373             start++;

   374             mid++;

   375             rightstart++;

   376         }

   377     }

   379     /* free the temporary memory */

   380     free(value);

   381 }

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

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

   385     if (l < r) {

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

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

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

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

   391     }

   392 }

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

   395         cmp_func cmpfnc, void *data) {

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

   398 }

   400 #ifdef USE_UCX_QSORT_R

   401 struct cmpfnc_swapargs_info {

   402     cmp_func func;

   403     void *data;

   404 };

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

   407     cmpfnc_swapargs_info* info = data;

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

   409 }

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

   412 		     cmp_func cmpfnc, void *data) {

   413     struct cmpfnc_swapargs_info info;

   414     info.func = cmpfnc;

   415     info.data = data;

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

   417 }

   418 #endif /* USE_UCX_QSORT_R */

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

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

   422             cmpfnc, data);

   423 }

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

   426     array->size--;

   427     if (index < array->size) {

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

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

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

   431     }

   432 }

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

   435     array->size--;

   436     if (index < array->size) {

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

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

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

   440     }

   441 }

   443 int ucx_array_shrink(UcxArray* array) {

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

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

   446     if (newptr) {

   447         array->data = newptr;

   448         array->capacity = array->size;

   449         return 0;

   450     } else {

   451         return 1;

   452     }

   453 }

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

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

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

   458                 capacity*array->elemsize);

   459         if (newptr) {

   460             array->data = newptr;

   461             array->capacity = capacity;

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

   463                 array->size = array->capacity;

   464             }

   465             return 0;

   466         } else {

   467             return 1;

   468         }

   469     } else {

   470         return ucx_array_reserve(array, capacity);

   471     }

   472 }

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

   475     if (array->capacity > capacity) {

   476         return 0;

   477     } else {

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

   479                 capacity*array->elemsize);

   480         if (newptr) {

   481             array->data = newptr;

   482             array->capacity = capacity;

   483             return 0;

   484         } else {

   485             return 1;

   486         }

   487     }

   488 }

Mercurial > hg > ucx / file revision

src/array.c@7e0f19fe23ff

src/array.c