frond 0.1.1

dynamic lexicographic containers
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

//! `frond` is an immutable, contiguous container for arbitrary keys and values. It can be split and merged.
//! It is initially created as [`sled`](https://github.com/spacejam/sled)'s new leaf structure,
//! but it can be used for any chunk of data that you may want to put on disk - like a LSM SST
//! etc...

mod composite;
mod naive;

pub use composite::Composite;
pub use naive::Petal as Naive;

type Key<'a> = &'a [u8];
type Value<'a> = &'a [u8];

pub trait Interface: Default {
    type Iter<'a>: DoubleEndedIterator<Item = (&'a [u8], &'a [u8])>
    where
        Self: 'a;

    fn get(&self, key: Key) -> Option<Value>;

    #[must_use]
    fn batch<'a, I: IntoIterator<Item = (&'a [u8], Option<&'a [u8]>)>>(&self, iter: I) -> Self;

    #[must_use]
    fn contains(&self, key: Key) -> bool;

    #[must_use]
    fn split(&self, split_key: Key) -> (Self, Self);

    #[must_use]
    fn len(&self) -> usize;

    #[must_use]
    fn merge(&self, rhs: &Self) -> Self;

    #[must_use]
    fn insert(&self, key: Key, value: Value) -> (Option<Value>, Self) {
        let last = self.get(key);
        let new = self.batch([(key, Some(value))]);
        (last, new)
    }

    #[must_use]
    fn remove(&self, key: Key) -> (Option<Value>, Self) {
        let last = self.get(key);
        let new = self.batch([(key, None)]);
        (last, new)
    }

    fn range<'a>(
        &'a self,
        start: std::ops::Bound<&[u8]>,
        end: std::ops::Bound<&[u8]>,
    ) -> Self::Iter<'a>;
}

impl Interface for Box<Naive> {
    type Iter<'a> = naive::Iter<'a> where Self: 'a;

    fn range<'a>(
        &'a self,
        start: std::ops::Bound<&[u8]>,
        end: std::ops::Bound<&[u8]>,
    ) -> Self::Iter<'a> {
        Naive::range(self, start, end)
    }

    fn get(&self, key: Key) -> Option<Value> {
        Naive::get(self, key)
    }

    fn batch<'a, I: IntoIterator<Item = (&'a [u8], Option<&'a [u8]>)>>(&self, iter: I) -> Self {
        Naive::batch(self, iter)
    }

    fn contains(&self, key: Key) -> bool {
        Naive::contains(self, key)
    }

    fn split(&self, split_key: Key) -> (Self, Self) {
        Naive::split(self, split_key)
    }

    fn len(&self) -> usize {
        Naive::len(self)
    }

    fn merge(&self, rhs: &Self) -> Self {
        Naive::merge(self, rhs)
    }
}

impl<A: Interface, B: Interface> Interface for Composite<A, B> {
    type Iter<'a> = composite::Iter<'a, A, B> where Self: 'a;

    fn get(&self, key: Key) -> Option<Value> {
        Composite::get(self, key)
    }

    fn range<'a>(
        &'a self,
        start: std::ops::Bound<&[u8]>,
        end: std::ops::Bound<&[u8]>,
    ) -> Self::Iter<'a> {
        Composite::range(self, start, end)
    }

    fn batch<'a, I: IntoIterator<Item = (&'a [u8], Option<&'a [u8]>)>>(&self, iter: I) -> Self {
        Composite::batch(self, iter)
    }

    fn contains(&self, key: Key) -> bool {
        Composite::contains(self, key)
    }

    fn split(&self, split_key: Key) -> (Self, Self) {
        Composite::split(self, split_key)
    }

    fn len(&self) -> usize {
        Composite::len(self)
    }

    fn merge(&self, rhs: &Self) -> Self {
        Composite::merge(self, rhs)
    }
}