llkv_btree/views/
node_view.rs

1use crate::codecs::read_u32_at;
2use crate::errors::Error;
3use crate::pager::Pager;
4use std::ops::Range;
5
6#[repr(u8)]
7#[derive(Clone, Copy, Debug, PartialEq, Eq)]
8pub(crate) enum NodeTag {
9    Internal = 0,
10    Leaf = 1,
11}
12impl NodeTag {
13    pub(crate) fn from_u8(x: u8) -> Result<Self, Error> {
14        match x {
15            0 => Ok(NodeTag::Internal),
16            1 => Ok(NodeTag::Leaf),
17            _ => Err(Error::Corrupt("unknown node tag")),
18        }
19    }
20}
21
22#[derive(Clone)]
23pub struct NodeView<P: Pager> {
24    page: P::Page,
25}
26
27impl<P: Pager> NodeView<P> {
28    pub(crate) fn new(page: P::Page) -> Result<Self, Error> {
29        if page.len() < 9 {
30            Err(Error::Corrupt("node too small"))
31        } else {
32            Ok(Self { page })
33        }
34    }
35
36    #[inline]
37    pub(crate) fn as_slice(&self) -> &[u8] {
38        &self.page
39    }
40
41    // TODO: Use?
42    // #[inline]
43    // pub(crate) fn into_page(self) -> P::Page {
44    //     self.page
45    // }
46
47    #[inline]
48    pub(crate) fn tag(&self) -> Result<NodeTag, Error> {
49        NodeTag::from_u8(self.as_slice()[0])
50    }
51
52    #[inline]
53    pub(crate) fn count(&self) -> usize {
54        u32::from_le_bytes(self.as_slice()[1..5].try_into().unwrap()) as usize
55    }
56
57    #[inline]
58    pub(crate) fn aux_len(&self) -> usize {
59        u32::from_le_bytes(self.as_slice()[5..9].try_into().unwrap()) as usize
60    }
61
62    #[inline]
63    fn hdr_len(&self) -> usize {
64        9
65    }
66
67    #[inline]
68    fn is_leaf(&self) -> bool {
69        self.as_slice()[0] == NodeTag::Leaf as u8
70    }
71
72    #[inline]
73    pub(crate) fn aux_range(&self) -> Range<usize> {
74        let h = self.hdr_len();
75        h..(h + self.aux_len())
76    }
77
78    #[inline]
79    fn entries_start(&self) -> usize {
80        self.hdr_len() + self.aux_len()
81    }
82
83    #[inline]
84    fn index_entry_size(&self) -> usize {
85        if self.is_leaf() { 16 } else { 4 }
86    }
87
88    #[inline]
89    fn index_table_start(&self) -> usize {
90        self.as_slice().len() - self.count() * self.index_entry_size()
91    }
92
93    // -------- Internal node entry decoding (row layout) --------
94
95    #[inline]
96    fn entry_offset_at(&self, i: usize) -> usize {
97        let base = self.index_table_start();
98        let off = u32::from_le_bytes(
99            self.as_slice()[base + i * 4..base + (i + 1) * 4]
100                .try_into()
101                .unwrap(),
102        );
103        self.entries_start() + off as usize
104    }
105
106    #[inline]
107    fn entry_slice(&self, i: usize) -> &[u8] {
108        let start = self.entry_offset_at(i);
109        let end = if i + 1 < self.count() {
110            self.entry_offset_at(i + 1)
111        } else {
112            self.index_table_start()
113        };
114        &self.as_slice()[start..end]
115    }
116
117    pub(crate) fn internal_entry_slices(&self, i: usize) -> (&[u8], &[u8]) {
118        let e = self.entry_slice(i);
119        let (klen, mut pos) = read_u32_at(e, 0);
120        let key = &e[pos..pos + klen as usize];
121        pos += klen as usize;
122        let (ilen, pos2) = read_u32_at(e, pos);
123        let idb = &e[pos2..pos2 + ilen as usize];
124        (key, idb)
125    }
126
127    // ------------- Leaf node decoding (columnar layout) -------------
128
129    #[inline]
130    fn leaf_keys_base(&self) -> usize {
131        self.entries_start()
132    }
133
134    #[inline]
135    fn leaf_keys_len(&self) -> usize {
136        let n = self.count();
137        if n == 0 {
138            return 0;
139        }
140        let base = self.index_table_start() + (n - 1) * 16;
141        let k_off =
142            u32::from_le_bytes(self.as_slice()[base..base + 4].try_into().unwrap()) as usize;
143        let k_len =
144            u32::from_le_bytes(self.as_slice()[base + 4..base + 8].try_into().unwrap()) as usize;
145        k_off + k_len
146    }
147
148    #[inline]
149    fn leaf_values_base(&self) -> usize {
150        self.leaf_keys_base() + self.leaf_keys_len()
151    }
152
153    #[inline(always)]
154    pub(crate) fn leaf_index_fields(&self, i: usize) -> (usize, usize, usize, usize) {
155        let base = self.index_table_start() + i * 16;
156        let k_off =
157            u32::from_le_bytes(self.as_slice()[base..base + 4].try_into().unwrap()) as usize;
158        let k_len =
159            u32::from_le_bytes(self.as_slice()[base + 4..base + 8].try_into().unwrap()) as usize;
160        let v_off =
161            u32::from_le_bytes(self.as_slice()[base + 8..base + 12].try_into().unwrap()) as usize;
162        let v_len =
163            u32::from_le_bytes(self.as_slice()[base + 12..base + 16].try_into().unwrap()) as usize;
164        (k_off, k_len, v_off, v_len)
165    }
166
167    // TODO: Use?
168    // #[inline]
169    // pub(crate) fn leaf_entry_key_range(&self, i: usize) -> core::ops::Range<usize> {
170    //     let (k_off, k_len, _, _) = self.leaf_index_fields(i);
171    //     let start = self.leaf_keys_base() + k_off;
172    //     let end = start + k_len;
173    //     start..end
174    // }
175
176    #[inline]
177    pub(crate) fn leaf_entry_slices(&self, i: usize) -> (&[u8], &[u8]) {
178        let (k_off, k_len, v_off, v_len) = self.leaf_index_fields(i);
179        let kb = self.leaf_keys_base();
180        let vb = self.leaf_values_base();
181        let key = &self.as_slice()[kb + k_off..kb + k_off + k_len];
182        let val = &self.as_slice()[vb + v_off..vb + v_off + v_len];
183        (key, val)
184    }
185
186    /// Exact byte range of the value payload for entry `i`.
187    #[inline(always)]
188    pub(crate) fn leaf_entry_value_range(&self, i: usize) -> Range<usize> {
189        let (_, _, v_off, v_len) = self.leaf_index_fields(i);
190        let start = self.leaf_values_base() + v_off;
191        let end = start + v_len;
192        start..end
193    }
194
195    /// Aux area of a leaf: [u32 next_len][next_id_bytes...].
196    #[inline]
197    pub(crate) fn leaf_next_aux(&self) -> &[u8] {
198        let aux = &self.as_slice()[self.aux_range()];
199        if aux.len() < 4 {
200            return &aux[0..0];
201        }
202        let (n, pos) = read_u32_at(aux, 0);
203        &aux[pos..pos + n as usize]
204    }
205
206    // TODO: Use?
207    // Returns Some(width) if all keys are fixed-width and packed;
208    // else None.
209    #[inline]
210    pub fn leaf_fixed_key_width(&self) -> Option<usize> {
211        if !self.is_leaf() {
212            return None;
213        }
214        let n = self.count();
215        if n == 0 {
216            return None;
217        }
218        let keys_len = self.leaf_keys_len();
219        if keys_len == 0 || keys_len % n != 0 {
220            return None;
221        }
222        let w = keys_len / n;
223        // Validate a few positions to avoid O(n) checking.
224        let checks = [0usize, n / 2, n - 1].into_iter().collect::<Vec<_>>();
225        for &i in checks.iter() {
226            let (k_off, k_len, _, _) = self.leaf_index_fields(i);
227            if k_len != w || k_off != i * w {
228                return None;
229            }
230        }
231        Some(w)
232    }
233
234    /// Returns the contiguous keys block (leaf only).
235    #[inline]
236    pub(crate) fn leaf_keys_block(&self) -> &[u8] {
237        let kb = self.leaf_keys_base();
238        &self.as_slice()[kb..kb + self.leaf_keys_len()]
239    }
240}
llkv_btree/views/node_view.rs

llkv_btree/views/
node_view.rs
