lsm_tree/
value.rs

1// Copyright (c) 2024-present, fjall-rs
2// This source code is licensed under both the Apache 2.0 and MIT License
3// (found in the LICENSE-* files in the repository)
4
5use crate::{key::InternalKey, Slice, ValueType};
6
7/// User defined key
8pub type UserKey = Slice;
9
10/// User defined data (blob of bytes)
11pub type UserValue = Slice;
12
13/// Sequence number - a monotonically increasing counter
14///
15/// Values with the same seqno are part of the same batch.
16///
17/// A value with a higher sequence number shadows an item with the
18/// same key and lower sequence number.
19/// This enables MVCC.
20///
21/// Stale items are lazily garbage-collected during compaction.
22pub type SeqNo = u64;
23
24/// Internal representation of KV pairs
25#[derive(Clone, Eq)]
26pub struct InternalValue {
27    /// Internal key
28    pub key: InternalKey,
29
30    /// User-defined value - an arbitrary byte array
31    ///
32    /// Supports up to 2^32 bytes
33    pub value: UserValue,
34}
35
36impl InternalValue {
37    /// Creates a new [`Value`].
38    ///
39    /// # Panics
40    ///
41    /// Panics if the key length is empty or greater than 2^16, or the value length is greater than 2^32.
42    pub fn new<V: Into<UserValue>>(key: InternalKey, value: V) -> Self {
43        let value = value.into();
44
45        assert!(!key.user_key.is_empty(), "key may not be empty");
46        assert!(
47            u32::try_from(value.len()).is_ok(),
48            "values can be 2^32 bytes in length"
49        );
50
51        Self { key, value }
52    }
53
54    /// Creates a new [`Value`].
55    ///
56    /// # Panics
57    ///
58    /// Panics if the key length is empty or greater than 2^16, or the value length is greater than 2^32.
59    pub fn from_components<K: Into<UserKey>, V: Into<UserValue>>(
60        user_key: K,
61        value: V,
62        seqno: SeqNo,
63        value_type: ValueType,
64    ) -> Self {
65        let key = InternalKey::new(user_key, seqno, value_type);
66        Self::new(key, value)
67    }
68
69    /// Creates a new tombstone.
70    ///
71    /// # Panics
72    ///
73    /// Panics if the key length is empty or greater than 2^16.
74    pub fn new_tombstone<K: Into<UserKey>>(key: K, seqno: u64) -> Self {
75        let key = InternalKey::new(key, seqno, ValueType::Tombstone);
76        Self::new(key, vec![])
77    }
78
79    /// Creates a new weak tombstone.
80    ///
81    /// # Panics
82    ///
83    /// Panics if the key length is empty or greater than 2^16.
84    pub fn new_weak_tombstone<K: Into<UserKey>>(key: K, seqno: u64) -> Self {
85        let key = InternalKey::new(key, seqno, ValueType::WeakTombstone);
86        Self::new(key, vec![])
87    }
88
89    #[doc(hidden)]
90    #[must_use]
91    pub fn is_tombstone(&self) -> bool {
92        self.key.is_tombstone()
93    }
94}
95
96impl PartialEq for InternalValue {
97    fn eq(&self, other: &Self) -> bool {
98        self.key == other.key
99    }
100}
101
102impl Ord for InternalValue {
103    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
104        self.key.cmp(&other.key)
105    }
106}
107
108impl PartialOrd for InternalValue {
109    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
110        Some(self.cmp(other))
111    }
112}
113
114#[cfg_attr(test, mutants::skip)]
115impl std::fmt::Debug for InternalValue {
116    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
117        write!(
118            f,
119            "{:?} => {:?}",
120            self.key,
121            if self.value.len() >= 64 {
122                format!("[ ... {} bytes ]", self.value.len())
123            } else {
124                format!("{:?}", self.value)
125            }
126        )
127    }
128}
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133    use test_log::test;
134
135    #[test]
136    fn pik_cmp_user_key() {
137        let a = InternalKey::new(*b"a", 0, ValueType::Value);
138        let b = InternalKey::new(*b"b", 0, ValueType::Value);
139        assert!(a < b);
140    }
141
142    #[test]
143    fn pik_cmp_seqno() {
144        let a = InternalKey::new(*b"a", 0, ValueType::Value);
145        let b = InternalKey::new(*b"a", 1, ValueType::Value);
146        assert!(a > b);
147    }
148}
lsm_tree/value.rs

lsm_tree/
value.rs
