extended_collections/bp_tree/
pager.rs

1use bincode::{self, deserialize, serialize, serialized_size};
2use bp_tree::node::{LeafNode, Node};
3use serde::de::DeserializeOwned;
4use serde::ser::Serialize;
5use std::borrow::Borrow;
6use std::error;
7use std::fmt;
8use std::fs::{File, OpenOptions};
9use std::io::{self, Read, Seek, SeekFrom, Write};
10use std::marker::PhantomData;
11use std::mem;
12use std::path::Path;
13use std::result;
14
15/// Convenience `Error` enum for `bp_tree`.
16#[derive(Debug)]
17pub enum Error {
18    /// An input or output error.
19    IOError(io::Error),
20    /// A serialization or deserialization error.
21    SerdeError(bincode::Error),
22}
23
24impl From<io::Error> for Error {
25    fn from(err: io::Error) -> Error {
26        Error::IOError(err)
27    }
28}
29
30impl From<bincode::Error> for Error {
31    fn from(err: bincode::Error) -> Error {
32        Error::SerdeError(err)
33    }
34}
35
36impl error::Error for Error {
37    fn description(&self) -> &str {
38        match self {
39            Error::IOError(ref error) => error.description(),
40            Error::SerdeError(ref error) => error.description(),
41        }
42    }
43
44    fn cause(&self) -> Option<&error::Error> {
45        match self {
46            Error::IOError(ref error) => error.cause(),
47            Error::SerdeError(ref error) => error.cause(),
48        }
49    }
50}
51
52impl fmt::Display for Error {
53    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
54        match self {
55            Error::IOError(ref error) => write!(f, "{}", error),
56            Error::SerdeError(ref error) => write!(f, "{}", error),
57        }
58    }
59}
60
61/// Convenience `Result` type for `bp_tree`.
62pub type Result<T> = result::Result<T, Error>;
63
64#[derive(Serialize, Deserialize)]
65struct Metadata {
66    pages: usize,
67    len: usize,
68    root_page: usize,
69    key_size: u64,
70    value_size: u64,
71    leaf_degree: usize,
72    internal_degree: usize,
73    free_page: Option<usize>,
74}
75
76pub struct Pager<T, U> {
77    db_file: File,
78    metadata: Metadata,
79    _marker: PhantomData<(T, U)>,
80}
81
82impl<T, U> Pager<T, U> {
83    pub fn new<P>(
84        file_path: P,
85        key_size: u64,
86        value_size: u64,
87        leaf_degree: usize,
88        internal_degree: usize,
89    ) -> Result<Pager<T, U>>
90    where
91        T: Serialize,
92        U: Serialize,
93        P: AsRef<Path>,
94    {
95        let header_size = Self::get_metadata_size();
96        let body_size = Node::<T, U>::get_max_size(
97            key_size,
98            value_size,
99            leaf_degree,
100            internal_degree
101        ) as u64;
102        let metadata = Metadata {
103            pages: 1,
104            len: 0,
105            root_page: 0,
106            key_size,
107            value_size,
108            leaf_degree,
109            internal_degree,
110            free_page: None,
111        };
112        let mut db_file = OpenOptions::new()
113            .read(true)
114            .write(true)
115            .create(true)
116            .open(file_path)?;
117        db_file.set_len(header_size + body_size)?;
118
119        db_file.seek(SeekFrom::Start(0))?;
120        let serialized_metadata = &serialize(&metadata)?;
121        db_file.write_all(serialized_metadata)?;
122
123        db_file.seek(SeekFrom::Start(header_size))?;
124        let serialized_node = &serialize(&Node::Leaf(LeafNode::<T, U>::new(leaf_degree)))?;
125        db_file.write_all(serialized_node)?;
126
127        let pager = Pager {
128            db_file,
129            metadata,
130            _marker: PhantomData,
131        };
132
133        Ok(pager)
134    }
135
136    pub fn open<P>(file_path: P) -> Result<Pager<T, U>>
137    where
138        P: AsRef<Path>,
139    {
140        let mut db_file = OpenOptions::new()
141            .read(true)
142            .write(true)
143            .create(true)
144            .open(file_path)?;
145        db_file.seek(SeekFrom::Start(0))?;
146
147        let mut buffer: Vec<u8> = vec![0; Self::get_metadata_size() as usize];
148        db_file.read_exact(buffer.as_mut_slice())?;
149        let metadata = deserialize(buffer.as_slice())?;
150
151        Ok(Pager {
152            db_file,
153            metadata,
154            _marker: PhantomData,
155        })
156    }
157
158    #[inline]
159    fn get_node_size(&self) -> u64 {
160        Node::<T, U>::get_max_size(
161            self.metadata.key_size,
162            self.metadata.value_size,
163            self.metadata.leaf_degree,
164            self.metadata.internal_degree,
165        ) as u64
166    }
167
168    #[inline]
169    fn get_metadata_size() -> u64 {
170        mem::size_of::<Metadata>() as u64
171    }
172
173    fn calculate_page_offset(&self, index: usize) -> u64 {
174        let header_size = Self::get_metadata_size();
175        let body_offset = self.get_node_size() * index as u64;
176        header_size + body_offset
177    }
178
179    pub fn get_leaf_degree(&self) -> usize {
180        self.metadata.leaf_degree
181    }
182
183    pub fn get_internal_degree(&self) -> usize {
184        self.metadata.internal_degree
185    }
186
187    pub fn get_len(&self) -> usize {
188        self.metadata.len
189    }
190
191    pub fn set_len(&mut self, len: usize) -> Result<()> {
192        self.metadata.len = len;
193        self.db_file.seek(SeekFrom::Start(0))?;
194        let serialized_metadata = &serialize(&self.metadata)?;
195        self.db_file.write_all(serialized_metadata).map_err(Error::IOError)
196    }
197
198    pub fn get_root_page(&self) -> usize {
199        self.metadata.root_page
200    }
201
202    pub fn set_root_page(&mut self, new_root_page: usize) -> Result<()> {
203        self.metadata.root_page = new_root_page;
204        self.db_file.seek(SeekFrom::Start(0))?;
205        let serialized_metadata = &serialize(&self.metadata)?;
206        self.db_file.write_all(serialized_metadata).map_err(Error::IOError)
207    }
208
209    pub fn get_page(&mut self, index: usize) -> Result<Node<T, U>>
210    where
211        T: DeserializeOwned,
212        U: DeserializeOwned,
213    {
214        let offset = self.calculate_page_offset(index);
215        self.db_file.seek(SeekFrom::Start(offset))?;
216        let mut buffer: Vec<u8> = vec![0; self.get_node_size() as usize];
217        self.db_file.read_exact(buffer.as_mut_slice())?;
218        deserialize(buffer.as_slice()).map_err(Error::SerdeError)
219    }
220
221    pub fn allocate_node(&mut self, new_node: &Node<T, U>) -> Result<usize>
222    where
223        T: DeserializeOwned + Serialize,
224        U: DeserializeOwned + Serialize,
225    {
226        match self.metadata.free_page {
227            None => {
228                self.metadata.pages += 1;
229                let len = self.calculate_page_offset(self.metadata.pages);
230                let node_size = self.get_node_size();
231                self.db_file.set_len(len)?;
232                self.db_file.seek(SeekFrom::Start(len - node_size))?;
233                let serialized_node = &serialize(&new_node)?;
234                self.db_file.write_all(serialized_node)?;
235
236                self.db_file.seek(SeekFrom::Start(0))?;
237                let serialized_metadata = &serialize(&self.metadata)?;
238                self.db_file.write_all(serialized_metadata)?;
239
240                Ok(self.metadata.pages - 1)
241            },
242            Some(free_page) => {
243                let offset = self.calculate_page_offset(free_page);
244                let mut buffer: Vec<u8> = vec![0; self.get_node_size() as usize];
245
246                self.db_file.seek(SeekFrom::Start(offset))?;
247                self.db_file.read_exact(buffer.as_mut_slice())?;
248
249                self.db_file.seek(SeekFrom::Start(offset))?;
250                let serialized_node = &serialize(&new_node)?;
251                self.db_file.write_all(serialized_node)?;
252
253                match deserialize(buffer.as_slice())? {
254                    Node::Free::<T, U>(new_free_page) => self.metadata.free_page = new_free_page,
255                    _ => unreachable!(),
256                }
257                self.db_file.seek(SeekFrom::Start(0))?;
258                let serialized_metadata = &serialize(&self.metadata)?;
259                self.db_file.write_all(serialized_metadata)?;
260
261                Ok(free_page)
262            },
263        }
264    }
265
266    pub fn deallocate_node(&mut self, index: usize) -> Result<()>
267    where
268        T: Serialize,
269        U: Serialize,
270    {
271        let offset = self.calculate_page_offset(index);
272
273        self.db_file.seek(SeekFrom::Start(offset))?;
274        let serialized_node = &serialize(&Node::Free::<T, U>(self.metadata.free_page))?;
275        self.db_file.write_all(serialized_node)?;
276
277        self.metadata.free_page = Some(index);
278        self.db_file.seek(SeekFrom::Start(0))?;
279        let serialized_metadata = &serialize(&self.metadata)?;
280        self.db_file.write_all(serialized_metadata).map_err(Error::IOError)
281    }
282
283    pub fn write_node(&mut self, index: usize, node: &Node<T, U>) -> Result<()>
284    where
285        T: Serialize,
286        U: Serialize,
287    {
288        let offset = self.calculate_page_offset(index);
289        self.db_file.seek(SeekFrom::Start(offset))?;
290        let serialized_node = &serialize(&node)?;
291        self.db_file.write_all(serialized_node).map_err(Error::IOError)
292    }
293
294    pub fn clear(&mut self) -> Result<()>
295    where
296        T: Serialize,
297        U: Serialize,
298    {
299        let header_size = Self::get_metadata_size();
300        let body_size = self.get_node_size();
301        self.metadata.pages = 1;
302        self.metadata.len = 0;
303        self.metadata.root_page = 0;
304        self.metadata.free_page = None;
305        self.db_file.set_len(header_size + body_size)?;
306
307        self.db_file.seek(SeekFrom::Start(0))?;
308        let serialized_metadata = &serialize(&self.metadata)?;
309        self.db_file.write_all(serialized_metadata)?;
310
311        self.db_file.seek(SeekFrom::Start(header_size))?;
312        let serialized_node = &serialize(&Node::Leaf(LeafNode::<T, U>::new(self.metadata.leaf_degree)))?;
313        self.db_file.write_all(serialized_node).map_err(Error::IOError)
314    }
315
316    pub fn validate_key<V>(&self, key: &V) -> Result<()>
317    where
318        T: Borrow<V>,
319        V: Serialize + ?Sized,
320    {
321        assert!(serialized_size(key)? <= self.metadata.key_size);
322        Ok(())
323    }
324
325    pub fn validate_value<V>(&self, value: &V) -> Result<()>
326    where
327        U: Borrow<V>,
328        V: Serialize + ?Sized,
329    {
330        assert!(serialized_size(value)? <= self.metadata.value_size);
331        Ok(())
332    }
333}
extended_collections/bp_tree/pager.rs

extended_collections/bp_tree/
pager.rs
