1 //! Runtime sized fixed array type with inlined storage optimization. 2 //! 3 //! This should be replaced with `smallvec` when that dependency is 4 //! available to us. In the meantime, this type should be kept small 5 //! with functionality only added when needed. 6 7 use core::fmt; 8 use std::ops::{Deref, DerefMut}; 9 10 /// Internal SmallVec like implementation but for fixed sized arrays whose 11 /// size is only known at runtime. 12 /// 13 /// Used to avoid allocations when possible for small or temporary 14 /// arrays. 15 #[derive(Clone)] 16 pub(crate) struct SmallArray<T, const N: usize> 17 where 18 T: Copy, 19 { 20 storage: SmallStorage<T, N>, 21 } 22 23 impl<T, const N: usize> SmallArray<T, N> 24 where 25 T: Copy, 26 { new(initial_value: T, len: usize) -> Self27 pub fn new(initial_value: T, len: usize) -> Self { 28 Self { 29 storage: if len <= N { 30 SmallStorage::Inline([initial_value; N], len) 31 } else { 32 SmallStorage::Heap(vec![initial_value; len]) 33 }, 34 } 35 } 36 as_slice(&self) -> &[T]37 pub fn as_slice(&self) -> &[T] { 38 match &self.storage { 39 SmallStorage::Inline(array, len) => &array[..*len], 40 SmallStorage::Heap(vec) => vec.as_slice(), 41 } 42 } 43 as_mut_slice(&mut self) -> &mut [T]44 pub fn as_mut_slice(&mut self) -> &mut [T] { 45 match &mut self.storage { 46 SmallStorage::Inline(array, len) => &mut array[..*len], 47 SmallStorage::Heap(vec) => vec.as_mut_slice(), 48 } 49 } 50 } 51 52 impl<T, const N: usize> Deref for SmallArray<T, N> 53 where 54 T: Copy, 55 { 56 type Target = [T]; 57 deref(&self) -> &Self::Target58 fn deref(&self) -> &Self::Target { 59 self.as_slice() 60 } 61 } 62 63 impl<T, const N: usize> DerefMut for SmallArray<T, N> 64 where 65 T: Copy, 66 { deref_mut(&mut self) -> &mut Self::Target67 fn deref_mut(&mut self) -> &mut Self::Target { 68 self.as_mut_slice() 69 } 70 } 71 72 impl<T, const N: usize> PartialEq for SmallArray<T, N> 73 where 74 T: Copy + PartialEq, 75 { eq(&self, other: &Self) -> bool76 fn eq(&self, other: &Self) -> bool { 77 self.as_slice() == other.as_slice() 78 } 79 } 80 81 impl<T, const N: usize> Eq for SmallArray<T, N> where T: Copy + Eq {} 82 83 impl<T, const N: usize> fmt::Debug for SmallArray<T, N> 84 where 85 T: Copy + fmt::Debug, 86 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result87 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 88 f.debug_list().entries(self.as_slice().iter()).finish() 89 } 90 } 91 92 #[derive(Clone)] 93 enum SmallStorage<T, const N: usize> { 94 Inline([T; N], usize), 95 Heap(Vec<T>), 96 } 97 98 #[derive(Clone)] 99 pub(crate) struct SmallArrayIter<T, const N: usize> 100 where 101 T: Copy, 102 { 103 array: SmallArray<T, N>, 104 pos: usize, 105 } 106 107 impl<T, const N: usize> Iterator for SmallArrayIter<T, N> 108 where 109 T: Copy, 110 { 111 type Item = T; 112 next(&mut self) -> Option<Self::Item>113 fn next(&mut self) -> Option<Self::Item> { 114 let pos = self.pos; 115 self.pos += 1; 116 self.array.as_slice().get(pos).copied() 117 } 118 } 119 120 impl<T, const N: usize> IntoIterator for SmallArray<T, N> 121 where 122 T: Copy, 123 { 124 type Item = T; 125 type IntoIter = SmallArrayIter<T, N>; 126 into_iter(self) -> Self::IntoIter127 fn into_iter(self) -> Self::IntoIter { 128 Self::IntoIter { 129 array: self, 130 pos: 0, 131 } 132 } 133 } 134 135 #[cfg(test)] 136 mod test { 137 use super::{SmallArray, SmallStorage}; 138 139 #[test] choose_inline()140 fn choose_inline() { 141 let arr = SmallArray::<_, 4>::new(0, 4); 142 assert!(matches!(arr.storage, SmallStorage::Inline(..))); 143 assert_eq!(arr.len(), 4); 144 } 145 146 #[test] choose_heap()147 fn choose_heap() { 148 let arr = SmallArray::<_, 4>::new(0, 5); 149 assert!(matches!(arr.storage, SmallStorage::Heap(..))); 150 assert_eq!(arr.len(), 5); 151 } 152 153 #[test] store_and_read_inline()154 fn store_and_read_inline() { 155 let mut arr = SmallArray::<_, 8>::new(0, 8); 156 for (i, value) in arr.as_mut_slice().iter_mut().enumerate() { 157 *value = i * 2; 158 } 159 let expected = [0, 2, 4, 6, 8, 10, 12, 14]; 160 assert_eq!(arr.as_slice(), &expected); 161 assert_eq!(format!("{arr:?}"), format!("{expected:?}")); 162 } 163 164 #[test] store_and_read_heap()165 fn store_and_read_heap() { 166 let mut arr = SmallArray::<_, 4>::new(0, 8); 167 for (i, value) in arr.as_mut_slice().iter_mut().enumerate() { 168 *value = i * 2; 169 } 170 let expected = [0, 2, 4, 6, 8, 10, 12, 14]; 171 assert_eq!(arr.as_slice(), &expected); 172 assert_eq!(format!("{arr:?}"), format!("{expected:?}")); 173 } 174 } 175