1use std::cmp::Ordering;
2
3use crate::coding::{decode_fixed64, put_fixed64, put_varint32};
4use crate::comparator::{BytewiseComparator, Comparator};
5
6pub const NUM_LEVELS: usize = 7;
7pub const L0_COMPACTION_TRIGGER: usize = 4;
8pub const L0_SLOWDOWN_WRITES_TRIGGER: usize = 8;
9pub const L0_STOP_WRITES_TRIGGER: usize = 12;
10pub const MAX_MEM_COMPACT_LEVEL: usize = 2;
11pub const READ_BYTES_PERIOD: usize = 1048576;
12
13pub type SequenceNumber = u64;
14pub const MAX_SEQUENCE_NUMBER: SequenceNumber = (1u64 << 56) - 1;
15
16#[derive(Debug, Copy, Clone, PartialEq, Eq)]
17#[repr(u8)]
18pub enum ValueType {
19 Deletion = 0x0,
20 Value = 0x1,
21}
22
23pub const VALUE_TYPE_FOR_SEEK: ValueType = ValueType::Value;
24
25#[derive(Debug, Clone, PartialEq, Eq)]
26pub struct ParsedInternalKey {
27 pub user_key: Vec<u8>,
28 pub sequence: SequenceNumber,
29 pub value_type: ValueType,
30}
31
32impl ParsedInternalKey {
33 pub fn new(
34 user_key: impl AsRef<[u8]>,
35 sequence: SequenceNumber,
36 value_type: ValueType,
37 ) -> Self {
38 Self {
39 user_key: user_key.as_ref().to_vec(),
40 sequence,
41 value_type,
42 }
43 }
44
45 pub fn encoding_len(&self) -> usize {
46 self.user_key.len() + 8
47 }
48}
49
50#[derive(Debug, Clone, PartialEq, Eq, Default)]
51pub struct InternalKey {
52 rep: Vec<u8>,
53}
54
55impl InternalKey {
56 pub fn new(
57 user_key: impl AsRef<[u8]>,
58 sequence: SequenceNumber,
59 value_type: ValueType,
60 ) -> Self {
61 let mut rep = Vec::new();
62 append_internal_key(
63 &mut rep,
64 &ParsedInternalKey::new(user_key, sequence, value_type),
65 );
66 Self { rep }
67 }
68
69 pub fn decode_from(&mut self, encoded: impl AsRef<[u8]>) {
70 self.rep.clear();
71 self.rep.extend_from_slice(encoded.as_ref());
72 }
73
74 pub fn encode(&self) -> &[u8] {
75 assert!(!self.rep.is_empty(), "empty InternalKey is invalid");
76 &self.rep
77 }
78
79 pub fn user_key(&self) -> &[u8] {
80 extract_user_key(&self.rep).expect("internal key requires an 8-byte tag")
81 }
82
83 pub fn clear(&mut self) {
84 self.rep.clear();
85 }
86
87 pub fn is_empty(&self) -> bool {
88 self.rep.is_empty()
89 }
90}
91
92#[derive(Debug, Clone)]
93pub struct InternalKeyComparator<C = BytewiseComparator> {
94 user_comparator: C,
95}
96
97impl Default for InternalKeyComparator<BytewiseComparator> {
98 fn default() -> Self {
99 Self::new(BytewiseComparator)
100 }
101}
102
103impl<C: Comparator> InternalKeyComparator<C> {
104 pub fn new(user_comparator: C) -> Self {
105 Self { user_comparator }
106 }
107
108 pub fn user_comparator(&self) -> &C {
109 &self.user_comparator
110 }
111
112 pub fn name_inherent(&self) -> &'static str {
113 "novakv.InternalKeyComparator"
114 }
115
116 pub fn compare(&self, a: &[u8], b: &[u8]) -> Ordering {
117 let user_order = self
118 .user_comparator
119 .compare(required_user_key(a), required_user_key(b));
120 if !user_order.is_eq() {
121 return user_order;
122 }
123 let anum = decode_fixed64(&a[a.len() - 8..]);
124 let bnum = decode_fixed64(&b[b.len() - 8..]);
125 bnum.cmp(&anum)
126 }
127
128 pub fn find_shortest_separator(&self, start: &mut Vec<u8>, limit: &[u8]) {
129 let user_start = required_user_key(start).to_vec();
130 let user_limit = required_user_key(limit);
131 let mut tmp = user_start.clone();
132 self.user_comparator
133 .find_shortest_separator(&mut tmp, user_limit);
134 if tmp.len() < user_start.len() && self.user_comparator.compare(&user_start, &tmp).is_lt() {
135 put_fixed64(
136 &mut tmp,
137 pack_sequence_and_type(MAX_SEQUENCE_NUMBER, VALUE_TYPE_FOR_SEEK),
138 );
139 debug_assert!(self.compare(start, &tmp).is_lt());
140 debug_assert!(self.compare(&tmp, limit).is_lt());
141 *start = tmp;
142 }
143 }
144
145 pub fn find_short_successor(&self, key: &mut Vec<u8>) {
146 let user_key = required_user_key(key).to_vec();
147 let mut tmp = user_key.clone();
148 self.user_comparator.find_short_successor(&mut tmp);
149 if tmp.len() < user_key.len() && self.user_comparator.compare(&user_key, &tmp).is_lt() {
150 put_fixed64(
151 &mut tmp,
152 pack_sequence_and_type(MAX_SEQUENCE_NUMBER, VALUE_TYPE_FOR_SEEK),
153 );
154 debug_assert!(self.compare(key, &tmp).is_lt());
155 *key = tmp;
156 }
157 }
158}
159
160impl<C: Comparator> Comparator for InternalKeyComparator<C> {
161 fn name(&self) -> &'static str {
162 self.name_inherent()
163 }
164
165 fn compare(&self, a: &[u8], b: &[u8]) -> Ordering {
166 InternalKeyComparator::compare(self, a, b)
167 }
168
169 fn find_shortest_separator(&self, start: &mut Vec<u8>, limit: &[u8]) {
170 InternalKeyComparator::find_shortest_separator(self, start, limit)
171 }
172
173 fn find_short_successor(&self, key: &mut Vec<u8>) {
174 InternalKeyComparator::find_short_successor(self, key)
175 }
176}
177
178#[derive(Debug, Clone, PartialEq, Eq)]
179pub struct LookupKey {
180 rep: Vec<u8>,
181 kstart: usize,
182}
183
184impl LookupKey {
185 pub fn new(user_key: impl AsRef<[u8]>, sequence: SequenceNumber) -> Self {
186 let user_key = user_key.as_ref();
187 let mut rep = Vec::with_capacity(user_key.len() + 13);
188 put_varint32(&mut rep, (user_key.len() + 8) as u32);
189 let kstart = rep.len();
190 rep.extend_from_slice(user_key);
191 put_fixed64(
192 &mut rep,
193 pack_sequence_and_type(sequence, VALUE_TYPE_FOR_SEEK),
194 );
195 Self { rep, kstart }
196 }
197
198 pub fn memtable_key(&self) -> &[u8] {
199 &self.rep
200 }
201
202 pub fn internal_key(&self) -> &[u8] {
203 &self.rep[self.kstart..]
204 }
205
206 pub fn user_key(&self) -> &[u8] {
207 &self.rep[self.kstart..self.rep.len() - 8]
208 }
209}
210
211pub fn internal_key_encoding_len(key: &ParsedInternalKey) -> usize {
212 key.encoding_len()
213}
214
215pub fn append_internal_key(dst: &mut Vec<u8>, key: &ParsedInternalKey) {
216 dst.extend_from_slice(&key.user_key);
217 put_fixed64(dst, pack_sequence_and_type(key.sequence, key.value_type));
218}
219
220pub fn parse_internal_key(internal_key: &[u8]) -> Option<ParsedInternalKey> {
221 if internal_key.len() < 8 {
222 return None;
223 }
224 let tag = decode_fixed64(&internal_key[internal_key.len() - 8..]);
225 let value_type = value_type_from_tag((tag & 0xff) as u8)?;
226 Some(ParsedInternalKey {
227 user_key: internal_key[..internal_key.len() - 8].to_vec(),
228 sequence: tag >> 8,
229 value_type,
230 })
231}
232
233pub fn extract_user_key(internal_key: &[u8]) -> Option<&[u8]> {
234 if internal_key.len() < 8 {
235 return None;
236 }
237 Some(&internal_key[..internal_key.len() - 8])
238}
239
240pub fn extract_value_type(internal_key: &[u8]) -> Option<ValueType> {
241 if internal_key.len() < 8 {
242 return None;
243 }
244 let tag = decode_fixed64(&internal_key[internal_key.len() - 8..]);
245 value_type_from_tag((tag & 0xff) as u8)
246}
247
248pub fn pack_sequence_and_type(sequence: SequenceNumber, value_type: ValueType) -> u64 {
249 assert!(sequence <= MAX_SEQUENCE_NUMBER);
250 (sequence << 8) | value_type as u64
251}
252
253fn value_type_from_tag(tag: u8) -> Option<ValueType> {
254 match tag {
255 0 => Some(ValueType::Deletion),
256 1 => Some(ValueType::Value),
257 _ => None,
258 }
259}
260
261fn required_user_key(internal_key: &[u8]) -> &[u8] {
262 extract_user_key(internal_key).expect("internal key requires an 8-byte tag")
263}