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