wnfs_hamt/
pointer.rs

1use super::{HAMT_VALUES_BUCKET_SIZE, Node, error::HamtError, hash::Hasher};
2use crate::serializable::PointerSerializable;
3use anyhow::Result;
4use serde::{Serialize, de::DeserializeOwned};
5use std::fmt::Debug;
6use wnfs_common::{
7    BlockStore, Cid, Link, Storable,
8    utils::{Arc, CondSync, error},
9};
10
11//--------------------------------------------------------------------------------------------------
12// Type Definitions
13//--------------------------------------------------------------------------------------------------
14
15/// A key-value pair type.
16///
17/// # Examples
18///
19/// ```
20/// use wnfs_hamt::Pair;
21///
22/// let pair = Pair::new("key", "value");
23///
24/// assert_eq!(pair.key, "key");
25/// assert_eq!(pair.value, "value");
26/// ```
27#[derive(Debug, Clone, PartialEq, Eq)]
28pub struct Pair<K, V> {
29    pub key: K,
30    pub value: V,
31}
32
33/// Each bit in the bitmask of a node maps a `Pointer` in the HAMT structure.
34/// A `Pointer` can be either a link to a child node or a collection of key-value pairs.
35pub(crate) enum Pointer<K: CondSync, V: CondSync, H: Hasher + CondSync> {
36    Values(Vec<Pair<K, V>>),
37    Link(Link<Arc<Node<K, V, H>>>),
38}
39
40//--------------------------------------------------------------------------------------------------
41// Implementations
42//--------------------------------------------------------------------------------------------------
43
44impl<K, V> Pair<K, V> {
45    /// Create a new `Pair` from a key and value.
46    ///
47    /// # Examples
48    ///
49    /// ```
50    /// use wnfs_hamt::Pair;
51    ///
52    /// let pair = Pair::new("key", "value");
53    ///
54    /// assert_eq!(pair.key, "key");
55    /// assert_eq!(pair.value, "value");
56    /// ```
57    pub fn new(key: K, value: V) -> Self {
58        Self { key, value }
59    }
60}
61
62impl<K: CondSync, V: CondSync, H: Hasher + CondSync> Pointer<K, V, H> {
63    /// Converts a Link pointer to a canonical form to ensure consistent tree representation after deletes.
64    pub async fn canonicalize(self, store: &impl BlockStore) -> Result<Option<Self>>
65    where
66        K: Storable + Clone + AsRef<[u8]>,
67        V: Storable + Clone,
68        K::Serializable: Serialize + DeserializeOwned,
69        V::Serializable: Serialize + DeserializeOwned,
70        H: CondSync,
71    {
72        match self {
73            Pointer::Link(link) => {
74                let node = link.resolve_owned_value(store).await?;
75                match node.pointers.len() {
76                    0 => Ok(None),
77                    1 if matches!(node.pointers[0], Pointer::Values(_)) => {
78                        Ok(Some(node.pointers[0].clone()))
79                    }
80                    2..=HAMT_VALUES_BUCKET_SIZE if node.count_values().is_ok() => {
81                        // Collect all the values of the node.
82                        let mut values = node
83                            .pointers
84                            .iter()
85                            .filter_map(|p| match p {
86                                Pointer::Values(values) => Some(values.clone()),
87                                _ => None,
88                            })
89                            .flatten()
90                            .collect::<Vec<_>>();
91
92                        // Bail if it's more values that we can fit into a bucket
93                        if values.len() > HAMT_VALUES_BUCKET_SIZE {
94                            return Ok(Some(Pointer::Link(Link::from(node))));
95                        }
96
97                        values.sort_unstable_by(|a, b| {
98                            H::hash(&a.key).partial_cmp(&H::hash(&b.key)).unwrap()
99                        });
100
101                        Ok(Some(Pointer::Values(values)))
102                    }
103                    _ => Ok(Some(Pointer::Link(Link::from(node)))),
104                }
105            }
106            _ => error(HamtError::NonCanonicalizablePointer),
107        }
108    }
109}
110
111impl<K, V, H> Storable for Pointer<K, V, H>
112where
113    K: Storable + CondSync,
114    V: Storable + CondSync,
115    K::Serializable: Serialize + DeserializeOwned,
116    V::Serializable: Serialize + DeserializeOwned,
117    H: Hasher + CondSync,
118{
119    type Serializable = PointerSerializable<K::Serializable, V::Serializable>;
120
121    async fn to_serializable(&self, store: &impl BlockStore) -> Result<Self::Serializable> {
122        Ok(match self {
123            Pointer::Values(values) => {
124                let mut serializables = Vec::with_capacity(values.len());
125                for pair in values.iter() {
126                    serializables.push(pair.to_serializable(store).await?);
127                }
128                PointerSerializable::Values(serializables)
129            }
130            Pointer::Link(link) => {
131                let cid = link.resolve_cid(store).await?;
132                PointerSerializable::Link(cid)
133            }
134        })
135    }
136
137    async fn from_serializable(
138        _cid: Option<&Cid>,
139        serializable: Self::Serializable,
140    ) -> Result<Self> {
141        Ok(match serializable {
142            PointerSerializable::Values(serializables) => {
143                let mut values = Vec::with_capacity(serializables.len());
144                for serializable in serializables {
145                    values.push(Pair::from_serializable(None, serializable).await?);
146                }
147                Self::Values(values)
148            }
149            PointerSerializable::Link(cid) => Self::Link(Link::from_cid(cid)),
150        })
151    }
152}
153
154impl<K, V> Storable for Pair<K, V>
155where
156    K: Storable + CondSync,
157    V: Storable + CondSync,
158    K::Serializable: Serialize + DeserializeOwned,
159    V::Serializable: Serialize + DeserializeOwned,
160{
161    type Serializable = (K::Serializable, V::Serializable);
162
163    async fn to_serializable(&self, store: &impl BlockStore) -> Result<Self::Serializable> {
164        let key = self.key.to_serializable(store).await?;
165        let value = self.value.to_serializable(store).await?;
166        Ok((key, value))
167    }
168
169    async fn from_serializable(
170        _cid: Option<&Cid>,
171        (key, value): Self::Serializable,
172    ) -> Result<Self> {
173        let key = K::from_serializable(None, key).await?;
174        let value = V::from_serializable(None, value).await?;
175        Ok(Pair { key, value })
176    }
177}
178
179impl<K: Clone + CondSync, V: Clone + CondSync, H: Hasher + CondSync> Clone for Pointer<K, V, H> {
180    fn clone(&self) -> Self {
181        match self {
182            Self::Values(arg0) => Self::Values(arg0.clone()),
183            Self::Link(arg0) => Self::Link(arg0.clone()),
184        }
185    }
186}
187
188impl<K: Debug + CondSync, V: Debug + CondSync, H: Hasher + CondSync> std::fmt::Debug
189    for Pointer<K, V, H>
190{
191    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
192        match self {
193            Self::Values(arg0) => f.debug_tuple("Values").field(arg0).finish(),
194            Self::Link(arg0) => f.debug_tuple("Link").field(arg0).finish(),
195        }
196    }
197}
198
199impl<K: CondSync, V: CondSync, H: Hasher + CondSync> Default for Pointer<K, V, H> {
200    fn default() -> Self {
201        Pointer::Values(Vec::new())
202    }
203}
204
205impl<K, V, H: Hasher + CondSync> PartialEq for Pointer<K, V, H>
206where
207    K: Storable + PartialEq + CondSync,
208    V: Storable + PartialEq + CondSync,
209    K::Serializable: Serialize + DeserializeOwned,
210    V::Serializable: Serialize + DeserializeOwned,
211{
212    fn eq(&self, other: &Self) -> bool {
213        match (self, other) {
214            (Pointer::Values(vals), Pointer::Values(other_vals)) => vals == other_vals,
215            (Pointer::Link(link), Pointer::Link(other_link)) => link == other_link,
216            _ => false,
217        }
218    }
219}
220
221//--------------------------------------------------------------------------------------------------
222// Tests
223//--------------------------------------------------------------------------------------------------
224
225#[cfg(test)]
226mod tests {
227    use super::*;
228    use testresult::TestResult;
229    use wnfs_common::MemoryBlockStore;
230
231    #[async_std::test]
232    async fn pointer_can_encode_decode_as_cbor() -> TestResult {
233        let store = &MemoryBlockStore::default();
234        let pointer: Pointer<String, i32, blake3::Hasher> = Pointer::Values(vec![
235            Pair {
236                key: "James".into(),
237                value: 4500,
238            },
239            Pair {
240                key: "Peter".into(),
241                value: 2000,
242            },
243        ]);
244
245        let pointer_cid = pointer.store(store).await?;
246        let decoded_pointer =
247            Pointer::<String, i32, blake3::Hasher>::load(&pointer_cid, store).await?;
248
249        assert_eq!(pointer, decoded_pointer);
250
251        Ok(())
252    }
253}
254
255#[cfg(test)]
256mod snapshot_tests {
257    use super::*;
258    use testresult::TestResult;
259    use wnfs_common::utils::SnapshotBlockStore;
260
261    #[async_std::test]
262    async fn test_pointer() -> TestResult {
263        let store = &SnapshotBlockStore::default();
264        let pointer: Pointer<String, i32, blake3::Hasher> = Pointer::Values(vec![
265            Pair {
266                key: "James".into(),
267                value: 4500,
268            },
269            Pair {
270                key: "Peter".into(),
271                value: 2000,
272            },
273        ]);
274
275        let cid = pointer.store(store).await?;
276        let ptr = store.get_block_snapshot(&cid).await?;
277
278        insta::assert_json_snapshot!(ptr);
279
280        Ok(())
281    }
282}
wnfs_hamt/pointer.rs

wnfs_hamt/
pointer.rs
