Skip to main content

utils/
array.rs

1//! Array helpers.
2
3use std::fmt;
4use std::hash::Hash;
5use std::ops::{Deref, DerefMut};
6
7/// A fixed-size array-backed vector.
8///
9/// `ArrayVec` has a fixed-sized `N` long array and a length field to track how many elements are
10/// populated. It is useful for storing a small but variable number of elements without heap
11/// allocation.
12///
13/// The implementation is intentionally simple, and requires [`Copy`] and [`Default`] bounds on some
14/// methods instead of using [`std::mem::MaybeUninit`].
15#[derive(Clone, PartialEq, Eq, Hash)]
16pub struct ArrayVec<T, const N: usize> {
17    len: usize,
18    data: [T; N],
19}
20
21impl<T, const N: usize> ArrayVec<T, N> {
22    /// Creates a new empty `ArrayVec`.
23    ///
24    /// # Examples
25    /// ```
26    /// # use utils::array::ArrayVec;
27    /// let vec: ArrayVec<i32, 5> = ArrayVec::new();
28    /// assert_eq!(vec.len(), 0);
29    /// ```
30    #[inline]
31    #[must_use]
32    pub fn new() -> Self
33    where
34        T: Copy + Default,
35    {
36        Self {
37            len: 0,
38            data: [T::default(); N],
39        }
40    }
41
42    /// Creates a new `ArrayVec`, copying initial data from the provided slice.
43    ///
44    /// # Examples
45    /// ```
46    /// # use utils::array::ArrayVec;
47    /// let mut vec: ArrayVec<i32, 5> = ArrayVec::<i32, 5>::from_slice(&[1, 2, 3]).unwrap();
48    /// assert_eq!(vec.len(), 3);
49    /// assert_eq!(vec.pop(), Some(3));
50    /// assert_eq!(vec.pop(), Some(2));
51    /// assert_eq!(vec.pop(), Some(1));
52    /// assert_eq!(vec.pop(), None);
53    ///
54    /// assert_eq!(ArrayVec::<i32, 5>::from_slice(&[1, 2, 3, 4, 5, 6]), None);
55    /// ```
56    #[inline]
57    #[must_use]
58    pub fn from_slice(slice: &[T]) -> Option<Self>
59    where
60        T: Copy + Default,
61    {
62        if slice.len() > N {
63            None
64        } else {
65            let mut data = [T::default(); N];
66            data[..slice.len()].copy_from_slice(slice);
67            Some(Self {
68                len: slice.len(),
69                data,
70            })
71        }
72    }
73
74    /// Adds an element to the end of the vector.
75    ///
76    /// Returns [`Err`] containing the provided value if the vector is already full.
77    ///
78    /// # Examples
79    /// ```
80    /// # use utils::array::ArrayVec;
81    /// let mut vec: ArrayVec<i32, 2> = ArrayVec::new();
82    /// assert_eq!(vec.push(1), Ok(()));
83    /// assert_eq!(vec.push(2), Ok(()));
84    /// assert_eq!(vec.push(3), Err(3)); // Vector is full
85    /// ```
86    #[inline]
87    pub fn push(&mut self, value: T) -> Result<(), T> {
88        let len = self.len;
89        if len < N {
90            self.data[len] = value;
91            // LLVM can't always tell that an element write doesn't overwrite the length, so
92            // write the length last using the value read above to avoid reading it again
93            self.len = len + 1;
94            Ok(())
95        } else {
96            Err(value)
97        }
98    }
99
100    /// Removes the last element from the vector and returns it, or [`None`] if it is empty.
101    ///
102    /// # Examples
103    /// ```
104    /// # use utils::array::ArrayVec;
105    /// let mut vec: ArrayVec<i32, 3> = ArrayVec::new();
106    /// vec.push(1).unwrap();
107    /// assert_eq!(vec.pop(), Some(1));
108    /// assert_eq!(vec.pop(), None);
109    /// ```
110    #[inline]
111    pub fn pop(&mut self) -> Option<T>
112    where
113        T: Default,
114    {
115        // Write the length last (see push)
116        let len = self.len.checked_sub(1)?;
117        let value = std::mem::take(&mut self.data[len]);
118        self.len = len;
119        Some(value)
120    }
121
122    /// Returns a slice of all the populated elements in the vector.
123    ///
124    /// # Examples
125    ///
126    /// ```
127    /// # use utils::array::ArrayVec;
128    /// let mut vec: ArrayVec<i32, 3> = ArrayVec::new();
129    /// vec.push(1).unwrap();
130    /// vec.push(2).unwrap();
131    /// assert_eq!(vec.as_slice(), &[1, 2]);
132    /// ```
133    #[inline]
134    pub fn as_slice(&self) -> &[T] {
135        #[cfg(feature = "unsafe")]
136        unsafe {
137            std::hint::assert_unchecked(self.len <= N);
138        }
139
140        &self.data[..self.len]
141    }
142
143    /// Returns a mutable slice of all the populated elements in the vector.
144    ///
145    /// # Examples
146    ///
147    /// ```
148    /// # use utils::array::ArrayVec;
149    /// let mut vec: ArrayVec<i32, 3> = ArrayVec::new();
150    /// vec.push(1).unwrap();
151    /// vec.push(2).unwrap();
152    /// let mut slice = vec.as_mut_slice();
153    /// slice[1] = 10;
154    /// assert_eq!(slice, &[1, 10]);
155    /// ```
156    #[inline]
157    pub fn as_mut_slice(&mut self) -> &mut [T] {
158        #[cfg(feature = "unsafe")]
159        unsafe {
160            std::hint::assert_unchecked(self.len <= N);
161        }
162
163        &mut self.data[..self.len]
164    }
165
166    /// Returns a reference to the backing array.
167    ///
168    /// Any items after the current length will be set to the default value.
169    ///
170    /// # Examples
171    /// ```
172    /// # use utils::array::ArrayVec;
173    /// let mut vec: ArrayVec<i32, 8> = ArrayVec::new();
174    /// vec.push(10).unwrap();
175    /// vec.push(6).unwrap();
176    /// vec.pop().unwrap();
177    /// assert_eq!(vec.into_array(), [10, 0, 0, 0, 0, 0, 0, 0]);
178    /// ```
179    #[inline]
180    pub fn as_array(&self) -> &[T; N] {
181        &self.data
182    }
183
184    /// Returns the capacity of the vector, which is always `N`.
185    ///
186    /// # Examples
187    /// ```
188    /// # use utils::array::ArrayVec;
189    /// let vec: ArrayVec<i32, 5> = ArrayVec::new();
190    /// assert_eq!(vec.capacity(), 5);
191    /// ```
192    #[inline]
193    pub fn capacity(&self) -> usize {
194        N
195    }
196
197    /// Returns whether the vector is full.
198    ///
199    /// # Examples
200    ///
201    /// ```
202    /// # use utils::array::ArrayVec;
203    /// let mut vec: ArrayVec<i32, 2> = ArrayVec::new();
204    /// assert!(!vec.is_full());
205    /// vec.push(1).unwrap();
206    /// assert!(!vec.is_full());
207    /// vec.push(2).unwrap();
208    /// assert!(vec.is_full());
209    /// ```
210    #[inline]
211    pub fn is_full(&self) -> bool {
212        self.len == N
213    }
214
215    /// Returns the backing array.
216    ///
217    /// Any items after the current length will be set to the default value.
218    ///
219    /// # Examples
220    /// ```
221    /// # use utils::array::ArrayVec;
222    /// let mut vec: ArrayVec<i32, 5> = ArrayVec::new();
223    /// vec.push(1).unwrap();
224    /// vec.push(2).unwrap();
225    /// vec.push(3).unwrap();
226    /// vec.pop().unwrap();
227    /// assert_eq!(vec.into_array(), [1, 2, 0, 0, 0]);
228    /// ```
229    #[inline]
230    pub fn into_array(self) -> [T; N] {
231        self.data
232    }
233}
234
235impl<T, const N: usize> Deref for ArrayVec<T, N> {
236    type Target = [T];
237
238    #[inline]
239    fn deref(&self) -> &Self::Target {
240        self.as_slice()
241    }
242}
243
244impl<T, const N: usize> DerefMut for ArrayVec<T, N> {
245    #[inline]
246    fn deref_mut(&mut self) -> &mut Self::Target {
247        self.as_mut_slice()
248    }
249}
250
251impl<'a, T, const N: usize> IntoIterator for &'a ArrayVec<T, N> {
252    type Item = &'a T;
253    type IntoIter = std::slice::Iter<'a, T>;
254
255    #[inline]
256    fn into_iter(self) -> Self::IntoIter {
257        self.iter()
258    }
259}
260
261impl<'a, T, const N: usize> IntoIterator for &'a mut ArrayVec<T, N> {
262    type Item = &'a mut T;
263    type IntoIter = std::slice::IterMut<'a, T>;
264
265    #[inline]
266    fn into_iter(self) -> Self::IntoIter {
267        self.iter_mut()
268    }
269}
270
271impl<T: fmt::Debug, const N: usize> fmt::Debug for ArrayVec<T, N> {
272    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
273        f.debug_struct("ArrayVec")
274            .field("len", &self.len)
275            .field("cap", &N)
276            .field("data", &self.as_slice())
277            .finish()
278    }
279}
280
281impl<T: Default + Copy, const N: usize> Default for ArrayVec<T, N> {
282    fn default() -> Self {
283        Self::new()
284    }
285}
286
287impl<T, const N: usize> From<[T; N]> for ArrayVec<T, N> {
288    fn from(data: [T; N]) -> Self {
289        ArrayVec { len: N, data }
290    }
291}