ucx: src/array.c@871a8ffe6c9d

     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, void* data) {

    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;

   107     memcpy(dest, data, elmsize);

   109     return 0;

   110 }

   112 int ucx_array_util_setptr_a(UcxAllocator* alloc, void** array, size_t* capacity,

   113     size_t index, void* data) {

   115     return ucx_array_util_set_a(alloc, array, capacity, sizeof(void*),

   116             index, &data);

   117 }

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

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

   121 }

   123 UcxArray* ucx_array_new_a(size_t capacity, size_t elemsize,

   124         UcxAllocator* allocator) {

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

   126     if(array) {

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

   128     }

   129     return array;

   130 }

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

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

   134 }

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

   137         UcxAllocator* allocator) {

   139     array->allocator = allocator;

   140     array->elemsize = elemsize;

   141     array->size = 0;

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

   144     if (array->data) {

   145         array->capacity = capacity;

   146     } else {

   147         array->capacity = 0;

   148     }

   149 }

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

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

   153         return 1;

   154     }

   156     dest->elemsize = src->elemsize;

   157     dest->size = src->size;

   159     if (dest->data) {

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

   161     }

   163     return 0;

   164 }

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

   167         cmp_func cmpfnc, void* data) {

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

   170         return 0;

   171     } else {

   172         if (array1->size == 0)

   173             return 1;

   175         size_t elemsize;

   176         if (cmpfnc == NULL) {

   177             cmpfnc = ucx_cmp_mem;

   178             elemsize = array1->elemsize;

   179             data = &elemsize;

   180         }

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

   183             int r = cmpfnc(

   184                     ucx_array_at(array1, i),

   185                     ucx_array_at(array2, i),

   186                     data);

   187             if (r != 0)

   188                 return 0;

   189         }

   190         return 1;

   191     }

   192 }

   194 void ucx_array_destroy(UcxArray *array) {

   195     if(array->data)

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

   197     array->data = NULL;

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

   199 }

   201 void ucx_array_free(UcxArray *array) {

   202     ucx_array_destroy(array);

   203     alfree(array->allocator, array);

   204 }

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

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

   208         return 1;

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

   211     if (data) {

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

   213     } else {

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

   215     }

   216     array->size += count;

   218     return 0;

   219 }

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

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

   223         return 1;

   225     if (array->size > 0) {

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

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

   228     }

   230     if (data) {

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

   232     } else {

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

   234     }

   235     array->size += count;

   237     return 0;

   238 }

   240 int ucx_array_set_from(UcxArray *array, size_t index,

   241         void *data, size_t count) {

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

   243         return 1;

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

   246         array->size = index+count;

   247     }

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

   250     if (data) {

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

   252     } else {

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

   254     }

   256     return 0;

   257 }

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

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

   262         return 1;

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

   266     if (array1->capacity < capacity) {

   267         if (ucx_array_reserve(array1, capacity)) {

   268             return 1;

   269         }

   270     }

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

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

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

   277     return 0;

   278 }

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

   281     char* memory = array->data;

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

   283     return loc;

   284 }

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

   287         cmp_func cmpfnc, void *data) {

   289     size_t elemsize;

   290     if (cmpfnc == NULL) {

   291         cmpfnc = ucx_cmp_mem;

   292         elemsize = array->elemsize;

   293         data = &elemsize;

   294     }

   296     if (array->size > 0) {

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

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

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

   300                 return i;

   301             }

   302         }

   303         return array->size;

   304     } else {

   305         return 0;

   306     }

   307 }

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

   310         cmp_func cmpfnc, void *data) {

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

   312 }

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

   315         cmp_func cmpfnc, void *data,

   316         size_t start, size_t mid, size_t end) {

   318     char* array = arrdata;

   320     size_t rightstart = mid + 1;

   322     if (cmpfnc(array + mid*elemsize,

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

   324         /* already sorted */

   325         return;

   326     }

   328     /* we need memory for one element */

   329     void *value = malloc(elemsize);

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

   332         if (cmpfnc(array + start*elemsize,

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

   334             start++;

   335         } else {

   336             /* save the value from the right */

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

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

   340             size_t shiftcount = rightstart-start;

   341             void *startptr = array + start*elemsize;

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

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

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

   346             memcpy(startptr, value, elemsize);

   348             start++;

   349             mid++;

   350             rightstart++;

   351         }

   352     }

   354     /* free the temporary memory */

   355     free(value);

   356 }

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

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

   360     if (l < r) {

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

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

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

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

   366     }

   367 }

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

   370         cmp_func cmpfnc, void *data) {

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

   373 }

   375 #ifdef USE_UCX_QSORT_R

   376 struct cmpfnc_swapargs_info {

   377     cmp_func func;

   378     void *data;

   379 };

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

   382     struct cmpfnc_swapargs_info* info = data;

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

   384 }

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

   387 		     cmp_func cmpfnc, void *data) {

   388     struct cmpfnc_swapargs_info info;

   389     info.func = cmpfnc;

   390     info.data = data;

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

   392 }

   393 #endif /* USE_UCX_QSORT_R */

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

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

   397             cmpfnc, data);

   398 }

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

   401     array->size--;

   402     if (index < array->size) {

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

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

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

   406     }

   407 }

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

   410     array->size--;

   411     if (index < array->size) {

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

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

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

   415     }

   416 }

   418 int ucx_array_shrink(UcxArray* array) {

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

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

   421     if (newptr) {

   422         array->data = newptr;

   423         array->capacity = array->size;

   424         return 0;

   425     } else {

   426         return 1;

   427     }

   428 }

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

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

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

   433                 capacity*array->elemsize);

   434         if (newptr) {

   435             array->data = newptr;

   436             array->capacity = capacity;

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

   438                 array->size = array->capacity;

   439             }

   440             return 0;

   441         } else {

   442             return 1;

   443         }

   444     } else {

   445         return ucx_array_reserve(array, capacity);

   446     }

   447 }

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

   450     if (array->capacity > capacity) {

   451         return 0;

   452     } else {

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

   454                 capacity*array->elemsize);

   455         if (newptr) {

   456             array->data = newptr;

   457             array->capacity = capacity;

   458             return 0;

   459         } else {

   460             return 1;

   461         }

   462     }

   463 }

   465 int ucx_array_grow(UcxArray* array, size_t count) {

   466     return ucx_array_reserve(array, array->size+count);

   467 }

Mercurial > hg > ucx / file revision

src/array.c@871a8ffe6c9d

src/array.c