ipld_collections/
list.rs

1use libipld::cache::Cache;
2use libipld::cache::IpldCache;
3use libipld::cbor::DagCbor;
4use libipld::cbor::DagCborCodec;
5use libipld::cid::Cid;
6use libipld::error::Result;
7use libipld::ipld::Ipld;
8use libipld::multihash::Code;
9use libipld::prelude::{Decode, Encode};
10use libipld::store::Store;
11use libipld::store::StoreParams;
12use libipld::DagCbor;
13
14#[derive(Clone, Debug, DagCbor)]
15pub enum Data<T: DagCbor> {
16    Value(T),
17    Link(Cid),
18}
19
20impl<T: DagCbor> Data<T> {
21    fn value(&self) -> Option<&T> {
22        if let Self::Value(value) = self {
23            Some(value)
24        } else {
25            None
26        }
27    }
28
29    fn cid(&self) -> Option<&Cid> {
30        if let Self::Link(cid) = self {
31            Some(cid)
32        } else {
33            None
34        }
35    }
36}
37
38#[derive(Clone, Debug, DagCbor)]
39pub struct Node<T: DagCbor> {
40    width: u32,
41    height: u32,
42    data: Vec<Data<T>>,
43}
44
45impl<T: DagCbor> Node<T> {
46    fn new(width: u32, height: u32, data: Vec<Data<T>>) -> Self {
47        Node {
48            width,
49            height,
50            data,
51        }
52    }
53
54    fn width(&self) -> usize {
55        self.width as usize
56    }
57
58    fn height(&self) -> u32 {
59        self.height
60    }
61
62    fn data(&self) -> &[Data<T>] {
63        &self.data
64    }
65
66    fn data_mut(&mut self) -> &mut Vec<Data<T>> {
67        &mut self.data
68    }
69}
70
71pub struct List<S: Store, T: DagCbor> {
72    nodes: IpldCache<S, DagCborCodec, Node<T>>,
73    root: Cid,
74}
75
76impl<S: Store, T: Clone + DagCbor + Send + Sync> List<S, T>
77where
78    S: Store,
79    S::Params: StoreParams<Hashes = Code>,
80    <S::Params as StoreParams>::Codecs: Into<DagCborCodec>,
81    T: Decode<DagCborCodec> + Encode<DagCborCodec> + Clone + Send + Sync,
82    DagCborCodec: Into<<S::Params as StoreParams>::Codecs>,
83    Ipld: Decode<<S::Params as StoreParams>::Codecs>,
84{
85    pub async fn new(store: S, cache_size: usize, width: u32) -> Result<Self> {
86        let cache = IpldCache::new(store, DagCborCodec, Code::Blake2b256, cache_size);
87        let root = cache.insert(Node::new(width, 0, vec![])).await?;
88        Ok(Self { nodes: cache, root })
89    }
90
91    pub async fn open(store: S, cache_size: usize, root: Cid) -> Result<Self> {
92        let cache = IpldCache::new(store, DagCborCodec, Code::Blake2b256, cache_size);
93        // warm up the cache and make sure it's available
94        cache.get(&root).await?;
95        Ok(Self { nodes: cache, root })
96    }
97
98    pub fn root(&self) -> &Cid {
99        &self.root
100    }
101
102    pub async fn from(
103        store: S,
104        width: u32,
105        cache_size: usize,
106        items: impl Iterator<Item = T>,
107    ) -> Result<Self> {
108        let cache = IpldCache::new(store, DagCborCodec, Code::Blake2b256, cache_size);
109
110        let mut items: Vec<Data<T>> = items.map(Data::Value).collect();
111        let mut height = 0;
112        let mut cid = cache.insert(Node::new(width, height, vec![])).await?;
113        let width = width as usize;
114
115        loop {
116            let n_items = items.len() / width + 1;
117            let mut items_next = Vec::with_capacity(n_items);
118            for chunk in items.chunks(width) {
119                let node = Node::new(width as u32, height, chunk.to_vec());
120                cid = cache.insert(node).await?;
121                items_next.push(Data::Link(cid));
122            }
123            if items_next.len() == 1 {
124                return Ok(Self {
125                    nodes: cache,
126                    root: cid,
127                });
128            }
129            items = items_next;
130            height += 1;
131        }
132    }
133
134    pub async fn push(&mut self, value: T) -> Result<()> {
135        let mut value = Data::Value(value);
136        let root = self.nodes.get(&self.root).await?;
137        let height = root.height();
138        let width = root.width();
139
140        let chain = {
141            let mut height = root.height();
142            let mut chain = Vec::with_capacity(height as usize + 1);
143            chain.push(root);
144            while height > 0 {
145                let cid = chain
146                    .last()
147                    .expect("at least one block")
148                    .data()
149                    .last()
150                    .expect("at least one link")
151                    .cid()
152                    .expect("height > 0, payload must be a cid");
153                let node = self.nodes.get(cid).await?;
154                height = node.height();
155                chain.push(node);
156            }
157            chain
158        };
159
160        let mut mutated = false;
161        let cache = &self.nodes;
162        let mut last = cache
163            .insert(Node::new(width as u32, height, vec![]))
164            .await?;
165        for mut node in chain.into_iter().rev() {
166            if mutated {
167                let data = node.data_mut();
168                data.pop();
169                data.push(value);
170                last = cache.insert(node).await?;
171                value = Data::Link(last);
172            } else {
173                let data = node.data_mut();
174                if data.len() < width {
175                    data.push(value);
176                    last = cache.insert(node).await?;
177                    value = Data::Link(last);
178                    mutated = true;
179                } else {
180                    let node = Node::new(width as u32, node.height(), vec![value]);
181                    last = cache.insert(node).await?;
182                    value = Data::Link(last);
183                    mutated = false;
184                }
185            }
186        }
187
188        if !mutated {
189            let children = vec![Data::Link(*self.root()), value];
190            let node = Node::new(width as u32, height + 1, children);
191            last = cache.insert(node).await?;
192        }
193
194        self.root = last;
195
196        Ok(())
197    }
198
199    pub async fn pop(&mut self) -> Result<Option<T>> {
200        // TODO
201        Ok(None)
202    }
203
204    pub async fn get(&mut self, mut index: usize) -> Result<Option<T>> {
205        let node = self.nodes.get(&self.root).await?;
206        let mut node_ref = &node;
207        let width = node.width();
208        let mut height = node.height();
209        let mut node;
210
211        if index > width.pow(height + 1) {
212            return Ok(None);
213        }
214
215        loop {
216            let data_index = index / width.pow(height);
217            if let Some(data) = node_ref.data().get(data_index) {
218                if height == 0 {
219                    return Ok(Some(data.value().unwrap().clone()));
220                }
221                let cid = data.cid().unwrap();
222                node = self.nodes.get(cid).await?;
223                node_ref = &node;
224                index %= width.pow(height);
225                height = node.height();
226            } else {
227                return Ok(None);
228            }
229        }
230    }
231
232    pub async fn set(&mut self, _index: usize, _value: T) -> Result<()> {
233        // TODO
234        Ok(())
235    }
236
237    pub async fn len(&mut self) -> Result<usize> {
238        let root = self.nodes.get(&self.root).await?;
239        let width = root.width();
240        let mut height = root.height();
241        let mut size = width.pow(height + 1);
242        let mut node = root;
243        loop {
244            let data = node.data();
245            size -= width.pow(height) * (width - data.len());
246            if height == 0 {
247                return Ok(size);
248            }
249            let cid = data.last().unwrap().cid().unwrap();
250            node = self.nodes.get(cid).await?;
251            height = node.height();
252        }
253    }
254
255    pub async fn is_empty(&mut self) -> Result<bool> {
256        let root = self.nodes.get(&self.root).await?;
257        Ok(root.data().is_empty())
258    }
259
260    pub fn iter(&mut self) -> Iter<'_, S, T> {
261        Iter {
262            list: self,
263            index: 0,
264        }
265    }
266}
267
268pub struct Iter<'a, S: Store, T: DagCbor> {
269    list: &'a mut List<S, T>,
270    index: usize,
271}
272
273impl<'a, S, T: DagCbor> Iter<'a, S, T>
274where
275    S: Store,
276    S::Params: StoreParams<Hashes = Code>,
277    <S::Params as StoreParams>::Codecs: Into<DagCborCodec>,
278    T: Decode<DagCborCodec> + Encode<DagCborCodec> + Clone + Send + Sync,
279    DagCborCodec: Into<<S::Params as StoreParams>::Codecs>,
280    Ipld: Decode<<S::Params as StoreParams>::Codecs>,
281{
282    #[allow(clippy::should_implement_trait)]
283    pub async fn next(&mut self) -> Result<Option<T>> {
284        let elem = self.list.get(self.index).await?;
285        self.index += 1;
286        Ok(elem)
287    }
288}
289
290#[cfg(test)]
291mod tests {
292    use super::*;
293    use async_std::task;
294    use libipld::mem::MemStore;
295    use libipld::store::DefaultParams;
296    use model::*;
297
298    #[async_std::test]
299    async fn test_list() -> Result<()> {
300        let store = MemStore::<DefaultParams>::default();
301        let mut list = List::new(store, 12, 3).await?;
302        for i in 0..13 {
303            assert_eq!(list.get(i).await?, None);
304            assert_eq!(list.len().await?, i);
305            list.push(i as i64).await?;
306            for j in 0..i {
307                assert_eq!(list.get(j).await?, Some(j as i64));
308            }
309        }
310        /*for i in 0..13 {
311            list.set(i, (i as i128 + 1).into())?;
312            assert_eq!(list.get(i)?, int(i + 1));
313        }*/
314        /*for i in (0..13).rev() {
315            assert_eq!(vec.len()?, i + 1);
316            assert_eq!(vec.pop()?, int(i));
317        }*/
318        Ok(())
319    }
320
321    #[async_std::test]
322    async fn test_list_from() -> Result<()> {
323        let store = MemStore::<DefaultParams>::default();
324        let data: Vec<_> = (0..13).map(|i| i as i64).collect();
325        let mut list = List::from(store, 12, 3, data.clone().into_iter()).await?;
326        let mut data2 = vec![];
327        let mut iter = list.iter();
328        while let Some(elem) = iter.next().await? {
329            data2.push(elem)
330        }
331        assert_eq!(data, data2);
332        Ok(())
333    }
334
335    #[test]
336    fn list_vec_eqv() {
337        const LEN: usize = 25;
338        model! {
339            Model => let mut vec = Vec::new(),
340            Implementation => let mut list = {
341                let store = MemStore::<DefaultParams>::default();
342                let fut = List::new(store, LEN,3);
343                task::block_on(fut).unwrap()
344            },
345            Push(usize)(i in 0..LEN) => {
346                vec.push(i as i64);
347                task::block_on(list.push(i as i64)).unwrap();
348            },
349            Get(usize)(i in 0..LEN) => {
350                let r1 = vec.get(i).cloned();
351                let r2 = task::block_on(list.get(i)).unwrap();
352                assert_eq!(r1, r2);
353            },
354            Len(usize)(_ in 0..LEN) => {
355                let r1 = vec.len();
356                let r2 = task::block_on(list.len()).unwrap();
357                assert_eq!(r1, r2);
358            },
359            IsEmpty(usize)(_ in 0..LEN) => {
360                let r1 = vec.is_empty();
361                let r2 = task::block_on(list.is_empty()).unwrap();
362                assert_eq!(r1, r2);
363            }
364        }
365    }
366}
ipld_collections/list.rs

ipld_collections/
list.rs
