ucx: src/array.c@135ce35d5108

     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 UcxArray ucx_array_new(size_t capacity, size_t elemsize) {

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

    60 }

    62 UcxArray ucx_array_new_a(size_t capacity, size_t elemsize,

    63         UcxAllocator* allocator) {

    64     UcxArray array;

    66     array.allocator = allocator;

    67     array.elemsize = elemsize;

    68     array.size = 0;

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

    71     if (array.data) {

    72         array.capacity = capacity;

    73     } else {

    74         array.capacity = 0;

    75     }

    77     return array;

    78 }

    80 UcxArray ucx_array_clone(UcxArray array) {

    81     UcxArray clone;

    83     clone.allocator = array.allocator;

    84     clone.elemsize = array.elemsize;

    85     clone.size = array.size;

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

    88     if (clone.data) {

    89         clone.capacity = array.capacity;

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

    91     } else {

    92         clone.capacity = clone.size = 0;

    93     }

    95     return clone;

    96 }

    98 int ucx_array_equals(UcxArray array1, UcxArray array2,

    99         cmp_func cmpfnc, void* data) {

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

   102         return 0;

   103     } else {

   104         if (array1.size == 0)

   105             return 1;

   107         if (cmpfnc == NULL) {

   108             cmpfnc = ucx_cmp_mem;

   109             data = &array1.elemsize;

   110         }

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

   113             int r = cmpfnc(

   114                     ucx_array_at(array1, i),

   115                     ucx_array_at(array2, i),

   116                     data);

   117             if (r != 0)

   118                 return 0;

   119         }

   120         return 1;

   121     }

   122 }

   124 void ucx_array_destroy(UcxArray *array) {

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

   126     array->data = NULL;

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

   128 }

   130 int ucx_array_append(UcxArray *array, void *data) {

   131     if (array->size == array->capacity) {

   132         if (ucx_array_reserve(array, array->capacity*2)) {

   133             return 1;

   134         }

   135     }

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

   138     if (data) {

   139         memcpy(dest, data, array->elemsize);

   140     } else {

   141         memset(dest, 0, array->elemsize);

   142     }

   144     return 0;

   145 }

   147 int ucx_array_prepend(UcxArray *array, void *data) {

   148     if (array->size == array->capacity) {

   149         if (ucx_array_reserve(array, array->capacity*2)) {

   150             return 1;

   151         }

   152     }

   154     array->size++;

   156     if (array->size > 1) {

   157         void *dest = ucx_array_at(*array,1);

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

   159     }

   161     if (data) {

   162         memcpy(array->data, data, array->elemsize);

   163     } else {

   164         memset(array->data, 0, array->elemsize);

   165     }

   167     return 0;

   168 }

   170 int ucx_array_set(UcxArray *array, size_t index, void *data) {

   171     if (index >= array->size) {

   172         if (ucx_array_reserve(array, index+1)) {

   173             return 1;

   174         }

   175         array->size = index+1;

   176     }

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

   179     if (data) {

   180         memcpy(dest, data, array->elemsize);

   181     } else {

   182         memset(dest, 0, array->elemsize);

   183     }

   185     return 0;

   186 }

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

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

   191         return 1;

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

   195     if (array1->capacity < capacity) {

   196         if (ucx_array_reserve(array1, capacity)) {

   197             return 1;

   198         }

   199     }

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

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

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

   206     return 0;

   207 }

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

   210     char* memory = array.data;

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

   212     return loc;

   213 }

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

   217     if (cmpfnc == NULL) {

   218         cmpfnc = ucx_cmp_mem;

   219         data = &array.elemsize;

   220     }

   222     if (array.size > 0) {

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

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

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

   226                 return i;

   227             }

   228         }

   229         return array.size;

   230     } else {

   231         return 0;

   232     }

   233 }

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

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

   237 }

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

   240         cmp_func cmpfnc, void *data,

   241         size_t start, size_t mid, size_t end) {

   243     char* array = arrdata;

   245     size_t rightstart = mid + 1;

   247     if (cmpfnc(array + mid*elemsize,

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

   249         /* already sorted */

   250         return;

   251     }

   253     /* we need memory for one element */

   254     void *value = malloc(elemsize);

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

   257         if (cmpfnc(array + start*elemsize,

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

   259             start++;

   260         } else {

   261             /* save the value from the right */

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

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

   265             size_t shiftcount = rightstart-start;

   266             void *startptr = array + start*elemsize;

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

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

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

   271             memcpy(startptr, value, elemsize);

   273             start++;

   274             mid++;

   275             rightstart++;

   276         }

   277     }

   279     /* free the temporary memory */

   280     free(value);

   281 }

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

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

   285     if (l < r) {

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

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

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

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

   291     }

   292 }

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

   295         cmp_func cmpfnc, void *data) {

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

   298 }

   300 #ifdef USE_UCX_QSORT_R

   301 struct cmpfnc_swapargs_info {

   302     cmp_func func;

   303     void *data;

   304 };

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

   307     cmpfnc_swapargs_info* info = data;

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

   309 }

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

   312 		     cmp_func cmpfnc, void *data) {

   313     struct cmpfnc_swapargs_info info;

   314     info.func = cmpfnc;

   315     info.data = data;

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

   317 }

   318 #endif /* USE_UCX_QSORT_R */

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

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

   322 }

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

   325     array->size--;

   326     if (index < array->size) {

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

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

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

   330     }

   331 }

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

   334     array->size--;

   335     if (index < array->size) {

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

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

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

   339     }

   340 }

   342 int ucx_array_shrink(UcxArray* array) {

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

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

   345     if (newptr) {

   346         array->data = newptr;

   347         array->capacity = array->size;

   348         return 0;

   349     } else {

   350         return 1;

   351     }

   352 }

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

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

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

   357                 capacity*array->elemsize);

   358         if (newptr) {

   359             array->data = newptr;

   360             array->capacity = capacity;

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

   362                 array->size = array->capacity;

   363             }

   364             return 0;

   365         } else {

   366             return 1;

   367         }

   368     } else {

   369         return ucx_array_reserve(array, capacity);

   370     }

   371 }

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

   374     if (array->capacity > capacity) {

   375         return 0;

   376     } else {

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

   378                 capacity*array->elemsize);

   379         if (newptr) {

   380             array->data = newptr;

   381             array->capacity = capacity;

   382             return 0;

   383         } else {

   384             return 1;

   385         }

   386     }

   387 }

Mercurial > hg > ucx / file revision

src/array.c@135ce35d5108

src/array.c