1/* $NetBSD: heapsort.c,v 1.3 2008/11/17 10:21:30 jnemeth Exp $ */ 2 3/*- 4 * Copyright (c) 1991, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35#if HAVE_NBTOOL_CONFIG_H 36#include "nbtool_config.h" 37/* 38 * XXX Undefine the renames of these functions so that we don't 39 * XXX rename the versions found in the host's headers by mistake! 40 */ 41#undef heapsort 42#endif 43 44#include <sys/cdefs.h> 45#if defined(LIBC_SCCS) && !defined(lint) 46#if 0 47static char sccsid[] = "from: @(#)heapsort.c 8.1 (Berkeley) 6/4/93"; 48#else 49__RCSID("$NetBSD: heapsort.c,v 1.3 2008/11/17 10:21:30 jnemeth Exp $"); 50#endif 51#endif /* LIBC_SCCS and not lint */ 52 53#if defined(_KERNEL) || defined(_STANDALONE) 54#include <sys/types.h> 55 56#include <lib/libkern/libkern.h> 57#else /* _KERNEL || _STANDALONE */ 58#include "namespace.h" 59#include <sys/types.h> 60 61#include <assert.h> 62#include <errno.h> 63#include <stdlib.h> 64 65#if HAVE_NBTOOL_CONFIG_H 66/* XXX Now, re-apply the renaming that we undid above. */ 67#define heapsort __nbcompat_heapsort 68#endif 69 70#ifdef __weak_alias 71__weak_alias(heapsort,_heapsort) 72#endif 73#endif /* _KERNEL || _STANDALONE */ 74 75/* 76 * Swap two areas of size number of bytes. Although qsort(3) permits random 77 * blocks of memory to be sorted, sorting pointers is almost certainly the 78 * common case (and, were it not, could easily be made so). Regardless, it 79 * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer 80 * arithmetic gets lost in the time required for comparison function calls. 81 */ 82#define SWAP(a, b, count, size, tmp) { \ 83 count = size; \ 84 do { \ 85 tmp = *a; \ 86 *a++ = *b; \ 87 *b++ = tmp; \ 88 } while (--count); \ 89} 90 91/* Copy one block of size size to another. */ 92#define COPY(a, b, count, size, tmp1, tmp2) { \ 93 count = size; \ 94 tmp1 = a; \ 95 tmp2 = b; \ 96 do { \ 97 *tmp1++ = *tmp2++; \ 98 } while (--count); \ 99} 100 101/* 102 * Build the list into a heap, where a heap is defined such that for 103 * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N. 104 * 105 * There are two cases. If j == nmemb, select largest of Ki and Kj. If 106 * j < nmemb, select largest of Ki, Kj and Kj+1. 107 */ 108#define CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp) { \ 109 for (par_i = initval; (child_i = par_i * 2) <= nmemb; \ 110 par_i = child_i) { \ 111 child = base + child_i * size; \ 112 if (child_i < nmemb && compar(child, child + size) < 0) { \ 113 child += size; \ 114 ++child_i; \ 115 } \ 116 par = base + par_i * size; \ 117 if (compar(child, par) <= 0) \ 118 break; \ 119 SWAP(par, child, count, size, tmp); \ 120 } \ 121} 122 123/* 124 * Select the top of the heap and 'heapify'. Since by far the most expensive 125 * action is the call to the compar function, a considerable optimization 126 * in the average case can be achieved due to the fact that k, the displaced 127 * element, is usually quite small, so it would be preferable to first 128 * heapify, always maintaining the invariant that the larger child is copied 129 * over its parent's record. 130 * 131 * Then, starting from the *bottom* of the heap, finding k's correct place, 132 * again maintaining the invariant. As a result of the invariant no element 133 * is 'lost' when k is assigned its correct place in the heap. 134 * 135 * The time savings from this optimization are on the order of 15-20% for the 136 * average case. See Knuth, Vol. 3, page 158, problem 18. 137 * 138 * XXX Don't break the #define SELECT line, below. Reiser cpp gets upset. 139 */ 140#define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) { \ 141 for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \ 142 child = base + child_i * size; \ 143 if (child_i < nmemb && compar(child, child + size) < 0) { \ 144 child += size; \ 145 ++child_i; \ 146 } \ 147 par = base + par_i * size; \ 148 COPY(par, child, count, size, tmp1, tmp2); \ 149 } \ 150 for (;;) { \ 151 child_i = par_i; \ 152 par_i = child_i / 2; \ 153 child = base + child_i * size; \ 154 par = base + par_i * size; \ 155 if (child_i == 1 || compar(k, par) < 0) { \ 156 COPY(child, k, count, size, tmp1, tmp2); \ 157 break; \ 158 } \ 159 COPY(child, par, count, size, tmp1, tmp2); \ 160 } \ 161} 162 163/* 164 * Heapsort -- Knuth, Vol. 3, page 145. Runs in O (N lg N), both average 165 * and worst. While heapsort is faster than the worst case of quicksort, 166 * the BSD quicksort does median selection so that the chance of finding 167 * a data set that will trigger the worst case is nonexistent. Heapsort's 168 * only advantage over quicksort is that it requires little additional memory. 169 */ 170#if defined(_KERNEL) || defined(_STANDALONE) 171int 172kheapsort(void *vbase, size_t nmemb, size_t size, 173 int (*compar)(const void *, const void *), void *k) 174#else 175int 176heapsort(void *vbase, size_t nmemb, size_t size, 177 int (*compar)(const void *, const void *)) 178#endif 179{ 180 size_t cnt, i, j, l; 181 char tmp, *tmp1, *tmp2; 182 char *base, *p, *t; 183#if !defined(_KERNEL) && !defined(_STANDALONE) 184 char *k; 185#endif 186 187 _DIAGASSERT(vbase != NULL); 188 _DIAGASSERT(compar != NULL); 189 190 if (nmemb <= 1) 191 return (0); 192 193 if (!size) { 194#if !defined(_KERNEL) && !defined(_STANDALONE) 195 errno = EINVAL; 196#endif 197 return (-1); 198 } 199 200#if !defined(_KERNEL) && !defined(_STANDALONE) 201 if ((k = malloc(size)) == NULL) 202 return (-1); 203#endif 204 205 /* 206 * Items are numbered from 1 to nmemb, so offset from size bytes 207 * below the starting address. 208 */ 209 base = (char *)vbase - size; 210 211 for (l = nmemb / 2 + 1; --l;) 212 CREATE(l, nmemb, i, j, t, p, size, cnt, tmp); 213 214 /* 215 * For each element of the heap, save the largest element into its 216 * final slot, save the displaced element (k), then recreate the 217 * heap. 218 */ 219 while (nmemb > 1) { 220 COPY(k, base + nmemb * size, cnt, size, tmp1, tmp2); 221 COPY(base + nmemb * size, base + size, cnt, size, tmp1, tmp2); 222 --nmemb; 223 SELECT(i, j, nmemb, t, p, size, k, cnt, tmp1, tmp2); 224 } 225#if !defined(_KERNEL) && !defined(_STANDALONE) 226 free(k); 227#endif 228 return (0); 229} 230