tech-userlevel archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
qsort_r again
(Cc: tech-kern because of kheapsort())
Some time back I made a set of patches for qsort_r(), that is, a
version of qsort that allows passing a data pointer through, along
with corresponding mergesort_r() and heapsort_r().
After some discussion the conclusion was that instead of using thunks
to implement qsort in terms of qsort_r, it was better to implement
both versions in terms of a common internal version. The following
patchset does that.
heapsort() is used in two places 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
data argument;
- update the callers for the signature change;
but I have not changed either caller to call kheapsort_r
instead. Based on the code, this should probably be done later; then
the plain kheapsort can be removed.
Note that this set of names and signatures matches what's in Linux.
Apparently FreeBSD did it differently, but there are reasons to prefer
this arrangement of arguments.
Joerg also says that the _r names are inappropriate because the
originals are reentrant, but I think that's tilting at windmills and
it's more useful to be compatible.
------
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 27 Aug 2016 20:06:46 -0000
@@ -60,6 +60,7 @@ __RCSID("$NetBSD: heapsort.c,v 1.3 2008/
#include <assert.h>
#include <errno.h>
+#include <stdbool.h>
#include <stdlib.h>
#if HAVE_NBTOOL_CONFIG_H
@@ -69,10 +70,24 @@ __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 */
/*
+ * Union of comparison function pointers for the plain and _r forms
+ */
+union heapsort_cmp {
+ int (*cmp)(const void *, const void *);
+ int (*cmp_r)(const void *, const void *, void *);
+};
+
+/*
+ * Macro for calling through the union
+ */
+#define COMPAR(a, b, d) (is_r ? compar->cmp_r(a, b, d) : compar->cmp(a, b))
+
+/*
* Swap two areas of size number of bytes. Although qsort(3) permits random
* blocks of memory to be sorted, sorting pointers is almost certainly the
* common case (and, were it not, could easily be made so). Regardless, it
@@ -109,12 +124,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 +155,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 +167,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; \
} \
@@ -168,13 +183,13 @@ __weak_alias(heapsort,_heapsort)
* only advantage over quicksort is that it requires little additional memory.
*/
#if defined(_KERNEL) || defined(_STANDALONE)
-int
-kheapsort(void *vbase, size_t nmemb, size_t size,
- int (*compar)(const void *, const void *), void *k)
+static int
+kheapsort_internal(void *vbase, size_t nmemb, size_t size, void *k,
+ bool is_r, const union heapsort_cmp *compar, void *data)
#else
-int
-heapsort(void *vbase, size_t nmemb, size_t size,
- int (*compar)(const void *, const void *))
+static int
+heapsort_internal(void *vbase, size_t nmemb, size_t size,
+ bool is_r, const union heapsort_cmp *compar, void *data)
#endif
{
size_t cnt, i, j, l;
@@ -186,6 +201,7 @@ heapsort(void *vbase, size_t nmemb, size
_DIAGASSERT(vbase != NULL);
_DIAGASSERT(compar != NULL);
+ _DIAGASSERT(is_r ? compar->cmp_r != NULL : compar->cmp != NULL);
if (nmemb <= 1)
return (0);
@@ -227,3 +243,49 @@ heapsort(void *vbase, size_t nmemb, size
#endif
return (0);
}
+
+////////////////////////////////////////////////////////////
+// heapsort_r() with data pointer
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+int
+kheapsort_r(void *vbase, size_t nmemb, size_t size, void *k,
+ int (*compar)(const void *, const void *, void *), void *data)
+{
+ union heapsort_cmp cmp = { .cmp_r = compar };
+
+ return kheapsort_internal(vbase, nmemb, size, k, true, &cmp, data);
+}
+#else
+int
+heapsort_r(void *vbase, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *, void *), void *data)
+{
+ union heapsort_cmp cmp = { .cmp_r = compar };
+
+ return heapsort_internal(vbase, nmemb, size, true, &cmp, data);
+}
+#endif
+
+////////////////////////////////////////////////////////////
+// original heapsort()
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+int
+kheapsort(void *vbase, size_t nmemb, size_t size, void *k,
+ int (*compar)(const void *, const void *))
+{
+ union heapsort_cmp cmp = { .cmp = compar };
+
+ return kheapsort_internal(vbase, nmemb, size, k, false, &cmp, NULL);
+}
+#else
+int
+heapsort(void *vbase, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *))
+{
+ union heapsort_cmp cmp = { .cmp = compar };
+
+ return heapsort_internal(vbase, nmemb, size, false, &cmp, NULL);
+}
+#endif
Index: include/stdlib.h
===================================================================
RCS file: /cvsroot/src/include/stdlib.h,v
retrieving revision 1.117
diff -u -p -r1.117 stdlib.h
--- include/stdlib.h 1 Jul 2016 22:42:01 -0000 1.117
+++ include/stdlib.h 27 Aug 2016 20:06:46 -0000
@@ -310,9 +310,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 ptsname_r(int, char *, size_t);
int radixsort(const unsigned char **, int, const unsigned char *,
unsigned);
Index: lib/libc/include/namespace.h
===================================================================
RCS file: /cvsroot/src/lib/libc/include/namespace.h,v
retrieving revision 1.180
diff -u -p -r1.180 namespace.h
--- lib/libc/include/namespace.h 3 Apr 2016 00:19:42 -0000 1.180
+++ lib/libc/include/namespace.h 27 Aug 2016 20:06:46 -0000
@@ -402,6 +402,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
@@ -482,6 +483,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
@@ -543,6 +545,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/Makefile.inc
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/Makefile.inc,v
retrieving revision 1.92
diff -u -p -r1.92 Makefile.inc
--- lib/libc/stdlib/Makefile.inc 1 Apr 2016 12:37:48 -0000 1.92
+++ lib/libc/stdlib/Makefile.inc 27 Aug 2016 20:06:46 -0000
@@ -76,8 +76,9 @@ MLINKS+=jemalloc.3 malloc.conf.5
MLINKS+=lsearch.3 lfind.3
MLINKS+=malloc.3 calloc.3 malloc.3 realloc.3 malloc.3 free.3
MLINKS+=posix_memalign.3 aligned_alloc.3
-MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3
MLINKS+=ptsname.3 ptsname_r.3
+MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3
+MLINKS+=qsort.3 qsort_r.3 qsort.3 heapsort_r.3 qsort.3 mergesort_r.3
MLINKS+=rand.3 rand_r.3
MLINKS+=rand.3 srand.3
MLINKS+=rand48.3 drand48.3 rand48.3 erand48.3 rand48.3 lrand48.3
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 27 Aug 2016 20:06:46 -0000
@@ -60,17 +60,33 @@ __RCSID("$NetBSD: merge.c,v 1.14 2012/03
#include <assert.h>
#include <errno.h>
+#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#ifdef __weak_alias
__weak_alias(mergesort,_mergesort)
+__weak_alias(mergesort_r,_mergesort_r)
#endif
+/*
+ * Union of comparison function pointers for the plain and _r forms
+ */
+union mergesort_cmp {
+ int (*cmp)(const void *, const void *);
+ int (*cmp_r)(const void *, const void *, void *);
+};
+
+/*
+ * Macro for calling through the union
+ */
+#define COMPAR(a, b, d) (is_r ? compar->cmp_r(a, b, d) : compar->cmp(a, b))
+
+
static void setup(u_char *, u_char *, size_t, size_t,
- int (*)(const void *, const void *));
+ bool is_r, const union mergesort_cmp *, void *);
static void insertionsort(u_char *, size_t, size_t,
- int (*)(const void *, const void *));
+ bool is_r, const union mergesort_cmp *, void *);
#define ISIZE sizeof(int)
#define PSIZE sizeof(u_char *)
@@ -107,9 +123,9 @@ 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 *))
+static int
+mergesort_internal(void *base, size_t nmemb, size_t size,
+ bool is_r, const union mergesort_cmp *compar, void *data)
{
size_t i;
int sense;
@@ -118,7 +134,8 @@ mergesort(void *base, size_t nmemb, size
u_char *list2, *list1, *p2, *p, *last, **p1;
_DIAGASSERT(base != NULL);
- _DIAGASSERT(cmp != NULL);
+ _DIAGASSERT(compar != NULL);
+ _DIAGASSERT(is_r ? compar->cmp_r != NULL : compar->cmp != NULL);
if (size < PSIZE / 2) { /* Pointers must fit into 2 * size. */
errno = EINVAL;
@@ -137,7 +154,7 @@ mergesort(void *base, size_t nmemb, size
return (-1);
list1 = base;
- setup(list1, list2, nmemb, size, cmp);
+ setup(list1, list2, nmemb, size, is_r, compar, data);
last = list2 + nmemb * size;
i = big = 0;
while (*EVAL(list2) != last) {
@@ -151,7 +168,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 (COMPAR(f1, f2, data) <= 0) {
q = f2;
b = f1, t = l1;
sense = -1;
@@ -164,7 +181,7 @@ mergesort(void *base, size_t nmemb, size
#if 0
LINEAR:
#endif
- while ((b += size) < t && cmp(q, b) >sense)
+ while ((b += size) < t && COMPAR(q, b, data)>sense)
if (++i == 6) {
big = 1;
goto EXPONENTIAL;
@@ -173,12 +190,12 @@ LINEAR:
EXPONENTIAL: for (i = size; ; i <<= 1)
if ((p = (b + i)) >= t) {
if ((p = t - size) > b &&
- (*cmp)(q, p) <= sense)
+ COMPAR(q, p, data) <= sense)
t = p;
else
b = p;
break;
- } else if ((*cmp)(q, p) <= sense) {
+ } else if (COMPAR(q, p, data) <= sense) {
t = p;
if (i == size)
big = 0;
@@ -190,16 +207,17 @@ SLOWCASE:
#endif
while (t > b+size) {
i = (((t - b) / size) >> 1) * size;
- if ((*cmp)(q, p = b + i) <= sense)
+ if (COMPAR(q, p = b + i, data) <= sense)
t = p;
else
b = p;
}
goto COPY;
FASTCASE: while (i > size)
- if ((*cmp)(q,
+ if (COMPAR(q,
p = b +
- (i = (unsigned int) i >> 1)) <= sense)
+ (i = (unsigned int) i >> 1),
+ data) <= sense)
t = p;
else
b = p;
@@ -276,22 +294,22 @@ COPY: b = t;
* is defined. Otherwise simple pairwise merging is used.)
*/
-/* XXX: shouldn't this function be static? - lukem 990810 */
-void
+static void
setup(u_char *list1, u_char *list2, size_t n, size_t size,
- int (*cmp)(const void *, const void *))
+ bool is_r, const union mergesort_cmp *compar, void *data)
{
int length, tmp, sense;
u_char *f1, *f2, *s, *l2, *last, *p2;
size_t size2, i;
- _DIAGASSERT(cmp != NULL);
+ _DIAGASSERT(compar != NULL);
+ _DIAGASSERT(is_r ? compar->cmp_r != NULL : compar->cmp != NULL);
_DIAGASSERT(list1 != NULL);
_DIAGASSERT(list2 != NULL);
size2 = size*2;
if (n <= 5) {
- insertionsort(list1, n, size, cmp);
+ insertionsort(list1, n, size, is_r, compar, data);
*EVAL(list2) = list2 + n*size;
return;
}
@@ -300,19 +318,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, is_r, compar, 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 = (COMPAR(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 ((COMPAR(f2, f2 + size, data) > 0) != sense)
break;
length += 2;
}
@@ -325,7 +343,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 ((COMPAR(f2-size, f2, data) > 0) != sense) {
p2 = *EVAL(p2) = f2 - list1 + list2;
if (sense > 0)
reverse(f1, f2 - size);
@@ -335,7 +353,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 || COMPAR(f2 - size, f2, data) > 0)
p2 = *EVAL(p2) = f2 - list1 + list2;
else
p2 = *EVAL(p2) = list2 + n*size;
@@ -344,7 +362,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 (COMPAR (f1, f1 + size, data) > 0)
swap(f1, f1 + size);
}
#endif /* NATURAL */
@@ -356,19 +374,44 @@ 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 *))
+ bool is_r, const union mergesort_cmp *compar, void *data)
{
u_char *ai, *s, *t, *u, tmp;
size_t i;
_DIAGASSERT(a != NULL);
- _DIAGASSERT(cmp != NULL);
+ _DIAGASSERT(compar != NULL);
+ _DIAGASSERT(is_r ? compar->cmp_r != NULL : compar->cmp != NULL);
for (ai = a+size; --n >= 1; ai += size)
for (t = ai; t > a; t -= size) {
u = t - size;
- if (cmp(u, t) <= 0)
+ if (COMPAR(u, t, data) <= 0)
break;
swap(u, t);
}
}
+
+////////////////////////////////////////////////////////////
+// mergesort_r()
+
+int
+mergesort_r(void *base, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *, void *), void *data)
+{
+ union mergesort_cmp cmp = { .cmp_r = compar };
+
+ return mergesort_internal(base, nmemb, size, true, &cmp, data);
+}
+
+////////////////////////////////////////////////////////////
+// original mergesort()
+
+int
+mergesort(void *base, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *))
+{
+ union mergesort_cmp cmp = { .cmp = compar };
+
+ return mergesort_internal(base, nmemb, size, false, &cmp, NULL);
+}
Index: lib/libc/stdlib/qsort.3
===================================================================
RCS file: /cvsroot/src/lib/libc/stdlib/qsort.3,v
retrieving revision 1.14
diff -u -p -r1.14 qsort.3
--- lib/libc/stdlib/qsort.3 19 Sep 2014 16:02:58 -0000 1.14
+++ lib/libc/stdlib/qsort.3 27 Aug 2016 20:06:46 -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,16 +155,35 @@ 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
@@ -169,8 +196,12 @@ did not permit the comparison routine it
This is no longer true.
.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
@@ -180,6 +211,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 27 Aug 2016 20:06:46 -0000
@@ -40,13 +40,32 @@ __RCSID("$NetBSD: qsort.c,v 1.22 2012/05
#include <sys/types.h>
+#include "namespace.h"
#include <assert.h>
#include <errno.h>
+#include <stdbool.h>
#include <stdlib.h>
-static inline char *med3(char *, char *, char *,
- int (*)(const void *, const void *));
-static inline void swapfunc(char *, char *, size_t, int);
+#ifdef __weak_alias
+__weak_alias(qsort_r,_qsort_r)
+#endif
+
+////////////////////////////////////////////////////////////
+// qsort_internal
+
+/*
+ * Union of comparison function pointers for the plain and _r forms
+ */
+union qsort_cmp {
+ int (*cmp)(const void *, const void *);
+ int (*cmp_r)(const void *, const void *, void *);
+};
+
+/*
+ * Macro for calling through the union
+ */
+#define COMPAR(a, b, d) (is_r ? compar->cmp_r(a, b, d) : compar->cmp(a, b))
+
#define min(a, b) (a) < (b) ? a : b
@@ -89,29 +108,31 @@ 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 *))
+ bool is_r, const union qsort_cmp *compar, 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 COMPAR(a, b, data) < 0 ?
+ (COMPAR(b, c, data) < 0 ? b : (COMPAR(a, c, data) < 0 ? c : a ))
+ :(COMPAR(b, c, data) > 0 ? b : (COMPAR(a, c, data) < 0 ? a : c ));
}
-void
-qsort(void *a, size_t n, size_t es,
- int (*cmp)(const void *, const void *))
+static void
+qsort_internal(void *a, size_t n, size_t es,
+ bool is_r, const union qsort_cmp *compar, void *data)
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
size_t d, r;
int swaptype, cmp_result;
_DIAGASSERT(a != NULL || n == 0 || es == 0);
- _DIAGASSERT(cmp != NULL);
+ _DIAGASSERT(compar != NULL);
+ _DIAGASSERT(is_r ? compar->cmp_r != NULL : compar->cmp != NULL);
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 && COMPAR(pl - es, pl, data) > 0;
pl -= es)
swap(pl, pl - es);
return;
@@ -122,25 +143,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, is_r, compar, data);
+ pm = med3(pm - d, pm, pm + d, is_r, compar, data);
+ pn = med3(pn - 2 * d, pn - d, pn, is_r, compar, data);
}
- pm = med3(pl, pm, pn, cmp);
+ pm = med3(pl, pm, pn, is_r, compar, 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 = COMPAR(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 = COMPAR(pc, a, data)) >= 0) {
if (cmp_result == 0) {
swap(pc, pd);
pd -= es;
@@ -160,12 +181,36 @@ 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_internal(a, r / es, es, is_r, compar, 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_internal(pn - r, r / es, es, cmp);*/
+}
+
+////////////////////////////////////////////////////////////
+// qsort_r()
+
+void
+qsort_r(void *a, size_t n, size_t es,
+ int (*compar)(const void *, const void *, void *), void *data)
+{
+ union qsort_cmp cmp = { .cmp_r = compar };
+
+ qsort_internal(a, n, es, true, &cmp, data);
+}
+
+////////////////////////////////////////////////////////////
+// original qsort()
+
+void
+qsort(void *a, size_t n, size_t es,
+ int (*compar)(const void *, const void *))
+{
+ union qsort_cmp cmp = { .cmp = compar };
+
+ qsort_internal(a, n, es, false, &cmp, NULL);
}
Index: sys/kern/kern_ksyms.c
===================================================================
RCS file: /cvsroot/src/sys/kern/kern_ksyms.c,v
retrieving revision 1.84
diff -u -p -r1.84 kern_ksyms.c
--- sys/kern/kern_ksyms.c 7 Jul 2016 06:55:43 -0000 1.84
+++ sys/kern/kern_ksyms.c 27 Aug 2016 20:06:47 -0000
@@ -397,7 +397,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: sys/lib/libkern/libkern.h
===================================================================
RCS file: /cvsroot/src/sys/lib/libkern/libkern.h,v
retrieving revision 1.124
diff -u -p -r1.124 libkern.h
--- sys/lib/libkern/libkern.h 7 Jul 2016 06:55:43 -0000 1.124
+++ sys/lib/libkern/libkern.h 27 Aug 2016 20:06:47 -0000
@@ -451,8 +451,10 @@ uintmax_t strtou(const char * __restrict
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);
#if __GNUC_PREREQ__(4, 5) \
&& (defined(__alpha_cix__) || defined(__mips_popcount))
Index: sys/ufs/ext2fs/ext2fs_htree.c
===================================================================
RCS file: /cvsroot/src/sys/ufs/ext2fs/ext2fs_htree.c,v
retrieving revision 1.9
diff -u -p -r1.9 ext2fs_htree.c
--- sys/ufs/ext2fs/ext2fs_htree.c 23 Aug 2016 06:23:26 -0000 1.9
+++ sys/ufs/ext2fs/ext2fs_htree.c 27 Aug 2016 20:06:47 -0000
@@ -306,7 +306,7 @@ ext2fs_htree_split_dirblock(char *block1
* Sort directory entry descriptors by name hash value.
*/
kheapsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry),
- ext2fs_htree_cmp_sort_entry, &dummy);
+ &dummy, ext2fs_htree_cmp_sort_entry);
/*
* Count the number of entries to move to directory block 2.
Index: distrib/sets/lists/comp/mi
===================================================================
RCS file: /cvsroot/src/distrib/sets/lists/comp/mi,v
retrieving revision 1.2059
diff -u -p -r1.2059 mi
--- distrib/sets/lists/comp/mi 27 Aug 2016 08:03:47 -0000 1.2059
+++ distrib/sets/lists/comp/mi 27 Aug 2016 20:06:47 -0000
@@ -6693,6 +6693,7 @@
./usr/share/man/cat3/hdestroy1_r.0 comp-c-catman .cat
./usr/share/man/cat3/hdestroy_r.0 comp-c-catman .cat
./usr/share/man/cat3/heapsort.0 comp-c-catman .cat
+./usr/share/man/cat3/heapsort_r.0 comp-c-catman .cat
./usr/share/man/cat3/herror.0 comp-c-catman .cat
./usr/share/man/cat3/hesiod.0 comp-c-catman hesiod,.cat
./usr/share/man/cat3/hesiod_end.0 comp-c-catman hesiod,.cat
@@ -7772,6 +7773,7 @@
./usr/share/man/cat3/menu_win.0 comp-c-catman .cat
./usr/share/man/cat3/menus.0 comp-c-catman .cat
./usr/share/man/cat3/mergesort.0 comp-c-catman .cat
+./usr/share/man/cat3/mergesort_r.0 comp-c-catman .cat
./usr/share/man/cat3/meta.0 comp-c-catman .cat
./usr/share/man/cat3/mi_vector_hash.0 comp-c-catman .cat
./usr/share/man/cat3/minor.0 comp-c-catman .cat
@@ -8506,6 +8508,7 @@
./usr/share/man/cat3/qdiv.0 comp-c-catman .cat
./usr/share/man/cat3/qiflush.0 comp-c-catman .cat
./usr/share/man/cat3/qsort.0 comp-c-catman .cat
+./usr/share/man/cat3/qsort_r.0 comp-c-catman .cat
./usr/share/man/cat3/queue.0 comp-c-catman .cat
./usr/share/man/cat3/quick_exit.0 comp-c-catman .cat
./usr/share/man/cat3/quota_close.0 comp-c-catman .cat
@@ -13975,6 +13978,7 @@
./usr/share/man/html3/hdestroy1_r.html comp-c-htmlman html
./usr/share/man/html3/hdestroy_r.html comp-c-htmlman html
./usr/share/man/html3/heapsort.html comp-c-htmlman html
+./usr/share/man/html3/heapsort_r.html comp-c-htmlman html
./usr/share/man/html3/herror.html comp-c-htmlman html
./usr/share/man/html3/hesiod.html comp-c-htmlman hesiod,html
./usr/share/man/html3/hesiod_end.html comp-c-htmlman hesiod,html
@@ -15021,6 +15025,7 @@
./usr/share/man/html3/menu_win.html comp-c-htmlman html
./usr/share/man/html3/menus.html comp-c-htmlman html
./usr/share/man/html3/mergesort.html comp-c-htmlman html
+./usr/share/man/html3/mergesort_r.html comp-c-htmlman html
./usr/share/man/html3/meta.html comp-c-htmlman html
./usr/share/man/html3/mi_vector_hash.html comp-c-htmlman html
./usr/share/man/html3/minor.html comp-c-htmlman html
@@ -15750,6 +15755,7 @@
./usr/share/man/html3/qdiv.html comp-c-htmlman html
./usr/share/man/html3/qiflush.html comp-c-htmlman html
./usr/share/man/html3/qsort.html comp-c-htmlman html
+./usr/share/man/html3/qsort_r.html comp-c-htmlman html
./usr/share/man/html3/queue.html comp-c-htmlman html
./usr/share/man/html3/quick_exit.html comp-c-htmlman html
./usr/share/man/html3/quota_close.html comp-c-htmlman html
@@ -21174,6 +21180,7 @@
./usr/share/man/man3/hdestroy1_r.3 comp-c-man .man
./usr/share/man/man3/hdestroy_r.3 comp-c-man .man
./usr/share/man/man3/heapsort.3 comp-c-man .man
+./usr/share/man/man3/heapsort_r.3 comp-c-man .man
./usr/share/man/man3/herror.3 comp-c-man .man
./usr/share/man/man3/hesiod.3 comp-c-man hesiod,.man
./usr/share/man/man3/hesiod_end.3 comp-c-man hesiod,.man
@@ -22253,6 +22260,7 @@
./usr/share/man/man3/menu_win.3 comp-c-man .man
./usr/share/man/man3/menus.3 comp-c-man .man
./usr/share/man/man3/mergesort.3 comp-c-man .man
+./usr/share/man/man3/mergesort_r.3 comp-c-man .man
./usr/share/man/man3/meta.3 comp-c-man .man
./usr/share/man/man3/mi_vector_hash.3 comp-c-man .man
./usr/share/man/man3/minor.3 comp-c-man .man
@@ -22987,6 +22995,7 @@
./usr/share/man/man3/qdiv.3 comp-c-man .man
./usr/share/man/man3/qiflush.3 comp-c-man .man
./usr/share/man/man3/qsort.3 comp-c-man .man
+./usr/share/man/man3/qsort_r.3 comp-c-man .man
./usr/share/man/man3/queue.3 comp-c-man .man
./usr/share/man/man3/quick_exit.3 comp-c-man .man
./usr/share/man/man3/quota_close.3 comp-c-man .man
--
David A. Holland
dholland%netbsd.org@localhost
Home |
Main Index |
Thread Index |
Old Index