Mercurial > hg > ucx / changeset

--- a/src/array.c	Wed Aug 07 20:45:21 2019 +0200
+++ b/src/array.c	Wed Aug 07 21:14:58 2019 +0200
@@ -26,10 +26,30 @@
  * POSSIBILITY OF SUCH DAMAGE.
  */
 
+#define _GNU_SOURCE /* we want to use qsort_r(), if available */
+
 #include "ucx/array.h"
 #include "ucx/utils.h"
 
 #include <string.h>
+#include <stdlib.h>
+
+#ifndef UCX_ARRAY_DISABLE_QSORT
+#if defined(__GLIBC__)
+#if __GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)
+#define ucx_array_sort_impl qsort_r
+#endif /* glibc version >= 2.8 */
+#endif /* __GLIBC__ */
+
+#if defined(__APPLE__) || defined(__FreeBSD__)
+#define ucx_array_sort_impl ucx_qsort_r
+#define USE_UCX_QSORT_R
+#endif /* __APLE__ or __FreeBSD__ */
+#endif /* UCX_ARRAY_DISABLE_QSORT */
+
+#ifndef ucx_array_sort_impl
+#define ucx_array_sort_impl ucx_mergesort
+#endif
 
 UcxArray ucx_array_new(size_t capacity, size_t elemsize) {
     return ucx_array_new_a(capacity, elemsize, ucx_default_allocator());
@@ -212,36 +232,39 @@
     return ucx_array_find(array, elem, cmpfnc, data) != array.size;
 }
 
-static void ucx_array_merge(UcxArray *array, cmp_func cmpfnc, void *data,
+static void ucx_mergesort_merge(void *arrdata,size_t elemsize,
+        cmp_func cmpfnc, void *data,
         size_t start, size_t mid, size_t end) { 
     
+    char* array = arrdata;
+    
     size_t rightstart = mid + 1; 
   
-    if (cmpfnc(ucx_array_at(*array, mid),
-            ucx_array_at(*array, rightstart), data) <= 0) {
+    if (cmpfnc(array + mid*elemsize,
+            array + rightstart*elemsize, data) <= 0) {
         /* already sorted */
         return;
     }
   
     /* we need memory for one element */
-    void *value = malloc(array->elemsize);
+    void *value = malloc(elemsize);
     
     while (start <= mid && rightstart <= end) { 
-        if (cmpfnc(ucx_array_at(*array, start),
-                ucx_array_at(*array, rightstart), data) <= 0) { 
+        if (cmpfnc(array + start*elemsize,
+                array + rightstart*elemsize, data) <= 0) { 
             start++; 
         } else {
             /* save the value from the right */
-            memcpy(value, ucx_array_at(*array, rightstart), array->elemsize);
+            memcpy(value, array + rightstart*elemsize, elemsize);
                         
             /* shift all left elements one element to the right */
             size_t shiftcount = rightstart-start;
-            void *startptr = ucx_array_at(*array, start);
-            void *dest = ucx_array_at(*array, start+1);
-            memmove(dest, startptr, shiftcount*array->elemsize);
+            void *startptr = array + start*elemsize;
+            void *dest = array + (start+1)*elemsize;
+            memmove(dest, startptr, shiftcount*elemsize);
             
             /* bring the first value from the right to the left */
-            memcpy(startptr, value, array->elemsize);
+            memcpy(startptr, value, elemsize);
   
             start++; 
             mid++; 
@@ -253,19 +276,45 @@
     free(value);
 } 
   
-static void ucx_array_mergesort(UcxArray *array, cmp_func cmpfnc, void *data,
-        size_t l, size_t r) { 
+static void ucx_mergesort_impl(void *arrdata, size_t elemsize,
+        cmp_func cmpfnc, void *data, size_t l, size_t r) { 
     if (l < r) {
         size_t m = l + (r - l) / 2; 
   
-        ucx_array_mergesort(array, cmpfnc, data, l, m); 
-        ucx_array_mergesort(array, cmpfnc, data, m + 1, r); 
-        ucx_array_merge(array, cmpfnc, data, l, m, r);
+        ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, l, m); 
+        ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, m + 1, r); 
+        ucx_mergesort_merge(arrdata, elemsize, cmpfnc, data, l, m, r);
     } 
 }
 
-void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {   
-    ucx_array_mergesort(&array, cmpfnc, data, 0, array.size-1);
+static void ucx_mergesort(void *arrdata, size_t count, size_t elemsize,
+        cmp_func cmpfnc, void *data) {
+    
+    ucx_mergesort_impl(arrdata, elemsize, cmpfnc, data, 0, count-1);
+}
+
+#ifdef USE_UCX_QSORT_R
+struct cmpfnc_swapargs_info {
+    cmp_func func;
+    void *data;
+};
+
+static int cmp_func_swap_args(void *data, const void *x, const void *y) {
+    cmpfnc_swapargs_info* info = data;
+    return info->func(x, y, info->data);
+}
+
+static void ucx_qsort_r(void *array, size_t count, size_t elemsize,
+		     cmp_func cmpfnc, void *data) {
+    struct cmpfnc_swapargs_info info;
+    info.func = cmpfnc;
+    info.data = data;
+    qsort_r(array, count, elemsize, &info, cmp_func_swap_args);
+}
+#endif /* USE_UCX_QSORT_R */
+
+void ucx_array_sort(UcxArray array, cmp_func cmpfnc, void *data) {
+    ucx_array_sort_impl(array.data, array.size, array.elemsize, cmpfnc, data);
 }
 
 void ucx_array_remove(UcxArray *array, size_t index) {

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