Cleanup + comments

[?]

Feb 11, 2021, 12:44 PM

73Z2UB3JGRLFNFORE7D64O4IHIFSZASD4G4FLJ4FJLHANT75MGIAC

Dependencies

[2] 7WJNSPEW Using the same definition of the "occupied" field uniform everywhere
[3] Q7DRIBBR Debugging replace (which cannot be del+put)
[4] KM3JAFGP Adding a test for next/prev
[5] QEUTVAZ4 Splitting btree::page
[6] EAAYH6BQ Debugging put
[7] X3QVVQIS More debugging (del seems to work now)
[8] SO25TWFL A few features for integrating it into Pijul
[9] OFINGD26 implementing prev() on cursors (+ some cleanup)
[10] 6UVFCERM Formatting, debugging, etc.
[11] FMN7X4J2 Micro-improvements, now noticeably faster than std::collections::BTreeMap
[12] OTWDDJE7 Trait/type cleanup
[13] APPY2E7M Unsized deletions + custom sizes back
[14] AOX2XQIS Actually, with the correct functions, Unsized pages are always slower than Sized pages (especially for writing)
[15] H3FVSQIQ Unsized pages
[16] KX3WVNZW Testing/debugging "rebalance causes split of the root"
[17] XEU2QVLC Debugging after plugging this into Pijul
[18] T73WR2BX Cleaner RC increments for keys and values containing references + more comments in `del`
[19] WAKPPBKO Fixing a double-free of roots after deletions (the root was freed both by handle_merge and by update_root)
[20] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
[21] OP6SVMOD Resetting history
[22] WS4ZQM4R Debugging, tests, etc.
[23] W26CFMAQ Improving safety of cursors
[24] PXF3R6SV Improving test coverage for btree::cursor
[25] LROAI3NB Two iterators (convenience functions), along with tests to move cursors (put and del still destroy cursors though)

Change contents

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

[4.50]

[4.45]

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

[4.190]

[4.137]

false,
edit in sanakirja-core/src/btree/put.rs at line 106

[4.5879]

[4.175]

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

[4.330]→[4.330:380](∅→∅)

P::move_next(cur.page.as_page(), &mut c);

[4.330]

[4.1067]

P::move_next(&mut c);
edit in sanakirja-core/src/btree/page_unsized.rs at line 31

[4.2648]→[4.2648:2747](∅→∅)

fn clean(page: &mut MutPage) {
let hdr = header_mut(page);
hdr.clean();
}
replacement in sanakirja-core/src/btree/page_unsized.rs at line 36

[4.147]→[4.147:236](∅→∅)

unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {
(&*s.0, &*s.1)

[4.147]

[4.236]

fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {
unsafe { (&*s.0, &*s.1) }
edit in sanakirja-core/src/btree/page_unsized.rs at line 40

[4.243]→[4.2747:3112](∅→∅),[4.2747]→[4.2747:3112](∅→∅),[4.3112]→[2.0:62](∅→∅),[2.62]→[4.3170:3213](∅→∅),[4.3170]→[4.3170:3213](∅→∅),[4.3213]→[2.63:129](∅→∅),[2.129]→[4.3275:3289](∅→∅),[4.3275]→[4.3275:3289](∅→∅),[4.3607]→[4.3607:3641](∅→∅)

fn size(m: &ModifiedPage<K, V, Self>) -> usize {
let mut occupied = {
let hdr = header(m.page.as_page());
(hdr.left_page() & 0xfff) as usize
};
occupied += HDR;
if m.skip_first {
occupied -= Self::current_size(m.page.as_page(), &m.c1) as usize;
}
if let Some((k, v)) = m.ins {
occupied += 8 + crate::alloc_size(k, v) as usize;
if let Some((k, v)) = m.ins2 {
occupied += 8 + crate::alloc_size(k, v) as usize;
}
}
occupied
}
edit in sanakirja-core/src/btree/page_unsized.rs at line 44

[4.3738]

[4.0]

replace: bool,
replacement in sanakirja-core/src/btree/page_unsized.rs at line 58

[3.107]→[3.107:130](∅→∅)

false,

[3.107]

[3.130]

replace,
replacement in sanakirja-core/src/btree/page_unsized.rs at line 71

[3.388]→[3.388:411](∅→∅)

false,

[3.388]

[3.411]

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

[4.4130]→[4.4130:4415](∅→∅),[4.4415]→[3.558:716](∅→∅)

}

fn replace<'a, T: AllocPage>(
txn: &mut T,
page: CowPage,
mutable: bool,
c: &Self::Cursor,
k0: &'a K,
v0: &'a V,
k1v1: Option<(&'a K, &'a V)>,
l: u64,
r: u64,
) -> Result<Put<'a, K, V>, T::Error> {
assert!(c.cur >= 0);
assert!(!c.is_leaf);
put::put::<_, _, _, Internal>(txn, page, mutable, true, c.cur as usize, k0, v0, k1v1, l, r)
replacement in sanakirja-core/src/btree/page_unsized.rs at line 196

[4.8955]→[4.8955:9003](∅→∅)

let mod_size = Self::size(&m.modified);

[4.8955]

[4.9003]

let mod_size = size::<K, V>(&m.modified);
replacement in sanakirja-core/src/btree/page_unsized.rs at line 210

[4.9489]→[4.9489:9722](∅→∅)

