/rust/registry/src/index.crates.io-6f17d22bba15001f/fst-0.4.7/src/raw/registry.rs

Source (jump to first uncovered line)
use crate::raw::build::BuilderNode;
use crate::raw::{CompiledAddr, NONE_ADDRESS};

#[derive(Debug)]
pub struct Registry {
    table: Vec<RegistryCell>,
    table_size: usize, // number of rows
    mru_size: usize,   // number of columns
}

#[derive(Debug)]
struct RegistryCache<'a> {
    cells: &'a mut [RegistryCell],
}

#[derive(Clone, Debug)]
pub struct RegistryCell {
    addr: CompiledAddr,
    node: BuilderNode,
}

#[derive(Debug)]
pub enum RegistryEntry<'a> {
    Found(CompiledAddr),
    NotFound(&'a mut RegistryCell),
    Rejected,
}

impl Registry {
    pub fn new(table_size: usize, mru_size: usize) -> Registry {
        let empty_cell = RegistryCell::none();
        let ncells = table_size.checked_mul(mru_size).unwrap();
        Registry { table: vec![empty_cell; ncells], table_size, mru_size }
    }

    pub fn entry<'a>(&'a mut self, node: &BuilderNode) -> RegistryEntry<'a> {
        if self.table.is_empty() {
            return RegistryEntry::Rejected;
        }
        let bucket = self.hash(node);
        let start = self.mru_size * bucket;
        let end = start + self.mru_size;
        RegistryCache { cells: &mut self.table[start..end] }.entry(node)
    }

    fn hash(&self, node: &BuilderNode) -> usize {
        // Basic FNV-1a hash as described:
        // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
        //
        // In unscientific experiments, this provides the same compression
        // as `std::hash::SipHasher` but is much much faster.
        const FNV_PRIME: u64 = 1099511628211;
        let mut h = 14695981039346656037;
        h = (h ^ (node.is_final as u64)).wrapping_mul(FNV_PRIME);
        h = (h ^ node.final_output.value()).wrapping_mul(FNV_PRIME);
        for t in &node.trans {
            h = (h ^ (t.inp as u64)).wrapping_mul(FNV_PRIME);
            h = (h ^ t.out.value()).wrapping_mul(FNV_PRIME);
            h = (h ^ (t.addr as u64)).wrapping_mul(FNV_PRIME);
        }
        (h as usize) % self.table_size
    }
}

impl<'a> RegistryCache<'a> {
    fn entry(mut self, node: &BuilderNode) -> RegistryEntry<'a> {
        if self.cells.len() == 1 {
            let cell = &mut self.cells[0];
            if !cell.is_none() && &cell.node == node {
                RegistryEntry::Found(cell.addr)
            } else {
                cell.node.clone_from(node);
                RegistryEntry::NotFound(cell)
            }
        } else if self.cells.len() == 2 {
            let cell1 = &mut self.cells[0];
            if !cell1.is_none() && &cell1.node == node {
                return RegistryEntry::Found(cell1.addr);
            }

            let cell2 = &mut self.cells[1];
            if !cell2.is_none() && &cell2.node == node {
                let addr = cell2.addr;
                self.cells.swap(0, 1);
                return RegistryEntry::Found(addr);
            }

            self.cells[1].node.clone_from(node);
            self.cells.swap(0, 1);
            RegistryEntry::NotFound(&mut self.cells[0])
        } else {
            let find = |c: &RegistryCell| !c.is_none() && &c.node == node;
            if let Some(i) = self.cells.iter().position(find) {
                let addr = self.cells[i].addr;
                self.promote(i); // most recently used
                RegistryEntry::Found(addr)
            } else {
                let last = self.cells.len() - 1;
                self.cells[last].node.clone_from(node); // discard LRU
                self.promote(last);
                RegistryEntry::NotFound(&mut self.cells[0])
            }
        }
    }

    fn promote(&mut self, mut i: usize) {
        assert!(i < self.cells.len());
        while i > 0 {
            self.cells.swap(i - 1, i);
            i -= 1;
        }
    }
}

impl RegistryCell {
    fn none() -> RegistryCell {
        RegistryCell { addr: NONE_ADDRESS, node: BuilderNode::default() }
    }

    fn is_none(&self) -> bool {
        self.addr == NONE_ADDRESS
    }

    pub fn insert(&mut self, addr: CompiledAddr) {
        self.addr = addr;
    }
}

