Cleanup

[?]

Feb 13, 2021, 3:32 PM

HN6Z5DU4WYMAIOOSNVHLIIMNF6Q53TNJ7YC27SLKWNXVYCTACQKQC

Dependencies

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

Change contents

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

[3.91]

[3.92]

//! This crate defines tools to implement datastructures that can live
//! in main memory or on-disk, meaning that their natural habitat is
//! memory-mapped files, but if that environment is threatened, might
//! seek refuge in lower-level environments.
//!
//! One core building block of this library is the notion of virtual
//! memory pages, which are allocated and freed by an
//! externally-provided allocator (see how the `sanakirja` crate does
//! this). The particular implementation used here is meant to allow a
//! transactional system with readers reading the structures
//! concurrently with one writer at a time.
//!
//! At the moment, only B trees are implemented, as well as three
//! important traits:
//!
//! - [`Representable`] is the trait of types that can be written to
//! disk and read from the disk.
//! - [`LoadPage`] is a trait used to get a pointer to a page. In the
//! most basic version, this may just return a pointer to the file,
//! offset by the requested offset. In more sophisticated versions,
//! this can be used to encrypt and compress pages.
//! - [`AllocPage`] allocates and frees pages, because as
//! datastructures need to be persisted on disk, we can't rely on
//! Rust's memory management to do it for us. Users of this crate
//! don't have to worry about this though.
edit in sanakirja-core/src/lib.rs at line 55

[3.764]

[3.0]

/// A macro to implement [`Representable`] on "plain" types,
/// i.e. fixed-sized types that are `repr(C)` and don't hold
/// references to out-of-tree pages.
edit in sanakirja-core/src/lib.rs at line 151

[3.2399]

[3.2399]

/// Representation of a page.
replacement in sanakirja-core/src/lib.rs at line 166

[3.448]→[3.448:495](∅→∅)

unsafe { core::mem::transmute(*self) }

[3.448]

[3.0]

Page {
data: unsafe { &*(self.data as *const [u8; PAGE_SIZE]) },
offset: self.offset,
}
edit in sanakirja-core/src/lib.rs at line 187

[3.403]

[3.2723]

}
}

