Fully commented implementation of Sized nodes + massive cleanup
[?]
Feb 14, 2021, 10:29 PM
TSMS6W4DOKQNUQ4PEMTLOIODR33VFPN6MMNS73ZPSU4BOQVRGPNACDependencies
- [2]
CCNPHVQCCleanup, comments, renaming - [3]
WS4ZQM4RDebugging, tests, etc. - [4]
ONES3V46reference counting works for put - [5]
OFINGD26implementing prev() on cursors (+ some cleanup) - [6]
RV2L6CZWA few comments - [7]
7WJNSPEWUsing the same definition of the "occupied" field uniform everywhere - [8]
APPY2E7MUnsized deletions + custom sizes back - [9]
73Z2UB3JCleanup + comments - [10]
UAQX27N4Tests - [11]
XEU2QVLCDebugging after plugging this into Pijul - [12]
PXF3R6SVImproving test coverage for btree::cursor - [13]
EHJFNMB2Debugging - [14]
W26CFMAQImproving safety of cursors - [15]
MSRWB47YDeletions at immutable leaves weren't really deleting anything - [16]
DV4A2LR7Double-inserts (rebalancing near an internal deletion) - [17]
LROAI3NBTwo iterators (convenience functions), along with tests to move cursors (put and del still destroy cursors though) - [18]
Q7DRIBBRDebugging replace (which cannot be del+put) - [19]
EAAYH6BQDebugging put - [20]
FMN7X4J2Micro-improvements, now noticeably faster than std::collections::BTreeMap - [21]
KMT3MF5NDrop a database - [22]
OTWDDJE7Trait/type cleanup - [23]
AOX2XQISActually, with the correct functions, Unsized pages are always slower than Sized pages (especially for writing) - [24]
HN6Z5DU4Cleanup - [25]
T73WR2BXCleaner RC increments for keys and values containing references + more comments in `del` - [26]
YXKP4AIWNew file locks, with multiple sets of free pages - [27]
NXMFNPZ7Comments + debugging drop - [28]
7P43FPFAWhen deleting in internal nodes, set the correct child - [29]
QEUTVAZ4Splitting btree::page - [30]
ESUI5EUZMaking as_page() unsafe - [31]
KX3WVNZWTesting/debugging "rebalance causes split of the root" - [32]
H3FVSQIQUnsized pages - [33]
X3QVVQISMore debugging (del seems to work now) - [34]
UUUVNC4DDebugging/cleanup around cursors - [35]
6DCQHIFPMinor changes after benchmarking - [36]
6DMPXOATMore debugging - [37]
OP6SVMODResetting history - [38]
KM3JAFGPAdding a test for next/prev - [39]
LSQ6V7M6Cleanup + docs - [40]
QYDGYIZRSplit trait Representable into its mandatory part and an optional part - [41]
6UVFCERMFormatting, debugging, etc.
Change contents
- replacement in sanakirja-core/src/lib.rs at line 284
/// Same as [`decr_rc`], but for pages allocated by the current/// Same as [`Self::decr_rc`], but for pages allocated by the current - edit in sanakirja-core/src/btree/put.rs at line 1
//! Insertions into a B tree. - edit in sanakirja-core/src/btree/put.rs at line 4
/// The representation of the update to a page.#[derive(Debug)]pub struct Ok {/// The new page, possibly the same as the previous version.pub page: MutPage,/// The freed page, or 0 if no page was freed.pub freed: u64,} - edit in sanakirja-core/src/btree/put.rs at line 14
/// The result of an insertion, i.e. either an update or a split.#[derive(Debug)]pub enum Put<'a, K: ?Sized, V: ?Sized> {Ok(Ok),Split {split_key: &'a K,split_value: &'a V,left: MutPage,right: MutPage,freed: u64,},} - replacement in sanakirja-core/src/btree/put.rs at line 45
if cursor.set(txn, Some((key, Some(value))))?.is_some() {if cursor.set(txn, key, Some(value))?.is_some() { - replacement in sanakirja-core/src/btree/put.rs at line 55
let is_owned = p < cursor.first_rc_len;let is_owned = p < cursor.first_rc_len(); - replacement in sanakirja-core/src/btree/put.rs at line 128
let is_owned = cursor.len() < cursor.first_rc_len;let is_owned = cursor.len() < cursor.first_rc_len(); - replacement in sanakirja-core/src/btree/put.rs at line 182
let is_owned = cursor.len() < cursor.first_rc_len;let is_owned = cursor.len() < cursor.first_rc_len(); - replacement in sanakirja-core/src/btree/put.rs at line 214
if cursor.len() < cursor.first_rc_len {if cursor.len() < cursor.first_rc_len() { - replacement in sanakirja-core/src/btree/put.rs at line 222
if cursor.len() == cursor.first_rc_len {if cursor.len() == cursor.first_rc_len() { - edit in sanakirja-core/src/btree/page_unsized.rs at line 2
use crate::btree::del::*;use crate::btree::put::*; - edit in sanakirja-core/src/btree/page_unsized.rs at line 27
debug!("init {:?}", page); - edit in sanakirja-core/src/btree/page_unsized.rs at line 29
debug!("init: {:?}", h); - replacement in sanakirja-core/src/btree/page_unsized.rs at line 36
fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {unsafe { (&*s.0, &*s.1) }unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {(&*s.0, &*s.1) - replacement in sanakirja-core/src/btree/page_unsized.rs at line 51
) -> Result<Put<'a, K, V>, T::Error> {) -> Result<crate::btree::put::Put<'a, K, V>, T::Error> { - replacement in sanakirja-core/src/btree/page_unsized.rs at line 88
) -> Result<Ok, T::Error> {) -> Result<crate::btree::put::Ok, T::Error> { - replacement in sanakirja-core/src/btree/page_unsized.rs at line 385
txn: &T,txn: &'a T, - edit in sanakirja-core/src/btree/page_unsized.rs at line 392
// `lookup` has the same semantic as// `core::slice::binary_search`, i.e. it returns either// `Ok(n)`, where `n` is the position where `(k0, v0)` was// found, or `Err(n)` where `n` is the position where// `(k0, v0)` can be inserted to preserve the order. - replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 21
) -> Result<Put<'a, K, V>, T::Error> {) -> Result<crate::btree::put::Put<'a, K, V>, T::Error> { - replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 108
) -> Result<Put<'a, K, V>, T::Error> {) -> Result<crate::btree::put::Put<'a, K, V>, T::Error> { - replacement in sanakirja-core/src/btree/page_unsized/header.rs at line 14
self.data = (((PAGE_SIZE as u16) << 1) | 1).to_le();self.data = (((PAGE_SIZE as u16) << 3) | 1).to_le(); - replacement in sanakirja-core/src/btree/page_unsized/header.rs at line 41
u16::from_le(self.data) >> 1u16::from_le(self.data) >> 3 - replacement in sanakirja-core/src/btree/page_unsized/header.rs at line 45
let dirty = u16::from_le(self.data) & 1;self.data = ((d << 1) | dirty).to_le()let dirty = u16::from_le(self.data) & 7;self.data = ((d << 3) | dirty).to_le() - edit in sanakirja-core/src/btree/page.rs at line 1
//! Implementation of B tree pages for Sized types, i.e. types whose//! representation has a size known at compile time (and the same as//! `core::mem::size_of()`).//!//! The details of the implementation are as follows://!//! - The page starts with a 16 bytes header of the following form//! (where all the fields are encoded in Little-Endian)://!//! ```//! #[repr(C)]//! pub struct Header {//! /// Offset to the first entry in the page, shifted 3 bits//! /// to the right to allow for the dirty bit (plus two//! /// extra bits, zero for now), as explained in the//! /// documentation of CowPage, at the root of this//! /// crate. This is 4096 for empty pages, and it is unused//! /// for leaves. Moreover, this field can't be increased://! /// when it reaches the bottom, the page must be cloned.//! data: u16,//! /// Number of entries on the page.//! n: u16,//! /// CRC (if used).//! crc: u32,//! /// The 52 most significant bits are the left child of//! /// this page (0 for leaves), while the 12 LSBs represent//! /// the space this page would take when cloned from scratch,//! /// minus the header. The reason for this is that entries//! /// in internal nodes aren't really removed when deleted,//! /// they're only "unlinked" from the array of offsets (see//! /// below). Therefore, we must have a way to tell when a//! /// page can be "compacted" to reclaim space.//! left_page: u64,//! }//! ```//! - For leaves, the rest of the page has the same representation as//! an array of length `n`, of elements of type `Tuple<K, V>`://! ```//! #[repr(C)]//! struct Tuple<K, V> {//! k: K,//! v: V,//! }//! ```//! If the alignment of that structure is more than 16 bytes, we//! need to add some padding between the header and that array.//! - For internal nodes, the rest of the page starts with an array of//! length `n` of Little-Endian-encoded `u64`, where the 12 least//! significant bits of each `u64` are an offset to a `Tuple<K, V>` in//! the page, and the 52 other bits are an offset in the file to the//! right child of the entry.//!//! Moreover, the offset represented by the 12 LSBs is after (or at)//! `header.data`.//! We say we can "allocate" in the page if the `data` of the header//! is greater than or equal to the position of the last "offset",//! plus the size we want to allocate (note that since we allocate//! from the end of the page, `data` is always a multiple of the//! alignment of `Tuple<K, V>`). - edit in sanakirja-core/src/btree/page.rs at line 68
use crate::btree::del::*;use crate::btree::put::*; - replacement in sanakirja-core/src/btree/page.rs at line 73
mod alloc;mod put;mod alloc; // The "alloc" trait, to provide common methods for leaves and internal nodes.mod put; // Inserting a new value onto a page (possibly splitting the page).mod rebalance; // Rebalance two sibling pages to the left or to the right.use super::page_unsized::{header, PageCursor}; - edit in sanakirja-core/src/btree/page.rs at line 82
mod rebalance;use super::page_unsized::header;pub use super::page_unsized::PageCursor; - edit in sanakirja-core/src/btree/page.rs at line 96
/// Empty type implementing `BTreePage` and `BTreeMutPage`. - edit in sanakirja-core/src/btree/page.rs at line 101
// Cursors are quite straightforward. One non-trivial thing is// that they represent both a position on a page and the interval// from that position to the end of the page, as is apparent in// their `split_at` method.//// Another thing to note is that -1 and `c.total` are valid// positions for a cursor `c`. The reason for this is that// position `-1` has a right child (which is the left child of the// first element). - replacement in sanakirja-core/src/btree/page.rs at line 128[3.2709]→[3.2709:2742](∅→∅),[3.2742]→[3.4797:4815](∅→∅),[3.4815]→[3.2759:2855](∅→∅),[3.2759]→[3.2759:2855](∅→∅),[3.2855]→[3.2855:2954](∅→∅),[3.2954]→[3.7103:7160](∅→∅),[3.7160]→[3.2996:3020](∅→∅),[3.2996]→[3.2996:3020](∅→∅),[3.3020]→[3.4816:4879](∅→∅),[3.4879]→[3.3069:3200](∅→∅),[3.3069]→[3.3069:3200](∅→∅),[3.3200]→[3.4880:5009](∅→∅),[3.5009]→[3.3470:3648](∅→∅),[3.3470]→[3.3470:3648](∅→∅),[3.3648]→[3.5010:5160](∅→∅),[3.5160]→[3.3939:3963](∅→∅),[3.3939]→[3.3939:3963](∅→∅)
fn current<'a, T: LoadPage>(_txn: &T,page: crate::Page<'a>,c: &Self::Cursor,) -> Option<(&'a K, &'a V, u64)> {if c.cur < 0 || c.cur >= c.total as isize {None} else if c.is_leaf {let f = core::mem::size_of::<Tuple<K, V>>();let off = {let al = core::mem::align_of::<Tuple<K, V>>();let hdr = (HDR + al - 1) & !(al - 1);hdr + c.cur as usize * f};unsafe {let kv = &*(page.data.as_ptr().add(off as usize) as *const Tuple<K, V>);Some((&kv.k, &kv.v, 0))}} else {unsafe {let off =u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur as usize));let kv = &*(page.data.as_ptr().add((off as usize) & 0xfff) as *const Tuple<K, V>);Some((&kv.k, &kv.v, off & !0xfff))}}fn split_at(c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {(PageCursor {cur: 0,total: c.cur.max(0) as usize,is_leaf: c.is_leaf,},*c,) - edit in sanakirja-core/src/btree/page.rs at line 163
}}// This is the first non-trivial method, let's explain it.fn current<'a, T: LoadPage>(_txn: &T,page: crate::Page<'a>,c: &Self::Cursor,) -> Option<(&'a K, &'a V, u64)> {// First, there's no current entry if the cursor is outside// the range of entries.if c.cur < 0 || c.cur >= c.total as isize {None} else if c.is_leaf {// Else, if this is a leaf, the elements are packed// together in a contiguous array.//// This means that the header may be followed by// padding. These are constants known at compile-time, by// the way, so `al` and `hdr` are optimised away by the// compiler.let al = core::mem::align_of::<Tuple<K, V>>();// The following is a way to compute the first multiple of// `al` after `HDR`, assuming `al` is a power of 2 (which// is always the case since we get it from `align_of`).let hdr = (HDR + al - 1) & !(al - 1);// The position of the `Tuple<K, V>` we're looking for is// `f * cur` bytes after the padded header:let f = core::mem::size_of::<Tuple<K, V>>();let kv = unsafe {&*(page.data.as_ptr().add(hdr + c.cur as usize * f) as *const Tuple<K, V>)};Some((&kv.k, &kv.v, 0))} else {// Internal nodes have an extra level of indirection: we// first need to find `off`, the offset in the page, in// the initial array of offsets. Since these offsets are// `u64`, and the header is of size 16 bytes, the array is// already aligned.unsafe {let off =u64::from_le(*(page.data.as_ptr().add(HDR + 8 * c.cur as usize) as *const u64));// Check that we aren't reading outside of the page// (for example because of a malformed offset).assert!((off as usize & 0xfff) + core::mem::size_of::<Tuple<K, V>>() <= 4096);// Once we have the offset, cast its 12 LSBs to a// position in the page, and read the `Tuple<K, V>` at// that position.let kv = &*(page.data.as_ptr().add((off as usize) & 0xfff) as *const Tuple<K, V>);Some((&kv.k, &kv.v, off & !0xfff))} - edit in sanakirja-core/src/btree/page.rs at line 220
// The left and right child methods aren't really surprising. One// thing to note is that cursors are always in positions between// `-1` and `c.total` (bounds included), so we only have to check// one side of the bound in the assertions.//// We also check, before entering the `unsafe` sections, that// we're only reading data that is on a page. - edit in sanakirja-core/src/btree/page.rs at line 229
assert!(c.cur >= 0); - edit in sanakirja-core/src/btree/page.rs at line 232
assert!(c.cur >= 0 && HDR as isize + c.cur * 8 - 8 <= 4088); - edit in sanakirja-core/src/btree/page.rs at line 239
assert!(c.cur < c.total as isize); - edit in sanakirja-core/src/btree/page.rs at line 242
assert!(c.cur < c.total as isize && HDR as isize + c.cur * 8 - 8 <= 4088); - edit in sanakirja-core/src/btree/page.rs at line 248
- replacement in sanakirja-core/src/btree/page.rs at line 250
txn: &T,txn: &'a T, - edit in sanakirja-core/src/btree/page.rs at line 257
// `lookup` has the same semantic as// `core::slice::binary_search`, i.e. it returns either// `Ok(n)`, where `n` is the position where `(k0, v0)` was// found, or `Err(n)` where `n` is the position where// `(k0, v0)` can be inserted to preserve the order. - replacement in sanakirja-core/src/btree/page.rs at line 263
let result;c.cur = match lookup {match lookup { - replacement in sanakirja-core/src/btree/page.rs at line 265
result = if c.is_leaf {c.cur = n as isize;// Just read the tuple, as we did multiple times// before.if c.is_leaf { - replacement in sanakirja-core/src/btree/page.rs at line 270[3.7283]→[3.5929:5965](∅→∅),[3.5929]→[3.5929:5965](∅→∅),[3.5965]→[3.5372:5447](∅→∅),[3.5447]→[3.6026:6183](∅→∅),[3.6026]→[3.6026:6183](∅→∅),[3.6183]→[3.6183:6236](∅→∅)
let off = {let al = core::mem::align_of::<Tuple<K, V>>();let hdr_size = (HDR + al - 1) & !(al - 1);(0, (hdr_size + f * n) as u16)};Ok(Leaf::kv(txn, page, off))let al = core::mem::align_of::<Tuple<K, V>>();let hdr_size = (HDR + al - 1) & !(al - 1);let tup =&*(page.data.as_ptr().add(hdr_size + f * n) as *const Tuple<K, V>);Ok((&tup.k, &tup.v, 0)) - replacement in sanakirja-core/src/btree/page.rs at line 278
Ok(Internal::kv(txn,page,(off & !0xfff, (off & 0xfff) as u16),))};n as isizelet tup =&*(page.data.as_ptr().add(off as usize & 0xfff) as *const Tuple<K, V>);Ok((&tup.k, &tup.v, off & !0xfff))} - replacement in sanakirja-core/src/btree/page.rs at line 284
result = Err(n);n as isizec.cur = n as isize;Err(n) - replacement in sanakirja-core/src/btree/page.rs at line 287
};result} - edit in sanakirja-core/src/btree/page.rs at line 289[3.6826]→[3.6826:6832](∅→∅),[3.6832]→[3.8769:8770](∅→∅),[3.554]→[3.8769:8770](∅→∅),[3.8769]→[3.8769:8770](∅→∅),[3.8770]→[3.6833:7083](∅→∅)
}fn split_at(c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {(PageCursor {cur: 0,total: c.cur.max(0) as usize,is_leaf: c.is_leaf,},*c,) - edit in sanakirja-core/src/btree/page.rs at line 295
// Once again, this is quite straightforward. - edit in sanakirja-core/src/btree/page.rs at line 301
// When deleting from internal nodes, we take a replacement from// one of the leaves (in our current implementation, the leftmost// entry of the right subtree). This method copies an entry from// the leaf onto the program stack, which is necessary since// deletions in leaves overwrites entries.//// Another design choice would have been to do the same as for the// unsized implementation, but in this case this would have meant// copying the saved value to the end of the leaf, potentially// preventing merges, and not even saving a memory copy. - edit in sanakirja-core/src/btree/page.rs at line 312
- replacement in sanakirja-core/src/btree/page.rs at line 323
fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {unsafe { (core::mem::transmute(&s.0), core::mem::transmute(&s.1)) }unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {(core::mem::transmute(&s.0), core::mem::transmute(&s.1)) - edit in sanakirja-core/src/btree/page.rs at line 327
// `put` inserts one or two entries onto a node (internal or// leaf). This is implemented the `put` module. - replacement in sanakirja-core/src/btree/page.rs at line 340
) -> Result<Put<'a, K, V>, T::Error> {) -> Result<super::put::Put<'a, K, V>, T::Error> { - edit in sanakirja-core/src/btree/page.rs at line 371
// This function updates an internal node, setting the left child// of the cursor to `l`. - replacement in sanakirja-core/src/btree/page.rs at line 378
r: u64,) -> Result<Ok, T::Error> {assert!(!c.is_leaf);l: u64,) -> Result<crate::btree::put::Ok, T::Error> {assert!(!c.is_leaf && c.cur >= 0 && (c.cur as usize) < c.total + 1); - edit in sanakirja-core/src/btree/page.rs at line 383
// If the page is mutable (dirty), just convert it to a// mutable page, and update. - replacement in sanakirja-core/src/btree/page.rs at line 386
unsafe { core::mem::transmute(page) }MutPage(page) - edit in sanakirja-core/src/btree/page.rs at line 388
// Else, clone the page. - edit in sanakirja-core/src/btree/page.rs at line 391
// First clone the left child of the page. - edit in sanakirja-core/src/btree/page.rs at line 395
// And then the rest of the page. - replacement in sanakirja-core/src/btree/page.rs at line 397[3.7421]→[3.2431:2458](∅→∅),[3.3183]→[3.2431:2458](∅→∅),[3.2431]→[3.2431:2458](∅→∅),[3.2458]→[3.7422:7496](∅→∅)
let mut n = 0;clone::<K, V, Internal>(page.as_page(), &mut new, s, &mut n);clone::<K, V, Internal>(page.as_page(), &mut new, s, &mut 0);// Mark the former version of the page as free. - replacement in sanakirja-core/src/btree/page.rs at line 402
assert!(c.cur >= 0 && (c.cur as usize) < c.total + 1);// Finally, update the left child of the cursor. - replacement in sanakirja-core/src/btree/page.rs at line 404
let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur as isize - 1);*off = (r | (u64::from_le(*off) & 0xfff)).to_le();let off = (page.0.data.add(HDR) as *mut u64).offset(c.cur - 1);*off = (l | (u64::from_le(*off) & 0xfff)).to_le(); - edit in sanakirja-core/src/btree/page.rs at line 419
// In the mutable case, we just need to move some memory// around. - replacement in sanakirja-core/src/btree/page.rs at line 422
let mut page: MutPage = unsafe { core::mem::transmute(page) };let mut page = MutPage(page); - replacement in sanakirja-core/src/btree/page.rs at line 424[3.2954]→[3.1672:1693](∅→∅),[3.1693]→[3.7497:7558](∅→∅),[3.7558]→[3.1693:1770](∅→∅),[3.1485]→[3.1693:1770](∅→∅),[3.5373]→[3.1693:1770](∅→∅),[3.1693]→[3.1693:1770](∅→∅)
unsafe {let f = core::mem::size_of::<Tuple<K, V>>();if c.is_leaf {let n = hdr.n() as usize;let f = core::mem::size_of::<Tuple<K, V>>();if c.is_leaf {// In leaves, we need to move the n - c - 1 elements// that are strictly after the cursor, by `f` (the// size of an entry).//// Here's the reasoning to avoid off-by-one errors: if// `c` is 0 (i.e. we're deleting the first element on// the page), we remove one entry, so there are n - 1// remaining entries.let n = hdr.n() as usize;let hdr_size = {// As usual, header + padding - replacement in sanakirja-core/src/btree/page.rs at line 438[3.5683]→[3.44726:44789](∅→∅),[3.44726]→[3.44726:44789](∅→∅),[3.44789]→[3.5197:5247](∅→∅),[3.5247]→[3.44830:44886](∅→∅),[3.44830]→[3.44830:44886](∅→∅),[3.44886]→[3.5248:5338](∅→∅),[3.5338]→[3.44967:45000](∅→∅),[3.44967]→[3.44967:45000](∅→∅),[3.45000]→[3.2544:2569](∅→∅),[3.2544]→[3.2544:2569](∅→∅)
let hdr_size = (HDR + al - 1) & !(al - 1);let off = c.cur as usize * f;let kv_ptr = p.add(hdr_size + off);core::ptr::copy(kv_ptr.add(f), kv_ptr, f * (n - c.cur as usize - 1));hdr.decr(f);} else {(HDR + al - 1) & !(al - 1)};let off = hdr_size + c.cur as usize * f;unsafe {core::ptr::copy(p.add(off + f), p.add(off), f * (n - c.cur as usize - 1));}// Removing `f` bytes from the page.hdr.decr(f);} else {// Internal nodes are easier to deal with, as we just// have to move the offsets.unsafe { - edit in sanakirja-core/src/btree/page.rs at line 452
(&mut *hdr).decr(f); - replacement in sanakirja-core/src/btree/page.rs at line 453
};if l > 0 {assert!(!c.is_leaf);// Removing `f` bytes from the page (the tuple), plus// one 8-bytes offset.hdr.decr(f + 8); - replacement in sanakirja-core/src/btree/page.rs at line 458[3.4276]→[3.4276:4301](∅→∅),[3.4301]→[3.192:275](∅→∅),[3.4375]→[3.14388:14459](∅→∅),[3.275]→[3.14388:14459](∅→∅),[3.14388]→[3.14388:14459](∅→∅)
unsafe {let off = (p.add(HDR) as *mut u64).offset(c.cur as isize - 1);*off = (l | (u64::from_le(*off) & 0xfff)).to_le();if l > 0 {unsafe {let off = (p.add(HDR) as *mut u64).offset(c.cur as isize - 1);*off = (l | (u64::from_le(*off) & 0xfff)).to_le();} - edit in sanakirja-core/src/btree/page.rs at line 466
// Returning the mutable page itself, and 0 (for "no page freed") - replacement in sanakirja-core/src/btree/page.rs at line 469[3.14597]→[3.14597:14618](∅→∅),[3.14618]→[3.4450:4499](∅→∅),[3.4499]→[3.2149:2217](∅→∅),[3.4570]→[3.14729:14760](∅→∅),[3.2217]→[3.14729:14760](∅→∅),[3.14729]→[3.14729:14760](∅→∅),[3.14760]→[3.4571:4646](∅→∅),[3.4646]→[3.6778:6821](∅→∅),[3.6821]→[3.5507:5570](∅→∅),[3.4646]→[3.5507:5570](∅→∅),[3.5570]→[3.102:152](∅→∅),[3.152]→[3.6822:6882](∅→∅),[3.5570]→[3.14932:14967](∅→∅),[3.152]→[3.14932:14967](∅→∅),[3.6882]→[3.14932:14967](∅→∅),[3.14932]→[3.14932:14967](∅→∅),[3.14967]→[3.2218:2376](∅→∅),[3.4811]→[3.15111:15136](∅→∅),[3.2376]→[3.15111:15136](∅→∅),[3.15111]→[3.15111:15136](∅→∅),[3.15136]→[3.4812:4891](∅→∅),[3.4891]→[3.6883:6926](∅→∅),[3.6926]→[3.5571:5634](∅→∅),[3.4891]→[3.5571:5634](∅→∅),[3.5634]→[3.153:203](∅→∅),[3.203]→[3.6927:6991](∅→∅),[3.5634]→[3.15312:15347](∅→∅),[3.203]→[3.15312:15347](∅→∅),[3.6991]→[3.15312:15347](∅→∅),[3.15312]→[3.15312:15347](∅→∅),[3.15347]→[3.2377:2460](∅→∅),[3.2460]→[3.6992:7152](∅→∅)
unsafe {let mut new = txn.alloc_page()?;<Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);if c.is_leaf {let s = Leaf::offset_slice::<T, K, V>(page.as_page());debug!("s = {:?}", s);let (s0, s1) = s.split_at(c.cur as usize);let (_, s1) = s1.split_at(1);debug!("leaf s0 {:?} s1 {:?}", s0, s1);let mut n = 0;clone::<K, V, Leaf>(page.as_page(), &mut new, s0, &mut n);clone::<K, V, Leaf>(page.as_page(), &mut new, s1, &mut n);} else {let s = Internal::offset_slice::<T, K, V>(page.as_page());debug!("s = {:?}", s);let (s0, s1) = s.split_at(c.cur as usize);let (_, s1) = s1.split_at(1);debug!("internal s0 {:?} s1 {:?}", s0, s1);let mut n = 0;clone::<K, V, Internal>(page.as_page(), &mut new, s0, &mut n);debug!("offset {:?}", n);if l > 0 {let off = (new.0.data.add(HDR) as *mut u64).offset(n - 1);// Immutable pages need to be cloned. The strategy is the// same in both cases: get an "offset slice", split it at// the cursor, remove the first entry of the second half,// and clone.let mut new = txn.alloc_page()?;<Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);if c.is_leaf {let s = Leaf::offset_slice::<T, K, V>(page.as_page());let (s0, s1) = s.split_at(c.cur as usize);let (_, s1) = s1.split_at(1);let mut n = 0;clone::<K, V, Leaf>(page.as_page(), &mut new, s0, &mut n);clone::<K, V, Leaf>(page.as_page(), &mut new, s1, &mut n);} else {// Internal nodes a bit trickier, since the left child// is not counted in the "offset slice", so we need to// clone it separately. Also, the `l` argument to this// function might be non-zero in this case.let s = Internal::offset_slice::<T, K, V>(page.as_page());let (s0, s1) = s.split_at(c.cur as usize);let (_, s1) = s1.split_at(1);// First, clone the left child of the page.let hdr = header(page.as_page());let left = hdr.left_page() & !0xfff;unsafe { *(new.0.data.add(HDR - 8) as *mut u64) = left.to_le() };// Then, clone the entries strictly before the cursor// (i.e. clone `s0`).let mut n = 0;clone::<K, V, Internal>(page.as_page(), &mut new, s0, &mut n);// If we need to update the left child of the deleted// item, do it.if l > 0 {unsafe {let off = new.0.data.offset(HDR as isize + (n - 1) * 8) as *mut u64; - edit in sanakirja-core/src/btree/page.rs at line 507
debug!("set offset {:?} {:?}", *off, l);} else {let hdr = header(page.as_page());let left = hdr.left_page() & !0xfff;*(new.0.data.add(HDR) as *mut u64).offset(-1) = left.to_le(); - edit in sanakirja-core/src/btree/page.rs at line 508
clone::<K, V, Internal>(page.as_page(), &mut new, s1, &mut n); - replacement in sanakirja-core/src/btree/page.rs at line 509
Ok((new, page.offset))// Finally, clone the right half of the page (`s1`).clone::<K, V, Internal>(page.as_page(), &mut new, s1, &mut n); - edit in sanakirja-core/src/btree/page.rs at line 513
Ok((new, page.offset)) - edit in sanakirja-core/src/btree/page.rs at line 517
// Decide what to do with the concatenation of two neighbouring// pages, with a middle element. - replacement in sanakirja-core/src/btree/page.rs at line 523
let mut hdr_size = HDR;let mid_size = if m.modified.c0.is_leaf {let f = core::mem::size_of::<Tuple<K, V>>();// First evaluate the size of the middle element on a page.let (hdr_size, mid_size) = if m.modified.c0.is_leaf { - replacement in sanakirja-core/src/btree/page.rs at line 526
hdr_size = (HDR + al - 1) & !(al - 1);f((HDR + al - 1) & !(al - 1),core::mem::size_of::<Tuple<K, V>>(),) - replacement in sanakirja-core/src/btree/page.rs at line 531
8 + core::mem::size_of::<Tuple<K, V>>()(HDR, 8 + core::mem::size_of::<Tuple<K, V>>()) - edit in sanakirja-core/src/btree/page.rs at line 533
// Evaluate the size of the modified half of the concatenation// (which includes the header). - edit in sanakirja-core/src/btree/page.rs at line 537
// Add the "occupied" size (which excludes the header). - replacement in sanakirja-core/src/btree/page.rs at line 542[3.16473]→[3.1827:1889](∅→∅),[3.3218]→[3.16536:16588](∅→∅),[3.1889]→[3.16536:16588](∅→∅),[3.5401]→[3.16536:16588](∅→∅),[3.16536]→[3.16536:16588](∅→∅),[3.16588]→[3.5402:5447](∅→∅),[3.5447]→[3.2797:2861](∅→∅),[3.2861]→[3.7703:7934](∅→∅)
let size = hdr_size + mod_size + mid_size + occupied;if size <= PAGE_SIZE {// mergelet mut new = txn.alloc_page()?;<Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);let freed = {let b0 = if m.modified.page.is_dirty() { 1 } else { 0 };let b1 = if m.other.is_dirty() { 1 } else { 0 };[m.modified.page.offset | b0, m.other.offset | b1]// One surprising observation here is that adding the sizes// works. This is surprising because of alignment and// padding. It works because we can split the sizes into an// offset part (always 8 bytes) and a data part (of a constant// alignment), and thus we never need any padding anywhere on// the page.if mod_size + mid_size + occupied <= PAGE_SIZE {// If the concatenation fits on a page, merge.let (page, freed) = if m.modified.c0.is_leaf {merge::<_, _, _, Leaf>(txn, m)?} else {merge::<_, _, _, Internal>(txn, m)? - edit in sanakirja-core/src/btree/page.rs at line 556[3.7949]→[3.7356:7395](∅→∅),[3.2861]→[3.7356:7395](∅→∅),[3.7395]→[3.7395:7452](∅→∅),[3.7452]→[3.7452:7473](∅→∅),[3.7473]→[3.7473:7534](∅→∅),[3.7534]→[3.16904:16918](∅→∅),[3.16904]→[3.16904:16918](∅→∅)
if m.modified.c0.is_leaf {merge::<_, _, _, Leaf>(txn, &mut new, m)} else {merge::<_, _, _, Internal>(txn, &mut new, m)} - replacement in sanakirja-core/src/btree/page.rs at line 557
page: new,page, - replacement in sanakirja-core/src/btree/page.rs at line 562[3.17328]→[3.3900:3947](∅→∅),[3.3947]→[3.7974:8051](∅→∅),[3.8051]→[3.3352:3405](∅→∅),[3.3419]→[3.3352:3405](∅→∅),[3.5920]→[3.3352:3405](∅→∅),[3.3405]→[3.549:640](∅→∅)
let rc = PageCursor::new(&m.other, 0);let first_size = <Page<K, V>>::current_size(m.other.as_page(), &rc);// If we can't rebalance, modify and return.if mod_size >= PAGE_SIZE / 2 || hdr_size + occupied - first_size < PAGE_SIZE / 2 {// If the modified page is large enough, or if the other page// has only just barely the minimum number of elements to be// at least half-full, return.//// The situation where the other page isn't full enough might// happen for example if elements occupy exactly 1/5th of a// page + 1 byte, and the modified page has 2 of them after// the deletion, while the other page has 3.if mod_size >= PAGE_SIZE / 2 || hdr_size + occupied - mid_size < PAGE_SIZE / 2 { - edit in sanakirja-core/src/btree/page.rs at line 572
// Perform the required modification and return. - replacement in sanakirja-core/src/btree/page.rs at line 577
true,m.modified.skip_first, - edit in sanakirja-core/src/btree/page.rs at line 586
// `ins2` is only ever used when the page immediately// below a deletion inside an internal node has split,// and we need to replace the deleted value, *and*// insert the middle entry of the split.debug_assert!(m.modified.ins2.is_none()); - edit in sanakirja-core/src/btree/page.rs at line 601
// Finally, if we're here, we can rebalance. There are four// (relatively explicit) cases, see the `rebalance` submodule// to see how this is done. - edit in sanakirja-core/src/btree/page.rs at line 621
/// Size of a modified page (including the header). - edit in sanakirja-core/src/btree/page.rs at line 633
// Extra size for the offsets.let extra = if m.c1.is_leaf { 0 } else { 8 }; - edit in sanakirja-core/src/btree/page.rs at line 638
let extra = if m.c1.is_leaf { 0 } else { 8 }; - edit in sanakirja-core/src/btree/page.rs at line 643
// If we skip the first entry of `m.c1`, remove its size. - replacement in sanakirja-core/src/btree/page.rs at line 645
total -= <Page<K, V> as BTreePage<K, V>>::current_size(m.page.as_page(), &m.c1) as usize;total -= extra + core::mem::size_of::<Tuple<K, V>>() - edit in sanakirja-core/src/btree/page.rs at line 650
/// Linear search, leaf version. This is relatively straightforward. - replacement in sanakirja-core/src/btree/page.rs at line 678
unsafe fn cmp<T: LoadPage, K: Storable, V: Storable>(/// An equivalent of `Ord::cmp` on `Tuple<K, V>` but using/// `Storable::compare` instead of `Ord::cmp` on `K` and `V`.fn cmp<T: LoadPage, K: Storable, V: Storable>( - replacement in sanakirja-core/src/btree/page.rs at line 688
let tup = &*(p.as_ptr().offset(off as isize & 0xfff) as *const Tuple<K, V>);assert!(off as usize + core::mem::size_of::<Tuple<K, V>>() <= PAGE_SIZE);let tup = unsafe { &*(p.as_ptr().offset(off as isize & 0xfff) as *const Tuple<K, V>) }; - edit in sanakirja-core/src/btree/page.rs at line 702
/// Linear search for internal nodes. Does what it says. - replacement in sanakirja-core/src/btree/page.rs at line 710
let mut a = 0;let mut b = s.len();for _ in 0..4 {let mid = (a + b) / 2;match cmp(txn, k0, v0, p, s[mid]) {Ordering::Less => a = mid,Ordering::Greater => b = mid,Ordering::Equal => b = mid + 1,}}let mut n = a;for &off in &s[a..b] {match cmp(txn, k0, v0, p, off) {Ordering::Less => n += 1,for (n, off) in s.iter().enumerate() {match cmp(txn, k0, v0, p, *off) {Ordering::Less => {} - replacement in sanakirja-core/src/btree/page.rs at line 717
Err(n)Err(s.len()) - edit in sanakirja-core/src/btree/page.rs at line 720
/// Lookup just forms slices of offsets (for internal nodes) or values/// (for leaves), and runs an internal search on them. - replacement in sanakirja-core/src/btree/page.rs at line 749
fn modify<T: LoadPage, K: Storable + core::fmt::Debug, V: Storable + core::fmt::Debug, L: Alloc>(/// Perform the modifications on a page, by copying it onto page `new`.fn modify<T: LoadPage, K: Storable, V: Storable, L: Alloc>( - edit in sanakirja-core/src/btree/page.rs at line 756
// First trick: in order to save code lines, set `l` to the left// page, and let `alloc` set it in `new` in the while loop// (setting `l = 0` in subsequent iterations). - edit in sanakirja-core/src/btree/page.rs at line 764
// If there's an insertion on two in the modified page, do them. - edit in sanakirja-core/src/btree/page.rs at line 773
// If there's no insertion, we have had no opportunity to set// the updated left chlid, so set it here. - replacement in sanakirja-core/src/btree/page.rs at line 777[3.35177]→[3.35177:35214](∅→∅),[3.35214]→[3.8351:8438](∅→∅),[3.8438]→[3.35287:35371](∅→∅),[3.20454]→[3.35287:35371](∅→∅),[3.3873]→[3.35287:35371](∅→∅),[3.5933]→[3.35287:35371](∅→∅),[3.35287]→[3.35287:35371](∅→∅)
let mut is_first = m.skip_first;while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.page.as_page(), &mut m.c1) {if is_first {is_first = false;continue;}// Then, clone `m.c1`, possibly skipping the first element.let mut c1 = m.c1.clone();if m.skip_first {<Page<K, V>>::move_next(&mut c1);}while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.page.as_page(), &mut c1) { - replacement in sanakirja-core/src/btree/page.rs at line 788[3.35449]→[3.6674:6771](∅→∅),[3.6771]→[3.6089:6102](∅→∅),[3.6100]→[3.6089:6102](∅→∅),[3.6089]→[3.6089:6102](∅→∅),[3.8887]→[3.20505:20528](∅→∅),[3.1958]→[3.20505:20528](∅→∅),[3.6102]→[3.20505:20528](∅→∅),[3.35531]→[3.20505:20528](∅→∅)
fn merge<T: LoadPage, K: Storable + core::fmt::Debug, V: Storable + core::fmt::Debug, L: Alloc>(txn: &T,new: &mut MutPage,/// The very unsurprising `merge` functionfn merge<T: AllocPage + LoadPage,K: Storable + core::fmt::Debug,V: Storable + core::fmt::Debug,L: Alloc,>(txn: &mut T, - replacement in sanakirja-core/src/btree/page.rs at line 797
) {) -> Result<(MutPage, [u64; 2]), T::Error> {// This algorithm is probably a bit naive, especially for leaves,// where if the left page is mutable, we can copy the other page// onto it.// Indeed, we first allocate a page, then clone both pages onto// it, in a different order depending on whether the modified page// is the left or the right child.let mut new = txn.alloc_page()?;<Page<K, V> as BTreeMutPage<K, V>>::init(&mut new); - replacement in sanakirja-core/src/btree/page.rs at line 809
modify::<_, _, _, L>(txn, new, &mut m.modified, &mut n);modify::<_, _, _, L>(txn, &mut new, &mut m.modified, &mut n); - replacement in sanakirja-core/src/btree/page.rs at line 812
alloc::<_, _, L>(new, m.mid.0, m.mid.1, 0, l, &mut n);alloc::<_, _, L>(&mut new, m.mid.0, m.mid.1, 0, l, &mut n); - replacement in sanakirja-core/src/btree/page.rs at line 814
alloc::<_, _, L>(new, k, v, 0, r, &mut n);alloc::<_, _, L>(&mut new, k, v, 0, r, &mut n); - replacement in sanakirja-core/src/btree/page.rs at line 820
alloc::<_, _, L>(new, k, v, l, r, &mut n);alloc::<_, _, L>(&mut new, k, v, l, r, &mut n); - replacement in sanakirja-core/src/btree/page.rs at line 823
alloc::<_, _, L>(new, m.mid.0, m.mid.1, 0, 0, &mut n);modify::<_, _, _, L>(txn, new, &mut m.modified, &mut n);alloc::<_, _, L>(&mut new, m.mid.0, m.mid.1, 0, 0, &mut n);modify::<_, _, _, L>(txn, &mut new, &mut m.modified, &mut n); - edit in sanakirja-core/src/btree/page.rs at line 826
let freed = {let b0 = if m.modified.page.is_dirty() { 1 } else { 0 };let b1 = if m.other.is_dirty() { 1 } else { 0 };[m.modified.page.offset | b0, m.other.offset | b1]};Ok((new, freed)) - edit in sanakirja-core/src/btree/page.rs at line 834
/// Clone a slice of offsets onto a page. This essentially does what/// it says. Note that the leftmost child of a page is not included in/// the offset slices, so we don't have to handle it here.////// This should really be in the `Alloc` trait, but Rust doesn't have/// associated type constructors, so we can't have an associated type/// that's sometimes a slice and sometimes a "Range". - replacement in sanakirja-core/src/btree/page.rs at line 844
s: Offsets<L::Offset>,s: Offsets, - edit in sanakirja-core/src/btree/page.rs at line 849
// We know we're in an internal node here. - replacement in sanakirja-core/src/btree/page.rs at line 851
let (r, off): (u64, u16) = (*off).into();let r = (*off) & !0xfff;let off = (*off) & 0xfff; - edit in sanakirja-core/src/btree/page.rs at line 856
// Reserve the space on the page - replacement in sanakirja-core/src/btree/page.rs at line 859
let off_new = L::alloc(hdr, size, core::mem::align_of::<Tuple<K, V>>());core::ptr::copy_nonoverlapping(ptr, new.0.data.offset(off_new as isize), size);L::set_offset(new, *n, r, off_new);let data = hdr.data() as u16;let off_new = data - size as u16;hdr.set_data(off_new);hdr.set_n(hdr.n() + 1);hdr.incr(8 + size);// Copy the entry from the original page to its// position on the new page.core::ptr::copy_nonoverlapping(ptr, new.0.data.add(off_new as usize), size);// Set the offset to this new entry in the offset// array, along with the right child page.let ptr = new.0.data.offset(HDR as isize + *n * 8) as *mut u64;*ptr = (r | off_new as u64).to_le(); - edit in sanakirja-core/src/btree/page.rs at line 890
// On leaves, we do have to update everything manually,// because we're simply copying stuff. - edit in sanakirja-core/src/btree/page.rs at line 899
/// Simply allocate an entry in the page, copy it, and set/// its right and left children. - edit in sanakirja-core/src/btree/page.rs at line 914
debug!("allocated {:?} {:?} {:?}", new_ptr, l, r); - replacement in sanakirja-core/src/btree/page/rebalance.rs at line 16
// page.// page, i.e. return a middle element, and append the current// middle element to the left page. - edit in sanakirja-core/src/btree/page/rebalance.rs at line 24
// First, perform the modification on the modified page, which we// know is the left page, and return the resulting mutable page// (the modified page may or may not be mutable before we do this). - replacement in sanakirja-core/src/btree/page/rebalance.rs at line 33
true,m.modified.skip_first, - edit in sanakirja-core/src/btree/page/rebalance.rs at line 64
// Append the middle element of the concatenation at the end of// the left page. We know the left page to be mutable by now, and// we also know there's enough space to do this. - replacement in sanakirja-core/src/btree/page/rebalance.rs at line 80
let (new_right, k, v) = if r == 0 && right_hdr.is_dirty() {// Rewrite the deleted element at the end of the page, so that// the pointer is still valid.let (new_right, k, v) = if r == 0 && m.other_is_mutable && right_hdr.is_dirty() {// Since `r == 0`, we know this is a leaf. Therefore, we need// to rewrite the deleted element to the end of the page, so// that the pointer to the new middle entry is valid when this// function returns. - replacement in sanakirja-core/src/btree/page/rebalance.rs at line 88
let al = core::mem::align_of::<Tuple<K, V>>();let hdr_size = (HDR + al - 1) & !(al - 1);// Remove the space for one entry. - edit in sanakirja-core/src/btree/page/rebalance.rs at line 92
let al = core::mem::align_of::<Tuple<K, V>>();let hdr_size = (HDR + al - 1) & !(al - 1); - edit in sanakirja-core/src/btree/page/rebalance.rs at line 97
// Save the leftmost element (we can't directly copy it to// the end, because the page may be full). - edit in sanakirja-core/src/btree/page/rebalance.rs at line 104
// Move the n - 1 last elements one entry to the left. - edit in sanakirja-core/src/btree/page/rebalance.rs at line 110
// Copy the last element to the end of the page. - edit in sanakirja-core/src/btree/page/rebalance.rs at line 116
// If this isn't a leaf, or isn't mutable, use the standard// deletion function, because we know this will leave the// pointer to the current entry valid.// We extend the pointer's lifetime here, because we know the// current deletion (we only rebalance during deletions) won't// touch this page anymore after this. - edit in sanakirja-core/src/btree/page/rebalance.rs at line 126
// If this frees the old "other" page, add it to the "freed"// array. - edit in sanakirja-core/src/btree/page/rebalance.rs at line 145
// Surprisingly, the `rebalance_right` function is simpler,// since://// - if we call it to rebalance two internal nodes, we're in the easy// case of rebalance_left.//// - Else, the middle element is the last one on the left page, and// isn't erased be leaf deletions, because these just move entries to// the left. - edit in sanakirja-core/src/btree/page/rebalance.rs at line 175
// Perform the modification on the modified page. - replacement in sanakirja-core/src/btree/page/rebalance.rs at line 182
true,m.modified.skip_first, - edit in sanakirja-core/src/btree/page/rebalance.rs at line 211
// Add the middle element of the concatenation as the first// element of the right page. We know the right page is mutable,// since we just modified it (hence the `assert_eq!(freed, 0)`. - edit in sanakirja-core/src/btree/page/rebalance.rs at line 233
// As explained in the general comment on this function, this// entry isn't erased by the deletion in `m.other` below, so we// can safely extend its lifetime. - replacement in sanakirja-core/src/btree/page/put.rs at line 20[3.6271]→[3.6271:6310](∅→∅),[3.6310]→[3.7687:7816](∅→∅),[3.7816]→[3.6416:6458](∅→∅),[3.6416]→[3.6416:6458](∅→∅)
) -> Result<Put<'a, K, V>, T::Error> {let size = core::mem::size_of::<Tuple<K, V>>()+ if k1v1.is_some() {core::mem::size_of::<Tuple<K, V>>()} else {0};) -> Result<crate::btree::put::Put<'a, K, V>, T::Error> {let size = if k1v1.is_some() { 2 } else { 1 }; - edit in sanakirja-core/src/btree/page/put.rs at line 34
let size = core::mem::size_of::<Tuple<K, V>>(); - replacement in sanakirja-core/src/btree/page/put.rs at line 35
hdr.decr(size);hdr.decr(8 + core::mem::size_of::<Tuple<K, V>>()); - replacement in sanakirja-core/src/btree/page/put.rs at line 97
) -> Result<Put<'a, K, V>, T::Error> {) -> Result<crate::btree::put::Put<'a, K, V>, T::Error> { - replacement in sanakirja-core/src/btree/page/put.rs at line 113
let (k, v, r) = L::kv(txn, page.as_page(), s1a.first::<T, K, V>());let (k, v, r) = L::kv(page.as_page(), L::first::<K, V>(&s1a)); - edit in sanakirja-core/src/btree/page/alloc.rs at line 3
/// This trait contains methods common to leaves and internal/// nodes. These methods are meant to be just a few lines long each,/// and avoid duplicating code in higher-level functions where just a/// few constants change between internal nodes and leaves. - replacement in sanakirja-core/src/btree/page/alloc.rs at line 8[3.17273]→[3.8265:8425](∅→∅),[3.8425]→[3.17546:17612](∅→∅),[3.6456]→[3.17546:17612](∅→∅),[3.10568]→[3.17546:17612](∅→∅),[3.17546]→[3.17546:17612](∅→∅)
fn can_alloc<K: Storable, V: Storable>(hdr: &Header, size: usize) -> bool;fn can_compact<K: Storable, V: Storable>(hdr: &Header, size: usize) -> bool;fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16;/// Is there enough room to add one entry into this page (without cloning)?fn can_alloc<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool; - replacement in sanakirja-core/src/btree/page/alloc.rs at line 11
// n = number of items to remove/// If we clone the page, will there be enough room for one entry?fn can_compact<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool;/// Remove the leftmost `n` elements from the page. On leaves,/// this moves the last truncated element to the end of the page/// and returns a pointer to that element (this function is only/// used in `crate::btree::put`, and the pointer becomes invalid/// at the end of the `crate::btree::put`).////// Returning the last deleted element isn't required for internal/// nodes, since the entries are still valid there. - edit in sanakirja-core/src/btree/page/alloc.rs at line 27
/// Allocate a new entry (size inferred), and return the offset on/// the page where the new entry can be copied. - replacement in sanakirja-core/src/btree/page/alloc.rs at line 30
fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16);/// Set the right child of the `n`th entry to `r`. If `n == -1`,/// this method can be used to set the leftmost child of a page. - replacement in sanakirja-core/src/btree/page/alloc.rs at line 34
type Offset: Into<(u64, u16)> + Copy + core::fmt::Debug;/// "Slices" of offsets, which aren't really slices in the case of/// leaves, but just intervals or "ranges". - replacement in sanakirja-core/src/btree/page/alloc.rs at line 39[3.18261]→[3.18261:18297](∅→∅),[3.18297]→[3.8639:8693](∅→∅),[3.8693]→[3.10825:10842](∅→∅),[3.5234]→[3.10825:10842](∅→∅),[3.10825]→[3.10825:10842](∅→∅),[3.10842]→[3.18357:18439](∅→∅),[3.18357]→[3.18357:18439](∅→∅)
) -> Offsets<'a, Self::Offset>;fn kv<'a, T: LoadPage, K: Storable, V: Storable>(txn: &T,page: crate::Page,off: (u64, u16),) -> (&'a K, &'a V, u64);) -> Offsets<'a>;/// First element of a slice offset. For the sake of code/// simplicity, we return a `u64` even for leaves. In internal/// nodes, the 52 MSBs encode a child page, and the 12 LSBs encode/// an offset in the page.fn first<'a, K, V>(off: &Offsets<'a>) -> u64;/// The tuple and right child at offset `off`.fn kv<'a, K: Storable, V: Storable>(page: crate::Page, off: u64) -> (&'a K, &'a V, u64); - edit in sanakirja-core/src/btree/page/alloc.rs at line 51
/// The type of offsets. - replacement in sanakirja-core/src/btree/page/alloc.rs at line 53
pub enum Offsets<'a, A> {Slice(&'a [A]),pub enum Offsets<'a> {/// Slices of child pages and offset-in-page for internal nodes,Slice(&'a [u64]),/// Ranges for leaves. - replacement in sanakirja-core/src/btree/page/alloc.rs at line 60
impl<'a, A: Into<(u64, u16)> + Copy> Offsets<'a, A> {impl<'a> Offsets<'a> {/// Splitting an offset slice, with the same semantics as/// `split_at` for slices, except if `mid` is equal to the length,/// in which case we return `(self, &[])`. - edit in sanakirja-core/src/btree/page/alloc.rs at line 67
debug!("split_at: {:?} {:?}", s.len(), mid); - replacement in sanakirja-core/src/btree/page/alloc.rs at line 80[3.19245]→[3.8694:8763](∅→∅),[3.8763]→[3.19330:19397](∅→∅),[3.10922]→[3.19330:19397](∅→∅),[3.19330]→[3.19330:19397](∅→∅)
pub fn first<T, K: Storable, V: Storable>(&self) -> (u64, u16) {match self {Offsets::Slice(s) => s[0].into(),}pub struct Leaf {}pub struct Internal {}impl Alloc for Leaf {// Checking if there's enough room is just bookkeeping.fn can_alloc<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool {let f = core::mem::size_of::<Tuple<K, V>>();let al = core::mem::align_of::<Tuple<K, V>>();let header_size = (HDR + al - 1) & !(al - 1);header_size + (hdr.n() as usize + n) * f <= PAGE_SIZE}/// There's no possible compaction on leaves, it's the same as allocating.fn can_compact<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool {Self::can_alloc::<K, V>(hdr, n)}fn set_right_child(_: &mut MutPage, _: isize, _: u64) {}fn offset_slice<'a, T: LoadPage, K: Storable, V: Storable>(page: crate::Page<'a>,) -> Offsets<'a> {let hdr = header(page);Offsets::Range(0..(hdr.n() as usize))}/// This returns an offset on the page, so we need to compute that.fn first<'a, K, V>(off: &Offsets<'a>) -> u64 {match off {Offsets::Slice(_) => unreachable!(), - replacement in sanakirja-core/src/btree/page/alloc.rs at line 116
(0, (hdr_size + r.start * size) as u16)(hdr_size + r.start * size) as u64 - edit in sanakirja-core/src/btree/page/alloc.rs at line 120
} - replacement in sanakirja-core/src/btree/page/alloc.rs at line 121
pub struct Leaf {}pub struct Internal {}fn kv<'a, K: Storable, V: Storable>(page: crate::Page, off: u64) -> (&'a K, &'a V, u64) {unsafe {let tup = &*(page.data.as_ptr().add(off as usize) as *const Tuple<K, V>);(&tup.k, &tup.v, 0)}} - replacement in sanakirja-core/src/btree/page/alloc.rs at line 128
impl Alloc for Leaf {fn can_alloc<K: Storable, V: Storable>(hdr: &Header, size: usize) -> bool {/// Here, we just move `total - *n` elements to the right, and/// increase the bookkeeping values (occupied bytes and number of/// elements).fn alloc_insert<K: Storable, V: Storable>(new: &mut MutPage, n: &mut isize, _: u64) -> usize { - edit in sanakirja-core/src/btree/page/alloc.rs at line 133[3.12508]→[3.8909:8964](∅→∅),[3.8964]→[3.6548:6582](∅→∅),[3.47760]→[3.6548:6582](∅→∅),[3.6582]→[3.47760:47814](∅→∅),[3.47760]→[3.47760:47814](∅→∅),[3.47814]→[3.6583:6648](∅→∅),[3.47888]→[3.20371:20377](∅→∅),[3.6648]→[3.20371:20377](∅→∅),[3.20371]→[3.20371:20377](∅→∅),[3.20377]→[3.8965:9047](∅→∅)
let al = core::mem::align_of::<Tuple<K, V>>();assert_eq!(size % al, 0);let header_size = (HDR + al - 1) & !(al - 1);header_size + (hdr.n() as usize) * f + size <= PAGE_SIZE}fn can_compact<K: Storable, V: Storable>(hdr: &Header, size: usize) -> bool { - replacement in sanakirja-core/src/btree/page/alloc.rs at line 134[3.9102]→[3.6742:6776](∅→∅),[3.47930]→[3.6742:6776](∅→∅),[3.6776]→[3.47930:47984](∅→∅),[3.47930]→[3.47930:47984](∅→∅),[3.47984]→[3.6777:7011](∅→∅)
assert_eq!(size % al, 0);let header_size = (HDR + al - 1) & !(al - 1);debug!("can_compact, leaf: {:?} {:?} {:?}",header_size,hdr.left_page() & 0xfff,size);header_size + ((hdr.left_page() & 0xfff) as usize) + size <= PAGE_SIZElet hdr_size = (HDR + al - 1) & !(al - 1);let hdr_n = header_mut(new).n();unsafe {core::ptr::copy(new.0.data.add(hdr_size + (*n as usize) * f),new.0.data.add(hdr_size + (*n as usize) * f + f),(hdr_n as usize - (*n as usize)) * f,);}let hdr = header_mut(new);hdr.set_n(hdr.n() + 1);hdr.incr(f);hdr_size + (*n as usize) * f - edit in sanakirja-core/src/btree/page/alloc.rs at line 148
- edit in sanakirja-core/src/btree/page/alloc.rs at line 153
debug!("truncate_left {:?} {:?}", page, n); - replacement in sanakirja-core/src/btree/page/alloc.rs at line 156
// debug!("{:?} {:?} {:?}", new, hdr.n(), *n);let hdr_n = header_mut(page).n();let hdr = header_mut(page);let hdr_n = hdr.n();hdr.set_n(hdr_n - n as u16);hdr.decr(n * f); - edit in sanakirja-core/src/btree/page/alloc.rs at line 161
// Now, this is a bit trickier. This performs a rotation by 1// without all the rotation machinery from the Rust core// library.//// Indeed, since we're in a leaf, we are effectively erasing// the split entry. There is a choice to be made here, between// passing the entry by value or by reference. Because splits// might cascade with the same middle entry, passing it by// value may be significantly worse if the tree is deep, and// is never significantly better (we'll end up copying this// entry twice anyway). - edit in sanakirja-core/src/btree/page/alloc.rs at line 173
// This performs a rotation by 1 without all the rotation// machinery from the core lib. - edit in sanakirja-core/src/btree/page/alloc.rs at line 189
}debug!("{:?} - {:?}", hdr_n, n);let hdr = header_mut(page);hdr.set_n(hdr_n - n as u16);hdr.decr(n * f);unsafe { - replacement in sanakirja-core/src/btree/page/alloc.rs at line 194[3.23204]→[3.23204:23271](∅→∅),[3.23271]→[3.7213:7250](∅→∅),[3.7250]→[3.23387:23443](∅→∅),[3.23387]→[3.23387:23443](∅→∅),[3.23443]→[3.7251:7261](∅→∅)
fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {assert_eq!(size % align, 0);hdr.set_n(hdr.n() + 1);hdr.incr(size);0}impl Alloc for Internal {fn can_alloc<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool {(HDR as usize) + (hdr.n() as usize) * 8 + n * (8 + core::mem::size_of::<Tuple<K, V>>())< hdr.data() as usize}fn can_compact<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool {(HDR as usize)+ ((hdr.left_page() & 0xfff) as usize)+ n * (8 + core::mem::size_of::<Tuple<K, V>>())<= PAGE_SIZE - replacement in sanakirja-core/src/btree/page/alloc.rs at line 208[3.23462]→[3.9362:9461](∅→∅),[3.9461]→[3.12678:12731](∅→∅),[3.23632]→[3.12678:12731](∅→∅),[3.12731]→[3.9462:9517](∅→∅),[3.9517]→[3.49481:49532](∅→∅),[3.49481]→[3.49481:49532](∅→∅),[3.49587]→[3.49587:49628](∅→∅)
fn alloc_insert<K: Storable, V: Storable>(new: &mut MutPage, n: &mut isize, _: u64) -> usize {let f = core::mem::size_of::<Tuple<K, V>>();let al = core::mem::align_of::<Tuple<K, V>>();let hdr_size = (HDR + al - 1) & !(al - 1);let hdr_n = header_mut(new).n();/// Set the right-hand child in the offset array, preserving the/// current offset.fn set_right_child(page: &mut MutPage, n: isize, r: u64) { - replacement in sanakirja-core/src/btree/page/alloc.rs at line 213
core::ptr::copy(new.0.data.add(hdr_size + (*n as usize) * f),new.0.data.add(hdr_size + (*n as usize) * f + f),(hdr_n as usize - (*n as usize)) * f,);debug_assert_eq!(r & 0xfff, 0);let ptr = page.0.data.offset(HDR as isize + n * 8) as *mut u64;let off = u64::from_le(*ptr) & 0xfff;*ptr = (r | off as u64).to_le(); - edit in sanakirja-core/src/btree/page/alloc.rs at line 218
let hdr = header_mut(new);hdr.set_n(hdr.n() + 1);hdr.incr(f);hdr_size + (*n as usize) * f - replacement in sanakirja-core/src/btree/page/alloc.rs at line 219
fn set_offset(new: &mut MutPage, n: isize, _: u64, off: u16) {fn offset_slice<'a, T, K: Storable, V: Storable>(page: crate::Page<'a>) -> Offsets<'a> {let hdr = header(page); - replacement in sanakirja-core/src/btree/page/alloc.rs at line 223
let ptr = new.0.data.offset(HDR as isize + n * 2) as *mut u16;*ptr = off.to_le();Offsets::Slice(core::slice::from_raw_parts(page.data.as_ptr().add(HDR) as *const u64,hdr.n() as usize,)) - edit in sanakirja-core/src/btree/page/alloc.rs at line 229
fn set_right_child(_: &mut MutPage, _: isize, _: u64) {}type Offset = LeafOffset; - replacement in sanakirja-core/src/btree/page/alloc.rs at line 230[3.25230]→[3.9518:9582](∅→∅),[3.9582]→[3.25300:25400](∅→∅),[3.5381]→[3.25300:25400](∅→∅),[3.11936]→[3.25300:25400](∅→∅),[3.25300]→[3.25300:25400](∅→∅),[3.25400]→[3.49998:50044](∅→∅)
fn offset_slice<'a, T: LoadPage, K: Storable, V: Storable>(page: crate::Page<'a>,) -> Offsets<'a, Self::Offset> {let hdr = header(page);Offsets::Range(0..(hdr.n() as usize))fn first<'a, K, V>(off: &Offsets<'a>) -> u64 {match off {Offsets::Slice(s) => s[0],Offsets::Range(_) => unreachable!(),} - replacement in sanakirja-core/src/btree/page/alloc.rs at line 236[3.25752]→[3.9583:9655](∅→∅),[3.9655]→[3.25812:25900](∅→∅),[3.12053]→[3.25812:25900](∅→∅),[3.25812]→[3.25812:25900](∅→∅)
fn kv<'a, T: LoadPage, K: Storable, V: Storable>(_txn: &T,page: crate::Page,(_, off): (u64, u16),) -> (&'a K, &'a V, u64) {fn kv<'a, K: Storable, V: Storable>(page: crate::Page, off: u64) -> (&'a K, &'a V, u64) { - replacement in sanakirja-core/src/btree/page/alloc.rs at line 239
let tup = &*(page.data.as_ptr().add(off as usize) as *const Tuple<K, V>);debug!(">>>>>>>> kv {:?} {:?}", off, tup);(&tup.k, &tup.v, 0)let tup = &*(page.data.as_ptr().add((off & 0xfff) as usize) as *const Tuple<K, V>);(&tup.k, &tup.v, off & !0xfff) - edit in sanakirja-core/src/btree/page/alloc.rs at line 243
} - replacement in sanakirja-core/src/btree/page/alloc.rs at line 244[3.26042]→[3.26042:26068](∅→∅),[3.26068]→[3.9830:9910](∅→∅),[3.9910]→[3.10176:10222](∅→∅),[3.7404]→[3.10176:10222](∅→∅),[3.10222]→[3.26259:26346](∅→∅),[3.7404]→[3.26259:26346](∅→∅),[3.12370]→[3.26259:26346](∅→∅),[3.26259]→[3.26259:26346](∅→∅),[3.26346]→[3.9911:9993](∅→∅),[3.9993]→[3.7497:7746](∅→∅),[3.7497]→[3.7497:7746](∅→∅),[3.7746]→[3.5447:5472](∅→∅),[3.7766]→[3.26527:26533](∅→∅),[3.5472]→[3.26527:26533](∅→∅),[3.26527]→[3.26527:26533](∅→∅)
impl Alloc for Internal {fn can_alloc<K: Storable, V: Storable>(hdr: &Header, size: usize) -> bool {debug!("can_alloc {:?}", hdr.data());(HDR as usize) + (hdr.n() as usize) * 8 + 8 + size < hdr.data() as usize}fn can_compact<K: Storable, V: Storable>(hdr: &Header, size: usize) -> bool {debug!("can_compact, internal: {:?} {:?} {:?}",HDR,hdr.left_page() & 0xfff,size);(HDR as usize) + (hdr.n() as usize) * 8 + ((hdr.left_page() & 0xfff) as usize) + 8 + size<= PAGE_SIZE}// Much simpler than in leaves, because we just need to move the// offsets. There's a little bit of bookkeeping involved though. - edit in sanakirja-core/src/btree/page/alloc.rs at line 250
// The following line copies the left child of the last entry// (hence the `- 8` and `- 1`) - edit in sanakirja-core/src/btree/page/alloc.rs at line 252
// We want to copy the left child of the first entry that// will be kept alive as the left child of the page. - edit in sanakirja-core/src/btree/page/alloc.rs at line 257
// We're removing n entries, so we need to copy the// remaining `hdr_n - n`, plus the leftmost child// (hence the + 1). - replacement in sanakirja-core/src/btree/page/alloc.rs at line 263[3.27048]→[3.12732:12785](∅→∅),[3.12785]→[3.7767:7831](∅→∅),[3.2033]→[3.7767:7831](∅→∅),[3.50098]→[3.7767:7831](∅→∅)
let f = core::mem::size_of::<Tuple<K, V>>();let size = { ((8 + f) * (hdr_n as usize - n)) as u64 };// Remaining occupied size on the page (minus the header).let size = (8 + core::mem::size_of::<Tuple<K, V>>()) * (hdr_n as usize - n); - replacement in sanakirja-core/src/btree/page/alloc.rs at line 267
debug!("truncate_left {:?} {:?}", hdr.left_page(), size);hdr.set_occupied(size);// Because the leftmost child has been copied from an entry// containing an offset, its 12 LBSs are still enconding an// offset on the page, whereas it should encode the occupied// bytes on the page. Reset it.hdr.set_occupied(size as u64); - replacement in sanakirja-core/src/btree/page/alloc.rs at line 274[3.27817]→[3.27817:27884](∅→∅),[3.27884]→[3.7832:7942](∅→∅),[3.7942]→[3.28000:28056](∅→∅),[3.28000]→[3.28000:28056](∅→∅),[3.28056]→[3.7943:7970](∅→∅),[3.7970]→[3.28069:28075](∅→∅),[3.28069]→[3.28069:28075](∅→∅)
fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {assert_eq!(size % align, 0);let data = hdr.data();hdr.set_data(data - size as u16);hdr.set_n(hdr.n() + 1);hdr.incr(size);data - size as u16} - replacement in sanakirja-core/src/btree/page/alloc.rs at line 276[3.10142]→[3.10142:10251](∅→∅),[3.10251]→[3.28245:28356](∅→∅),[3.28245]→[3.28245:28356](∅→∅),[3.28356]→[3.10252:10336](∅→∅),[3.10336]→[3.28426:28451](∅→∅),[3.28426]→[3.28426:28451](∅→∅),[3.28451]→[3.10337:10380](∅→∅)
let size = core::mem::size_of::<Tuple<K, V>>();debug!("alloc internal {:?} {:?}", n, size);let (hdr_n, off_new) = {let hdr = header_mut(new);(hdr.n(),Self::alloc(&mut *hdr, size, core::mem::align_of::<Tuple<K, V>>()),)};debug!("off_new = {:?}", off_new);let hdr = header_mut(new);// Move the `data` field one entry to the left.let data = hdr.data() as u16;let off_new = data - core::mem::size_of::<Tuple<K, V>>() as u16;hdr.set_data(off_new);// Increment the number of entries, add the newly occupied size.hdr.set_n(hdr.n() + 1);hdr.incr(8 + core::mem::size_of::<Tuple<K, V>>());let hdr_n = hdr.n(); - edit in sanakirja-core/src/btree/page/alloc.rs at line 289
// Make space in the offset array by moving the last// `hdr_n - *n` elements. - edit in sanakirja-core/src/btree/page/alloc.rs at line 296
// Add the offset.let ptr = new.0.data.offset(HDR as isize + *n * 8) as *mut u64;*ptr = (r | off_new as u64).to_le(); - edit in sanakirja-core/src/btree/page/alloc.rs at line 300
Self::set_offset(new, *n, r, off_new); - edit in sanakirja-core/src/btree/page/alloc.rs at line 301
}fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16) {unsafe {let ptr = new.0.data.offset(HDR as isize + n * 8) as *mut u64;*ptr = (r | off as u64).to_le();}}fn set_right_child(page: &mut MutPage, n: isize, r: u64) {unsafe {let ptr = page.0.data.offset(HDR as isize + n * 8) as *mut u64;let off = u64::from_le(*ptr) & 0xfff;*ptr = (r | off as u64).to_le();} - edit in sanakirja-core/src/btree/page/alloc.rs at line 302[3.29259]→[3.29259:29294](∅→∅),[3.29294]→[3.10381:10435](∅→∅),[3.10435]→[3.29364:29672](∅→∅),[3.12822]→[3.29364:29672](∅→∅),[3.29364]→[3.29364:29672](∅→∅),[3.29672]→[3.10436:10508](∅→∅),[3.10508]→[3.29732:29837](∅→∅),[3.12894]→[3.29732:29837](∅→∅),[3.29732]→[3.29732:29837](∅→∅),[3.29837]→[3.10509:10627](∅→∅),[3.10627]→[3.29943:29959](∅→∅),[3.13046]→[3.29943:29959](∅→∅),[3.29943]→[3.29943:29959](∅→∅)
type Offset = InternalOffset;fn offset_slice<'a, T, K: Storable, V: Storable>(page: crate::Page<'a>,) -> Offsets<'a, Self::Offset> {let hdr = header(page);unsafe {Offsets::Slice(core::slice::from_raw_parts(page.data.as_ptr().add(HDR) as *const InternalOffset,hdr.n() as usize,))}}fn kv<'a, T: LoadPage, K: Storable, V: Storable>(_txn: &T,page: crate::Page,(r, off): (u64, u16),) -> (&'a K, &'a V, u64) {unsafe {let tup = &*(page.data.as_ptr().add(off as usize) as *const Tuple<K, V>);(&tup.k, &tup.v, r)}} - edit in sanakirja-core/src/btree/page/alloc.rs at line 303
#[derive(Debug, Clone, Copy)]#[repr(C)]pub struct LeafOffset(u16);impl Into<(u64, u16)> for LeafOffset {fn into(self) -> (u64, u16) {(0, self.0)}}impl Into<usize> for LeafOffset {fn into(self) -> usize {self.0 as usize}}#[derive(Debug, Clone, Copy)]#[repr(C)]pub struct InternalOffset(u64);impl Into<(u64, u16)> for InternalOffset {fn into(self) -> (u64, u16) {(self.0 & !0xfff, (self.0 & 0xfff) as u16)}}impl Into<usize> for InternalOffset {fn into(self) -> usize {self.0 as usize}} - replacement in sanakirja-core/src/btree/mod.rs at line 1
//! An implementation of B trees.//! 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. - edit in sanakirja-core/src/btree/mod.rs at line 16
#[doc(hidden)] - replacement in sanakirja-core/src/btree/mod.rs at line 19
mod del;pub use del::*;mod put;pub use put::*;pub mod del;pub use del::del;pub mod put;pub use put::put; - edit in sanakirja-core/src/btree/mod.rs at line 26[3.8427]→[3.45830:45919](∅→∅),[3.50142]→[3.45830:45919](∅→∅),[3.45830]→[3.45830:45919](∅→∅),[3.45919]→[3.50143:50184](∅→∅),[3.50184]→[3.45944:46098](∅→∅),[3.45944]→[3.45944:46098](∅→∅)
#[derive(Debug)]pub struct Ok {page: MutPage,freed: u64,}#[derive(Debug)]pub enum Put<'a, K: ?Sized, V: ?Sized> {Ok(Ok),Split {split_key: &'a K,split_value: &'a V,left: MutPage,right: MutPage,freed: u64,},} - replacement in sanakirja-core/src/btree/mod.rs at line 122
txn: &T,txn: &'a T, - replacement in sanakirja-core/src/btree/mod.rs at line 163
) -> Result<Put<'a, K, V>, T::Error>;) -> Result<crate::btree::put::Put<'a, K, V>, T::Error>; - replacement in sanakirja-core/src/btree/mod.rs at line 173
) -> Result<Ok, T::Error>;) -> Result<crate::btree::put::Ok, T::Error>; - replacement in sanakirja-core/src/btree/mod.rs at line 183
fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V);unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V); - replacement in sanakirja-core/src/btree/mod.rs at line 199[3.49260]→[3.12786:12821](∅→∅),[3.12821]→[3.49299:49343](∅→∅),[3.30037]→[3.49299:49343](∅→∅),[3.14472]→[3.49299:49343](∅→∅),[3.49299]→[3.49299:49343](∅→∅),[3.14606]→[3.50201:50204](∅→∅),[3.50201]→[3.50201:50204](∅→∅),[3.50204]→[3.0:107](∅→∅),[3.107]→[3.3868:3885](∅→∅),[3.50204]→[3.3868:3885](∅→∅),[3.3885]→[3.10971:11014](∅→∅),[3.50567]→[3.50267:50280](∅→∅),[3.11014]→[3.50267:50280](∅→∅),[3.9428]→[3.50267:50280](∅→∅),[3.14664]→[3.50267:50280](∅→∅),[3.50267]→[3.50267:50280](∅→∅),[3.50280]→[3.108:136](∅→∅),[3.136]→[3.50280:50303](∅→∅),[3.50280]→[3.50280:50303](∅→∅),[3.50303]→[3.137:196](∅→∅),[3.196]→[3.50303:50398](∅→∅),[3.50303]→[3.50303:50398](∅→∅),[3.50398]→[3.197:224](∅→∅),[3.224]→[3.30618:30636](∅→∅),[3.50398]→[3.30618:30636](∅→∅),[3.30636]→[3.225:254](∅→∅),[3.254]→[3.30636:30654](∅→∅),[3.30636]→[3.30636:30654](∅→∅),[3.30654]→[3.255:324](∅→∅),[3.324]→[3.168:194](∅→∅),[3.30654]→[3.168:194](∅→∅),[3.194]→[3.325:351](∅→∅),[3.194]→[3.50436:50452](∅→∅),[3.351]→[3.50436:50452](∅→∅),[3.30654]→[3.50436:50452](∅→∅),[3.50436]→[3.50436:50452](∅→∅),[3.50452]→[3.352:379](∅→∅),[3.379]→[3.50452:50468](∅→∅),[3.50452]→[3.50452:50468](∅→∅),[3.50468]→[3.380:443](∅→∅),[3.443]→[3.50468:50527](∅→∅),[3.50468]→[3.50468:50527](∅→∅),[3.50527]→[3.444:499](∅→∅),[3.499]→[3.6361:6378](∅→∅),[3.6378]→[3.11015:11087](∅→∅),[3.11087]→[3.30668:30691](∅→∅),[3.50680]→[3.30668:30691](∅→∅),[3.30691]→[3.195:249](∅→∅),[3.249]→[3.50760:50858](∅→∅),[3.30597]→[3.50760:50858](∅→∅),[3.50760]→[3.50760:50858](∅→∅),[3.50858]→[3.14163:14233](∅→∅),[3.14233]→[3.50920:50936](∅→∅),[3.50920]→[3.50920:50936](∅→∅),[3.50936]→[3.14234:14303](∅→∅),[3.14303]→[3.5975:5991](∅→∅),[3.5975]→[3.5975:5991](∅→∅),[3.5991]→[3.50936:50974](∅→∅),[3.50936]→[3.50936:50974](∅→∅),[3.50974]→[3.5992:6029](∅→∅),[3.6029]→[3.500:601](∅→∅),[3.601]→[3.14304:14342](∅→∅),[3.6029]→[3.14304:14342](∅→∅),[3.14342]→[3.51022:51192](∅→∅),[3.30734]→[3.51022:51192](∅→∅),[3.6029]→[3.51022:51192](∅→∅),[3.51022]→[3.51022:51192](∅→∅)
m: Concat<'a, K, V, Self>,) -> Result<Op<'a, T, K, V>, T::Error>;}/// Represents the result of a merge or rebalance, without touching/// the parent of the merge/rebalance.#[derive(Debug)]pub enum Op<'a, T, K: ?Sized, V: ?Sized> {Merged {// New merged page.page: MutPage,// Pages freed by the merge (0 meaning "no page").freed: [u64; 2],marker: core::marker::PhantomData<T>,},Rebalanced {// New middle key.k: &'a K,// New middle value.v: &'a V,// Do `k` and `v` come from a page shared with another tree?incr_kv_rc: bool,// New left page.l: u64,// New right page.r: u64,// Pages freed by the rebalance (0 meaning "no page").freed: [u64; 2],},Put(Put<'a, K, V>),}/// Represents a page with modifications from a merge.#[derive(Debug)]pub struct ModifiedPage<'a, K: ?Sized, V: ?Sized, P: BTreePage<K, V>> {pub page: CowPage,// Whether the page is mutable with another tree.pub mutable: bool,// Start copying c0 (keep `page`'s left child).pub c0: P::Cursor,// If > 0, replace the right child of c0's last element with `l`.pub l: u64,// If > 0, replace the left child of c1's last element with `r`.pub r: u64,// Possibly insert a new binding.pub ins: Option<(&'a K, &'a V)>,// If a rebalance causes a split, we might need to insert an entry// after the replacement.pub ins2: Option<(&'a K, &'a V)>,// The first element of c1 is to be deleted, the others must be copied.pub c1: P::Cursor,// Whether to skip `c1`'s first element.pub skip_first: bool,m: del::Concat<'a, K, V, Self>,) -> Result<del::Op<'a, T, K, V>, T::Error>; - edit in sanakirja-core/src/btree/mod.rs at line 203[3.51195]→[3.602:698](∅→∅),[3.698]→[3.51660:51677](∅→∅),[3.51660]→[3.51660:51677](∅→∅),[3.51677]→[3.11088:11154](∅→∅),[3.11154]→[3.699:791](∅→∅),[3.9834]→[3.699:791](∅→∅),[3.791]→[3.31033:31062](∅→∅),[3.9834]→[3.31033:31062](∅→∅),[3.51779]→[3.31033:31062](∅→∅),[3.31062]→[3.792:830](∅→∅),[3.830]→[3.31110:31134](∅→∅),[3.14954]→[3.31110:31134](∅→∅),[3.31110]→[3.31110:31134](∅→∅),[3.31134]→[3.831:919](∅→∅),[3.919]→[3.51969:51996](∅→∅),[3.51969]→[3.51969:51996](∅→∅),[3.51996]→[3.920:1118](∅→∅),[3.1118]→[3.5818:5850](∅→∅),[3.51996]→[3.5818:5850](∅→∅),[3.5850]→[3.51996:51999](∅→∅),[3.51996]→[3.51996:51999](∅→∅)
/// Represents the concatenation of a modified page and one of its/// sibling (left or right).#[derive(Debug)]pub struct Concat<'a, K: ?Sized, V: ?Sized, P: BTreePage<K, V>> {/// Modified page.pub modified: ModifiedPage<'a, K, V, P>,/// Middle element.pub mid: (&'a K, &'a V),/// Sibling of the modified page.pub other: CowPage,/// Is the modified field on the left or on the right of the/// concatenation?pub mod_is_left: bool,/// Is the other page owned by this tree? If not, it means `other`/// is shared with another tree, and hence we need to increase the/// reference count of entries coming from `other`.pub other_is_mutable: bool,} - edit in sanakirja-core/src/btree/del.rs at line 1
//! Deletions from a B tree. - edit in sanakirja-core/src/btree/del.rs at line 3
use super::put::{Ok, Put}; - edit in sanakirja-core/src/btree/del.rs at line 6
/// Represents the result of a merge or rebalance, without touching/// the parent of the merge/rebalance.#[derive(Debug)]pub enum Op<'a, T, K: ?Sized, V: ?Sized> {Merged {// New merged page.page: MutPage,// Pages freed by the merge (0 meaning "no page").freed: [u64; 2],marker: core::marker::PhantomData<T>,},Rebalanced {// New middle key.k: &'a K,// New middle value.v: &'a V,// Do `k` and `v` come from a page shared with another tree?incr_kv_rc: bool,// New left page.l: u64,// New right page.r: u64,// Pages freed by the rebalance (0 meaning "no page").freed: [u64; 2],},Put(crate::btree::put::Put<'a, K, V>),}/// Represents a page with modifications from a merge.#[derive(Debug)]pub struct ModifiedPage<'a, K: ?Sized, V: ?Sized, P: BTreePage<K, V>> {pub page: CowPage,// Whether the page is mutable with another tree.pub mutable: bool,// Start copying c0 (keep `page`'s left child).pub c0: P::Cursor,// If > 0, replace the right child of c0's last element with `l`.pub l: u64,// If > 0, replace the left child of c1's last element with `r`.pub r: u64,// Possibly insert a new binding.pub ins: Option<(&'a K, &'a V)>,// If a rebalance causes a split, we might need to insert an entry// after the replacement.pub ins2: Option<(&'a K, &'a V)>,// The first element of c1 is to be deleted, the others must be copied.pub c1: P::Cursor,// Whether to skip `c1`'s first element.pub skip_first: bool,}/// Represents the concatenation of a modified page and one of its/// sibling (left or right).#[derive(Debug)]pub struct Concat<'a, K: ?Sized, V: ?Sized, P: BTreePage<K, V>> {/// Modified page.pub modified: ModifiedPage<'a, K, V, P>,/// Middle element.pub mid: (&'a K, &'a V),/// Sibling of the modified page.pub other: CowPage,/// Is the modified field on the left or on the right of the/// concatenation?pub mod_is_left: bool,/// Is the other page owned by this tree? If not, it means `other`/// is shared with another tree, and hence we need to increase the/// reference count of entries coming from `other`.pub other_is_mutable: bool,} - replacement in sanakirja-core/src/btree/del.rs at line 92
if cursor.set(txn, Some((key, value)))?.is_none() {if cursor.set(txn, key, value)?.is_none() { - replacement in sanakirja-core/src/btree/del.rs at line 104
/// Delete the entry pointed to by `cursor`./// Delete the entry pointed to by `cursor`. The cursor can't be used/// after this.#[doc(hidden)] - replacement in sanakirja-core/src/btree/del.rs at line 127
if p0 < cursor.first_rc_len {if p0 < cursor.first_rc_len() { - replacement in sanakirja-core/src/btree/del.rs at line 140[3.7994]→[3.13637:13710](∅→∅),[3.13710]→[3.8067:8093](∅→∅),[3.7185]→[3.8067:8093](∅→∅),[3.8067]→[3.8067:8093](∅→∅),[3.8093]→[3.13711:13841](∅→∅),[3.13841]→[3.8093:8182](∅→∅),[3.8093]→[3.8093:8182](∅→∅),[3.8182]→[3.13842:13900](∅→∅),[3.13900]→[3.8240:8302](∅→∅),[3.7255]→[3.8240:8302](∅→∅),[3.8240]→[3.8240:8302](∅→∅),[3.8302]→[3.13901:13963](∅→∅)
let mut left_page = P::right_child(cur.page.as_page(), &cur.cursor);while left_page > 0 {if cursor.first_rc_len >= N_CURSORS && txn.rc(left_page)? >= 2 {cursor.first_rc_len = cursor.len()}let page = txn.load_page(left_page)?;let curs = P::cursor_first(&page);left_page = P::left_child(page.as_page(), &curs);cursor.push(PageCursor { page, cursor: curs });}let leaf_is_shared = cursor.len() >= cursor.first_rc_len;let right_subtree = P::right_child(cur.page.as_page(), &cur.cursor);cursor.set_first_leaf(txn, right_subtree)?;let leaf_is_shared = cursor.len() >= cursor.first_rc_len(); - replacement in sanakirja-core/src/btree/del.rs at line 188
if cursor.len() + 1 >= cursor.first_rc_len {if cursor.len() + 1 >= cursor.first_rc_len() { - replacement in sanakirja-core/src/btree/del.rs at line 195
let root_is_shared = cursor.first_rc_len == 1;let root_is_shared = cursor.first_rc_len() == 1; - replacement in sanakirja-core/src/btree/del.rs at line 227
let is_rc = cursor.len() >= cursor.first_rc_len;let is_rc = cursor.len() >= cursor.first_rc_len(); - replacement in sanakirja-core/src/btree/del.rs at line 278
let rc_level = cursor.first_rc_len;let rc_level = cursor.first_rc_len(); - replacement in sanakirja-core/src/btree/del.rs at line 285
let (k0, v0) = P::from_saved(k0v0.as_ref().unwrap());let (k0, v0) = unsafe { P::from_saved(k0v0.as_ref().unwrap()) }; - replacement in sanakirja-core/src/btree/del.rs at line 364
let mutable = cursor.len() < cursor.first_rc_len;let mutable = cursor.len() < cursor.first_rc_len(); - replacement in sanakirja-core/src/btree/del.rs at line 431
last_op.ins = Some(P::from_saved(k0v0));last_op.ins = Some(unsafe { P::from_saved(k0v0) }); - replacement in sanakirja-core/src/btree/del.rs at line 460
last_op.ins = Some(P::from_saved(k0v0));last_op.ins = Some(unsafe { P::from_saved(k0v0) }); - replacement in sanakirja-core/src/btree/del.rs at line 476
let (k0, _) = P::from_saved(k0v0);let (k0, _) = unsafe { P::from_saved(k0v0) }; - replacement in sanakirja-core/src/btree/del.rs at line 486
if cursor.len() + 2 >= cursor.first_rc_len && !split_key_is_k0 {if cursor.len() + 2 >= cursor.first_rc_len() && !split_key_is_k0 { - replacement in sanakirja-core/src/btree/del.rs at line 500
if cursor.len() + 1 < cursor.first_rc_len {if cursor.len() + 1 < cursor.first_rc_len() { - replacement in sanakirja-core/src/btree/del.rs at line 633
let (k0, _) = P::from_saved(k0v0);let (k0, _) = unsafe { P::from_saved(k0v0) }; - replacement in sanakirja-core/src/btree/del.rs at line 678
) -> Result<Put<'a, K, V>, T::Error> {) -> Result<super::put::Put<'a, K, V>, T::Error> { - edit in sanakirja-core/src/btree/cursor.rs at line 4
use log::*; - replacement in sanakirja-core/src/btree/cursor.rs at line 22
/// A position in a database (mostly for internal use)./// A position in a B tree. - replacement in sanakirja-core/src/btree/cursor.rs at line 24
// Invariant: all items up to (and including) stack[pointer],// except possibly 0, are initialised./// Invariant: the first `len` items are initialised. - replacement in sanakirja-core/src/btree/cursor.rs at line 26
pub first_rc_len: usize,/// The length of the stack at the position of the first page/// shared with another tree. This definition is a little bit/// convoluted, but allows for efficient comparisons between/// `first_rc_len` and `len` to check whether a page is shared/// with another tree.first_rc_len: usize,/// Number of initialised items on the stack. - replacement in sanakirja-core/src/btree/cursor.rs at line 36
impl<'a, K: ?Sized, V: ?Sized, P: BTreePage<K, V>> Cursor<K, V, P> {impl<K: ?Sized, V: ?Sized, P: BTreePage<K, V>> Cursor<K, V, P> {/// Create a new cursor, initialised to the first entry of the B tree. - edit in sanakirja-core/src/btree/cursor.rs at line 91
} - edit in sanakirja-core/src/btree/cursor.rs at line 92
impl<K: ?Sized, V: ?Sized, P: BTreePage<K, V>> Cursor<K, V, P> { - edit in sanakirja-core/src/btree/cursor.rs at line 99
}pub(super) fn first_rc_len(&self) -> usize {self.first_rc_len - edit in sanakirja-core/src/btree/cursor.rs at line 120
pub(super) fn set_first_leaf<T: LoadPage>(&mut self,txn: &T,mut left_page: u64,) -> Result<(), T::Error> {while left_page > 0 {if self.first_rc_len >= N_CURSORS && txn.rc(left_page)? >= 2 {self.first_rc_len = self.len}let page = txn.load_page(left_page)?;let curs = P::cursor_first(&page);left_page = P::left_child(page.as_page(), &curs);self.push(PageCursor { page, cursor: curs });}Ok(())}/// Reset the cursor to the first element of the database.pub fn reset<'a, T: LoadPage>(&mut self) {self.len = 1;let init = unsafe { &mut *self.stack[0].as_mut_ptr() };init.cursor = P::cursor_before(&init.page);}// An invariant of cursors, fundamental to understand the `next`// and `prev` functions below, is that the lower levels (in the// tree, upper levels on the stack) are the left children of the// cursor's position on a page./// Set the cursor to the first position larger than or equal to/// the specified key and value. - replacement in sanakirja-core/src/btree/cursor.rs at line 154
k: Option<(&K, Option<&V>)>,k: &K,v: Option<&V>, - edit in sanakirja-core/src/btree/cursor.rs at line 168
debug!("set cursor {:?}", self.len); - replacement in sanakirja-core/src/btree/cursor.rs at line 173[3.11167]→[3.811:847](∅→∅),[3.66693]→[3.811:847](∅→∅),[3.847]→[3.66693:66731](∅→∅),[3.66693]→[3.66693:66731](∅→∅),[3.66731]→[3.19265:19365](∅→∅),[3.15269]→[3.66814:66973](∅→∅),[3.19365]→[3.66814:66973](∅→∅),[3.34329]→[3.66814:66973](∅→∅),[3.8407]→[3.66814:66973](∅→∅),[3.66814]→[3.66814:66973](∅→∅),[3.66973]→[3.19366:19416](∅→∅),[3.19416]→[3.848:873](∅→∅),[3.67027]→[3.848:873](∅→∅),[3.873]→[3.15270:15337](∅→∅)
debug!("{:?}", cursor);if let Some((k, v)) = k {if let Ok((kk, vv, _)) = P::set_cursor(txn, current.page.as_page(), cursor, k, v) {if v.is_some() {return Ok(Some((kk, vv)));}last_match = Some((kk, vv));last_matching_page = self.len} else {debug!("not found on page {:?}", current.page)if let Ok((kk, vv, _)) = P::set_cursor(txn, current.page.as_page(), cursor, k, v) {if v.is_some() {return Ok(Some((kk, vv))); - replacement in sanakirja-core/src/btree/cursor.rs at line 177
} else {*cursor = P::cursor_first(¤t.page);last_match = Some((kk, vv));last_matching_page = self.len - edit in sanakirja-core/src/btree/cursor.rs at line 199
/// Set the cursor after the last element, so that [`Self::next`]/// returns `None`, and [`Self::prev`] returns the last element. - edit in sanakirja-core/src/btree/cursor.rs at line 228[3.68805]→[3.1018:1020](∅→∅),[3.1020]→[3.3453:3459](∅→∅),[3.3459]→[3.11917:11929](∅→∅),[3.11929]→[3.12678:12776](∅→∅),[3.12776]→[3.11930:11963](∅→∅),[3.3567]→[3.11930:11963](∅→∅),[3.11963]→[3.3595:3619](∅→∅),[3.3595]→[3.3595:3619](∅→∅),[3.2136]→[3.2136:2291](∅→∅)
}impl<'a,K: Storable + ?Sized + core::fmt::Debug,V: Storable + ?Sized + core::fmt::Debug,P: BTreePage<K, V> + 'a,> Cursor<K, V, P>{// Cursor invariant: the lower levels (in the tree, upper levels// on the stack) are the left children of the cursor's position on// a page. - replacement in sanakirja-core/src/btree/cursor.rs at line 229[3.2292]→[3.7972:8070](∅→∅),[3.12059]→[3.1156:1184](∅→∅),[3.8070]→[3.1156:1184](∅→∅),[3.11441]→[3.1156:1184](∅→∅)
pub fn next<T: LoadPage>(&mut self, txn: &'a T) -> Result<Option<(&'a K, &'a V)>, T::Error> {debug!("=== next");/// Return the current position of the cursor, and move the cursor/// to the next position.pub fn next<'a, T: LoadPage>(&mut self,txn: &'a T,) -> Result<Option<(&'a K, &'a V)>, T::Error> { - edit in sanakirja-core/src/btree/cursor.rs at line 236
debug!("next: {:?}", self.len); - replacement in sanakirja-core/src/btree/cursor.rs at line 240
// Then visit the left child of the page (if any), i.e. push.// Visit the left child of the page (if any), i.e. push. - replacement in sanakirja-core/src/btree/cursor.rs at line 258
return Ok(Some((k, v)));unsafe {return Ok(Some((core::mem::transmute(k), core::mem::transmute(v))));} - replacement in sanakirja-core/src/btree/cursor.rs at line 269
pub fn prev<T: LoadPage>(&mut self, txn: &'a T) -> Result<Option<(&'a K, &'a V)>, T::Error> {debug!("======== prev");/// Move the cursor to the previous entry, and return that/// entry.pub fn prev<'a, T: LoadPage>(&mut self,txn: &'a T,) -> Result<Option<(&'a K, &'a V)>, T::Error> { - edit in sanakirja-core/src/btree/cursor.rs at line 277[3.20415]→[3.8286:8347](∅→∅),[3.13403]→[3.8286:8347](∅→∅),[3.8347]→[3.20416:20471](∅→∅),[3.20471]→[3.8406:8421](∅→∅),[3.8406]→[3.8406:8421](∅→∅)
debug!("prev = {:?} {:?} {:?}",self.len, current.page, current.cursor); - edit in sanakirja-core/src/btree/cursor.rs at line 278
debug!("empty"); - edit in sanakirja-core/src/btree/cursor.rs at line 290
debug!("current = {:?} {:?}", k, v); - replacement in sanakirja-core/src/btree/cursor.rs at line 300
return Ok(Some((k, v)));unsafe {return Ok(Some((core::mem::transmute(k), core::mem::transmute(v))));} - edit in sanakirja-core/src/btree/cursor.rs at line 304
debug!("pop"); - replacement in sanakirja-core/src/btree/cursor.rs at line 331
cursor.set(txn, origin)?;if let Some((k, v)) = origin {cursor.set(txn, k, v)?;} - replacement in sanakirja-core/src/btree/cursor.rs at line 369
cursor.set(txn, origin)?;if let Some((k, v)) = origin {cursor.set(txn, k, v)?;} - replacement in sanakirja/src/tests.rs at line 58
let (k, v) = curs.set(&txn, Some((&((i0 * i0) % m), None))).unwrap().unwrap();let (k, v) = curs.set(&txn, &((i0 * i0) % m), None).unwrap().unwrap(); - replacement in sanakirja/src/tests.rs at line 64
let (k, v) = curs.set(&txn, Some((&((i0 * i0) % m), Some(&a)))).unwrap().unwrap();let (k, v) = curs.set(&txn, &((i0 * i0) % m), Some(&a)).unwrap().unwrap(); - replacement in sanakirja/src/tests.rs at line 252
curs.set(&txn, Some((&500, Some(&a)))).unwrap();curs.set(&txn, &500, Some(&a)).unwrap(); - replacement in sanakirja/src/tests.rs at line 870
let (&k, v) = cursor.set(&txn, Some((&i, None))).unwrap().unwrap();let (&k, v) = cursor.set(&txn, &i, None).unwrap().unwrap(); - replacement in sanakirja/src/tests.rs at line 881
let (&k, v) = cursor.set(&txn, Some((&i, None))).unwrap().unwrap();let (&k, v) = cursor.set(&txn, &i, None).unwrap().unwrap(); - replacement in sanakirja/src/environment/muttxn.rs at line 231
btree::del_at_cursor(self, &mut db, &mut curs)?;btree::del::del_at_cursor(self, &mut db, &mut curs)?; - replacement in sanakirja/src/environment/muttxn.rs at line 275
curs.set(self, Some((&off, None)))?;curs.set(self, &off, None)?; - replacement in sanakirja/src/environment/muttxn.rs at line 308
curs.set(self, Some((&off, None)))?;curs.set(self, &off, None)?; - replacement in sanakirja/src/environment/muttxn.rs at line 343
let rc = if let Some((rc, _)) = curs.set(self, Some((&off, None)))? {let rc = if let Some((rc, _)) = curs.set(self, &off, None)? { - replacement in sanakirja/src/environment/muttxn.rs at line 353
btree::del_at_cursor(self, &mut rc_, &mut curs)?;btree::del::del_at_cursor(self, &mut rc_, &mut curs)?;