Mercurial > hg > ucx / changeset

     1.1 --- a/src/array.c	Wed Aug 07 20:45:21 2019 +0200
     1.2 +++ b/src/array.c	Wed Aug 07 21:14:58 2019 +0200
     1.3 @@ -26,10 +26,30 @@
     1.4   * POSSIBILITY OF SUCH DAMAGE.
     1.5   */
     1.6  
     1.7 +#define _GNU_SOURCE /* we want to use qsort_r(), if available */
     1.8 +
     1.9  #include "ucx/array.h"
    1.10  #include "ucx/utils.h"
    1.11  
    1.12  #include <string.h>
    1.13 +#include <stdlib.h>
    1.14 +
    1.15 +#ifndef UCX_ARRAY_DISABLE_QSORT
    1.16 +#if defined(__GLIBC__)
    1.17 +#if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)
    1.18 +#define ucx_array_sort_impl qsort_r
    1.19 +#endif /* glibc version >= 2.8 */
    1.20 +#endif /* __GLIBC__ */
    1.21 +
    1.22 +#if defined(__APPLE__) || defined(__FreeBSD__)
    1.23 +#define ucx_array_sort_impl ucx_qsort_r
    1.24 +#define USE_UCX_QSORT_R
    1.25 +#endif /* __APLE__ or __FreeBSD__ */
    1.26 +#endif /* UCX_ARRAY_DISABLE_QSORT */
    1.27 +
    1.28 +#ifndef ucx_array_sort_impl
    1.29 +#define ucx_array_sort_impl ucx_mergesort
    1.30 +#endif
    1.31  
    1.32  UcxArray ucx_array_new(size_t capacity, size_t elemsize) {
    1.33      return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
    1.34 @@ -212,36 +232,39 @@
    1.35      return ucx_array_find(array, elem, cmpfnc, data) != array.size;
    1.36  }
    1.37  
    1.38 -static void ucx_array_merge(UcxArray *array, cmp_func cmpfnc, void *data,
    1.39 +static void ucx_mergesort_merge(void *arrdata,size_t elemsize,
    1.40 +        cmp_func cmpfnc, void *data,
    1.41          size_t start, size_t mid, size_t end) { 
    1.42      
    1.43 +    char* array = arrdata;
    1.44 +    
    1.45      size_t rightstart = mid + 1; 
    1.46    
    1.47 -    if (cmpfnc(ucx_array_at(*array, mid),
    1.48 -            ucx_array_at(*array, rightstart), data) <= 0) {
    1.49 +    if (cmpfnc(array + mid*elemsize,
    1.50 +            array + rightstart*elemsize, data) <= 0) {
    1.51          /* already sorted */
    1.52          return;
    1.53      }
    1.54    
    1.55      /* we need memory for one element */
    1.56 -    void *value = malloc(array->elemsize);
    1.57 +    void *value = malloc(elemsize);
    1.58      
    1.59      while (start <= mid && rightstart <= end) { 
    1.60 -        if (cmpfnc(ucx_array_at(*array, start),
    1.61 -                ucx_array_at(*array, rightstart), data) <= 0) { 
    1.62 +        if (cmpfnc(array + start*elemsize,
    1.63 +                array + rightstart*elemsize, data) <= 0) { 
    1.64              start++; 
    1.65          } else {
    1.66              /* save the value from the right */
    1.67 -            memcpy(value, ucx_array_at(*array, rightstart), array->elemsize);
    1.68 +            memcpy(value, array + rightstart*elemsize, elemsize);
    1.69                          
    1.70              /* shift all left elements one element to the right */
    1.71              size_t shiftcount = rightstart-start;
    1.72 -            void *startptr = ucx_array_at(*array, start);
    1.73 -            void *dest = ucx_array_at(*array, start+1);
    1.74 -            memmove(dest, startptr, shiftcount*array->elemsize);
    1.75 +            void *startptr = array + start*elemsize;
    1.76 +            void *dest = array + (start+1)*elemsize;
    1.77 +            memmove(dest, startptr, shiftcount*elemsize);
    1.78              
    1.79              /* bring the first value from the right to the left */
    1.80 -            memcpy(startptr, value, array->elemsize);
    1.81 +            memcpy(startptr, value, elemsize);
    1.82    
    1.83              start++; 
    1.84              mid++; 
    1.85 @@ -253,19 +276,45 @@
    1.86      free(value);
    1.87  } 
    1.88    
    1.89 -static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data,
    1.90 -        size_t l, size_t r) { 
    1.91 +static void ucx_mergesort_impl(void *arrdata, size_t elemsize,
    1.92 +        cmp_func cmpfnc, void *data, size_t l, size_t r) { 
    1.93      if (l < r) {
    1.94          size_t m = l + (r - l) / 2; 
    1.95    
    1.96 -        ucx_array_mergesort(array, cmpfnc, data, l, m); 
    1.97 -        ucx_array_mergesort(array, cmpfnc, data, m + 1, r); 
    1.98 -        ucx_array_merge(array, cmpfnc, data, l, m, r);
    1.99 +        ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m); 
   1.100 +        ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r); 
   1.101 +        ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);
   1.102      } 
   1.103  }
   1.104  
   1.105 -void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {   
   1.106 -    ucx_array_mergesort(&array, cmpfnc, data, 0, array.size-1);
   1.107 +static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,
   1.108 +        cmp_func cmpfnc, void *data) {
   1.109 +    
   1.110 +    ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);
   1.111 +}
   1.112 +
   1.113 +#ifdef USE_UCX_QSORT_R
   1.114 +struct cmpfnc_swapargs_info {
   1.115 +    cmp_func func;
   1.116 +    void *data;
   1.117 +};
   1.118 +
   1.119 +static int cmp_func_swap_args(void *data, const void *x, const void *y) {
   1.120 +    cmpfnc_swapargs_info* info = data;
   1.121 +    return info->func(x, y, info->data);
   1.122 +}
   1.123 +
   1.124 +static void ucx_qsort_r(void *array, size_t count, size_t elemsize,
   1.125 +		     cmp_func cmpfnc, void *data) {
   1.126 +    struct cmpfnc_swapargs_info info;
   1.127 +    info.func = cmpfnc;
   1.128 +    info.data = data;
   1.129 +    qsort_r(array, count, elemsize, &info, cmp_func_swap_args);
   1.130 +}
   1.131 +#endif /* USE_UCX_QSORT_R */
   1.132 +
   1.133 +void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {
   1.134 +    ucx_array_sort_impl(array.data, array.size, array.elemsize, cmpfnc, data);
   1.135  }
   1.136  
   1.137  void ucx_array_remove(UcxArray *array, size_t index) {

     2.1 --- a/src/ucx/array.h	Wed Aug 07 20:45:21 2019 +0200
     2.2 +++ b/src/ucx/array.h	Wed Aug 07 21:14:58 2019 +0200
     2.3 @@ -234,8 +234,12 @@
     2.4  /**
     2.5   * Sorts a UcxArray with the best available sort algorithm.
     2.6   * 
     2.7 - * A merge sort algorithm is used, which is guaranteed to use no more additional
     2.8 - * memory than for exactly one element.
     2.9 + * The qsort_r() function is used, if available (glibc, FreeBSD or MacOS).
    2.10 + * The order of arguments is automatically adjusted for the FreeBSD and MacOS
    2.11 + * version of qsort_r().
    2.12 + * 
    2.13 + * If qsort_r() is not available, a merge sort algorithm is used, which is
    2.14 + * guaranteed to use no more additional memory than for exactly one element.
    2.15   * 
    2.16   * @param array the array to sort
    2.17   * @param cmpfnc the function that shall be used to compare the element data