impl CowPage {
pub fn is_dirty(&self) -> bool {
unsafe { (*self.data) & 1 != 0 }
edit in sanakirja-core/src/btree/put.rs at line 1

[3.3448]→[3.3449:3927](∅→∅)

// Copyright 2015 Pierre-Étienne Meunier and Florent Becker. See the
// COPYRIGHT file at the top-level directory of this distribution and
// at http://pijul.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
edit in sanakirja-core/src/btree/put.rs at line 123

[3.883]

[3.883]

let cursor = P::cursor_first(&p.0);
replacement in sanakirja-core/src/btree/put.rs at line 125

[3.920]→[3.5763:5791](∅→∅),[3.5763]→[3.5763:5791](∅→∅)

P::put(

[3.920]

[3.5791]

if let Put::Ok(p) = P::put(
replacement in sanakirja-core/src/btree/put.rs at line 130

[3.79]→[3.175:232](∅→∅),[3.5879]→[3.175:232](∅→∅)

&P::cursor_first(p.0.as_page()),

[3.79]

[3.5927]

&cursor,
replacement in sanakirja-core/src/btree/put.rs at line 136

[3.6078]→[3.6078:6102](∅→∅),[3.6102]→[2.2089:2133](∅→∅),[2.2133]→[3.6102:6136](∅→∅),[3.6102]→[3.6102:6136](∅→∅)

)?;
// Return the new root.
return Ok(p);

[3.6078]

[3.6641]

)? {
// Return the new root.
return Ok(p.page);
} else {
unreachable!()
}
replacement in sanakirja-core/src/btree/put.rs at line 208

[2.3610]→[2.3610:3667](∅→∅)

let mut c = P::cursor_first(cur.page.as_page());

[2.3610]

[3.1067]

let mut c = P::cursor_first(&cur.page);
replacement in sanakirja-core/src/btree/page_unsized.rs at line 91

[3.4964]→[3.4964:5030](∅→∅)

let page = if mutable && Self::is_dirty(page.as_page()) {

[3.4814]

[3.5030]

let page = if mutable && page.is_dirty() {
replacement in sanakirja-core/src/btree/page_unsized.rs at line 103

[3.5580]→[3.5580:5652](∅→∅)

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

[3.5580]

[3.5652]

let b = if page.is_dirty() { 1 } else { 0 };
replacement in sanakirja-core/src/btree/page_unsized.rs at line 123

[3.710]→[3.594:649](∅→∅)

if mutable && Self::is_dirty(page.as_page()) {

[3.710]

[3.6199]

if mutable && page.is_dirty() {
replacement in sanakirja-core/src/btree/page_unsized.rs at line 215

[3.9736]→[3.9736:10008](∅→∅)

let b0 = if Self::is_dirty(m.modified.page.as_page()) {
1
} else {
0
};
let b1 = if Self::is_dirty(m.other.as_page()) {
1
} else {
0
};

[3.9736]

[3.10008]

let b0 = if m.modified.page.is_dirty() { 1 } else { 0 };
let b1 = if m.other.is_dirty() { 1 } else { 0 };
replacement in sanakirja-core/src/btree/page_unsized.rs at line 223

[3.10222]→[3.50:106](∅→∅)

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

[3.10222]

[3.10286]

let rc = PageCursor::new(&m.other, 0);
replacement in sanakirja-core/src/btree/page_unsized.rs at line 289

[3.1440]→[3.11689:11833](∅→∅),[3.11689]→[3.11689:11833](∅→∅)

fn is_dirty(page: crate::Page) -> bool {
header(page).is_dirty()
}

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

[3.1440]

[3.1215]

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

[3.1251]→[3.1251:1310](∅→∅)

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

[3.1251]

[3.1310]

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

[3.137]→[3.1335:1390](∅→∅),[3.11890]→[3.1335:1390](∅→∅)

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

[3.137]

[3.138]

fn cursor_before(p: &crate::CowPage) -> Self::Cursor {
replacement in sanakirja-core/src/btree/page_unsized.rs at line 300

[3.12099]→[3.1418:1472](∅→∅)

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

[3.12099]

[3.170]

fn cursor_after(p: &crate::CowPage) -> Self::Cursor {
replacement in sanakirja-core/src/btree/page_unsized.rs at line 506

[3.323]→[3.1647:1707](∅→∅),[3.386]→[3.3554:3583](∅→∅),[3.1707]→[3.3554:3583](∅→∅),[3.3554]→[3.3554:3583](∅→∅)

pub(super) fn new(p: crate::Page, cur: isize) -> Self {
let hdr = header(p);

[3.323]

[3.3583]

pub(super) fn new(p: &crate::CowPage, cur: isize) -> Self {
let hdr = unsafe { &*(p.data as *const Header) };
replacement in sanakirja-core/src/btree/page_unsized.rs at line 515

[3.3747]→[3.1708:1758](∅→∅),[3.462]→[3.3802:3831](∅→∅),[3.1758]→[3.3802:3831](∅→∅),[3.3802]→[3.3802:3831](∅→∅)

pub(super) fn after(p: crate::Page) -> Self {
let hdr = header(p);

[3.3747]

[3.3831]

pub(super) fn after(p: &crate::CowPage) -> Self {
let hdr = unsafe { &*(p.data as *const Header) };
replacement in sanakirja-core/src/btree/page_unsized.rs at line 586

[3.20399]→[3.560:620](∅→∅)

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

[3.20399]

[3.20467]

let mut rc = PageCursor::new(&m.other, 0);
replacement in sanakirja-core/src/btree/page_unsized.rs at line 593

[3.20764]→[3.621:681](∅→∅)

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

[3.20764]

[3.20832]

let mut rc = PageCursor::new(&m.other, 0);
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 18

[3.23324]→[3.682:741](∅→∅)

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

[3.23324]

[3.23384]

let rc = super::PageCursor::new(&m.other, 0);
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 67

[3.2129]→[3.2129:2188](∅→∅)

let lc = PageCursor::after(m.modified.page.as_page());

[3.2129]

[3.1699]

let lc = PageCursor::after(&m.modified.page);
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 110

[3.25516]→[3.860:927](∅→∅)

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

[3.25516]

[3.25584]

let rc = super::PageCursor::new(&m.modified.page, 0);
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 158

[3.2850]→[3.1927:1987](∅→∅)

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

[3.2850]

[3.1987]

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

[3.2144]→[3.2985:3040](∅→∅),[3.2985]→[3.2985:3040](∅→∅)

assert_eq!(new_right.0.offset, page.0.offset);
edit in sanakirja-core/src/btree/page_unsized/put.rs at line 109

[3.29577]

[3.29577]

debug!("split_unsized");
replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 142

[3.757]→[3.757:767](∅→∅),[3.767]→[3.4274:4317](∅→∅)

}
if replace {
continue;

[3.757]

[3.4317]

if replace {
continue;
}
edit in sanakirja-core/src/btree/page_unsized/put.rs at line 147

[3.30357]→[3.769:832](∅→∅)

debug!("{:?} {:?} {:?} {:?}", r, off, is_left, total);
replacement in sanakirja-core/src/btree/page_unsized/header.rs at line 68

[3.16991]→[3.16991:17048](∅→∅)

pub fn header<'a>(page: crate::Page<'a>) -> &'a Header {

[3.16991]

[3.17048]

pub(crate) fn header<'a>(page: crate::Page<'a>) -> &'a Header {
edit in sanakirja-core/src/btree/page.rs at line 31

[3.2227]→[3.2227:2311](∅→∅)

fn is_dirty(page: crate::Page) -> bool {
header(page).is_dirty()
}
replacement in sanakirja-core/src/btree/page.rs at line 33

[3.2342]→[3.2342:2402](∅→∅)

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

[3.2342]

[3.2402]

fn is_empty(c: &Self::Cursor) -> bool {
replacement in sanakirja-core/src/btree/page.rs at line 37

[3.2443]→[3.2443:2502](∅→∅)

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

[3.2443]

[3.2502]

fn is_init(c: &Self::Cursor) -> bool {
replacement in sanakirja-core/src/btree/page.rs at line 41

[3.2527]→[3.2527:2582](∅→∅)

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

[3.2527]

[3.2582]

fn cursor_before(p: &crate::CowPage) -> Self::Cursor {
replacement in sanakirja-core/src/btree/page.rs at line 45

[3.2620]→[3.2620:2674](∅→∅)

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

[3.2620]

[3.2674]

fn cursor_after(p: &crate::CowPage) -> Self::Cursor {
replacement in sanakirja-core/src/btree/page.rs at line 259

[3.1671]→[3.2130:2196](∅→∅),[3.2130]→[3.2130:2196](∅→∅)

let page = if mutable && Self::is_dirty(page.as_page()) {

[3.11691]

[3.11747]

let page = if mutable && page.is_dirty() {
replacement in sanakirja-core/src/btree/page.rs at line 271

[3.1768]→[3.1352:1438](∅→∅)

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

[3.1768]

[3.2644]

freed = page.offset | if page.is_dirty() { 1 } else { 0 };
replacement in sanakirja-core/src/btree/page.rs at line 290

[3.5196]→[3.3427:3482](∅→∅)

if mutable && Self::is_dirty(page.as_page()) {

[3.5196]

[3.2803]

if mutable && page.is_dirty() {
replacement in sanakirja-core/src/btree/page.rs at line 386

[3.16918]→[3.5633:5701](∅→∅),[3.5701]→[3.16976:17048](∅→∅),[3.16976]→[3.16976:17048](∅→∅),[3.17048]→[3.3219:3351](∅→∅)

let b0 = if Self::is_dirty(m.modified.page.as_page()) {
1
} else {
0
};
let b1 = if Self::is_dirty(m.other.as_page()) {
1
} else {
0
};

[3.16918]

[3.17114]

let b0 = if m.modified.page.is_dirty() { 1 } else { 0 };
let b1 = if m.other.is_dirty() { 1 } else { 0 };
replacement in sanakirja-core/src/btree/page.rs at line 394

[3.17328]→[3.1020:1076](∅→∅)

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

[3.17328]

[3.5843]

let rc = PageCursor::new(&m.other, 0);
edit in sanakirja-core/src/btree/page.rs at line 465

[3.136]

[3.1890]

v0: Option<&V>,
edit in sanakirja-core/src/btree/page.rs at line 471

[3.268]

[3.268]

Ordering::Less => n += 1,
Ordering::Greater => return Err(n),
Ordering::Equal => {
if let Some(v0) = v0 {
match sm.v.compare(txn, v0) {
Ordering::Less => n += 1,
Ordering::Greater => return Err(n),
Ordering::Equal => return Ok(n),
}
} else {
return Ok(n);
}
}
}
}
Err(n)
}

unsafe fn cmp<T: LoadPage, K: Representable, V: Representable>(
txn: &T,
k0: &K,
v0: Option<&V>,
p: &[u8; 4096],
off: u64,
) -> Ordering {
let off = u64::from_le(off) & 0xfff;
let (k, v) = read::<T, K, V>(txn, p.as_ptr().offset(off as isize & 0xfff));
let k = K::from_raw_ptr(txn, k);
match k.compare(txn, k0) {
Ordering::Equal => {
if let Some(v0) = v0 {
let v = V::from_raw_ptr(txn, v);
v.compare(txn, v0)
} else {
Ordering::Equal
}
}
o => o,
}
}

unsafe fn internal_search<T: LoadPage, K: Representable, V: Representable>(
txn: &T,
k0: &K,
v0: Option<&V>,
s: &[u64],
p: &[u8; 4096],
) -> Result<usize, usize> {
let mut a = 0;
let mut b = s.len();
for _ in 0..4 {
let mid = (a + b) / 2;
match cmp(txn, k0, v0, p, s[mid]) {
Ordering::Less => a = mid,
Ordering::Greater => b = mid,
Ordering::Equal => b = mid + 1,
}
}
let mut n = a;
for &off in &s[a..b] {
match cmp(txn, k0, v0, p, off) {
replacement in sanakirja-core/src/btree/page.rs at line 557

[3.355]→[3.45837:46036](∅→∅),[3.45837]→[3.45837:46036](∅→∅),[3.46036]→[3.10485:10502](∅→∅),[3.10485]→[3.10485:10502](∅→∅),[3.10502]→[3.487:576](∅→∅),[3.46098]→[3.11275:11285](∅→∅),[3.576]→[3.11275:11285](∅→∅),[3.11275]→[3.11275:11285](∅→∅)

if let Some(v0) = v0 {
s.binary_search_by(|tup| match tup.k.compare(txn, &k0) {
Ordering::Equal => tup.v.compare(txn, &v0),
c => c,
})
} else {
// leaf_binary_search(txn, k0, s)
leaf_linear_search(txn, k0, s)
}

[3.45837]

[3.11285]

leaf_linear_search(txn, k0, v0, s)
replacement in sanakirja-core/src/btree/page.rs at line 563

[3.5223]→[3.11416:11540](∅→∅),[3.11416]→[3.11416:11540](∅→∅),[3.11540]→[3.4842:5175](∅→∅),[3.5175]→[3.6023:6045](∅→∅),[3.6045]→[3.5334:5384](∅→∅),[3.5198]→[3.5334:5384](∅→∅),[3.5334]→[3.5334:5384](∅→∅),[3.5384]→[3.11717:11842](∅→∅),[3.11717]→[3.11717:11842](∅→∅),[3.11842]→[3.5199:5383](∅→∅),[3.5424]→[3.11987:12012](∅→∅),[3.5383]→[3.11987:12012](∅→∅),[3.11987]→[3.11987:12012](∅→∅)

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.5223]

[3.12012]

internal_search(txn, k0, v0, s, page.data)
replacement in sanakirja-core/src/btree/page.rs at line 617

[3.6207]→[3.1250:1310](∅→∅)

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

[3.6207]

[3.20657]

let mut rc = PageCursor::new(&m.other, 0);
replacement in sanakirja-core/src/btree/page.rs at line 624

[3.36081]→[3.1311:1371](∅→∅)

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

[3.36081]

[3.21005]

let mut rc = PageCursor::new(&m.other, 0);
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 17

[3.823]→[3.1372:1431](∅→∅)

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

[3.823]

[3.883]

let rc = super::PageCursor::new(&m.other, 0);
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 66

[3.1736]→[3.1432:1491](∅→∅)

let lc = PageCursor::after(m.modified.page.as_page());

[3.1736]

[3.8453]

let lc = PageCursor::after(&m.modified.page);
replacement in sanakirja-core/src/btree/page/rebalance.rs at line 147

[3.4422]→[3.1543:1610](∅→∅)

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

[3.4422]

[3.4490]

let rc = super::PageCursor::new(&m.modified.page, 0);
replacement in sanakirja-core/src/btree/page/put.rs at line 129

[3.9805]→[3.9805:9863](∅→∅)

left = unsafe { core::mem::transmute(page) };

[3.9805]

[3.9863]

left = MutPage(page);
edit in sanakirja-core/src/btree/mod.rs at line 1

[3.45735]

[3.45736]

//! An implementation of B trees.
edit in sanakirja-core/src/btree/mod.rs at line 32

[3.46226]→[3.46226:46263](∅→∅),[3.46263]→[3.8899:8900](∅→∅)

fn is_dirty(page: Page) -> bool;
replacement in sanakirja-core/src/btree/mod.rs at line 35

[3.9006]→[3.9006:9058](∅→∅)

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

[3.9006]

[3.9058]

fn is_empty(c: &Self::Cursor) -> bool;
replacement in sanakirja-core/src/btree/mod.rs at line 38

[3.9125]→[3.9125:9176](∅→∅)

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

[3.9125]

[3.8428]

fn is_init(c: &Self::Cursor) -> bool;
replacement in sanakirja-core/src/btree/mod.rs at line 42

[3.8521]→[3.8521:8568](∅→∅)

fn cursor_before(p: Page) -> Self::Cursor;

[3.8521]

[3.9177]

fn cursor_before(p: &CowPage) -> Self::Cursor;
replacement in sanakirja-core/src/btree/mod.rs at line 47

[3.9324]→[3.8568:8615](∅→∅),[3.8568]→[3.8568:8615](∅→∅)

fn cursor_first(p: Page) -> Self::Cursor {

[3.9324]

[3.8615]

fn cursor_first(p: &CowPage) -> Self::Cursor {
replacement in sanakirja-core/src/btree/mod.rs at line 57

[3.8883]→[3.8883:8929](∅→∅)

fn cursor_after(p: Page) -> Self::Cursor;

[3.8883]

[3.9361]

fn cursor_after(p: &CowPage) -> Self::Cursor;
replacement in sanakirja-core/src/btree/mod.rs at line 61

[3.9493]→[3.8929:8975](∅→∅),[3.8929]→[3.8929:8975](∅→∅)

fn cursor_last(p: Page) -> Self::Cursor {

[3.9493]

[3.8975]

fn cursor_last(p: &CowPage) -> Self::Cursor {
replacement in sanakirja-core/src/btree/mod.rs at line 249

[3.499]→[3.50527:50557](∅→∅),[3.50527]→[3.50527:50557](∅→∅)

#[derive(Debug, Clone, Copy)]

[3.499]

[3.50557]

#[derive(Debug)]
replacement in sanakirja-core/src/btree/mod.rs at line 391

[3.833]→[3.9369:9428](∅→∅)

let mut cursor = P::cursor_before(page.as_page());

[3.833]

[3.891]

let mut cursor = P::cursor_before(&page);
replacement in sanakirja-core/src/btree/mod.rs at line 431

[3.519]→[3.1777:1912](∅→∅)

let mut stack: [MaybeUninit<cursor::PageCursor<K, V, P>>; cursor::N_CURSORS] =
[MaybeUninit::uninit(); cursor::N_CURSORS];

[3.1776]

[2.4903]

let mut stack: [MaybeUninit<cursor::PageCursor<K, V, P>>; cursor::N_CURSORS] = [
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
MaybeUninit::uninit(),
];
edit in sanakirja-core/src/btree/mod.rs at line 462

[3.2003]

[3.2003]

cursor: P::cursor_before(&page),
edit in sanakirja-core/src/btree/mod.rs at line 464

[3.2017]→[3.2017:2067](∅→∅)

cursor: P::cursor_before(page.as_page()),
edit in sanakirja-core/src/btree/mod.rs at line 490

[3.2740]

[3.2740]

cursor: P::cursor_before(&page),
edit in sanakirja-core/src/btree/mod.rs at line 492

[3.2770]→[3.2770:2836](∅→∅)

cursor: P::cursor_before(page.as_page()),
replacement in sanakirja-core/src/btree/mod.rs at line 494

[3.2877]→[3.2877:2902](∅→∅)

continue

[3.2877]

[3.2902]

continue;
replacement in sanakirja-core/src/btree/mod.rs at line 499

[2.5650]→[3.2917:2962](∅→∅),[3.1286]→[3.2917:2962](∅→∅)

if P::is_dirty(cur.page.as_page()) {

[2.5650]

[3.2962]

if cur.page.is_dirty() {
replacement in sanakirja-core/src/btree/mod.rs at line 506

[3.3103]→[3.3103:3121](∅→∅)

break

[3.3103]

[3.3121]

break;
edit in sanakirja-core/src/btree/del.rs at line 1

[3.52511]→[3.52512:52989](∅→∅)

// Copyright 2015 Pierre-Étienne Meunier and Florent Becker. See the
// COPYRIGHT file at the top-level directory of this distribution and
// at http://pijul.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
edit in sanakirja-core/src/btree/del.rs at line 4

[3.53074]→[3.31220:31232](∅→∅)

use log::*;
replacement in sanakirja-core/src/btree/del.rs at line 20

[3.9635]→[3.53549:53628](∅→∅),[3.53549]→[3.53549:53628](∅→∅),[3.53628]→[3.356:385](∅→∅)

let found = cursor.set(txn, Some((key, value)))?;
if found.is_none() {
debug!("not found");

[3.9635]

[3.53628]

if cursor.set(txn, Some((key, value)))?.is_none() {
// If the key and value weren't found, return.
edit in sanakirja-core/src/btree/del.rs at line 24

[3.53660]

[3.53660]

// Else, the cursor is set on `(key, value)` if `value.is_some()`
// or on the first entry with key `key` else.
//
// We delete that position, which might be in a leaf or in an
// internal node.
edit in sanakirja-core/src/btree/del.rs at line 49

[3.16416]

[3.16416]

//
// Else, that RC doesn't need to be changed, since it's still
// referenced by the same pages as before, just not by the pages
// that are cloned by this deletion.
edit in sanakirja-core/src/btree/del.rs at line 62

[3.16769]

[3.480]
replacement in sanakirja-core/src/btree/del.rs at line 65

[3.594]→[3.54094:54122](∅→∅),[3.30693]→[3.54094:54122](∅→∅),[3.16803]→[3.54094:54122](∅→∅),[3.54094]→[3.54094:54122](∅→∅)

find_min(txn, cursor)?;

[3.594]

[3.6150]

let cur = cursor.current();
let mut left_page = P::right_child(cur.page.as_page(), &cur.cursor);
while left_page > 0 {
let page = txn.load_page(left_page)?;
let curs = P::cursor_first(&page);
left_page = P::left_child(page.as_page(), &curs);
cursor.push(PageCursor { page, cursor: curs });
}
edit in sanakirja-core/src/btree/del.rs at line 78

[3.2442]→[3.775:847](∅→∅)

modify_rc(txn, &last_op, cursor.pointer(), cursor.first_rc_level)?;
edit in sanakirja-core/src/btree/del.rs at line 79

[3.55546]

[3.55546]

// If the leaf is shared with another tree, then since we're
// cloning the leaf, update the reference counts of all the
// references contained in the leaf.
if cursor.pointer() >= cursor.first_rc_level {
modify_rc(txn, &last_op)?;
}
edit in sanakirja-core/src/btree/del.rs at line 99

[3.2510]→[3.30945:30986](∅→∅),[3.17537]→[3.30945:30986](∅→∅),[3.30945]→[3.30945:30986](∅→∅)

debug!("concat = {:?}", concat);
edit in sanakirja-core/src/btree/del.rs at line 106

[3.4264]→[3.6964:7002](∅→∅)

debug!("merge: {:?}", merge);
replacement in sanakirja-core/src/btree/del.rs at line 113

[3.1202]→[3.1202:1380](∅→∅)

// Update the reference counts, potentially freeing the page
// at the current level.
modify_rc(txn, &last_op, cursor.pointer(), cursor.first_rc_level)?;

[3.1202]

[3.59591]

// If the modified page is shared with another tree, we will
// clone it in the next round. Therefore, update the reference
// counts of all the references in the modified page.
if cursor.pointer() >= cursor.first_rc_level {
modify_rc(txn, &last_op)?;
}
replacement in sanakirja-core/src/btree/del.rs at line 123

[3.17985]→[3.10274:10347](∅→∅),[3.10347]→[3.409:445](∅→∅),[3.445]→[3.10383:10410](∅→∅),[3.10383]→[3.10383:10410](∅→∅)

update_root(
txn,
db,
last_op,
k0v0,
cursor.first_rc_level == 0,
&mut free,
)?;

[3.17985]

[3.18066]

let root_is_shared = cursor.first_rc_level == 0;
update_root(txn, db, last_op, k0v0, root_is_shared, &mut free)?;
replacement in sanakirja-core/src/btree/del.rs at line 126

[3.18067]→[3.18067:18161](∅→∅),[3.18161]→[3.1381:1425](∅→∅),[3.1425]→[3.10476:10577](∅→∅)

// Finally, free all the freed pages, now that we don't need to
// read them anymore.
for (n, p) in free.iter().enumerate() {
if p[0] > 0 || p[1] > 0 {
debug!("freeing at level {:?}: {:?}", n, p);
}

[3.18067]

[3.60797]

// Finally, free all the pages marked as free during the deletion,
// now that we don't need to read them anymore.
for p in free.iter() {
edit in sanakirja-core/src/btree/del.rs at line 140

[3.61091]→[3.10578:10598](∅→∅)

debug!("/del");
edit in sanakirja-core/src/btree/del.rs at line 143

[3.61107]→[3.1479:1668](∅→∅),[3.1668]→[3.61107:61149](∅→∅),[3.61107]→[3.61107:61149](∅→∅),[3.61149]→[3.2592:2654](∅→∅),[3.2654]→[3.18206:18252](∅→∅),[3.18206]→[3.18206:18252](∅→∅),[3.18252]→[3.61248:61268](∅→∅),[3.61248]→[3.61248:61268](∅→∅),[3.61268]→[3.18253:18287](∅→∅),[3.18287]→[3.61305:61365](∅→∅),[3.61305]→[3.61305:61365](∅→∅),[3.61365]→[3.9740:9813](∅→∅),[3.31531]→[3.61446:61472](∅→∅),[3.32463]→[3.61446:61472](∅→∅),[3.8627]→[3.61446:61472](∅→∅),[3.61446]→[3.61446:61472](∅→∅),[3.61501]→[3.61501:61547](∅→∅),[3.61547]→[3.9814:9866](∅→∅),[3.9866]→[3.32516:32574](∅→∅),[3.32516]→[3.32516:32574](∅→∅),[3.32574]→[3.5851:5907](∅→∅),[3.5907]→[3.61770:61776](∅→∅),[3.61770]→[3.61770:61776](∅→∅),[3.1526]→[3.61776:61787](∅→∅),[3.8691]→[3.61776:61787](∅→∅),[3.61776]→[3.61776:61787](∅→∅),[3.61787]→[3.31532:31535](∅→∅)

/// Follow the leftmost pages of each page until the leftmost leaf of
/// the subtree starting at `cursor.pointer()`, and set `cursor` to
/// point to the leftmost element of that subtree.
fn find_min<
T: AllocPage + LoadPage,
K: Representable + ?Sized,
V: Representable + ?Sized,
P: BTreeMutPage<K, V> + core::fmt::Debug,
>(
txn: &mut T,
cursor: &mut Cursor<K, V, P>,
) -> Result<(), T::Error> {
let cur = cursor.current();
let mut left_page = P::right_child(cur.page.as_page(), &cur.cursor);
while left_page > 0 {
let page = txn.load_page(left_page)?;
let curs = P::cursor_first(page.as_page());
left_page = P::left_child(page.as_page(), &curs);
cursor.push(PageCursor { page, cursor: curs });
}
Ok(())
}
edit in sanakirja-core/src/btree/del.rs at line 158

[3.1674]→[3.9894:9929](∅→∅)

debug!("curs0 = {:?}", curs0);
replacement in sanakirja-core/src/btree/del.rs at line 162

[3.1716]→[3.1716:1912](∅→∅)

// In this case, we need to save the replacement. If the
// replacement has references, we will increment them later,
// when updating the page where the deletion happens.

[3.1716]

[3.10027]

// In this case, we need to save the replacement, and if this
// leaf is shared with another tree, we also need increment
// the replacement's references, since we are copying it.
edit in sanakirja-core/src/btree/del.rs at line 178

[3.33451]

[3.33451]

c1,
skip_first: true,
edit in sanakirja-core/src/btree/del.rs at line 184

[3.33534]→[3.33534:33580](∅→∅)

c1,
skip_first: true,
edit in sanakirja-core/src/btree/del.rs at line 257

[3.62739]

[3.33871]

// The middle element comes from the page above this
// concatenation, and hence has the same lifetime as that
// page. However, our choice of lifetimes can't express
// this, but we also know that we are not going to mutate
// the parent before rebalancing or merging the
// concatenation, and hence this pointer will be alive
// during these operations (i.e. during the merge or
// rebalance).
edit in sanakirja-core/src/btree/del.rs at line 267

[3.33951]

[3.62764]
edit in sanakirja-core/src/btree/del.rs at line 420

[3.37905]→[3.0:110](∅→∅)

debug!(
"handle_merge for level {:?}, freed {:?}",
cursor.pointer(),
freed
);
edit in sanakirja-core/src/btree/del.rs at line 441

[3.20950]→[3.20950:20991](∅→∅)

p: usize,
first_rc_level: usize,
replacement in sanakirja-core/src/btree/del.rs at line 445

[3.21091]→[3.21091:21309](∅→∅),[3.21309]→[3.6585:6662](∅→∅),[3.6662]→[3.21374:21396](∅→∅),[3.21374]→[3.21374:21396](∅→∅)

if p >= first_rc_level {
while let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut c0) {
for o in k.page_offsets().chain(v.page_offsets()) {
txn.incr_rc(o)?;
}
if left != 0 {
txn.incr_rc(left)?;
}
left = r;

[3.33576]

[3.63295]

while let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut c0) {
for o in k.page_offsets().chain(v.page_offsets()) {
txn.incr_rc(o)?;
replacement in sanakirja-core/src/btree/del.rs at line 449

[3.63305]→[3.6663:6816](∅→∅),[3.6816]→[3.22229:22255](∅→∅),[3.22229]→[3.22229:22255](∅→∅),[3.22255]→[3.11994:12029](∅→∅)

// The insertions are taken care of in `handle_merge` above,
// so we can directly move to the `c1` part of the
// modification.
if m.skip_first {
P::move_next(&mut c1);

[3.63305]

[3.22308]

if left != 0 {
txn.incr_rc(left)?;
replacement in sanakirja-core/src/btree/del.rs at line 452

[3.22318]→[3.22318:22450](∅→∅),[3.22450]→[3.6817:6894](∅→∅)

// If we are not updating the left child of c1's first
// element, increment that left child.
if m.l == 0 {
if left != 0 {
txn.incr_rc(left)?;
}

[3.22318]

[3.22515]

left = r;
}
// The insertions are taken care of in `handle_merge` above,
// so we can directly move to the `c1` part of the
// modification.
if m.skip_first {
P::move_next(&mut c1);
}
// If we are not updating the left child of c1's first
// element, increment that left child.
if m.l == 0 {
if left != 0 {
txn.incr_rc(left)?;
edit in sanakirja-core/src/btree/del.rs at line 466

[3.22525]

[3.22525]

}
replacement in sanakirja-core/src/btree/del.rs at line 468

[3.22526]→[3.6895:7019](∅→∅),[3.7019]→[3.22705:22891](∅→∅),[3.22705]→[3.22705:22891](∅→∅),[3.22891]→[3.7020:7056](∅→∅),[3.7056]→[3.22951:22998](∅→∅),[3.22951]→[3.22951:22998](∅→∅)

// If we are not updating the right child of the first
// element of `c1`, increment that right child's RC.
if let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut c1) {
for o in k.page_offsets().chain(v.page_offsets()) {
txn.incr_rc(o)?;
}
if m.r == 0 && r != 0 {
txn.incr_rc(r)?;
}

[3.22526]

[3.22998]

// If we are not updating the right child of the first
// element of `c1`, increment that right child's RC.
if let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut c1) {
for o in k.page_offsets().chain(v.page_offsets()) {
txn.incr_rc(o)?;
replacement in sanakirja-core/src/btree/del.rs at line 474

[3.23008]→[3.23008:23290](∅→∅),[3.23324]→[3.23324:23371](∅→∅)

// Finally, increment the RCs of all other elements in `c1`.
while let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut c1) {
for o in k.page_offsets().chain(v.page_offsets()) {
txn.incr_rc(o)?;
}
if r != 0 {
txn.incr_rc(r)?;
}

[3.23008]

[3.63615]

if m.r == 0 && r != 0 {
txn.incr_rc(r)?;
}
}
// Finally, increment the RCs of all other elements in `c1`.
while let Some((k, v, r)) = P::next(txn, m.page.as_page(), &mut c1) {
for o in k.page_offsets().chain(v.page_offsets()) {
txn.incr_rc(o)?;
}
if r != 0 {
txn.incr_rc(r)?;
replacement in sanakirja-core/src/btree/del.rs at line 498

[3.23528]→[3.23528:23568](∅→∅)

mut last_op: ModifiedPage<K, V, P>,

[3.23528]

[3.3791]

last_op: ModifiedPage<K, V, P>,
replacement in sanakirja-core/src/btree/del.rs at line 507

[3.6330]→[3.6330:6489](∅→∅)

// We don't do this if the table is empty, in order to be
// consistent with put and drop.
debug!("single child {:?} {:?}", d, is_rc);

[3.6330]

[3.6489]

// We don't do this if the table is empty (i.e. if `d == 0`),
// in order to be consistent with put and drop.
replacement in sanakirja-core/src/btree/del.rs at line 510

[3.6508]→[3.7057:7110](∅→∅)

if P::is_dirty(last_op.page.as_page()) {

[3.6508]

[3.7110]

if last_op.page.is_dirty() {
replacement in sanakirja-core/src/btree/del.rs at line 519

[3.10692]→[3.10692:10719](∅→∅),[3.10719]→[3.6973:7030](∅→∅),[3.6973]→[3.6973:7030](∅→∅),[3.7030]→[3.10720:10767](∅→∅),[3.10767]→[3.7091:7116](∅→∅),[3.7091]→[3.7091:7116](∅→∅),[3.7116]→[3.10768:10809](∅→∅),[3.10809]→[3.7171:7203](∅→∅),[3.7171]→[3.7171:7203](∅→∅)

if freed > 0 {
if P::is_dirty(last_op.page.as_page()) {
txn.decr_rc_owned(freed)?;
} else {
txn.decr_rc(freed)?;
}
}

[3.10692]

[3.7203]

free[0][0] = freed;
replacement in sanakirja-core/src/btree/del.rs at line 527

[3.7364]→[3.12030:12083](∅→∅)

match modify::<_, K, V, P>(txn, &mut last_op)? {

[3.7364]

[3.7365]

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

[3.7406]

[3.7406]

// Here, the root was simply updated (i.e. some elements
// might have been deleted/inserted/updated), so we just
// need to update the Db.
replacement in sanakirja-core/src/btree/del.rs at line 538

[3.7537]→[3.7537:7580](∅→∅)

left: l,
right: r,

[3.7537]

[3.7580]

left: MutPage(CowPage { offset: l, .. }),
right: MutPage(CowPage { offset: r, .. }),
edit in sanakirja-core/src/btree/del.rs at line 542

[3.38925]

[3.7600]

// Else, the root has split, and we need to allocate a new
// page to hold the split key/value and the two sides of
// the split.
replacement in sanakirja-core/src/btree/del.rs at line 548

[3.39035]→[3.10626:10686](∅→∅)

let mut c = P::cursor_before(page.0.as_page());

[3.39035]

[3.12084]

let mut c = P::cursor_before(&page.0);
replacement in sanakirja-core/src/btree/del.rs at line 550

[3.12118]→[3.12118:12236](∅→∅)

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

[3.12118]

[3.3820]

let page = if let Put::Ok(p) = P::put(txn, page.0, true, false, &c, k, v, None, l, r)? {
p.page
} else {
unreachable!()
};
replacement in sanakirja-core/src/btree/del.rs at line 557

[3.12288]→[3.7714:7766](∅→∅),[3.3947]→[3.7714:7766](∅→∅)

(k0 as *const K) == (k as *const K)

[3.12288]

[3.24220]

core::ptr::eq(k0, k)
edit in sanakirja-core/src/btree/del.rs at line 561

[3.24278]

[3.24278]

// If the root isn't shared with another tree, and the
// split key is different from the replacement, increment
// the RCs of the references contained in the split
// key/value.
//
// The replacement need not be incremented again, since it
// was already increment when we took it from the page in
// `leaf_delete`.
edit in sanakirja-core/src/btree/del.rs at line 574

[3.39551]

[3.10760]

// Finally, update the database.
replacement in sanakirja-core/src/btree/del.rs at line 581

[3.12290]→[3.3218:3351](∅→∅)

fn single_child<K: Representable+?Sized, V: Representable+?Sized, P: BTreeMutPage<K, V>>(m: &ModifiedPage<K, V, P>) -> Option<u64> {

[3.12290]

[3.3351]

fn single_child<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreeMutPage<K, V>>(
m: &ModifiedPage<K, V, P>,
) -> Option<u64> {
replacement in sanakirja-core/src/btree/del.rs at line 588

[3.3441]→[3.3441:3668](∅→∅)

debug!(
"single_child: {:?} {:?} {:?} {:?}",
m.page,
m.c0, c1, m.ins
);
if P::is_empty(m.page.as_page(), &m.c0)
&& m.ins.is_none()
&& P::is_empty(m.page.as_page(), &c1)
{

[3.3441]

[3.3668]

if P::is_empty(&m.c0) && m.ins.is_none() && P::is_empty(&c1) {
edit in sanakirja-core/src/btree/del.rs at line 594

[3.3720]→[3.3720:3721](∅→∅)
replacement in sanakirja-core/src/btree/del.rs at line 595

[3.3722]→[3.12290:12329](∅→∅),[3.12290]→[3.12290:12329](∅→∅)

/// Apply the modifications to a page.

[3.3722]

[3.12329]

/// Apply the modifications to a page. This is exclusively used for
/// the root page, because other modifications are applied during a
/// merge/rebalance attempts.
replacement in sanakirja-core/src/btree/del.rs at line 606

[3.12475]→[3.12475:12514](∅→∅)

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

[3.12475]

[3.12514]

m: ModifiedPage<'a, K, V, P>,
edit in sanakirja-core/src/btree/del.rs at line 608

[3.12553]→[3.12553:12584](∅→∅)

debug!("modify: {:?}", m);
edit in sanakirja-core/src/btree/del.rs at line 609

[3.12618]

[3.12618]

// The following call might actually replace the first element
// of `m.c1` if `m.skip_first`.
edit in sanakirja-core/src/btree/del.rs at line 624

[3.12846]

[3.12846]

// If there's no insertion to do, we might still need to
// delete elements, or update children.
edit in sanakirja-core/src/btree/del.rs at line 630

[3.13021]

[3.13021]

// If the left page of the current entry has changed,
// update it.
edit in sanakirja-core/src/btree/del.rs at line 636

[3.13152]

[3.13152]

// If there's no insertion, and `m.l == 0`, we are
// actually deleting an entry of the root, and so we need
// to update the right child of the current entry. The
// following moves one step to the right and updates:
edit in sanakirja-core/src/btree/cursor.rs at line 14

[3.10822]→[3.63956:63959](∅→∅),[3.63956]→[3.63956:63959](∅→∅),[3.63959]→[3.10745:10830](∅→∅),[3.51634]→[3.24468:24496](∅→∅),[3.10830]→[3.24468:24496](∅→∅),[3.24468]→[3.24468:24496](∅→∅),[3.24496]→[3.64079:64220](∅→∅),[3.64079]→[3.64079:64220](∅→∅),[3.64220]→[3.10831:10915](∅→∅),[3.51715]→[3.24563:24591](∅→∅),[3.10915]→[3.24563:24591](∅→∅),[3.24563]→[3.24563:24591](∅→∅),[3.24591]→[3.64339:64341](∅→∅),[3.64339]→[3.64339:64341](∅→∅)

}

impl<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>> Clone
for PageCursor<K, V, P>
{
fn clone(&self) -> Self {
PageCursor {
page: self.page,
cursor: self.cursor.clone(),
}
}
}
impl<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>> Copy
for PageCursor<K, V, P>
{
replacement in sanakirja-core/src/btree/cursor.rs at line 16

[3.64344]→[3.64344:64459](∅→∅)

// This is 1 + the maximal depth of a tree. Cursors start at 1 to
// allow for splitting the root on an insertion.

[3.64344]

[3.64459]

// This is 1 + the maximal depth of a tree.
replacement in sanakirja-core/src/btree/cursor.rs at line 22

[3.64743]→[3.64743:64882](∅→∅)

// larger than 2^52, the maximum depth is 24, and we add the extra
// room to allow for splitting.
pub(crate) const N_CURSORS: usize = 25;

[3.64743]

[3.64882]

// larger than 2^52, the maximum depth is 24.
pub(crate) const N_CURSORS: usize = 24;
replacement in sanakirja-core/src/btree/cursor.rs at line 25

[3.64883]→[3.64883:64907](∅→∅)

#[derive(Debug, Clone)]

[3.64883]

[3.64907]

#[derive(Debug)]
replacement in sanakirja-core/src/btree/cursor.rs at line 37

[3.10907]→[3.65353:65424](∅→∅),[3.983]→[3.65353:65424](∅→∅),[3.24872]→[3.65353:65424](∅→∅),[3.65353]→[3.65353:65424](∅→∅)

let mut stack = [core::mem::MaybeUninit::uninit(); N_CURSORS];

[3.10907]

[3.10908]

let mut stack = [
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
core::mem::MaybeUninit::uninit(),
];
edit in sanakirja-core/src/btree/cursor.rs at line 65

[3.646]

[3.10951]

cursor: P::cursor_before(&page),
edit in sanakirja-core/src/btree/cursor.rs at line 67

[3.10969]→[3.10969:11023](∅→∅)

cursor: P::cursor_before(page.as_page()),
replacement in sanakirja-core/src/btree/cursor.rs at line 114

[3.7828]→[3.7828:7889](∅→∅)

init.cursor = P::cursor_before(init.page.as_page());

[3.7828]

[3.7889]

init.cursor = P::cursor_before(&init.page);
replacement in sanakirja-core/src/btree/cursor.rs at line 121

[3.2648]→[3.66334:66371](∅→∅),[3.66334]→[3.66334:66371](∅→∅),[3.1684]→[3.66371:66450](∅→∅),[3.66371]→[3.66371:66450](∅→∅)

let page = current.page;
if self.first_rc_level >= N_CURSORS && txn.rc(page.offset)? >= 2 {

[3.2648]

[3.66450]

// let page = current.page;
if self.first_rc_level >= N_CURSORS && txn.rc(current.page.offset)? >= 2 {
replacement in sanakirja-core/src/btree/cursor.rs at line 128

[3.66731]→[3.34237:34329](∅→∅)

if let Ok((kk, vv, _)) = P::set_cursor(txn, page.as_page(), cursor, k, v) {

[3.66731]

[3.66814]

if let Ok((kk, vv, _)) = P::set_cursor(txn, current.page.as_page(), cursor, k, v) {
replacement in sanakirja-core/src/btree/cursor.rs at line 135

[3.873]→[3.873:932](∅→∅)

debug!("not found on page {:?}", page)

[3.873]

[3.67027]

debug!("not found on page {:?}", current.page)
replacement in sanakirja-core/src/btree/cursor.rs at line 138

[3.7912]→[3.7912:7971](∅→∅)

*cursor = P::cursor_first(page.as_page());

[3.7912]

[3.67045]

*cursor = P::cursor_first(&current.page);
replacement in sanakirja-core/src/btree/cursor.rs at line 140

[3.67059]→[3.34330:34397](∅→∅)

let next_page = P::left_child(page.as_page(), cursor);

[3.67059]

[3.67163]

let next_page = P::left_child(current.page.as_page(), cursor);
edit in sanakirja-core/src/btree/cursor.rs at line 144

[3.972]

[3.11223]

cursor: P::cursor_before(&page),
edit in sanakirja-core/src/btree/cursor.rs at line 146

[3.11249]→[3.11249:11311](∅→∅)

cursor: P::cursor_before(page.as_page()),
replacement in sanakirja-core/src/btree/cursor.rs at line 166

[3.11427]→[3.11427:11492](∅→∅)

current.cursor = P::cursor_last(current.page.as_page());

[3.11427]

[3.67886]

current.cursor = P::cursor_last(&current.page);
edit in sanakirja-core/src/btree/cursor.rs at line 180

[3.11830]

[3.11830]

cursor: P::cursor_last(&page),
edit in sanakirja-core/src/btree/cursor.rs at line 182

[3.11856]→[3.11856:11916](∅→∅)

cursor: P::cursor_last(page.as_page()),
replacement in sanakirja-core/src/btree/cursor.rs at line 206

[3.82]→[3.12060:12129](∅→∅)

if P::is_init(current.page.as_page(), &current.cursor) {

[3.82]

[3.0]

if P::is_init(&current.cursor) {
edit in sanakirja-core/src/btree/cursor.rs at line 213

[3.12481]

[3.12481]

cursor: P::cursor_before(&page),
edit in sanakirja-core/src/btree/cursor.rs at line 215

[3.12511]→[3.12511:12577](∅→∅)

cursor: P::cursor_before(page.as_page()),
edit in sanakirja-core/src/btree/cursor.rs at line 223

[3.12916]

[3.12916]

cursor: P::cursor_before(&page),
edit in sanakirja-core/src/btree/cursor.rs at line 225

[3.12946]→[3.12946:13012](∅→∅)

cursor: P::cursor_before(page.as_page()),
replacement in sanakirja-core/src/btree/cursor.rs at line 244

[3.580]→[3.13403:13473](∅→∅),[3.8421]→[3.13403:13473](∅→∅),[3.13403]→[3.13403:13473](∅→∅)

if P::is_empty(current.page.as_page(), &current.cursor) {

[3.8421]

[3.581]

if P::is_empty(&current.cursor) {
edit in sanakirja-core/src/btree/cursor.rs at line 250

[3.1403]

[3.13720]

cursor: P::cursor_after(&page),
edit in sanakirja-core/src/btree/cursor.rs at line 252

[3.13750]→[3.13750:13815](∅→∅)

cursor: P::cursor_after(page.as_page()),
edit in sanakirja-core/src/btree/cursor.rs at line 263

[3.14235]

[3.14235]

cursor: P::cursor_after(&page),
edit in sanakirja-core/src/btree/cursor.rs at line 265

[3.14265]→[3.14265:14330](∅→∅)

cursor: P::cursor_after(page.as_page()),
replacement in sanakirja/src/tests.rs at line 507

[3.9854]→[3.9854:9892](∅→∅)

let n = i * 128; // _000_000;

[3.9854]

[3.9892]

let n = i * 1_000_000;
replacement in sanakirja/src/tests.rs at line 515

[3.10123]→[3.10123:10134](∅→∅)

/*

[3.10123]

[3.1200]
edit in sanakirja/src/tests.rs at line 523

[3.1553]→[3.1553:1554](∅→∅)
replacement in sanakirja/src/tests.rs at line 534

[3.2227]→[3.10135:10146](∅→∅)

*/

[3.2227]

[3.2228]
edit in sanakirja/src/tests.rs at line 550

[3.2880]→[3.10206:10217](∅→∅)

/*
edit in sanakirja/src/tests.rs at line 561

[3.3310]→[3.10218:10229](∅→∅)

*/
edit in sanakirja/src/tests.rs at line 669

[36.108]

[3.4468]

debug!("====== del {:?}", i);