| 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 |
}; |