Debugging replace (which cannot be del+put)

Dependencies

• [2] T73WR2BX Cleaner RC increments for keys and values containing references + more comments in `del`
• [3] MSRWB47Y Deletions at immutable leaves weren't really deleting anything
• [4] 7P43FPFA When deleting in internal nodes, set the correct child
• [5] H3FVSQIQ Unsized pages
• [6] QEUTVAZ4 Splitting btree::page
• [7] AOX2XQIS Actually, with the correct functions, Unsized pages are always slower than Sized pages (especially for writing)
• [8] XEU2QVLC Debugging after plugging this into Pijul
• [9] NQBEOCFO Tests cleanup
• [10] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
• [11] WS4ZQM4R Debugging, tests, etc.
• [12] S4V4QZ5C Debugging reference-counting for put
• [13] OP6SVMOD Resetting history
• [14] W26CFMAQ Improving safety of cursors
• [15] 6UVFCERM Formatting, debugging, etc.
• [16] OTWDDJE7 Trait/type cleanup
• [17] 6DCQHIFP Minor changes after benchmarking
• [18] LROAI3NB Two iterators (convenience functions), along with tests to move cursors (put and del still destroy cursors though)
• [19] 6DMPXOAT More debugging
• [20] APPY2E7M Unsized deletions + custom sizes back
• [21] G4JEQLLX Debugging synchronisation
• [22] KX3WVNZW Testing/debugging "rebalance causes split of the root"
• [23] OFINGD26 implementing prev() on cursors (+ some cleanup)
• [24] 7WJNSPEW Using the same definition of the "occupied" field uniform everywhere
• [25] EAAYH6BQ Debugging put
• [26] X3QVVQIS More debugging (del seems to work now)
• [27] UAQX27N4 Tests

Change contents

