1 use crate::raw::build::BuilderNode; 2 use crate::raw::{CompiledAddr, NONE_ADDRESS}; 3 4 #[derive(Debug)] 5 pub struct Registry { 6 table: Vec<RegistryCell>, 7 table_size: usize, // number of rows 8 mru_size: usize, // number of columns 9 } 10 11 #[derive(Debug)] 12 struct RegistryCache<'a> { 13 cells: &'a mut [RegistryCell], 14 } 15 16 #[derive(Clone, Debug)] 17 pub struct RegistryCell { 18 addr: CompiledAddr, 19 node: BuilderNode, 20 } 21 22 #[derive(Debug)] 23 pub enum RegistryEntry<'a> { 24 Found(CompiledAddr), 25 NotFound(&'a mut RegistryCell), 26 Rejected, 27 } 28 29 impl Registry { new(table_size: usize, mru_size: usize) -> Registry30 pub fn new(table_size: usize, mru_size: usize) -> Registry { 31 let empty_cell = RegistryCell::none(); 32 let ncells = table_size.checked_mul(mru_size).unwrap(); 33 Registry { table: vec![empty_cell; ncells], table_size, mru_size } 34 } 35 entry<'a>(&'a mut self, node: &BuilderNode) -> RegistryEntry<'a>36 pub fn entry<'a>(&'a mut self, node: &BuilderNode) -> RegistryEntry<'a> { 37 if self.table.is_empty() { 38 return RegistryEntry::Rejected; 39 } 40 let bucket = self.hash(node); 41 let start = self.mru_size * bucket; 42 let end = start + self.mru_size; 43 RegistryCache { cells: &mut self.table[start..end] }.entry(node) 44 } 45 hash(&self, node: &BuilderNode) -> usize46 fn hash(&self, node: &BuilderNode) -> usize { 47 // Basic FNV-1a hash as described: 48 // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function 49 // 50 // In unscientific experiments, this provides the same compression 51 // as `std::hash::SipHasher` but is much much faster. 52 const FNV_PRIME: u64 = 1099511628211; 53 let mut h = 14695981039346656037; 54 h = (h ^ (node.is_final as u64)).wrapping_mul(FNV_PRIME); 55 h = (h ^ node.final_output.value()).wrapping_mul(FNV_PRIME); 56 for t in &node.trans { 57 h = (h ^ (t.inp as u64)).wrapping_mul(FNV_PRIME); 58 h = (h ^ t.out.value()).wrapping_mul(FNV_PRIME); 59 h = (h ^ (t.addr as u64)).wrapping_mul(FNV_PRIME); 60 } 61 (h as usize) % self.table_size 62 } 63 } 64 65 impl<'a> RegistryCache<'a> { entry(mut self, node: &BuilderNode) -> RegistryEntry<'a>66 fn entry(mut self, node: &BuilderNode) -> RegistryEntry<'a> { 67 if self.cells.len() == 1 { 68 let cell = &mut self.cells[0]; 69 if !cell.is_none() && &cell.node == node { 70 RegistryEntry::Found(cell.addr) 71 } else { 72 cell.node.clone_from(node); 73 RegistryEntry::NotFound(cell) 74 } 75 } else if self.cells.len() == 2 { 76 let cell1 = &mut self.cells[0]; 77 if !cell1.is_none() && &cell1.node == node { 78 return RegistryEntry::Found(cell1.addr); 79 } 80 81 let cell2 = &mut self.cells[1]; 82 if !cell2.is_none() && &cell2.node == node { 83 let addr = cell2.addr; 84 self.cells.swap(0, 1); 85 return RegistryEntry::Found(addr); 86 } 87 88 self.cells[1].node.clone_from(node); 89 self.cells.swap(0, 1); 90 RegistryEntry::NotFound(&mut self.cells[0]) 91 } else { 92 let find = |c: &RegistryCell| !c.is_none() && &c.node == node; 93 if let Some(i) = self.cells.iter().position(find) { 94 let addr = self.cells[i].addr; 95 self.promote(i); // most recently used 96 RegistryEntry::Found(addr) 97 } else { 98 let last = self.cells.len() - 1; 99 self.cells[last].node.clone_from(node); // discard LRU 100 self.promote(last); 101 RegistryEntry::NotFound(&mut self.cells[0]) 102 } 103 } 104 } 105 promote(&mut self, mut i: usize)106 fn promote(&mut self, mut i: usize) { 107 assert!(i < self.cells.len()); 108 while i > 0 { 109 self.cells.swap(i - 1, i); 110 i -= 1; 111 } 112 } 113 } 114 115 impl RegistryCell { none() -> RegistryCell116 fn none() -> RegistryCell { 117 RegistryCell { addr: NONE_ADDRESS, node: BuilderNode::default() } 118 } 119 is_none(&self) -> bool120 fn is_none(&self) -> bool { 121 self.addr == NONE_ADDRESS 122 } 123 insert(&mut self, addr: CompiledAddr)124 pub fn insert(&mut self, addr: CompiledAddr) { 125 self.addr = addr; 126 } 127 } 128 129 #[cfg(test)] 130 mod tests { 131 use super::{Registry, RegistryCache, RegistryCell, RegistryEntry}; 132 use crate::raw::build::BuilderNode; 133 use crate::raw::{Output, Transition}; 134 assert_rejected(entry: RegistryEntry)135 fn assert_rejected(entry: RegistryEntry) { 136 match entry { 137 RegistryEntry::Rejected => {} 138 entry => panic!("expected rejected entry, got: {:?}", entry), 139 } 140 } 141 assert_not_found(entry: RegistryEntry)142 fn assert_not_found(entry: RegistryEntry) { 143 match entry { 144 RegistryEntry::NotFound(_) => {} 145 entry => panic!("expected nout found entry, got: {:?}", entry), 146 } 147 } 148 assert_insert_and_found(reg: &mut Registry, bnode: &BuilderNode)149 fn assert_insert_and_found(reg: &mut Registry, bnode: &BuilderNode) { 150 match reg.entry(&bnode) { 151 RegistryEntry::NotFound(cell) => cell.insert(1234), 152 entry => panic!("unexpected not found entry, got: {:?}", entry), 153 } 154 match reg.entry(&bnode) { 155 RegistryEntry::Found(addr) => assert_eq!(addr, 1234), 156 entry => panic!("unexpected found entry, got: {:?}", entry), 157 } 158 } 159 160 #[test] empty_is_ok()161 fn empty_is_ok() { 162 let mut reg = Registry::new(0, 0); 163 let bnode = BuilderNode { 164 is_final: false, 165 final_output: Output::zero(), 166 trans: vec![], 167 }; 168 assert_rejected(reg.entry(&bnode)); 169 } 170 171 #[test] one_final_is_ok()172 fn one_final_is_ok() { 173 let mut reg = Registry::new(1, 1); 174 let bnode = BuilderNode { 175 is_final: true, 176 final_output: Output::zero(), 177 trans: vec![], 178 }; 179 assert_insert_and_found(&mut reg, &bnode); 180 } 181 182 #[test] one_with_trans_is_ok()183 fn one_with_trans_is_ok() { 184 let mut reg = Registry::new(1, 1); 185 let bnode = BuilderNode { 186 is_final: false, 187 final_output: Output::zero(), 188 trans: vec![Transition { 189 addr: 0, 190 inp: b'a', 191 out: Output::zero(), 192 }], 193 }; 194 assert_insert_and_found(&mut reg, &bnode); 195 assert_not_found( 196 reg.entry(&BuilderNode { is_final: true, ..bnode.clone() }), 197 ); 198 assert_not_found(reg.entry(&BuilderNode { 199 trans: vec![Transition { 200 addr: 0, 201 inp: b'b', 202 out: Output::zero(), 203 }], 204 ..bnode.clone() 205 })); 206 assert_not_found(reg.entry(&BuilderNode { 207 trans: vec![Transition { 208 addr: 0, 209 inp: b'a', 210 out: Output::new(1), 211 }], 212 ..bnode.clone() 213 })); 214 } 215 216 #[test] cache_works()217 fn cache_works() { 218 let mut reg = Registry::new(1, 1); 219 220 let bnode1 = BuilderNode { is_final: true, ..BuilderNode::default() }; 221 assert_insert_and_found(&mut reg, &bnode1); 222 223 let bnode2 = 224 BuilderNode { final_output: Output::new(1), ..bnode1.clone() }; 225 assert_insert_and_found(&mut reg, &bnode2); 226 assert_not_found(reg.entry(&bnode1)); 227 } 228 229 #[test] promote()230 fn promote() { 231 let bn = BuilderNode::default(); 232 let mut bnodes = vec![ 233 RegistryCell { addr: 1, node: bn.clone() }, 234 RegistryCell { addr: 2, node: bn.clone() }, 235 RegistryCell { addr: 3, node: bn.clone() }, 236 RegistryCell { addr: 4, node: bn.clone() }, 237 ]; 238 let mut cache = RegistryCache { cells: &mut bnodes }; 239 240 cache.promote(0); 241 assert_eq!(cache.cells[0].addr, 1); 242 assert_eq!(cache.cells[1].addr, 2); 243 assert_eq!(cache.cells[2].addr, 3); 244 assert_eq!(cache.cells[3].addr, 4); 245 246 cache.promote(1); 247 assert_eq!(cache.cells[0].addr, 2); 248 assert_eq!(cache.cells[1].addr, 1); 249 assert_eq!(cache.cells[2].addr, 3); 250 assert_eq!(cache.cells[3].addr, 4); 251 252 cache.promote(3); 253 assert_eq!(cache.cells[0].addr, 4); 254 assert_eq!(cache.cells[1].addr, 2); 255 assert_eq!(cache.cells[2].addr, 1); 256 assert_eq!(cache.cells[3].addr, 3); 257 258 cache.promote(2); 259 assert_eq!(cache.cells[0].addr, 1); 260 assert_eq!(cache.cells[1].addr, 4); 261 assert_eq!(cache.cells[2].addr, 2); 262 assert_eq!(cache.cells[3].addr, 3); 263 } 264 } 265