52X5P7NDBQHIJDIYNY3XUPDHHOO3PDPPNKGO2PGLXKVNM3EVECTQC · Changes

edit in sanakirja-core/src/lib.rs at line 179

[3.168]→[3.1746:1749](∅→∅),[3.633]→[3.1746:1749](∅→∅),[3.1746]→[3.1746:1749](∅→∅),[3.1749]→[3.1868:1965](∅→∅),[3.1566]→[3.1833:1969](∅→∅),[3.1965]→[3.1833:1969](∅→∅),[3.228]→[3.1833:1969](∅→∅),[3.709]→[3.1833:1969](∅→∅),[3.1833]→[3.1833:1969](∅→∅)

}

fn alloc_size<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(k: &K, v: &V) -> usize {

let s = ((k.size() + V::ALIGN - 1) & !(V::ALIGN - 1)) + v.size();

let al = K::ALIGN.max(V::ALIGN);

(s + al - 1) & !(al - 1)

edit in sanakirja-core/src/btree/put.rs at line 41

[3.4317]

[3.0]

debug!("put {:?} {:?}", key, value);

replacement in sanakirja-core/src/btree/put.rs at line 127

[3.1695]→[3.2192:2242](∅→∅)

debug!("Want to split the root");

[3.1695]

[3.1696]

debug!("Split {:?} {:?}", split_key, split_value);

edit in sanakirja-core/src/btree/put.rs at line 174

[3.7298]

[3.2134]

debug!("Ok");

edit in sanakirja-core/src/btree/page_unsized.rs at line 1

[3.2014]

[3.2015]

//! Implementation of B tree pages for Unsized types, or types with an

//! dynamically-sized representation (for example enums with widely

//! different sizes).

//!

//! This module follows the same organisation as the sized

//! implementation, and contains types shared between the two

//! implementations.

//!

//! The types that can be used with this implementation must implement

//! the [`UnsizedStorable`] trait, which essentially replaces the

//! [`core::mem`] functions for determining the size and alignment of

//! values.

//!

//! One key difference is the implementation of leaves (internal nodes

//! have the same format): indeed, in this implementation, leaves have

//! almost the same format as internal nodes, except that their

//! offsets are written on the page as little-endian-encoded [`u16`]

//! (with only the 12 LSBs used, i.e. 4 bits unused).

replacement in sanakirja-core/src/btree/page_unsized.rs at line 24

[3.2054]→[3.2054:2066](∅→∅)

use log::*;

[3.2054]

[3.2066]

// The header is the same as for the sized implementation, so we share

// it here.

pub(super) mod header;

edit in sanakirja-core/src/btree/page_unsized.rs at line 29

[3.2067]

[3.2076]

// Like in the sized implementation, we have the same three submodules.

edit in sanakirja-core/src/btree/page_unsized.rs at line 31

[3.2087]

[3.1018]

// This is a common module with the sized implementation.

pub(super) mod cursor;

edit in sanakirja-core/src/btree/page_unsized.rs at line 36

[3.1027]

[3.2087]

pub(super) mod rebalance;

replacement in sanakirja-core/src/btree/page_unsized.rs at line 38

[3.2101]→[3.404:437](∅→∅),[3.437]→[3.2128:2143](∅→∅),[3.2128]→[3.2128:2143](∅→∅)

pub(in super::super) mod header;

mod rebalance;

[3.2101]

[3.438]

use cursor::*;

edit in sanakirja-core/src/btree/page_unsized.rs at line 46

[3.2325]

}

// Many of these functions are the same as in the Sized implementations.

impl<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized> super::BTreePage<K, V>

for Page<K, V>

{

fn is_empty(c: &Self::Cursor) -> bool {

c.cur >= c.total as isize

}

fn is_init(c: &Self::Cursor) -> bool {

c.cur < 0

}

type Cursor = PageCursor;

fn cursor_before(p: &crate::CowPage) -> Self::Cursor {

PageCursor::new(p, -1)

}

fn cursor_after(p: &crate::CowPage) -> Self::Cursor {

PageCursor::after(p)

}

// Split a cursor, returning two cursors `(a, b)` where b is the

// same as `c`, and `a` is a cursor running from the first element

// of the page to `c` (excluding `c`).

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,

)

}

fn move_next(c: &mut Self::Cursor) -> bool {

if c.cur < c.total as isize {

c.cur += 1;

true

} else {

false

}

fn move_prev(c: &mut Self::Cursor) -> bool {

if c.cur > 0 {

c.cur -= 1;

true

} else {

c.cur = -1;

false

}

// This function is the same as the sized implementation for

// internal nodes, since the only difference between leaves and

// internal nodes in this implementation is the size of offsets (2

// bytes for leaves, 8 bytes for internal nodes).

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 {

unsafe {

let off =

u16::from_le(*(page.data.as_ptr().add(HDR + c.cur as usize * 2) as *const u16));

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off as usize));

Some((

K::from_raw_ptr(txn, k as *const u8),

V::from_raw_ptr(txn, v as *const u8),

0,

))

}

} else {

unsafe {

let off =

u64::from_le(*(page.data.as_ptr().add(HDR + c.cur as usize * 8) as *const u64));

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add((off & 0xfff) as usize));

Some((

K::from_raw_ptr(txn, k as *const u8),

V::from_raw_ptr(txn, v as *const u8),

off & !0xfff,

))

}

// These methods are the same as in the sized implementation.

fn left_child(page: crate::Page, c: &Self::Cursor) -> u64 {

assert!(c.cur >= 0);

if c.is_leaf {

0

} else {

assert!(c.cur >= 0 && HDR as isize + c.cur * 8 - 8 <= 4088);

let off =

unsafe { *(page.data.as_ptr().add((HDR + c.cur as usize * 8) - 8) as *const u64) };

u64::from_le(off) & !0xfff

}

fn right_child(page: crate::Page, c: &Self::Cursor) -> u64 {

assert!(c.cur < c.total as isize);

if c.is_leaf {

0

} else {

assert!(c.cur < c.total as isize && HDR as isize + c.cur * 8 - 8 <= 4088);

let off = unsafe { *(page.data.as_ptr().add(HDR + c.cur as usize * 8) as *const u64) };

u64::from_le(off) & !0xfff

}

fn set_cursor<'a, T: LoadPage>(

txn: &'a T,

page: crate::Page,

c: &mut PageCursor,

k0: &K,

v0: Option<&V>,

) -> Result<(&'a K, &'a V, u64), usize> {

unsafe {

// `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.

match lookup(txn, page, c, k0, v0) {

Ok(n) => {

c.cur = n as isize;

if c.is_leaf {

let off =

u16::from_le(*(page.data.as_ptr().add(HDR + n * 2) as *const u16));

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off as usize));

Ok((K::from_raw_ptr(txn, k), V::from_raw_ptr(txn, v), 0))

} else {

let off =

u64::from_le(*(page.data.as_ptr().add(HDR + n * 8) as *const u64));

let (k, v) =

read::<T, K, V>(txn, page.data.as_ptr().add(off as usize & 0xfff));

Ok((

K::from_raw_ptr(txn, k),

V::from_raw_ptr(txn, v),

off & !0xfff,

))

}

Err(n) => {

c.cur = n as isize;

Err(n)

}

// There quite some duplicated code in the following function, because

// we're forming a slice of offsets, and the using the core library's

// `binary_search_by` method on slices.

unsafe fn lookup<T: LoadPage, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

txn: &T,

page: crate::Page,

c: &mut PageCursor,

k0: &K,

v0: Option<&V>,

) -> Result<usize, usize> {

let hdr = header(page);

c.total = hdr.n() as usize;

c.is_leaf = hdr.is_leaf();

if c.is_leaf {

let s = core::slice::from_raw_parts(

page.data.as_ptr().add(HDR) as *const u16,

hdr.n() as usize,

);

if let Some(v0) = v0 {

s.binary_search_by(|&off| {

let off = u16::from_le(off);

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));

let k = K::from_raw_ptr(txn, k as *const u8);

match k.compare(txn, k0) {

Ordering::Equal => {

let v = V::from_raw_ptr(txn, v as *const u8);

v.compare(txn, v0)

}

cmp => cmp,

}

})

} else {

s.binary_search_by(|&off| {

let off = u16::from_le(off);

let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));

let k = K::from_raw_ptr(txn, k);

k.compare(txn, k0)

})

}

} else {

let s = core::slice::from_raw_parts(

page.data.as_ptr().add(HDR) as *const u64,

hdr.n() as usize,

);

if let Some(v0) = v0 {

s.binary_search_by(|&off| {

let off = u64::from_le(off) & 0xfff;

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));

let k = K::from_raw_ptr(txn, k);

match k.compare(txn, k0) {

Ordering::Equal => {

let v = V::from_raw_ptr(txn, v);

v.compare(txn, v0)

}

cmp => cmp,

}

})

} else {

s.binary_search_by(|&off| {

let off = u64::from_le(off) & 0xfff;

let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));

let k = K::from_raw_ptr(txn, k);

k.compare(txn, k0)

})

}

edit in sanakirja-core/src/btree/page_unsized.rs at line 273

[3.2487]

// The init function is straightforward.

edit in sanakirja-core/src/btree/page_unsized.rs at line 279

[3.2648]

[3.0]

// Deletions in internal nodes of a B tree need to replace the

// deleted value with a value from a leaf.

//

// In this implementation of pages, we never actually wipe any

// data from pages, we're even only appending data, or cloning the

// pages to compact them. Therefore, raw pointers to leaves are

// always valid for as long as the page isn't freed, which can

// only happen at the very last step of an insertion or deletion.

edit in sanakirja-core/src/btree/page_unsized.rs at line 296

[3.243]

[3.3641]

// As in the sized implementation, `put` is split into its own submodule.

replacement in sanakirja-core/src/btree/page_unsized.rs at line 309

[2.1176]→[3.381:410](∅→∅),[3.3909]→[3.381:410](∅→∅)

assert!(c.cur >= 0);

[2.1176]

[3.3909]

debug_assert!(c.cur >= 0);

debug_assert!(k1v1.is_none() || replace);

edit in sanakirja-core/src/btree/page_unsized.rs at line 340

[3.4585]

// Update the left child of the entry pointed to by cursor `c`.

replacement in sanakirja-core/src/btree/page_unsized.rs at line 346

[3.4718]→[3.4718:4734](∅→∅)

r: u64,

[3.4718]

[2.1177]

l: u64,

edit in sanakirja-core/src/btree/page_unsized.rs at line 351

[3.2188]

[3.5030]

// If the page is dirty (allocated by this transaction)

// and isn't shared, just make it mutable.

replacement in sanakirja-core/src/btree/page_unsized.rs at line 354

[3.5053]→[3.5053:5103](∅→∅)

unsafe { core::mem::transmute(page) }

[3.5053]

[3.5103]

MutPage(page)

edit in sanakirja-core/src/btree/page_unsized.rs at line 356

[3.5120]

// Else, clone the page:

edit in sanakirja-core/src/btree/page_unsized.rs at line 359

[3.5268]

[3.3298]

// Copy the left child

replacement in sanakirja-core/src/btree/page_unsized.rs at line 363

[3.5411]→[3.3364:3432](∅→∅),[3.3432]→[3.5479:5506](∅→∅),[3.421]→[3.5479:5506](∅→∅),[3.5479]→[3.5479:5506](∅→∅),[3.5506]→[3.3433:3507](∅→∅),[3.3507]→[3.2189:2246](∅→∅),[3.507]→[3.2189:2246](∅→∅),[3.5580]→[3.2189:2246](∅→∅),[3.2246]→[3.5652:5689](∅→∅),[3.5652]→[3.5652:5689](∅→∅)

let s = Internal::offset_slice::<K, V>(page.as_page());

let mut n = 0;

clone::<K, V, Internal>(page.as_page(), &mut new, s, &mut n);

let b = if page.is_dirty() { 1 } else { 0 };

freed = page.offset | b;

[3.5411]

[3.5689]

// Copy all the entries

let s = Internal::offset_slice(page.as_page());

clone::<K, V, Internal>(page.as_page(), &mut new, s, &mut 0);

// Mark the old version for freeing.

freed = page.offset | if page.is_dirty() { 1 } else { 0 };

replacement in sanakirja-core/src/btree/page_unsized.rs at line 370

[3.5716]→[3.605:652](∅→∅)

assert!(c.cur < c.total as isize + 1);

[3.5716]

[3.5754]

// Finally, update the left children of the cursor. We know

// that all valid positions of a cursor except the leftmost

// one (-1) have a left child.

assert!(c.cur >= 0);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 376

[3.5856]→[3.5856:5919](∅→∅)

*off = (r | (u64::from_le(*off) & 0xfff)).to_le();

[3.5856]

[3.5919]

*off = (l | (u64::from_le(*off) & 0xfff)).to_le();

edit in sanakirja-core/src/btree/page_unsized.rs at line 381

[3.5967]

[3.1190]

// Here is how deletions work: if the page is dirty and mutable,

// we "unlink" the value by moving the end of the offset array to

// the left by one offset (2 bytes in leaves, 8 bytes in internal

// nodes).

replacement in sanakirja-core/src/btree/page_unsized.rs at line 392

[3.761]→[3.653:710](∅→∅),[3.1340]→[3.653:710](∅→∅)

assert!(c.cur >= 0 && c.cur < c.total as isize);

[3.761]

[3.2247]

// Check that the cursor is at a valid position for a deletion.

debug_assert!(c.cur >= 0 && c.cur < c.total as isize);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 396

[3.6230]→[3.6230:6305](∅→∅)

let mut page: MutPage = unsafe { core::mem::transmute(page) };

[3.6230]

[3.6305]

let mut page = MutPage(page);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 398

[3.6350]→[3.6350:6448](∅→∅)

