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/// User defined data (blob of bytes)
10#[allow(clippy::module_name_repetitions)]
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#[allow(clippy::module_name_repetitions)]
26#[derive(Clone, Eq)]
27pub struct InternalValue {
28    /// Internal key
29    pub key: InternalKey,
30
31    /// User-defined value - an arbitrary byte array
32    ///
33    /// Supports up to 2^32 bytes
34    pub value: UserValue,
35}
36
37impl InternalValue {
38    /// Creates a new [`Value`].
39    ///
40    /// # Panics
41    ///
42    /// Panics if the key length is empty or greater than 2^16, or the value length is greater than 2^32.
43    pub fn new<V: Into<UserValue>>(key: InternalKey, value: V) -> Self {
44        let value = value.into();
45
46        assert!(!key.user_key.is_empty(), "key may not be empty");
47        assert!(
48            u32::try_from(value.len()).is_ok(),
49            "values can be 2^32 bytes in length"
50        );
51
52        Self { key, value }
53    }
54
55    /// Creates a new [`Value`].
56    ///
57    /// # Panics
58    ///
59    /// Panics if the key length is empty or greater than 2^16, or the value length is greater than 2^32.
60    pub fn from_components<K: Into<UserKey>, V: Into<UserValue>>(
61        user_key: K,
62        value: V,
63        seqno: SeqNo,
64        value_type: ValueType,
65    ) -> Self {
66        let key = InternalKey::new(user_key, seqno, value_type);
67        Self::new(key, value)
68    }
69
70    /// Creates a new tombstone.
71    ///
72    /// # Panics
73    ///
74    /// Panics if the key length is empty or greater than 2^16.
75    pub fn new_tombstone<K: Into<UserKey>>(key: K, seqno: u64) -> Self {
76        let key = InternalKey::new(key, seqno, ValueType::Tombstone);
77        Self::new(key, vec![])
78    }
79
80    /// Creates a new weak tombstone.
81    ///
82    /// # Panics
83    ///
84    /// Panics if the key length is empty or greater than 2^16.
85    pub fn new_weak_tombstone<K: Into<UserKey>>(key: K, seqno: u64) -> Self {
86        let key = InternalKey::new(key, seqno, ValueType::WeakTombstone);
87        Self::new(key, vec![])
88    }
89
90    #[doc(hidden)]
91    #[must_use]
92    pub fn is_tombstone(&self) -> bool {
93        self.key.is_tombstone()
94    }
95}
96
97impl PartialEq for InternalValue {
98    fn eq(&self, other: &Self) -> bool {
99        self.key == other.key
100    }
101}
102
103impl Ord for InternalValue {
104    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
105        self.key.cmp(&other.key)
106    }
107}
108
109impl PartialOrd for InternalValue {
110    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
111        Some(self.cmp(other))
112    }
113}
114
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
