btree/
page.rs

1use crate::error::Error;
2use crate::node::Node;
3use crate::node_type::{Key, NodeType, Offset};
4use crate::page_layout::{
5    ToByte, INTERNAL_NODE_HEADER_SIZE, INTERNAL_NODE_NUM_CHILDREN_OFFSET,
6    INTERNAL_NODE_NUM_CHILDREN_SIZE, IS_ROOT_OFFSET, KEY_SIZE, LEAF_NODE_HEADER_SIZE,
7    LEAF_NODE_NUM_PAIRS_OFFSET, LEAF_NODE_NUM_PAIRS_SIZE, NODE_TYPE_OFFSET, PAGE_SIZE,
8    PARENT_POINTER_OFFSET, PARENT_POINTER_SIZE, PTR_SIZE, VALUE_SIZE,
9};
10use std::convert::TryFrom;
11
12/// Value is a wrapper for a value in the page.
13pub struct Value(pub usize);
14
15/// Page is a wrapper for a single page of memory
16/// providing some helpful helpers for quick access.
17pub struct Page {
18    data: Box<[u8; PAGE_SIZE]>,
19}
20
21impl Page {
22    pub fn new(data: [u8; PAGE_SIZE]) -> Page {
23        Page {
24            data: Box::new(data),
25        }
26    }
27
28    /// write_value_at_offset writes a given value (as BigEndian) at a certain offset
29    /// overriding values at that offset.
30    pub fn write_value_at_offset(&mut self, offset: usize, value: usize) -> Result<(), Error> {
31        if offset > PAGE_SIZE - PTR_SIZE {
32            return Err(Error::UnexpectedError);
33        }
34        let bytes = value.to_be_bytes();
35        self.data[offset..offset + PTR_SIZE].clone_from_slice(&bytes);
36        Ok(())
37    }
38
39    /// get_value_from_offset Fetches a value calculated as BigEndian, sized to usize.
40    /// This function may error as the value might not fit into a usize.
41    pub fn get_value_from_offset(&self, offset: usize) -> Result<usize, Error> {
42        let bytes = &self.data[offset..offset + PTR_SIZE];
43        let Value(res) = Value::try_from(bytes)?;
44        Ok(res)
45    }
46
47    /// insert_bytes_at_offset pushes #size bytes from offset to end_offset
48    /// inserts #size bytes from given slice.
49    pub fn insert_bytes_at_offset(
50        &mut self,
51        bytes: &[u8],
52        offset: usize,
53        end_offset: usize,
54        size: usize,
55    ) -> Result<(), Error> {
56        // This Should not occur - better verify.
57        if end_offset + size > self.data.len() {
58            return Err(Error::UnexpectedError);
59        }
60        for idx in (offset..=end_offset).rev() {
61            self.data[idx + size] = self.data[idx]
62        }
63        self.data[offset..offset + size].clone_from_slice(bytes);
64        Ok(())
65    }
66
67    /// write_bytes_at_offset write bytes at a certain offset overriding previous values.
68    pub fn write_bytes_at_offset(
69        &mut self,
70        bytes: &[u8],
71        offset: usize,
72        size: usize,
73    ) -> Result<(), Error> {
74        self.data[offset..offset + size].clone_from_slice(bytes);
75        Ok(())
76    }
77
78    /// get_ptr_from_offset Fetches a slice of bytes from certain offset and of certain size.
79    pub fn get_ptr_from_offset(&self, offset: usize, size: usize) -> &[u8] {
80        &self.data[offset..offset + size]
81    }
82
83    /// get_data returns the underlying array.
84    pub fn get_data(&self) -> [u8; PAGE_SIZE] {
85        *self.data
86    }
87}
88
89/// Implement TryFrom<Box<Node>> for Page allowing for easier
90/// serialization of data from a Node to an on-disk formatted page.
91impl TryFrom<&Node> for Page {
92    type Error = Error;
93    fn try_from(node: &Node) -> Result<Page, Error> {
94        let mut data: [u8; PAGE_SIZE] = [0x00; PAGE_SIZE];
95        // is_root byte
96        data[IS_ROOT_OFFSET] = node.is_root.to_byte();
97
98        // node_type byte
99        data[NODE_TYPE_OFFSET] = u8::from(&node.node_type);
100
101        // parent offest
102        if !node.is_root {
103            match node.parent_offset {
104                Some(Offset(parent_offset)) => data
105                    [PARENT_POINTER_OFFSET..PARENT_POINTER_OFFSET + PARENT_POINTER_SIZE]
106                    .clone_from_slice(&parent_offset.to_be_bytes()),
107                // Expected an offset of an inner / leaf node.
108                None => return Err(Error::UnexpectedError),
109            };
110        }
111
112        match &node.node_type {
113            NodeType::Internal(child_offsets, keys) => {
114                data[INTERNAL_NODE_NUM_CHILDREN_OFFSET
115                    ..INTERNAL_NODE_NUM_CHILDREN_OFFSET + INTERNAL_NODE_NUM_CHILDREN_SIZE]
116                    .clone_from_slice(&child_offsets.len().to_be_bytes());
117
118                let mut page_offset = INTERNAL_NODE_HEADER_SIZE;
119                for Offset(child_offset) in child_offsets {
120                    data[page_offset..page_offset + PTR_SIZE]
121                        .clone_from_slice(&child_offset.to_be_bytes());
122                    page_offset += PTR_SIZE;
123                }
124
125                for Key(key) in keys {
126                    let key_bytes = key.as_bytes();
127                    let mut raw_key: [u8; KEY_SIZE] = [0x00; KEY_SIZE];
128                    if key_bytes.len() > KEY_SIZE {
129                        return Err(Error::KeyOverflowError);
130                    } else {
131                        for (i, byte) in key_bytes.iter().enumerate() {
132                            raw_key[i] = *byte;
133                        }
134                    }
135                    data[page_offset..page_offset + KEY_SIZE].clone_from_slice(&raw_key);
136                    page_offset += KEY_SIZE
137                }
138            }
139            NodeType::Leaf(kv_pairs) => {
140                // num of pairs
141                data[LEAF_NODE_NUM_PAIRS_OFFSET
142                    ..LEAF_NODE_NUM_PAIRS_OFFSET + LEAF_NODE_NUM_PAIRS_SIZE]
143                    .clone_from_slice(&kv_pairs.len().to_be_bytes());
144
145                let mut page_offset = LEAF_NODE_HEADER_SIZE;
146                for pair in kv_pairs {
147                    let key_bytes = pair.key.as_bytes();
148                    let mut raw_key: [u8; KEY_SIZE] = [0x00; KEY_SIZE];
149                    if key_bytes.len() > KEY_SIZE {
150                        return Err(Error::KeyOverflowError);
151                    } else {
152                        for (i, byte) in key_bytes.iter().enumerate() {
153                            raw_key[i] = *byte;
154                        }
155                    }
156                    data[page_offset..page_offset + KEY_SIZE].clone_from_slice(&raw_key);
157                    page_offset += KEY_SIZE;
158
159                    let value_bytes = pair.value.as_bytes();
160                    let mut raw_value: [u8; VALUE_SIZE] = [0x00; VALUE_SIZE];
161                    if value_bytes.len() > VALUE_SIZE {
162                        return Err(Error::ValueOverflowError);
163                    } else {
164                        for (i, byte) in value_bytes.iter().enumerate() {
165                            raw_value[i] = *byte;
166                        }
167                    }
168                    data[page_offset..page_offset + VALUE_SIZE].clone_from_slice(&raw_value);
169                    page_offset += VALUE_SIZE;
170                }
171            }
172            NodeType::Unexpected => return Err(Error::UnexpectedError),
173        }
174
175        Ok(Page::new(data))
176    }
177}
178
179/// Attempts to convert a slice to an array of a fixed size (PTR_SIZE),
180/// and then return the BigEndian value of the byte array.
181impl TryFrom<&[u8]> for Value {
182    type Error = Error;
183
184    fn try_from(arr: &[u8]) -> Result<Self, Self::Error> {
185        if arr.len() > PTR_SIZE {
186            return Err(Error::TryFromSliceError("Unexpected Error: Array recieved is larger than the maximum allowed size of: 4096B."));
187        }
188
189        let mut truncated_arr = [0u8; PTR_SIZE];
190        for (i, item) in arr.iter().enumerate() {
191            truncated_arr[i] = *item;
192        }
193
194        Ok(Value(usize::from_be_bytes(truncated_arr)))
195    }
196}
197
198#[cfg(test)]
199mod tests {
200    use crate::error::Error;
201
202    #[test]
203    fn node_to_page_works_for_leaf_node() -> Result<(), Error> {
204        use crate::node::Node;
205        use crate::node_type::{KeyValuePair, NodeType};
206        use crate::page::Page;
207        use std::convert::TryFrom;
208
209        let some_leaf = Node::new(
210            NodeType::Leaf(vec![
211                KeyValuePair::new("foo".to_string(), "bar".to_string()),
212                KeyValuePair::new("lebron".to_string(), "james".to_string()),
213                KeyValuePair::new("ariana".to_string(), "grande".to_string()),
214            ]),
215            true,
216            None,
217        );
218
219        // Serialize data.
220        let page = Page::try_from(&some_leaf)?;
221        // Deserialize back the page.
222        let res = Node::try_from(page)?;
223
224        assert_eq!(res.is_root, some_leaf.is_root);
225        assert_eq!(res.node_type, some_leaf.node_type);
226        assert_eq!(res.parent_offset, some_leaf.parent_offset);
227        Ok(())
228    }
229
230    #[test]
231    fn node_to_page_works_for_internal_node() -> Result<(), Error> {
232        use crate::node::Node;
233        use crate::node_type::{Key, NodeType, Offset};
234        use crate::page::Page;
235        use crate::page_layout::PAGE_SIZE;
236        use std::convert::TryFrom;
237
238        let internal_node = Node::new(
239            NodeType::Internal(
240                vec![
241                    Offset(PAGE_SIZE),
242                    Offset(PAGE_SIZE * 2),
243                    Offset(PAGE_SIZE * 3),
244                    Offset(PAGE_SIZE * 4),
245                ],
246                vec![
247                    Key("foo bar".to_string()),
248                    Key("lebron".to_string()),
249                    Key("ariana".to_string()),
250                ],
251            ),
252            true,
253            None,
254        );
255
256        // Serialize data.
257        let page = Page::try_from(&internal_node)?;
258        // Deserialize back the page.
259        let res = Node::try_from(page)?;
260
261        assert_eq!(res.is_root, internal_node.is_root);
262        assert_eq!(res.node_type, internal_node.node_type);
263        assert_eq!(res.parent_offset, internal_node.parent_offset);
264        Ok(())
265    }
266}
btree/page.rs

btree/
page.rs
