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