• replacement in sanakirja-core/src/btree/page_unsized.rs at line 76
  [5.3929]→[5.411:505](∅→∅)
  − put::put::<_, _, _, Leaf>(txn, page, mutable, c.cur as usize, k0, v0, k1v1, 0, 0)
  [5.3929]

  [5.4014]
  + put::put::<_, _, _, Leaf>(

  + txn,

  + page,

  + mutable,

  + false,

  + c.cur as usize,

  + k0,

  + v0,

  + k1v1,

  + 0,

  + 0,

  + )
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 89
  [5.4031]→[5.506:604](∅→∅)
  − put::put::<_, _, _, Internal>(txn, page, mutable, c.cur as usize, k0, v0, k1v1, l, r)
  [5.4031]

  [5.4120]
  + put::put::<_, _, _, Internal>(

  + txn,

  + page,

  + mutable,

  + false,

  + c.cur as usize,

  + k0,

  + v0,

  + k1v1,

  + l,

  + r,

  + )
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 115
  [5.4415]→[5.4415:4469](∅→∅),[5.4469]→[5.454:569](∅→∅)
  − // We're never in a leaf if we're doing this.

  − let new = Self::del(txn, page, mutable, c, l)?;

  − Self::put(txn, new.0, true, c, k0, v0, k1v1, l, r)
  [5.4415]

  [5.4578]
  + 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 159
  [5.1303]→[5.1303:1340](∅→∅)
  − ) -> Result<MutPage, T::Error> {
  [5.1303]

  [5.653]
  + ) -> Result<(MutPage, u64), T::Error> {
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 171
  [5.6630]→[5.787:864](∅→∅)
  − core::ptr::copy(ptr.offset(1), ptr, n - c.cur as usize);
  [5.6630]

  [5.6698]
  + core::ptr::copy(ptr.offset(1), ptr, n - c.cur as usize - 1);
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 178
  [5.6998]→[5.941:1033](∅→∅)
  − core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - c.cur as usize);
  [5.6998]

  [5.7081]
  + core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - c.cur as usize - 1);
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 191
  [5.7521]→[5.7521:7542](∅→∅)
  − Ok(page)
  [5.7521]

  [5.7542]
  + Ok((page, 0))
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 209
  [5.8320]→[5.8320:8398](∅→∅),[5.8398]→[4.0:71](∅→∅)
  − let off = (page.data.add(HDR) as *mut u64).offset(n - 1);

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

  [5.8436]
  + if l > 0 {

  + let off = (new.0.data.add(HDR) as *mut u64).offset(n - 1);

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

  + } 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();

  + }
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 219
  [5.8537]→[5.8537:8561](∅→∅)
  − Ok(new)
  [5.8537]

  [5.8561]
  + Ok((new, page.as_page().offset))
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 288
  [5.10928]→[5.10928:10975](∅→∅),[5.10975]→[5.650:903](∅→∅),[5.903]→[5.11065:11117](∅→∅),[5.11065]→[5.11065:11117](∅→∅)
  − return Ok(Op::Put(Put::Ok(Ok {

  − page: Self::del(

  − txn,

  − m.modified.page,

  − m.modified.mutable,

  − &m.modified.c1,

  − m.modified.l,

  − )?,

  − freed: 0,

  − })));
  [5.10928]

  [5.11117]
  + let (page, freed) = Self::del(

  + txn,

  + m.modified.page,

  + m.modified.mutable,

  + &m.modified.c1,

  + m.modified.l,

  + )?;

  + return Ok(Op::Put(Put::Ok(Ok { page, freed })));
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 374
  [5.13595]→[5.13595:13715](∅→∅),[5.13715]→[5.2735:2815](∅→∅),[5.2815]→[5.1888:1917](∅→∅),[5.13792]→[5.1888:1917](∅→∅),[5.1917]→[5.13883:13967](∅→∅),[5.13883]→[5.13883:13967](∅→∅),[5.13967]→[5.1213:1350](∅→∅),[5.1350]→[5.14101:14134](∅→∅),[5.14101]→[5.14101:14134](∅→∅)
  − unsafe {

  − if c.is_leaf {

  − 2 + entry_size::<K, V>(page.data.as_ptr().add(u16::from_le(

  − *(page.data.as_ptr().add(HDR) as *const u16).offset(c.cur),

  − ) as usize))

  − } else {

  − 8 + entry_size::<K, V>(page.data.as_ptr().add(

  − (u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).offset(c.cur))

  − & 0xfff) as usize,

  − ))

  − }
  [5.13595]

  [5.14134]
  + if c.is_leaf {

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

  + } else {

  + Internal::current_size::<K, V>(page, c.cur)
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 24
  [5.23715]→[5.23715:23777](∅→∅)
  − let mut new_left = if let Some((k, v)) = m.modified.ins {
  [5.23715]

  [5.129]
  + let new_left = if let Some((k, v)) = m.modified.ins {
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 49
  [5.24156]→[5.1837:1864](∅→∅)
  − <Page<K, V>>::del(
  [5.24156]

  [5.1864]
  + let (page, freed) = <Page<K, V>>::del(
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 55
  [5.1996]→[5.1996:2007](∅→∅),[5.2007]→[5.24235:24242](∅→∅),[5.24235]→[5.24235:24242](∅→∅),[5.24242]→[5.742:801](∅→∅),[5.4608]→[5.656:789](∅→∅),[5.801]→[5.656:789](∅→∅),[5.656]→[5.656:789](∅→∅)
  − )?

  − };

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

  − 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)?

  − {
  [5.1996]

  [5.789]
  + )?;
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 57
  [5.812]→[5.812:877](∅→∅)
  − let b = if header(new_left.0.as_page()).is_dirty() {
  [5.812]

  [5.877]
  + let b = if header(m.modified.page.as_page()).is_dirty() {
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 64
  [5.994]→[5.994:1018](∅→∅)
  − new_left = page
  [5.994]

  [5.1018]
  + page

  + };

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

  + 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)?

  + {

  + assert_eq!(page.0.offset, new_left.0.offset);

  + assert_eq!(freed, 0);
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 76
  [5.24372]→[5.24372:24432](∅→∅),[5.24432]→[5.2008:2082](∅→∅),[5.2082]→[5.24486:24623](∅→∅),[5.24486]→[5.24486:24623](∅→∅)
  − let (new_right, k, v): (_, &K, &V) = unsafe {

  − (

  − <Page<K, V>>::del(txn, m.other, m.other_is_mutable, &rc, r)?,

  − core::mem::transmute(k),

  − core::mem::transmute(v),

  − )

  − };

  − if new_right.0.offset != m.other.offset {
  [5.24372]

  [5.24623]
  + let (new_right, freed) = <Page<K, V>>::del(txn, m.other, m.other_is_mutable, &rc, r)?;

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

  + if freed > 0 {
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 81
  [5.24722]→[5.1062:1101](∅→∅)
  − freed_[1] = m.other.offset | b
  [5.24722]

  [5.24760]
  + freed_[1] = freed | b
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 114
  [5.25830]→[5.25830:25893](∅→∅)
  − let mut new_right = if let Some((k, v)) = m.modified.ins {
  [5.25830]

  [5.1156]
  + let new_right = if let Some((k, v)) = m.modified.ins {
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 139
  [5.26272]→[5.2083:2110](∅→∅)
  − <Page<K, V>>::del(
  [5.26272]

  [5.2110]
  + let (page, freed) = <Page<K, V>>::del(
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 145
  [5.2242]→[5.2242:2253](∅→∅),[5.2253]→[5.26351:26358](∅→∅),[5.26351]→[5.26351:26358](∅→∅),[5.26358]→[5.1468:1509](∅→∅),[5.1509]→[5.26396:26490](∅→∅),[5.26396]→[5.26396:26490](∅→∅)
  − )?

  − };

  − 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)?

  − {
  [5.2242]

  [5.1510]
  + )?;
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 147
  [5.1533]→[5.1533:1599](∅→∅)
  − let b = if header(new_right.0.as_page()).is_dirty() {
  [5.1533]

  [5.1599]
  + let b = if header(m.modified.page.as_page()).is_dirty() {
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 154
  [5.1716]→[5.26490:26515](∅→∅),[5.26490]→[5.26490:26515](∅→∅)
  − new_right = page
  [5.1716]

  [5.26515]
  + page

  + };

  + 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)?

  + {

  + assert_eq!(new_right.0.offset, page.0.offset);

  + assert_eq!(freed, 0);
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 165
  [5.26559]→[5.2254:2335](∅→∅),[5.2335]→[5.26620:26665](∅→∅),[5.26620]→[5.26620:26665](∅→∅)
  − let new_left = <Page<K, V>>::del(txn, m.other, m.other_is_mutable, &lc, 0)?;

  − if new_left.0.offset != m.other.offset {
  [5.26559]

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

  + if freed > 0 {
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 169
  [5.26764]→[5.1717:1756](∅→∅)
  − freed_[1] = m.other.offset | b
  [5.26764]

  [5.26802]
  + freed_[1] = freed | b
• edit in sanakirja-core/src/btree/page_unsized/put.rs at line 14
  [5.27256]

  [5.27256]
  + replace: bool,
• edit in sanakirja-core/src/btree/page_unsized/put.rs at line 28
  [5.27545]

  [5.27545]
  + let size_replaced = if replace {

  + // We're always in an internal node if we replace.

  + let cur_size = Internal::current_size::<K, V>(page.as_page(), u as isize);

  + size as isize - cur_size as isize

  + } else {

  + size as isize

  + };
• replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 40
  [5.27786]→[5.27786:27848](∅→∅)
  − let mut page = unsafe { core::mem::transmute(page) };
  [5.27786]

  [5.27848]
  + let mut page = MutPage(page);
• edit in sanakirja-core/src/btree/page_unsized/put.rs at line 42
  [5.27880]

  [5.27880]
  + if replace {

  + assert!(!hdr.is_leaf());

  + unsafe {

  + let p = page.0.data;

  + let ptr = p.add(HDR + n 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 - n as usize - 1);

  + header_mut(&mut page).decr(size)

  + }

  + }
• replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 61
  [5.28178]→[5.2478:2520](∅→∅)
  − } else if L::can_compact(hdr, size) {
  [5.28178]

  [5.28228]
  + } else if L::can_compact(hdr, size_replaced) {
• edit in sanakirja-core/src/btree/page_unsized/put.rs at line 68
  [5.28543]

  [5.28543]
  + let s1 = if replace { s1.split_at(1).1 } else { s1 };
• replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 86
  [5.29136]→[5.29136:29224](∅→∅)
  − return split_unsized::<_, _, _, L>(txn, page.as_page(), u, k0, v0, k1v1, l, r);
  [5.29136]

  [5.29224]
  + return split_unsized::<_, _, _, L>(txn, page.as_page(), replace, u, k0, v0, k1v1, l, r);
• edit in sanakirja-core/src/btree/page_unsized/put.rs at line 99
  [5.29434]

  [5.29434]
  + replace: bool,
• replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 140
  [5.767]→[5.767:768](∅→∅)
  −
  [5.767]

  [5.30307]
  + if replace {

  + continue;

  + }
• edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 6
  [5.2975]

  [5.2975]
  + fn current_size<K: Representable + ?Sized, V: Representable + ?Sized>(

  + page: crate::Page,

  + cur: isize,

  + ) -> usize;
• replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 11
  [5.3028]→[5.3028:3083](∅→∅)
  − fn can_compact(hdr: &Header, size: usize) -> bool;
  [5.3028]

  [5.3083]
  + fn can_compact(hdr: &Header, size: isize) -> bool;
• edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 68
  [5.35961]

  [5.3182]
  + fn current_size<K: Representable + ?Sized, V: Representable + ?Sized>(

  + page: crate::Page,

  + cur: isize,

  + ) -> usize {

  + unsafe {

  + 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))

  + }

  + }

  +
• replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 89
  [5.36218]→[5.3318:3374](∅→∅)
  − fn can_compact(hdr: &Header, size: usize) -> bool {
  [5.36218]

  [5.3374]
  + fn can_compact(hdr: &Header, size: isize) -> bool {
• replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 96
  [5.1795]→[5.3525:3623](∅→∅),[5.3525]→[5.3525:3623](∅→∅),[5.3623]→[5.3016:3041](∅→∅)
  − (HDR as usize) + (hdr.n() as usize) * 2 + ((hdr.left_page() & 0xfff) as usize) + 2 + size

  − <= PAGE_SIZE
  [5.3525]

  [5.36463]
  + (HDR as isize) + (hdr.n() as isize) * 2 + ((hdr.left_page() & 0xfff) as isize) + 2 + size

  + <= PAGE_SIZE as isize
• edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 192
  [5.39747]

  [5.39747]
  + }

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

  + page: crate::Page,

  + cur: isize,

  + ) -> usize {

  + unsafe {

  + 8 + entry_size::<K, V>(page.data.as_ptr().add(

  + (u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).offset(cur)) & 0xfff)

  + as usize,

  + ))

  + }
• edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 204
  [5.39753]

  [5.4206]
  +
• replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 215
  [5.39948]→[5.4261:4317](∅→∅)
  − fn can_compact(hdr: &Header, size: usize) -> bool {
  [5.39948]

  [5.4317]
  + fn can_compact(hdr: &Header, size: isize) -> bool {
• replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 222
  [5.4468]→[5.4468:4566](∅→∅),[5.4566]→[5.3125:3150](∅→∅)
  − (HDR as usize) + (hdr.n() as usize) * 8 + ((hdr.left_page() & 0xfff) as usize) + 8 + size

  − <= PAGE_SIZE
  [5.4468]

  [5.40203]
  + (HDR as isize) + (hdr.n() as isize) * 8 + ((hdr.left_page() & 0xfff) as isize) + 8 + size

  + <= PAGE_SIZE as isize
• replacement in sanakirja-core/src/btree/page.rs at line 93
  [5.1844]→[5.4879:4973](∅→∅)
  − put::put::<_, _, _, Leaf>(txn, page, mutable, c.cur as usize, k0, v0, k1v1, 0, 0)
  [5.1844]

  [5.1918]
  + put::put::<_, _, _, Leaf>(

  + txn,

  + page,

  + mutable,

  + false,

  + c.cur as usize,

  + k0,

  + v0,

  + k1v1,

  + 0,

  + 0,

  + )
• replacement in sanakirja-core/src/btree/page.rs at line 106
  [5.1935]→[5.4974:5072](∅→∅)
  − put::put::<_, _, _, Internal>(txn, page, mutable, c.cur as usize, k0, v0, k1v1, l, r)
  [5.1935]

  [5.11455]
  + put::put::<_, _, _, Internal>(

  + txn,

  + page,

  + mutable,

  + false,

  + c.cur as usize,

  + k0,

  + v0,

  + k1v1,

  + l,

  + r,

  + )
• replacement in sanakirja-core/src/btree/page.rs at line 132
  [5.1326]→[5.1326:1380](∅→∅),[5.1380]→[5.3287:3402](∅→∅)
  − // We're never in a leaf if we're doing this.

  − let new = Self::del(txn, page, mutable, c, l)?;

  − Self::put(txn, new.0, true, c, k0, v0, k1v1, l, r)
  [5.1326]

  [5.1513]
  + 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 188
  [5.5274]→[5.5274:5311](∅→∅)
  − ) -> Result<MutPage, T::Error> {
  [5.5274]

  [5.5137]
  + ) -> Result<(MutPage, u64), T::Error> {
• replacement in sanakirja-core/src/btree/page.rs at line 206
  [5.5414]→[5.5414:5506](∅→∅)
  − core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - c.cur as usize);
  [5.5414]

  [5.5374]
  + core::ptr::copy(ptr.offset(1), ptr, hdr.n() as usize - c.cur as usize - 1);
• replacement in sanakirja-core/src/btree/page.rs at line 219
  [5.312]→[5.4428:4449](∅→∅),[5.4428]→[5.4428:4449](∅→∅)
  − Ok(page)
  [5.312]

  [5.14580]
  + Ok((page, 0))
• edit in sanakirja-core/src/btree/page.rs at line 226
  [5.4646]

  [5.5507]
  + debug!("s = {:?}", s);
• edit in sanakirja-core/src/btree/page.rs at line 229
  [3.152]

  [5.14932]
  + debug!("leaf s0 {:?} s1 {:?}", s0, s1);
• edit in sanakirja-core/src/btree/page.rs at line 235
  [5.4891]

  [5.5571]
  + debug!("s = {:?}", s);
• edit in sanakirja-core/src/btree/page.rs at line 238
  [3.203]

  [5.15312]
  + debug!("internal s0 {:?} s1 {:?}", s0, s1);
• replacement in sanakirja-core/src/btree/page.rs at line 241
  [5.4978]→[5.15423:15501](∅→∅),[5.2460]→[5.15423:15501](∅→∅),[5.15423]→[5.15423:15501](∅→∅),[5.15501]→[4.72:143](∅→∅)
  − let off = (page.data.add(HDR) as *mut u64).offset(n - 1);

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

  [5.2461]
  + debug!("offset {:?}", n);

  + if l > 0 {

  + let off = (new.0.data.add(HDR) as *mut u64).offset(n - 1);

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

  + debug!("set offset {:?} {:?}", *off, l);

  + } else {

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

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

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

  + }
• replacement in sanakirja-core/src/btree/page.rs at line 253
  [5.15633]→[5.15633:15657](∅→∅)
  − Ok(new)
  [5.15633]

  [5.15657]
  + Ok((new, page.offset))
• replacement in sanakirja-core/src/btree/page.rs at line 321
  [5.6309]→[5.3693:3740](∅→∅),[5.3740]→[5.3483:3736](∅→∅),[5.3736]→[5.6428:6458](∅→∅),[5.6428]→[5.6428:6458](∅→∅),[5.6458]→[5.3741:3763](∅→∅)
  − return Ok(Op::Put(Put::Ok(Ok {

  − page: Self::del(

  − txn,

  − m.modified.page,

  − m.modified.mutable,

  − &m.modified.c1,

  − m.modified.l,

  − )?,

  − freed: 0,

  − })));
  [5.6309]

  [5.3763]
  + let (page, freed) = Self::del(

  + txn,

  + m.modified.page,

  + m.modified.mutable,

  + &m.modified.c1,

  + m.modified.l,

  + )?;

  + return Ok(Op::Put(Put::Ok(Ok { page, freed })));
• edit in sanakirja-core/src/btree/page.rs at line 380
  [5.19851]→[5.6185:6226](∅→∅)
  − debug!("current {:?}", off);
• edit in sanakirja-core/src/btree/page.rs at line 382
  [5.6336]→[5.6336:6408](∅→∅)
  − debug!("k {:?}", K::from_raw_ptr(txn, k as *const u8));
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 48
  [5.1650]→[5.4520:4547](∅→∅)
  − <Page<K, V>>::del(
  [5.1650]

  [5.4547]
  + let (page, freed) = <Page<K, V>>::del(
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 54
  [5.4679]→[5.4679:4690](∅→∅)
  − )?
  [5.4679]

  [5.1729]
  + )?;

  + if freed > 0 {

  + let b = if header(m.modified.page.as_page()).is_dirty() {

  + 1

  + } else {

  + 0

  + };

  + freed_[0] = freed | b

  + }

  + page
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 112
  [5.47398]→[5.47398:47415](∅→∅),[5.47415]→[5.3292:3306](∅→∅),[5.3292]→[5.3292:3306](∅→∅),[5.3306]→[5.4691:4769](∅→∅),[5.4769]→[5.3364:3460](∅→∅),[5.3364]→[5.3364:3460](∅→∅)
  − unsafe {

  − (

  − <Page<K, V>>::del(txn, m.other, m.other_is_mutable, &rc, r)?,

  − core::mem::transmute(k),

  − core::mem::transmute(v),

  − )
  [5.47398]

  [5.47416]
  + let (page, freed) = <Page<K, V>>::del(txn, m.other, m.other_is_mutable, &rc, r)?;

  + if freed > 0 {

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

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

  + freed_[1] = freed | b;
• edit in sanakirja-core/src/btree/page/rebalance.rs at line 118
  [5.47426]

  [5.3471]
  + unsafe { (page, core::mem::transmute(k), core::mem::transmute(v)) }
• edit in sanakirja-core/src/btree/page/rebalance.rs at line 120
  [5.3478]→[5.3478:3623](∅→∅),[5.3623]→[5.2799:2838](∅→∅),[5.2838]→[5.3661:3667](∅→∅),[5.3661]→[5.3661:3667](∅→∅)
  − if new_right.0.offset != m.other.offset {

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

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

  − freed_[1] = m.other.offset | b

  − }
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 151
  [5.4736]→[5.4736:4799](∅→∅)
  − let mut new_right = if let Some((k, v)) = m.modified.ins {
  [5.4736]

  [5.2893]
  + let new_right = if let Some((k, v)) = m.modified.ins {
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 174
  [5.5178]→[5.4770:4797](∅→∅)
  − <Page<K, V>>::del(
  [5.5178]

  [5.4797]
  + let (page, freed) = <Page<K, V>>::del(
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 180
  [5.4929]→[5.4929:4940](∅→∅),[5.4940]→[5.5257:5264](∅→∅),[5.5257]→[5.5257:5264](∅→∅),[5.5264]→[5.3140:3181](∅→∅),[5.3181]→[5.5302:5396](∅→∅),[5.5302]→[5.5302:5396](∅→∅)
  − )?

  − };

  − 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)?

  − {
  [5.4929]

  [5.3182]
  + )?;
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 182
  [5.3205]→[5.3205:3271](∅→∅)
  − let b = if header(new_right.0.as_page()).is_dirty() {
  [5.3205]

  [5.3271]
  + let b = if header(m.modified.page.as_page()).is_dirty() {
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 189
  [5.3388]→[5.5396:5421](∅→∅),[5.5396]→[5.5396:5421](∅→∅)
  − new_right = page
  [5.3388]

  [5.5421]
  + page

  + };

  + 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)?

  + {

  + assert_eq!(freed, 0);

  + assert_eq!(new_right.0.offset, page.0.offset);
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 200
  [5.5465]→[5.4941:5022](∅→∅),[5.5022]→[5.5526:5571](∅→∅),[5.5526]→[5.5526:5571](∅→∅)
  − let new_left = <Page<K, V>>::del(txn, m.other, m.other_is_mutable, &lc, 0)?;

  − if new_left.0.offset != m.other.offset {
  [5.5465]

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

  + if freed > 0 {
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 204
  [5.5670]→[5.3389:3428](∅→∅)
  − freed_[1] = m.other.offset | b
  [5.5670]

  [5.5708]
  + freed_[1] = freed | b
• edit in sanakirja-core/src/btree/page/put.rs at line 13
  [5.6169]

  [5.6169]
  + replace: bool,
• replacement in sanakirja-core/src/btree/page/put.rs at line 30
  [5.6702]→[5.6702:6764](∅→∅)
  − let mut page = unsafe { core::mem::transmute(page) };
  [5.6224]

  [5.6764]
  + let mut page = MutPage(page);
• edit in sanakirja-core/src/btree/page/put.rs at line 32
  [5.6796]

  [5.6796]
  + if replace {

  + assert!(!hdr.is_leaf());

  + unsafe {

  + let p = page.0.data;

  + let ptr = p.add(HDR + n 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 - n as usize - 1);

  + let hdr = header_mut(&mut page);

  + hdr.decr(size);

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

  + }

  + }
• edit in sanakirja-core/src/btree/page/put.rs at line 60
  [5.7477]

  [5.7477]
  + let s1 = if replace { s1.split_at(1).1 } else { s1 };
• edit in sanakirja-core/src/btree/page/put.rs at line 63
  [5.8004]

  [5.7567]
  + debug!("alloc: {:?} {:?} {:?}", l, r, n);
• edit in sanakirja-core/src/btree/page/put.rs at line 70
  [5.7828]

  [5.8193]
  + debug!("alloc: {:?}", new);

  + debug!("alloc: {:?}", header(new.0.as_page()).left_page());
• replacement in sanakirja-core/src/btree/page/put.rs at line 73
  [5.8257]→[5.7895:7974](∅→∅),[5.7895]→[5.7895:7974](∅→∅)
  −

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

  − return Ok(Put::Ok(Ok {
  [5.8257]

  [5.7974]
  + Ok(Put::Ok(Ok {
• replacement in sanakirja-core/src/btree/page/put.rs at line 75
  [5.7997]→[5.7997:8047](∅→∅)
  − freed: page.offset | b0,

  − }));
  [5.7997]

  [5.8047]
  + freed: if is_dirty {

  + page.offset | 1

  + } else {

  + page.offset

  + },

  + }))
• replacement in sanakirja-core/src/btree/page/put.rs at line 84
  [5.47513]→[5.47513:47589](∅→∅)
  − return split::<_, _, _, L>(txn, page, mutable, s, u, k0, v0, l, r);
  [5.47513]

  [5.8372]
  + split::<_, _, _, L>(txn, page, mutable, s, u, k0, v0, l, r)
• edit in sanakirja-core/src/btree/page/alloc.rs at line 192
  [5.7404]

  [5.26259]
  + debug!("can_alloc {:?}", hdr.data());
• replacement in sanakirja-core/src/btree/mod.rs at line 125
  [5.8945]→[5.50475:50495](∅→∅),[5.50475]→[5.50475:50495](∅→∅)
  − BTreePage<K, V>
  [5.8945]

  [5.48223]
  + BTreePage<K, V> + core::fmt::Debug
• replacement in sanakirja-core/src/btree/mod.rs at line 160
  [5.9058]→[5.9058:9094](∅→∅)
  − ) -> Result<MutPage, T::Error>;
  [5.9058]

  [5.48757]
  + ) -> Result<(MutPage, u64), T::Error>;
• edit in sanakirja-core/src/btree/mod.rs at line 183
  [5.49472]

  [5.5469]
  + debug!("modify: {:?}", m);
• replacement in sanakirja-core/src/btree/mod.rs at line 192
  [5.3421]→[5.5620:5695](∅→∅),[5.5695]→[5.3485:3742](∅→∅),[5.3485]→[5.3485:3742](∅→∅)
  − let page = Self::del(txn, m.page, m.mutable, &m.c1, m.l)?;

  − Ok(Put::Ok(Ok {

  − freed: if page.0.offset != m.page.offset {

  − m.page.offset

  − } else {

  − 0

  − },

  − page,

  − }))
  [5.3421]

  [5.5668]
  + let (page, freed) = Self::del(txn, m.page, m.mutable, &m.c1, m.l)?;

  + Ok(Put::Ok(Ok { freed, page }))
• replacement in sanakirja-core/src/btree/del.rs at line 122
  [2.1425]→[2.1425:1478](∅→∅)
  − debug!("freeing at level {:?}: {:?}", n, p);
  [2.1425]

  [5.60797]
  + if p[0] > 0 || p[1] > 0 {

  + debug!("freeing at level {:?}: {:?}", n, p);

  + }
• edit in sanakirja-core/src/btree/del.rs at line 136
  [5.61091]

  [5.61091]
  + debug!("/del");
• replacement in sanakirja-core/src/btree/del.rs at line 539
  [5.6825]→[5.6825:6973](∅→∅)
  − let page = P::del(txn, last_op.page, last_op.mutable, &last_op.c1, d)?;

  − if page.0.offset != last_op.page.offset && !is_rc {
  [5.6825]

  [5.6973]
  + let (page, freed) = P::del(txn, last_op.page, last_op.mutable, &last_op.c1, d)?;

  + if freed > 0 {
• replacement in sanakirja-core/src/btree/del.rs at line 542
  [5.7030]→[5.7030:7091](∅→∅)
  − txn.decr_rc_owned(last_op.page.offset)?;
  [5.7030]

  [5.7091]
  + txn.decr_rc_owned(freed)?;
• replacement in sanakirja-core/src/btree/del.rs at line 544
  [5.7116]→[5.7116:7171](∅→∅)
  − txn.decr_rc(last_op.page.offset)?;
  [5.7116]

  [5.7171]
  + txn.decr_rc(freed)?;
• edit in sanakirja/src/tests.rs at line 165
  [3.490]

  [3.490]
  + let mut values = Vec::with_capacity(n as usize);

  + for i in 0..n {

  + put(&mut txn, &mut db, &i, &i).unwrap();

  + if i != i0 {

  + values.push(i);

  + }

  + }

  + let db2 = fork_db(&mut txn, &db).unwrap();

  + del(&mut txn, &mut db, &i0, None).unwrap();

  + assert_eq!(

  + btree::iter(&txn, &db, None)

  + .unwrap()

  + .map(|kv| *kv.unwrap().0)

  + .collect::<Vec<_>>(),

  + values

  + );

  + }

  +

  + #[test]

  + pub fn del_internal() {

  + env_logger::try_init().unwrap_or(());

  + let env = Env::new_anon(409600000, 1).unwrap();

  + let mut txn = Env::mut_txn_begin(&env).unwrap();

  + let mut db: Db<u64, u64> = create_db(&mut txn).unwrap();

  + let n = 300 as u64;

  + let i0 = 127 as u64;
• edit in sanakirja/src/tests.rs at line 199
  [3.724]

  [3.724]
  + crate::debug::debug(&txn, &[&db], "debug", true);

  + debug!("===============");
• edit in sanakirja/src/tests.rs at line 202
  [3.772]

  [3.772]
  + let db3: Db<u64, u64> = Db {

  + db: 20480,

  + k: std::marker::PhantomData,

  + v: std::marker::PhantomData,

  + p: std::marker::PhantomData,

  + };

  + crate::debug::debug(&txn, &[&db, &db2, &db3], "debug2", true);
• replacement in sanakirja/src/tests.rs at line 221
  [5.9952]→[5.5685:5701](∅→∅),[5.5685]→[5.5685:5701](∅→∅)
  − pub fn fork() {
  [5.9952]

  [5.5742]
  + pub fn fork_test() {
• edit in sanakirja/src/tests.rs at line 275
  [5.9628]

  [5.10238]
  + crate::debug::debug(&txn, &[&db, &db2], &format!("debug-{}", i), true);

  + debug!("deleting {:?}", i);
• edit in sanakirja/src/tests.rs at line 279
  [5.10295]→[5.9629:9690](∅→∅)
  − crate::debug::debug(&txn, &[&db, &db2], "debug2", true);