1-- A vector with a private initialized inline prefix. Unused inline slots
2-- have no readable item image. The spill descriptor remains empty until
3-- the first growth allocation.
4
5import core/mem
6import core/vec
7
8small_value: type (item: type, fixed inline_slots: u32) = struct
9 count: usize
10 inline_values: [inline_slots]item
11 spill: vec.list(item)
12 spilled: bool
13end small_value
14
15--- Vector with an inline prefix and allocator-backed spill storage. Only
16--- initialized slots are readable; the item type must conform to `zeroable`.
17public small: type (item: type is zeroable, fixed inline_slots: u32) = struct
18 storage: small_value(item, inline_slots)
19end small
20
21--- Create an empty inline vector without allocating. Unused inline slots have
22--- no readable item value.
23public new: (item: type is zeroable, fixed inline_slots: u32)
24 -> (value: small(item, inline_slots)) =
25 fresh := vec.new(item: item)
26 value = (storage: (count: 0, inline_values: uninit,
27 spill: fresh, spilled: false))
28end new
29
30--- Return the initialized item count without copying inline storage.
31---
32--- A read-only pointer accepts addresses of mutable and immutable containers
33--- without copying their inline storage.
34public length: (item: type is zeroable, fixed inline_slots: u32,
35 value: ptr small(item, inline_slots)) -> (count: usize) =
36 count = value.val.storage.count
37end length
38
39--- Return the inline capacity before spilling, or the backing vector capacity
40--- afterwards.
41public capacity: (item: type is zeroable, fixed inline_slots: u32,
42 value: ptr small(item, inline_slots)) -> (count: usize) =
43 if value.val.storage.spilled then
44 count = vec.capacity(value.val.storage.spill)
45 else
46 count = usize(inline_slots)
47 end if
48end capacity
49
50first_capacity: (fixed inline_slots: u32)
51 -> (count: usize) ! mem.out_of_memory =
52 current: usize = usize(inline_slots)
53 if current == 0 then
54 count = 8
55 return
56 end if
57 maximum: usize = 0 -% 1
58 fail mem.out_of_memory when current > maximum / 2
59 count = current * 2
60end first_capacity
61
62pop_list: (item: type is zeroable, inout values: vec.list(item))
63 -> (removed: item from values) ! mem.empty =
64 removed = vec.pop(values) else (problem)
65 _ = problem
66 fail mem.empty
67 end
68end pop_list
69
70--- Append inline while room remains, then spill to allocated storage.
71--- Allocation failure leaves the vector unchanged. Growth or the first spill
72--- invalidates old item views.
73public push: (item: type is zeroable, fixed inline_slots: u32,
74 provider: type is mem.allocator,
75 escaping inout value: small(item, inline_slots),
76 inout state: provider, escaping added: item)
77 -> none ! mem.out_of_memory =
78 if value.storage.spilled then
79 try vec.push(value.storage.spill, state, added)
80 inc value.storage.count
81 return
82 end if
83 if value.storage.count < usize(inline_slots) then
84 value.storage.inline_values[value.storage.count] = added
85 inc value.storage.count
86 return
87 end if
88
89 wanted: usize = try first_capacity(inline_slots: inline_slots)
90 mut fresh := vec.new(item: item)
91 try vec.reserve(fresh, state, wanted)
92
93 mut at: usize = 0
94 while at < value.storage.count do
95 -- Only the prefix has an item image. Reserve established room for
96 -- every one of these pushes without another allocation.
97 copied: item = value.storage.inline_values[at]
98 try vec.push(fresh, state, copied)
99 inc at
100 end while
101 try vec.push(fresh, state, added)
102
103 value.storage.spill = fresh
104 value.storage.spilled = true
105 inc value.storage.count
106end push
107
108--- Lend the initialized mutable prefix from inline or spill storage. The
109--- container and its backing must remain valid for the view's lifetime.
110public used: (item: type is zeroable, fixed inline_slots: u32,
111 inout value: small(item, inline_slots))
112 -> (view: []mut item from value) =
113 if value.storage.spilled then
114 view = vec.used(value.storage.spill)
115 else
116 view = value.storage.inline_values[0..<value.storage.count]
117 end if
118end used
119
120--- Copy the indexed item without copying the container. Reports
121--- `mem.out_of_bounds` outside its initialized prefix.
122public get: (item: type is zeroable, fixed inline_slots: u32,
123 value: ptr small(item, inline_slots), index: usize)
124 -> (result: item from value) ! mem.out_of_bounds =
125 if value.val.storage.spilled then
126 result = (vec.get(value.val.storage.spill, index) else (problem)
127 _ = problem
128 fail mem.out_of_bounds
129 end)
130 else
131 fail mem.out_of_bounds when index >= value.val.storage.count
132 result = value.val.storage.inline_values[index]
133 end if
134end get
135
136--- Lend a writable item pointer. Reports `mem.out_of_bounds` before forming
137--- an invalid pointer; end the pointer before a push or release.
138---
139--- A writable slot, with the same binding lock as vec.at [0800].
140public at: (item: type is zeroable, fixed inline_slots: u32,
141 inout value: small(item, inline_slots), index: usize)
142 -> (slot: ptr mut item from value) ! mem.out_of_bounds =
143 view: []mut item = used(value)
144 fail mem.out_of_bounds when index >= lenof view
145 slot = addr view[index]
146end at
147
148--- Remove and return the last item, retaining spill capacity. Reports
149--- `mem.empty` when empty; popping does not switch back to inline storage.
150public pop: (item: type is zeroable, fixed inline_slots: u32,
151 inout value: small(item, inline_slots))
152 -> (removed: item from value) ! mem.empty =
153 fail mem.empty when value.storage.count == 0
154 if value.storage.spilled then
155 removed = try pop_list(value.storage.spill)
156 dec value.storage.count
157 else
158 dec value.storage.count
159 removed = value.storage.inline_values[value.storage.count]
160 end if
161end pop
162
163--- Free any spill allocation through its original provider and reset to an
164--- empty inline vector. Does not clean up resources referenced by items.
165public release: (item: type is zeroable, fixed inline_slots: u32,
166 provider: type is mem.allocator,
167 inout value: small(item, inline_slots),
168 inout state: provider) -> none =
169 if value.storage.spilled then
170 vec.release(value.storage.spill, state)
171 end if
172 value.storage.count = 0
173 value.storage.spilled = false
174end release