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// SAFETY: does not modify the content in storage.
45unsafe impl<T, const N: usize> Sealed for [T; N] {
46 type Storage = [MaybeUninit<T>; N];
47
48 fn new_storage() -> Self::Storage {
49 // SAFETY: An uninitialized `[MaybeUninit<_>; _]` is valid.
50 unsafe { MaybeUninit::uninit().assume_init() }
51 }
52}
53
54impl<T, const N: usize> ArrayLike for [T; N] {
55 type Item = T;
56
57 fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] {
58 storage
59 }
60
61 fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] {
62 storage
63 }
64}
65
66// SAFETY: does not modify the content in storage.
67#[cfg(feature = "read")]
68unsafe impl<T, const N: usize> Sealed for Box<[T; N]> {
69 type Storage = Box<[MaybeUninit<T>; N]>;
70
71 fn new_storage() -> Self::Storage {
72 // SAFETY: An uninitialized `[MaybeUninit<_>; _]` is valid.
73 Box::new(unsafe { MaybeUninit::uninit().assume_init() })
74 }
75}
76
77#[cfg(feature = "read")]
78impl<T, const N: usize> ArrayLike for Box<[T; N]> {
79 type Item = T;
80
81 fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] {
82 &storage[..]
83 }
84
85 fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] {
86 &mut storage[..]
87 }
88}
89
90#[cfg(feature = "read")]
91unsafe impl<T> Sealed for Vec<T> {
92 type Storage = Box<[MaybeUninit<T>]>;
93
94 fn new_storage() -> Self::Storage {
95 Box::new([])
96 }
97
98 fn grow(storage: &mut Self::Storage, additional: usize) -> Result<(), CapacityFull> {
99 let mut vec: Vec<_> = core::mem::replace(dest:storage, src:Box::new([])).into();
100 vec.reserve(additional);
101 // SAFETY: This is a `Vec` of `MaybeUninit`.
102 unsafe { vec.set_len(new_len:vec.capacity()) };
103 *storage = vec.into_boxed_slice();
104 Ok(())
105 }
106}
107
108#[cfg(feature = "read")]
109impl<T> ArrayLike for Vec<T> {
110 type Item = T;
111
112 fn as_slice(storage: &Self::Storage) -> &[MaybeUninit<T>] {
113 storage
114 }
115
116 fn as_mut_slice(storage: &mut Self::Storage) -> &mut [MaybeUninit<T>] {
117 storage
118 }
119}
120
121pub(crate) struct ArrayVec<A: ArrayLike> {
122 storage: A::Storage,
123 len: usize,
124}
125
126impl<A: ArrayLike> ArrayVec<A> {
127 pub fn new() -> Self {
128 Self {
129 storage: A::new_storage(),
130 len: 0,
131 }
132 }
133
134 pub fn clear(&mut self) {
135 let ptr: *mut [A::Item] = &mut **self;
136 // Set length first so the type invariant is upheld even if `drop_in_place` panicks.
137 self.len = 0;
138 // SAFETY: `ptr` contains valid elements only and we "forget" them by setting the length.
139 unsafe { ptr::drop_in_place(ptr) };
140 }
141
142 pub fn try_push(&mut self, value: A::Item) -> Result<(), CapacityFull> {
143 let mut storage = A::as_mut_slice(&mut self.storage);
144 if self.len >= storage.len() {
145 A::grow(&mut self.storage, 1)?;
146 storage = A::as_mut_slice(&mut self.storage);
147 }
148
149 storage[self.len] = MaybeUninit::new(value);
150 self.len += 1;
151 Ok(())
152 }
153
154 pub fn try_insert(&mut self, index: usize, element: A::Item) -> Result<(), CapacityFull> {
155 assert!(index <= self.len);
156
157 let mut storage = A::as_mut_slice(&mut self.storage);
158 if self.len >= storage.len() {
159 A::grow(&mut self.storage, 1)?;
160 storage = A::as_mut_slice(&mut self.storage);
161 }
162
163 // SAFETY: storage[index] is filled later.
164 unsafe {
165 let p = storage.as_mut_ptr().add(index);
166 core::ptr::copy(p as *const _, p.add(1), self.len - index);
167 }
168 storage[index] = MaybeUninit::new(element);
169 self.len += 1;
170 Ok(())
171 }
172
173 pub fn pop(&mut self) -> Option<A::Item> {
174 if self.len == 0 {
175 None
176 } else {
177 self.len -= 1;
178 // SAFETY: this element is valid and we "forget" it by setting the length.
179 Some(unsafe { A::as_slice(&self.storage)[self.len].as_ptr().read() })
180 }
181 }
182
183 pub fn swap_remove(&mut self, index: usize) -> A::Item {
184 assert!(self.len > 0);
185 A::as_mut_slice(&mut self.storage).swap(index, self.len - 1);
186 self.pop().unwrap()
187 }
188}
189
190#[cfg(feature = "read")]
191impl<T> ArrayVec<Vec<T>> {
192 pub fn into_vec(mut self) -> Vec<T> {
193 let len: usize = core::mem::replace(&mut self.len, src:0);
194 let storage: Box<[MaybeUninit]> = core::mem::replace(&mut self.storage, src:Box::new([]));
195 let slice: &mut [MaybeUninit] = Box::leak(storage);
196 debug_assert!(len <= slice.len());
197 // SAFETY: valid elements.
198 unsafe { Vec::from_raw_parts(slice.as_mut_ptr() as *mut T, length:len, capacity:slice.len()) }
199 }
200}
201
202impl<A: ArrayLike> Drop for ArrayVec<A> {
203 fn drop(&mut self) {
204 self.clear();
205 }
206}
207
208impl<A: ArrayLike> Default for ArrayVec<A> {
209 fn default() -> Self {
210 Self::new()
211 }
212}
213
214impl<A: ArrayLike> ops::Deref for ArrayVec<A> {
215 type Target = [A::Item];
216
217 fn deref(&self) -> &[A::Item] {
218 let slice: &&[MaybeUninit<::Item>] = &A::as_slice(&self.storage);
219 debug_assert!(self.len <= slice.len());
220 // SAFETY: valid elements.
221 unsafe { slice::from_raw_parts(data:slice.as_ptr() as _, self.len) }
222 }
223}
224
225impl<A: ArrayLike> ops::DerefMut for ArrayVec<A> {
226 fn deref_mut(&mut self) -> &mut [A::Item] {
227 let slice: &mut &mut [MaybeUninit<::Item>] = &mut A::as_mut_slice(&mut self.storage);
228 debug_assert!(self.len <= slice.len());
229 // SAFETY: valid elements.
230 unsafe { slice::from_raw_parts_mut(data:slice.as_mut_ptr() as _, self.len) }
231 }
232}
233
234impl<A: ArrayLike> Clone for ArrayVec<A>
235where
236 A::Item: Clone,
237{
238 fn clone(&self) -> Self {
239 let mut new: ArrayVec = Self::default();
240 for value: &impl Clone in &**self {
241 new.try_push(value.clone()).unwrap();
242 }
243 new
244 }
245}
246
247impl<A: ArrayLike> PartialEq for ArrayVec<A>
248where
249 A::Item: PartialEq,
250{
251 fn eq(&self, other: &Self) -> bool {
252 **self == **other
253 }
254}
255
256impl<A: ArrayLike> Eq for ArrayVec<A> where A::Item: Eq {}
257
258impl<A: ArrayLike> fmt::Debug for ArrayVec<A>
259where
260 A::Item: fmt::Debug,
261{
262 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
263 fmt::Debug::fmt(&**self, f)
264 }
265}
266