libkv 0.1.0

A library for building data structures atop key-value stores.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

use std::marker::PhantomData;

use crate::{Codec, Decodable, Encoding, Iter, KeySerde, StorageError};

/// Trait representing an arbitrary data structure that can be used in a
/// Key-Value store.
///
/// The trait requires the following associated types:
/// - `Key`: The type of the key used to index the data structure.
/// - `Enc`: The encoding used to serialize and deserialize the data structure.
/// - `Value`: The value type, that can be (de)serialized using the `Enc` encoding.
/// - `DsType`: A type that indicates whether the data structure is terminal or
///     non-terminal.
///
/// The trait also requires the following methods:
/// - `with_prefix`: A constructor that takes a byte-prefix, and returns a handle
///    to the data structure with that prefix.
/// - `should_skip_key`: A method that takes a key and returns whether the key
///   should be skipped when iterating over the data structure.
pub trait DataStructure {
    /// The type of the key used to index the data structure.
    type Key: KeySerde;
    /// The encoding used to serialize and deserialize the data structure.
    type Enc: Encoding;
    /// The value type, that can be (de)serialized using the `Enc` encoding.
    type Value: Codec<Self::Enc>;
    /// A type that indicates whether the data structure is terminal or non-terminal.
    type DsType: sealed::ContainerType;

    /// Constructor that takes a byte-prefix, and returns a handle to the data structure
    fn with_prefix(prefix: Vec<u8>) -> Self
    where
        Self: Sized;

    /// Returns whether the given key should be skipped when iterating over the data structure.
    fn should_skip_key(key: &Self::Key) -> bool;
}

/// A trait representing a data structure that is a container of other data structures.
///
/// Most data structures are non-terminal, meaning they contain other data structures.
/// Since we represent actual values as the `Item` structure, even "simple" data structures
/// like a Key-Value Map are considered non-terminal, and thus are marked as `Container`.
pub trait Container: DataStructure<DsType = NonTerminal> {
    type Inner: DataStructure;
}

mod sealed {
    pub trait ContainerType: Sized {}
}

pub struct Terminal {}
impl sealed::ContainerType for Terminal {}
pub struct NonTerminal {}
impl sealed::ContainerType for NonTerminal {}

pub struct DsIter<'a, D: DataStructure> {
    _marker: PhantomData<D>,
    prefix: Vec<u8>,
    iter: Iter<'a, (Vec<u8>, Vec<u8>)>,
}

impl<'a, D: DataStructure> DsIter<'a, D> {
    pub const fn new(prefix: Vec<u8>, iter: Iter<'a, (Vec<u8>, Vec<u8>)>) -> Self {
        Self {
            _marker: PhantomData,
            prefix,
            iter,
        }
    }
}

impl<'a, D: DataStructure> Iterator for DsIter<'a, D> {
    type Item = Result<(D::Key, D::Value), StorageError<D::Enc>>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let (mut key_bytes, val_bytes) = self.iter.next()?;
            if !key_bytes.starts_with(&self.prefix) {
                return None;
            }
            let key_bytes = key_bytes.split_off(self.prefix.len());
            let key = <<D as DataStructure>::Key as KeySerde>::decode(&mut key_bytes.as_slice())
                .map(|k| (D::should_skip_key(&k), k));

            match key {
                Ok((true, _)) => continue,
                Ok((false, key)) => {
                    let val = <D::Value as Decodable<D::Enc>>::decode(&val_bytes)
                        .map_err(StorageError::ValueDeserialize);
                    return Some(val.map(|val| (key, val)));
                }
                Err(e) => return Some(Err(StorageError::KeyDeserialize(e))),
            }
        }
    }
}