ucx: src/array.c@62660a4875c9

     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 */

    31 #include "ucx/array.h"

    32 #include "ucx/utils.h"

    34 #include <string.h>

    35 #include <stdlib.h>

    37 #ifndef UCX_ARRAY_DISABLE_QSORT

    38 #ifdef __GLIBC__

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

    40 #define ucx_array_sort_impl qsort_r

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

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

    43 #define ucx_array_sort_impl ucx_qsort_r

    44 #define USE_UCX_QSORT_R

    45 #endif /* __GLIBC__, __APLE__, __FreeBSD__ */

    46 #endif /* UCX_ARRAY_DISABLE_QSORT */

    48 #ifndef ucx_array_sort_impl

    49 #define ucx_array_sort_impl ucx_mergesort

    50 #endif

    52 UcxArray ucx_array_new(size_t capacity, size_t elemsize) {

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

    54 }

    56 UcxArray ucx_array_new_a(size_t capacity, size_t elemsize,

    57         UcxAllocator* allocator) {

    58     UcxArray array;

    60     array.allocator = allocator;

    61     array.elemsize = elemsize;

    62     array.size = 0;

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

    65     if (array.data) {

    66         array.capacity = capacity;

    67     } else {

    68         array.capacity = 0;

    69     }

    71     return array;

    72 }

    74 UcxArray ucx_array_clone(UcxArray array) {

    75     UcxArray clone;

    77     clone.allocator = array.allocator;

    78     clone.elemsize = array.elemsize;

    79     clone.size = array.size;

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

    82     if (clone.data) {

    83         clone.capacity = array.capacity;

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

    85     } else {

    86         clone.capacity = clone.size = 0;

    87     }

    89     return clone;

    90 }

    92 int ucx_array_equals(UcxArray array1, UcxArray array2,

    93         cmp_func cmpfnc, void* data) {

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

    96         return 0;

    97     } else {

    98         if (array1.size == 0)

    99             return 1;

   101         if (cmpfnc == NULL) {

   102             cmpfnc = ucx_cmp_mem;

   103             data = &array1.elemsize;

   104         }

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

   107             int r = cmpfnc(

   108                     ucx_array_at(array1, i),

   109                     ucx_array_at(array2, i),

   110                     data);

   111             if (r != 0)

   112                 return 0;

   113         }

   114         return 1;

   115     }

   116 }

   118 void ucx_array_free(UcxArray *array) {

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

   120     array->data = NULL;

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

   122 }

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

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

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

   127             return 1;

   128         }

   129     }

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

   132     if (data) {

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

   134     } else {

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

   136     }

   138     return 0;

   139 }

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

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

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

   144             return 1;

   145         }

   146     }

   148     array->size++;

   150     if (array->size > 1) {

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

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

   153     }

   155     if (data) {

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

   157     } else {

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

   159     }

   161     return 0;

   162 }

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

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

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

   167             return 1;

   168         }

   169         array->size = index+1;

   170     }

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

   173     if (data) {

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

   175     } else {

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

   177     }

   179     return 0;

   180 }

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

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

   185         return 1;

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

   189     if (array1->capacity < capacity) {

   190         if (ucx_array_reserve(array1, capacity)) {

   191             return 1;

   192         }

   193     }

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

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

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

   200     return 0;

   201 }

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

   204     char* memory = array.data;

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

   206     return loc;

   207 }

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

   211     if (cmpfnc == NULL) {

   212         cmpfnc = ucx_cmp_mem;

   213         data = &array.elemsize;

   214     }

   216     if (array.size > 0) {

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

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

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

   220                 return i;

   221             }

   222         }

   223         return array.size;

   224     } else {

   225         return 0;

   226     }

   227 }

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

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

   231 }

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

   234         cmp_func cmpfnc, void *data,

   235         size_t start, size_t mid, size_t end) {

   237     char* array = arrdata;

   239     size_t rightstart = mid + 1;

   241     if (cmpfnc(array + mid*elemsize,

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

   243         /* already sorted */

   244         return;

   245     }

   247     /* we need memory for one element */

   248     void *value = malloc(elemsize);

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

   251         if (cmpfnc(array + start*elemsize,

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

   253             start++;

   254         } else {

   255             /* save the value from the right */

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

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

   259             size_t shiftcount = rightstart-start;

   260             void *startptr = array + start*elemsize;

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

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

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

   265             memcpy(startptr, value, elemsize);

   267             start++;

   268             mid++;

   269             rightstart++;

   270         }

   271     }

   273     /* free the temporary memory */

   274     free(value);

   275 }

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

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

   279     if (l < r) {

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

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

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

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

   285     }

   286 }

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

   289         cmp_func cmpfnc, void *data) {

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

   292 }

   294 #ifdef USE_UCX_QSORT_R

   295 struct cmpfnc_swapargs_info {

   296     cmp_func func;

   297     void *data;

   298 };

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

   301     struct cmpfnc_swapargs_info* info = data;

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

   303 }

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

   306 		     cmp_func cmpfnc, void *data) {

   307     struct cmpfnc_swapargs_info info;

   308     info.func = cmpfnc;

   309     info.data = data;

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

   311 }

   312 #endif /* USE_UCX_QSORT_R */

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

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

   316 }

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

   319     array->size--;

   320     if (index < array->size) {

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

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

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

   324     }

   325 }

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

   328     array->size--;

   329     if (index < array->size) {

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

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

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

   333     }

   334 }

   336 int ucx_array_shrink(UcxArray* array) {

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

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

   339     if (newptr) {

   340         array->data = newptr;

   341         array->capacity = array->size;

   342         return 0;

   343     } else {

   344         return 1;

   345     }

   346 }

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

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

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

   351                 capacity*array->elemsize);

   352         if (newptr) {

   353             array->data = newptr;

   354             array->capacity = capacity;

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

   356                 array->size = array->capacity;

   357             }

   358             return 0;

   359         } else {

   360             return 1;

   361         }

   362     } else {

   363         return ucx_array_reserve(array, capacity);

   364     }

   365 }

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

   368     if (array->capacity > capacity) {

   369         return 0;

   370     } else {

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

   372                 capacity*array->elemsize);

   373         if (newptr) {

   374             array->data = newptr;

   375             array->capacity = capacity;

   376             return 0;

   377         } else {

   378             return 1;

   379         }

   380     }

   381 }

Mercurial > hg > ucx / file revision

src/array.c@62660a4875c9

src/array.c