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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
//! Inner node header type
use core::fmt::Debug;
use crate::{
raw::{LeafNode, NodePtr},
AsBytes,
};
/// The common header for all inner nodes
#[derive(Clone, PartialEq, Eq)]
pub struct Header<const PREFIX_LEN: usize> {
/// Number of children of this inner node. This field has no meaning for
/// a leaf node.
///
/// This needs to be a [`u16`], since a node 256 can hold up to 256 children
/// if this was a [`u8`] (0-255) it would overflow when adding the last
/// element
num_children: u16,
/// Number of bytes used by the prefix
prefix_len: u32,
/// The key prefix for this node.
prefix: [u8; PREFIX_LEN],
}
impl<const PREFIX_LEN: usize> Header<PREFIX_LEN> {
/// Create a new header with the given prefix and prefix length.
///
/// The given prefix length must be greater than or equal to `prefix.len()`.
/// If it is longer, it represents the case where there are implicit bytes
/// in the prefix.
///
/// There can also be implicit bytes in the prefix in the case that
/// `prefix.len()` > `PREFIX_LEN`, since the header will only store
/// `PREFIX_LEN` bytes directly.
#[inline]
pub fn new(prefix: &[u8], prefix_len: usize) -> Self {
debug_assert!(
prefix_len >= prefix.len(),
"Explicit prefix length must be greater than or equal to the length of the actual \
prefix passed."
);
let mut header = Self {
num_children: 0,
prefix_len: prefix_len as u32,
prefix: [0; PREFIX_LEN],
};
let len = prefix.len().min(PREFIX_LEN);
header.prefix[..len].copy_from_slice(&prefix[..len]);
header
}
/// Create a new `Header` for an empty node.
#[inline]
pub fn empty() -> Self {
Self {
num_children: 0,
prefix_len: 0,
prefix: [0; PREFIX_LEN],
}
}
/// Read the initialized portion of the prefix present in the header.
#[inline]
pub fn read_prefix(&self) -> &[u8] {
&self.prefix[0..self.capped_prefix_len()]
}
/// Get the number of bytes in the prefix.
#[inline]
pub fn prefix_len(&self) -> usize {
self.prefix_len as usize
}
/// Minimum between [`Self::prefix_len`] and `PREFIX_LEN`.
#[inline]
pub fn capped_prefix_len(&self) -> usize {
(self.prefix_len as usize).min(PREFIX_LEN)
}
/// Return the number of children of this node.
#[inline]
pub fn num_children(&self) -> usize {
usize::from(self.num_children)
}
/// Left trim by `len`, copies the remaining data to the beginning of the
/// prefix
///
/// # Panics
/// - If `len` > length of the prefix
#[inline]
pub fn ltrim_by(&mut self, len: usize) {
assert!(
(len as u32) <= self.prefix_len,
"given length [{len}] must be less than or equal to the prefix length [{}]",
self.prefix_len
);
self.prefix_len -= len as u32;
let begin = len;
let end = begin + self.capped_prefix_len();
unsafe {
// SAFETY: This function is called when mismatch happened and
// we used the node to match the number of bytes,
// by this we know that len < prefix len, but since we + 1,
// to skip the key byte we have that len <= prefix len
core::hint::assert_unchecked(end <= self.prefix.len());
// SAFETY: This is by construction end = begin + len
core::hint::assert_unchecked(begin <= end);
}
self.prefix.copy_within(begin..end, 0);
}
/// Set the length of the prefix to 0 and returns a copy of the
/// prefix, length and capped length
#[inline]
pub fn clear_prefix(&mut self) -> ([u8; PREFIX_LEN], usize, usize) {
let len = self.prefix_len();
let capped_len = self.capped_prefix_len();
self.prefix_len = 0;
(self.prefix, len, capped_len)
}
/// Append `new` to the prefix and sums `new_len` to the prefix length
#[inline]
pub fn push_prefix(&mut self, new: &[u8], new_len: usize) {
let begin = self.capped_prefix_len();
let end = (begin + new.len()).min(PREFIX_LEN);
let len = end - begin;
self.prefix[begin..end].copy_from_slice(&new[..len]);
self.prefix_len += new_len as u32;
}
/// Increments the number of children
#[inline]
pub fn inc_num_children(&mut self) {
self.num_children += 1;
}
/// Decrements the number of children
#[inline]
pub fn dec_num_children(&mut self) {
self.num_children -= 1;
}
/// Reset the number of children to 0.
#[inline]
pub fn reset_num_children(&mut self) {
self.num_children = 0;
}
/// Remove the `len` length starting portion of this header's prefix and
/// refill the prefix value with contents from the given leaf.
///
/// # Safety
///
/// This function must not be called concurrently with any other read or
/// modification of the given leaf or header.
#[inline]
pub unsafe fn ltrim_by_with_leaf<K: AsBytes, V>(
&mut self,
len: usize,
depth: usize,
leaf_ptr: NodePtr<PREFIX_LEN, LeafNode<K, V, PREFIX_LEN>>,
) {
self.prefix_len -= len as u32;
// SAFETY: Since have a mutable reference
// is safe to create a shared reference from it
let leaf_key = unsafe { leaf_ptr.as_key_ref().as_bytes() };
let begin = depth + len;
let end = begin + self.capped_prefix_len();
let len = end - begin;
unsafe {
// SAFETY: This function is called a mismatch happened and
// we used the leaf to match the number of matching bytes,
// by this we know that len < prefix len, but since we + 1,
// to skip the key byte we have that len <= prefix len
core::hint::assert_unchecked(end <= leaf_key.len());
// SAFETY: This is by construction end = begin + len
core::hint::assert_unchecked(begin <= end);
}
let leaf_key = &leaf_key[begin..end];
self.prefix[..len].copy_from_slice(leaf_key)
}
}
impl<const PREFIX_LEN: usize> Debug for Header<PREFIX_LEN> {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.debug_struct("Header")
.field("num_children", &self.num_children)
.field("prefix_len", &self.prefix_len)
.field(
"prefix",
&&self.prefix[..(self.prefix_len as usize).min(self.prefix.len())],
)
.finish()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn header_delete_prefix() {
let mut h = Header::<16>::new(&[1, 2, 3, 4, 5, 6, 7, 8], 8);
assert_eq!(h.read_prefix(), &[1, 2, 3, 4, 5, 6, 7, 8]);
assert_eq!(h.prefix_len(), 8);
h.ltrim_by(0);
assert_eq!(h.read_prefix(), &[1, 2, 3, 4, 5, 6, 7, 8]);
assert_eq!(h.prefix_len(), 8);
h.ltrim_by(3);
assert_eq!(h.read_prefix(), &[4, 5, 6, 7, 8]);
assert_eq!(h.prefix_len(), 5);
h.ltrim_by(1);
assert_eq!(h.read_prefix(), &[5, 6, 7, 8]);
assert_eq!(h.prefix_len(), 4);
h.ltrim_by(4);
assert_eq!(h.read_prefix(), &[] as &[u8]);
assert_eq!(h.prefix_len(), 0);
}
#[test]
#[should_panic = "given length [10] must be less than or equal to the prefix length [8]"]
fn header_ltrim_prefix_too_many_bytes_panic() {
let mut h = Header::<16>::new(&[1, 2, 3, 4, 5, 6, 7, 8], 8);
assert_eq!(h.read_prefix(), &[1, 2, 3, 4, 5, 6, 7, 8]);
assert_eq!(h.prefix_len(), 8);
h.ltrim_by(10);
}
}