champ_trie/
node.rs

1//! CHAMP trie node types and bitmap helpers.
2
3use std::fmt;
4
5use safe_bump::Idx;
6
7/// Bits per trie level (5 → 32-way branching).
8pub const BITS_PER_LEVEL: u32 = 5;
9
10/// Maximum bit-shift value (depth 12, last level uses 4 bits).
11pub const MAX_SHIFT: u32 = 60;
12
13/// Inline entry storing a key-value pair with its precomputed hash.
14pub struct Entry<K, V> {
15    /// Precomputed 64-bit hash of the key.
16    pub hash: u64,
17    /// The key.
18    pub key: K,
19    /// The value.
20    pub value: V,
21}
22
23/// CHAMP trie node.
24///
25/// Two variants maintain the canonical form invariant:
26/// - [`Inner`](Self::Inner) — bitmap-compressed node at depth `d < D`
27/// - [`Collision`](Self::Collision) — linear node for full 64-bit hash collisions
28pub enum Node<K, V> {
29    /// Bitmap-compressed inner node.
30    ///
31    /// Invariant: `data_map & node_map == 0` (disjoint positions).
32    Inner {
33        /// Bitmap of positions occupied by inline entries.
34        data_map: u32,
35        /// Bitmap of positions occupied by child subtrees.
36        node_map: u32,
37        /// Index of the first inline entry in the entries arena.
38        data_start: Idx<Entry<K, V>>,
39        /// Index of the first child pointer in the children arena.
40        children_start: Idx<Idx<Self>>,
41        /// `AdHash` of this subtree.
42        adhash: u64,
43    },
44    /// Collision node for keys sharing the same 64-bit hash.
45    ///
46    /// Invariant: `entries_len >= 2`.
47    Collision {
48        /// The shared 64-bit hash value.
49        hash: u64,
50        /// Index of the first entry in the entries arena.
51        entries_start: Idx<Entry<K, V>>,
52        /// Number of collision entries.
53        entries_len: u8,
54        /// `AdHash` of this subtree.
55        adhash: u64,
56    },
57}
58
59// ---------------------------------------------------------------------------
60// Bitmap helpers
61// ---------------------------------------------------------------------------
62
63/// Extracts the 5-bit hash fragment at the given bit-shift depth.
64#[inline]
65#[must_use]
66pub const fn fragment(hash: u64, shift: u32) -> u32 {
67    ((hash >> shift) & 0x1F) as u32
68}
69
70/// Returns the single-bit mask for the given fragment (0..31).
71#[inline]
72#[must_use]
73pub const fn mask(frag: u32) -> u32 {
74    1 << frag
75}
76
77/// Returns the compact index of `bit` within `bitmap`.
78///
79/// Counts the number of set bits below `bit`.
80#[inline]
81#[must_use]
82pub const fn index(bitmap: u32, bit: u32) -> usize {
83    (bitmap & (bit - 1)).count_ones() as usize
84}
85
86/// Offsets a base index by `n` positions.
87#[inline]
88#[must_use]
89pub const fn offset<T>(base: Idx<T>, n: usize) -> Idx<T> {
90    Idx::from_raw(base.into_raw() + n)
91}
92
93// ---------------------------------------------------------------------------
94// Node accessors
95// ---------------------------------------------------------------------------
96
97impl<K, V> Node<K, V> {
98    /// Returns the `AdHash` of this node's subtree.
99    #[must_use]
100    pub const fn adhash(&self) -> u64 {
101        match self {
102            Self::Inner { adhash, .. } | Self::Collision { adhash, .. } => *adhash,
103        }
104    }
105
106    /// Returns the number of inline data entries.
107    #[must_use]
108    pub const fn data_len(&self) -> usize {
109        match self {
110            Self::Inner { data_map, .. } => data_map.count_ones() as usize,
111            Self::Collision { entries_len, .. } => *entries_len as usize,
112        }
113    }
114
115    /// Returns the number of child subtrees (always 0 for collision nodes).
116    #[must_use]
117    pub const fn children_len(&self) -> usize {
118        match self {
119            Self::Inner { node_map, .. } => node_map.count_ones() as usize,
120            Self::Collision { .. } => 0,
121        }
122    }
123}
124
125// ---------------------------------------------------------------------------
126// Manual trait impls — avoid false `K: Trait, V: Trait` bounds.
127// Node contains only indices (Copy) and primitives — no actual K/V data.
128// ---------------------------------------------------------------------------
129
130impl<K, V> Clone for Node<K, V> {
131    fn clone(&self) -> Self {
132        *self
133    }
134}
135
136impl<K, V> Copy for Node<K, V> {}
137
138impl<K, V> fmt::Debug for Node<K, V> {
139    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
140        match self {
141            Self::Inner {
142                data_map,
143                node_map,
144                adhash,
145                ..
146            } => f
147                .debug_struct("Inner")
148                .field("data_map", &format_args!("{data_map:#034b}"))
149                .field("node_map", &format_args!("{node_map:#034b}"))
150                .field("adhash", adhash)
151                .finish(),
152            Self::Collision {
153                hash,
154                entries_len,
155                adhash,
156                ..
157            } => f
158                .debug_struct("Collision")
159                .field("hash", hash)
160                .field("entries_len", entries_len)
161                .field("adhash", adhash)
162                .finish(),
163        }
164    }
165}
champ_trie/node.rs

champ_trie/
node.rs
