nx_qsort.nx source
↩ module page · 184 lines · 5704 B
1// nx_qsort.nx -- in-place quicksort for i64 arrays + a generic
2// indirect variant that takes a comparator function pointer.
3//
4// Used by:
5// - nx_link / nx_objdump / nx_nm: sort symbols by address or name.
6// - nx_dwarf_line: sort PC ranges before emitting the line program.
7// - nx_audit / nx_metrics: sort scores for top-N reporting.
8//
9// Today most NishiLang call sites do bubble-sort or insertion-sort
10// inline, which is fine for tiny arrays but quadratic above ~50
11// elements. This module gives O(n log n) average + O(log n) stack.
12//
13// Implementation notes:
14// - Lomuto partition (simpler than Hoare; the constant-factor
15// difference doesn't matter when symbol counts are < 100k).
16// - Recursion bound = log2(n) + small constant; for n = 1M, that
17// is ~20 frames -- fits even a tiny call stack.
18// - When n <= 16 we fall back to insertion sort (lower overhead
19// for small arrays; classic optimisation).
20
21// nx_safety_envelope:
22// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
23// sil_target: SIL1
24// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
25// verdict: NOT_YET_EVALUATED
26
27import "syscalls.nx"
28
29// Insertion-sort cutoff: below this, quicksort delegates here.
30const NX_QSORT_INSERTION_CUTOFF: i64 = 16
31
32// ---- i64 specialisation ------------------------------------------
33
34func nx_qsort_swap_i64(a: *i64, i: i64, j: i64) -> i64 {
35 let t: i64 = a[i]
36 a[i] = a[j]
37 a[j] = t
38 return 0
39}
40
41func nx_qsort_insertion_i64(a: *i64, lo: i64, hi: i64) -> i64 {
42 var i: i64 = lo + 1
43 while i <= hi {
44 let key: i64 = a[i]
45 var j: i64 = i - 1
46 var done: i64 = 0
47 while done == 0 {
48 if j < lo { done = 1 }
49 else {
50 if a[j] > key {
51 a[j + 1] = a[j]
52 j = j - 1
53 } else { done = 1 }
54 }
55 }
56 a[j + 1] = key
57 i = i + 1
58 }
59 return 0
60}
61
62func nx_qsort_partition_i64(a: *i64, lo: i64, hi: i64) -> i64 {
63 // Median-of-three pivot for better behaviour on sorted inputs.
64 let mid: i64 = lo + (hi - lo) / 2
65 if a[lo] > a[mid] { nx_qsort_swap_i64(a, lo, mid) }
66 if a[lo] > a[hi] { nx_qsort_swap_i64(a, lo, hi) }
67 if a[mid] > a[hi] { nx_qsort_swap_i64(a, mid, hi) }
68 nx_qsort_swap_i64(a, mid, hi - 1)
69 let pivot: i64 = a[hi - 1]
70 var i: i64 = lo
71 var j: i64 = hi - 1
72 var done: i64 = 0
73 while done == 0 {
74 i = i + 1
75 var inner: i64 = 0
76 while inner == 0 {
77 if a[i] < pivot { i = i + 1 } else { inner = 1 }
78 }
79 j = j - 1
80 var inner2: i64 = 0
81 while inner2 == 0 {
82 if j > lo {
83 if a[j] > pivot { j = j - 1 } else { inner2 = 1 }
84 } else { inner2 = 1 }
85 }
86 if i >= j { done = 1 }
87 else { nx_qsort_swap_i64(a, i, j) }
88 }
89 nx_qsort_swap_i64(a, i, hi - 1)
90 return i
91}
92
93func nx_qsort_i64_range(a: *i64, lo: i64, hi: i64) -> i64 {
94 if hi <= lo { return 0 }
95 if hi - lo + 1 <= NX_QSORT_INSERTION_CUTOFF {
96 return nx_qsort_insertion_i64(a, lo, hi)
97 }
98 let p: i64 = nx_qsort_partition_i64(a, lo, hi)
99 nx_qsort_i64_range(a, lo, p - 1)
100 nx_qsort_i64_range(a, p + 1, hi)
101 return 0
102}
103
104// Sort `a[0..n]` in ascending order.
105func nx_qsort_i64(a: *i64, n: i64) -> i64 {
106 if n < 2 { return 0 }
107 return nx_qsort_i64_range(a, 0, n - 1)
108}
109
110// Generic indirect sort with a comparator function pointer is
111// deferred -- nxc2 does not yet support func-as-arg type syntax.
112// Once it does, add nx_qsort_idx that takes (ctx, i, j) -> cmp.
113
114// ---- self-test ---------------------------------------------------
115
116func main() -> i64 {
117 let n: i64 = 32
118 let raw: *u8 = sys_mmap(n * 8)
119 let a: *i64 = raw as *i64
120
121 // Build a deterministic shuffle: 0,29,2,27,4,...
122 var i: i64 = 0
123 while i < n {
124 if (i & 1) == 0 { a[i] = i }
125 else { a[i] = n - 1 - i }
126 i = i + 1
127 }
128
129 nx_qsort_i64(a, n)
130
131 // Verify ascending.
132 var k: i64 = 1
133 while k < n {
134 if a[k] < a[k - 1] {
135 return __syscall(93, 1, 0, 0, 0, 0, 0)
136 }
137 k = k + 1
138 }
139
140 // Verify identity (every value 0..n-1 still present, exactly once).
141 let seen_raw: *u8 = sys_mmap(n)
142 var s: i64 = 0
143 while s < n { seen_raw[s] = 0; s = s + 1 }
144 var t: i64 = 0
145 while t < n {
146 if a[t] < 0 { return __syscall(93, 2, 0, 0, 0, 0, 0) }
147 if a[t] >= n { return __syscall(93, 3, 0, 0, 0, 0, 0) }
148 if seen_raw[a[t]] != 0 { return __syscall(93, 4, 0, 0, 0, 0, 0) }
149 seen_raw[a[t]] = 1
150 t = t + 1
151 }
152
153 // Insertion-sort path: tiny array.
154 let small_raw: *u8 = sys_mmap(4 * 8)
155 let small: *i64 = small_raw as *i64
156 small[0] = 4; small[1] = 1; small[2] = 3; small[3] = 2
157 nx_qsort_i64(small, 4)
158 if small[0] != 1 { return __syscall(93, 5, 0, 0, 0, 0, 0) }
159 if small[1] != 2 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
160 if small[2] != 3 { return __syscall(93, 7, 0, 0, 0, 0, 0) }
161 if small[3] != 4 { return __syscall(93, 8, 0, 0, 0, 0, 0) }
162
163 // Already-sorted case (median-of-three should not pathologise).
164 var u: i64 = 0
165 while u < n { a[u] = u; u = u + 1 }
166 nx_qsort_i64(a, n)
167 var v: i64 = 0
168 while v < n {
169 if a[v] != v { return __syscall(93, 9, 0, 0, 0, 0, 0) }
170 v = v + 1
171 }
172
173 // Reverse-sorted case.
174 var w: i64 = 0
175 while w < n { a[w] = n - 1 - w; w = w + 1 }
176 nx_qsort_i64(a, n)
177 var x: i64 = 0
178 while x < n {
179 if a[x] != x { return __syscall(93, 10, 0, 0, 0, 0, 0) }
180 x = x + 1
181 }
182
183 return 0
184}