wnfs_hamt/
hamt.rs

1use super::{HAMT_VERSION, KeyValueChange, Node};
2use crate::{Hasher, serializable::HamtSerializable};
3use anyhow::Result;
4use semver::Version;
5use serde::{Serialize, de::DeserializeOwned};
6use std::hash::Hash;
7use wnfs_common::{
8    BlockStore, Cid, Link, Storable,
9    utils::{Arc, CondSync},
10};
11
12//--------------------------------------------------------------------------------------------------
13// Type Definitions
14//--------------------------------------------------------------------------------------------------
15
16/// Hash Array Mapped Trie (HAMT) is an implementation of an associative array that combines the characteristics
17/// of a hash table and an array mapped trie.
18///
19/// This type wraps the actual implementation which can be found in the [`Node`](crate::Node).
20///
21/// # Examples
22///
23/// ```
24/// use wnfs_hamt::Hamt;
25///
26/// let hamt = Hamt::<String, usize>::new();
27/// println!("HAMT: {:?}", hamt);
28/// ```
29#[derive(Debug, Clone)]
30pub struct Hamt<K: CondSync, V: CondSync, H = blake3::Hasher>
31where
32    H: Hasher + CondSync,
33{
34    pub root: Arc<Node<K, V, H>>,
35    pub version: Version,
36}
37
38//--------------------------------------------------------------------------------------------------
39// Implementations
40//--------------------------------------------------------------------------------------------------
41
42impl<K: CondSync, V: CondSync, H: Hasher + CondSync> Hamt<K, V, H> {
43    /// Creates a new empty HAMT.
44    ///
45    /// # Examples
46    ///
47    /// ```
48    /// use wnfs_hamt::Hamt;
49    ///
50    /// let hamt = Hamt::<String, usize>::new();
51    /// println!("HAMT: {:?}", hamt);
52    /// ```
53    pub fn new() -> Self {
54        Self {
55            root: Arc::new(Node::default()),
56            version: HAMT_VERSION,
57        }
58    }
59
60    /// Creates a new `HAMT` with the given root node.
61    ///
62    /// # Examples
63    ///
64    /// ```
65    /// use std::sync::Arc;
66    /// use wnfs_hamt::{Hamt, Node};
67    ///
68    /// let hamt = Hamt::<String, usize>::with_root(Arc::new(Node::default()));
69    ///
70    /// println!("HAMT: {:?}", hamt);
71    /// ```
72    pub fn with_root(root: Arc<Node<K, V, H>>) -> Self {
73        Self {
74            root,
75            version: HAMT_VERSION,
76        }
77    }
78
79    /// Gets the difference between two HAMTs at the key-value level.
80    ///
81    /// # Examples
82    ///
83    /// ```
84    /// use std::sync::Arc;
85    /// use wnfs_hamt::{Hamt, Node};
86    /// use wnfs_common::MemoryBlockStore;
87    ///
88    /// #[async_std::main]
89    /// async fn main() {
90    ///     let store = &MemoryBlockStore::default();
91    ///
92    ///     let main_hamt = Hamt::<String, usize>::with_root({
93    ///         let mut node = Arc::new(Node::default());
94    ///         node.set("foo".into(), 400, store).await.unwrap();
95    ///         node.set("bar".into(), 500, store).await.unwrap();
96    ///         node
97    ///     });
98    ///
99    ///     let other_hamt = Hamt::<String, usize>::with_root({
100    ///         let mut node = Arc::new(Node::default());
101    ///         node.set("foo".into(), 200, store).await.unwrap();
102    ///         node.set("qux".into(), 600, store).await.unwrap();
103    ///         node
104    ///     });
105    ///
106    ///     let diff = main_hamt.diff(&other_hamt, store).await.unwrap();
107    ///
108    ///     println!("diff: {:#?}", diff);
109    /// }
110    pub async fn diff(
111        &self,
112        other: &Self,
113        store: &impl BlockStore,
114    ) -> Result<Vec<KeyValueChange<K, V>>>
115    where
116        K: Storable + Clone + Eq + Hash + AsRef<[u8]>,
117        V: Storable + Clone + Eq,
118        K::Serializable: Serialize + DeserializeOwned,
119        V::Serializable: Serialize + DeserializeOwned,
120    {
121        super::diff(
122            Link::from(Arc::clone(&self.root)),
123            Link::from(Arc::clone(&other.root)),
124            store,
125        )
126        .await
127    }
128}
129
130impl<K, V, H> Storable for Hamt<K, V, H>
131where
132    K: Storable + CondSync,
133    V: Storable + CondSync,
134    K::Serializable: Serialize + DeserializeOwned,
135    V::Serializable: Serialize + DeserializeOwned,
136    H: Hasher + CondSync,
137{
138    type Serializable = HamtSerializable<K::Serializable, V::Serializable>;
139
140    async fn to_serializable(&self, store: &impl BlockStore) -> Result<Self::Serializable> {
141        Ok(HamtSerializable {
142            root: self.root.to_serializable(store).await?,
143            version: self.version.clone(),
144            structure: "hamt".to_string(),
145        })
146    }
147
148    async fn from_serializable(
149        _cid: Option<&Cid>,
150        serializable: Self::Serializable,
151    ) -> Result<Self> {
152        Ok(Self {
153            root: Arc::new(Node::from_serializable(None, serializable.root).await?),
154            version: serializable.version,
155        })
156    }
157}
158
159impl<K: CondSync, V: CondSync, H: Hasher + CondSync> Default for Hamt<K, V, H> {
160    fn default() -> Self {
161        Self::new()
162    }
163}
164
165impl<K: CondSync, V: CondSync, H> PartialEq for Hamt<K, V, H>
166where
167    K: Storable + PartialEq + CondSync,
168    V: Storable + PartialEq + CondSync,
169    K::Serializable: Serialize + DeserializeOwned,
170    V::Serializable: Serialize + DeserializeOwned,
171    H: Hasher + CondSync,
172{
173    fn eq(&self, other: &Self) -> bool {
174        self.root == other.root && self.version == other.version
175    }
176}
177
178//--------------------------------------------------------------------------------------------------
179// Tests
180//--------------------------------------------------------------------------------------------------
181
182#[cfg(test)]
183mod tests {
184    use super::*;
185    use wnfs_common::MemoryBlockStore;
186
187    #[async_std::test]
188    async fn hamt_can_encode_decode_as_cbor() {
189        let store = &MemoryBlockStore::default();
190        let root = Arc::new(Node::default());
191        let hamt: Hamt<String, i32> = Hamt::with_root(root);
192
193        let hamt_cid = hamt.store(store).await.unwrap();
194        let decoded_hamt = Hamt::load(&hamt_cid, store).await.unwrap();
195
196        assert_eq!(hamt, decoded_hamt);
197    }
198}
199
200#[cfg(test)]
201mod snapshot_tests {
202    use super::*;
203    use wnfs_common::utils::SnapshotBlockStore;
204
205    #[async_std::test]
206    async fn test_hamt() {
207        let store = &SnapshotBlockStore::default();
208        let node = &mut Arc::new(Node::<[u8; 4], String>::default());
209        for i in 0..99_u32 {
210            node.set(i.to_le_bytes(), i.to_string(), store)
211                .await
212                .unwrap();
213        }
214
215        let hamt = Hamt::with_root(Arc::clone(node));
216        let cid = hamt.store(store).await.unwrap();
217        let hamt = store.get_block_snapshot(&cid).await.unwrap();
218
219        insta::assert_json_snapshot!(hamt);
220    }
221}
wnfs_hamt/hamt.rs

wnfs_hamt/
hamt.rs
