1/*-
2 * Copyright (c) 1992, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 4. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 *
29 * Attribution:
30 * Derived from the 4.4BSD-Lite / FreeBSD C library (CSRG, UC Berkeley):
31 * - lib/libc/stdlib/heapsort.c by Peter McIlroy (1992, 1993)
32 * - lib/libc/stdlib/qsort.c by Jon L. Bentley and M. Douglas McIlroy (1993)
33 *
34 * Refactored for kernel usage:
35 * - Allocation-free in-place heapsort (0 heap allocations, safe in atomic/IRQ
36 * contexts)
37 * - Guaranteed O(1) auxiliary stack space (non-recursive)
38 * - Architecture-optimized word-aligned swap routines
39 */
40
41#include <math/sort.h>
42#include <stdbool.h>
43#include <stddef.h>
44#include <stdint.h>
45
46#define swapcode(TYPE, parmi, parmj, n) \
47 { \
48 size_t i = (n) / sizeof(TYPE); \
49 TYPE *pi = (TYPE *) (parmi); \
50 TYPE *pj = (TYPE *) (parmj); \
51 do { \
52 TYPE t = *pi; \
53 *pi++ = *pj; \
54 *pj++ = t; \
55 } while (--i > 0); \
56 }
57
58#define SWAPINIT(a, es) \
59 swaptype = ((uintptr_t) (a) % sizeof(long) || (es) % sizeof(long)) ? 2 \
60 : (es) == sizeof(long) ? 0 \
61 : 1;
62
63static inline void swapfunc(char *a, char *b, size_t n, size_t swaptype) {
64 if (swaptype == 0) {
65 long t = *(long *) (void *) (a);
66 *(long *) (void *) (a) = *(long *) (void *) (b);
67 *(long *) (void *) (b) = t;
68 } else if (swaptype == 1) {
69 swapcode(long, (void *) a, (void *) b, n);
70 } else {
71 swapcode(char, a, b, n);
72 }
73}
74
75/*
76 * Sift-down operation on a 0-indexed binary max-heap.
77 * Pushes base[root] down into its correct position to restore the heap.
78 */
79static void sift_down(char *base, size_t root, size_t n, size_t size,
80 cmp_t *compar, size_t swaptype) {
81 size_t child;
82 while ((child = 2 * root + 1) < n) {
83 /* If right child exists and is greater than left child, select right
84 * child */
85 if (child + 1 < n &&
86 compar(base + (child + 1) * size, base + child * size) > 0) {
87 child++;
88 }
89
90 /* If the largest child is greater than the parent, swap and descend */
91 if (compar(base + child * size, base + root * size) > 0) {
92 swapfunc(a: base + root * size, b: base + child * size, n: size, swaptype);
93 root = child;
94 } else {
95 break;
96 }
97 }
98}
99
100/*
101 * In-place heapsort implementation:
102 * - Time complexity: O(n log n) best, average, and worst-case
103 * - Auxiliary space: O(1) stack space, 0 dynamic memory allocations
104 */
105int heapsort(void *vbase, size_t nmemb, size_t size, cmp_t *compar) {
106 char *base = (char *) vbase;
107 size_t swaptype;
108
109 if (!base || nmemb <= 1) {
110 return 0;
111 }
112
113 if (size == 0) {
114 return -1;
115 }
116
117 SWAPINIT(base, size);
118
119 for (size_t i = nmemb / 2; i > 0; i--) {
120 sift_down(base, root: i - 1, n: nmemb, size, compar, swaptype);
121 }
122
123 for (size_t i = nmemb - 1; i > 0; i--) {
124 swapfunc(a: base, b: base + i * size, n: size, swaptype);
125 sift_down(base, root: 0, n: i, size, compar, swaptype);
126 }
127
128 return 0;
129}
130
131void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
132 cmp_t *compar) {
133 if (!key || !base || size == 0) {
134 return NULL;
135 }
136
137 size_t l = 0;
138 size_t r = nmemb;
139
140 while (l < r) {
141 size_t mid = l + (r - l) / 2;
142 const void *elem = (const char *) base + mid * size;
143 int cmp = compar(key, elem);
144
145 if (cmp < 0) {
146 r = mid;
147 } else if (cmp > 0) {
148 l = mid + 1;
149 } else {
150 return (void *) elem;
151 }
152 }
153
154 return NULL;
155}
156