ucx: src/array.c@6089eb30a51a

     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 #if defined(__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 #endif /* __GLIBC__ */

    44 #if defined(__APPLE__) || defined(__FreeBSD__)

    45 #define ucx_array_sort_impl ucx_qsort_r

    46 #define USE_UCX_QSORT_R

    47 #endif /* __APLE__ or __FreeBSD__ */

    48 #endif /* UCX_ARRAY_DISABLE_QSORT */

    50 #ifndef ucx_array_sort_impl

    51 #define ucx_array_sort_impl ucx_mergesort

    52 #endif

    54 UcxArray ucx_array_new(size_t capacity, size_t elemsize) {

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

    56 }

    58 UcxArray ucx_array_new_a(size_t capacity, size_t elemsize,

    59         UcxAllocator* allocator) {

    60     UcxArray array;

    62     array.allocator = allocator;

    63     array.elemsize = elemsize;

    64     array.size = 0;

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

    67     if (array.data) {

    68         array.capacity = capacity;

    69     } else {

    70         array.capacity = 0;

    71     }

    73     return array;

    74 }

    76 UcxArray ucx_array_clone(UcxArray array) {

    77     UcxArray clone;

    79     clone.allocator = array.allocator;

    80     clone.elemsize = array.elemsize;

    81     clone.size = array.size;

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

    84     if (clone.data) {

    85         clone.capacity = array.capacity;

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

    87     } else {

    88         clone.capacity = clone.size = 0;

    89     }

    91     return clone;

    92 }

    94 int ucx_array_equals(UcxArray array1, UcxArray array2,

    95         cmp_func cmpfnc, void* data) {

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

    98         return 0;

    99     } else {

   100         if (array1.size == 0)

   101             return 1;

   103         if (cmpfnc == NULL) {

   104             cmpfnc = ucx_cmp_mem;

   105             data = &array1.elemsize;

   106         }

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

   109             int r = cmpfnc(

   110                     ucx_array_at(array1, i),

   111                     ucx_array_at(array2, i),

   112                     data);

   113             if (r != 0)

   114                 return 0;

   115         }

   116         return 1;

   117     }

   118 }

   120 void ucx_array_free(UcxArray *array) {

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

   122     array->data = NULL;

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

   124 }

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

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

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

   129             return 1;

   130         }

   131     }

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

   134     if (data) {

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

   136     } else {

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

   138     }

   140     return 0;

   141 }

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

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

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

   146             return 1;

   147         }

   148     }

   150     array->size++;

   152     if (array->size > 1) {

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

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

   155     }

   157     if (data) {

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

   159     } else {

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

   161     }

   163     return 0;

   164 }

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

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

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

   169             return 1;

   170         }

   171         array->size = index+1;

   172     }

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

   175     if (data) {

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

   177     } else {

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

   179     }

   181     return 0;

   182 }

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

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

   187         return 1;

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

   191     if (array1->capacity < capacity) {

   192         if (ucx_array_reserve(array1, capacity)) {

   193             return 1;

   194         }

   195     }

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

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

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

   202     return 0;

   203 }

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

   206     char* memory = array.data;

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

   208     return loc;

   209 }

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

   213     if (cmpfnc == NULL) {

   214         cmpfnc = ucx_cmp_mem;

   215         data = &array.elemsize;

   216     }

   218     if (array.size > 0) {

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

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

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

   222                 return i;

   223             }

   224         }

   225         return array.size;

   226     } else {

   227         return 0;

   228     }

   229 }

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

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

   233 }

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

   236         cmp_func cmpfnc, void *data,

   237         size_t start, size_t mid, size_t end) {

   239     char* array = arrdata;

   241     size_t rightstart = mid + 1;

   243     if (cmpfnc(array + mid*elemsize,

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

   245         /* already sorted */

   246         return;

   247     }

   249     /* we need memory for one element */

   250     void *value = malloc(elemsize);

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

   253         if (cmpfnc(array + start*elemsize,

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

   255             start++;

   256         } else {

   257             /* save the value from the right */

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

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

   261             size_t shiftcount = rightstart-start;

   262             void *startptr = array + start*elemsize;

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

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

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

   267             memcpy(startptr, value, elemsize);

   269             start++;

   270             mid++;

   271             rightstart++;

   272         }

   273     }

   275     /* free the temporary memory */

   276     free(value);

   277 }

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

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

   281     if (l < r) {

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

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

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

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

   287     }

   288 }

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

   291         cmp_func cmpfnc, void *data) {

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

   294 }

   296 #ifdef USE_UCX_QSORT_R

   297 struct cmpfnc_swapargs_info {

   298     cmp_func func;

   299     void *data;

   300 };

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

   303     cmpfnc_swapargs_info* info = data;

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

   305 }

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

   308 		     cmp_func cmpfnc, void *data) {

   309     struct cmpfnc_swapargs_info info;

   310     info.func = cmpfnc;

   311     info.data = data;

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

   313 }

   314 #endif /* USE_UCX_QSORT_R */

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

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

   318 }

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

   321     array->size--;

   322     if (index < array->size) {

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

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

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

   326     }

   327 }

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

   330     array->size--;

   331     if (index < array->size) {

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

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

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

   335     }

   336 }

   338 int ucx_array_shrink(UcxArray* array) {

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

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

   341     if (newptr) {

   342         array->data = newptr;

   343         array->capacity = array->size;

   344         return 0;

   345     } else {

   346         return 1;

   347     }

   348 }

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

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

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

   353                 capacity*array->elemsize);

   354         if (newptr) {

   355             array->data = newptr;

   356             array->capacity = capacity;

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

   358                 array->size = array->capacity;

   359             }

   360             return 0;

   361         } else {

   362             return 1;

   363         }

   364     } else {

   365         return ucx_array_reserve(array, capacity);

   366     }

   367 }

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

   370     if (array->capacity > capacity) {

   371         return 0;

   372     } else {

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

   374                 capacity*array->elemsize);

   375         if (newptr) {

   376             array->data = newptr;

   377             array->capacity = capacity;

   378             return 0;

   379         } else {

   380             return 1;

   381         }

   382     }

   383 }

Mercurial > hg > ucx / file revision

src/array.c@6089eb30a51a

src/array.c