unsafe {

if c.is_leaf {

let n = hdr.n() as usize;

[3.6350]

[3.711]

let n = hdr.n();

if c.is_leaf {

unsafe {

replacement in sanakirja-core/src/btree/page_unsized.rs at line 402

[3.786]→[3.6514:6630](∅→∅),[3.6514]→[3.6514:6630](∅→∅),[3.6630]→[3.762:843](∅→∅),[3.864]→[3.6698:6759](∅→∅),[3.843]→[3.6698:6759](∅→∅),[3.6698]→[3.6698:6759](∅→∅),[3.6759]→[3.865:940](∅→∅),[3.940]→[3.6825:6998](∅→∅),[3.6825]→[3.6825:6998](∅→∅),[3.6998]→[3.844:940](∅→∅),[3.1033]→[3.7081:7125](∅→∅),[3.940]→[3.7081:7125](∅→∅),[3.7081]→[3.7081:7125](∅→∅)

let kv_ptr = p.add((*ptr) as usize);

let size = entry_size::<K, V>(kv_ptr);

core::ptr::copy(ptr.offset(1), ptr, n - c.cur as usize - 1);

hdr.decr(size);

} else {

let ptr = p.add(HDR + c.cur as usize * 8) as *mut u64;

let off = (u64::from_le(*ptr) & 0xfff) as usize;

let kv_ptr = p.add(off);

let size = entry_size::<K, V>(kv_ptr);

core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - c.cur as usize - 1);

(&mut *hdr).decr(size);

[3.786]

[3.7125]

// Get the offset in the page of the key/value data.

let off = u16::from_le(*ptr);

assert_eq!(off & 0xf000, 0);

// Erase the offset by shifting the last (`n -

// c.cur - 1`) offsets. The reasoning against

// "off-by-one errors" is that if the cursor is

// positioned on the first element (`c.cur == 0`),

// there are `n-1` elements to shift.

core::ptr::copy(ptr.offset(1), ptr, n as usize - c.cur as usize - 1);

// Remove the size of the actualy key/value, plus

// 2 bytes (the offset).

hdr.decr(2 + entry_size::<K, V>(p.add(off as usize)));

replacement in sanakirja-core/src/btree/page_unsized.rs at line 415

[3.7143]→[3.7143:7158](∅→∅),[3.7158]→[3.7158:7274](∅→∅)

};

if l > 0 {

assert!(!c.is_leaf);

// Updating the left page if necessary.

[3.7143]

[3.7274]

} else {

replacement in sanakirja-core/src/btree/page_unsized.rs at line 417

[3.7299]→[3.7299:7453](∅→∅)

let off = (p.add(HDR) as *mut u64).offset(c.cur as isize - 1);

*off = (l | (u64::from_le(*off) & 0xfff)).to_le();

[3.7299]

[3.7453]

let ptr = p.add(HDR + c.cur as usize * 8) as *mut u64;

// Offset to the key/value data.

let off = u64::from_le(*ptr);

// Shift the offsets like in the leaf case above.

core::ptr::copy(ptr.offset(1), ptr, n as usize - c.cur as usize - 1);

if l > 0 {

// In an internal node, we may have to update

// the left child of the current

// position. After the move, the current

// offset is at `ptr`, so we need to find the

// offset one step to the left.

let p = ptr.offset(-1);

*p = (l | (u64::from_le(*p) & 0xfff)).to_le();

}

// Remove the size of the key/value, plus 8 bytes

// (the offset).

hdr.decr(8 + entry_size::<K, V>(p.add(off as usize)));

replacement in sanakirja-core/src/btree/page_unsized.rs at line 435

[3.7471]→[3.7471:7521](∅→∅)

}

hdr.set_n(hdr.n() - 1);

[3.7471]

[3.941]

};

hdr.set_n(n - 1);

// Return the page, and 0 for "nothing was freed".

replacement in sanakirja-core/src/btree/page_unsized.rs at line 440

[3.7559]→[3.7559:7800](∅→∅),[3.7800]→[3.1034:1097](∅→∅),[3.1097]→[3.0:50](∅→∅),[3.1097]→[3.7854:8148](∅→∅),[3.50]→[3.7854:8148](∅→∅),[3.7854]→[3.7854:8148](∅→∅),[3.8148]→[3.1098:1161](∅→∅),[3.1161]→[3.51:101](∅→∅),[3.1161]→[3.8202:8320](∅→∅),[3.101]→[3.8202:8320](∅→∅),[3.8202]→[3.8202:8320](∅→∅),[3.8320]→[3.968:999](∅→∅)

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::<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 {

let s = Internal::offset_slice::<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, Internal>(page.as_page(), &mut new, s0, &mut n);

if l > 0 {

[3.7559]

[3.999]

// If the page cannot be mutated, we allocate a new page and clone.

let mut new = txn.alloc_page()?;

<Page<K, V> as BTreeMutPage<K, V>>::init(&mut new);

if c.is_leaf {

// In a leaf, this is just a matter of getting the

// offset slice, removing the current position and

// cloning.

let s = Leaf::offset_slice(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 {

// In an internal node, things are a bit trickier,

// since we might need to update the left child.

//

// First, clone the leftmost child of the page.

let hdr = header(page.as_page());

let left = hdr.left_page() & !0xfff;

unsafe {

*(new.0.data.add(HDR) as *mut u64).offset(-1) = left.to_le();

}

// Then, clone the first half of the page.

let s = Internal::offset_slice(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, Internal>(page.as_page(), &mut new, s0, &mut n);

// Update the left child, which was written by the

// call to `clone` as the right child of the last

// entry in `s0`.

if l > 0 {

unsafe {

edit in sanakirja-core/src/btree/page_unsized.rs at line 476

[3.1157]→[3.1157:1391](∅→∅)

} 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_unsized.rs at line 477

[3.71]→[3.8436:8519](∅→∅),[3.1413]→[3.8436:8519](∅→∅),[3.8436]→[3.8436:8519](∅→∅)

clone::<K, V, Internal>(page.as_page(), &mut new, s1, &mut n);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 478

[3.8537]→[3.1414:1463](∅→∅)

Ok((new, page.as_page().offset))

[3.8537]

[3.8561]

// Then, clone the second half of the page.

clone::<K, V, Internal>(page.as_page(), &mut new, s1, &mut n);

edit in sanakirja-core/src/btree/page_unsized.rs at line 481

[3.8575]

// Return the new page, and the offset of the freed page.

Ok((new, page.offset))

edit in sanakirja-core/src/btree/page_unsized.rs at line 486

[3.8592]

// Decide what to do with the concatenation of two neighbouring

// pages, with a middle element.

//

// This is highly similar to the sized case.

replacement in sanakirja-core/src/btree/page_unsized.rs at line 494

[3.8743]→[3.8743:8771](∅→∅)

let hdr_size = HDR;

[3.8743]

[3.8771]

// First evaluate the size of the middle element on a

// page. Contrarily to the sized case, the offsets are

// aligned, so the header is always the same size (no

// padding).

edit in sanakirja-core/src/btree/page_unsized.rs at line 503

[3.8955]

[3.281]

// Evaluate the size of the modified page of the concatenation

// (which includes the header).

edit in sanakirja-core/src/btree/page_unsized.rs at line 507

[3.331]

[3.9003]

// Add the "occupied" size (which excludes the header).

replacement in sanakirja-core/src/btree/page_unsized.rs at line 512

[3.9135]→[3.0:62](∅→∅),[3.62]→[3.9197:9489](∅→∅),[3.9197]→[3.9197:9489](∅→∅),[3.9489]→[3.3594:3840](∅→∅),[3.3840]→[3.332:371](∅→∅),[3.9489]→[3.332:371](∅→∅),[3.371]→[3.371:428](∅→∅)

let size = hdr_size + mod_size + mid_size + occupied;

debug!(

"size = {:?} {:?} {:?} {:?} {:?}",

mod_size, mid_size, occupied, hdr_size, size

);

if size <= PAGE_SIZE {

// merge

let 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]

};

if m.modified.c0.is_leaf {

merge::<_, _, _, Leaf>(txn, &mut new, m)

[3.9135]

[3.428]

if mod_size + mid_size + occupied <= PAGE_SIZE {

// If the concatenation fits on a page, merge.

return if m.modified.c0.is_leaf {

merge::<_, _, _, _, Leaf>(txn, m)

replacement in sanakirja-core/src/btree/page_unsized.rs at line 517

[3.449]→[3.449:510](∅→∅),[3.510]→[3.9722:9736](∅→∅),[3.9722]→[3.9722:9736](∅→∅),[3.2418]→[3.10008:10070](∅→∅),[3.10008]→[3.10008:10070](∅→∅),[3.10070]→[3.3841:3864](∅→∅),[3.3864]→[3.10145:10212](∅→∅),[3.10145]→[3.10145:10212](∅→∅)

merge::<_, _, _, Internal>(txn, &mut new, m)

}

return Ok(Op::Merged {

page: new,

freed,

marker: core::marker::PhantomData,

});

[3.449]

[3.10212]

merge::<_, _, _, _, Internal>(txn, m)

};

replacement in sanakirja-core/src/btree/page_unsized.rs at line 520

[3.10222]→[3.2419:2466](∅→∅),[3.2466]→[3.3865:3942](∅→∅),[3.3942]→[3.10363:10496](∅→∅),[3.657]→[3.10363:10496](∅→∅),[3.10363]→[3.10363:10496](∅→∅)

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 || occupied - first_size < PAGE_SIZE / 2 {

[3.10222]

[3.10496]

// If we can't merge, evaluate the size of the first binding

// on the other page, to see if we can rebalance.

let first_other = PageCursor::new(&m.other, 0);

let first_other_size = current_size::<K, V>(m.other.as_page(), &first_other);

// If the modified page is at least half-full, or if removing

// the first entry on the other page would make that other

// page less than half-full, don't rebalance. See the Sized

// implementation to see cases where this happens.

if mod_size >= PAGE_SIZE / 2 || HDR + occupied - first_other_size < PAGE_SIZE / 2 {

replacement in sanakirja-core/src/btree/page_unsized.rs at line 536

[3.10698]→[3.557:583](∅→∅)

true,

[3.10698]

m.modified.skip_first,

edit in sanakirja-core/src/btree/page_unsized.rs at line 545

[3.10928]

[3.1464]

debug_assert!(m.modified.ins2.is_none());

edit in sanakirja-core/src/btree/page_unsized.rs at line 556

[3.11141]

// Finally, if we're here, we can rebalance. There are four

// (relatively explicit) cases, see the `rebalance` submodule

// to see how this is done.

replacement in sanakirja-core/src/btree/page_unsized.rs at line 566

[3.11375]→[3.11375:11567](∅→∅)

if m.modified.c0.is_leaf {

rebalance_right::<_, _, _, Leaf>(txn, m)

} else {

rebalance_right::<_, _, _, Internal>(txn, m)

}

[3.11375]

[3.11567]

rebalance_right::<_, _, _, Self>(txn, m)

edit in sanakirja-core/src/btree/page_unsized.rs at line 571

[3.11586]

[3.2426]

/// Size of a modified page (including the header).

edit in sanakirja-core/src/btree/page_unsized.rs at line 580

[3.834]

// Extra size for the offsets.

replacement in sanakirja-core/src/btree/page_unsized.rs at line 584

[3.918]→[3.918:977](∅→∅)

total += extra + crate::alloc_size(k, v) as usize;

[3.918]

[3.977]

total += extra + alloc_size(k, v) as usize;

replacement in sanakirja-core/src/btree/page_unsized.rs at line 586

[3.1016]→[3.1016:1079](∅→∅)

total += extra + crate::alloc_size(k, v) as usize;

[3.1016]

[3.1079]

total += extra + alloc_size(k, v) as usize;

replacement in sanakirja-core/src/btree/page_unsized.rs at line 590

[3.1117]→[3.3988:4086](∅→∅)

total -= <Page<K, V> as BTreePage<K, V>>::current_size(m.page.as_page(), &m.c1) as usize;

[3.1117]

[3.1215]

total -= current_size::<K, V>(m.page.as_page(), &m.c1) as usize;

edit in sanakirja-core/src/btree/page_unsized.rs at line 594

[3.1233]→[3.1233:1234](∅→∅),[3.1234]→[3.2494:2601](∅→∅),[3.2601]→[3.2467:2511](∅→∅),[3.1440]→[3.2467:2511](∅→∅),[3.2511]→[3.1215:1249](∅→∅),[3.11833]→[3.1215:1249](∅→∅),[3.1249]→[3.11858:11864](∅→∅),[3.11858]→[3.11858:11864](∅→∅),[3.11864]→[3.1250:1251](∅→∅),[3.1251]→[3.2512:2555](∅→∅),[3.2555]→[3.1310:1334](∅→∅),[3.1310]→[3.1310:1334](∅→∅),[3.1334]→[3.107:137](∅→∅),[3.137]→[3.2556:2615](∅→∅),[3.2615]→[3.138:169](∅→∅),[3.1390]→[3.138:169](∅→∅),[3.1417]→[3.12093:12099](∅→∅),[3.169]→[3.12093:12099](∅→∅),[3.12093]→[3.12093:12099](∅→∅),[3.12099]→[3.2616:2674](∅→∅),[3.2674]→[3.170:199](∅→∅),[3.1472]→[3.170:199](∅→∅),[3.1497]→[3.12329:12335](∅→∅),[3.199]→[3.12329:12335](∅→∅),[3.12329]→[3.12329:12335](∅→∅),[3.12335]→[3.1498:1531](∅→∅),[3.1531]→[3.12385:12459](∅→∅),[3.12385]→[3.12385:12459](∅→∅),[3.12459]→[3.1532:1571](∅→∅),[3.1571]→[3.1571:1691](∅→∅),[3.1691]→[3.904:1084](∅→∅),[3.1084]→[3.1827:1907](∅→∅),[3.1827]→[3.1827:1907](∅→∅),[3.1907]→[3.1907:1930](∅→∅),[3.1930]→[3.1930:2046](∅→∅),[3.2046]→[3.2046:2102](∅→∅),[3.2102]→[3.12825:12842](∅→∅),[3.1720]→[3.12825:12842](∅→∅),[3.12825]→[3.12825:12842](∅→∅),[3.12842]→[3.2103:2224](∅→∅),[3.2224]→[3.2224:2323](∅→∅),[3.2323]→[3.2323:2346](∅→∅),[3.2346]→[3.2346:2462](∅→∅),[3.2462]→[3.2462:2529](∅→∅),[3.2529]→[3.13133:13149](∅→∅),[3.1887]→[3.13133:13149](∅→∅),[3.13133]→[3.13133:13149](∅→∅),[3.13149]→[3.1235:1236](∅→∅),[3.1236]→[3.13527:13595](∅→∅),[3.13527]→[3.13527:13595](∅→∅),[3.13595]→[3.1769:1917](∅→∅),[3.1917]→[3.14134:14150](∅→∅),[3.14134]→[3.14134:14150](∅→∅),[3.14150]→[3.1237:1286](∅→∅),[3.1286]→[3.2920:2958](∅→∅),[3.14219]→[3.2920:2958](∅→∅),[3.2958]→[3.14248:14340](∅→∅),[3.14248]→[3.14248:14340](∅→∅),[3.14340]→[3.1287:1336](∅→∅),[3.1336]→[3.14409:14490](∅→∅),[3.14409]→[3.14409:14490](∅→∅),[3.14490]→[3.2959:2983](∅→∅),[3.2983]→[3.14490:14588](∅→∅),[3.14490]→[3.14490:14588](∅→∅),[3.14588]→[3.2984:3013](∅→∅),[3.3013]→[3.14588:14642](∅→∅),[3.14588]→[3.14588:14642](∅→∅),[3.14642]→[3.1351:1473](∅→∅),[3.3120]→[3.14739:14859](∅→∅),[3.1473]→[3.14739:14859](∅→∅),[3.14739]→[3.14739:14859](∅→∅),[3.14859]→[3.3121:3164](∅→∅),[3.3164]→[3.14859:14913](∅→∅),[3.14859]→[3.14859:14913](∅→∅),[3.14913]→[3.3165:3265](∅→∅),[3.3265]→[3.15004:15095](∅→∅),[3.15004]→[3.15004:15095](∅→∅),[3.15095]→[2.1229:1249](∅→∅),[2.1249]→[3.15112:15139](∅→∅),[3.15112]→[3.15112:15139](∅→∅),[3.15139]→[3.200:228](∅→∅),[3.228]→[3.15163:15266](∅→∅),[3.15163]→[3.15163:15266](∅→∅),[3.15266]→[2.1250:1569](∅→∅),[2.1569]→[3.15266:15321](∅→∅),[3.15266]→[3.15266:15321](∅→∅),[3.15396]→[3.15396:15764](∅→∅),[3.15764]→[3.15764:15817](∅→∅),[3.15817]→[3.15817:15976](∅→∅),[3.15976]→[3.1918:2119](∅→∅),[3.2119]→[3.16066:16089](∅→∅),[3.16066]→[3.16066:16089](∅→∅),[3.16089]→[3.3266:3297](∅→∅),[3.3297]→[3.16111:16194](∅→∅),[3.16111]→[3.16111:16194](∅→∅),[3.16194]→[3.3298:3329](∅→∅),[3.3329]→[3.16216:16284](∅→∅),[3.16216]→[3.16216:16284](∅→∅)

impl<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized> super::BTreePage<K, V>

for Page<K, V>

{

fn is_empty(c: &Self::Cursor) -> bool {

c.cur >= c.total as isize

}

fn is_init(c: &Self::Cursor) -> bool {

c.cur < 0

}

type Cursor = PageCursor;

fn cursor_before(p: &crate::CowPage) -> Self::Cursor {

PageCursor::new(p, -1)

}

fn cursor_after(p: &crate::CowPage) -> Self::Cursor {

PageCursor::after(p)

}

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 {

unsafe {

let off = {

u16::from_le(*(page.data.as_ptr().add(HDR + c.cur as usize * 2) as *const u16))

as usize

};

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off));

Some((

K::from_raw_ptr(txn, k as *const u8),

V::from_raw_ptr(txn, v as *const u8),

0,

))

}

} else {

unsafe {

let off = u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).offset(c.cur));

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add((off & 0xfff) as usize));

Some((

K::from_raw_ptr(txn, k as *const u8),

V::from_raw_ptr(txn, v as *const u8),

off & !0xfff,

))

}

fn current_size(page: crate::Page, c: &Self::Cursor) -> usize {

if c.is_leaf {

Leaf::current_size::<K, V>(page, c.cur)

} else {

Internal::current_size::<K, V>(page, c.cur)

}

fn move_next(c: &mut Self::Cursor) -> bool {

if c.cur < c.total as isize {

c.cur += 1;

true

} else {

false

}

fn move_prev(c: &mut Self::Cursor) -> bool {

if c.cur > 0 {

c.cur -= 1;

true

} else {

c.cur = -1;

false

}

fn left_child(page: crate::Page, c: &Self::Cursor) -> u64 {

assert!(c.cur >= 0);

if c.is_leaf {

0

} else {

let off =

unsafe { *(page.data.as_ptr().add((HDR + c.cur as usize * 8) - 8) as *const u64) };

u64::from_le(off) & !0xfff

}

fn right_child(page: crate::Page, c: &Self::Cursor) -> u64 {

assert!(c.cur < c.total as isize);

if c.is_leaf {

0

} else {

let off = unsafe { *(page.data.as_ptr().add(HDR + c.cur as usize * 8) as *const u64) };

u64::from_le(off) & !0xfff

}

fn set_cursor<'a, T: LoadPage>(

txn: &'a T,

page: crate::Page,

c: &mut PageCursor,

k0: &K,

v0: Option<&V>,

) -> Result<(&'a K, &'a V, u64), usize> {

unsafe {

// `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.

let lookup = lookup(txn, page, c, k0, v0);

let result;

c.cur = match lookup {

Ok(n) => {

result = if c.is_leaf {

let off = {

let off =

u16::from_le(*(page.data.as_ptr().add(HDR + n * 2) as *const u16));

(0, off)

};

Ok(Leaf::kv(txn, page, off))

} else {

let off =

u64::from_le(*(page.data.as_ptr().add(HDR + n * 8) as *const u64));

Ok(Internal::kv(

txn,

page,

(off & !0xfff, (off & 0xfff) as u16),

))

};

n as isize

}

Err(n) => {

result = Err(n);

n as isize

}

};

result

}

replacement in sanakirja-core/src/btree/page_unsized.rs at line 595

[3.16285]→[3.1337:1591](∅→∅),[3.1591]→[3.16369:16379](∅→∅),[3.16369]→[3.16369:16379](∅→∅),[3.16379]→[3.229:254](∅→∅),[3.254]→[3.16400:16424](∅→∅),[3.16400]→[3.16400:16424](∅→∅),[3.16424]→[3.3330:3376](∅→∅),[3.3376]→[3.16454:16537](∅→∅),[3.16454]→[3.16454:16537](∅→∅)

/// Split a cursor, returning two cursors `(a, b)` where b is the

/// same as `c`, and `a` is a cursor running from the first

/// element of the page to `c` (excluding `c`).

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,

)

}

[3.16285]

[3.16537]

// Size of a pair of type `(K, V)`. This is computed in the same way

// as a struct with fields of type `K` and `V` in C.

fn alloc_size<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(k: &K, v: &V) -> usize {

let s = ((k.size() + V::ALIGN - 1) & !(V::ALIGN - 1)) + v.size();

let al = K::ALIGN.max(V::ALIGN);

(s + al - 1) & !(al - 1)

replacement in sanakirja-core/src/btree/page_unsized.rs at line 603

[3.16540]→[3.2602:2691](∅→∅),[3.2691]→[3.16615:16628](∅→∅),[3.1559]→[3.16615:16628](∅→∅),[3.16615]→[3.16615:16628](∅→∅)

unsafe fn lookup<T: LoadPage, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

txn: &T,

[3.16540]

[3.16628]

// Total size of the entry for that cursor position, including the

// offset size.

fn current_size<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

replacement in sanakirja-core/src/btree/page_unsized.rs at line 607

[3.16651]→[3.255:279](∅→∅),[3.279]→[3.16671:16822](∅→∅),[3.16671]→[3.16671:16822](∅→∅)

c: &mut PageCursor,

k0: &K,

v0: Option<&V>,

) -> Result<usize, usize> {

let hdr = header(page);

c.total = hdr.n() as usize;

c.is_leaf = hdr.is_leaf();

[3.16651]

[3.16822]

c: &PageCursor,

) -> usize {

replacement in sanakirja-core/src/btree/page_unsized.rs at line 610

[3.16841]→[3.16841:17098](∅→∅),[3.17098]→[3.17098:17252](∅→∅),[3.17252]→[3.17252:17336](∅→∅),[3.17336]→[3.17336:17406](∅→∅),[3.17406]→[3.17406:17449](∅→∅),[3.17449]→[3.2120:2142](∅→∅),[3.2142]→[3.17472:17639](∅→∅),[3.17472]→[3.17472:17639](∅→∅),[3.17639]→[3.17639:17780](∅→∅),[3.17780]→[3.17780:17840](∅→∅)

let s = core::slice::from_raw_parts(

page.data.as_ptr().add(HDR) as *const u16,

hdr.n() as usize,

);

if let Some(v0) = v0 {

s.binary_search_by(|&off| {

let off = u16::from_le(off);

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));

let k = K::from_raw_ptr(txn, k as *const u8);

match k.compare(txn, k0) {

Ordering::Equal => {

let v = V::from_raw_ptr(txn, v as *const u8);

v.compare(txn, v0)

}

cmp => cmp,

}

})

} else {

s.binary_search_by(|&off| {

let off = u16::from_le(off);

let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize));

let k = K::from_raw_ptr(txn, k);

k.compare(txn, k0)

})

}

[3.16841]

[3.17840]

Leaf::current_size::<K, V>(page, c.cur)

replacement in sanakirja-core/src/btree/page_unsized.rs at line 612

[3.17853]→[3.17853:18118](∅→∅),[3.18118]→[3.18118:18267](∅→∅),[3.18267]→[3.18267:18351](∅→∅),[3.18351]→[3.18351:18408](∅→∅),[3.18408]→[3.18408:18451](∅→∅),[3.18451]→[3.2143:2165](∅→∅),[3.2165]→[3.18474:18649](∅→∅),[3.18474]→[3.18474:18649](∅→∅),[3.18649]→[3.18649:18798](∅→∅),[3.18798]→[3.18798:18858](∅→∅)

let s = core::slice::from_raw_parts(

page.data.as_ptr().add(HDR) as *const u64,

hdr.n() as usize,

);

if let Some(v0) = v0 {

s.binary_search_by(|&off| {

let off = u64::from_le(off) & 0xfff;

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));

let k = K::from_raw_ptr(txn, k);

match k.compare(txn, k0) {

Ordering::Equal => {

let v = V::from_raw_ptr(txn, v);

v.compare(txn, v0)

}

cmp => cmp,

}

})

} else {

s.binary_search_by(|&off| {

let off = u64::from_le(off) & 0xfff;

let (k, _) = read::<T, K, V>(txn, page.data.as_ptr().offset(off as isize & 0xfff));

let k = K::from_raw_ptr(txn, k);

k.compare(txn, k0)

})

}

[3.17853]

[3.18858]

Internal::current_size::<K, V>(page, c.cur)

replacement in sanakirja-core/src/btree/page_unsized.rs at line 616

[3.18867]→[3.18867:18897](∅→∅),[3.18897]→[3.280:304](∅→∅),[3.304]→[3.1560:1646](∅→∅)

#[derive(Debug, Clone, Copy)]

pub struct PageCursor {

pub(super) cur: isize,

pub(super) total: usize,

pub(super) is_leaf: bool,

[3.18867]

[3.3472]

pub(super) trait AllocWrite<K: ?Sized, V: ?Sized> {

fn alloc_write(new: &mut MutPage, k0: &K, v0: &V, l: u64, r: u64, n: &mut isize);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 620

[3.3475]→[3.305:323](∅→∅),[3.323]→[3.2675:2797](∅→∅),[3.2797]→[3.3583:3624](∅→∅),[3.3583]→[3.3583:3624](∅→∅),[3.3624]→[3.387:408](∅→∅),[3.408]→[3.3641:3747](∅→∅),[3.3641]→[3.3641:3747](∅→∅),[3.3747]→[3.2798:2910](∅→∅),[3.2910]→[3.3831:3860](∅→∅),[3.3831]→[3.3831:3860](∅→∅),[3.3860]→[3.463:484](∅→∅),[3.484]→[3.3877:3997](∅→∅),[3.3877]→[3.3877:3997](∅→∅),[3.3997]→[3.1759:1808](∅→∅),[3.537]→[3.4051:4109](∅→∅),[3.1808]→[3.4051:4109](∅→∅),[3.4051]→[3.4051:4109](∅→∅),[3.4109]→[3.538:559](∅→∅),[3.559]→[3.4126:4252](∅→∅),[3.4126]→[3.4126:4252](∅→∅),[3.4252]→[3.18970:18973](∅→∅),[3.18970]→[3.18970:18973](∅→∅),[3.18973]→[3.1592:1603](∅→∅),[3.1603]→[3.18991:19008](∅→∅),[3.18991]→[3.18991:19008](∅→∅),[3.19008]→[3.2692:2796](∅→∅),[3.2796]→[3.19108:19122](∅→∅),[3.19108]→[3.19108:19122](∅→∅),[3.19122]→[3.2166:2169](∅→∅)

impl PageCursor {

pub(super) fn new(p: &crate::CowPage, cur: isize) -> Self {

let hdr = unsafe { &*(p.data as *const Header) };

assert!(cur < hdr.n() as isize);

PageCursor {

cur,

total: hdr.n() as usize,

is_leaf: hdr.is_leaf(),

}

pub(super) fn after(p: &crate::CowPage) -> Self {

let hdr = unsafe { &*(p.data as *const Header) };

let total = hdr.n();

PageCursor {

cur: total as isize,

total: total as usize,

is_leaf: hdr.is_leaf(),

}

pub(super) fn last(p: crate::Page) -> Self {

let hdr = header(p);

let total = hdr.n();

PageCursor {

cur: (total - 1) as isize,

total: total as usize,

is_leaf: hdr.is_leaf(),

}

fn modify<

T: LoadPage,

K: UnsizedStorable + ?Sized + core::fmt::Debug,

V: UnsizedStorable + ?Sized + core::fmt::Debug,

L: Alloc,

>(

[3.3475]

[3.19129]

/// Perform the modifications on a page, by copying it onto page `new`.

fn modify<T: LoadPage, K: ?Sized, V: ?Sized, P: BTreeMutPage<K, V>, L: AllocWrite<K, V>>(

replacement in sanakirja-core/src/btree/page_unsized.rs at line 624

[3.19165]→[3.19165:19209](∅→∅)

m: &mut ModifiedPage<K, V, Page<K, V>>,

[3.19165]

[3.19209]

m: &mut ModifiedPage<K, V, P>,

replacement in sanakirja-core/src/btree/page_unsized.rs at line 627

[3.19232]→[3.19232:19262](∅→∅),[3.19262]→[3.4087:4241](∅→∅),[3.4241]→[3.19416:19462](∅→∅),[3.1012]→[3.19416:19462](∅→∅),[3.19416]→[3.19416:19462](∅→∅)

debug!("modify {:?}", m);

let mut l = <Page<K, V>>::left_child(m.page.as_page(), &m.c0);

while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.page.as_page(), &mut m.c0) {

alloc::<_, _, L>(new, k, v, l, r, n);

[3.19232]

[3.19462]

// This is the exact same implementation as in the sized

// module. I'm not convinced

let mut l = P::left_child(m.page.as_page(), &m.c0);

while let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut m.c0) {

L::alloc_write(new, k, v, l, r, n);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 636

[3.19558]→[3.19558:19664](∅→∅)

alloc::<_, _, L>(new, k, v, 0, 0, n);

alloc::<_, _, L>(new, k2, v2, m.l, m.r, n);

[3.19558]

[3.19664]

L::alloc_write(new, k, v, 0, 0, n);

L::alloc_write(new, k2, v2, m.l, m.r, n);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 639

[3.19681]→[3.19681:19735](∅→∅)

alloc::<_, _, L>(new, k, v, m.l, m.r, n);

[3.19681]

[3.19735]

L::alloc_write(new, k, v, m.l, m.r, n);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 644

[3.19780]→[3.19780:19817](∅→∅),[3.19817]→[3.4242:4329](∅→∅),[3.4329]→[3.19904:19988](∅→∅),[3.1111]→[3.19904:19988](∅→∅),[3.19904]→[3.19904:19988](∅→∅),[3.19988]→[3.2170:2216](∅→∅)

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;

}

alloc::<_, _, L>(new, k, v, l, r, n);

[3.19780]

[3.20035]

let mut c1 = m.c1.clone();

if m.skip_first {

P::move_next(&mut c1);

}

while let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut c1) {

L::alloc_write(new, k, v, l, r, n);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 654

[3.20059]→[3.1604:1614](∅→∅),[3.1614]→[3.20076:20093](∅→∅),[3.20076]→[3.20076:20093](∅→∅),[3.20093]→[3.2797:2901](∅→∅),[3.2901]→[3.20193:20207](∅→∅),[3.20193]→[3.20193:20207](∅→∅)

fn merge<

T: LoadPage,

K: UnsizedStorable + ?Sized + core::fmt::Debug,

V: UnsizedStorable + ?Sized + core::fmt::Debug,

L: Alloc,

[3.20059]

[3.2217]

/// The very unsurprising `merge` function

pub(super) fn merge<

'a,

T: AllocPage + LoadPage,

K: ?Sized,

V: ?Sized,

P: BTreeMutPage<K, V>,

L: AllocWrite<K, V>,

replacement in sanakirja-core/src/btree/page_unsized.rs at line 663

[3.2220]→[3.20214:20227](∅→∅),[3.20214]→[3.20214:20227](∅→∅),[3.20227]→[3.20227:20250](∅→∅),[3.20250]→[3.4330:4367](∅→∅),[3.4367]→[3.20288:20292](∅→∅),[3.20288]→[3.20288:20292](∅→∅)

txn: &T,

new: &mut MutPage,

mut m: Concat<K, V, Page<K, V>>,

) {

[3.2220]

[3.20292]

txn: &mut T,

mut m: Concat<K, V, P>,

) -> Result<Op<'a, T, K, V>, 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()?;

P::init(&mut new);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 678

[3.20334]→[3.20334:20399](∅→∅),[3.20399]→[3.2911:2962](∅→∅),[3.2962]→[3.4368:4434](∅→∅),[3.4434]→[3.20533:20596](∅→∅),[3.1189]→[3.20533:20596](∅→∅),[3.20533]→[3.20533:20596](∅→∅),[3.20596]→[3.4435:4525](∅→∅),[3.4525]→[3.20686:20741](∅→∅),[3.1291]→[3.20686:20741](∅→∅),[3.20686]→[3.20686:20741](∅→∅)

modify::<_, _, _, L>(txn, new, &mut m.modified, &mut n);

let mut rc = PageCursor::new(&m.other, 0);

let l = <Page<K, V>>::left_child(m.other.as_page(), &rc);

alloc::<_, _, L>(new, m.mid.0, m.mid.1, 0, l, &mut n);

while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.other.as_page(), &mut rc) {

alloc::<_, _, L>(new, k, v, 0, r, &mut n);

[3.20334]

[3.20741]

modify::<_, _, _, _, L>(txn, &mut new, &mut m.modified, &mut n);

let mut rc = P::cursor_first(&m.other);

let l = P::left_child(m.other.as_page(), &rc);

L::alloc_write(&mut new, m.mid.0, m.mid.1, 0, l, &mut n);

while let Some((k, v, r)) = P::next(txn, m.other.as_page(), &mut rc) {

L::alloc_write(&mut new, k, v, 0, r, &mut n);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 686

[3.20764]→[3.2963:3014](∅→∅),[3.3014]→[3.4526:4686](∅→∅),[3.4686]→[3.20992:21047](∅→∅),[3.1474]→[3.20992:21047](∅→∅),[3.20992]→[3.20992:21047](∅→∅)

let mut rc = PageCursor::new(&m.other, 0);

let mut l = <Page<K, V>>::left_child(m.other.as_page(), &rc);

while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.other.as_page(), &mut rc) {

alloc::<_, _, L>(new, k, v, l, r, &mut n);

[3.20764]

[3.21047]

let mut rc = P::cursor_first(&m.other);

let mut l = P::left_child(m.other.as_page(), &rc);

while let Some((k, v, r)) = P::next(txn, m.other.as_page(), &mut rc) {

L::alloc_write(&mut new, k, v, l, r, &mut n);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 692

[3.21076]→[3.21076:21139](∅→∅),[3.21139]→[3.21139:21204](∅→∅)

alloc::<_, _, L>(new, m.mid.0, m.mid.1, 0, 0, &mut n);

modify::<_, _, _, L>(txn, new, &mut m.modified, &mut n);

[3.21076]

[3.21204]

L::alloc_write(&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_unsized.rs at line 695

[3.21210]

let b0 = if m.modified.page.is_dirty() { 1 } else { 0 };

let b1 = if m.other.is_dirty() { 1 } else { 0 };

Ok(Op::Merged {

page: new,

freed: [m.modified.page.offset | b0, m.other.offset | b1],

marker: core::marker::PhantomData,

})

replacement in sanakirja-core/src/btree/page_unsized.rs at line 711

[3.21384]→[3.21384:21429](∅→∅),[3.21429]→[3.0:52](∅→∅),[3.52]→[3.21467:21704](∅→∅),[3.21467]→[3.21467:21704](∅→∅),[3.21784]→[3.21784:21935](∅→∅),[3.21935]→[3.2221:2300](∅→∅),[3.2300]→[3.22022:22275](∅→∅),[3.22022]→[3.22022:22275](∅→∅)

match s {

Offsets::Slice(s) => {

debug!("clone: {:?} {:?}", s, s.len());

for off in s.iter() {

let (r, off): (u64, u16) = (*off).into();

debug!("clone: {:?} {:?}", r, off);

unsafe {

let ptr = page.data.as_ptr().add(off as usize);

let size = entry_size::<K, V>(ptr);

debug!("size: {:?}", size);

let hdr = header_mut(new);

let off_new = L::alloc(hdr, size, K::ALIGN.max(V::ALIGN));

debug!("off_new: {:?}", off_new);

core::ptr::copy_nonoverlapping(ptr, new.0.data.offset(off_new as isize), size);

L::set_offset(new, *n, r, off_new);

}

*n += 1;

[3.21384]

[3.22275]

for off in s.0.iter() {

let (r, off): (u64, usize) = (*off).into();

unsafe {

let ptr = page.data.as_ptr().add(off);

let size = entry_size::<K, V>(ptr);

// Reserve the space on the page

let hdr = header_mut(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);

if hdr.is_leaf() {

hdr.incr(2 + size);

} else {

hdr.incr(8 + 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_unsized.rs at line 732

[3.22289]

core::ptr::copy_nonoverlapping(ptr, new.0.data.offset(off_new as isize), size);

replacement in sanakirja-core/src/btree/page_unsized.rs at line 734

[3.22299]→[3.22299:22308](∅→∅),[3.22308]→[3.2981:3059](∅→∅),[3.3059]→[3.22382:22584](∅→∅),[3.22382]→[3.22382:22584](∅→∅),[3.22584]→[3.4367:4414](∅→∅),[3.4414]→[3.22640:22808](∅→∅),[3.22640]→[3.22640:22808](∅→∅)

}

fn alloc<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized, L: Alloc>(

new: &mut MutPage,

k0: &K,

v0: &V,

l: u64,

r: u64,

n: &mut isize,

) {

let size = alloc_size(k0, v0);

let off_new = L::alloc_insert::<K, V>(new, n, size, r);

unsafe {

let new_ptr = new.0.data.add(off_new);

k0.write_to_page(new_ptr);

let ks = k0.size();

let v_ptr = new_ptr.add((ks + V::ALIGN - 1) & !(V::ALIGN - 1));

v0.write_to_page(v_ptr);

[3.22299]

[3.22808]

*n += 1;

edit in sanakirja-core/src/btree/page_unsized.rs at line 736

[3.22814]→[3.22814:22892](∅→∅)

if l > 0 {

L::set_right_child(new, *n - 1, l);

}

*n += 1;

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 1

[3.22926]→[3.1809:1836](∅→∅)

use super::header::header;

[3.22926]

[3.22927]

use super::cursor::*;

edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 4

[3.22942]

// The implementation here is mostly the same as in the sized case,

// except for leaves, which makes it hard to refactor.

edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 16

[3.23215]→[3.63:98](∅→∅)

debug!("rebalancing {:?}", m);

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 18

[3.23311]→[3.23311:23324](∅→∅),[3.23324]→[3.3015:3065](∅→∅)

// page.

let rc = super::PageCursor::new(&m.other, 0);

[3.23311]

[3.4725]

// page, i.e. return a middle element, and append the current

// middle element to the left page.

let rc = super::cursor::PageCursor::new(&m.other, 0);

edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 23

[3.4869]→[3.4869:4999](∅→∅)

// Extend the lifetimes of k and v.

let (k, v): (&K, &V) = unsafe { (core::mem::transmute(k), core::mem::transmute(v)) };

edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 26

[3.23715]

[3.1918]

// 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_unsized/rebalance.rs at line 35

[3.23920]→[3.1680:1698](∅→∅)

true,

[3.23920]

m.modified.skip_first,

edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 66

[3.2129]

[3.5210]

// 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_unsized/rebalance.rs at line 79

[3.24372]→[3.5345:5496](∅→∅)

let b = {

let hdr = &*header(m.other.as_page());

if hdr.is_dirty() {

1

} else {

0

}

};

[3.24372]

[3.2406]

// 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.

let k = unsafe { core::mem::transmute(k) };

let v = unsafe { core::mem::transmute(v) };

// If this frees the old "other" page, add it to the "freed"

// array.

let is_dirty = m.other.is_dirty();

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 90

[3.24722]→[3.2607:2637](∅→∅)

freed_[1] = freed | b

[3.2606]

[3.24760]

freed_[1] = if is_dirty { freed | 1 } else { freed }

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 95

[3.24851]→[3.24851:24945](∅→∅)

k: unsafe { core::mem::transmute(k) },

v: unsafe { core::mem::transmute(v) },

[3.24851]

[3.0]

k,

v,

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 102

[3.24970]→[3.24970:25027](∅→∅),[3.25027]→[3.3165:3269](∅→∅),[3.3269]→[3.25127:25144](∅→∅),[3.25127]→[3.25127:25144](∅→∅)

pub(crate) fn rebalance_right<

'a,

T: AllocPage,

K: UnsizedStorable + ?Sized + core::fmt::Debug,

V: UnsizedStorable + ?Sized + core::fmt::Debug,

L: Alloc,

>(

[3.24970]

[3.25144]

// 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.

//

// This implementation is shared with the sized one.

pub(crate) fn rebalance_right<'a, T: AllocPage, K: ?Sized, V: ?Sized, P: BTreeMutPage<K, V>>(

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 115

[3.25161]→[3.5497:5534](∅→∅)

m: Concat<'a, K, V, Page<K, V>>,

[3.25161]

[3.25203]

m: Concat<'a, K, V, P>,

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 119

[3.25320]→[3.5535:5592](∅→∅),[3.5592]→[3.5592:5676](∅→∅)

let lc = super::PageCursor::last(m.other.as_page());

let (k0, v0, r0) = <Page<K, V>>::current(txn, m.other.as_page(), &lc).unwrap();

[3.25320]

[3.25475]

let lc = P::cursor_last(&m.other);

let (k0, v0, r0) = P::current(txn, m.other.as_page(), &lc).unwrap();

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 123

[3.25516]→[3.3117:3175](∅→∅),[3.3175]→[3.5677:5748](∅→∅)

let rc = super::PageCursor::new(&m.modified.page, 0);

let rl = <Page<K, V>>::left_child(m.modified.page.as_page(), &rc);

[3.25516]

[3.25655]

let rc = P::cursor_first(&m.modified.page);

let rl = P::left_child(m.modified.page.as_page(), &rc);

edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 128

[3.25830]

[3.2638]

// Perform the modification on the modified page.

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 131

[3.5800]→[3.1843:1907](∅→∅),[3.2697]→[3.1843:1907](∅→∅)

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(

[3.5800]

[3.25958]

if let Put::Ok(Ok { page, freed }) = P::put(

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 135

[3.26036]→[3.1908:1926](∅→∅)

true,

[3.26036]

m.modified.skip_first,

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 143

[3.26188]→[3.1225:1252](∅→∅),[3.1252]→[3.5801:5855](∅→∅),[3.5855]→[3.1414:1467](∅→∅),[3.1414]→[3.1414:1467](∅→∅)

if freed > 0 {

let b = if is_dirty { 1 } else { 0 };

freed_[0] = freed | b;

}

[3.26188]

freed_[0] = if is_dirty { freed | 1 } else { freed };

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 150

[3.5907]→[3.2698:2745](∅→∅),[3.26272]→[3.2698:2745](∅→∅)

let (page, freed) = <Page<K, V>>::del(

[3.5907]

[3.2110]

let (page, freed) = P::del(

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 158

[3.1533]→[3.5908:5958](∅→∅),[3.5958]→[3.1671:1706](∅→∅),[3.1671]→[3.1671:1706](∅→∅)

let b = if is_dirty { 1 } else { 0 };

freed_[0] = freed | b;

[3.1533]

[3.1706]

freed_[0] = if is_dirty { freed | 1 } else { freed };

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 162

[3.2850]→[3.5959:6035](∅→∅)

let new_right = if let Put::Ok(Ok { freed, page }) = <Page<K, V>>::put(

[3.2850]

[3.1987]

// 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)`.

let new_right = if let Put::Ok(Ok { freed, page }) = P::put(

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 178

[3.3040]→[3.3040:3070](∅→∅)

assert_eq!(freed, 0);

[3.2144]

[3.6036]

debug_assert_eq!(freed, 0);

edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 184

[3.26559]

[3.6050]

// 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_unsized/rebalance.rs at line 189

[3.6148]→[3.6148:6299](∅→∅),[3.6299]→[3.3071:3161](∅→∅),[3.26559]→[3.3071:3161](∅→∅)

let b = {

let hdr = &*header(m.other.as_page());

if hdr.is_dirty() {

1

} else {

0

}

};

let (new_left, freed) = <Page<K, V>>::del(txn, m.other, m.other_is_mutable, &lc, 0)?;

[3.6148]

[3.3161]

let is_dirty = m.other.is_dirty();

let (new_left, freed) = P::del(txn, m.other, m.other_is_mutable, &lc, 0)?;

replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 193

[3.26764]→[3.3181:3211](∅→∅)

freed_[1] = freed | b

[3.3180]

[3.26802]

freed_[1] = if is_dirty { freed | 1 } else { freed }

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 4

[3.27039]→[3.27039:27058](∅→∅)

pub(crate) fn put<

[3.27039]

[3.27058]

pub(super) fn put<

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 9

[3.3374]→[3.27184:27198](∅→∅),[3.27184]→[3.27184:27198](∅→∅)

L: Alloc,

[3.3374]

[3.27198]

L: Alloc + AllocWrite<K, V>,

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 22

[2.1628]

[3.27397]

// Size of the new insertions, not counting the offsets.

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 29

[3.27545]

[3.3232]

// Sized occupied by the data in these insertions (not counting

// the offsets), if we need to compact the page.

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 38

[3.3495]

[3.6407]

// Number of extra offsets.

let n_ins = {

let n_ins = if k1v1.is_some() { 2 } else { 1 };

if replace {

n_ins - 1

} else {

n_ins

}

};

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 48

[3.6445]→[3.27583:27618](∅→∅),[3.2487]→[3.27583:27618](∅→∅),[3.27583]→[3.27583:27618](∅→∅),[3.27618]→[3.27618:27674](∅→∅),[3.27674]→[3.6446:6521](∅→∅),[3.6521]→[3.27757:27786](∅→∅),[3.2477]→[3.27757:27786](∅→∅),[3.2574]→[3.27757:27786](∅→∅),[3.27757]→[3.27757:27786](∅→∅)

let is_dirty = hdr.is_dirty();

debug!("put {:?} {:?} {:?}", u, mutable, is_dirty);

if mutable && is_dirty && L::can_alloc(header(page.as_page()), size) {

debug!("can alloc");

[3.6445]

[3.3496]

if mutable && page.is_dirty() && L::can_alloc(header(page.as_page()), size, n_ins) {

// First, if the page is dirty and mutable, mark it mutable.

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 52

[3.27880]

[3.3535]

// If we replace, we first need to "unlink" the previous

// value, by erasing its offset.

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 58

[3.6600]

[3.3556]

// In this case, we know we're not in a leaf, so offsets

// are of size 8.

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 67

[3.49]→[3.49:81](∅→∅)

hdr.decr(size);

[3.3967]

[3.81]

// Decreasing these figures here, we'll increase them

// again in the calls to `alloc_write` below.

hdr.decr(8 + size);

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 73

[3.4040]

[3.27880]

// Do the actual insertions.

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 75

[3.27919]→[3.27919:28045](∅→∅)

alloc::<_, _, L>(&mut page, k0, v0, 0, 0, &mut n);

alloc::<_, _, L>(&mut page, k1, v1, l, r, &mut n);

[3.27919]

[3.28045]

L::alloc_write(&mut page, k0, v0, 0, 0, &mut n);

L::alloc_write(&mut page, k1, v1, l, r, &mut n);

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 78

[3.28062]→[3.28062:28125](∅→∅)

alloc::<_, _, L>(&mut page, k0, v0, l, r, &mut n);

[3.28062]

[3.28125]

L::alloc_write(&mut page, k0, v0, l, r, &mut n);

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 80

[3.28135]

// Return: no page was freed.

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 82

[3.28178]→[3.4041:4092](∅→∅)

} else if L::can_compact(hdr, size_replaced) {

[3.28178]

[3.28228]

} else if L::can_compact(hdr, size_replaced, n_ins) {

// Allocate a new page, split the offsets at the position of

// the insertion, and each side of the split onto the new

// page, with the insertion between them.

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 87

[3.28269]→[3.28269:28311](∅→∅)

debug!("can compact: {:?}", new);

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 88

[3.28371]

// Clone the leftmost child.

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 91

[3.28439]→[3.6601:6658](∅→∅)

let s = L::offset_slice::<K, V>(page.as_page());

[3.28439]

[3.28496]

// Split the offsets.

let s = L::offset_slice(page.as_page());

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 95

[3.28543]

[3.4093]

// Drop the first element of `s1` if we're replacing it.

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 97

[3.4155]

[3.28543]

// Finally, clone and insert.

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 102

[3.28669]→[3.2383:2507](∅→∅)

alloc::<_, _, L>(&mut new, k0, v0, 0, l, &mut n);

alloc::<_, _, L>(&mut new, k1, v1, 0, r, &mut n);

[3.28669]

[3.28793]

L::alloc_write(&mut new, k0, v0, 0, l, &mut n);

L::alloc_write(&mut new, k1, v1, 0, r, &mut n);

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 105

[3.28810]→[3.28810:28872](∅→∅)

alloc::<_, _, L>(&mut new, k0, v0, l, r, &mut n);

[3.28810]

[3.28872]

L::alloc_write(&mut new, k0, v0, l, r, &mut n);

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 109

[3.28947]→[3.28947:29025](∅→∅)

let b0 = if is_dirty { 1 } else { 0 };

return Ok(Put::Ok(Ok {

[3.54]

[3.29025]

// And return, freeing the old version of the page.

Ok(Put::Ok(Ok {

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 112

[3.29048]→[3.29048:29098](∅→∅)

freed: page.offset | b0,

}));

[3.29048]

[3.29098]

freed: page.offset | if page.is_dirty() { 1 } else { 0 },

}))

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 115

[3.29111]→[3.29111:29136](∅→∅),[3.29136]→[3.6789:6886](∅→∅)

debug!("split");

return split_unsized::<_, _, _, L>(txn, page.as_page(), replace, u, k0, v0, k1v1, l, r);

[3.29111]

[3.29224]

split_unsized::<_, _, _, L>(txn, page, replace, u, k0, v0, k1v1, l, r)

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 119

[3.29233]

// Surprisingly, the following function is simpler than in the sized

// case, because we can't be too efficient in this case, since we have

// to go through all the elements linearly anyway to get their sizes.

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 127

[3.3479]→[3.29377:29391](∅→∅),[3.29377]→[3.29377:29391](∅→∅)

L: Alloc,

[3.3479]

[3.29391]

L: Alloc + AllocWrite<K, V>,

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 130

[3.29411]→[3.29411:29434](∅→∅)

page: crate::Page,

[3.29411]

[3.4254]

page: CowPage,

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 139

[2.1687]→[3.3235:3264](∅→∅),[3.29577]→[3.3235:3264](∅→∅),[3.3264]→[3.29577:29605](∅→∅),[3.29577]→[3.29577:29605](∅→∅),[3.29605]→[3.29605:29628](∅→∅)

debug!("split_unsized");

let hdr = header(page);

let n0 = hdr.n();

[2.1687]

[3.29628]

let hdr = header(page.as_page());

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 146

[3.29822]→[3.29822:29878](∅→∅)

let left_child = header(page).left_page() & !0xfff;

[3.29822]

[3.29878]

// Clone the leftmost child. If we're inserting at position 0,

// this means this leftmost child must, and will be replaced.

let left_child = hdr.left_page() & !0xfff;

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 151

[3.29930]→[3.29930:29990](∅→∅)

let mut split = (core::ptr::null(), core::ptr::null());

[3.29930]

[3.29990]

// Pointer to the split key and value.

let mut split = None;

// We start filling the left page, and we will change to filling

// the right page when the left one is at least half-full.

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 158

[3.30029]

// There are two synchronised counters here: `hdr.n()` and

// `n`. The reason for this is that operations on `hdr.n()` are

// somewhat cumbersome, as they might involve extra operations to

// convert to/from the little-endian encoding of `hdr.n()`.

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 163

[3.30048]→[3.30048:30069](∅→∅),[3.30069]→[3.551:649](∅→∅),[3.649]→[3.30203:30210](∅→∅),[3.30203]→[3.30203:30210](∅→∅)

let s = unsafe {

core::slice::from_raw_parts(page.data.as_ptr().add(HDR) as *const L::Offset, n0 as usize)

};

[3.30048]

[3.30210]

let s = L::offset_slice(page.as_page());

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 165

[3.30235]→[3.30235:30307](∅→∅)

let mut is_left = true;

for (uu, off) in s.iter().enumerate() {

[3.30235]

[3.255]

for (uu, off) in s.0.iter().enumerate() {

// If the current position of the cursor is the insertion,

// (i.e. `uu == u`), insert.

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 169

[3.276]

// The following is tricky and makes assumptions on the

// rest of the code. If we are inserting two elements

// (i.e. if `k1v1.is_some()`), this means we're replacing

// one on the page.

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 174

[3.319]→[3.319:587](∅→∅),[3.587]→[3.587:608](∅→∅),[3.608]→[3.608:743](∅→∅),[3.743]→[3.743:757](∅→∅),[3.757]→[3.3265:3290](∅→∅)

alloc::<K, V, L>(current_page, k0, v0, 0, l0, &mut n);

total += alloc_size(k0, v0) + L::extra_size();

alloc::<K, V, L>(current_page, k1, v1, 0, r0, &mut n);

total += alloc_size(k1, v1) + L::extra_size();

} else {

alloc::<K, V, L>(current_page, k0, v0, l0, r0, &mut n);

total += alloc_size(k0, v0) + L::extra_size();

}

if replace {

[3.319]

[3.3290]

// As explained in the documentation for `put` in the

// definition of `BTreeMutPage`, `l0` and `r0` are the

// left and right children of k1v1, since this means

// the right child of a deleted entry has split, and

// we must replace the deleted entry with `(k0, v0)`.

L::alloc_write(current_page, k0, v0, 0, l0, &mut n);

total += alloc_size(k0, v0) + L::OFFSET_SIZE;

L::alloc_write(current_page, k1, v1, 0, r0, &mut n);

total += alloc_size(k1, v1) + L::OFFSET_SIZE;

// Replacing the next element:

debug_assert!(replace);

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 187

[3.3316]

} else {

L::alloc_write(current_page, k0, v0, l0, r0, &mut n);

total += alloc_size(k0, v0) + L::OFFSET_SIZE;

if replace {

continue;

}

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 195

[3.4327]→[3.30307:30357](∅→∅),[3.768]→[3.30307:30357](∅→∅),[3.30307]→[3.30307:30357](∅→∅)

let (r, off): (u64, u16) = (*off).into();

[3.4327]

[3.832]

// Then, i.e. either if we're not at the position of an

// insertion, or else if we're not replacing the current

// position, just copy the current entry to the appropriate

// page (left or right).

let (r, off): (u64, usize) = (*off).into();

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 202

[3.30374]→[3.30374:30434](∅→∅)

let ptr = page.data.as_ptr().add(off as usize);

[3.30374]

[3.0]

let ptr = page.data.add(off);

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 204

[3.93]→[3.30535:30619](∅→∅),[3.30535]→[3.30535:30619](∅→∅),[3.30619]→[3.30619:30670](∅→∅)

if is_left && total >= PAGE_SIZE / 2 {

is_left = false;

split = read::<T, K, V>(txn, ptr);

[3.48]

[3.30670]

// If the left side of the split is at least half-full, we

// know that we can do all the insertions we need on the

// right-hand side (even if there are two of them, and the

// replaced value is of size 0), so we switch.

if split.is_none() && total >= PAGE_SIZE / 2 {

// Don't write the next entry onto any page, keep it

// as the split entry.

let (k, v) = read::<T, K, V>(txn, ptr);

split = Some((K::from_raw_ptr(txn, k), V::from_raw_ptr(txn, v)));

// Set the entry count for the current page, before

// switching and resetting the counter.

header_mut(current_page).set_n(n as u16);

// And set the leftmost child of the right page to

// `r`.

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 221

[3.30725]

// Then, switch page and reset the counter.

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 226

[3.30812]→[3.2588:2684](∅→∅)

let off_new = L::alloc(header_mut(current_page), size, K::ALIGN.max(V::ALIGN));

[3.30812]

[3.30916]

// Else, we're simply allocating a new entry on the

// current page.

let off_new = {

let hdr = header_mut(current_page);

let data = hdr.data();

assert!(

HDR + hdr.n() as usize * L::OFFSET_SIZE + L::OFFSET_SIZE + size

< data as usize

);

// Move the data pointer `size` bytes to the left.

hdr.set_data(data - size as u16);

// And increase the number of entries, and

// occupied size of the page.

hdr.incr(size + L::OFFSET_SIZE);

data - size as u16

};

// Copy the entry.

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 248

[3.31100]→[3.31100:31160](∅→∅)

L::set_offset(current_page, n, r, off_new);

[3.31100]

[3.31160]

// And set the offset.

L::set_offset(current_page, n, r | (off_new as u64));

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 252

[3.31198]→[3.1781:1826](∅→∅)

total += size + L::extra_size();

[3.31198]

total += size + L::OFFSET_SIZE;

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 255

[3.867]→[3.867:889](∅→∅)

if u == s.len() {

[3.867]

[3.889]

header_mut(current_page).set_n(n as u16);

// Finally, it is possible that we haven't had a chance to do the

// insertions yet: this is the case iff we're inserting at the end

// of all the entries, so handle this now.

if u == s.0.len() {

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 262

[3.928]→[3.928:1062](∅→∅)

alloc::<K, V, L>(current_page, k0, v0, 0, l0, &mut n);

alloc::<K, V, L>(current_page, k1, v1, 0, r0, &mut n);

[3.928]

[3.1062]

L::alloc_write(current_page, k0, v0, 0, l0, &mut n);

L::alloc_write(current_page, k1, v1, 0, r0, &mut n);

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 265

[3.1079]→[3.1079:1147](∅→∅)

alloc::<K, V, L>(current_page, k0, v0, l0, r0, &mut n);

[3.1079]

[3.31734]

L::alloc_write(current_page, k0, v0, l0, r0, &mut n);

edit in sanakirja-core/src/btree/page_unsized/put.rs at line 268

[3.31750]

[3.31783]

let (split_key, split_value) = split.unwrap();

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 270

[3.31803]→[3.31803:31927](∅→∅)

split_key: unsafe { K::from_raw_ptr(txn, split.0) },

split_value: unsafe { V::from_raw_ptr(txn, split.1) },

[3.31803]

[3.31927]

split_key,

split_value,

replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 274

[3.31956]→[3.31956:31991](∅→∅)

freed: if hdr.is_dirty() {

[3.31956]

[3.31991]

freed: if page.is_dirty() {

replacement in sanakirja-core/src/btree/page_unsized/header.rs at line 13

[3.15630]→[3.15630:15659](∅→∅)

pub fn init(&mut self) {

[3.15630]

[2.1688]

pub(crate) fn init(&mut self) {

replacement in sanakirja-core/src/btree/page_unsized/header.rs at line 20

[3.15801]→[3.15801:15830](∅→∅)

pub fn n(&self) -> u16 {

[3.15801]

[3.2642]

pub(crate) fn n(&self) -> u16 {

replacement in sanakirja-core/src/btree/page_unsized/header.rs at line 24

[3.15871]→[3.15871:15909](∅→∅)

pub fn set_n(&mut self, n: u16) {

[3.15871]

[3.2672]

pub(crate) fn set_n(&mut self, n: u16) {

edit in sanakirja-core/src/btree/page_unsized/header.rs at line 28

[3.16006]→[3.16006:16043](∅→∅),[3.16043]→[3.2701:2742](∅→∅),[3.2742]→[3.16081:16088](∅→∅),[3.16081]→[3.16081:16088](∅→∅)

pub fn is_dirty(&self) -> bool {

u16::from_le(self.data) & 1 != 0

}

edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 4

[3.33838]

/// We'd love to share this trait with the sized implementation, but

/// unfortunately, the type parameters of almost all methods are

/// different.

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 8

[3.33863]→[3.2945:2975](∅→∅)

fn extra_size() -> usize;

[3.33863]

[3.3480]

const OFFSET_SIZE: usize;

/// Size (including the offset size) of the entry at position

/// `cur`.

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 16

[3.4466]→[3.2975:3028](∅→∅),[3.2975]→[3.2975:3028](∅→∅),[3.3028]→[3.4467:4522](∅→∅),[3.4522]→[3.3083:3149](∅→∅),[3.3083]→[3.3083:3149](∅→∅)

fn can_alloc(hdr: &Header, size: usize) -> bool;

fn can_compact(hdr: &Header, size: isize) -> bool;

fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16;

[3.4466]

[3.34279]

/// Can we allocate an entry of `size` bytes, where `size` doesn't

/// include the offset bytes?

fn can_alloc(hdr: &Header, size: usize, n: usize) -> bool {

(HDR as usize) + (hdr.n() as usize) * Self::OFFSET_SIZE + n * Self::OFFSET_SIZE + size

<= hdr.data() as usize

}

/// If we cloned the page, could we allocate an entry of `size`

/// bytes, where `size` doesn't include the offset bytes?

fn can_compact(hdr: &Header, size: isize, n: usize) -> bool {

(HDR as isize)

+ (hdr.n() as isize) * Self::OFFSET_SIZE as isize

+ ((hdr.left_page() & 0xfff) as isize)

+ (n * Self::OFFSET_SIZE) as isize

+ size

<= PAGE_SIZE as isize

}

/// 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.

fn set_right_child(_new: &mut MutPage, _n: isize, _r: u64) {}

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 39

[3.34280]→[3.34280:34317](∅→∅),[3.34317]→[3.3560:3643](∅→∅),[3.3643]→[3.34396:34413](∅→∅),[3.34396]→[3.34396:34413](∅→∅),[3.34413]→[3.34413:34498](∅→∅)

// n = number of items to remove

fn truncate_left<T, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

txn: &T,

page: &mut MutPage,

n: usize,

) -> Option<(*const K, *const V)>;

[3.34280]

[3.34498]

/// Set the n^th offset on the page to `r`, which encodes a page

/// offset in its 52 MSBs, and an offset on the page in its 12 LSBs.

fn set_offset(new: &mut MutPage, n: isize, r: u64);

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 43

[3.34499]→[3.3644:3723](∅→∅),[3.3723]→[3.34574:34865](∅→∅),[3.34574]→[3.34574:34865](∅→∅),[3.34865]→[3.3724:3807](∅→∅),[3.3807]→[3.34944:35011](∅→∅),[3.34944]→[3.34944:35011](∅→∅),[3.35011]→[3.3808:3894](∅→∅),[3.3894]→[3.35083:35100](∅→∅),[3.3015]→[3.35083:35100](∅→∅),[3.35083]→[3.35083:35100](∅→∅),[3.35100]→[3.35100:35182](∅→∅)

fn alloc_insert<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

new: &mut MutPage,

n: &mut isize,

size: usize,

r: u64,

) -> usize;

fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16);

fn set_right_child(new: &mut MutPage, n: isize, r: u64);

type Offset: Into<(u64, u16)> + Copy + core::fmt::Debug;

fn offset_slice<'a, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

page: crate::Page<'a>,

) -> Offsets<'a, Self::Offset>;

fn kv<'a, T: LoadPage, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

txn: &T,

page: crate::Page,

off: (u64, u16),

) -> (&'a K, &'a V, u64);

[3.34499]

[3.35182]

/// The type of offsets, u64 in internal nodes, u16 in leaves.

type Offset: Into<(u64, usize)> + Copy;

fn offset_slice<'a>(page: crate::Page<'a>) -> Offsets<'a, Self::Offset>;

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 49

[3.35185]→[3.35185:35257](∅→∅)

#[derive(Debug, Clone)]

pub enum Offsets<'a, A> {

Slice(&'a [A]),

}

[3.35185]

[3.35257]

#[derive(Debug, Clone, Copy)]

pub struct Offsets<'a, A>(pub &'a [A]);

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 52

[3.35258]→[3.35258:35776](∅→∅)

impl<'a, A: Into<(u64, u16)> + Copy> Offsets<'a, A> {

pub fn split_at(&self, mid: usize) -> (Self, Self) {

match self {

Offsets::Slice(s) if mid < s.len() => {

debug!("split_at: {:?} {:?}", s.len(), mid);

let (a, b) = s.split_at(mid);

(Offsets::Slice(a), Offsets::Slice(b))

}

Offsets::Slice(s) => {

debug_assert_eq!(mid, s.len());

(Offsets::Slice(s), Offsets::Slice(&[][..]))

}

[3.35258]

[3.35776]

impl<'a, A: Copy> Offsets<'a, A> {

pub fn split_at(self, mid: usize) -> (Self, Self) {

if mid < self.0.len() {

let (a, b) = self.0.split_at(mid);

(Offsets(a), Offsets(b))

} else {

debug_assert_eq!(mid, self.0.len());

(self, Offsets(&[][..]))

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 68

[3.35860]→[3.3150:3181](∅→∅),[3.3181]→[3.35945:35961](∅→∅),[3.35945]→[3.35945:35961](∅→∅)

fn extra_size() -> usize {

2

}

[3.35860]

[3.3895]

const OFFSET_SIZE: usize = 2;

// Note: the size returned by this function includes the offset.

edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 75

[3.4662]

// Find the offset of the current position, get its size.

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 77

[3.4679]→[3.4679:4850](∅→∅)

2 + entry_size::<K, V>(page.data.as_ptr().add(u16::from_le(

*(page.data.as_ptr().add(HDR) as *const u16).offset(cur),

) as usize))

[3.4679]

[3.4850]

debug_assert!(cur >= 0);

let off = *(page.data.as_ptr().add(HDR + 2 * cur as usize) as *const u16);

Self::OFFSET_SIZE

+ entry_size::<K, V>(page.data.as_ptr().add(u16::from_le(off) as usize))

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 84

[3.4867]→[3.3182:3236](∅→∅),[3.35961]→[3.3182:3236](∅→∅),[3.3236]→[3.1396:1558](∅→∅),[3.1558]→[3.1558:1640](∅→∅),[3.1640]→[3.36212:36218](∅→∅),[3.3317]→[3.36212:36218](∅→∅),[3.36212]→[3.36212:36218](∅→∅),[3.36218]→[3.4868:4924](∅→∅),[3.4924]→[3.3374:3390](∅→∅),[3.3374]→[3.3374:3390](∅→∅),[3.3390]→[3.1641:1690](∅→∅),[3.1690]→[3.3443:3525](∅→∅),[3.3443]→[3.3443:3525](∅→∅),[3.3525]→[3.4925:5057](∅→∅),[3.5057]→[3.36463:36469](∅→∅),[3.3643]→[3.36463:36469](∅→∅),[3.3041]→[3.36463:36469](∅→∅),[3.36463]→[3.36463:36469](∅→∅),[3.36469]→[3.3975:4058](∅→∅),[3.4058]→[3.36548:36566](∅→∅),[3.36548]→[3.36548:36566](∅→∅),[3.36566]→[3.36566:36746](∅→∅)

fn can_alloc(hdr: &Header, size: usize) -> bool {

debug!(

"can_alloc, leaf: {:?} {:?} {:?} {:?}",

HDR,

hdr.n() * 2,

hdr.data(),

size

);

(HDR as usize) + (hdr.n() as usize) * 2 + 2 + size <= hdr.data() as usize

}

fn can_compact(hdr: &Header, size: isize) -> bool {

debug!(

"can_compact, leaf: {:?} {:?} {:?}",

HDR,

hdr.left_page() & 0xfff,

size

);

(HDR as isize) + (hdr.n() as isize) * 2 + ((hdr.left_page() & 0xfff) as isize) + 2 + size

<= PAGE_SIZE as isize

}

fn truncate_left<T, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

_txn: &T,

page: &mut MutPage,

n: usize,

) -> Option<(*const K, *const V)> {

debug!("truncate_left {:?} {:?}", page, n);

let hdr_n = header_mut(page).n();

[3.4867]

[3.36746]

fn set_offset(new: &mut MutPage, n: isize, off: u64) {

edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 86

[3.36763]→[3.36763:36943](∅→∅),[3.36943]→[3.3644:3774](∅→∅),[3.3774]→[3.37081:37149](∅→∅),[3.37081]→[3.37081:37149](∅→∅),[3.37149]→[3.3775:3872](∅→∅),[3.3872]→[3.37278:37431](∅→∅),[3.37278]→[3.37278:37431](∅→∅),[3.37431]→[3.3873:4008](∅→∅),[3.4008]→[3.1796:1868](∅→∅),[3.1868]→[3.4008:4050](∅→∅),[3.4008]→[3.4008:4050](∅→∅),[3.4050]→[3.37719:37751](∅→∅),[3.37719]→[3.37719:37751](∅→∅),[3.37751]→[3.4051:4102](∅→∅),[3.4102]→[3.37817:37823](∅→∅),[3.37817]→[3.37817:37823](∅→∅),[3.37823]→[3.4059:4138](∅→∅),[3.4138]→[3.37898:38113](∅→∅),[3.37898]→[3.37898:38113](∅→∅),[3.38113]→[3.4103:4173](∅→∅),[3.4173]→[3.38191:38259](∅→∅),[3.38191]→[3.38191:38259](∅→∅),[3.38259]→[3.38259:38276](∅→∅),[3.38276]→[3.38276:38664](∅→∅)

core::ptr::copy(

page.0.data.add(HDR + n * 2),

page.0.data.add(HDR),

(hdr_n as usize - n) * 2,

);

}

let deleted_offsets =

unsafe { core::slice::from_raw_parts(page.0.data.add(HDR) as *const u16, n as usize) };

let deleted_size: u64 = deleted_offsets

.iter()

.map(|&off| 2 + unsafe { entry_size::<K, V>(page.0.data.add(off as usize)) } as u64)

.sum();

let hdr = header_mut(page);

hdr.set_n(hdr_n - n as u16);

hdr.decr(deleted_size as usize);

None

}

fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {

assert_eq!(size % align, 0);

let data = hdr.data();

assert!(HDR + hdr.n() as usize * 2 + 2 + size < data as usize);

hdr.set_data(data - size as u16);

hdr.set_n(hdr.n() + 1);

hdr.incr(size);

data - size as u16

}

fn alloc_insert<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

new: &mut MutPage,

n: &mut isize,

size: usize,

_: u64,

) -> usize {

let (hdr_n, off_new) = {

let hdr = header_mut(new);

(

hdr.n(),

Self::alloc(&mut *hdr, size, K::ALIGN.max(V::ALIGN)),

)

};

// Making space for the new offset

unsafe {

core::ptr::copy(

new.0.data.add(HDR + (*n as usize) * 2),

new.0.data.add(HDR + (*n as usize) * 2 + 2),

(hdr_n as usize - (*n as usize)) * 2,

);

}

Self::set_offset(new, *n, 0, off_new);

off_new as usize

}

fn set_offset(new: &mut MutPage, n: isize, _: u64, off: u16) {

unsafe {

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 87

[3.38739]→[3.38739:38771](∅→∅)

*ptr = off.to_le();

[3.38739]

[3.38771]

*ptr = (off as u16).to_le();

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 90

[3.38787]→[3.38787:38848](∅→∅)

fn set_right_child(_: &mut MutPage, _: isize, _: u64) {}

[3.38787]

[3.38848]

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 93

[3.38879]→[3.4139:4222](∅→∅),[3.4222]→[3.38958:39058](∅→∅),[3.38958]→[3.38958:39058](∅→∅)

fn offset_slice<'a, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

page: crate::Page<'a>,

) -> Offsets<'a, Self::Offset> {

let hdr = header(page);

[3.38879]

[3.39058]

fn offset_slice<'a>(page: crate::Page<'a>) -> Offsets<'a, Self::Offset> {

let hdr_n = header(page).n();

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 96

[3.39075]→[3.39075:39131](∅→∅)

Offsets::Slice(core::slice::from_raw_parts(

[3.39075]

[3.39131]

Offsets(core::slice::from_raw_parts(

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 98

[3.39197]→[3.39197:39231](∅→∅)

hdr.n() as usize,

[3.39197]

[3.39231]

hdr_n as usize,

edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 102

[3.39262]→[3.4223:4309](∅→∅),[3.4309]→[3.39334:39351](∅→∅),[3.3124]→[3.39334:39351](∅→∅),[3.39334]→[3.39334:39351](∅→∅),[3.39351]→[3.39351:39456](∅→∅),[3.39456]→[3.39456:39607](∅→∅),[3.39607]→[3.39607:39623](∅→∅)

fn kv<'a, T: LoadPage, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

txn: &T,

page: crate::Page,

(_, off): (u64, u16),

) -> (&'a K, &'a V, u64) {

unsafe {

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off as usize));

(K::from_raw_ptr(txn, k), V::from_raw_ptr(txn, v), 0)

}

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 105

[3.39652]→[3.4174:4205](∅→∅),[3.4205]→[3.39737:39747](∅→∅),[3.39737]→[3.39737:39747](∅→∅),[3.39747]→[3.5058:5064](∅→∅)

fn extra_size() -> usize {

8

}

[3.39652]

[3.4310]

const OFFSET_SIZE: usize = 8;

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 118

[3.5433]→[3.4206:4260](∅→∅),[3.39753]→[3.4206:4260](∅→∅),[3.4260]→[3.1869:2117](∅→∅),[3.2117]→[3.39942:39948](∅→∅),[3.39942]→[3.39942:39948](∅→∅),[3.39948]→[3.5434:5490](∅→∅),[3.5490]→[3.4317:4468](∅→∅),[3.4317]→[3.4317:4468](∅→∅),[3.4468]→[3.5491:5623](∅→∅),[3.5623]→[3.40203:40209](∅→∅),[3.4586]→[3.40203:40209](∅→∅),[3.3150]→[3.40203:40209](∅→∅),[3.40203]→[3.40203:40209](∅→∅),[3.40209]→[3.4587:4588](∅→∅),[3.4588]→[3.4390:4473](∅→∅),[3.4473]→[3.40288:40306](∅→∅),[3.40288]→[3.40288:40306](∅→∅),[3.40306]→[3.40306:40543](∅→∅)

fn can_alloc(hdr: &Header, size: usize) -> bool {

debug!(

"can_alloc, internal: {:?} {:?} {:?} {:?}",

HDR,

hdr.n() * 8,

hdr.data(),

size

);

(HDR as usize) + (hdr.n() as usize) * 8 + 8 + size <= hdr.data() as usize

}

fn can_compact(hdr: &Header, size: isize) -> bool {

debug!(

"can_compact, internal: {:?} {:?} {:?}",

HDR,

hdr.left_page() & 0xfff,

size

);

(HDR as isize) + (hdr.n() as isize) * 8 + ((hdr.left_page() & 0xfff) as isize) + 8 + size

<= PAGE_SIZE as isize

}

fn truncate_left<T, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

_txn: &T,

page: &mut MutPage,

n: usize,

) -> Option<(*const K, *const V)> {

// The following line copies the left child of the last entry

// (hence the `- 8` and `- 1`)

let hdr_n = header_mut(page).n();

[3.5433]

[3.40543]

/// 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_unsized/alloc.rs at line 122

[3.40560]→[3.40560:40744](∅→∅)

core::ptr::copy(

page.0.data.add(HDR + (n - 1) * 8),

page.0.data.add(HDR - 8),

(hdr_n as usize - n + 1) * 8,

);

[3.40560]

[3.40744]

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_unsized/alloc.rs at line 127

[3.40754]→[3.40754:41045](∅→∅),[3.41045]→[3.4589:4690](∅→∅),[3.4690]→[3.41186:41410](∅→∅),[3.41186]→[3.41186:41410](∅→∅),[3.41410]→[3.4691:4826](∅→∅),[3.4826]→[3.2118:2191](∅→∅),[3.2191]→[3.4826:4868](∅→∅),[3.4826]→[3.4826:4868](∅→∅),[3.4868]→[3.41643:41675](∅→∅),[3.41643]→[3.41643:41675](∅→∅),[3.41675]→[3.4869:4920](∅→∅),[3.4920]→[3.41741:41747](∅→∅),[3.41741]→[3.41741:41747](∅→∅),[3.41747]→[3.4474:4553](∅→∅),[3.4553]→[3.41822:42037](∅→∅),[3.41822]→[3.41822:42037](∅→∅),[3.42037]→[3.4921:4991](∅→∅),[3.4991]→[3.42115:42140](∅→∅),[3.42115]→[3.42115:42140](∅→∅),[3.42140]→[3.42140:42157](∅→∅),[3.42157]→[3.42157:42373](∅→∅),[3.42373]→[3.42373:42383](∅→∅),[3.42383]→[3.42383:42455](∅→∅)

let size = {

let offsets = unsafe {

core::slice::from_raw_parts(

page.0.data.add(HDR + n * 8) as *const u16,

hdr_n as usize - n as usize,

)

};

offsets

.iter()

.map(|&off| 8 + unsafe { entry_size::<K, V>(page.0.data.add(off as usize)) } as u64)

.sum()

};

let hdr = header_mut(page);

hdr.set_n(hdr_n - n as u16);

debug!("truncate_left {:?} {:?}", hdr.left_page(), size);

hdr.set_occupied(size);

None

}

fn alloc(hdr: &mut Header, size: usize, align: usize) -> u16 {

assert_eq!(size % align, 0);

let data = hdr.data();

assert!(HDR + hdr.n() as usize * 8 + 8 + size <= data as usize);

hdr.set_data(data - size as u16);

hdr.set_n(hdr.n() + 1);

hdr.incr(size);

data - size as u16

}

fn alloc_insert<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

new: &mut MutPage,

n: &mut isize,

size: usize,

r: u64,

) -> usize {

let (hdr_n, off_new) = {

let hdr = header_mut(new);

(

hdr.n(),

Self::alloc(&mut *hdr, size, K::ALIGN.max(V::ALIGN)),

)

};

unsafe {

core::ptr::copy(

new.0.data.add(HDR + (*n as usize) * 8),

new.0.data.add(HDR + (*n as usize) * 8 + 8),

(hdr_n as usize - (*n as usize)) * 8,

);

}

Self::set_offset(new, *n, r, off_new);

off_new as usize

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 128

[3.42461]→[3.42461:42528](∅→∅)

fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16) {

[3.42461]

[3.42528]

fn set_offset(new: &mut MutPage, n: isize, off: u64) {

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 132

[3.42620]→[3.42620:42665](∅→∅)

*ptr = (r | off as u64).to_le();

[3.42620]

[3.42665]

*ptr = off.to_le();

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 135

[3.42681]→[3.42681:42948](∅→∅)

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();

}

[3.42681]

[3.42948]

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 138

[3.42983]→[3.4554:4637](∅→∅),[3.4637]→[3.43062:43162](∅→∅),[3.43062]→[3.43062:43162](∅→∅),[3.43162]→[3.2192:2250](∅→∅)

fn offset_slice<'a, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

page: crate::Page<'a>,

) -> Offsets<'a, Self::Offset> {

let hdr = header(page);

debug!("internal page {:?} {:?}", page, hdr.n());

[3.42983]

[3.43162]

fn offset_slice<'a>(page: crate::Page<'a>) -> Offsets<'a, Self::Offset> {

let hdr_n = header(page).n() as usize;

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 141

[3.43179]→[3.43179:43235](∅→∅)

Offsets::Slice(core::slice::from_raw_parts(

[3.43179]

[3.43235]

Offsets(core::slice::from_raw_parts(

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 143

[3.43305]→[3.43305:43339](∅→∅)

hdr.n() as usize,

[3.43305]

[3.43339]

hdr_n,

edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 145

[3.43354]→[3.43354:43370](∅→∅),[3.43370]→[3.4638:4724](∅→∅),[3.4724]→[3.43442:43459](∅→∅),[3.3233]→[3.43442:43459](∅→∅),[3.43442]→[3.43442:43459](∅→∅),[3.43459]→[3.43459:43564](∅→∅),[3.43564]→[3.43564:43715](∅→∅)

}

fn kv<'a, T: LoadPage, K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized>(

txn: &T,

page: crate::Page,

(r, off): (u64, u16),

) -> (&'a K, &'a V, u64) {

unsafe {

let (k, v) = read::<T, K, V>(txn, page.data.as_ptr().add(off as usize));

(K::from_raw_ptr(txn, k), V::from_raw_ptr(txn, v), r)

edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 148

[3.43733]

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 153

[3.43803]→[3.43803:43896](∅→∅)

impl Into<(u64, u16)> for LeafOffset {

fn into(self) -> (u64, u16) {

(0, self.0)

[3.43803]

[3.43896]

impl Into<(u64, usize)> for LeafOffset {

fn into(self) -> (u64, usize) {

(0, self.0 as usize)

replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 169

[3.44075]→[3.44075:44203](∅→∅)

impl Into<(u64, u16)> for InternalOffset {

fn into(self) -> (u64, u16) {

(self.0 & !0xfff, (self.0 & 0xfff) as u16)

[3.44075]

[3.44203]

impl Into<(u64, usize)> for InternalOffset {

fn into(self) -> (u64, usize) {

(self.0 & !0xfff, (self.0 & 0xfff) as usize)

edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 178

[3.44303]

}

impl<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized> AllocWrite<K, V> for Leaf {

fn alloc_write(new: &mut MutPage, k0: &K, v0: &V, l: u64, r: u64, n: &mut isize) {

alloc_write::<K, V, Self>(new, k0, v0, l, r, n)

}

impl<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized> AllocWrite<K, V> for Internal {

fn alloc_write(new: &mut MutPage, k0: &K, v0: &V, l: u64, r: u64, n: &mut isize) {

alloc_write::<K, V, Self>(new, k0, v0, l, r, n)

}

// Allocate a new entry and copy (k0, v0) into the new slot.

fn alloc_write<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized, L: Alloc>(

new: &mut MutPage,

k0: &K,

v0: &V,

l: u64,

r: u64,

n: &mut isize,

) {

let size = alloc_size(k0, v0);

let off_new = alloc_insert::<K, V, L>(new, n, size, r);

unsafe {

let new_ptr = new.0.data.add(off_new);

k0.write_to_page(new_ptr);

let ks = k0.size();

let v_ptr = new_ptr.add((ks + V::ALIGN - 1) & !(V::ALIGN - 1));

v0.write_to_page(v_ptr);

}

if l > 0 {

L::set_right_child(new, *n - 1, l);

}

*n += 1;

}

/// Reserve space on the page for `size` bytes of data (i.e. not

/// counting the offset), set the right child of the new position

/// to `r`, add the offset to the new data to the offset array,

/// and return the new offset.

fn alloc_insert<K: UnsizedStorable + ?Sized, V: UnsizedStorable + ?Sized, L: Alloc>(

new: &mut MutPage,

n: &mut isize,

size: usize,

r: u64,

) -> usize {

let hdr = header_mut(new);

let data = hdr.data();

// If we're here, the following assertion has been checked by the

// `can_alloc` method.

debug_assert!(HDR + (hdr.n() as usize + 1) * L::OFFSET_SIZE + size <= data as usize);

hdr.set_data(data - size as u16);

hdr.set_n(hdr.n() + 1);

hdr.incr(L::OFFSET_SIZE + size);

let off_new = data - size as u16;

let hdr_n = hdr.n();

// Making space for the new offset

unsafe {

core::ptr::copy(

new.0.data.add(HDR + (*n as usize) * L::OFFSET_SIZE),

new.0

.data

.add(HDR + (*n as usize) * L::OFFSET_SIZE + L::OFFSET_SIZE),

(hdr_n as usize - (*n as usize)) * L::OFFSET_SIZE,

);

edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 248

[3.44309]

L::set_offset(new, *n, r | (off_new as u64));

off_new as usize

replacement in sanakirja-core/src/btree/page.rs at line 3

[2.2023]→[2.2023:2052](∅→∅)

//! `core::mem::size_of()`).

[2.2023]

[2.2052]

//! [`core::mem::size_of()`]).

replacement in sanakirja-core/src/btree/page.rs at line 53

[2.3957]→[2.3957:4094](∅→∅)

//! 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

[2.3957]

[2.4094]

//! 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

replacement in sanakirja-core/src/btree/page.rs at line 79

[2.4901]→[2.4901:4948](∅→∅)

use super::page_unsized::{header, PageCursor};

[2.4901]

[3.20]

use super::page_unsized::{cursor::PageCursor, header};

replacement in sanakirja-core/src/btree/page.rs at line 98

[3.8700]→[3.498:554](∅→∅)

pub struct Page<K, V>(super::page_unsized::Page<K, V>);

[3.8700]

[3.2145]

pub struct Page<K, V> {

k: core::marker::PhantomData<K>,

v: core::marker::PhantomData<V>,

}

edit in sanakirja-core/src/btree/page.rs at line 141

[2.5728]→[3.3963:3969](∅→∅),[3.3963]→[3.3963:3969](∅→∅),[3.3969]→[3.3969:3970](∅→∅),[3.3970]→[3.5161:5230](∅→∅),[3.5230]→[3.4038:4095](∅→∅),[3.4038]→[3.4038:4095](∅→∅),[3.4095]→[3.5231:5371](∅→∅),[3.5371]→[3.4436:4446](∅→∅),[3.4436]→[3.4436:4446](∅→∅)

}

fn current_size(_page: crate::Page, c: &Self::Cursor) -> usize {

assert!(c.cur >= 0 && c.cur < c.total as isize);

if c.is_leaf {

core::mem::size_of::<Tuple<K, V>>()

} else {

8 + core::mem::size_of::<Tuple<K, V>>()

}

replacement in sanakirja-core/src/btree/page.rs at line 256

[2.9106]→[3.5690:5745](∅→∅),[3.5690]→[3.5690:5745](∅→∅),[3.5745]→[2.9107:9134](∅→∅)

let lookup = lookup(txn, page, c, k0, v0);

match lookup {

[2.9106]

[3.5804]

match lookup(txn, page, c, k0, v0) {

edit in sanakirja-core/src/btree/page.rs at line 335

[3.4878]

[3.1824]

// In the sized case, deletions can never cause a split, so we

// never have to insert two elements at the same position.

assert!(k1v1.is_none());

replacement in sanakirja-core/src/btree/page.rs at line 339

[3.1844]→[3.5624:5731](∅→∅),[3.5731]→[3.7253:7278](∅→∅),[3.7278]→[3.5754:5900](∅→∅),[3.5754]→[3.5754:5900](∅→∅)

put::put::<_, _, _, Leaf>(

txn,

page,

mutable,

replace,

c.cur as usize,

k0,

v0,

k1v1,

0,

)

[3.1844]

[3.1918]

put::put::<_, _, _, Leaf>(txn, page, mutable, replace, c.cur as usize, k0, v0, 0, 0)

replacement in sanakirja-core/src/btree/page.rs at line 341

[3.1935]→[3.5901:6012](∅→∅),[3.6012]→[3.7279:7304](∅→∅),[3.7304]→[3.6035:6181](∅→∅),[3.6035]→[3.6035:6181](∅→∅)

put::put::<_, _, _, Internal>(

txn,

page,

mutable,

replace,

c.cur as usize,

k0,

v0,

k1v1,

l,

r,

)

[3.1935]

[3.11455]

put::put::<_, _, _, Internal>(txn, page, mutable, replace, c.cur as usize, k0, v0, l, r)

replacement in sanakirja-core/src/btree/page.rs at line 525

[2.16681]→[2.16681:16788](∅→∅)

let (page, freed) = if m.modified.c0.is_leaf {

merge::<_, _, _, Leaf>(txn, m)?

[2.16681]

[2.16788]

return if m.modified.c0.is_leaf {

super::page_unsized::merge::<_, _, _, _, Leaf>(txn, m)

replacement in sanakirja-core/src/btree/page.rs at line 528

[2.16809]→[2.16809:16861](∅→∅)

merge::<_, _, _, Internal>(txn, m)?

[2.16809]

[3.7934]

super::page_unsized::merge::<_, _, _, _, Internal>(txn, m)

replacement in sanakirja-core/src/btree/page.rs at line 581

[3.6594]→[3.441:633](∅→∅)

if m.modified.c0.is_leaf {

rebalance_right::<_, _, _, Leaf>(txn, m)

} else {

rebalance_right::<_, _, _, Internal>(txn, m)

}

[3.6594]

[3.18457]

super::page_unsized::rebalance::rebalance_right::<_, _, _, Self>(txn, m)

edit in sanakirja-core/src/btree/page.rs at line 714

[3.12021]→[2.19031:19163](∅→∅),[3.6673]→[3.5491:5504](∅→∅),[3.6049]→[3.5491:5504](∅→∅),[2.19163]→[3.5491:5504](∅→∅),[3.5491]→[3.5491:5504](∅→∅),[3.8490]→[3.20093:20116](∅→∅),[3.1787]→[3.20093:20116](∅→∅),[3.5504]→[3.20093:20116](∅→∅),[3.34714]→[3.20093:20116](∅→∅),[3.20116]→[3.5505:5549](∅→∅),[3.5549]→[3.34779:34802](∅→∅),[3.34779]→[3.34779:34802](∅→∅),[3.34802]→[2.19164:19347](∅→∅),[2.19347]→[3.8196:8350](∅→∅),[3.34802]→[3.8196:8350](∅→∅),[3.8350]→[3.5637:5683](∅→∅),[3.3774]→[3.5637:5683](∅→∅),[3.5637]→[3.5637:5683](∅→∅),[3.20315]→[3.35024:35039](∅→∅),[3.5683]→[3.35024:35039](∅→∅),[3.35024]→[3.35024:35039](∅→∅),[3.35039]→[3.35039:35045](∅→∅),[3.35045]→[2.19348:19417](∅→∅),[2.19417]→[3.710:744](∅→∅),[3.35045]→[3.710:744](∅→∅),[3.744]→[3.8491:8532](∅→∅),[3.8532]→[3.5684:5790](∅→∅),[3.5790]→[3.8644:8661](∅→∅),[3.8644]→[3.8644:8661](∅→∅),[3.8661]→[3.5791:5845](∅→∅),[3.5845]→[3.8718:8728](∅→∅),[3.8718]→[3.8718:8728](∅→∅),[3.8728]→[3.35142:35155](∅→∅),[3.20371]→[3.35142:35155](∅→∅),[3.801]→[3.35142:35155](∅→∅),[3.35142]→[3.35142:35155](∅→∅),[3.35155]→[2.19418:19539](∅→∅),[2.19539]→[3.35155:35177](∅→∅),[3.35155]→[3.35155:35177](∅→∅),[3.35177]→[2.19540:19790](∅→∅),[2.19790]→[3.6050:6096](∅→∅),[3.35371]→[3.6050:6096](∅→∅),[3.20504]→[3.35425:35446](∅→∅),[3.6096]→[3.35425:35446](∅→∅),[3.5981]→[3.35425:35446](∅→∅),[3.35425]→[3.35425:35446](∅→∅),[3.35446]→[3.35446:35449](∅→∅),[3.35449]→[2.19791:19979](∅→∅),[2.19979]→[3.8439:8476](∅→∅),[3.20528]→[3.8439:8476](∅→∅),[3.8476]→[2.19980:20452](∅→∅),[2.20452]→[3.35631:35673](∅→∅),[3.35631]→[3.35631:35673](∅→∅),[3.35673]→[2.20453:20523](∅→∅),[2.20523]→[3.5733:5784](∅→∅),[3.6207]→[3.5733:5784](∅→∅),[3.5784]→[3.8477:8543](∅→∅),[3.8543]→[2.20524:20592](∅→∅),[2.20592]→[3.8544:8634](∅→∅),[3.6271]→[3.8544:8634](∅→∅),[3.8634]→[2.20593:20653](∅→∅),[3.20936]→[3.36058:36081](∅→∅),[2.20653]→[3.36058:36081](∅→∅),[3.6416]→[3.36058:36081](∅→∅),[3.36058]→[3.36058:36081](∅→∅),[3.36081]→[3.5785:5836](∅→∅),[3.5836]→[3.8635:8795](∅→∅),[3.8795]→[2.20654:20714](∅→∅),[3.21218]→[3.36340:36369](∅→∅),[2.20714]→[3.36340:36369](∅→∅),[3.6562]→[3.36340:36369](∅→∅),[3.36340]→[3.36340:36369](∅→∅),[3.36369]→[2.20715:20853](∅→∅),[3.21349]→[3.36499:36505](∅→∅),[2.20853]→[3.36499:36505](∅→∅),[3.6691]→[3.36499:36505](∅→∅),[3.36499]→[3.36499:36505](∅→∅),[3.36505]→[2.20854:21081](∅→∅),[2.21081]→[3.36505:36508](∅→∅),[3.36505]→[3.36505:36508](∅→∅)

/// Perform the modifications on a page, by copying it onto page `new`.

fn modify<T: LoadPage, K: Storable, V: Storable, L: Alloc>(

txn: &T,

new: &mut MutPage,

m: &mut ModifiedPage<K, V, Page<K, V>>,

n: &mut isize,

) {

// 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).

let mut l = <Page<K, V>>::left_child(m.page.as_page(), &m.c0);

while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.page.as_page(), &mut m.c0) {

alloc::<_, _, L>(new, k, v, l, r, n);

l = 0;

}

// If there's an insertion on two in the modified page, do them.

if let Some((k, v)) = m.ins {

if let Some((k2, v2)) = m.ins2 {

alloc::<_, _, L>(new, k, v, 0, 0, n);

alloc::<_, _, L>(new, k2, v2, m.l, m.r, n);

} else {

alloc::<_, _, L>(new, k, v, m.l, m.r, n);

}

} else {

// If there's no insertion, we have had no opportunity to set

// the updated left chlid, so set it here.

l = m.l

}

// 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) {

alloc::<_, _, L>(new, k, v, l, r, n);

l = 0;

}

/// The very unsurprising `merge` function

fn merge<

T: AllocPage + LoadPage,

K: Storable + core::fmt::Debug,

V: Storable + core::fmt::Debug,

L: Alloc,

>(

txn: &mut T,

mut m: Concat<K, V, Page<K, V>>,

) -> 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);

let mut n = 0;

if m.mod_is_left {

modify::<_, _, _, L>(txn, &mut new, &mut m.modified, &mut n);

let mut rc = PageCursor::new(&m.other, 0);

let l = <Page<K, V>>::left_child(m.other.as_page(), &rc);

alloc::<_, _, L>(&mut new, m.mid.0, m.mid.1, 0, l, &mut n);

while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.other.as_page(), &mut rc) {

alloc::<_, _, L>(&mut new, k, v, 0, r, &mut n);

}

} else {

let mut rc = PageCursor::new(&m.other, 0);

let mut l = <Page<K, V>>::left_child(m.other.as_page(), &rc);

while let Some((k, v, r)) = <Page<K, V>>::next(txn, m.other.as_page(), &mut rc) {

alloc::<_, _, L>(&mut new, k, v, l, r, &mut n);

l = 0;

}

alloc::<_, _, L>(&mut new, m.mid.0, m.mid.1, 0, 0, &mut n);

modify::<_, _, _, L>(txn, &mut new, &mut m.modified, &mut n);

}

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 730

[2.21552]

[3.38877]

let size = core::mem::size_of::<Tuple<K, V>>();

replacement in sanakirja-core/src/btree/page.rs at line 732

[3.38911]→[2.21553:21636](∅→∅)

let r = (*off) & !0xfff;

let off = (*off) & 0xfff;

[3.38911]

[3.22604]

let off = u64::from_le(*off);

let r = off & !0xfff;

let off = off & 0xfff;

edit in sanakirja-core/src/btree/page.rs at line 737

[3.22697]→[3.6819:6887](∅→∅)

let size = core::mem::size_of::<Tuple<K, V>>();

edit in sanakirja-core/src/btree/page.rs at line 743

[2.21839]→[2.21839:21923](∅→∅)

hdr.set_n(hdr.n() + 1);

hdr.incr(8 + size);

edit in sanakirja-core/src/btree/page.rs at line 755

[3.39378]

let hdr = header_mut(new);

hdr.set_n(hdr.n() + s.len() as u16);

hdr.incr((8 + size) * s.len());

edit in sanakirja-core/src/btree/page.rs at line 780

[3.39990]→[3.39990:39991](∅→∅),[3.39991]→[2.22534:22626](∅→∅),[2.22626]→[3.7040:7086](∅→∅),[3.39991]→[3.7040:7086](∅→∅),[3.7086]→[3.23686:23709](∅→∅),[3.6917]→[3.23686:23709](∅→∅),[3.23686]→[3.23686:23709](∅→∅),[3.23709]→[3.40103:40174](∅→∅),[3.40103]→[3.40103:40174](∅→∅),[3.40174]→[3.7087:7141](∅→∅),[3.7141]→[3.23773:23786](∅→∅),[3.6140]→[3.23773:23786](∅→∅),[3.6978]→[3.23773:23786](∅→∅),[3.23773]→[3.23773:23786](∅→∅),[3.23786]→[3.7142:7352](∅→∅),[3.7411]→[3.24072:24078](∅→∅),[3.24072]→[3.24072:24078](∅→∅),[3.24078]→[3.40544:40622](∅→∅),[3.40544]→[3.40544:40622](∅→∅),[3.40622]→[3.40622:40624](∅→∅)

/// Simply allocate an entry in the page, copy it, and set

/// its right and left children.

fn alloc<K: Storable, V: Storable, L: Alloc>(

new: &mut MutPage,

k0: &K,

v0: &V,

l: u64,

r: u64,

n: &mut isize,

) {

let off_new = L::alloc_insert::<K, V>(new, n, r);

unsafe {

let new_ptr = &mut *(new.0.data.add(off_new as usize) as *mut Tuple<K, V>);

core::ptr::copy_nonoverlapping(k0, &mut new_ptr.k, 1);

core::ptr::copy_nonoverlapping(v0, &mut new_ptr.v, 1);

}

if l > 0 {

L::set_right_child(new, *n - 1, l);

}

*n += 1;

}

edit in sanakirja-core/src/btree/page/rebalance.rs at line 78

[3.2798]→[3.9473:9520](∅→∅)

let right_hdr = header(m.other.as_page());

replacement in sanakirja-core/src/btree/page/rebalance.rs at line 79

[3.9569]→[2.23174:23260](∅→∅)

let (new_right, k, v) = if r == 0 && m.other_is_mutable && right_hdr.is_dirty() {

[3.9569]

[2.23260]

let (new_right, k, v) = if r == 0 && m.other_is_mutable && m.other.is_dirty() {

replacement in sanakirja-core/src/btree/page/rebalance.rs at line 130

[3.8290]→[3.9719:9781](∅→∅)

freed_[1] = freed | if is_dirty { 1 } else { 0 };

[3.8290]

[3.47416]

freed_[1] = if is_dirty { freed | 1 } else { freed };

edit in sanakirja-core/src/btree/page/rebalance.rs at line 140

[3.125]→[3.2839:2862](∅→∅),[3.3846]→[3.2839:2862](∅→∅),[3.2862]→[3.3861:3871](∅→∅),[3.3861]→[3.3861:3871](∅→∅),[3.3871]→[2.24368:24692](∅→∅),[2.24692]→[3.3871:3910](∅→∅),[3.3871]→[3.3871:3910](∅→∅),[3.3910]→[3.7346:7364](∅→∅),[3.7364]→[3.7541:7613](∅→∅),[3.7613]→[3.4035:4069](∅→∅),[3.7446]→[3.4035:4069](∅→∅),[3.4035]→[3.4035:4069](∅→∅),[3.4069]→[3.9827:9864](∅→∅),[3.9864]→[3.4114:4231](∅→∅),[3.7489]→[3.4114:4231](∅→∅),[3.4114]→[3.4114:4231](∅→∅),[3.4231]→[3.9865:9999](∅→∅),[3.8302]→[3.4381:4422](∅→∅),[3.9999]→[3.4381:4422](∅→∅),[3.4927]→[3.4381:4422](∅→∅),[3.7586]→[3.4381:4422](∅→∅),[3.4381]→[3.4381:4422](∅→∅),[3.4422]→[3.5939:5997](∅→∅),[3.5997]→[3.10000:10071](∅→∅),[3.10071]→[3.4561:4562](∅→∅),[3.5010]→[3.4561:4562](∅→∅),[3.4561]→[3.4561:4562](∅→∅),[3.4562]→[3.2863:2892](∅→∅),[3.2892]→[3.4735:4736](∅→∅),[3.4735]→[3.4735:4736](∅→∅),[3.4736]→[2.24693:24747](∅→∅),[2.24747]→[3.8510:8569](∅→∅),[3.4736]→[3.8510:8569](∅→∅),[3.8569]→[3.10072:10123](∅→∅),[3.10123]→[3.8597:8661](∅→∅),[3.8569]→[3.8597:8661](∅→∅),[3.2961]→[3.4864:4942](∅→∅),[3.8661]→[3.4864:4942](∅→∅),[3.4864]→[3.4864:4942](∅→∅),[3.4942]→[2.24748:24783](∅→∅),[3.8680]→[3.4942:5094](∅→∅),[2.24783]→[3.4942:5094](∅→∅),[3.4942]→[3.4942:5094](∅→∅),[3.5094]→[3.10124:10174](∅→∅),[3.10174]→[3.3104:3139](∅→∅),[3.3104]→[3.3104:3139](∅→∅),[3.3139]→[3.5094:5178](∅→∅),[3.5094]→[3.5094:5178](∅→∅),[3.5178]→[3.10175:10226](∅→∅),[3.10226]→[3.8570:8617](∅→∅),[3.5178]→[3.8570:8617](∅→∅),[3.8617]→[3.4797:4929](∅→∅),[3.4797]→[3.4797:4929](∅→∅),[3.4929]→[3.8618:8630](∅→∅),[3.8630]→[3.3182:3205](∅→∅),[3.5396]→[3.3182:3205](∅→∅),[3.3205]→[3.10227:10277](∅→∅),[3.10277]→[3.3343:3388](∅→∅),[3.3343]→[3.3343:3388](∅→∅),[3.3388]→[3.8702:8722](∅→∅),[3.8722]→[2.24784:24986](∅→∅),[2.24986]→[3.10278:10354](∅→∅),[3.8722]→[3.10278:10354](∅→∅),[3.10354]→[3.8741:8898](∅→∅),[3.8741]→[3.8741:8898](∅→∅),[3.8898]→[3.8857:8887](∅→∅),[3.8857]→[3.8857:8887](∅→∅),[3.8887]→[3.10355:10368](∅→∅),[3.10368]→[3.5421:5465](∅→∅),[3.8942]→[3.5421:5465](∅→∅),[3.5421]→[3.5421:5465](∅→∅),[3.5465]→[2.24987:25160](∅→∅),[2.25160]→[3.10369:10507](∅→∅),[3.5465]→[3.10369:10507](∅→∅),[3.10507]→[3.8943:9052](∅→∅),[3.5465]→[3.8943:9052](∅→∅),[3.9052]→[3.10508:10565](∅→∅),[3.3428]→[3.5708:5799](∅→∅),[3.10565]→[3.5708:5799](∅→∅),[3.9083]→[3.5708:5799](∅→∅),[3.5708]→[3.5708:5799](∅→∅),[3.5799]→[3.10566:10588](∅→∅),[3.10588]→[3.126:167](∅→∅),[3.5895]→[3.126:167](∅→∅)

freed: freed_,

})

}

// 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.

pub(crate) fn rebalance_right<

'a,

T: AllocPage,

K: Storable + core::fmt::Debug,

V: Storable + core::fmt::Debug,

L: Alloc,

>(

txn: &mut T,

m: Concat<'a, K, V, Page<K, V>>,

) -> Result<Op<'a, T, K, V>, T::Error> {

assert!(!m.mod_is_left);

// Take the last element of the left page.

let lc = PageCursor::last(m.other.as_page());

let (k0, v0, r0) = <Page<K, V>>::current(txn, m.other.as_page(), &lc).unwrap();

// First element of the right page.

let rc = super::PageCursor::new(&m.modified.page, 0);

let rl = <Page<K, V>>::left_child(m.modified.page.as_page(), &rc);

let mut freed_ = [0, 0];

// Perform the modification on the modified page.

let new_right = if let Some((k, v)) = m.modified.ins {

let is_dirty = m.modified.page.is_dirty();

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(

txn,

m.modified.page,

m.modified.mutable,

m.modified.skip_first,

&m.modified.c1,

k,

v,

m.modified.ins2,

m.modified.l,

m.modified.r,

)? {

let b = if is_dirty { 1 } else { 0 };

freed_[0] = freed | b;

page

} else {

unreachable!()

}

} else {

let is_dirty = m.modified.page.is_dirty();

let (page, freed) = <Page<K, V>>::del(

txn,

m.modified.page,

m.modified.mutable,

&m.modified.c1,

m.modified.l,

)?;

if freed > 0 {

let b = if is_dirty { 1 } else { 0 };

freed_[0] = freed | b;

}

page

};

// 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)`.

let new_right = if let Put::Ok(Ok { freed, page }) = <Page<K, V>>::put(

txn,

new_right.0,

true,

false,

&rc,

m.mid.0,

m.mid.1,

None,

r0,

rl,

)? {

assert_eq!(freed, 0);

page

} else {

unreachable!()

};

// 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.

let k = unsafe { core::mem::transmute(k0) };

let v = unsafe { core::mem::transmute(v0) };

let is_dirty = m.other.is_dirty();

let (new_left, freed) = <Page<K, V>>::del(txn, m.other, m.other_is_mutable, &lc, 0)?;

if freed > 0 {

freed_[1] = freed | if is_dirty { 1 } else { 0 }

}

Ok(Op::Rebalanced {

l: new_left.0.offset,

r: new_right.0.offset,

k,

v,

incr_kv_rc: !m.modified.mutable,

replacement in sanakirja-core/src/btree/page/put.rs at line 3

[3.5945]→[3.5945:5964](∅→∅)

pub(crate) fn put<

[3.5945]

[3.5964]

pub(super) fn put<

replacement in sanakirja-core/src/btree/page/put.rs at line 8

[3.7686]→[3.6097:6111](∅→∅),[3.7687]→[3.6097:6111](∅→∅),[3.6097]→[3.6097:6111](∅→∅)

L: Alloc,

[3.7686]

[3.6111]

L: Alloc + super::super::page_unsized::AllocWrite<K, V>,

edit in sanakirja-core/src/btree/page/put.rs at line 17

[3.6213]→[3.6213:6247](∅→∅)

k1v1: Option<(&'a K, &'a V)>,

edit in sanakirja-core/src/btree/page/put.rs at line 20

[2.25219]→[2.25219:25270](∅→∅),[2.25270]→[3.7817:7865](∅→∅),[3.6458]→[3.7817:7865](∅→∅)

let size = if k1v1.is_some() { 2 } else { 1 };

debug!("put {:?} {:?} {:?}", k0, v0, k1v1);

replacement in sanakirja-core/src/btree/page/put.rs at line 21

[3.10627]→[3.6496:6531](∅→∅),[3.5283]→[3.6496:6531](∅→∅),[3.6496]→[3.6496:6531](∅→∅),[3.6531]→[3.10628:10711](∅→∅)

let is_dirty = hdr.is_dirty();

if mutable && is_dirty && L::can_alloc::<K, V>(header(page.as_page()), size) {

[3.10627]

[3.9104]

let is_dirty = page.is_dirty();

if mutable && is_dirty && L::can_alloc::<K, V>(header(page.as_page())) {

// If the page is mutable (i.e. not shared with another tree)

// and dirty, here's what we do:

edit in sanakirja-core/src/btree/page/put.rs at line 30

[3.9164]

// If we're replacing a value, this can't be in a leaf,

// hence the only thing that needs to be done is erasing

// the offset in the offset array. This is a bit naive,

// since we're moving that array back and forth.

replacement in sanakirja-core/src/btree/page/put.rs at line 42

[3.9720]→[3.6796:6835](∅→∅),[3.6796]→[3.6796:6835](∅→∅),[3.6835]→[3.7688:7814](∅→∅),[3.7814]→[3.6967:6984](∅→∅),[3.6967]→[3.6967:6984](∅→∅),[3.6984]→[3.7931:7984](∅→∅),[3.8414]→[3.7815:7878](∅→∅),[3.7984]→[3.7815:7878](∅→∅),[3.6984]→[3.7815:7878](∅→∅),[3.7878]→[3.7050:7060](∅→∅),[3.7050]→[3.7050:7060](∅→∅)

if let Some((k1, v1)) = k1v1 {

alloc::<_, _, L>(&mut page, k0, v0, 0, 0, &mut n);

alloc::<_, _, L>(&mut page, k1, v1, l, r, &mut n);

} else {

debug!("lrn = {:?} {:?} {:?}", l, r, n);

alloc::<_, _, L>(&mut page, k0, v0, l, r, &mut n);

}

[3.9720]

[3.7060]

// Do the actual insertions.

L::alloc_write(&mut page, k0, v0, l, r, &mut n);

// No page was freed, return the page.

replacement in sanakirja-core/src/btree/page/put.rs at line 46

[3.7103]→[3.6225:6275](∅→∅)

} else if L::can_compact::<K, V>(hdr, size) {

[3.7103]

[3.7156]

} else if L::can_compact::<K, V>(hdr) {

// Here, we could allocate if we cloned, so let's clone:

edit in sanakirja-core/src/btree/page/put.rs at line 51

[3.7370]

[3.10783]

// Take the offsets and split it at the cursor position.

edit in sanakirja-core/src/btree/page/put.rs at line 55

[3.7477]

[3.9721]

// If we're replacing, remove the offset that needs to go.

edit in sanakirja-core/src/btree/page/put.rs at line 58

[3.9783]

[3.7477]

// And then clone the page, inserting the new elements between

// the two halves of the split offsets.

replacement in sanakirja-core/src/btree/page/put.rs at line 63

[3.10908]→[3.9784:9834](∅→∅),[3.5526]→[3.9784:9834](∅→∅),[3.8004]→[3.9784:9834](∅→∅),[3.9834]→[3.7567:7606](∅→∅),[3.8004]→[3.7567:7606](∅→∅),[3.7567]→[3.7567:7606](∅→∅),[3.7606]→[3.8005:8129](∅→∅),[3.8129]→[3.7736:7753](∅→∅),[3.7736]→[3.7736:7753](∅→∅),[3.7753]→[3.8130:8192](∅→∅),[3.8192]→[3.7818:7828](∅→∅),[3.7818]→[3.7818:7828](∅→∅),[3.7828]→[3.9835:9871](∅→∅),[3.9871]→[3.10909:10977](∅→∅)

debug!("alloc: {:?} {:?} {:?}", l, r, n);

if let Some((k1, v1)) = k1v1 {

alloc::<_, _, L>(&mut new, k0, v0, 0, 0, &mut n);

alloc::<_, _, L>(&mut new, k1, v1, l, r, &mut n);

} else {

alloc::<_, _, L>(&mut new, k0, v0, l, r, &mut n);

}

debug!("alloc: {:?}", new);

debug!("alloc: {:?}", header(new.0.as_page()).left_page());

[3.10908]

[3.10977]

L::alloc_write(&mut new, k0, v0, l, r, &mut n);

replacement in sanakirja-core/src/btree/page/put.rs at line 74

[3.8060]→[3.11042:11095](∅→∅),[3.11095]→[3.47480:47513](∅→∅),[3.1827]→[3.47480:47513](∅→∅),[3.47480]→[3.47480:47513](∅→∅),[3.47513]→[3.10107:10175](∅→∅)

let s = core::mem::size_of::<Tuple<K, V>>();

assert!(k1v1.is_none());

split::<_, _, _, L>(txn, page, mutable, s, u, k0, v0, l, r)

[3.8060]

[3.8372]

// Else, split the page.

split::<_, _, _, L>(txn, page, mutable, u, k0, v0, l, r)

replacement in sanakirja-core/src/btree/page/put.rs at line 84

[3.8057]→[3.8524:8538](∅→∅),[3.8407]→[3.8524:8538](∅→∅),[3.8524]→[3.8524:8538](∅→∅)

L: Alloc,

[3.8057]

[3.8538]

L: Alloc + super::super::page_unsized::AllocWrite<K, V>,

edit in sanakirja-core/src/btree/page/put.rs at line 89

[3.8596]→[3.8596:8613](∅→∅)

size: usize,

replacement in sanakirja-core/src/btree/page/put.rs at line 98

[3.8777]→[3.8777:8837](∅→∅)

let page_is_dirty = if hdr.is_dirty() { 1 } else { 0 };

[3.8777]

[3.8837]

let page_is_dirty = if page.is_dirty() { 1 } else { 0 };

edit in sanakirja-core/src/btree/page/put.rs at line 105

[3.8993]

[3.9051]

// Find the split entry (i.e. the entry going up in the B

// tree). Then, mid_child is the right child of the split

// key/value, and `s1` is the offsets of the right side of the

// split.

edit in sanakirja-core/src/btree/page/put.rs at line 114

[3.9225]

// Else, the split key is the first element of `s1`: set the

// new, updated `s1`.

replacement in sanakirja-core/src/btree/page/put.rs at line 123

[3.9527]→[3.11269:11374](∅→∅)

// If we are here, u >= k, i.e. the insertion is in the right-hand

// side of the split.

[3.9527]

[3.11374]

// If we are here, u >= k, i.e. the insertion is in the

// right-hand side of the split, or is the split entry itself.

edit in sanakirja-core/src/btree/page/put.rs at line 128

[3.11507]

// if we're inserting in the right-hand side, clone to the

// newly allocated `right` page, by

edit in sanakirja-core/src/btree/page/put.rs at line 131

[3.11534]

// Splitting the offsets to make space for an insertion,

// and insert in the middle.

//

// Off-by-one error? Nope: since `k` is the split entry,

// the right page starts at index `k + 1`, hence if `u ==

// k + 1`, `kk` must be 0.

replacement in sanakirja-core/src/btree/page/put.rs at line 142

[3.11760]→[3.11760:11824](∅→∅)

alloc::<K, V, L>(&mut right, k0, v0, l, r, &mut n);

[3.11760]

[3.11824]

L::alloc_write(&mut right, k0, v0, l, r, &mut n);

replacement in sanakirja-core/src/btree/page/put.rs at line 145

[3.11912]→[3.11912:12009](∅→∅)

let mut n = 0;

clone::<K, V, L>(page.as_page(), &mut right, s1, &mut n);

[3.11912]

[3.12009]

// Else, just clone the page, we'll take care of returning

// the split entry afterwards.

clone::<K, V, L>(page.as_page(), &mut right, s1, &mut 0);

replacement in sanakirja-core/src/btree/page/put.rs at line 150

[3.12020]→[3.9527:9566](∅→∅),[3.9527]→[3.9527:9566](∅→∅)

if mutable && hdr.is_dirty() {

[3.12020]

[3.9622]

if mutable && page.is_dirty() {

replacement in sanakirja-core/src/btree/page/put.rs at line 157

[3.9934]→[3.9934:9985](∅→∅)

hdr.decr((n - 1 - k) as usize * size);

[3.9934]

[3.9985]

hdr.decr((n - 1 - k) as usize * core::mem::size_of::<Tuple<K, V>>());

edit in sanakirja-core/src/btree/page/put.rs at line 159

[3.10002]

// Else, we need to clone the first `k-1` entries,

// i.e. `s0`, onto a new left page.

edit in sanakirja-core/src/btree/page/put.rs at line 167

[3.12092]

// Finally, if `u` is the middle element, its left and right

// children become the leftmost child of the right page, and

// the rightmost child of the left page, respectively.

edit in sanakirja-core/src/btree/page/put.rs at line 185

[3.11447]

// Else, the insertion is in the new left page. We first clone

// the left page, inserting (k,v) at its position:

replacement in sanakirja-core/src/btree/page/put.rs at line 189

[3.11582]→[3.11582:11605](∅→∅)

let mut n = 0;

[3.8957]

[3.12122]

// Clone the leftmost page

edit in sanakirja-core/src/btree/page/put.rs at line 192

[3.11714]

// Clone the two sides, with an entry in between.

edit in sanakirja-core/src/btree/page/put.rs at line 194

[3.11764]

[3.12185]

let mut n = 0;

replacement in sanakirja-core/src/btree/page/put.rs at line 196

[3.12251]→[3.9024:9083](∅→∅),[3.6402]→[3.9024:9083](∅→∅),[3.9024]→[3.9024:9083](∅→∅)

alloc::<K, V, L>(&mut left, k0, v0, l, r, &mut n);

[3.12251]

[3.12252]

L::alloc_write(&mut left, k0, v0, l, r, &mut n);

replacement in sanakirja-core/src/btree/page/put.rs at line 199

[3.11965]→[3.11965:11997](∅→∅)

let mut right: MutPage;

[3.11965]

[3.11997]

let mut right;

replacement in sanakirja-core/src/btree/page/put.rs at line 201

[3.12016]→[3.12016:12114](∅→∅)

if mutable && hdr.is_dirty() {

right = unsafe { core::mem::transmute(page) };

[3.12016]

[3.8098]

// Then, for the right page:

if mutable && page.is_dirty() {

// If we can mutate the original page, remove the first

// `k` entries, and return a pointer to the split key (at

// position `k` on the page)

right = MutPage(page);

edit in sanakirja-core/src/btree/page/put.rs at line 215

[3.12379]

// Else, clone the right page.

edit in sanakirja-core/src/btree/page/put.rs at line 218

[3.9457]

[3.12487]

// The left child of the right page is `mid_child`,

// i.e. the right child of the split entry.

L::set_right_child(&mut right, -1, mid_child);

// Clone the rest of the page.

edit in sanakirja-core/src/btree/page/put.rs at line 223

[3.12514]→[3.12514:12573](∅→∅)

L::set_right_child(&mut right, -1, mid_child);

replacement in sanakirja-core/src/btree/page/alloc.rs at line 9

[2.25812]→[2.25812:25888](∅→∅)

fn can_alloc<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool;

[2.25812]

[3.17612]

fn can_alloc<K: Storable, V: Storable>(hdr: &Header) -> bool;

replacement in sanakirja-core/src/btree/page/alloc.rs at line 12

[2.25960]→[2.25960:26038](∅→∅)

fn can_compact<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool;

[2.25960]

[2.26038]

fn can_compact<K: Storable, V: Storable>(hdr: &Header) -> bool;

replacement in sanakirja-core/src/btree/page/alloc.rs at line 87

[2.27832]→[2.27832:27909](∅→∅)

fn can_alloc<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool {

[2.27832]

[2.27909]

fn can_alloc<K: Storable, V: Storable>(hdr: &Header) -> bool {

replacement in sanakirja-core/src/btree/page/alloc.rs at line 91

[2.28071]→[2.28071:28133](∅→∅)

header_size + (hdr.n() as usize + n) * f <= PAGE_SIZE

[2.28071]

[2.28133]

header_size + (hdr.n() as usize + 1) * f <= PAGE_SIZE

replacement in sanakirja-core/src/btree/page/alloc.rs at line 95

[2.28219]→[2.28219:28338](∅→∅)

fn can_compact<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool {

Self::can_alloc::<K, V>(hdr, n)

[2.28219]

[2.28338]

fn can_compact<K: Storable, V: Storable>(hdr: &Header) -> bool {

Self::can_alloc::<K, V>(hdr)

replacement in sanakirja-core/src/btree/page/alloc.rs at line 197

[2.30600]→[2.30600:30773](∅→∅)

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>>())

[2.30600]

[2.30773]

fn can_alloc<K: Storable, V: Storable>(hdr: &Header) -> bool {

(HDR as usize) + (hdr.n() as usize + 1) * 8 + core::mem::size_of::<Tuple<K, V>>()

replacement in sanakirja-core/src/btree/page/alloc.rs at line 202

[2.30814]→[2.30814:30893](∅→∅)

fn can_compact<K: Storable, V: Storable>(hdr: &Header, n: usize) -> bool {

[2.30814]

[2.30893]

fn can_compact<K: Storable, V: Storable>(hdr: &Header) -> bool {

replacement in sanakirja-core/src/btree/page/alloc.rs at line 205

[2.30967]→[2.30967:31027](∅→∅)

+ n * (8 + core::mem::size_of::<Tuple<K, V>>())

[2.30967]

[2.31027]

+ 8

+ core::mem::size_of::<Tuple<K, V>>()

edit in sanakirja-core/src/btree/page/alloc.rs at line 304

[3.29961]

impl<K: Storable, V: Storable> crate::btree::page_unsized::AllocWrite<K, V> for Internal {

fn alloc_write(new: &mut MutPage, k0: &K, v0: &V, l: u64, r: u64, n: &mut isize) {

alloc_write::<K, V, Self>(new, k0, v0, l, r, n)

}

impl<K: Storable, V: Storable> crate::btree::page_unsized::AllocWrite<K, V> for Leaf {

fn alloc_write(new: &mut MutPage, k0: &K, v0: &V, l: u64, r: u64, n: &mut isize) {

alloc_write::<K, V, Self>(new, k0, v0, l, r, n)

}

/// Simply allocate an entry in the page, copy it, and set its right

/// and left children.

fn alloc_write<K: Storable, V: Storable, L: Alloc>(

new: &mut MutPage,

k0: &K,

v0: &V,

l: u64,

r: u64,

n: &mut isize,

) {

let off_new = L::alloc_insert::<K, V>(new, n, r);

unsafe {

let new_ptr = &mut *(new.0.data.add(off_new as usize) as *mut Tuple<K, V>);

core::ptr::copy_nonoverlapping(k0, &mut new_ptr.k, 1);

core::ptr::copy_nonoverlapping(v0, &mut new_ptr.v, 1);

}

if l > 0 {

L::set_right_child(new, *n - 1, l);

}

*n += 1;

}

edit in sanakirja-core/src/btree/mod.rs at line 109

[3.9109]→[3.10457:10458](∅→∅),[3.10458]→[3.10458:10522](∅→∅),[3.10522]→[3.29298:29355](∅→∅),[3.29298]→[3.29298:29355](∅→∅)

/// Returns the size of the entry pointed to by the cursor.

fn current_size(p: Page, c: &Self::Cursor) -> usize;

edit in sanakirja-core/src/btree/mod.rs at line 149

[3.10988]

[3.14162]

///

/// 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`.

replacement in sanakirja/src/tests.rs at line 504

[3.1148]→[3.9834:9854](∅→∅),[3.9854]→[3.15959:15990](∅→∅)

for i in 1..3 {

let n = i * 1_000_000;

[3.1148]

[3.9892]

for i in 1..2 {

let n = i * 5000;

edit in sanakirja/src/tests.rs at line 528

[3.2045]

crate::debug::debug(&txn, &[&db], "debug", true);

Cleaning up the unsized part

Dependencies

Change contents