158f0484fSRodney W. Grimes /*-
28a16b7a1SPedro F. Giffuni * SPDX-License-Identifier: BSD-3-Clause
38a16b7a1SPedro F. Giffuni *
458f0484fSRodney W. Grimes * Copyright (c) 1991, 1993
558f0484fSRodney W. Grimes * The Regents of the University of California. All rights reserved.
646cdc140SDavid Chisnall * Copyright (c) 2014 David T. Chisnall
746cdc140SDavid Chisnall * All rights reserved.
858f0484fSRodney W. Grimes *
958f0484fSRodney W. Grimes * This code is derived from software contributed to Berkeley by
1058f0484fSRodney W. Grimes * Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias.
1158f0484fSRodney W. Grimes *
1258f0484fSRodney W. Grimes * Redistribution and use in source and binary forms, with or without
1358f0484fSRodney W. Grimes * modification, are permitted provided that the following conditions
1458f0484fSRodney W. Grimes * are met:
1558f0484fSRodney W. Grimes * 1. Redistributions of source code must retain the above copyright
1658f0484fSRodney W. Grimes * notice, this list of conditions and the following disclaimer.
1758f0484fSRodney W. Grimes * 2. Redistributions in binary form must reproduce the above copyright
1858f0484fSRodney W. Grimes * notice, this list of conditions and the following disclaimer in the
1958f0484fSRodney W. Grimes * documentation and/or other materials provided with the distribution.
203fb3b97cSEd Maste * 3. Neither the name of the University nor the names of its contributors
2158f0484fSRodney W. Grimes * may be used to endorse or promote products derived from this software
2258f0484fSRodney W. Grimes * without specific prior written permission.
2358f0484fSRodney W. Grimes *
2458f0484fSRodney W. Grimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
2558f0484fSRodney W. Grimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
2658f0484fSRodney W. Grimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2758f0484fSRodney W. Grimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
2858f0484fSRodney W. Grimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2958f0484fSRodney W. Grimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
3058f0484fSRodney W. Grimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
3158f0484fSRodney W. Grimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
3258f0484fSRodney W. Grimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
3358f0484fSRodney W. Grimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
3458f0484fSRodney W. Grimes * SUCH DAMAGE.
3558f0484fSRodney W. Grimes */
3658f0484fSRodney W. Grimes
3758f0484fSRodney W. Grimes #include <errno.h>
3858f0484fSRodney W. Grimes #include <stddef.h>
398a459911SBruce Evans #include <stdlib.h>
4058f0484fSRodney W. Grimes
4146cdc140SDavid Chisnall #ifdef I_AM_HEAPSORT_B
4246cdc140SDavid Chisnall #include "block_abi.h"
4346cdc140SDavid Chisnall #define COMPAR(x, y) CALL_BLOCK(compar, x, y)
44c8aeb6b4SDavid Chisnall typedef DECLARE_BLOCK(int, heapsort_block, const void *, const void *);
4546cdc140SDavid Chisnall #else
4646cdc140SDavid Chisnall #define COMPAR(x, y) compar(x, y)
4746cdc140SDavid Chisnall #endif
4846cdc140SDavid Chisnall
4958f0484fSRodney W. Grimes /*
5058f0484fSRodney W. Grimes * Swap two areas of size number of bytes. Although qsort(3) permits random
5158f0484fSRodney W. Grimes * blocks of memory to be sorted, sorting pointers is almost certainly the
5258f0484fSRodney W. Grimes * common case (and, were it not, could easily be made so). Regardless, it
5358f0484fSRodney W. Grimes * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
5458f0484fSRodney W. Grimes * arithmetic gets lost in the time required for comparison function calls.
5558f0484fSRodney W. Grimes */
5658f0484fSRodney W. Grimes #define SWAP(a, b, count, size, tmp) { \
5758f0484fSRodney W. Grimes count = size; \
5858f0484fSRodney W. Grimes do { \
5958f0484fSRodney W. Grimes tmp = *a; \
6058f0484fSRodney W. Grimes *a++ = *b; \
6158f0484fSRodney W. Grimes *b++ = tmp; \
6258f0484fSRodney W. Grimes } while (--count); \
6358f0484fSRodney W. Grimes }
6458f0484fSRodney W. Grimes
6558f0484fSRodney W. Grimes /* Copy one block of size size to another. */
6658f0484fSRodney W. Grimes #define COPY(a, b, count, size, tmp1, tmp2) { \
6758f0484fSRodney W. Grimes count = size; \
6858f0484fSRodney W. Grimes tmp1 = a; \
6958f0484fSRodney W. Grimes tmp2 = b; \
7058f0484fSRodney W. Grimes do { \
7158f0484fSRodney W. Grimes *tmp1++ = *tmp2++; \
7258f0484fSRodney W. Grimes } while (--count); \
7358f0484fSRodney W. Grimes }
7458f0484fSRodney W. Grimes
7558f0484fSRodney W. Grimes /*
7658f0484fSRodney W. Grimes * Build the list into a heap, where a heap is defined such that for
7758f0484fSRodney W. Grimes * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N.
7858f0484fSRodney W. Grimes *
7958f0484fSRodney W. Grimes * There two cases. If j == nmemb, select largest of Ki and Kj. If
8058f0484fSRodney W. Grimes * j < nmemb, select largest of Ki, Kj and Kj+1.
8158f0484fSRodney W. Grimes */
8258f0484fSRodney W. Grimes #define CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp) { \
8358f0484fSRodney W. Grimes for (par_i = initval; (child_i = par_i * 2) <= nmemb; \
8458f0484fSRodney W. Grimes par_i = child_i) { \
8558f0484fSRodney W. Grimes child = base + child_i * size; \
8646cdc140SDavid Chisnall if (child_i < nmemb && COMPAR(child, child + size) < 0) { \
8758f0484fSRodney W. Grimes child += size; \
8858f0484fSRodney W. Grimes ++child_i; \
8958f0484fSRodney W. Grimes } \
9058f0484fSRodney W. Grimes par = base + par_i * size; \
9146cdc140SDavid Chisnall if (COMPAR(child, par) <= 0) \
9258f0484fSRodney W. Grimes break; \
9358f0484fSRodney W. Grimes SWAP(par, child, count, size, tmp); \
9458f0484fSRodney W. Grimes } \
9558f0484fSRodney W. Grimes }
9658f0484fSRodney W. Grimes
9758f0484fSRodney W. Grimes /*
9858f0484fSRodney W. Grimes * Select the top of the heap and 'heapify'. Since by far the most expensive
9958f0484fSRodney W. Grimes * action is the call to the compar function, a considerable optimization
10058f0484fSRodney W. Grimes * in the average case can be achieved due to the fact that k, the displaced
10132223c1bSPedro F. Giffuni * elememt, is usually quite small, so it would be preferable to first
10258f0484fSRodney W. Grimes * heapify, always maintaining the invariant that the larger child is copied
10358f0484fSRodney W. Grimes * over its parent's record.
10458f0484fSRodney W. Grimes *
10558f0484fSRodney W. Grimes * Then, starting from the *bottom* of the heap, finding k's correct place,
10658f0484fSRodney W. Grimes * again maintianing the invariant. As a result of the invariant no element
10758f0484fSRodney W. Grimes * is 'lost' when k is assigned its correct place in the heap.
10858f0484fSRodney W. Grimes *
10958f0484fSRodney W. Grimes * The time savings from this optimization are on the order of 15-20% for the
11058f0484fSRodney W. Grimes * average case. See Knuth, Vol. 3, page 158, problem 18.
11158f0484fSRodney W. Grimes *
11258f0484fSRodney W. Grimes * XXX Don't break the #define SELECT line, below. Reiser cpp gets upset.
11358f0484fSRodney W. Grimes */
11458f0484fSRodney W. Grimes #define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) { \
11558f0484fSRodney W. Grimes for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \
11658f0484fSRodney W. Grimes child = base + child_i * size; \
11746cdc140SDavid Chisnall if (child_i < nmemb && COMPAR(child, child + size) < 0) { \
11858f0484fSRodney W. Grimes child += size; \
11958f0484fSRodney W. Grimes ++child_i; \
12058f0484fSRodney W. Grimes } \
12158f0484fSRodney W. Grimes par = base + par_i * size; \
12258f0484fSRodney W. Grimes COPY(par, child, count, size, tmp1, tmp2); \
12358f0484fSRodney W. Grimes } \
12458f0484fSRodney W. Grimes for (;;) { \
12558f0484fSRodney W. Grimes child_i = par_i; \
12658f0484fSRodney W. Grimes par_i = child_i / 2; \
12758f0484fSRodney W. Grimes child = base + child_i * size; \
12858f0484fSRodney W. Grimes par = base + par_i * size; \
12946cdc140SDavid Chisnall if (child_i == 1 || COMPAR(k, par) < 0) { \
13058f0484fSRodney W. Grimes COPY(child, k, count, size, tmp1, tmp2); \
13158f0484fSRodney W. Grimes break; \
13258f0484fSRodney W. Grimes } \
13358f0484fSRodney W. Grimes COPY(child, par, count, size, tmp1, tmp2); \
13458f0484fSRodney W. Grimes } \
13558f0484fSRodney W. Grimes }
13658f0484fSRodney W. Grimes
1378d3aa83dSCraig Rodrigues #ifdef I_AM_HEAPSORT_B
13848d59c22SCraig Rodrigues int heapsort_b(void *, size_t, size_t, heapsort_block);
1398d3aa83dSCraig Rodrigues #else
14048d59c22SCraig Rodrigues int heapsort(void *, size_t, size_t,
14148d59c22SCraig Rodrigues int (*)(const void *, const void *));
1428d3aa83dSCraig Rodrigues #endif
14358f0484fSRodney W. Grimes /*
14458f0484fSRodney W. Grimes * Heapsort -- Knuth, Vol. 3, page 145. Runs in O (N lg N), both average
14558f0484fSRodney W. Grimes * and worst. While heapsort is faster than the worst case of quicksort,
14658f0484fSRodney W. Grimes * the BSD quicksort does median selection so that the chance of finding
14758f0484fSRodney W. Grimes * a data set that will trigger the worst case is nonexistent. Heapsort's
14858f0484fSRodney W. Grimes * only advantage over quicksort is that it requires little additional memory.
14958f0484fSRodney W. Grimes */
15046cdc140SDavid Chisnall #ifdef I_AM_HEAPSORT_B
15146cdc140SDavid Chisnall int
heapsort_b(void * vbase,size_t nmemb,size_t size,heapsort_block compar)15276470dd5SCraig Rodrigues heapsort_b(void *vbase, size_t nmemb, size_t size, heapsort_block compar)
15346cdc140SDavid Chisnall #else
15458f0484fSRodney W. Grimes int
15576470dd5SCraig Rodrigues heapsort(void *vbase, size_t nmemb, size_t size,
15676470dd5SCraig Rodrigues int (*compar)(const void *, const void *))
15746cdc140SDavid Chisnall #endif
15858f0484fSRodney W. Grimes {
159badf97cdSDavid Schultz size_t cnt, i, j, l;
1608fb3f3f6SDavid E. O'Brien char tmp, *tmp1, *tmp2;
16158f0484fSRodney W. Grimes char *base, *k, *p, *t;
16258f0484fSRodney W. Grimes
16358f0484fSRodney W. Grimes if (nmemb <= 1)
16458f0484fSRodney W. Grimes return (0);
16558f0484fSRodney W. Grimes
16658f0484fSRodney W. Grimes if (!size) {
16758f0484fSRodney W. Grimes errno = EINVAL;
16858f0484fSRodney W. Grimes return (-1);
16958f0484fSRodney W. Grimes }
17058f0484fSRodney W. Grimes
17158f0484fSRodney W. Grimes if ((k = malloc(size)) == NULL)
17258f0484fSRodney W. Grimes return (-1);
17358f0484fSRodney W. Grimes
17458f0484fSRodney W. Grimes /*
17558f0484fSRodney W. Grimes * Items are numbered from 1 to nmemb, so offset from size bytes
17658f0484fSRodney W. Grimes * below the starting address.
17758f0484fSRodney W. Grimes */
17858f0484fSRodney W. Grimes base = (char *)vbase - size;
17958f0484fSRodney W. Grimes
18058f0484fSRodney W. Grimes for (l = nmemb / 2 + 1; --l;)
18158f0484fSRodney W. Grimes CREATE(l, nmemb, i, j, t, p, size, cnt, tmp);
18258f0484fSRodney W. Grimes
18358f0484fSRodney W. Grimes /*
18458f0484fSRodney W. Grimes * For each element of the heap, save the largest element into its
18558f0484fSRodney W. Grimes * final slot, save the displaced element (k), then recreate the
18658f0484fSRodney W. Grimes * heap.
18758f0484fSRodney W. Grimes */
18858f0484fSRodney W. Grimes while (nmemb > 1) {
18958f0484fSRodney W. Grimes COPY(k, base + nmemb * size, cnt, size, tmp1, tmp2);
19058f0484fSRodney W. Grimes COPY(base + nmemb * size, base + size, cnt, size, tmp1, tmp2);
19158f0484fSRodney W. Grimes --nmemb;
19258f0484fSRodney W. Grimes SELECT(i, j, nmemb, t, p, size, k, cnt, tmp1, tmp2);
19358f0484fSRodney W. Grimes }
19458f0484fSRodney W. Grimes free(k);
19558f0484fSRodney W. Grimes return (0);
19658f0484fSRodney W. Grimes }
197