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