1import core/mem
2
3--- Growable contiguous list with explicit allocator arguments. Its public
4--- shape contains opaque typed storage; no allocator is stored in the list.
5---
6--- The list shape is public as in prototype 3, but its `values` field has the
7--- opaque mem.storage(item) type: clients can inspect the container shape
8--- without reaching raw-storage counters or bytes.
9public list: type (item: type) = struct
10 values: mem.storage(item)
11end list
12
13--- Create an empty list without allocating. Supply the allocator when growing
14--- or releasing it.
15public new: (item: type) -> (result: list(item)) =
16 store := mem.empty_storage(item: item)
17 result = (values: store)
18end new
19
20--- Return the number of initialized items.
21public length: (item: type, value: list(item)) -> (count: usize) =
22 count = mem.initialized(value.values)
23end length
24
25--- Return the number of items that fit without further growth.
26public capacity: (item: type, value: list(item)) -> (count: usize) =
27 count = mem.capacity(value.values)
28end capacity
29
30copy_zero_prefix: (item: type, source: mem.storage(item),
31 inout target: mem.storage(item), count: usize)
32 -> (ok: bool) =
33 mem.transfer_zero_prefix(source, target, count) else (problem)
34 _ = problem
35 ok = false
36 return
37 end
38 ok = true
39end copy_zero_prefix
40
41copy_prefix: (item: type, source: mem.storage(item),
42 inout target: mem.storage(item), count: usize)
43 -> (ok: bool) =
44 if sizeof item == 0 then
45 ok = copy_zero_prefix(source, target, count)
46 return
47 end if
48
49 mut at: usize = 0
50 while at < count do
51 admitted: usize = mem.transfer(source, at, target) else (problem)
52 _ = problem
53 ok = false
54 return
55 end
56 _ = admitted
57 inc at
58 end while
59 ok = true
60end copy_prefix
61
62drain_zero: (item: type, inout value: mem.storage(item)) -> none =
63 mem.drain_zero_prefix(value) else (problem)
64 _ = problem
65 end
66end drain_zero
67
68drain: (item: type, inout value: mem.storage(item)) -> none =
69 if sizeof item == 0 then
70 drain_zero(value)
71 return
72 end if
73
74 while mem.initialized(value) > 0 do
75 discarded: item = mem.withdraw(value) else (problem)
76 -- D151 makes this unreachable after the positive initialized
77 -- query. It is an internal raw-state defect, not allocation
78 -- pressure, so do not manufacture out_of_memory here.
79 _ = problem
80 return
81 end
82 end while
83end drain
84
85byte_extent: (item: type, slots: usize)
86 -> (extent: usize) ! mem.out_of_memory =
87 item_size: usize = sizeof item
88 if item_size == 0 then
89 -- A zero-sized item still has logical slots. A nonempty capacity
90 -- acquires and eventually frees one zero-byte provider extent.
91 extent = 0
92 return
93 end if
94
95 maximum: usize = 0 -% 1
96 fail mem.out_of_memory when slots > maximum / item_size
97 extent = slots * item_size
98end byte_extent
99
100next_growth: (capacity: usize) -> (next: usize) ! mem.out_of_memory =
101 next = grown(capacity) else (problem)
102 _ = problem
103 fail mem.out_of_memory
104 end
105end next_growth
106
107free_empty: (item: type, provider: type is mem.allocator,
108 inout value: mem.storage(item), inout state: provider) -> none =
109 slots: usize = mem.capacity(value)
110 return when slots == 0
111 -- Every capacity published by vec passed byte_extent before reserve, so
112 -- this product is an internal vector invariant rather than a second
113 -- fallible allocation request.
114 extent: usize = slots * sizeof item
115 block: ptr mut u8 = mem.dispose(value) else (problem)
116 _ = problem
117 return
118 end
119 provider.free(state, block, extent)
120end free_empty
121
122--- Ensure room for at least `want` items. May grow backing in place or copy
123--- to a replacement. Failure preserves the old length, capacity and values;
124--- successful relocation invalidates old views. Use the original provider for
125--- existing backing.
126public reserve: (item: type, provider: type is mem.allocator,
127 inout value: list(item), inout state: provider, want: usize)
128 -> none ! mem.out_of_memory =
129 old_count: usize = mem.initialized(value.values)
130 old_capacity: usize = mem.capacity(value.values)
131 return when want <= old_capacity
132
133 extent: usize = try byte_extent(item: item, slots: want)
134 old_extent: usize = old_capacity * sizeof item
135 if mem.grow_storage(value.values, state, old_extent, extent, want) then
136 return
137 end if
138 block: ptr mut u8 = try provider.alloc
139 (state, extent, alignof item)
140 mut fresh := mem.reserve(item: item, base: block, slots: want)
141 copied: bool = copy_prefix(value.values, fresh, old_count)
142 if not copied then
143 -- Given D151's private counters, want > old_capacity and an empty
144 -- replacement, transfer cannot reject this prefix. Keep the
145 -- established rollback and public outcome if that internal
146 -- invariant is ever violated; it is not evidence of provider OOM.
147 drain(fresh)
148 free_empty(fresh, state)
149 fail mem.out_of_memory
150 end if
151
152 drain(value.values)
153 free_empty(value.values, state)
154 value.values = fresh
155end reserve
156
157--- Append a value, growing capacity when needed. Reports `mem.out_of_memory`
158--- without appending on allocation failure. Successful growth may invalidate
159--- views into the previous allocation.
160public push: (item: type, provider: type is mem.allocator,
161 inout value: list(item), inout state: provider,
162 escaping added: item) -> none ! mem.out_of_memory =
163 if length(value) == capacity(value) then
164 next: usize = try next_growth(capacity(value))
165 try reserve(value, state, next)
166 end if
167 admitted: usize = mem.admit(value.values, added) else (problem)
168 -- After successful growth or a spare-slot check, raw_full would
169 -- indicate an internal invariant defect. Retain the established
170 -- public fallback without claiming the provider exhausted memory.
171 _ = problem
172 fail mem.out_of_memory
173 end
174 _ = admitted
175end push
176
177--- Copy the indexed item, preserving origins of references it contains.
178--- Reports `mem.out_of_bounds` outside the initialized prefix.
179public get: (item: type, value: list(item), at: usize)
180 -> (result: item from value) ! mem.out_of_bounds =
181 result = mem.get(value.values, at) else (problem)
182 _ = problem
183 fail mem.out_of_bounds
184 end
185end get
186
187--- Lend a writable pointer to an indexed item. Reports `mem.out_of_bounds`
188--- for a missing slot; end the pointer's lifetime before growing or releasing
189--- the list.
190---
191--- A writable slot for in-place update. While the result lives the list
192--- binding may not be passed inout or sink [0800]: bind it, update through
193--- it, and let it end before the next push, reserve or release.
194public at: (item: type, inout value: list(item), index: usize)
195 -> (slot: ptr mut item from value) ! mem.out_of_bounds =
196 view: []mut item = mem.used(value.values)
197 fail mem.out_of_bounds when index >= lenof view
198 slot = addr view[index]
199end at
200
201--- Copy the last item without removing it. Reports `mem.empty` for an empty
202--- list.
203public last: (item: type, value: list(item))
204 -> (result: item from value) ! mem.empty =
205 count: usize = length(value)
206 fail mem.empty when count == 0
207 result = mem.get(value.values, count - 1) else (problem)
208 _ = problem
209 fail mem.empty
210 end
211end last
212
213--- Remove and return the last item. Reports `mem.empty` without mutation when
214--- empty; retains capacity.
215public pop: (item: type, inout value: list(item))
216 -> (result: item from value) ! mem.empty =
217 result = mem.withdraw(value.values) else (problem)
218 _ = problem
219 fail mem.empty
220 end
221end pop
222
223--- Discard all items and retain capacity. Does not release resources
224--- referenced by discarded values.
225public clear: (item: type, inout value: list(item)) -> none =
226 mem.clear(value.values)
227end clear
228
229--- Discard items, free backing through the original provider and reset the
230--- list. End all views first; nested resources remain the caller's
231--- responsibility.
232public release: (item: type, provider: type is mem.allocator,
233 inout value: list(item), inout state: provider) -> none =
234 drain(value.values)
235 free_empty(value.values, state)
236end release