tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

qsort_r



(Cc: tech-kern because of kheapsort())

My irritation with not being able to pass a data pointer through
qsort() boiled over just now. Apparently Linux and/or GNU has a
qsort_r() that supports this; so, following is a patch that gives us
a compatible qsort_r() plus mergesort_r(), and heapsort_r().

I have done it by having the original, non-_r functions provide a
thunk for the comparison function, as this is least invasive. If we
think this is too expensive, an alternative is generating a union of
function pointers and making tests at the call sites; another option
is to duplicate the code (hopefully with cpp rather than C&P) but that
seems like a bad plan. Note that the thunks use an extra struct to
hold the function pointer; this is to satisfy C standards pedantry
about void pointers vs. function pointers, and if we decide not to
care it could be simplified.

This patch was supposed to have all the necessary support widgetry,
like namespace.h changes, but there's at least one more thing not in
it: MLINKS for the new functions and corresponding setlist
changes. If I've forgotten anything else, let me know.

heapsort() is used in one place in the kernel as kheapsort(), which
takes an extra argument so that the heapsort code itself doesn't have
to know how to malloc in the kernel. I have done the following:
   - add kheapsort_r()
   - change the signature of plain kheapsort() to move the extra
     argument to a place it is less likely to cause confusion with the
     userdata argument;
   - update the caller for the signature change;
but I have not changed the caller to call kheapsort_r instead. Based
on the code, this should probably be done later as like many sort
calls it's using a global for context. At this point the plain
kheapsort can be removed.

   ------

