Debian Codegraph @

sort/sort.ha

raw
1 // SPDX-License-Identifier: MPL-2.0
2 // (c) Hare authors <https://harelang.org>
3
4 use math;
5 use types;
6
7 // Sorts a slice of items. This function provides a stable sort - relative order
8 // of equal elements is preserved.
9 //
10 // In the event that [[sort]] returns nomem, the input is unchanged.
11 export fn sort(items: []opaque, itemsz: size, cmp: *cmpfunc) (void | nomem) = {
12 if (len(items) < 256) {
13 insort(items, itemsz, cmp);
14 return;
15 };
16 powersort(items, itemsz, cmp)?;
17 };
18
19 // Sorts a slice of items in place. This function provides a stable sort -
20 // relative order of equal elements is preserved.
21 //
22 // The list is sorted in place, with no additional allocations. This is
23 // inefficient for large lists (see [[sort]]), but has the advantage of never
24 // returning nomem.
25 export fn inplace(items: []opaque, itemsz: size, cmp: *cmpfunc) void = {
26 return insort(items, itemsz, cmp);
27 };
28
29 // Checks if all of the items in a slice are sorted.
30 export fn sorted(items: []opaque, itemsz: size, cmp: *cmpfunc) bool = {
31 let ba = items: *[*]u8;
32 for (let i = 1z; i < len(items); i += 1) {
33 if (cmp(&ba[(i - 1) * itemsz], &ba[i * itemsz]) > 0) {
34 return false;
35 };
36 };
37 return true;
38 };
39
40 fn swap(a: *opaque, b: *opaque, sz: size) void = {
41 let a = a: *[*]u8, b = b: *[*]u8;
42 for (let i = 0z; i < sz; i += 1) {
43 let c = a[i];
44 a[i] = b[i];
45 b[i] = c;
46 };
47 };
48
49 // Finds the index of the rightmost value that is equal to key or, if such value
50 // does not exist, less than key.
51 fn search_rightmost(
52 in: []opaque,
53 sz: size,
54 key: const *opaque,
55 cmp: *cmpfunc,
56 ) size = {
57 let l = 0z;
58 let r = len(in);
59 let ba = in: *[*]u8;
60 for (l < r) {
61 let m = l + (r - l) / 2;
62 if (cmp(key, &ba[m * sz]) < 0) {
63 r = m;
64 } else {
65 l = m + 1;
66 };
67 };
68 return r - 1;
69 };
70
71 fn insort(items: []opaque, itemsz: size, cmp: *cmpfunc) void = {
72 let ba = items: *[*]u8;
73 for (let i = 0z; i < len(items); i += 1) {
74 let bound = search_rightmost(items[..i], itemsz,
75 &ba[i * itemsz], cmp);
76 for (let j = i; j > bound + 1; j -= 1) {
77 let a = &ba[(j - 1) * itemsz];
78 let b = &ba[j * itemsz];
79 swap(a, b, itemsz);
80 };
81 };
82 };
83
84 // Based on paper "Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods
85 // That Optimally Adapt to Existing Runs"; J. Ian Munro, Sebastian Wild
86 //
87 // https://arxiv.org/pdf/1805.04154.pdf
88
89 def MINRUN: size = 24; // FIXME: needs tuning
90 def EMPTY: size = -1z;
91
92 // A run of non-decreasing elements on the interval [start; end).
93 type run = struct {
94 start: size, // Set to EMPTY when a run is merged
95 end: size,
96 };
97
98 fn powersort(items: []opaque, itemsz: size, cmp: *cmpfunc) (void | nomem) = {
99 // npowers = floor(log2(n)) + 1
100 const npowers = math::bit_size(len(items)) + 1;
101 const runs: []run = alloc([run { start = EMPTY, ... }...], npowers + 1)?;
102 defer free(runs);
103 let top = 0u8;
104
105 const aux: []u8 = alloc([0...], len(items) * itemsz)?;
106 defer free(aux);
107
108 let a = run {
109 start = 0z,
110 end = extend(items, itemsz, cmp, 0),
111 };
112 const length = a.end - a.start;
113 if (length < MINRUN) {
114 a.end = if (a.start + MINRUN < len(items))
115 a.start + MINRUN else len(items);
116 insort(cut(items, itemsz, a.start, a.end), itemsz, cmp);
117 };
118 for (a.end < len(items)) {
119 let b = run {
120 start = a.end,
121 end = extend(items, itemsz, cmp, a.end),
122 };
123 const length = b.end - b.start;
124 if (length < MINRUN) {
125 b.end = if (b.start + MINRUN < len(items))
126 b.start + MINRUN else len(items);
127 insort(cut(items, itemsz, b.start, b.end), itemsz, cmp);
128 };
129 const k = node_power(0, len(items), a.start, b.start, b.end);
130 assert(k != top);
131 for (let i = top; i > k; i -= 1) {
132 if (runs[i].start == EMPTY) continue;
133 merge(items, itemsz, cmp, aux,
134 runs[i].start, runs[i].end, a.end);
135
136 a.start = runs[i].start;
137 runs[i].start = EMPTY;
138 };
139 runs[k] = a;
140 top = k;
141
142 a = b;
143 };
144 assert(a.end == len(items));
145 for (let i = top; i > 0; i -= 1) {
146 if (runs[i].start == EMPTY) continue;
147 merge(items, itemsz, cmp, aux,
148 runs[i].start, runs[i].end, len(items));
149 };
150 };
151
152 // Returns 'end' such that [start; end) in 'items' is non-decreasing
153 //
154 // a[0] ≤ a[1] ≤ ... ≤ a[n - 1] - kept as-is
155 // a[1] > a[1] > ... > a[n - 1] - reversed
156 //
157 // Note: reversing a sequence with equal elements will move their relative
158 // locations, which is undesirable for a stable sort.
159 fn extend(items: []opaque, itemsz: size, cmp: *cmpfunc, start: size) size = {
160 const n = len(items);
161 const items = (items: *[*]u8)[..len(items) * itemsz];
162
163 assert(n - start > 0, "Empty extension");
164 if (start + 1 == n) {
165 return n;
166 };
167
168 if (cmp(&items[start * itemsz], &items[(start + 1) * itemsz]) <= 0) {
169 let end = start + 2;
170 for (end < n && cmp(&items[(end - 1) * itemsz], &items[end * itemsz]) <= 0) {
171 end += 1;
172 };
173 return end;
174 } else {
175 let end = start + 2;
176 for (end < n && cmp(&items[(end - 1) * itemsz], &items[end * itemsz]) > 0) {
177 end += 1;
178 };
179 reverse(cut(items, itemsz, start, end), itemsz);
180 return end;
181 };
182 };
183
184 fn reverse(items: []opaque, itemsz: size) void = {
185 const n = len(items);
186 const items = (items: *[*]u8)[..n * itemsz];
187 for (let i = 0z; i < n / 2; i += 1) {
188 swap(&items[i * itemsz], &items[(n - i - 1) * itemsz], itemsz);
189 };
190 };
191
192 fn merge(
193 items: []opaque,
194 itemsz: size,
195 cmp: *cmpfunc,
196 aux: []u8,
197 l: size,
198 m: size,
199 r: size,
200 ) void = {
201 l *= itemsz;
202 m *= itemsz;
203 r *= itemsz;
204
205 const items = items: *[*]u8;
206 // Placing items at the beginning results in better cache performance
207 // (probably)
208 aux[..m - l] = items[l..m];
209
210 let i = 0z, j = m, out = l;
211 for (i < m - l && j < r; out += itemsz) {
212 if (cmp(&aux[i], &items[j]) < 0) {
213 items[out..out + itemsz] = aux[i..i + itemsz];
214 i += itemsz;
215 } else {
216 items[out..out + itemsz] = items[j..j + itemsz];
217 j += itemsz;
218 };
219 };
220 if (i < m - l) {
221 const sz = (m - l) - i;
222 items[out..out + sz] = aux[i..i + sz];
223 out += sz;
224 };
225 if (j < r) {
226 const sz = r - j;
227 items[out..out + sz] = items[j..j + sz];
228 out += sz;
229 };
230 };
231
232 fn cut(items: []opaque, itemsz: size, l: size, r: size) []opaque = {
233 return *(&types::slice {
234 data = &(items: *[*]u8)[l * itemsz],
235 length = r - l,
236 capacity = 0,
237 }: *[]opaque);
238 };
239
240 fn node_power(left: size, right: size, start_a: size, start_b: size, end_b: size) u8 = {
241 const n: u64 = right - left;
242 const l: u64 = start_a + start_b - 2 * left;
243 const r: u64 = start_b + end_b - 2 * left;
244 const a = ((l << 30) / n): u32;
245 const b = ((r << 30) / n): u32;
246 return math::leading_zeros_u32(a ^ b);
247 };