icydb_core/db/index/
entry.rs

1use crate::{key::Key, traits::Storable};
2use candid::CandidType;
3use canic_cdk::structures::storable::Bound;
4use serde::{Deserialize, Serialize};
5use std::{borrow::Cow, collections::BTreeSet};
6use thiserror::Error as ThisError;
7
8///
9/// Constants
10///
11
12const INDEX_ENTRY_LEN_BYTES: usize = 4;
13pub const MAX_INDEX_ENTRY_KEYS: usize = 65_535;
14#[allow(clippy::cast_possible_truncation)]
15pub const MAX_INDEX_ENTRY_BYTES: u32 =
16    (INDEX_ENTRY_LEN_BYTES + (MAX_INDEX_ENTRY_KEYS * Key::STORED_SIZE)) as u32;
17
18///
19/// IndexEntryCorruption
20///
21
22#[derive(Debug, ThisError)]
23pub enum IndexEntryCorruption {
24    #[error("index entry exceeds max size")]
25    TooLarge { len: usize },
26
27    #[error("index entry missing key count")]
28    MissingLength,
29
30    #[error("index entry key count exceeds limit")]
31    TooManyKeys { count: usize },
32
33    #[error("index entry length does not match key count")]
34    LengthMismatch,
35
36    #[error("index entry contains invalid key bytes")]
37    InvalidKey,
38
39    #[error("index entry contains duplicate key")]
40    DuplicateKey,
41
42    #[error("index entry contains zero keys")]
43    EmptyEntry,
44
45    #[error("unique index entry contains {keys} keys")]
46    NonUniqueEntry { keys: usize },
47}
48
49impl IndexEntryCorruption {
50    #[must_use]
51    pub const fn message(&self) -> &'static str {
52        match self {
53            Self::TooLarge { .. } => "corrupted index entry: exceeds max size",
54            Self::MissingLength => "corrupted index entry: missing key count",
55            Self::TooManyKeys { .. } => "corrupted index entry: key count exceeds limit",
56            Self::LengthMismatch => "corrupted index entry: length mismatch",
57            Self::InvalidKey => "corrupted index entry: invalid key bytes",
58            Self::DuplicateKey => "corrupted index entry: duplicate key",
59            Self::EmptyEntry => "corrupted index entry: empty entry",
60            Self::NonUniqueEntry { .. } => "corrupted index entry: non-unique entry",
61        }
62    }
63}
64
65///
66/// IndexEntryEncodeError
67///
68
69#[derive(Debug, ThisError)]
70pub enum IndexEntryEncodeError {
71    #[error("index entry exceeds max keys: {keys} (limit {MAX_INDEX_ENTRY_KEYS})")]
72    TooManyKeys { keys: usize },
73}
74
75impl IndexEntryEncodeError {
76    #[must_use]
77    pub const fn keys(&self) -> usize {
78        match self {
79            Self::TooManyKeys { keys } => *keys,
80        }
81    }
82}
83
84///
85/// IndexEntry
86///
87
88#[derive(CandidType, Clone, Debug, Deserialize, Serialize)]
89pub struct IndexEntry {
90    keys: BTreeSet<Key>,
91}
92
93impl IndexEntry {
94    #[must_use]
95    pub fn new(key: Key) -> Self {
96        let mut keys = BTreeSet::new();
97        keys.insert(key);
98
99        Self { keys }
100    }
101
102    pub fn insert_key(&mut self, key: Key) {
103        self.keys.insert(key);
104    }
105
106    pub fn remove_key(&mut self, key: &Key) {
107        self.keys.remove(key);
108    }
109
110    #[must_use]
111    pub fn contains(&self, key: &Key) -> bool {
112        self.keys.contains(key)
113    }
114
115    #[must_use]
116    pub fn is_empty(&self) -> bool {
117        self.keys.is_empty()
118    }
119
120    #[must_use]
121    pub fn len(&self) -> usize {
122        self.keys.len()
123    }
124
125    pub fn iter_keys(&self) -> impl Iterator<Item = Key> + '_ {
126        self.keys.iter().copied()
127    }
128
129    #[must_use]
130    pub fn single_key(&self) -> Option<Key> {
131        if self.keys.len() == 1 {
132            self.keys.iter().copied().next()
133        } else {
134            None
135        }
136    }
137}
138
139///
140/// RawIndexEntry
141///
142
143#[derive(Clone, Debug, Eq, PartialEq)]
144pub struct RawIndexEntry(Vec<u8>);
145
146impl RawIndexEntry {
147    pub fn try_from_entry(entry: &IndexEntry) -> Result<Self, IndexEntryEncodeError> {
148        let keys = entry.len();
149        if keys > MAX_INDEX_ENTRY_KEYS {
150            return Err(IndexEntryEncodeError::TooManyKeys { keys });
151        }
152
153        let mut out = Vec::with_capacity(INDEX_ENTRY_LEN_BYTES + (keys * Key::STORED_SIZE));
154        let count = u32::try_from(keys).map_err(|_| IndexEntryEncodeError::TooManyKeys { keys })?;
155        out.extend_from_slice(&count.to_be_bytes());
156        for key in entry.iter_keys() {
157            out.extend_from_slice(&key.to_bytes());
158        }
159
160        Ok(Self(out))
161    }
162
163    pub fn try_decode(&self) -> Result<IndexEntry, IndexEntryCorruption> {
164        let bytes = self.0.as_slice();
165        if bytes.len() > MAX_INDEX_ENTRY_BYTES as usize {
166            return Err(IndexEntryCorruption::TooLarge { len: bytes.len() });
167        }
168        if bytes.len() < INDEX_ENTRY_LEN_BYTES {
169            return Err(IndexEntryCorruption::MissingLength);
170        }
171
172        let mut len_buf = [0u8; INDEX_ENTRY_LEN_BYTES];
173        len_buf.copy_from_slice(&bytes[..INDEX_ENTRY_LEN_BYTES]);
174        let count = u32::from_be_bytes(len_buf) as usize;
175        if count == 0 {
176            return Err(IndexEntryCorruption::EmptyEntry);
177        }
178        if count > MAX_INDEX_ENTRY_KEYS {
179            return Err(IndexEntryCorruption::TooManyKeys { count });
180        }
181
182        let expected = INDEX_ENTRY_LEN_BYTES
183            .checked_add(
184                count
185                    .checked_mul(Key::STORED_SIZE)
186                    .ok_or(IndexEntryCorruption::LengthMismatch)?,
187            )
188            .ok_or(IndexEntryCorruption::LengthMismatch)?;
189        if bytes.len() != expected {
190            return Err(IndexEntryCorruption::LengthMismatch);
191        }
192
193        let mut keys = BTreeSet::new();
194        let mut offset = INDEX_ENTRY_LEN_BYTES;
195        for _ in 0..count {
196            let end = offset + Key::STORED_SIZE;
197            let key = Key::try_from_bytes(&bytes[offset..end])
198                .map_err(|_| IndexEntryCorruption::InvalidKey)?;
199            if !keys.insert(key) {
200                return Err(IndexEntryCorruption::DuplicateKey);
201            }
202            offset = end;
203        }
204
205        Ok(IndexEntry { keys })
206    }
207
208    #[must_use]
209    pub fn as_bytes(&self) -> &[u8] {
210        &self.0
211    }
212
213    #[must_use]
214    pub const fn len(&self) -> usize {
215        self.0.len()
216    }
217
218    #[must_use]
219    pub const fn is_empty(&self) -> bool {
220        self.0.is_empty()
221    }
222}
223
224impl Storable for RawIndexEntry {
225    fn to_bytes(&self) -> Cow<'_, [u8]> {
226        Cow::Borrowed(&self.0)
227    }
228
229    fn from_bytes(bytes: Cow<'_, [u8]>) -> Self {
230        Self(bytes.into_owned())
231    }
232
233    fn into_bytes(self) -> Vec<u8> {
234        self.0
235    }
236
237    const BOUND: Bound = Bound::Bounded {
238        max_size: MAX_INDEX_ENTRY_BYTES,
239        is_fixed_size: false,
240    };
241}
icydb_core/db/index/entry.rs

icydb_core/db/index/
entry.rs
