forest/cid_collections/
small_cid_vec.rs

1// Copyright 2019-2026 ChainSafe Systems
2// SPDX-License-Identifier: Apache-2.0, MIT
3
4use super::*;
5use crate::utils::get_size::{GetSize, nunny_vec_heap_size_helper};
6use cid::Cid;
7use nunny::Vec as NonEmpty;
8use serde::{Deserialize, Serialize};
9
10#[cfg(doc)]
11use crate::blocks::TipsetKey;
12
13/// There are typically MANY small, immutable collections of CIDs in, e.g [`TipsetKey`]s.
14///
15/// Save space on those by:
16/// - Using [`SmallCid`]s
17///   (In the median case, this uses 40 B over 96 B per CID)
18///
19/// This may be expanded to have [`smallvec`](https://docs.rs/smallvec/1.11.0/smallvec/index.html)-style indirection
20/// to save more on heap allocations.
21#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize, PartialOrd, Ord)]
22#[cfg_attr(test, derive(derive_quickcheck_arbitrary::Arbitrary))]
23pub struct SmallCidNonEmptyVec(NonEmpty<SmallCid>);
24
25impl GetSize for SmallCidNonEmptyVec {
26    fn get_heap_size_with_tracker<T: get_size2::GetSizeTracker>(&self, tracker: T) -> (usize, T) {
27        nunny_vec_heap_size_helper(&self.0, tracker)
28    }
29}
30
31impl SmallCidNonEmptyVec {
32    /// Returns `true` if the slice contains an element with the given value.
33    ///
34    /// See also [`contains`](https://doc.rust-lang.org/std/primitive.slice.html#method.contains).
35    pub fn contains(&self, cid: Cid) -> bool {
36        self.0.contains(&SmallCid::from(cid))
37    }
38
39    /// Returns a non-empty collection of `CID`
40    pub fn into_cids(self) -> NonEmpty<Cid> {
41        self.0.into_iter_ne().map(From::from).collect_vec()
42    }
43
44    /// Returns an iterator of `CID`s.
45    pub fn iter(&self) -> impl Iterator<Item = Cid> + '_ {
46        self.0.iter().map(|cid| Cid::from(cid.clone()))
47    }
48
49    /// Returns the number of `CID`s
50    pub fn len(&self) -> usize {
51        self.0.len()
52    }
53}
54
55impl<'a> IntoIterator for &'a SmallCidNonEmptyVec {
56    type Item = Cid;
57
58    type IntoIter = std::iter::Map<std::slice::Iter<'a, SmallCid>, fn(&SmallCid) -> Cid>;
59
60    fn into_iter(self) -> Self::IntoIter {
61        self.0.iter().map(|cid| Cid::from(cid.clone()))
62    }
63}
64
65impl IntoIterator for SmallCidNonEmptyVec {
66    type Item = Cid;
67
68    type IntoIter =
69        std::iter::Map<<NonEmpty<SmallCid> as IntoIterator>::IntoIter, fn(SmallCid) -> Cid>;
70
71    fn into_iter(self) -> Self::IntoIter {
72        self.0.into_iter().map(Cid::from)
73    }
74}
75
76/// A [`MaybeCompactedCid`], with indirection to save space on the most common CID variant, at the cost
77/// of an extra allocation on rare variants.
78///
79/// This is NOT intended as a general purpose type - other collections should use the variants
80/// of [`MaybeCompactedCid`], so that the discriminant is not repeated.
81#[cfg_vis::cfg_vis(doc, pub)]
82#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, GetSize)]
83pub enum SmallCid {
84    Inline(CidV1DagCborBlake2b256),
85    Indirect(Uncompactable),
86}
87
88//////////////////////////
89// SmallCid conversions //
90//////////////////////////
91
92impl From<Cid> for SmallCid {
93    fn from(value: Cid) -> Self {
94        match MaybeCompactedCid::from(value) {
95            MaybeCompactedCid::Compact(c) => Self::Inline(c),
96            MaybeCompactedCid::Uncompactable(u) => Self::Indirect(u),
97        }
98    }
99}
100
101impl From<SmallCid> for Cid {
102    fn from(value: SmallCid) -> Self {
103        match value {
104            SmallCid::Inline(c) => c.into(),
105            SmallCid::Indirect(u) => u.into(),
106        }
107    }
108}
109
110impl Serialize for SmallCid {
111    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
112    where
113        S: serde::Serializer,
114    {
115        Cid::from(self.clone()).serialize(serializer)
116    }
117}
118
119impl<'de> Deserialize<'de> for SmallCid {
120    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
121    where
122        D: serde::Deserializer<'de>,
123    {
124        Cid::deserialize(deserializer).map(Into::into)
125    }
126}
127
128/////////////////////
129// Arbitrary impls //
130/////////////////////
131
132#[cfg(test)]
133// Note this goes through MaybeCompactedCid, artificially bumping the probability of compact CIDs
134impl quickcheck::Arbitrary for SmallCid {
135    fn arbitrary(g: &mut quickcheck::Gen) -> Self {
136        Self::from(Cid::from(MaybeCompactedCid::arbitrary(g)))
137    }
138}
139
140impl From<NonEmpty<Cid>> for SmallCidNonEmptyVec {
141    fn from(value: NonEmpty<Cid>) -> Self {
142        Self(value.into_iter_ne().map(From::from).collect_vec())
143    }
144}
forest/cid_collections/small_cid_vec.rs

forest/cid_collections/
small_cid_vec.rs
