// SPDX-License-Identifier: MPL-2.0 // (c) Hare authors use math; use types; // Sorts a slice of items. This function provides a stable sort - relative order // of equal elements is preserved. // // In the event that [[sort]] returns nomem, the input is unchanged. export fn sort(items: []opaque, itemsz: size, cmp: *cmpfunc) (void | nomem) = { if (len(items) < 256) { insort(items, itemsz, cmp); return; }; powersort(items, itemsz, cmp)?; }; // Sorts a slice of items in place. This function provides a stable sort - // relative order of equal elements is preserved. // // The list is sorted in place, with no additional allocations. This is // inefficient for large lists (see [[sort]]), but has the advantage of never // returning nomem. export fn inplace(items: []opaque, itemsz: size, cmp: *cmpfunc) void = { return insort(items, itemsz, cmp); }; // Checks if all of the items in a slice are sorted. export fn sorted(items: []opaque, itemsz: size, cmp: *cmpfunc) bool = { let ba = items: *[*]u8; for (let i = 1z; i < len(items); i += 1) { if (cmp(&ba[(i - 1) * itemsz], &ba[i * itemsz]) > 0) { return false; }; }; return true; }; fn swap(a: *opaque, b: *opaque, sz: size) void = { let a = a: *[*]u8, b = b: *[*]u8; for (let i = 0z; i < sz; i += 1) { let c = a[i]; a[i] = b[i]; b[i] = c; }; }; // Finds the index of the rightmost value that is equal to key or, if such value // does not exist, less than key. fn search_rightmost( in: []opaque, sz: size, key: const *opaque, cmp: *cmpfunc, ) size = { let l = 0z; let r = len(in); let ba = in: *[*]u8; for (l < r) { let m = l + (r - l) / 2; if (cmp(key, &ba[m * sz]) < 0) { r = m; } else { l = m + 1; }; }; return r - 1; }; fn insort(items: []opaque, itemsz: size, cmp: *cmpfunc) void = { let ba = items: *[*]u8; for (let i = 0z; i < len(items); i += 1) { let bound = search_rightmost(items[..i], itemsz, &ba[i * itemsz], cmp); for (let j = i; j > bound + 1; j -= 1) { let a = &ba[(j - 1) * itemsz]; let b = &ba[j * itemsz]; swap(a, b, itemsz); }; }; }; // Based on paper "Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods // That Optimally Adapt to Existing Runs"; J. Ian Munro, Sebastian Wild // // https://arxiv.org/pdf/1805.04154.pdf def MINRUN: size = 24; // FIXME: needs tuning def EMPTY: size = -1z; // A run of non-decreasing elements on the interval [start; end). type run = struct { start: size, // Set to EMPTY when a run is merged end: size, }; fn powersort(items: []opaque, itemsz: size, cmp: *cmpfunc) (void | nomem) = { // npowers = floor(log2(n)) + 1 const npowers = math::bit_size(len(items)) + 1; const runs: []run = alloc([run { start = EMPTY, ... }...], npowers + 1)?; defer free(runs); let top = 0u8; const aux: []u8 = alloc([0...], len(items) * itemsz)?; defer free(aux); let a = run { start = 0z, end = extend(items, itemsz, cmp, 0), }; const length = a.end - a.start; if (length < MINRUN) { a.end = if (a.start + MINRUN < len(items)) a.start + MINRUN else len(items); insort(cut(items, itemsz, a.start, a.end), itemsz, cmp); }; for (a.end < len(items)) { let b = run { start = a.end, end = extend(items, itemsz, cmp, a.end), }; const length = b.end - b.start; if (length < MINRUN) { b.end = if (b.start + MINRUN < len(items)) b.start + MINRUN else len(items); insort(cut(items, itemsz, b.start, b.end), itemsz, cmp); }; const k = node_power(0, len(items), a.start, b.start, b.end); assert(k != top); for (let i = top; i > k; i -= 1) { if (runs[i].start == EMPTY) continue; merge(items, itemsz, cmp, aux, runs[i].start, runs[i].end, a.end); a.start = runs[i].start; runs[i].start = EMPTY; }; runs[k] = a; top = k; a = b; }; assert(a.end == len(items)); for (let i = top; i > 0; i -= 1) { if (runs[i].start == EMPTY) continue; merge(items, itemsz, cmp, aux, runs[i].start, runs[i].end, len(items)); }; }; // Returns 'end' such that [start; end) in 'items' is non-decreasing // // a[0] ≤ a[1] ≤ ... ≤ a[n - 1] - kept as-is // a[1] > a[1] > ... > a[n - 1] - reversed // // Note: reversing a sequence with equal elements will move their relative // locations, which is undesirable for a stable sort. fn extend(items: []opaque, itemsz: size, cmp: *cmpfunc, start: size) size = { const n = len(items); const items = (items: *[*]u8)[..len(items) * itemsz]; assert(n - start > 0, "Empty extension"); if (start + 1 == n) { return n; }; if (cmp(&items[start * itemsz], &items[(start + 1) * itemsz]) <= 0) { let end = start + 2; for (end < n && cmp(&items[(end - 1) * itemsz], &items[end * itemsz]) <= 0) { end += 1; }; return end; } else { let end = start + 2; for (end < n && cmp(&items[(end - 1) * itemsz], &items[end * itemsz]) > 0) { end += 1; }; reverse(cut(items, itemsz, start, end), itemsz); return end; }; }; fn reverse(items: []opaque, itemsz: size) void = { const n = len(items); const items = (items: *[*]u8)[..n * itemsz]; for (let i = 0z; i < n / 2; i += 1) { swap(&items[i * itemsz], &items[(n - i - 1) * itemsz], itemsz); }; }; fn merge( items: []opaque, itemsz: size, cmp: *cmpfunc, aux: []u8, l: size, m: size, r: size, ) void = { l *= itemsz; m *= itemsz; r *= itemsz; const items = items: *[*]u8; // Placing items at the beginning results in better cache performance // (probably) aux[..m - l] = items[l..m]; let i = 0z, j = m, out = l; for (i < m - l && j < r; out += itemsz) { if (cmp(&aux[i], &items[j]) < 0) { items[out..out + itemsz] = aux[i..i + itemsz]; i += itemsz; } else { items[out..out + itemsz] = items[j..j + itemsz]; j += itemsz; }; }; if (i < m - l) { const sz = (m - l) - i; items[out..out + sz] = aux[i..i + sz]; out += sz; }; if (j < r) { const sz = r - j; items[out..out + sz] = items[j..j + sz]; out += sz; }; }; fn cut(items: []opaque, itemsz: size, l: size, r: size) []opaque = { return *(&types::slice { data = &(items: *[*]u8)[l * itemsz], length = r - l, capacity = 0, }: *[]opaque); }; fn node_power(left: size, right: size, start_a: size, start_b: size, end_b: size) u8 = { const n: u64 = right - left; const l: u64 = start_a + start_b - 2 * left; const r: u64 = start_b + end_b - 2 * left; const a = ((l << 30) / n): u32; const b = ((r << 30) / n): u32; return math::leading_zeros_u32(a ^ b); };