containers.tngl.sh
A trie in Rust
blackson.tngl.sh
1pub(crate) const SHIFT: u8 = 4;
2pub(crate) const SIZE: usize = 1 << SHIFT;
3pub(crate) const MASK: usize = SIZE - 1;
4// The number of chunks that the key is divided into. Also the maximum depth of the map.
5pub(crate) const MAX_DEPTH: usize = usize::BITS as usize / SHIFT as usize;
6
7/// Allows us to extract nybbles (4 bits at a time).
8///
9/// Should be implemented for lists of bytes, byte strings,
10/// as well as basic integer types.
11///
12/// Note: the `PartialEq` bound is included as a convenience,
13/// since we always need it in practice.
14///
15/// Note: we accept and return `usize` rather than `u8` as a convenience because
16/// we wish to use these for indices without casting.
17pub trait Chunk: PartialEq {
18 /// Note: we accept and return `usize` rather than `u8` as a convenience because
19 /// we wish to use these for indices without casting.
20 fn chunk(&self, idx: usize) -> usize;
21}
22
23impl Chunk for Vec<u8> {
24 fn chunk(&self, idx: usize) -> usize {
25 (self[idx / 2] >> ((idx % 2) * 4)) as usize
26 }
27}
28
29impl<const N: usize> Chunk for [u8; N] {
30 fn chunk(&self, idx: usize) -> usize {
31 (self[idx / 2] >> ((idx % 2) * 4)) as usize
32 }
33}
34
35impl Chunk for [u8] {
36 fn chunk(&self, idx: usize) -> usize {
37 (self[idx / 2] >> ((idx % 2) * 4)) as usize
38 }
39}
40
41impl Chunk for usize {
42 fn chunk(&self, idx: usize) -> usize {
43 let sh = usize::BITS as u8 - (SHIFT * (idx as u8 + 1));
44 (self >> sh) & MASK
45 }
46}
47
48impl Chunk for u32 {
49 fn chunk(&self, idx: usize) -> usize {
50 let sh = u32::BITS as u8 - (SHIFT * (idx as u8 + 1));
51 ((self >> sh) & MASK as u32) as usize
52 }
53}
54
55impl Chunk for i32 {
56 fn chunk(&self, idx: usize) -> usize {
57 let sh = i32::BITS as u8 - (SHIFT * (idx as u8 + 1));
58 ((*self as u32 >> sh) & MASK as u32) as usize
59 }
60}
61
62impl Chunk for u64 {
63 fn chunk(&self, idx: usize) -> usize {
64 let sh = u64::BITS as u8 - (SHIFT * (idx as u8 + 1));
65 ((self >> sh) & MASK as u64) as usize
66 }
67}
68
69impl Chunk for i64 {
70 fn chunk(&self, idx: usize) -> usize {
71 let sh = i64::BITS as u8 - (SHIFT * (idx as u8 + 1));
72 (((*self) as u64 >> sh) & MASK as u64) as usize
73 }
74}