#[cfg(test)]
mod tests {
    use super::{Registry, RegistryCache, RegistryCell, RegistryEntry};
    use crate::raw::build::BuilderNode;
    use crate::raw::{Output, Transition};

    fn assert_rejected(entry: RegistryEntry) {
        match entry {
            RegistryEntry::Rejected => {}
            entry => panic!("expected rejected entry, got: {:?}", entry),
        }
    }

    fn assert_not_found(entry: RegistryEntry) {
        match entry {
            RegistryEntry::NotFound(_) => {}
            entry => panic!("expected nout found entry, got: {:?}", entry),
        }
    }

    fn assert_insert_and_found(reg: &mut Registry, bnode: &BuilderNode) {
        match reg.entry(&bnode) {
            RegistryEntry::NotFound(cell) => cell.insert(1234),
            entry => panic!("unexpected not found entry, got: {:?}", entry),
        }
        match reg.entry(&bnode) {
            RegistryEntry::Found(addr) => assert_eq!(addr, 1234),
            entry => panic!("unexpected found entry, got: {:?}", entry),
        }
    }

    #[test]
    fn empty_is_ok() {
        let mut reg = Registry::new(0, 0);
        let bnode = BuilderNode {
            is_final: false,
            final_output: Output::zero(),
            trans: vec![],
        };
        assert_rejected(reg.entry(&bnode));
    }

    #[test]
    fn one_final_is_ok() {
        let mut reg = Registry::new(1, 1);
        let bnode = BuilderNode {
            is_final: true,
            final_output: Output::zero(),
            trans: vec![],
        };
        assert_insert_and_found(&mut reg, &bnode);
    }

    #[test]
    fn one_with_trans_is_ok() {
        let mut reg = Registry::new(1, 1);
        let bnode = BuilderNode {
            is_final: false,
            final_output: Output::zero(),
            trans: vec![Transition {
                addr: 0,
                inp: b'a',
                out: Output::zero(),
            }],
        };
        assert_insert_and_found(&mut reg, &bnode);
        assert_not_found(
            reg.entry(&BuilderNode { is_final: true, ..bnode.clone() }),
        );
        assert_not_found(reg.entry(&BuilderNode {
            trans: vec![Transition {
                addr: 0,
                inp: b'b',
                out: Output::zero(),
            }],
            ..bnode.clone()
        }));
        assert_not_found(reg.entry(&BuilderNode {
            trans: vec![Transition {
                addr: 0,
                inp: b'a',
                out: Output::new(1),
            }],
            ..bnode.clone()
        }));
    }

    #[test]
    fn cache_works() {
        let mut reg = Registry::new(1, 1);

        let bnode1 = BuilderNode { is_final: true, ..BuilderNode::default() };
        assert_insert_and_found(&mut reg, &bnode1);

        let bnode2 =
            BuilderNode { final_output: Output::new(1), ..bnode1.clone() };
        assert_insert_and_found(&mut reg, &bnode2);
        assert_not_found(reg.entry(&bnode1));
    }

    #[test]
    fn promote() {
        let bn = BuilderNode::default();
        let mut bnodes = vec![
            RegistryCell { addr: 1, node: bn.clone() },
            RegistryCell { addr: 2, node: bn.clone() },
            RegistryCell { addr: 3, node: bn.clone() },
            RegistryCell { addr: 4, node: bn.clone() },
        ];
        let mut cache = RegistryCache { cells: &mut bnodes };

        cache.promote(0);
        assert_eq!(cache.cells[0].addr, 1);
        assert_eq!(cache.cells[1].addr, 2);
        assert_eq!(cache.cells[2].addr, 3);
        assert_eq!(cache.cells[3].addr, 4);

        cache.promote(1);
        assert_eq!(cache.cells[0].addr, 2);
        assert_eq!(cache.cells[1].addr, 1);
        assert_eq!(cache.cells[2].addr, 3);
        assert_eq!(cache.cells[3].addr, 4);

        cache.promote(3);
        assert_eq!(cache.cells[0].addr, 4);
        assert_eq!(cache.cells[1].addr, 2);
        assert_eq!(cache.cells[2].addr, 1);
        assert_eq!(cache.cells[3].addr, 3);

        cache.promote(2);
        assert_eq!(cache.cells[0].addr, 1);
        assert_eq!(cache.cells[1].addr, 4);
        assert_eq!(cache.cells[2].addr, 2);
        assert_eq!(cache.cells[3].addr, 3);
    }
}

