ucx: src/array.c@7fd13b9f8f60

     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>

    39 #ifndef UCX_ARRAY_DISABLE_QSORT

    40 #ifdef __GLIBC__

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

    42 #define ucx_array_sort_impl qsort_r

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

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

    45 #define ucx_array_sort_impl ucx_qsort_r

    46 #define USE_UCX_QSORT_R

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

    48 #if __STDC_VERSION__ >= 201112L

    49 #define ucx_array_sort_impl qsort_s

    50 #endif

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

    52 #endif /* UCX_ARRAY_DISABLE_QSORT */

    54 #ifndef ucx_array_sort_impl

    55 #define ucx_array_sort_impl ucx_mergesort

    56 #endif

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

    59     size_t required_capacity = array->capacity;

    60     while (reqcap > required_capacity) {

    61         if (required_capacity * 2 < required_capacity)

    62             return 1;

    63         required_capacity <<= 1;

    64     }

    65     if (ucx_array_reserve(array, required_capacity)) {

    66         return 1;

    67     }

    68 }

    70 UcxArray ucx_array_new(size_t capacity, size_t elemsize) {

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

    72 }

    74 UcxArray ucx_array_new_a(size_t capacity, size_t elemsize,

    75         UcxAllocator* allocator) {

    76     UcxArray array;

    78     array.allocator = allocator;

    79     array.elemsize = elemsize;

    80     array.size = 0;

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

    83     if (array.data) {

    84         array.capacity = capacity;

    85     } else {

    86         array.capacity = 0;

    87     }

    89     return array;

    90 }

    92 UcxArray ucx_array_clone(UcxArray array) {

    93     UcxArray clone;

    95     clone.allocator = array.allocator;

    96     clone.elemsize = array.elemsize;

    97     clone.size = array.size;

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

   100     if (clone.data) {

   101         clone.capacity = array.capacity;

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

   103     } else {

   104         clone.capacity = clone.size = 0;

   105     }

   107     return clone;

   108 }

   110 int ucx_array_equals(UcxArray array1, UcxArray array2,

   111         cmp_func cmpfnc, void* data) {

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

   114         return 0;

   115     } else {

   116         if (array1.size == 0)

   117             return 1;

   119         if (cmpfnc == NULL) {

   120             cmpfnc = ucx_cmp_mem;

   121             data = &array1.elemsize;

   122         }

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

   125             int r = cmpfnc(

   126                     ucx_array_at(array1, i),

   127                     ucx_array_at(array2, i),

   128                     data);

   129             if (r != 0)

   130                 return 0;

   131         }

   132         return 1;

   133     }

   134 }

   136 void ucx_array_destroy(UcxArray *array) {

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

   138     array->data = NULL;

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

   140 }

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

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

   144         return 1;

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

   147     if (data) {

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

   149     } else {

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

   151     }

   152     array->size += count;

   154     return 0;

   155 }

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

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

   159         return 1;

   161     if (array->size > 0) {

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

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

   164     }

   166     if (data) {

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

   168     } else {

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

   170     }

   171     array->size += count;

   173     return 0;

   174 }

   176 int ucx_array_set_from(UcxArray *array, size_t index,

   177         void *data, size_t count) {

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

   179         return 1;

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

   182         array->size = index+count;

   183     }

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

   186     if (data) {

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

   188     } else {

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

   190     }

   192     return 0;

   193 }

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

   196     va_list ap;

   197     va_start(ap, array);

   198     int elem = va_arg(ap, int);

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

   200     va_end(ap);

   201     return ret;

   202 }

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

   205     va_list ap;

   206     va_start(ap, array);

   207     int elem = va_arg(ap, int);

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

   209     va_end(ap);

   210     return ret;

   211 }

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

   214     va_list ap;

   215     va_start(ap, index);

   216     int elem = va_arg(ap, int);

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

   218     va_end(ap);

   219     return ret;

   220 }

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

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

   225         return 1;

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

   229     if (array1->capacity < capacity) {

   230         if (ucx_array_reserve(array1, capacity)) {

   231             return 1;

   232         }

   233     }

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

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

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

   240     return 0;

   241 }

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

   244     char* memory = array.data;

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

   246     return loc;

   247 }

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

   251     if (cmpfnc == NULL) {

   252         cmpfnc = ucx_cmp_mem;

   253         data = &array.elemsize;

   254     }

   256     if (array.size > 0) {

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

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

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

   260                 return i;

   261             }

   262         }

   263         return array.size;

   264     } else {

   265         return 0;

   266     }

   267 }

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

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

   271 }

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

   274         cmp_func cmpfnc, void *data,

   275         size_t start, size_t mid, size_t end) {

   277     char* array = arrdata;

   279     size_t rightstart = mid + 1;

   281     if (cmpfnc(array + mid*elemsize,

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

   283         /* already sorted */

   284         return;

   285     }

   287     /* we need memory for one element */

   288     void *value = malloc(elemsize);

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

   291         if (cmpfnc(array + start*elemsize,

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

   293             start++;

   294         } else {

   295             /* save the value from the right */

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

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

   299             size_t shiftcount = rightstart-start;

   300             void *startptr = array + start*elemsize;

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

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

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

   305             memcpy(startptr, value, elemsize);

   307             start++;

   308             mid++;

   309             rightstart++;

   310         }

   311     }

   313     /* free the temporary memory */

   314     free(value);

   315 }

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

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

   319     if (l < r) {

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

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

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

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

   325     }

   326 }

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

   329         cmp_func cmpfnc, void *data) {

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

   332 }

   334 #ifdef USE_UCX_QSORT_R

   335 struct cmpfnc_swapargs_info {

   336     cmp_func func;

   337     void *data;

   338 };

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

   341     cmpfnc_swapargs_info* info = data;

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

   343 }

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

   346 		     cmp_func cmpfnc, void *data) {

   347     struct cmpfnc_swapargs_info info;

   348     info.func = cmpfnc;

   349     info.data = data;

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

   351 }

   352 #endif /* USE_UCX_QSORT_R */

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

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

   356 }

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

   359     array->size--;

   360     if (index < array->size) {

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

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

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

   364     }

   365 }

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

   368     array->size--;

   369     if (index < array->size) {

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

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

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

   373     }

   374 }

   376 int ucx_array_shrink(UcxArray* array) {

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

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

   379     if (newptr) {

   380         array->data = newptr;

   381         array->capacity = array->size;

   382         return 0;

   383     } else {

   384         return 1;

   385     }

   386 }

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

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

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

   391                 capacity*array->elemsize);

   392         if (newptr) {

   393             array->data = newptr;

   394             array->capacity = capacity;

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

   396                 array->size = array->capacity;

   397             }

   398             return 0;

   399         } else {

   400             return 1;

   401         }

   402     } else {

   403         return ucx_array_reserve(array, capacity);

   404     }

   405 }

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

   408     if (array->capacity > capacity) {

   409         return 0;

   410     } else {

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

   412                 capacity*array->elemsize);

   413         if (newptr) {

   414             array->data = newptr;

   415             array->capacity = capacity;

   416             return 0;

   417         } else {

   418             return 1;

   419         }

   420     }

   421 }

Mercurial > hg > ucx / file revision

src/array.c@7fd13b9f8f60

src/array.c