diff options
Diffstat (limited to 'lib/libc/stdlib/heapsort.c')
-rw-r--r-- | lib/libc/stdlib/heapsort.c | 26 |
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; |