summaryrefslogtreecommitdiffstats
path: root/lib/libc/stdlib/heapsort.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libc/stdlib/heapsort.c')
-rw-r--r--lib/libc/stdlib/heapsort.c26
1 files changed, 22 insertions, 4 deletions
diff --git a/lib/libc/stdlib/heapsort.c b/lib/libc/stdlib/heapsort.c
index 4bad8a7..673a6a1 100644
--- a/lib/libc/stdlib/heapsort.c
+++ b/lib/libc/stdlib/heapsort.c
@@ -1,6 +1,8 @@
/*-
* Copyright (c) 1991, 1993
* The Regents of the University of California. All rights reserved.
+ * Copyright (c) 2014 David T. Chisnall
+ * All rights reserved.
*
* This code is derived from software contributed to Berkeley by
* Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias.
@@ -40,6 +42,14 @@ __FBSDID("$FreeBSD$");
#include <stddef.h>
#include <stdlib.h>
+#ifdef I_AM_HEAPSORT_B
+#include "block_abi.h"
+#define COMPAR(x, y) CALL_BLOCK(compar, x, y)
+typedef DECLARE_BLOCK(int, heapsort_block, const void *, const void *);
+#else
+#define COMPAR(x, y) compar(x, y)
+#endif
+
/*
* 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
@@ -77,12 +87,12 @@ __FBSDID("$FreeBSD$");
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) < 0) { \
child += size; \
++child_i; \
} \
par = base + par_i * size; \
- if (compar(child, par) <= 0) \
+ if (COMPAR(child, par) <= 0) \
break; \
SWAP(par, child, count, size, tmp); \
} \
@@ -108,7 +118,7 @@ __FBSDID("$FreeBSD$");
#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) < 0) { \
child += size; \
++child_i; \
} \
@@ -120,7 +130,7 @@ __FBSDID("$FreeBSD$");
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) < 0) { \
COPY(child, k, count, size, tmp1, tmp2); \
break; \
} \
@@ -135,11 +145,19 @@ __FBSDID("$FreeBSD$");
* a data set that will trigger the worst case is nonexistent. Heapsort's
* only advantage over quicksort is that it requires little additional memory.
*/
+#ifdef I_AM_HEAPSORT_B
+int
+heapsort_b(vbase, nmemb, size, compar)
+ void *vbase;
+ size_t nmemb, size;
+ heapsort_block compar;
+#else
int
heapsort(vbase, nmemb, size, compar)
void *vbase;
size_t nmemb, size;
int (*compar)(const void *, const void *);
+#endif
{
size_t cnt, i, j, l;
char tmp, *tmp1, *tmp2;
OpenPOWER on IntegriCloud