|
| 1 | +#![no_std] |
| 2 | + |
| 3 | +#[cfg(feature = "alloc")] |
| 4 | +extern crate alloc; |
| 5 | + |
| 6 | +use core::ptr::read_unaligned; |
| 7 | + |
| 8 | +use tinyvec::ArrayVec; |
| 9 | + |
| 10 | +/// A generic tinyvec::ArrayVec backed map with O(n) lookup. |
| 11 | +/// Maintains insertion order and tracks the last accessed entry index. |
| 12 | +pub struct ArrayMap<K, V, const N: usize> |
| 13 | +where |
| 14 | + K: PartialEq + Default, |
| 15 | + V: Default, |
| 16 | +{ |
| 17 | + entries: ArrayVec<[(K, V); N]>, |
| 18 | + last_accessed_index: Option<usize>, |
| 19 | +} |
| 20 | + |
| 21 | +impl<K, V, const N: usize> ArrayMap<K, V, N> |
| 22 | +where |
| 23 | + K: PartialEq + Default, |
| 24 | + V: Default, |
| 25 | +{ |
| 26 | + pub fn new() -> Self { |
| 27 | + Self { |
| 28 | + entries: ArrayVec::new(), |
| 29 | + last_accessed_index: None, |
| 30 | + } |
| 31 | + } |
| 32 | + |
| 33 | + pub fn len(&self) -> usize { |
| 34 | + self.entries.len() |
| 35 | + } |
| 36 | + |
| 37 | + pub fn is_empty(&self) -> bool { |
| 38 | + self.entries.is_empty() |
| 39 | + } |
| 40 | + |
| 41 | + pub fn last_accessed_index(&self) -> Option<usize> { |
| 42 | + self.last_accessed_index |
| 43 | + } |
| 44 | + |
| 45 | + pub fn get(&self, index: usize) -> Option<&(K, V)> { |
| 46 | + self.entries.get(index) |
| 47 | + } |
| 48 | + |
| 49 | + pub fn get_mut(&mut self, index: usize) -> Option<&mut (K, V)> { |
| 50 | + self.entries.get_mut(index) |
| 51 | + } |
| 52 | + |
| 53 | + pub fn get_u8(&self, index: u8) -> Option<&(K, V)> { |
| 54 | + self.get(index as usize) |
| 55 | + } |
| 56 | + |
| 57 | + pub fn get_mut_u8(&mut self, index: u8) -> Option<&mut (K, V)> { |
| 58 | + self.get_mut(index as usize) |
| 59 | + } |
| 60 | + |
| 61 | + pub fn get_by_key(&self, key: &K) -> Option<&V> { |
| 62 | + self.entries.iter().find(|(k, _)| k == key).map(|(_, v)| v) |
| 63 | + } |
| 64 | + |
| 65 | + pub fn get_mut_by_key(&mut self, key: &K) -> Option<&mut V> { |
| 66 | + self.entries |
| 67 | + .iter_mut() |
| 68 | + .find(|(k, _)| k == key) |
| 69 | + .map(|(_, v)| v) |
| 70 | + } |
| 71 | + |
| 72 | + pub fn find(&self, key: &K) -> Option<(usize, &(K, V))> { |
| 73 | + self.entries.iter().enumerate().find(|(_, (k, _))| k == key) |
| 74 | + } |
| 75 | + |
| 76 | + pub fn find_mut(&mut self, key: &K) -> Option<(usize, &mut (K, V))> { |
| 77 | + self.entries |
| 78 | + .iter_mut() |
| 79 | + .enumerate() |
| 80 | + .find(|(_, (k, _))| k == key) |
| 81 | + } |
| 82 | + |
| 83 | + pub fn find_index(&self, key: &K) -> Option<usize> { |
| 84 | + self.find(key).map(|(idx, _)| idx) |
| 85 | + } |
| 86 | + |
| 87 | + pub fn set_last_accessed_index<E>(&mut self, index: usize) -> Result<(), E> |
| 88 | + where |
| 89 | + E: From<ArrayMapError>, |
| 90 | + { |
| 91 | + if index < self.entries.len() { |
| 92 | + self.last_accessed_index = Some(index); |
| 93 | + Ok(()) |
| 94 | + } else { |
| 95 | + Err(ArrayMapError::IndexOutOfBounds.into()) |
| 96 | + } |
| 97 | + } |
| 98 | + |
| 99 | + pub fn insert<E>(&mut self, key: K, value: V, error: E) -> Result<usize, E> { |
| 100 | + let new_idx = self.entries.len(); |
| 101 | + // tinyvec's try_push returns Some(item) on failure, None on success |
| 102 | + if self.entries.try_push((key, value)).is_some() { |
| 103 | + return Err(error); |
| 104 | + } |
| 105 | + self.last_accessed_index = Some(new_idx); |
| 106 | + Ok(new_idx) |
| 107 | + } |
| 108 | +} |
| 109 | + |
| 110 | +impl<K, V, const N: usize> Default for ArrayMap<K, V, N> |
| 111 | +where |
| 112 | + K: PartialEq + Default, |
| 113 | + V: Default, |
| 114 | +{ |
| 115 | + fn default() -> Self { |
| 116 | + Self::new() |
| 117 | + } |
| 118 | +} |
| 119 | + |
| 120 | +// Optimized [u8; 32] key methods (4x u64 comparison instead of 32x u8). |
| 121 | +impl<V, const N: usize> ArrayMap<[u8; 32], V, N> |
| 122 | +where |
| 123 | + V: Default, |
| 124 | +{ |
| 125 | + pub fn get_by_pubkey(&self, key: &[u8; 32]) -> Option<&V> { |
| 126 | + self.entries |
| 127 | + .iter() |
| 128 | + .find(|(k, _)| pubkey_eq(k, key)) |
| 129 | + .map(|(_, v)| v) |
| 130 | + } |
| 131 | + |
| 132 | + pub fn get_mut_by_pubkey(&mut self, key: &[u8; 32]) -> Option<&mut V> { |
| 133 | + self.entries |
| 134 | + .iter_mut() |
| 135 | + .find(|(k, _)| pubkey_eq(k, key)) |
| 136 | + .map(|(_, v)| v) |
| 137 | + } |
| 138 | + |
| 139 | + pub fn find_by_pubkey(&self, key: &[u8; 32]) -> Option<(usize, &([u8; 32], V))> { |
| 140 | + self.entries |
| 141 | + .iter() |
| 142 | + .enumerate() |
| 143 | + .find(|(_, (k, _))| pubkey_eq(k, key)) |
| 144 | + } |
| 145 | + |
| 146 | + pub fn find_mut_by_pubkey(&mut self, key: &[u8; 32]) -> Option<(usize, &mut ([u8; 32], V))> { |
| 147 | + self.entries |
| 148 | + .iter_mut() |
| 149 | + .enumerate() |
| 150 | + .find(|(_, (k, _))| pubkey_eq(k, key)) |
| 151 | + } |
| 152 | + |
| 153 | + pub fn find_pubkey_index(&self, key: &[u8; 32]) -> Option<usize> { |
| 154 | + self.find_by_pubkey(key).map(|(idx, _)| idx) |
| 155 | + } |
| 156 | +} |
| 157 | + |
| 158 | +#[derive(Debug, Clone, Copy, PartialEq, Eq)] |
| 159 | +pub enum ArrayMapError { |
| 160 | + CapacityExceeded, |
| 161 | + IndexOutOfBounds, |
| 162 | +} |
| 163 | + |
| 164 | +impl core::fmt::Display for ArrayMapError { |
| 165 | + fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { |
| 166 | + match self { |
| 167 | + ArrayMapError::CapacityExceeded => write!(f, "ArrayMap capacity exceeded"), |
| 168 | + ArrayMapError::IndexOutOfBounds => write!(f, "ArrayMap index out of bounds"), |
| 169 | + } |
| 170 | + } |
| 171 | +} |
| 172 | + |
| 173 | +#[inline(always)] |
| 174 | +pub const fn pubkey_eq(p1: &[u8; 32], p2: &[u8; 32]) -> bool { |
| 175 | + let p1_ptr = p1.as_ptr() as *const u64; |
| 176 | + let p2_ptr = p2.as_ptr() as *const u64; |
| 177 | + |
| 178 | + unsafe { |
| 179 | + read_unaligned(p1_ptr) == read_unaligned(p2_ptr) |
| 180 | + && read_unaligned(p1_ptr.add(1)) == read_unaligned(p2_ptr.add(1)) |
| 181 | + && read_unaligned(p1_ptr.add(2)) == read_unaligned(p2_ptr.add(2)) |
| 182 | + && read_unaligned(p1_ptr.add(3)) == read_unaligned(p2_ptr.add(3)) |
| 183 | + } |
| 184 | +} |
0 commit comments