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 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434
//! An implementation of B trees. The core operations on B trees //! (lookup, iterate, put and del) are generic in the actual //! implementation of nodes, via the [`BTreePage`] and //! [`BTreeMutPage`]. This allows for a simpler code for the //! high-level functions, as well as specialised, high-performance //! implementations for the nodes. //! //! Two different implementations are supplied: one in [`page`] for //! types with a size known at compile-time, which yields denser //! leaves, and hence shallower trees (if the values are really using //! the space). The other one, in [`page_unsized`], is for //! dynamic-sized types, or types whose representation is dynamic, for //! example enums that are `Sized` in Rust, but whose cases vary //! widely in size. use crate::*; #[doc(hidden)] pub mod cursor; pub use cursor::{iter, rev_iter, Cursor, Iter, RevIter}; pub mod del; pub use del::del; pub mod put; pub use put::put; pub mod page; pub mod page_unsized; pub trait BTreePage<K: ?Sized, V: ?Sized>: Sized { type Cursor: Clone + Copy + core::fmt::Debug; /// Whether this cursor is at the end of the page. fn is_empty(c: &Self::Cursor) -> bool; /// Whether this cursor is strictly before the first element. fn is_init(c: &Self::Cursor) -> bool; /// Returns a cursor set before the first element of the page /// (i.e. set to -1). fn cursor_before(p: &CowPage) -> Self::Cursor; /// Returns a cursor set to the first element of the page /// (i.e. 0). If the page is empty, the returned cursor might be /// empty. fn cursor_first(p: &CowPage) -> Self::Cursor { let mut c = Self::cursor_before(p); Self::move_next(&mut c); c } /// Returns a cursor set after the last element of the page /// (i.e. to element n) fn cursor_after(p: &CowPage) -> Self::Cursor; /// Returns a cursor set to the last element of the page. If the /// cursor is empty, this is the same as `cursor_before`. fn cursor_last(p: &CowPage) -> Self::Cursor { let mut c = Self::cursor_after(p); Self::move_prev(&mut c); c } /// Return the element currently pointed to by the cursor (if the /// cursor is not before or after the elements of the page), and /// move the cursor to the next element. fn next<'b, T: LoadPage>( txn: &T, p: Page<'b>, c: &mut Self::Cursor, ) -> Option<(&'b K, &'b V, u64)> { if let Some((k, v, r)) = Self::current(txn, p, c) { Self::move_next(c); Some((k, v, r)) } else { None } } /// Move the cursor to the previous element, and return that /// element. In that sense, this is not the symmetric of `next`. fn prev<'b, T: LoadPage>( txn: &T, p: Page<'b>, c: &mut Self::Cursor, ) -> Option<(&'b K, &'b V, u64)> { if Self::move_prev(c) { Self::current(txn, p, c) } else { None } } /// Move the cursor to the next position. Returns whether the /// cursor was actually moved (i.e. `true` if and only if the /// cursor isn't already after the last element). fn move_next(c: &mut Self::Cursor) -> bool; /// Move the cursor to the previous position. Returns whether the /// cursor was actually moved (i.e. `true` if and only if the /// cursor isn't strictly before the page). fn move_prev(c: &mut Self::Cursor) -> bool; /// Returns the current element, if the cursor is pointing at one. fn current<'a, T: LoadPage>( txn: &T, p: Page<'a>, c: &Self::Cursor, ) -> Option<(&'a K, &'a V, u64)>; /// Returns the left child of the entry pointed to by the cursor. fn left_child(p: Page, c: &Self::Cursor) -> u64; /// Returns the right child of the entry pointed to by the cursor. fn right_child(p: Page, c: &Self::Cursor) -> u64; /// Sets the cursor to the last element less than or equal to `k0` /// if `v0.is_none()`, and to `(k0, v0)` if `v0.is_some()`. fn set_cursor<'a, T: LoadPage>( txn: &'a T, page: Page, c: &mut Self::Cursor, k0: &K, v0: Option<&V>, ) -> Result<(&'a K, &'a V, u64), usize>; fn split_at(c: &Self::Cursor) -> (Self::Cursor, Self::Cursor); } pub struct PageIterator<'a, T: LoadPage, K: ?Sized, V: ?Sized, P: BTreePage<K, V>> { cursor: P::Cursor, txn: &'a T, page: Page<'a>, } impl<'a, T: LoadPage, K: ?Sized + 'a, V: ?Sized + 'a, P: BTreePage<K, V>> Iterator for PageIterator<'a, T, K, V, P> { type Item = (&'a K, &'a V, u64); fn next(&mut self) -> Option<Self::Item> { P::next(self.txn, self.page, &mut self.cursor) } } pub trait BTreeMutPage<K: ?Sized, V: ?Sized>: BTreePage<K, V> + core::fmt::Debug { /// Initialise a page. fn init(page: &mut MutPage); /// Add an entry to the page, possibly splitting the page in the /// process. /// /// Makes the assumption that `k1v1.is_some()` implies /// `replace`. The "double insertion" is only ever used when /// deleting, and when the right child of a deleted entry (in an /// internal node) has split while we were looking for a /// replacement for the deleted entry. /// /// Since we only look for replacements in the right child, the /// left child of the insertion isn't modified, in which case `l` /// and `r` are interpreted as the left and right child of the new /// entry, `k1v1`. fn put<'a, T: AllocPage>( txn: &mut T, page: CowPage, mutable: bool, replace: bool, c: &Self::Cursor, k0: &'a K, v0: &'a V, k1v1: Option<(&'a K, &'a V)>, l: u64, r: u64, ) -> Result<crate::btree::put::Put<'a, K, V>, T::Error>; /// Add an entry to `page`, at position `c`. Does not check /// whether there is enough space to do so. This method is mostly /// useful for cloning pages. #[allow(unused_variables)] unsafe fn put_mut( page: &mut MutPage, c: &Self::Cursor, k0: &K, v0: &V, r: u64, ) { unimplemented!() } #[allow(unused_variables)] unsafe fn set_left_child( page: &mut MutPage, c: &Self::Cursor, l: u64 ) { unimplemented!() } /// Update the left child of the position pointed to by the /// cursor. fn update_left_child<T: AllocPage>( txn: &mut T, page: CowPage, mutable: bool, c: &Self::Cursor, r: u64, ) -> Result<crate::btree::put::Ok, T::Error>; type Saved; /// Save a leaf entry as a replacement, when we delete at an /// internal node. This can be a pointer to the leaf if the leaf /// isn't mutated, or the actual value, or something else. fn save_deleted_leaf_entry(k: &K, v: &V) -> Self::Saved; /// Recover the saved value. unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V); /// Delete an entry on the page, returning the resuting page along /// with the offset of the freed page (or 0 if no page was freed, /// i.e. if `page` is mutable). fn del<T: AllocPage>( txn: &mut T, page: CowPage, mutable: bool, c: &Self::Cursor, l: u64, ) -> Result<(MutPage, u64), T::Error>; /// Merge, rebalance or update a concatenation. fn merge_or_rebalance<'a, 'b, T: AllocPage>( txn: &mut T, m: del::Concat<'a, K, V, Self>, ) -> Result<del::Op<'a, T, K, V>, T::Error>; } /// A database, which is essentially just a page offset along with markers. #[derive(Debug)] pub struct Db_<K: ?Sized, V: ?Sized, P: BTreePage<K, V>> { pub db: u64, pub k: core::marker::PhantomData<K>, pub v: core::marker::PhantomData<V>, pub p: core::marker::PhantomData<P>, } /// A database of sized values. pub type Db<K, V> = Db_<K, V, page::Page<K, V>>; /// A database of unsized values. pub type UDb<K, V> = Db_<K, V, page_unsized::Page<K, V>>; impl<K: ?Sized, V: ?Sized, P: BTreePage<K, V>> Db_<K, V, P> { /// Load a database from a page offset. pub fn from_page(db: u64) -> Self { Db_ { db, k: core::marker::PhantomData, v: core::marker::PhantomData, p: core::marker::PhantomData, } } } /// Create a database with an arbitrary page implementation. pub fn create_db_<T: AllocPage, K: ?Sized, V: ?Sized, P: BTreeMutPage<K, V>>( txn: &mut T, ) -> Result<Db_<K, V, P>, T::Error> { let mut page = txn.alloc_page()?; P::init(&mut page); Ok(Db_ { db: page.0.offset, k: core::marker::PhantomData, v: core::marker::PhantomData, p: core::marker::PhantomData, }) } /// Create a database for sized keys and values. pub fn create_db<T: AllocPage, K: Storable, V: Storable>( txn: &mut T, ) -> Result<Db_<K, V, page::Page<K, V>>, T::Error> { create_db_(txn) } /// Fork a database. pub fn fork_db<T: AllocPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreeMutPage<K, V>>( txn: &mut T, db: &Db_<K, V, P>, ) -> Result<Db_<K, V, P>, T::Error> { txn.incr_rc(db.db)?; Ok(Db_ { db: db.db, k: core::marker::PhantomData, v: core::marker::PhantomData, p: core::marker::PhantomData, }) } /// Get the first entry of a database greater than or equal to `k` (or /// to `(k, v)` if `v.is_some()`). pub fn get<'a, T: LoadPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreePage<K, V>>( txn: &'a T, db: &Db_<K, V, P>, k: &K, v: Option<&V>, ) -> Result<Option<(&'a K, &'a V)>, T::Error> { // Set the "cursor stack" by setting a skip list cursor in // each page from the root to the appropriate leaf. let mut last_match = None; let mut page = txn.load_page(db.db)?; // This is a for loop, to allow the compiler to unroll (maybe). for _ in 0..cursor::N_CURSORS { let mut cursor = P::cursor_before(&page); if let Ok((kk, vv, _)) = P::set_cursor(txn, page.as_page(), &mut cursor, k, v) { if v.is_some() { return Ok(Some((kk, vv))); } last_match = Some((kk, vv)); } else if let Some((k, v, _)) = P::current(txn, page.as_page(), &cursor) { // Here, Rust says that `k` and `v` have the same lifetime // as `page`, but we actually know that they're alive for // as long as `txn` doesn't change, so we can safely // extend their lifetimes: unsafe { last_match = Some((core::mem::transmute(k), core::mem::transmute(v))) } } // The cursor is set to the first element greater than or // equal to the (k, v) we're looking for, so we need to // explore the left subtree. let next_page = P::left_child(page.as_page(), &cursor); if next_page > 0 { page = txn.load_page(next_page)?; } else { break; } } Ok(last_match) } /// Drop a database recursively, dropping all referenced keys and /// values that aren't shared with other databases. pub fn drop<T: AllocPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreePage<K, V>>( txn: &mut T, db: Db_<K, V, P>, ) -> Result<(), T::Error> { // In order to make this function tail-recursive, we simulate a // stack with the following: use core::mem::MaybeUninit; let mut stack: [MaybeUninit<cursor::PageCursor<K, V, P>>; cursor::N_CURSORS] = [ MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), MaybeUninit::uninit(), ]; let mut ptr = 0; // Push the root page of `db` onto the stack. let page = txn.load_page(db.db)?; stack[0] = MaybeUninit::new(cursor::PageCursor { cursor: P::cursor_before(&page), page, }); // Then perform a DFS: loop { // Look at the top element of the stack. let cur = unsafe { &mut *stack[ptr].as_mut_ptr() }; // If it needs to be dropped (i.e. if its RC is <= 1), iterate // its cursor and drop all its referenced pages. let rc = txn.rc(cur.page.offset)?; if rc <= 1 { // if there's a current element in the cursor (i.e. we // aren't before or after the elements), decrease its RC. if let Some((k, v, _)) = P::current(txn, cur.page.as_page(), &cur.cursor) { for o in k.page_references().chain(v.page_references()) { txn.decr_rc(o)?; } } // In all cases, move next and push the left child onto // the stack. This works because pushed cursors are // initially set to before the page's elements. if P::move_next(&mut cur.cursor) { let r = P::left_child(cur.page.as_page(), &cur.cursor); if r > 0 { ptr += 1; let page = txn.load_page(r)?; stack[ptr] = MaybeUninit::new(cursor::PageCursor { cursor: P::cursor_before(&page), page, }) } continue; } } // Here, either rc > 1, or else `P::move_next` returned // `false`, meaning that the cursor is after the last element. if cur.page.is_dirty() { txn.decr_rc_owned(cur.page.offset)?; } else { txn.decr_rc(cur.page.offset)?; } // If this was the bottom element of the stack, stop, else, pop. if ptr == 0 { break; } else { ptr -= 1; } } Ok(()) }