champ_trie/
map_sync.rs

1//! Multi-threaded CHAMP map.
2
3use std::fmt;
4use std::hash::Hash;
5use std::ops;
6
7use safe_bump::Idx;
8
9use crate::ChampCheckpoint;
10use crate::adhash;
11use crate::arena_sync::ChampArenaSync;
12use crate::iter::Iter;
13use crate::node::{self, Entry, Node};
14use crate::ops::get::get_recursive;
15use crate::ops::insert::insert_recursive;
16use crate::ops::remove::{RemoveOutcome, remove_recursive};
17use crate::store::ChampStore;
18
19/// Persistent hash map based on a CHAMP trie, multi-threaded.
20///
21/// Identical API to [`ChampMap`](crate::ChampMap) but backed by
22/// [`SharedArena`](safe_bump::SharedArena) for `Send + Sync` support.
23pub struct ChampMapSync<K, V> {
24    store: ChampArenaSync<K, V>,
25    root: Option<safe_bump::Idx<crate::node::Node<K, V>>>,
26    size: usize,
27    adhash: u64,
28}
29
30// ---------------------------------------------------------------------------
31// Construction & accessors — no trait bounds
32// ---------------------------------------------------------------------------
33
34impl<K, V> ChampMapSync<K, V> {
35    /// Creates an empty map.
36    #[must_use]
37    pub const fn new() -> Self {
38        Self {
39            store: ChampArenaSync::new(),
40            root: None,
41            size: 0,
42            adhash: 0,
43        }
44    }
45
46    /// Returns the number of key-value pairs.
47    #[must_use]
48    pub const fn len(&self) -> usize {
49        self.size
50    }
51
52    /// Returns `true` if the map contains no entries.
53    #[must_use]
54    pub const fn is_empty(&self) -> bool {
55        self.size == 0
56    }
57
58    /// Returns the current `AdHash` value.
59    #[must_use]
60    pub const fn adhash(&self) -> u64 {
61        self.adhash
62    }
63
64    /// Saves the current map state for later rollback.
65    #[must_use]
66    pub fn checkpoint(&self) -> ChampCheckpoint<K, V> {
67        ChampCheckpoint {
68            store: self.store.checkpoint(),
69            root: self.root,
70            size: self.size,
71            adhash: self.adhash,
72        }
73    }
74
75    /// Returns the total number of allocated items in each arena:
76    /// `(nodes, entries, children)`.
77    ///
78    /// Includes dead COW copies — reflects true memory footprint.
79    #[must_use]
80    pub fn arena_len(&self) -> (usize, usize, usize) {
81        self.store.arena_len()
82    }
83
84    /// Restores the map to a previously saved checkpoint.
85    pub fn rollback(&mut self, cp: ChampCheckpoint<K, V>) {
86        self.store.rollback(cp.store);
87        self.root = cp.root;
88        self.size = cp.size;
89        self.adhash = cp.adhash;
90    }
91}
92
93// ---------------------------------------------------------------------------
94// Read operations
95// ---------------------------------------------------------------------------
96
97impl<K: Hash + Eq, V> ChampMapSync<K, V> {
98    /// Returns a reference to the value associated with `key`.
99    #[must_use]
100    pub fn get(&self, key: &K) -> Option<&V> {
101        let root = self.root?;
102        get_recursive(&self.store, root, adhash::hash_one(key), key, 0)
103    }
104
105    /// Returns `true` if the map contains the given key.
106    #[must_use]
107    pub fn contains_key(&self, key: &K) -> bool {
108        self.get(key).is_some()
109    }
110}
111
112// ---------------------------------------------------------------------------
113// Write operations
114// ---------------------------------------------------------------------------
115
116impl<K: Hash + Eq + Clone, V: Hash + Clone> ChampMapSync<K, V> {
117    /// Inserts a key-value pair into the map.
118    ///
119    /// Returns `None` if the key was new, or `Some(old_value)` if an existing
120    /// value was replaced.
121    ///
122    /// # Panics
123    ///
124    /// Panics if internal arena allocation returns an unexpected `None`.
125    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
126        let hash = adhash::hash_one(&key);
127        let entry = Entry { hash, key, value };
128
129        if let Some(root) = self.root {
130            let outcome = insert_recursive(&mut self.store, root, entry, 0);
131            self.root = Some(outcome.node);
132            self.adhash = self.adhash.wrapping_add(outcome.adhash_delta);
133            if outcome.old_value.is_none() {
134                self.size += 1;
135            }
136            outcome.old_value
137        } else {
138            let value_hash = adhash::hash_one(&entry.value);
139            let contribution = adhash::entry_adhash(hash, value_hash);
140            let frag = node::fragment(hash, 0);
141            let bit = node::mask(frag);
142            let data_start = self
143                .store
144                .alloc_entries(std::iter::once(entry))
145                .expect("single entry");
146            let new_node = self.store.alloc_node(Node::Inner {
147                data_map: bit,
148                node_map: 0,
149                data_start,
150                children_start: Idx::from_raw(0),
151                adhash: contribution,
152            });
153            self.root = Some(new_node);
154            self.size = 1;
155            self.adhash = contribution;
156            None
157        }
158    }
159
160    /// Removes a key from the map. Returns the removed value, or `None` if
161    /// the key was not present.
162    pub fn remove(&mut self, key: &K) -> Option<V> {
163        let root = self.root?;
164        let hash = adhash::hash_one(key);
165        match remove_recursive(&mut self.store, root, hash, key, 0) {
166            RemoveOutcome::NotFound => None,
167            RemoveOutcome::Removed {
168                node,
169                adhash_delta,
170                removed_value,
171            } => {
172                self.root = node;
173                self.size -= 1;
174                self.adhash = self.adhash.wrapping_sub(adhash_delta);
175                Some(removed_value)
176            }
177        }
178    }
179}
180
181// ---------------------------------------------------------------------------
182// Iterator stubs
183// ---------------------------------------------------------------------------
184
185impl<K, V> ChampMapSync<K, V> {
186    /// Returns an iterator over `(&K, &V)` pairs.
187    #[must_use]
188    pub fn iter(&self) -> Iter<'_, K, V> {
189        Iter::new(&self.store, self.root)
190    }
191}
192
193// ---------------------------------------------------------------------------
194// Trait impls
195// ---------------------------------------------------------------------------
196
197impl<K, V> Default for ChampMapSync<K, V> {
198    fn default() -> Self {
199        Self::new()
200    }
201}
202
203impl<K, V> fmt::Debug for ChampMapSync<K, V> {
204    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
205        f.debug_struct("ChampMapSync")
206            .field("len", &self.size)
207            .field("adhash", &format_args!("{:#018x}", self.adhash))
208            .finish_non_exhaustive()
209    }
210}
211
212impl<K: Hash + Eq + Clone, V: Hash + Clone> Extend<(K, V)> for ChampMapSync<K, V> {
213    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
214        for (k, v) in iter {
215            self.insert(k, v);
216        }
217    }
218}
219
220impl<K: Hash + Eq + Clone, V: Hash + Clone> FromIterator<(K, V)> for ChampMapSync<K, V> {
221    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
222        let mut map = Self::new();
223        map.extend(iter);
224        map
225    }
226}
227
228impl<K: Hash + Eq, V> ops::Index<&K> for ChampMapSync<K, V> {
229    type Output = V;
230
231    fn index(&self, key: &K) -> &V {
232        self.get(key).expect("key not found")
233    }
234}
235
236impl<'a, K, V> IntoIterator for &'a ChampMapSync<K, V> {
237    type Item = (&'a K, &'a V);
238    type IntoIter = Iter<'a, K, V>;
239
240    fn into_iter(self) -> Iter<'a, K, V> {
241        self.iter()
242    }
243}
champ_trie/map_sync.rs

champ_trie/
map_sync.rs