Coverage Report

Created: 2025-02-21 07:11

Line	Count	Source (jump to first uncovered line)
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 {
30	0	pub fn new(table_size: usize, mru_size: usize) -> Registry {
31	0	let empty_cell = RegistryCell::none();
32	0	let ncells = table_size.checked_mul(mru_size).unwrap();
33	0	Registry { table: vec![empty_cell; ncells], table_size, mru_size }
34	0	}
35
36	0	pub fn entry<'a>(&'a mut self, node: &BuilderNode) -> RegistryEntry<'a> {
37	0	if self.table.is_empty() {
38	0	return RegistryEntry::Rejected;
39	0	}
40	0	let bucket = self.hash(node);
41	0	let start = self.mru_size * bucket;
42	0	let end = start + self.mru_size;
43	0	RegistryCache { cells: &mut self.table[start..end] }.entry(node)
44	0	}
45
46	0	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	0	let mut h = 14695981039346656037;
54	0	h = (h ^ (node.is_final as u64)).wrapping_mul(FNV_PRIME);
55	0	h = (h ^ node.final_output.value()).wrapping_mul(FNV_PRIME);
56	0	for t in &node.trans {
57	0	h = (h ^ (t.inp as u64)).wrapping_mul(FNV_PRIME);
58	0	h = (h ^ t.out.value()).wrapping_mul(FNV_PRIME);
59	0	h = (h ^ (t.addr as u64)).wrapping_mul(FNV_PRIME);
60	0	}
61	0	(h as usize) % self.table_size
62	0	}
63		}
64
65		impl<'a> RegistryCache<'a> {
66	0	fn entry(mut self, node: &BuilderNode) -> RegistryEntry<'a> {
67	0	if self.cells.len() == 1 {
68	0	let cell = &mut self.cells[0];
69	0	if !cell.is_none() && &cell.node == node {
70	0	RegistryEntry::Found(cell.addr)
71		} else {
72	0	cell.node.clone_from(node);
73	0	RegistryEntry::NotFound(cell)
74		}
75	0	} else if self.cells.len() == 2 {
76	0	let cell1 = &mut self.cells[0];
77	0	if !cell1.is_none() && &cell1.node == node {
78	0	return RegistryEntry::Found(cell1.addr);
79	0	}
80	0
81	0	let cell2 = &mut self.cells[1];
82	0	if !cell2.is_none() && &cell2.node == node {
83	0	let addr = cell2.addr;
84	0	self.cells.swap(0, 1);
85	0	return RegistryEntry::Found(addr);
86	0	}
87	0
88	0	self.cells[1].node.clone_from(node);
89	0	self.cells.swap(0, 1);
90	0	RegistryEntry::NotFound(&mut self.cells[0])
91		} else {
92	0	let find = \|c: &RegistryCell\| !c.is_none() && &c.node == node;
93	0	if let Some(i) = self.cells.iter().position(find) {
94	0	let addr = self.cells[i].addr;
95	0	self.promote(i); // most recently used
96	0	RegistryEntry::Found(addr)
97		} else {
98	0	let last = self.cells.len() - 1;
99	0	self.cells[last].node.clone_from(node); // discard LRU
100	0	self.promote(last);
101	0	RegistryEntry::NotFound(&mut self.cells[0])
102		}
103		}
104	0	}
105
106	0	fn promote(&mut self, mut i: usize) {
107	0	assert!(i < self.cells.len());
108	0	while i > 0 {
109	0	self.cells.swap(i - 1, i);
110	0	i -= 1;
111	0	}
112	0	}
113		}
114
115		impl RegistryCell {
116	0	fn none() -> RegistryCell {
117	0	RegistryCell { addr: NONE_ADDRESS, node: BuilderNode::default() }
118	0	}
119
120	0	fn is_none(&self) -> bool {
121	0	self.addr == NONE_ADDRESS
122	0	}
123
124	0	pub fn insert(&mut self, addr: CompiledAddr) {
125	0	self.addr = addr;
126	0	}
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
135		fn assert_rejected(entry: RegistryEntry) {
136		match entry {
137		RegistryEntry::Rejected => {}
138		entry => panic!("expected rejected entry, got: {:?}", entry),
139		}
140		}
141
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
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]
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]
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]
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]
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]
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		}