trine-kv 0.2.0

Embedded LSM MVCC key-value database.
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

use std::cmp::Ordering;

use crate::types::Sequence;

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum ValueKind {
    Put,
    PointDelete,
    RangeDelete,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct InternalKey {
    user_key: Vec<u8>,
    sequence: Sequence,
    kind: ValueKind,
    batch_index: u32,
}

impl InternalKey {
    #[must_use]
    pub fn new(
        user_key: impl Into<Vec<u8>>,
        sequence: Sequence,
        kind: ValueKind,
        batch_index: u32,
    ) -> Self {
        Self {
            user_key: user_key.into(),
            sequence,
            kind,
            batch_index,
        }
    }

    #[must_use]
    pub fn user_key(&self) -> &[u8] {
        &self.user_key
    }

    #[must_use]
    pub const fn sequence(&self) -> Sequence {
        self.sequence
    }

    #[must_use]
    pub const fn kind(&self) -> ValueKind {
        self.kind
    }

    #[must_use]
    pub const fn batch_index(&self) -> u32 {
        self.batch_index
    }
}

impl Ord for InternalKey {
    fn cmp(&self, other: &Self) -> Ordering {
        self.user_key
            .cmp(&other.user_key)
            .then_with(|| other.sequence.cmp(&self.sequence))
            .then_with(|| other.batch_index.cmp(&self.batch_index))
            .then_with(|| self.kind.cmp(&other.kind))
    }
}

impl PartialOrd for InternalKey {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

pub(crate) fn first_internal_key_for_user(user_key: &[u8]) -> InternalKey {
    InternalKey::new(
        user_key.to_vec(),
        Sequence::new(u64::MAX),
        ValueKind::Put,
        u32::MAX,
    )
}

pub(crate) fn last_internal_key_for_user(user_key: &[u8]) -> InternalKey {
    InternalKey::new(user_key.to_vec(), Sequence::ZERO, ValueKind::RangeDelete, 0)
}

#[cfg(test)]
mod tests {
    use super::{InternalKey, ValueKind};
    use crate::types::Sequence;

    #[test]
    fn internal_keys_sort_user_key_ascending_then_sequence_descending() {
        let mut keys = [
            InternalKey::new("b", Sequence::new(1), ValueKind::Put, 0),
            InternalKey::new("a", Sequence::new(1), ValueKind::Put, 0),
            InternalKey::new("a", Sequence::new(3), ValueKind::Put, 0),
            InternalKey::new("a", Sequence::new(2), ValueKind::Put, 0),
        ];

        keys.sort();

        let ordered = keys.map(|key| (key.user_key().to_vec(), key.sequence().get()));
        assert_eq!(
            ordered,
            [
                (b"a".to_vec(), 3),
                (b"a".to_vec(), 2),
                (b"a".to_vec(), 1),
                (b"b".to_vec(), 1),
            ]
        );
    }

    #[test]
    fn batch_index_sorts_later_batch_operations_first() {
        let mut keys = [
            InternalKey::new("a", Sequence::new(1), ValueKind::Put, 0),
            InternalKey::new("a", Sequence::new(1), ValueKind::PointDelete, 1),
        ];

        keys.sort();

        assert_eq!(keys[0].batch_index(), 1);
        assert_eq!(keys[0].kind(), ValueKind::PointDelete);
    }
}