vec.nx source
↩ module page · 104 lines · 2865 B
1// vec.nx -- dynamic-array of i64 (Phase G7 in the roadmap).
2//
3// Specialised to i64 for now; generics will generalise to Vec<T> once
4// parse.nx grows multi-param + full monomorphization support. That
5// migration is API-compatible: rename occurrences of i64 in element
6// positions only.
7//
8// Growth: geometric 2x on push (classical amortized O(1)). Backing
9// storage via sys_mmap; never freed (compiler run-once, servers
10// long-running will switch to a per-request arena later).
11//
12// No bounds-check-on-get to match kernel-code convention; call
13// vec_get only after checking vec_len.
14
15import "syscalls.nx"
16
17struct Vec {
18 data: *i64,
19 len: i64,
20 cap: i64,
21}
22
23// Build a Vec preallocated to `initial_cap` slots. Cap = 0 defers
24// allocation until first push.
25func vec_new(initial_cap: i64) -> *Vec {
26 let raw: *u8 = sys_mmap(64)
27 let v: *Vec = raw as *Vec
28 v.len = 0
29 v.cap = initial_cap
30 if initial_cap > 0 {
31 v.data = sys_mmap(initial_cap * 8 + 16) as *i64
32 } else {
33 v.data = 0 as *i64
34 }
35 return v
36}
37
38func vec_len(v: *Vec) -> i64 {
39 return v.len
40}
41
42// Read element at index i. Caller is responsible for 0 <= i < len.
43func vec_get(v: *Vec, i: i64) -> i64 {
44 return v.data[i]
45}
46
47// Overwrite element at index i.
48func vec_set(v: *Vec, i: i64, x: i64) -> i64 {
49 v.data[i] = x
50 return 0
51}
52
53// Grow cap (doubling or to at least `want` slots) by copying the
54// old data into a fresh allocation. mmap is page-sized anyway so
55// the waste is bounded.
56func vec_grow(v: *Vec, want: i64) -> i64 {
57 var new_cap: i64 = v.cap * 2
58 if new_cap < want { new_cap = want }
59 if new_cap < 8 { new_cap = 8 }
60 let nd: *i64 = sys_mmap(new_cap * 8 + 16) as *i64
61 var i: i64 = 0
62 while i < v.len {
63 nd[i] = v.data[i]
64 i = i + 1
65 }
66 v.data = nd
67 v.cap = new_cap
68 return 0
69}
70
71// Amortised O(1) push to the end.
72func vec_push(v: *Vec, x: i64) -> i64 {
73 if v.len >= v.cap {
74 vec_grow(v, v.len + 1)
75 }
76 v.data[v.len] = x
77 v.len = v.len + 1
78 return 0
79}
80
81// Pop the last element. Returns 0 and leaves len unchanged when empty
82// -- caller gates with vec_len to distinguish.
83func vec_pop(v: *Vec) -> i64 {
84 if v.len <= 0 { return 0 }
85 v.len = v.len - 1
86 return v.data[v.len]
87}
88
89// Truncate to length `n` (no-op if already shorter). Doesn't shrink
90// the backing buffer -- just resets the logical length.
91func vec_truncate(v: *Vec, n: i64) -> i64 {
92 if n < v.len { v.len = n }
93 return 0
94}
95
96// Linear search for `needle`. Returns first matching index or -1.
97func vec_index_of(v: *Vec, needle: i64) -> i64 {
98 var i: i64 = 0
99 while i < v.len {
100 if v.data[i] == needle { return i }
101 i = i + 1
102 }
103 return -1
104}