champ_trie/lib.rs
1//! Persistent hash map based on CHAMP.
2//!
3//! CHAMP (Compressed Hash-Array Mapped Prefix-tree) is a refined HAMT that
4//! guarantees **canonical form**: the same set of key-value pairs always
5//! produces the same trie structure, regardless of insertion order.
6//!
7//! # Key properties
8//!
9//! - **Canonical form**: same contents = same structure
10//! - **O(1) structural equality**: via incrementally maintained `AdHash`
11//! - **COW structural sharing**: cheap copy, mutate-on-write
12//! - **Zero `unsafe`**: enforced by `#![forbid(unsafe_code)]`
13//!
14//! # References
15//!
16//! - Steindorfer & Vinju, 2015 — "Optimizing Hash-Array Mapped Tries
17//! for Fast and Lean Immutable JVM Collections", OOPSLA 2015
18//! - Bagwell, 2001 — "Ideal Hash Trees"
19
20#![forbid(unsafe_code)]
21#![deny(missing_docs)]
22#![allow(clippy::module_name_repetitions)]
23
24use std::fmt;
25
26use safe_bump::Idx;
27
28pub mod adhash;
29pub mod iter;
30pub mod node;
31pub mod store;
32
33mod arena;
34mod arena_sync;
35mod map;
36mod map_sync;
37mod ops;
38
39#[cfg(test)]
40mod tests;
41
42pub use map::ChampMap;
43pub use map_sync::ChampMapSync;
44
45/// Saved map state for rollback.
46///
47/// Created by [`ChampMap::checkpoint`] or [`ChampMapSync::checkpoint`].
48/// Restoring via `rollback` discards all changes made after the checkpoint.
49pub struct ChampCheckpoint<K, V> {
50 /// Three-arena store checkpoint.
51 pub store: store::StoreCheckpoint<K, V>,
52 /// Root node index at checkpoint time.
53 pub root: Option<Idx<node::Node<K, V>>>,
54 /// Entry count at checkpoint time.
55 pub size: usize,
56 /// `AdHash` at checkpoint time.
57 pub adhash: u64,
58}
59
60// ChampCheckpoint contains only indices and primitives — no actual K/V data.
61
62impl<K, V> Clone for ChampCheckpoint<K, V> {
63 fn clone(&self) -> Self {
64 *self
65 }
66}
67
68impl<K, V> Copy for ChampCheckpoint<K, V> {}
69
70impl<K, V> fmt::Debug for ChampCheckpoint<K, V> {
71 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
72 f.debug_struct("ChampCheckpoint")
73 .field("size", &self.size)
74 .field("adhash", &self.adhash)
75 .finish_non_exhaustive()
76 }
77}