1#[cfg(feature = "read")]
2use alloc::boxed::Box;
3#[cfg(feature = "read")]
4use alloc::vec::Vec;
5use core::fmt;
6use core::mem::MaybeUninit;
7use core::ops;
8use core::ptr;
9use core::slice;
10
11mod sealed {
12 /// # Safety
13 /// Implementer must not modify the content in storage.
14 pub unsafe trait Sealed {
15 type Storage;
16
17 fn new_storage() -> Self::Storage;
18
19 fn grow(_storage: &mut Self::Storage, _additional: usize) -> Result<(), CapacityFull> {
20 Err(CapacityFull)
21 }
22 }
23
24 #[derive(Clone, Copy, Debug)]
25 pub struct CapacityFull;
26}
27
28use sealed::*;
29
30/// Marker trait for types that can be used as backing storage when a growable array type is needed.
31///
32/// This trait is sealed and cannot be implemented for types outside this crate.
33pub trait ArrayLike: Sealed {
34 /// Type of the elements being stored.
35 type Item;
36
37 #[doc(hidden)]
38 fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<Self::Item>];
39
40 #[doc(hidden)]
41 fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<Self::Item>];
42}
43
44// Use macro since const generics can't be used due to MSRV.
45macro_rules! impl_array {
46 () => {};
47 ($n:literal $($rest:tt)*) => {
48 // SAFETY: does not modify the content in storage.
49 unsafe impl<T> Sealed for [T; $n] {
50 type Storage = [MaybeUninit<T>; $n];
51
52 fn new_storage() -> Self::Storage {
53 // SAFETY: An uninitialized `[MaybeUninit<_>; _]` is valid.
54 unsafe { MaybeUninit::uninit().assume_init() }
55 }
56 }
57
58 impl<T> ArrayLike for [T; $n] {
59 type Item = T;
60
61 fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] {
62 storage
63 }
64
65 fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] {
66 storage
67 }
68 }
69
70 impl_array!($($rest)*);
71 }
72}
73
74#[cfg(feature = "read")]
75macro_rules! impl_box {
76 () => {};
77 ($n:literal $($rest:tt)*) => {
78 // SAFETY: does not modify the content in storage.
79 unsafe impl<T> Sealed for Box<[T; $n]> {
80 type Storage = Box<[MaybeUninit<T>; $n]>;
81
82 fn new_storage() -> Self::Storage {
83 // SAFETY: An uninitialized `[MaybeUninit<_>; _]` is valid.
84 Box::new(unsafe { MaybeUninit::uninit().assume_init() })
85 }
86 }
87
88 impl<T> ArrayLike for Box<[T; $n]> {
89 type Item = T;
90
91 fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] {
92 &storage[..]
93 }
94
95 fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] {
96 &mut storage[..]
97 }
98 }
99
100 impl_box!($($rest)*);
101 }
102}
103
104impl_array!(0 1 2 3 4 8 16 32 64 128 192);
105#[cfg(feature = "read")]
106impl_box!(0 1 2 3 4 8 16 32 64 128 192);
107
108#[cfg(feature = "read")]
109unsafe impl<T> Sealed for Vec<T> {
110 type Storage = Box<[MaybeUninit<T>]>;
111
112 fn new_storage() -> Self::Storage {
113 Box::new([])
114 }
115
116 fn grow(storage: &mut Self::Storage, additional: usize) -> Result<(), CapacityFull> {
117 let mut vec: Vec<_> = core::mem::replace(dest:storage, src:Box::new([])).into();
118 vec.reserve(additional);
119 // SAFETY: This is a `Vec` of `MaybeUninit`.
120 unsafe { vec.set_len(new_len:vec.capacity()) };
121 *storage = vec.into_boxed_slice();
122 Ok(())
123 }
124}
125
126#[cfg(feature = "read")]
127impl<T> ArrayLike for Vec<T> {
128 type Item = T;
129
130 fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] {
131 storage
132 }
133
134 fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] {
135 storage
136 }
137}
138
139pub(crate) struct ArrayVec<A: ArrayLike> {
140 storage: A::Storage,
141 len: usize,
142}
143
144impl<A: ArrayLike> ArrayVec<A> {
145 pub fn new() -> Self {
146 Self {
147 storage: A::new_storage(),
148 len: 0,
149 }
150 }
151
152 pub fn clear(&mut self) {
153 let ptr: *mut [A::Item] = &mut **self;
154 // Set length first so the type invariant is upheld even if `drop_in_place` panicks.
155 self.len = 0;
156 // SAFETY: `ptr` contains valid elements only and we "forget" them by setting the length.
157 unsafe { ptr::drop_in_place(ptr) };
158 }
159
160 pub fn try_push(&mut self, value: A::Item) -> Result<(), CapacityFull> {
161 let mut storage = A::as_mut_slice(&mut self.storage);
162 if self.len >= storage.len() {
163 A::grow(&mut self.storage, 1)?;
164 storage = A::as_mut_slice(&mut self.storage);
165 }
166
167 storage[self.len] = MaybeUninit::new(value);
168 self.len += 1;
169 Ok(())
170 }
171
172 pub fn try_insert(&mut self, index: usize, element: A::Item) -> Result<(), CapacityFull> {
173 assert!(index <= self.len);
174
175 let mut storage = A::as_mut_slice(&mut self.storage);
176 if self.len >= storage.len() {
177 A::grow(&mut self.storage, 1)?;
178 storage = A::as_mut_slice(&mut self.storage);
179 }
180
181 // SAFETY: storage[index] is filled later.
182 unsafe {
183 let p = storage.as_mut_ptr().add(index);
184 core::ptr::copy(p as *const _, p.add(1), self.len - index);
185 }
186 storage[index] = MaybeUninit::new(element);
187 self.len += 1;
188 Ok(())
189 }
190
191 pub fn pop(&mut self) -> Option<A::Item> {
192 if self.len == 0 {
193 None
194 } else {
195 self.len -= 1;
196 // SAFETY: this element is valid and we "forget" it by setting the length.
197 Some(unsafe { A::as_slice(&self.storage)[self.len].as_ptr().read() })
198 }
199 }
200
201 pub fn swap_remove(&mut self, index: usize) -> A::Item {
202 assert!(self.len > 0);
203 A::as_mut_slice(&mut self.storage).swap(index, self.len - 1);
204 self.pop().unwrap()
205 }
206}
207
208#[cfg(feature = "read")]
209impl<T> ArrayVec<Vec<T>> {
210 pub fn into_vec(mut self) -> Vec<T> {
211 let len: usize = core::mem::replace(&mut self.len, src:0);
212 let storage: Box<[MaybeUninit]> = core::mem::replace(&mut self.storage, src:Box::new([]));
213 let slice: &mut [MaybeUninit] = Box::leak(storage);
214 debug_assert!(len <= slice.len());
215 // SAFETY: valid elements.
216 unsafe { Vec::from_raw_parts(slice.as_mut_ptr() as *mut T, length:len, capacity:slice.len()) }
217 }
218}
219
220impl<A: ArrayLike> Drop for ArrayVec<A> {
221 fn drop(&mut self) {
222 self.clear();
223 }
224}
225
226impl<A: ArrayLike> Default for ArrayVec<A> {
227 fn default() -> Self {
228 Self::new()
229 }
230}
231
232impl<A: ArrayLike> ops::Deref for ArrayVec<A> {
233 type Target = [A::Item];
234
235 fn deref(&self) -> &[A::Item] {
236 let slice: &&[MaybeUninit<::Item>] = &A::as_slice(&self.storage);
237 debug_assert!(self.len <= slice.len());
238 // SAFETY: valid elements.
239 unsafe { slice::from_raw_parts(data:slice.as_ptr() as _, self.len) }
240 }
241}
242
243impl<A: ArrayLike> ops::DerefMut for ArrayVec<A> {
244 fn deref_mut(&mut self) -> &mut [A::Item] {
245 let slice: &mut &mut [MaybeUninit<::Item>] = &mut A::as_mut_slice(&mut self.storage);
246 debug_assert!(self.len <= slice.len());
247 // SAFETY: valid elements.
248 unsafe { slice::from_raw_parts_mut(data:slice.as_mut_ptr() as _, self.len) }
249 }
250}
251
252impl<A: ArrayLike> Clone for ArrayVec<A>
253where
254 A::Item: Clone,
255{
256 fn clone(&self) -> Self {
257 let mut new: ArrayVec = Self::default();
258 for value: &impl Clone in &**self {
259 new.try_push(value.clone()).unwrap();
260 }
261 new
262 }
263}
264
265impl<A: ArrayLike> PartialEq for ArrayVec<A>
266where
267 A::Item: PartialEq,
268{
269 fn eq(&self, other: &Self) -> bool {
270 **self == **other
271 }
272}
273
274impl<A: ArrayLike> Eq for ArrayVec<A> where A::Item: Eq {}
275
276impl<A: ArrayLike> fmt::Debug for ArrayVec<A>
277where
278 A::Item: fmt::Debug,
279{
280 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
281 fmt::Debug::fmt(&**self, f)
282 }
283}
284