unsafe {
if m.modified.c0.is_leaf {
merge::<_, _, _, Leaf>(txn, &mut new, m)
} else {
merge::<_, _, _, Internal>(txn, &mut new, m)
}

[4.9489]

[4.9722]

if m.modified.c0.is_leaf {
merge::<_, _, _, Leaf>(txn, &mut new, m)
} else {
merge::<_, _, _, Internal>(txn, &mut new, m)
replacement in sanakirja-core/src/btree/page_unsized.rs at line 236

[4.10547]→[4.10547:10596](∅→∅)

return Ok(Op::Put(Self::replace(

[4.10547]

[4.10596]

return Ok(Op::Put(Self::put(
edit in sanakirja-core/src/btree/page_unsized.rs at line 240

[4.10698]

[4.10698]

true,
edit in sanakirja-core/src/btree/page_unsized.rs at line 275

[4.11586]

[4.1341]

fn size<K: Representable + ?Sized, V: Representable + ?Sized>(
m: &ModifiedPage<K, V, Page<K, V>>,
) -> usize {
let mut total = {
let hdr = header(m.page.as_page());
(hdr.left_page() & 0xfff) as usize
};
total += HDR;
let extra = if m.c1.is_leaf { 2 } else { 8 };
if let Some((k, v)) = m.ins {
total += extra + crate::alloc_size(k, v) as usize;
if let Some((k, v)) = m.ins2 {
total += extra + crate::alloc_size(k, v) as usize;
}
}
if m.skip_first {
total -= <Page<K, V> as BTreePage<K, V>>::current_size(m.page.as_page(), &m.c1) as usize;
}
total
}
replacement in sanakirja-core/src/btree/page_unsized.rs at line 347

[4.13149]→[4.13149:13283](∅→∅),[4.13283]→[4.2530:2631](∅→∅),[4.2631]→[4.13375:13392](∅→∅),[4.13375]→[4.13375:13392](∅→∅),[4.13392]→[4.1085:1212](∅→∅),[4.1212]→[4.13510:13527](∅→∅),[4.13510]→[4.13510:13527](∅→∅)

unsafe fn unchecked_current_ptr(page: crate::Page, c: &Self::Cursor) -> *const u8 {
page.data.as_ptr().add(if c.is_leaf {
u16::from_le(*(page.data.as_ptr().add(HDR + c.cur as usize * 2) as *const u16)) as usize
} else {
(u64::from_le(*(page.data.as_ptr().add(HDR + c.cur as usize * 8) as *const u64))
& 0xfff) as usize
})
}

[4.13149]

[4.13527]
replacement in sanakirja-core/src/btree/page_unsized.rs at line 355

[4.14150]→[4.14150:14219](∅→∅)

fn move_next(_page: crate::Page, c: &mut Self::Cursor) -> bool {

[4.14150]

[4.2920]

fn move_next(c: &mut Self::Cursor) -> bool {
replacement in sanakirja-core/src/btree/page_unsized.rs at line 363

[4.14340]→[4.14340:14409](∅→∅)

fn move_prev(_page: crate::Page, c: &mut Self::Cursor) -> bool {

[4.14340]

[4.14409]

fn move_prev(c: &mut Self::Cursor) -> bool {
replacement in sanakirja-core/src/btree/page_unsized.rs at line 430

[4.16285]→[4.16285:16369](∅→∅)

fn split_at(_: crate::Page, c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {

[4.16285]

[4.16369]

/// 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) {
replacement in sanakirja-core/src/btree/page_unsized.rs at line 547

[4.18973]→[4.18973:18991](∅→∅)

unsafe fn modify<

[4.18973]

[4.18991]

fn modify<
replacement in sanakirja-core/src/btree/page_unsized.rs at line 585

[4.20059]→[4.20059:20076](∅→∅)

unsafe fn merge<

[4.20059]

[4.20076]

fn merge<
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 25

[3.1976]→[4.129:197](∅→∅),[4.23777]→[4.129:197](∅→∅)

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

[3.1976]

[4.23842]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 29

[4.23920]

[4.23920]

true,
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 68

[3.2188]→[3.2188:2321](∅→∅)

if let Put::Ok(Ok { page, freed }) =
<Page<K, V>>::put(txn, new_left.0, true, &lc, m.mid.0, m.mid.1, None, 0, rl)?
{

[3.2188]

[3.2321]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
txn, new_left.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,
)? {
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 116

[3.2697]→[4.1156:1224](∅→∅),[4.25893]→[4.1156:1224](∅→∅)

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

[3.2697]

[4.25958]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 120

[4.26036]

[4.26036]

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

[3.2850]→[3.2850:2985](∅→∅)

if let Put::Ok(Ok { page, freed }) =
<Page<K, V>>::put(txn, new_right.0, true, &rc, m.mid.0, m.mid.1, None, r0, rl)?
{

[3.2850]

[3.2985]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
txn,
new_right.0,
true,
false,
&rc,
m.mid.0,
m.mid.1,
None,
r0,
rl,
)? {
edit in sanakirja-core/src/btree/page_unsized/header.rs at line 63

[4.16833]→[4.16833:16926](∅→∅)

}

pub fn clean(&mut self) {
self.n = (u16::from_le(self.n) & 0xfff).to_le()
edit in sanakirja-core/src/btree/page.rs at line 29

[4.554]

[4.8769]

impl<K: Representable, V: Representable> super::BTreePage<K, V> for Page<K, V> {
fn is_dirty(page: crate::Page) -> bool {
header(page).is_dirty()
}

type Cursor = PageCursor;

fn is_empty(_: crate::Page, c: &Self::Cursor) -> bool {
c.cur >= c.total as isize
}

fn is_init(_: crate::Page, c: &Self::Cursor) -> bool {
c.cur < 0
}

fn cursor_before(p: crate::Page) -> Self::Cursor {
PageCursor::new(p, -1)
}

fn cursor_after(p: crate::Page) -> 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 {
let f = tuple_size::<K, V>();
let off = {
let al = K::ALIGN.max(V::ALIGN);
let hdr = (HDR + al - 1) & !(al - 1);
hdr + c.cur as usize * f
};
unsafe {
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) as *const u64).add(c.cur as usize));
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 {
assert!(c.cur >= 0 && c.cur < c.total as isize);
unsafe {
if c.is_leaf {
tuple_size::<K, V>()
} else {
8 + entry_size::<K, V>(page.data.as_ptr().add(
(u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur as usize))
& 0xfff) as usize,
))
}
}
}
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().offset(HDR as isize + c.cur * 8) as *const u64) };
u64::from_le(off) & !0xfff
}
}
fn set_cursor<'a, T: LoadPage>(
txn: &T,
page: crate::Page,
c: &mut PageCursor,
k0: &K,
v0: Option<&V>,
) -> Result<(&'a K, &'a V, u64), usize> {
unsafe {
let lookup = lookup(txn, page, c, k0, v0);
let result;
c.cur = match lookup {
Ok(n) => {
result = if c.is_leaf {
let f = tuple_size::<K, V>();
let off = {
let al = K::ALIGN.max(V::ALIGN);
let hdr_size = (HDR + al - 1) & !(al - 1);
(0, (hdr_size + f * n) as u16)
};
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
}
}
edit in sanakirja-core/src/btree/page.rs at line 178

[4.8770]

[4.5036]

fn split_at(c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {
(
PageCursor {
cur: 0,
total: c.cur.max(0) as usize,
is_leaf: c.is_leaf,
},
*c,
)
}
}
edit in sanakirja-core/src/btree/page.rs at line 197

[4.9933]→[4.1422:1457](∅→∅),[4.1457]→[4.610:672](∅→∅)

fn clean(page: &mut MutPage) {
<super::page_unsized::Page<K, V>>::clean(page)
}
replacement in sanakirja-core/src/btree/page.rs at line 208

[4.10101]→[4.1088:1219](∅→∅)

unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {
(core::mem::transmute(&s.0), core::mem::transmute(&s.1))

[4.10101]

[4.1219]

fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {
unsafe { (core::mem::transmute(&s.0), core::mem::transmute(&s.1)) }
edit in sanakirja-core/src/btree/page.rs at line 212

[4.1226]→[4.1354:1407](∅→∅),[4.10101]→[4.1354:1407](∅→∅),[4.1407]→[2.130:156](∅→∅),[2.156]→[4.1577:1625](∅→∅),[4.1577]→[4.1577:1625](∅→∅),[4.1625]→[4.10234:10292](∅→∅),[4.10234]→[4.10234:10292](∅→∅),[4.10292]→[4.44417:44443](∅→∅),[4.44443]→[4.10355:10400](∅→∅),[4.1468]→[4.10355:10400](∅→∅),[4.10355]→[4.10355:10400](∅→∅),[4.10400]→[2.157:206](∅→∅),[2.206]→[4.10452:10469](∅→∅),[4.10452]→[4.10452:10469](∅→∅),[4.10469]→[2.207:232](∅→∅),[2.232]→[4.10497:10508](∅→∅),[4.10497]→[4.10497:10508](∅→∅),[4.1740]→[4.79:117](∅→∅),[4.117]→[2.233:354](∅→∅),[2.354]→[4.492:535](∅→∅),[4.1799]→[4.492:535](∅→∅),[4.535]→[2.355:422](∅→∅),[2.422]→[4.10875:10899](∅→∅),[4.10875]→[4.10875:10899](∅→∅),[4.10899]→[2.423:548](∅→∅),[2.548]→[4.10916:10923](∅→∅),[4.10916]→[4.10916:10923](∅→∅)

fn size(m: &ModifiedPage<K, V, Self>) -> usize {
let mut total = {
let hdr = header(m.page.as_page());
(hdr.left_page() & 0xfff) as usize
};
if m.c1.is_leaf {
let al = K::ALIGN.max(V::ALIGN);
total += (HDR + al - 1) & (!al - 1);
} else {
total += HDR
};
if let Some((k, v)) = m.ins {
let extra = if m.c1.is_leaf { 8 } else { 0 };
total += extra + crate::alloc_size(k, v) as usize;
if let Some((k, v)) = m.ins2 {
total += extra + crate::alloc_size(k, v) as usize;
}
}
if m.skip_first {
total -= Self::current_size(m.page.as_page(), &m.c1) as usize;
}
total
}
edit in sanakirja-core/src/btree/page.rs at line 216

[4.11010]

[4.970]

replace: bool,
replacement in sanakirja-core/src/btree/page.rs at line 230

[3.5731]→[3.5731:5754](∅→∅)

false,

[3.5731]

[3.5754]

replace,
replacement in sanakirja-core/src/btree/page.rs at line 243

[3.6012]→[3.6012:6035](∅→∅)

false,

[3.6012]

[3.6035]

replace,
edit in sanakirja-core/src/btree/page.rs at line 254

[4.11472]→[4.1553:1587](∅→∅),[4.1587]→[4.1082:1326](∅→∅),[4.1082]→[4.1082:1326](∅→∅),[4.1326]→[3.6182:6608](∅→∅),[3.6608]→[4.1513:1520](∅→∅),[4.3402]→[4.1513:1520](∅→∅),[4.1513]→[4.1513:1520](∅→∅)

fn replace<'a, T: AllocPage>(
txn: &mut T,
page: CowPage,
mutable: bool,
c: &Self::Cursor,
k0: &'a K,
v0: &'a V,
k1v1: Option<(&'a K, &'a V)>,
l: u64,
r: u64,
) -> Result<Put<'a, K, V>, T::Error> {
if r == 0 {
put::put::<_, _, _, Leaf>(txn, page, mutable, true, c.cur as usize, k0, v0, k1v1, 0, 0)
} else {
put::put::<_, _, _, Internal>(
txn,
page,
mutable,
true,
c.cur as usize,
k0,
v0,
k1v1,
l,
r,
)
}
}
replacement in sanakirja-core/src/btree/page.rs at line 375

[4.16292]→[4.2976:3024](∅→∅)

let mod_size = Self::size(&m.modified);

[4.16292]

[4.5228]

let mod_size = size::<K, V>(&m.modified);
replacement in sanakirja-core/src/btree/page.rs at line 385

[4.5514]→[4.16691:16755](∅→∅),[4.2861]→[4.16691:16755](∅→∅),[4.16691]→[4.16691:16755](∅→∅),[4.16755]→[4.2862:2923](∅→∅),[4.5571]→[4.16806:16831](∅→∅),[4.2923]→[4.16806:16831](∅→∅),[4.16806]→[4.16806:16831](∅→∅),[4.16831]→[4.2924:2989](∅→∅),[4.5632]→[4.16886:16904](∅→∅),[4.2989]→[4.16886:16904](∅→∅),[4.16886]→[4.16886:16904](∅→∅)

unsafe {
if m.modified.c0.is_leaf {
merge::<_, _, _, Leaf>(txn, &mut new, m)
} else {
merge::<_, _, _, Internal>(txn, &mut new, m)
}

[4.2861]

[4.16904]

if m.modified.c0.is_leaf {
merge::<_, _, _, Leaf>(txn, &mut new, m)
} else {
merge::<_, _, _, Internal>(txn, &mut new, m)
replacement in sanakirja-core/src/btree/page.rs at line 411

[4.3536]→[4.3536:3585](∅→∅)

return Ok(Op::Put(Self::replace(

[4.3536]

[4.6024]

return Ok(Op::Put(Self::put(
edit in sanakirja-core/src/btree/page.rs at line 415

[4.6126]

[4.6126]

true,
replacement in sanakirja-core/src/btree/page.rs at line 450

[4.18476]→[4.5416:5497](∅→∅),[4.5497]→[4.18583:18628](∅→∅),[4.18583]→[4.18583:18628](∅→∅),[4.18628]→[4.6646:6678](∅→∅),[4.6678]→[4.18726:18733](∅→∅),[4.18726]→[4.18726:18733](∅→∅),[4.18733]→[4.6679:6739](∅→∅),[4.6739]→[4.5688:5806](∅→∅),[4.5806]→[4.18819:18825](∅→∅),[4.18819]→[4.18819:18825](∅→∅),[4.18825]→[4.1077:1107](∅→∅),[4.1107]→[4.5807:5862](∅→∅),[4.18851]→[4.5807:5862](∅→∅),[4.5862]→[4.1108:1139](∅→∅),[4.5889]→[4.19108:19114](∅→∅),[4.1139]→[4.19108:19114](∅→∅),[4.19108]→[4.19108:19114](∅→∅),[4.19114]→[4.5890:5944](∅→∅),[4.5944]→[4.1140:1169](∅→∅),[4.5969]→[4.19402:19408](∅→∅),[4.1169]→[4.19402:19408](∅→∅),[4.19402]→[4.19402:19408](∅→∅),[4.19408]→[4.5970:6003](∅→∅),[4.6003]→[4.3105:3122](∅→∅),[4.3105]→[4.3105:3122](∅→∅),[4.3122]→[4.3815:3872](∅→∅),[4.3815]→[4.3815:3872](∅→∅),[4.3872]→[4.6004:6142](∅→∅),[4.6142]→[4.1529:1571](∅→∅),[4.19528]→[4.1529:1571](∅→∅),[4.1571]→[4.45226:45250](∅→∅),[4.45226]→[4.45226:45250](∅→∅),[4.45250]→[4.19593:19696](∅→∅),[4.3185]→[4.19593:19696](∅→∅),[4.19593]→[4.19593:19696](∅→∅),[4.19696]→[4.6143:6184](∅→∅),[4.6184]→[4.19836:19851](∅→∅),[4.7354]→[4.19836:19851](∅→∅),[4.19836]→[4.19836:19851](∅→∅),[4.6226]→[4.6226:6336](∅→∅),[4.6408]→[4.6408:6603](∅→∅),[4.6603]→[4.19944:19961](∅→∅),[4.7461]→[4.19944:19961](∅→∅),[4.5653]→[4.19944:19961](∅→∅),[4.3363]→[4.19944:19961](∅→∅),[4.19944]→[4.19944:19961](∅→∅),[4.19961]→[4.6604:6625](∅→∅),[4.6625]→[4.3737:3863](∅→∅),[4.3863]→[4.6731:7036](∅→∅),[4.6731]→[4.6731:7036](∅→∅)

impl<K: Representable, V: Representable> super::BTreePage<K, V> for Page<K, V> {
fn is_dirty(page: crate::Page) -> bool {
header(page).is_dirty()
}

fn is_empty(_: crate::Page, c: &Self::Cursor) -> bool {
c.cur >= c.total as isize
}

fn is_init(_: crate::Page, c: &Self::Cursor) -> bool {
c.cur < 0
}
type Cursor = PageCursor;
fn cursor_before(p: crate::Page) -> Self::Cursor {
PageCursor::new(p, -1)
}
fn cursor_after(p: crate::Page) -> 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 {
let f = tuple_size::<K, V>();
let off = {
let al = K::ALIGN.max(V::ALIGN);
let hdr = (HDR + al - 1) & !(al - 1);
hdr + c.cur as usize * f
};
unsafe {
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) as *const u64).add(c.cur as usize));
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,
))
}

[4.18476]

[4.20159]

fn size<K: Representable, V: Representable>(m: &ModifiedPage<K, V, Page<K, V>>) -> usize {
let mut total = {
let hdr = header(m.page.as_page());
(hdr.left_page() & 0xfff) as usize
};
if m.c1.is_leaf {
let al = K::ALIGN.max(V::ALIGN);
total += (HDR + al - 1) & (!al - 1);
} else {
total += HDR
};
if let Some((k, v)) = m.ins {
let extra = if m.c1.is_leaf { 0 } else { 8 };
total += extra + crate::alloc_size(k, v) as usize;
if let Some((k, v)) = m.ins2 {
total += extra + crate::alloc_size(k, v) as usize;
replacement in sanakirja-core/src/btree/page.rs at line 468

[4.20175]→[4.7683:7771](∅→∅),[4.7771]→[4.7037:7094](∅→∅),[4.7094]→[4.7771:7817](∅→∅),[4.7771]→[4.7771:7817](∅→∅),[4.7817]→[4.1572:1614](∅→∅),[4.1614]→[4.45308:45403](∅→∅),[4.45308]→[4.45308:45403](∅→∅),[4.45403]→[4.7095:7132](∅→∅),[4.7132]→[4.20611:20628](∅→∅),[4.45431]→[4.20611:20628](∅→∅),[4.20611]→[4.20611:20628](∅→∅),[4.20628]→[4.3864:3991](∅→∅),[4.4022]→[4.20721:20738](∅→∅),[4.8017]→[4.20721:20738](∅→∅),[4.3991]→[4.20721:20738](∅→∅),[4.20721]→[4.20721:20738](∅→∅),[4.20738]→[4.8018:8086](∅→∅),[4.8086]→[4.7236:7293](∅→∅),[4.7293]→[4.20807:20851](∅→∅),[4.8086]→[4.20807:20851](∅→∅),[4.20807]→[4.20807:20851](∅→∅),[4.20851]→[4.1615:1652](∅→∅),[4.45484]→[4.21215:21236](∅→∅),[4.1652]→[4.21215:21236](∅→∅),[4.21215]→[4.21215:21236](∅→∅),[4.21236]→[4.3754:3817](∅→∅),[4.3817]→[4.3992:4135](∅→∅),[4.4358]→[4.21394:21443](∅→∅),[4.8405]→[4.21394:21443](∅→∅),[4.4135]→[4.21394:21443](∅→∅),[4.21394]→[4.21394:21443](∅→∅),[4.21443]→[4.8406:8475](∅→∅),[4.8475]→[4.7404:7442](∅→∅),[4.7442]→[4.21542:21634](∅→∅),[4.21542]→[4.21542:21634](∅→∅),[4.21634]→[4.8476:8626](∅→∅),[4.8626]→[4.7443:7467](∅→∅),[4.7467]→[4.8626:8724](∅→∅),[4.8626]→[4.8626:8724](∅→∅),[4.8724]→[4.7468:7497](∅→∅),[4.7497]→[4.21699:21753](∅→∅),[4.8724]→[4.21699:21753](∅→∅),[4.21699]→[4.21699:21753](∅→∅),[4.21753]→[4.4136:4258](∅→∅),[4.7604]→[4.21841:21896](∅→∅),[4.8822]→[4.21841:21896](∅→∅),[4.4258]→[4.21841:21896](∅→∅),[4.21841]→[4.21841:21896](∅→∅),[4.21896]→[4.8823:8888](∅→∅),[4.8888]→[4.7605:7648](∅→∅),[4.7648]→[4.21962:22016](∅→∅),[4.8888]→[4.21962:22016](∅→∅),[4.21962]→[4.21962:22016](∅→∅),[4.22016]→[4.4259:4378](∅→∅),[4.7752]→[4.22098:22153](∅→∅),[4.8980]→[4.22098:22153](∅→∅),[4.4378]→[4.22098:22153](∅→∅),[4.22098]→[4.22098:22153](∅→∅),[4.22153]→[4.3818:3854](∅→∅),[4.3854]→[4.22176:22193](∅→∅),[4.22176]→[4.22176:22193](∅→∅),[4.22193]→[4.8981:9008](∅→∅),[4.9008]→[4.1170:1198](∅→∅),[4.1198]→[4.22245:22285](∅→∅),[4.22245]→[4.22245:22285](∅→∅),[4.22285]→[4.9009:9055](∅→∅),[4.9055]→[4.22339:22356](∅→∅),[4.22339]→[4.22339:22356](∅→∅),[4.22356]→[4.9056:9111](∅→∅),[4.9111]→[4.22435:22459](∅→∅),[4.709]→[4.22435:22459](∅→∅),[4.22435]→[4.22435:22459](∅→∅),[4.24582]→[4.24582:24688](∅→∅),[4.24688]→[4.1653:1707](∅→∅),[4.1707]→[4.45554:45590](∅→∅),[4.45554]→[4.45554:45590](∅→∅),[4.45590]→[4.24765:24956](∅→∅),[4.3929]→[4.24765:24956](∅→∅),[4.24765]→[4.24765:24956](∅→∅),[4.25123]→[4.25123:25150](∅→∅),[4.25150]→[4.3930:3983](∅→∅),[4.9267]→[4.25199:25228](∅→∅),[4.3983]→[4.25199:25228](∅→∅),[4.25199]→[4.25199:25228](∅→∅),[4.25228]→[4.4498:4628](∅→∅),[4.4628]→[4.5821:6022](∅→∅),[4.9455]→[4.25407:25430](∅→∅),[4.6022]→[4.25407:25430](∅→∅),[4.4074]→[4.25407:25430](∅→∅),[4.25407]→[4.25407:25430](∅→∅),[4.25430]→[4.7753:7784](∅→∅),[4.7784]→[4.25452:25535](∅→∅),[4.25452]→[4.25452:25535](∅→∅),[4.25535]→[4.7785:7816](∅→∅),[4.7816]→[4.25557:25625](∅→∅),[4.25557]→[4.25557:25625](∅→∅),[4.25625]→[4.9456:9541](∅→∅),[4.9541]→[4.25710:25720](∅→∅),[4.25710]→[4.25710:25720](∅→∅),[4.25720]→[4.1199:1224](∅→∅),[4.1224]→[4.25741:25765](∅→∅),[4.25741]→[4.25741:25765](∅→∅),[4.25765]→[4.7817:7863](∅→∅),[4.7863]→[4.25795:25872](∅→∅),[4.25795]→[4.25795:25872](∅→∅)

unsafe fn unchecked_current_ptr(page: crate::Page, c: &Self::Cursor) -> *const u8 {
assert!(c.cur >= 0 && c.cur < c.total as isize);
page.data.as_ptr().add(if c.is_leaf {
let f = tuple_size::<K, V>();
let al = K::ALIGN.max(V::ALIGN);
let hdr = (HDR + al - 1) & !(al - 1);
hdr + c.cur as usize * f
} else {
(u64::from_le(*(page.data.as_ptr().add(HDR + c.cur as usize * 8) as *const u64))
& 0xfff) as usize
})
}
fn current_size(page: crate::Page, c: &Self::Cursor) -> usize {
assert!(c.cur >= 0 && c.cur < c.total as isize);
unsafe {
if c.is_leaf {
tuple_size::<K, V>()
} else {
8 + entry_size::<K, V>(page.data.as_ptr().add(
(u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur as usize))
& 0xfff) as usize,
))
}
}
}
fn move_next(_page: crate::Page, c: &mut Self::Cursor) -> bool {
if c.cur < c.total as isize {
c.cur += 1;
true
} else {
false
}
}
fn move_prev(_page: crate::Page, 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().offset(HDR as isize + c.cur * 8) as *const u64) };
u64::from_le(off) & !0xfff
}
}
fn set_cursor<'a, T: LoadPage>(
txn: &T,
page: crate::Page,
c: &mut PageCursor,
k0: &K,
v0: Option<&V>,
) -> Result<(&'a K, &'a V, u64), usize> {
unsafe {
let lookup = lookup(txn, page, c, k0, v0);
let result;
c.cur = match lookup {
Ok(n) => {
result = if c.is_leaf {
let f = tuple_size::<K, V>();
let off = {
let al = K::ALIGN.max(V::ALIGN);
let hdr_size = (HDR + al - 1) & !(al - 1);
(0, (hdr_size + f * n) as u16)
};
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
}
}

fn split_at(_: crate::Page, c: &Self::Cursor) -> (Self::Cursor, Self::Cursor) {
(
PageCursor {
cur: 0,
total: c.cur.max(0) as usize,
is_leaf: c.is_leaf,
},
*c,
)

[4.20175]

[4.26184]

if m.skip_first {
total -= <Page<K, V> as BTreePage<K, V>>::current_size(m.page.as_page(), &m.c1) as usize;
edit in sanakirja-core/src/btree/page.rs at line 471

[4.26190]

[4.26190]

total
replacement in sanakirja-core/src/btree/page.rs at line 545

[4.34631]→[4.8331:8349](∅→∅)

unsafe fn modify<

[4.12021]

[4.5384]

fn modify<
replacement in sanakirja-core/src/btree/page.rs at line 582

[4.35449]→[4.8729:8746](∅→∅)

unsafe fn merge<

[4.35449]

[4.5982]

fn merge<
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 24

[4.1271]→[4.1944:2012](∅→∅)

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

[4.1271]

[4.1336]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
edit in sanakirja-core/src/btree/page/rebalance.rs at line 28

[4.1414]

[4.1414]

true,
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 67

[4.8171]→[4.2392:2525](∅→∅),[4.1491]→[4.2392:2525](∅→∅),[4.2392]→[4.2392:2525](∅→∅)

if let Put::Ok(Ok { page, freed }) =
<Page<K, V>>::put(txn, new_left.0, true, &lc, m.mid.0, m.mid.1, None, 0, rl)?
{

[4.1491]

[4.2525]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
txn, new_left.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,
)? {
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 153

[3.8569]→[4.2893:2961](∅→∅),[4.4799]→[4.2893:2961](∅→∅)

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

[3.8569]

[4.4864]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
edit in sanakirja-core/src/btree/page/rebalance.rs at line 157

[4.4942]

[4.4942]

true,
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 193

[3.8722]→[3.8722:8857](∅→∅)

if let Put::Ok(Ok { page, freed }) =
<Page<K, V>>::put(txn, new_right.0, true, &rc, m.mid.0, m.mid.1, None, r0, rl)?
{

[3.8722]

[3.8857]

if let Put::Ok(Ok { page, freed }) = <Page<K, V>>::put(
txn,
new_right.0,
true,
false,
&rc,
m.mid.0,
m.mid.1,
None,
r0,
rl,
)? {
edit in sanakirja-core/src/btree/mod.rs at line 31

[4.50264]→[4.46176:46226](∅→∅),[4.8054]→[4.46176:46226](∅→∅),[4.13213]→[4.46176:46226](∅→∅),[4.46176]→[4.46176:46226](∅→∅)

type Cursor: Clone + Copy + core::fmt::Debug;
edit in sanakirja-core/src/btree/mod.rs at line 32

[4.46263]

[4.8428]

type Cursor: Clone + Copy + core::fmt::Debug;

/// Whether this cursor is at the end of the page.
fn is_empty(p: Page, c: &Self::Cursor) -> bool;

/// Whether this cursor is strictly before the first element.
fn is_init(p: Page, c: &Self::Cursor) -> bool;
edit in sanakirja-core/src/btree/mod.rs at line 44

[4.8568]

[4.8568]

/// Returns a cursor set to the first element of the page
/// (i.e. 0). If the page is empty, the returned cursor might be
/// empty.
replacement in sanakirja-core/src/btree/mod.rs at line 51

[4.8699]→[4.8699:8735](∅→∅)

Self::move_next(p, &mut c);

[4.8699]

[4.8735]

Self::move_next(&mut c);
edit in sanakirja-core/src/btree/mod.rs at line 55

[4.8791]

[4.8791]
edit in sanakirja-core/src/btree/mod.rs at line 59

[4.8929]

[4.8929]

/// Returns a cursor set to the last element of the page. If the
/// cursor is empty, this is the same as `cursor_before`.
replacement in sanakirja-core/src/btree/mod.rs at line 64

[4.9018]→[4.9018:9054](∅→∅)

Self::move_prev(p, &mut c);

[4.9018]

[4.9054]

Self::move_prev(&mut c);
edit in sanakirja-core/src/btree/mod.rs at line 67

[4.9070]

[4.8055]

/// Return the element currently pointed to by the cursor (if the
/// cursor is not before or after the elements of the page), and
/// move the cursor to the next element.
replacement in sanakirja-core/src/btree/mod.rs at line 77

[4.13380]→[4.28545:28580](∅→∅),[4.28545]→[4.28545:28580](∅→∅)

Self::move_next(p, c);

[4.13380]

[4.28580]

Self::move_next(c);
edit in sanakirja-core/src/btree/mod.rs at line 83

[4.46676]

[4.8193]

/// Move the cursor to the previous element, and return that
/// element. In that sense, this is not the symmetric of `next`.
replacement in sanakirja-core/src/btree/mod.rs at line 91

[4.8330]→[4.28727:28762](∅→∅),[4.13487]→[4.28727:28762](∅→∅),[4.28727]→[4.28727:28762](∅→∅)

if Self::move_prev(p, c) {

[4.8330]

[4.13488]

if Self::move_prev(c) {
replacement in sanakirja-core/src/btree/mod.rs at line 97

[4.28844]→[4.28844:28958](∅→∅)

fn move_next(p: Page, c: &mut Self::Cursor) -> bool;
fn move_prev(p: Page, c: &mut Self::Cursor) -> bool;

[4.28844]

[4.8475]

/// Move the cursor to the next position. Returns whether the
/// cursor was actually moved (i.e. `true` if and only if the
/// cursor isn't at the end of the page already).
fn move_next(c: &mut Self::Cursor) -> bool;

/// Move the cursor to the previous position. Returns whether the
/// cursor was actually moved (i.e. `true` if and only if the
/// cursor isn't strictly before the page).
fn move_prev(c: &mut Self::Cursor) -> bool;

/// Returns the current element, if the cursor is pointing at one.
replacement in sanakirja-core/src/btree/mod.rs at line 114

[4.9109]→[4.29221:29298](∅→∅),[4.47041]→[4.29221:29298](∅→∅)

unsafe fn unchecked_current_ptr(p: Page, c: &Self::Cursor) -> *const u8;

[4.9109]

[4.29298]

/// Returns the size of the entry pointed to by the cursor.
edit in sanakirja-core/src/btree/mod.rs at line 117

[4.29355]

[4.29355]

/// Returns the left child of the entry pointed to by the cursor.
edit in sanakirja-core/src/btree/mod.rs at line 120

[4.29408]

[4.29408]

/// Returns the right child of the entry pointed to by the cursor.
edit in sanakirja-core/src/btree/mod.rs at line 123

[4.29462]

[4.13803]

/// Sets the cursor to the last element less than or equal to `k0`
/// if `v0.is_none()`, and to `(k0, v0)` if `v0.is_some()`.
replacement in sanakirja-core/src/btree/mod.rs at line 133

[4.8722]→[4.29531:29659](∅→∅),[4.29531]→[4.29531:29659](∅→∅),[4.29659]→[4.9110:9161](∅→∅)

fn split_at(p: Page, c: &Self::Cursor) -> (Self::Cursor, Self::Cursor);
fn is_empty(p: Page, c: &Self::Cursor) -> bool;
fn is_init(p: Page, c: &Self::Cursor) -> bool;

[4.8722]

[4.47598]

fn split_at(c: &Self::Cursor) -> (Self::Cursor, Self::Cursor);
edit in sanakirja-core/src/btree/mod.rs at line 165

[4.48225]

[4.29719]

/// Initialise a page.
replacement in sanakirja-core/src/btree/mod.rs at line 167

[4.29752]→[4.29752:29786](∅→∅)

fn clean(page: &mut MutPage);

[4.29752]

[4.14162]

/// Add an entry to the page, possibly splitting the page in the
/// process.
edit in sanakirja-core/src/btree/mod.rs at line 174

[4.48362]

[4.48362]

replace: bool,
edit in sanakirja-core/src/btree/mod.rs at line 183

[4.48501]

[4.14193]

/// Update the left child of the position pointed to by the
/// cursor.
edit in sanakirja-core/src/btree/mod.rs at line 194

[4.2050]

[4.2050]

/// Save a leaf entry as a replacement, when we delete at an
/// internal node. This can be a pointer to the leaf if the leaf
/// isn't mutated, or the actual value, or something else.
replacement in sanakirja-core/src/btree/mod.rs at line 200

[4.2112]→[4.2112:2177](∅→∅)

unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V);

[4.2112]

[4.2177]

/// Recover the saved value.
fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V);
edit in sanakirja-core/src/btree/mod.rs at line 203

[4.2178]

[4.8946]

/// Delete an entry on the page, returning the resuting page along
/// with the offset of the freed page (or 0 if no page was freed,
/// i.e. if `page` is mutable).
replacement in sanakirja-core/src/btree/mod.rs at line 214

[4.48758]→[4.14344:14378](∅→∅),[4.14378]→[4.48778:48799](∅→∅),[4.48778]→[4.48778:48799](∅→∅),[4.48799]→[4.29931:29954](∅→∅),[4.29954]→[4.48819:48906](∅→∅),[4.48819]→[4.48819:48906](∅→∅),[4.48906]→[4.13913:13951](∅→∅),[4.13951]→[4.48906:48938](∅→∅),[4.48906]→[4.48906:48938](∅→∅),[4.48938]→[4.13952:13994](∅→∅),[4.13994]→[4.49207:49208](∅→∅),[4.49207]→[4.49207:49208](∅→∅)

fn replace<'a, T: AllocPage>(
txn: &mut T,
page: CowPage,
mutable: bool,
c: &Self::Cursor,
k0: &'a K,
v0: &'a V,
k1v1: Option<(&'a K, &'a V)>,
l: u64,
r: u64,
) -> Result<Put<'a, K, V>, T::Error>;

[4.48758]

[4.14379]

/// Merge, rebalance or update a concatenation.
edit in sanakirja-core/src/btree/mod.rs at line 219

[4.49343]→[4.49343:49344](∅→∅),[4.49344]→[4.14473:14506](∅→∅),[4.14506]→[4.49363:49384](∅→∅),[4.49363]→[4.49363:49384](∅→∅),[4.49384]→[4.14507:14553](∅→∅),[4.30087]→[4.49429:49472](∅→∅),[4.14553]→[4.49429:49472](∅→∅),[4.49429]→[4.49429:49472](∅→∅),[4.49472]→[3.10307:10342](∅→∅),[3.10342]→[4.5469:5507](∅→∅),[4.49472]→[4.5469:5507](∅→∅),[4.5507]→[4.30129:30159](∅→∅),[4.30129]→[4.30129:30159](∅→∅),[4.30159]→[4.13995:14080](∅→∅),[4.14080]→[4.49773:49794](∅→∅),[4.30238]→[4.49773:49794](∅→∅),[4.5589]→[4.49773:49794](∅→∅),[4.49773]→[4.49773:49794](∅→∅),[4.49794]→[4.14081:14162](∅→∅),[4.14162]→[4.50115:50129](∅→∅),[4.30314]→[4.50115:50129](∅→∅),[4.5667]→[4.50115:50129](∅→∅),[4.50115]→[4.50115:50129](∅→∅),[4.50129]→[4.30315:30332](∅→∅),[4.30332]→[4.3391:3421](∅→∅),[4.3421]→[3.10343:10475](∅→∅),[3.10475]→[4.5668:5700](∅→∅),[4.3742]→[4.5668:5700](∅→∅),[4.5700]→[4.9095:9224](∅→∅),[4.9224]→[4.5701:5825](∅→∅),[4.3853]→[4.5701:5825](∅→∅),[4.5825]→[4.9225:9352](∅→∅),[4.5913]→[4.3853:3867](∅→∅),[4.9352]→[4.3853:3867](∅→∅),[4.3853]→[4.3853:3867](∅→∅),[4.30617]→[4.50129:50146](∅→∅),[4.3867]→[4.50129:50146](∅→∅),[4.50129]→[4.50129:50146](∅→∅),[4.50146]→[4.14554:14606](∅→∅)

fn modify<'a, T: AllocPage>(
txn: &mut T,
m: &mut ModifiedPage<'a, K, V, Self>,
) -> Result<Put<'a, K, V>, T::Error> {
debug!("modify: {:?}", m);
if let Some((k, v)) = m.ins {
if m.skip_first {
Self::replace(txn, m.page, m.mutable, &m.c1, k, v, m.ins2, m.l, m.r)
} else {
Self::put(txn, m.page, m.mutable, &m.c1, k, v, m.ins2, m.l, m.r)
}
} else {
if m.skip_first {
let (page, freed) = Self::del(txn, m.page, m.mutable, &m.c1, m.l)?;
Ok(Put::Ok(Ok { freed, page }))
} else if m.l > 0 {
Ok(Put::Ok(Self::update_left_child(
txn, m.page, m.mutable, &m.c1, m.l,
)?))
} else {
let mut c1 = m.c1.clone();
Self::move_next(m.page.as_page(), &mut c1);
Ok(Put::Ok(Self::update_left_child(
txn, m.page, m.mutable, &c1, m.r,
)?))
}
}
}

fn size(m: &ModifiedPage<K, V, Self>) -> usize;
replacement in sanakirja-core/src/btree/mod.rs at line 270

[4.51424]→[4.30856:30912](∅→∅)

P::move_next(self.page.as_page(), &mut c1);

[4.51424]

[4.51471]

P::move_next(&mut c1);
replacement in sanakirja-core/src/btree/del.rs at line 179

[4.9929]→[4.9929:9998](∅→∅)

let (c0, c1) = P::split_at(curs0.page.as_page(), &curs0.cursor);

[4.9929]

[4.1714]

let (c0, c1) = P::split_at(&curs0.cursor);
replacement in sanakirja-core/src/btree/del.rs at line 234

[4.2423]→[4.2423:2496](∅→∅)

let (k0, v0) = unsafe { P::from_saved(k0v0.as_ref().unwrap()) };

[4.2423]

[4.2496]

let (k0, v0) = P::from_saved(k0v0.as_ref().unwrap());
replacement in sanakirja-core/src/btree/del.rs at line 306

[4.34502]→[4.10499:10570](∅→∅)

let (c0, c1) = P::split_at(curs.page.as_page(), &curs.cursor);

[4.34502]

[4.34609]

let (c0, c1) = P::split_at(&curs.cursor);
replacement in sanakirja-core/src/btree/del.rs at line 368

[4.3208]→[4.3208:3280](∅→∅)

last_op.ins = Some(unsafe { P::from_saved(k0v0) });

[4.3208]

[4.3280]

last_op.ins = Some(P::from_saved(k0v0));
replacement in sanakirja-core/src/btree/del.rs at line 397

[4.3342]→[4.3342:3414](∅→∅)

last_op.ins = Some(unsafe { P::from_saved(k0v0) });

[4.3342]

[4.3414]

last_op.ins = Some(P::from_saved(k0v0));
replacement in sanakirja-core/src/btree/del.rs at line 413

[4.6177]→[4.6177:6243](∅→∅)

let (k0, _) = unsafe { P::from_saved(k0v0) };

[4.6177]

[4.6243]

let (k0, _) = P::from_saved(k0v0);
replacement in sanakirja-core/src/btree/del.rs at line 477

[4.22255]→[4.22255:22308](∅→∅)

P::move_next(m.page.as_page(), &mut c1);

[4.22255]

[4.22308]

P::move_next(&mut c1);
replacement in sanakirja-core/src/btree/del.rs at line 554

[4.7364]→[4.38633:38675](∅→∅),[4.38633]→[4.38633:38675](∅→∅)

match P::modify(txn, &mut last_op)? {

[4.7364]

[4.7365]

match modify::<_, K, V, P>(txn, &mut last_op)? {
replacement in sanakirja-core/src/btree/del.rs at line 570

[4.10686]→[4.10686:10738](∅→∅),[4.10738]→[4.7633:7713](∅→∅)

P::move_next(page.0.as_page(), &mut c);
P::put(txn, page.0, true, &c, k, v, None, l.0.offset, r.0.offset)?;

[4.10686]

[4.3820]

P::move_next(&mut c);
P::put(
txn, page.0, true, false, &c, k, v, None, l.0.offset, r.0.offset,
)?;
replacement in sanakirja-core/src/btree/del.rs at line 575

[4.3885]→[4.3885:3947](∅→∅)

let (k0, _) = unsafe { P::from_saved(k0v0) };

[4.3885]

[4.7714]

let (k0, _) = P::from_saved(k0v0);
edit in sanakirja-core/src/btree/del.rs at line 590

[4.63669]

/// Apply the modifications to a page.
fn modify<
'a,
T: AllocPage,
K: Representable + ?Sized,
V: Representable + ?Sized,
P: BTreeMutPage<K, V>,
>(
txn: &mut T,
m: &mut ModifiedPage<'a, K, V, P>,
) -> Result<Put<'a, K, V>, T::Error> {
debug!("modify: {:?}", m);
if let Some((k, v)) = m.ins {
P::put(
txn,
m.page,
m.mutable,
m.skip_first,
&m.c1,
k,
v,
m.ins2,
m.l,
m.r,
)
} else {
if m.skip_first {
let (page, freed) = P::del(txn, m.page, m.mutable, &m.c1, m.l)?;
Ok(Put::Ok(Ok { freed, page }))
} else if m.l > 0 {
Ok(Put::Ok(P::update_left_child(
txn, m.page, m.mutable, &m.c1, m.l,
)?))
} else {
let mut c1 = m.c1.clone();
P::move_next(&mut c1);
Ok(Put::Ok(P::update_left_child(
txn, m.page, m.mutable, &c1, m.r,
)?))
}
}
}
replacement in sanakirja-core/src/btree/cursor.rs at line 200

[4.84]→[4.2293:2368](∅→∅)

P::move_next(current.page.as_page(), &mut current.cursor);

[4.84]

[4.2368]

P::move_next(&mut current.cursor);
replacement in sanakirja-core/src/btree/cursor.rs at line 211

[4.8186]→[4.2447:2522](∅→∅),[4.12721]→[4.2447:2522](∅→∅)

P::move_next(current.page.as_page(), &mut current.cursor);

[4.8186]

[4.12796]

P::move_next(&mut current.cursor);
replacement in sanakirja-core/src/btree/cursor.rs at line 246

[4.2716]→[4.2716:2795](∅→∅)

P::move_prev(current.page.as_page(), &mut current.cursor);

[4.2716]

[4.13838]

P::move_prev(&mut current.cursor);
replacement in sanakirja-core/src/btree/cursor.rs at line 259

[4.2902]→[4.2902:2981](∅→∅)

P::move_prev(current.page.as_page(), &mut current.cursor);

[4.2902]

[4.70713]

P::move_prev(&mut current.cursor);
replacement in sanakirja-core/src/btree/cursor.rs at line 266

[4.3068]→[4.3068:3143](∅→∅)

P::move_prev(current.page.as_page(), &mut current.cursor);

[4.3068]

[4.14441]

P::move_prev(&mut current.cursor);