champ_trie/
store.rs

1//! Storage abstraction for CHAMP trie operations.
2
3use safe_bump::{Checkpoint, Idx};
4
5use crate::node::{Entry, Node};
6
7/// Saved state of the three storage arenas.
8pub struct StoreCheckpoint<K, V> {
9    /// Nodes arena checkpoint.
10    pub nodes: Checkpoint<Node<K, V>>,
11    /// Entries arena checkpoint.
12    pub entries: Checkpoint<Entry<K, V>>,
13    /// Children arena checkpoint.
14    pub children: Checkpoint<Idx<Node<K, V>>>,
15}
16
17// StoreCheckpoint contains only Checkpoint<T> values (Copy) — no K/V data.
18
19impl<K, V> Clone for StoreCheckpoint<K, V> {
20    fn clone(&self) -> Self {
21        *self
22    }
23}
24
25impl<K, V> Copy for StoreCheckpoint<K, V> {}
26
27/// Storage backend for CHAMP operations.
28///
29/// Abstracts over [`Arena`](safe_bump::Arena) (single-thread) and
30/// [`SharedArena`](safe_bump::SharedArena) (multi-thread) backends.
31pub trait ChampStore<K, V> {
32    /// Allocates a single node, returning its index.
33    fn alloc_node(&mut self, node: Node<K, V>) -> Idx<Node<K, V>>;
34
35    /// Returns a reference to the node at `idx`.
36    fn get_node(&self, idx: Idx<Node<K, V>>) -> &Node<K, V>;
37
38    /// Allocates a contiguous block of entries, returning the index of the
39    /// first one. Returns `None` if the iterator is empty.
40    fn alloc_entries(
41        &mut self,
42        iter: impl IntoIterator<Item = Entry<K, V>>,
43    ) -> Option<Idx<Entry<K, V>>>;
44
45    /// Returns a reference to the entry at `idx`.
46    fn get_entry(&self, idx: Idx<Entry<K, V>>) -> &Entry<K, V>;
47
48    /// Allocates a contiguous block of child node indices, returning the
49    /// index of the first one. Returns `None` if the iterator is empty.
50    fn alloc_children(
51        &mut self,
52        iter: impl IntoIterator<Item = Idx<Node<K, V>>>,
53    ) -> Option<Idx<Idx<Node<K, V>>>>;
54
55    /// Returns a reference to the child index at `idx`.
56    fn get_child(&self, idx: Idx<Idx<Node<K, V>>>) -> &Idx<Node<K, V>>;
57
58    /// Saves the current state of all three arenas.
59    fn checkpoint(&self) -> StoreCheckpoint<K, V>;
60
61    /// Rolls back all three arenas to a previous checkpoint.
62    fn rollback(&mut self, cp: StoreCheckpoint<K, V>);
63
64    /// Returns the total number of allocated items in each arena:
65    /// `(nodes, entries, children)`.
66    ///
67    /// Includes dead COW copies — reflects true memory footprint.
68    fn arena_len(&self) -> (usize, usize, usize);
69}
champ_trie/store.rs

champ_trie/
store.rs