Index: include/stdlib.h
===================================================================
RCS file: /cvsroot/src/include/stdlib.h,v
retrieving revision 1.106
diff -u -p -r1.106 stdlib.h
--- include/stdlib.h    26 Apr 2013 18:07:43 -0000      1.106
+++ include/stdlib.h    8 Dec 2013 22:13:22 -0000
@@ -299,9 +299,16 @@ int         getenv_r(const char *, char *, size
 
 void    cfree(void *);
 
-int     heapsort(void *, size_t, size_t, int (*)(const void *, const void *));
+int     heapsort(void *, size_t, size_t,
+           int (*)(const void *, const void *));
+int     heapsort_r(void *, size_t, size_t,
+           int (*)(const void *, const void *, void *), void *);
 int     mergesort(void *, size_t, size_t,
            int (*)(const void *, const void *));
+int     mergesort_r(void *, size_t, size_t,
+           int (*)(const void *, const void *, void *), void *);
+void    qsort_r(void *, size_t, size_t,
+           int (*)(const void *, const void *, void *), void *);
 int     radixsort(const unsigned char **, int, const unsigned char *,
            unsigned);
 int     sradixsort(const unsigned char **, int, const unsigned char *,
Index: common/lib/libc/stdlib/heapsort.c
===================================================================
RCS file: /cvsroot/src/common/lib/libc/stdlib/heapsort.c,v
retrieving revision 1.3
diff -u -p -r1.3 heapsort.c
--- common/lib/libc/stdlib/heapsort.c   17 Nov 2008 10:21:30 -0000      1.3
+++ common/lib/libc/stdlib/heapsort.c   8 Dec 2013 22:13:23 -0000
@@ -69,6 +69,7 @@ __RCSID("$NetBSD: heapsort.c,v 1.3 2008/
 
 #ifdef __weak_alias
 __weak_alias(heapsort,_heapsort)
+__weak_alias(heapsort_r,_heapsort_r)
 #endif
 #endif /* _KERNEL || _STANDALONE */
 
@@ -109,12 +110,12 @@ __weak_alias(heapsort,_heapsort)
        for (par_i = initval; (child_i = par_i * 2) <= nmemb; \
            par_i = child_i) { \
                child = base + child_i * size; \
-               if (child_i < nmemb && compar(child, child + size) < 0) { \
+               if (child_i < nmemb && compar(child, child + size, data) < 0) {\
                        child += size; \
                        ++child_i; \
                } \
                par = base + par_i * size; \
-               if (compar(child, par) <= 0) \
+               if (compar(child, par, data) <= 0) \
                        break; \
                SWAP(par, child, count, size, tmp); \
        } \
@@ -140,7 +141,7 @@ __weak_alias(heapsort,_heapsort)
 #define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) 
{ \
        for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \
                child = base + child_i * size; \
-               if (child_i < nmemb && compar(child, child + size) < 0) { \
+               if (child_i < nmemb && compar(child, child + size, data) < 0) {\
                        child += size; \
                        ++child_i; \
                } \
@@ -152,7 +153,7 @@ __weak_alias(heapsort,_heapsort)
                par_i = child_i / 2; \
                child = base + child_i * size; \
                par = base + par_i * size; \
-               if (child_i == 1 || compar(k, par) < 0) { \
+               if (child_i == 1 || compar(k, par, data) < 0) { \
                        COPY(child, k, count, size, tmp1, tmp2); \
                        break; \
                } \
@@ -169,12 +170,12 @@ __weak_alias(heapsort,_heapsort)
  */
 #if defined(_KERNEL) || defined(_STANDALONE)
 int
-kheapsort(void *vbase, size_t nmemb, size_t size,
-    int (*compar)(const void *, const void *), void *k)
+kheapsort_r(void *vbase, size_t nmemb, size_t size, void *k,
+    int (*compar)(const void *, const void *, void *), void *data)
 #else
 int
-heapsort(void *vbase, size_t nmemb, size_t size,
-    int (*compar)(const void *, const void *))
+heapsort_r(void *vbase, size_t nmemb, size_t size,
+    int (*compar)(const void *, const void *, void *), void *data)
 #endif
 {
        size_t cnt, i, j, l;
@@ -227,3 +228,40 @@ heapsort(void *vbase, size_t nmemb, size
 #endif
        return (0);
 }
+
+////////////////////////////////////////////////////////////
+// original heapsort()
+
+struct __heapsort {
+       int (*cmp)(const void *, const void *);
+};
+
+static int
+__heapsort_cmp(const void *a, const void *b, void *data)
+{
+       struct __heapsort *hs = data;
+
+       return hs->cmp(a, b);
+}
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+int
+kheapsort(void *vbase, size_t nmemb, size_t size, void *k,
+    int (*compar)(const void *, const void *))
+{
+       struct __heapsort hs;
+
+       hs.cmp = compar;
+       return kheapsort_r(vbase, nmemb, size, k, __heapsort_cmp, &hs);
+}
+#else
+int
+heapsort(void *vbase, size_t nmemb, size_t size,
+    int (*compar)(const void *, const void *))
+{
+       struct __heapsort hs;
+
+       hs.cmp = compar;
+       return heapsort_r(vbase, nmemb, size, __heapsort_cmp, &hs);
+}
+#endif
Index: sys/kern/kern_ksyms.c
===================================================================
RCS file: /cvsroot/src/sys/kern/kern_ksyms.c,v
retrieving revision 1.70
diff -u -p -r1.70 kern_ksyms.c
--- sys/kern/kern_ksyms.c       7 Apr 2013 00:49:45 -0000       1.70
+++ sys/kern/kern_ksyms.c       8 Dec 2013 22:13:23 -0000
@@ -385,7 +385,7 @@ addsymtab(const char *name, void *symsta
        tab->sd_symsize = n * sizeof(Elf_Sym);
        tab->sd_nglob = nglob;
        addsymtab_strstart = str;
-       if (kheapsort(nsym, n, sizeof(Elf_Sym), addsymtab_compar, &ts) != 0)
+       if (kheapsort(nsym, n, sizeof(Elf_Sym), &ts, addsymtab_compar) != 0)
                panic("addsymtab");
 
 #ifdef KDTRACE_HOOKS
Index: lib/libc/include/namespace.h
===================================================================
RCS file: /cvsroot/src/lib/libc/include/namespace.h,v
retrieving revision 1.169
diff -u -p -r1.169 namespace.h
--- lib/libc/include/namespace.h        28 Aug 2013 17:47:07 -0000      1.169
+++ lib/libc/include/namespace.h        8 Dec 2013 22:13:31 -0000
@@ -387,6 +387,7 @@
 #define gmtime_r               _gmtime_r
 #define group_from_gid         _group_from_gid
 #define heapsort               _heapsort
+#define heapsort_r             _heapsort_r
 #define herror                 _herror
 #define hes_error              _hes_error
 #define hes_free               _hes_free
@@ -467,6 +468,7 @@
 #define lseek                  _lseek
 #define membar_producer                _membar_producer
 #define mergesort              _mergesort
+#define mergesort_r            _mergesort_r
 #define mi_vector_hash         _mi_vector_hash
 #define mkstemp                        _mkstemp
 #define mktime_z               _mktime_z
@@ -527,6 +529,7 @@
 #define pwrite                 _pwrite
 #define qabs                   _qabs
 #define qdiv                   _qdiv
+#define qsort_r                        _qsort_r
 #define radixsort              _radixsort
 #define random                 _random
 #define randomid               _randomid
Index: lib/libc/stdlib/merge.c
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/merge.c,v
retrieving revision 1.14
diff -u -p -r1.14 merge.c
--- lib/libc/stdlib/merge.c     13 Mar 2012 21:13:48 -0000      1.14
+++ lib/libc/stdlib/merge.c     8 Dec 2013 22:13:32 -0000
@@ -65,12 +65,13 @@ __RCSID("$NetBSD: merge.c,v 1.14 2012/03
 
 #ifdef __weak_alias
 __weak_alias(mergesort,_mergesort)
+__weak_alias(mergesort_r,_mergesort_r)
 #endif
 
 static void setup(u_char *, u_char *, size_t, size_t,
-    int (*)(const void *, const void *));
+    int (*)(const void *, const void *, void *), void *);
 static void insertionsort(u_char *, size_t, size_t,
-    int (*)(const void *, const void *));
+    int (*)(const void *, const void *, void *), void *);
 
 #define ISIZE sizeof(int)
 #define PSIZE sizeof(u_char *)
@@ -108,8 +109,8 @@ static void insertionsort(u_char *, size
  * Arguments are as for qsort.
  */
 int
-mergesort(void *base, size_t nmemb, size_t size,
-    int (*cmp)(const void *, const void *))
+mergesort_r(void *base, size_t nmemb, size_t size,
+    int (*cmp)(const void *, const void *, void *), void *data)
 {
        size_t i;
        int sense;
@@ -137,7 +138,7 @@ mergesort(void *base, size_t nmemb, size
                return (-1);
 
        list1 = base;
-       setup(list1, list2, nmemb, size, cmp);
+       setup(list1, list2, nmemb, size, cmp, data);
        last = list2 + nmemb * size;
        i = big = 0;
        while (*EVAL(list2) != last) {
@@ -151,7 +152,7 @@ mergesort(void *base, size_t nmemb, size
                        p2 = *EVAL(p2);
                l2 = list1 + (p2 - list2);
                while (f1 < l1 && f2 < l2) {
-                       if ((*cmp)(f1, f2) <= 0) {
+                       if ((*cmp)(f1, f2, data) <= 0) {
                                q = f2;
                                b = f1, t = l1;
                                sense = -1;
@@ -164,7 +165,7 @@ mergesort(void *base, size_t nmemb, size
 #if 0
 LINEAR:
 #endif
-                               while ((b += size) < t && cmp(q, b) >sense)
+                               while ((b += size) < t && cmp(q, b, data)>sense)
                                        if (++i == 6) {
                                                big = 1;
                                                goto EXPONENTIAL;
@@ -173,12 +174,12 @@ LINEAR:
 EXPONENTIAL:                   for (i = size; ; i <<= 1)
                                        if ((p = (b + i)) >= t) {
                                                if ((p = t - size) > b &&
-                                                   (*cmp)(q, p) <= sense)
+                                                   (*cmp)(q, p, data) <= sense)
                                                        t = p;
                                                else
                                                        b = p;
                                                break;
-                                       } else if ((*cmp)(q, p) <= sense) {
+                                       } else if ((*cmp)(q, p, data) <= sense) 
{
                                                t = p;
                                                if (i == size)
                                                        big = 0; 
@@ -190,7 +191,7 @@ SLOWCASE:
 #endif
                                while (t > b+size) {
                                        i = (((t - b) / size) >> 1) * size;
-                                       if ((*cmp)(q, p = b + i) <= sense)
+                                       if ((*cmp)(q, p = b + i, data) <= sense)
                                                t = p;
                                        else
                                                b = p;
@@ -199,7 +200,8 @@ SLOWCASE:
 FASTCASE:                      while (i > size)
                                        if ((*cmp)(q,
                                                p = b +
-                                                   (i = (unsigned int) i >> 
1)) <= sense)
+                                                   (i = (unsigned int) i >> 1),
+                                                    data) <= sense)
                                                t = p;
                                        else
                                                b = p;
@@ -279,7 +281,7 @@ COPY:                               b = t;
 /* XXX: shouldn't this function be static? - lukem 990810 */
 void
 setup(u_char *list1, u_char *list2, size_t n, size_t size,
-    int (*cmp)(const void *, const void *))
+    int (*cmp)(const void *, const void *, void *), void *data)
 {
        int length, tmp, sense;
        u_char *f1, *f2, *s, *l2, *last, *p2;
@@ -291,7 +293,7 @@ setup(u_char *list1, u_char *list2, size
 
        size2 = size*2;
        if (n <= 5) {
-               insertionsort(list1, n, size, cmp);
+               insertionsort(list1, n, size, cmp, data);
                *EVAL(list2) = list2 + n*size;
                return;
        }
@@ -300,19 +302,19 @@ setup(u_char *list1, u_char *list2, size
         * for simplicity.
         */
        i = 4 + (n & 1);
-       insertionsort(list1 + (n - i) * size, i, size, cmp);
+       insertionsort(list1 + (n - i) * size, i, size, cmp, data);
        last = list1 + size * (n - i);
        *EVAL(list2 + (last - list1)) = list2 + n * size;
 
 #ifdef NATURAL
        p2 = list2;
        f1 = list1;
-       sense = (cmp(f1, f1 + size) > 0);
+       sense = (cmp(f1, f1 + size, data) > 0);
        for (; f1 < last; sense = !sense) {
                length = 2;
                                        /* Find pairs with same sense. */
                for (f2 = f1 + size2; f2 < last; f2 += size2) {
-                       if ((cmp(f2, f2+ size) > 0) != sense)
+                       if ((cmp(f2, f2 + size, data) > 0) != sense)
                                break;
                        length += 2;
                }
@@ -325,7 +327,7 @@ setup(u_char *list1, u_char *list2, size
                } else {                                /* Natural merge */
                        l2 = f2;
                        for (f2 = f1 + size2; f2 < l2; f2 += size2) {
-                               if ((cmp(f2-size, f2) > 0) != sense) {
+                               if ((cmp(f2-size, f2, data) > 0) != sense) {
                                        p2 = *EVAL(p2) = f2 - list1 + list2;
                                        if (sense > 0)
                                                reverse(f1, f2 - size);
@@ -335,7 +337,7 @@ setup(u_char *list1, u_char *list2, size
                        if (sense > 0)
                                reverse(f1, f2 - size);
                        f1 = f2;
-                       if (f2 < last || cmp(f2 - size, f2) > 0)
+                       if (f2 < last || cmp(f2 - size, f2, data) > 0)
                                p2 = *EVAL(p2) = f2 - list1 + list2;
                        else
                                p2 = *EVAL(p2) = list2 + n*size;
@@ -344,7 +346,7 @@ setup(u_char *list1, u_char *list2, size
 #else          /* pairwise merge only. */
        for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
                p2 = *EVAL(p2) = p2 + size2;
-               if (cmp (f1, f1 + size) > 0)
+               if (cmp (f1, f1 + size, data) > 0)
                        swap(f1, f1 + size);
        }
 #endif /* NATURAL */
@@ -356,7 +358,7 @@ setup(u_char *list1, u_char *list2, size
  */
 static void
 insertionsort(u_char *a, size_t n, size_t size,
-    int (*cmp)(const void *, const void *))
+    int (*cmp)(const void *, const void *, void *), void *data)
 {
        u_char *ai, *s, *t, *u, tmp;
        size_t i;
@@ -367,8 +369,33 @@ insertionsort(u_char *a, size_t n, size_
        for (ai = a+size; --n >= 1; ai += size)
                for (t = ai; t > a; t -= size) {
                        u = t - size;
-                       if (cmp(u, t) <= 0)
+                       if (cmp(u, t, data) <= 0)
                                break;
                        swap(u, t);
                }
 }
+
+////////////////////////////////////////////////////////////
+// original mergesort()
+
+struct __mergesort {
+       int (*cmp)(const void *, const void *);
+};
+
+static int
+__mergesort_cmp(const void *a, const void *b, void *data)
+{
+       struct __mergesort *ms = data;
+
+       return ms->cmp(a, b);
+}
+
+int
+mergesort(void *base, size_t nmemb, size_t size,
+    int (*cmp)(const void *, const void *))
+{
+       struct __mergesort ms;
+
+       ms.cmp = cmp;
+       return mergesort_r(base, nmemb, size, __mergesort_cmp, &ms);
+}
Index: lib/libc/stdlib/qsort.3
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/qsort.3,v
retrieving revision 1.13
diff -u -p -r1.13 qsort.3
--- lib/libc/stdlib/qsort.3     7 Aug 2003 16:43:42 -0000       1.13
+++ lib/libc/stdlib/qsort.3     8 Dec 2013 22:13:33 -0000
@@ -33,13 +33,16 @@
 .\"
 .\"     from: @(#)qsort.3      8.1 (Berkeley) 6/4/93
 .\"
-.Dd June 4, 1993
+.Dd December 8, 2013
 .Dt QSORT 3
 .Os
 .Sh NAME
 .Nm qsort ,
 .Nm heapsort ,
-.Nm mergesort
+.Nm mergesort ,
+.Nm qsort_r ,
+.Nm heapsort_r ,
+.Nm mergesort_r
 .Nd sort functions
 .Sh LIBRARY
 .Lb libc
@@ -51,6 +54,11 @@
 .Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const 
void *, const void *)"
 .Ft int
 .Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const 
void *, const void *)"
+.Ft void
+.Fn qsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const 
void *, const void *, void *)" "void *userdata"
+.Fn heapsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const 
void *, const void *, void *)" "void *userdata"
+.Ft int
+.Fn mergesort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const 
void *, const void *, void *)" "void *userdata"
 .Sh DESCRIPTION
 The
 .Fn qsort
@@ -147,24 +155,47 @@ is faster than
 .Fn heapsort .
 Memory availability and pre-existing order in the data can make this
 untrue.
+.Pp
+The
+.Fn qsort_r ,
+.Fn heapsort_r ,
+and
+.Fn mergesort_r
+functions are the same as
+.Fn qsort ,
+.Fn heapsort ,
+and
+.Fn mergesort
+respectively except that they accept an additional argument
+.Fa userdata
+which is passed through as an additional argument (the third and last)
+of the comparison function.
 .Sh RETURN VALUES
 The
 .Fn qsort
-function
-returns no value.
+and
+.Fn qsort_r
+functions
+return no value.
 .Pp
 Upon successful completion,
-.Fn heapsort
-and
+.Fn heapsort ,
 .Fn mergesort
+.Fn heapsort_r ,
+and
+.Fn mergesort_r
 return 0.
 Otherwise, they return \-1 and the global variable
 .Va errno
 is set to indicate the error.
 .Sh ERRORS
 The
-.Fn heapsort
-function succeeds unless:
+.Fn heapsort ,
+.Fn mergesort
+.Fn heapsort_r ,
+and
+.Fn heapsort_r
+functions succeed unless:
 .Bl -tag -width Er
 .It Bq Er EINVAL
 The
@@ -174,6 +205,8 @@ the
 .Fa size
 argument to
 .Fn mergesort
+or
+.Fn mergesort_r
 is less than
 .Dq "sizeof(void *) / 2" .
 .It Bq Er ENOMEM
@@ -236,3 +269,11 @@ The
 function
 conforms to
 .St -ansiC .
+.Sh HISTORY
+The
+.Fn qsort_r ,
+.Fn heapsort_r ,
+and
+.Fn mergesort_r
+functions were added in
+.Nx 7.0 .
Index: lib/libc/stdlib/qsort.c
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/qsort.c,v
retrieving revision 1.22
diff -u -p -r1.22 qsort.c
--- lib/libc/stdlib/qsort.c     26 May 2012 21:47:05 -0000      1.22
+++ lib/libc/stdlib/qsort.c     8 Dec 2013 22:13:33 -0000
@@ -44,8 +44,15 @@ __RCSID("$NetBSD: qsort.c,v 1.22 2012/05
 #include <errno.h>
 #include <stdlib.h>
 
+#ifdef __weak_alias
+__weak_alias(qsort_r,_qsort_r)
+#endif
+
+////////////////////////////////////////////////////////////
+// qsort_r
+
 static inline char     *med3(char *, char *, char *,
-    int (*)(const void *, const void *));
+    int (*)(const void *, const void *, void *), void *);
 static inline void      swapfunc(char *, char *, size_t, int);
 
 #define min(a, b)      (a) < (b) ? a : b
@@ -89,17 +96,17 @@ swapfunc(char *a, char *b, size_t n, int
 
 static inline char *
 med3(char *a, char *b, char *c,
-    int (*cmp)(const void *, const void *))
+    int (*cmp)(const void *, const void *, void *), void *data)
 {
 
-       return cmp(a, b) < 0 ?
-              (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
-              :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
+       return cmp(a, b, data) < 0 ?
+              (cmp(b, c, data) < 0 ? b : (cmp(a, c, data) < 0 ? c : a ))
+              :(cmp(b, c, data) > 0 ? b : (cmp(a, c, data) < 0 ? a : c ));
 }
 
 void
-qsort(void *a, size_t n, size_t es,
-    int (*cmp)(const void *, const void *))
+qsort_r(void *a, size_t n, size_t es,
+    int (*cmp)(const void *, const void *, void *), void *data)
 {
        char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
        size_t d, r;
@@ -111,7 +118,8 @@ qsort(void *a, size_t n, size_t es,
 loop:  SWAPINIT(a, es);
        if (n < 7) {
                for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
-                       for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
+                       for (pl = pm;
+                            pl > (char *) a && cmp(pl - es, pl, data) > 0;
                             pl -= es)
                                swap(pl, pl - es);
                return;
@@ -122,25 +130,25 @@ loop:     SWAPINIT(a, es);
                pn = (char *) a + (n - 1) * es;
                if (n > 40) {
                        d = (n / 8) * es;
-                       pl = med3(pl, pl + d, pl + 2 * d, cmp);
-                       pm = med3(pm - d, pm, pm + d, cmp);
-                       pn = med3(pn - 2 * d, pn - d, pn, cmp);
+                       pl = med3(pl, pl + d, pl + 2 * d, cmp, data);
+                       pm = med3(pm - d, pm, pm + d, cmp, data);
+                       pn = med3(pn - 2 * d, pn - d, pn, cmp, data);
                }
-               pm = med3(pl, pm, pn, cmp);
+               pm = med3(pl, pm, pn, cmp, data);
        }
        swap(a, pm);
        pa = pb = (char *) a + es;
 
        pc = pd = (char *) a + (n - 1) * es;
        for (;;) {
-               while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
+               while (pb <= pc && (cmp_result = cmp(pb, a, data)) <= 0) {
                        if (cmp_result == 0) {
                                swap(pa, pb);
                                pa += es;
                        }
                        pb += es;
                }
-               while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
+               while (pb <= pc && (cmp_result = cmp(pc, a, data)) >= 0) {
                        if (cmp_result == 0) {
                                swap(pc, pd);
                                pd -= es;
@@ -160,12 +168,37 @@ loop:     SWAPINIT(a, es);
        r = min((size_t)(pd - pc), pn - pd - es);
        vecswap(pb, pn - r, r);
        if ((r = pb - pa) > es)
-               qsort(a, r / es, es, cmp);
+               qsort_r(a, r / es, es, cmp, data);
        if ((r = pd - pc) > es) { 
                /* Iterate rather than recurse to save stack space */
                a = pn - r;
                n = r / es;
                goto loop;
        }
-/*             qsort(pn - r, r / es, es, cmp);*/
+/*             qsort_r(pn - r, r / es, es, cmp);*/
+}
+
+////////////////////////////////////////////////////////////
+// original qsort()
+
+struct __qsort {
+       int (*cmp)(const void *, const void *);
+};
+
+static int
+__qsort_cmp(const void *a, const void *b, void *data)
+{
+       struct __qsort *qs = data;
+
+       return qs->cmp(a, b);
+}
+
+void
+qsort(void *a, size_t n, size_t es,
+    int (*cmp)(const void *, const void *))
+{
+       struct __qsort qs;
+
+       qs.cmp = cmp;
+       qsort_r(a, n, es, __qsort_cmp, &qs);
 }
Index: sys/lib/libkern/libkern.h
===================================================================
RCS file: /cvsroot/src/sys/lib/libkern/libkern.h,v
retrieving revision 1.108
diff -u -p -r1.108 libkern.h
--- sys/lib/libkern/libkern.h   28 Aug 2013 16:20:38 -0000      1.108
+++ sys/lib/libkern/libkern.h   8 Dec 2013 22:13:33 -0000
@@ -337,8 +337,10 @@ unsigned long long strtoull(const char *
 uintmax_t strtoumax(const char *, char **, int);
 int     snprintb(char *, size_t, const char *, uint64_t);
 int     snprintb_m(char *, size_t, const char *, uint64_t, size_t);
-int     kheapsort(void *, size_t, size_t, int (*)(const void *, const void *),
-                  void *);
+int     kheapsort(void *, size_t, size_t, void *,
+           int (*)(const void *, const void *));
+int     kheapsort_r(void *, size_t, size_t, void *,
+           int (*)(const void *, const void *, void *), void *);
 uint32_t crc32(uint32_t, const uint8_t *, size_t);
 unsigned int   popcount(unsigned int) __constfunc;
 unsigned int   popcountl(unsigned long) __constfunc;


-- 
David A. Holland
dholland%netbsd.org@localhost


Home | Main Index | Thread Index | Old Index