libkv/
container.rs

1use std::marker::PhantomData;
2
3use crate::{Codec, Decodable, Encoding, Iter, KeySerde, StorageError};
4
5/// Trait representing an arbitrary data structure that can be used in a
6/// Key-Value store.
7///
8/// The trait requires the following associated types:
9/// - `Key`: The type of the key used to index the data structure.
10/// - `Enc`: The encoding used to serialize and deserialize the data structure.
11/// - `Value`: The value type, that can be (de)serialized using the `Enc` encoding.
12/// - `DsType`: A type that indicates whether the data structure is terminal or
13///     non-terminal.
14///
15/// The trait also requires the following methods:
16/// - `with_prefix`: A constructor that takes a byte-prefix, and returns a handle
17///    to the data structure with that prefix.
18/// - `should_skip_key`: A method that takes a key and returns whether the key
19///   should be skipped when iterating over the data structure.
20pub trait DataStructure {
21    /// The type of the key used to index the data structure.
22    type Key: KeySerde;
23    /// The encoding used to serialize and deserialize the data structure.
24    type Enc: Encoding;
25    /// The value type, that can be (de)serialized using the `Enc` encoding.
26    type Value: Codec<Self::Enc>;
27    /// A type that indicates whether the data structure is terminal or non-terminal.
28    type DsType: sealed::ContainerType;
29
30    /// Constructor that takes a byte-prefix, and returns a handle to the data structure
31    fn with_prefix(prefix: Vec<u8>) -> Self
32    where
33        Self: Sized;
34
35    /// Returns whether the given key should be skipped when iterating over the data structure.
36    fn should_skip_key(key: &Self::Key) -> bool;
37}
38
39/// A trait representing a data structure that is a container of other data structures.
40///
41/// Most data structures are non-terminal, meaning they contain other data structures.
42/// Since we represent actual values as the `Item` structure, even "simple" data structures
43/// like a Key-Value Map are considered non-terminal, and thus are marked as `Container`.
44pub trait Container: DataStructure<DsType = NonTerminal> {
45    type Inner: DataStructure;
46}
47
48mod sealed {
49    pub trait ContainerType: Sized {}
50}
51
52pub struct Terminal {}
53impl sealed::ContainerType for Terminal {}
54pub struct NonTerminal {}
55impl sealed::ContainerType for NonTerminal {}
56
57pub struct DsIter<'a, D: DataStructure> {
58    _marker: PhantomData<D>,
59    prefix: Vec<u8>,
60    iter: Iter<'a, (Vec<u8>, Vec<u8>)>,
61}
62
63impl<'a, D: DataStructure> DsIter<'a, D> {
64    pub const fn new(prefix: Vec<u8>, iter: Iter<'a, (Vec<u8>, Vec<u8>)>) -> Self {
65        Self {
66            _marker: PhantomData,
67            prefix,
68            iter,
69        }
70    }
71}
72
73impl<'a, D: DataStructure> Iterator for DsIter<'a, D> {
74    type Item = Result<(D::Key, D::Value), StorageError<D::Enc>>;
75
76    fn next(&mut self) -> Option<Self::Item> {
77        loop {
78            let (mut key_bytes, val_bytes) = self.iter.next()?;
79            if !key_bytes.starts_with(&self.prefix) {
80                return None;
81            }
82            let key_bytes = key_bytes.split_off(self.prefix.len());
83            let key = <<D as DataStructure>::Key as KeySerde>::decode(&mut key_bytes.as_slice())
84                .map(|k| (D::should_skip_key(&k), k));
85
86            match key {
87                Ok((true, _)) => continue,
88                Ok((false, key)) => {
89                    let val = <D::Value as Decodable<D::Enc>>::decode(&val_bytes)
90                        .map_err(StorageError::ValueDeserialize);
91                    return Some(val.map(|val| (key, val)));
92                }
93                Err(e) => return Some(Err(StorageError::KeyDeserialize(e))),
94            }
95        }
96    }
97}
libkv/container.rs

libkv/
container.rs
