Double-inserts (rebalancing near an internal deletion)

Dependencies

• [2] X3QVVQIS More debugging (del seems to work now)
• [3] EHJFNMB2 Debugging
• [4] OP6SVMOD Resetting history
• [5] EAAYH6BQ Debugging put
• [6] WS4ZQM4R Debugging, tests, etc.
• [*] FMN7X4J2 Micro-improvements, now noticeably faster than std::collections::BTreeMap

Change contents

• replacement in sanakirja-core/src/lib.rs at line 11
  [3.444]→[3.444:505](∅→∅)
  − type Ord: Ord;

  − fn ord(&self, txn: &T) -> &Self::Ord;
  [3.444]

  [3.505]
  + fn compare(&self, txn: &T, b: &Self) -> core::cmp::Ordering;
• replacement in sanakirja-core/src/lib.rs at line 31
  [3.1154]→[3.1154:1253](∅→∅)
  − type Ord = Self;

  − fn ord(&self, _: &T) -> &Self::Ord {

  − self
  [3.1154]

  [3.1253]
  + fn compare(&self, _: &T, b: &Self) -> core::cmp::Ordering {

  + self.cmp(b)
• edit in sanakirja-core/src/btree/put.rs at line 37
  [3.4653]

  [3.4653]
  + None,
• edit in sanakirja-core/src/btree/put.rs at line 81
  [8.405]

  [8.405]
  + None,
• edit in sanakirja-core/src/btree/put.rs at line 97
  [3.5999]

  [3.5999]
  + None,
• edit in sanakirja-core/src/btree/page.rs at line 2
  [3.8638]

  [3.0]
  + use core::cmp::Ordering;

  + use core::mem::MaybeUninit;
• edit in sanakirja-core/src/btree/page.rs at line 5
  [3.12]→[2.0:28](∅→∅)
  − use core::mem::MaybeUninit;
• replacement in sanakirja-core/src/btree/page.rs at line 65
  [3.9723]→[3.0:147](∅→∅),[3.147]→[3.9813:9832](∅→∅),[3.9813]→[3.9813:9832](∅→∅)
  − impl<T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug> super::BTreeMutPage<T, K, V>

  − for Page<K, V>
  [3.9723]

  [3.9832]
  + impl<

  + T: AllocPage + core::fmt::Debug,

  + K: Representable<T> + core::fmt::Debug,

  + V: Representable<T> + core::fmt::Debug,

  + > super::BTreeMutPage<T, K, V> for Page<K, V>
• edit in sanakirja-core/src/btree/page.rs at line 99
  [3.1799]

  [3.10687]
  + if let Some((k, v)) = m.ins2 {

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

  + }
• replacement in sanakirja-core/src/btree/page.rs at line 104
  [3.10772]→[3.10772:10806](∅→∅)
  − occupied += 2
  [3.10772]

  [3.10806]
  + if m.ins2.is_some() {

  + occupied += 4;

  + } else {

  + occupied += 2;

  + }
• edit in sanakirja-core/src/btree/page.rs at line 110
  [3.10824]

  [3.10824]
  + } else if m.ins2.is_some() {

  + occupied += 16
• edit in sanakirja-core/src/btree/page.rs at line 126
  [3.11068]

  [3.11068]
  + k1v1: Option<(&'a K, &'a V)>,
• replacement in sanakirja-core/src/btree/page.rs at line 131
  [3.1844]→[3.1844:1918](∅→∅)
  − put::<_, _, _, Leaf>(txn, page, mutable, c.cur, k0, v0, 0, 0)
  [3.1844]

  [3.1918]
  + put::<_, _, _, Leaf>(txn, page, mutable, c.cur, k0, v0, k1v1, 0, 0)
• replacement in sanakirja-core/src/btree/page.rs at line 133
  [3.1935]→[3.1935:2013](∅→∅)
  − put::<_, _, _, Internal>(txn, page, mutable, c.cur, k0, v0, l, r)
  [3.1935]

  [3.11455]
  + put::<_, _, _, Internal>(txn, page, mutable, c.cur, k0, v0, k1v1, l, r)
• edit in sanakirja-core/src/btree/page.rs at line 137
  [3.11472]

  [3.11472]
  + fn replace<'a>(

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

  + // We're never in a leaf if we're doing this.

  + assert!(l > 0);

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

  + Self::put(txn, new.0, mutable, c, k0, v0, k1v1, l, r)

  + }

  +
• replacement in sanakirja-core/src/btree/page.rs at line 163
  [3.11691]→[3.2038:2130](∅→∅)
  − debug!("update_left_child: {:?} {:?} {:?}", page, mutable, header(page.as_page()));
  [3.11691]

  [3.2130]
  + debug!(

  + "update_left_child: {:?} {:?} {:?}",

  + page,

  + mutable,

  + header(page.as_page())

  + );
• replacement in sanakirja-core/src/btree/page.rs at line 201
  [3.2954]→[3.2954:4160](∅→∅)
  − unsafe { if c.is_leaf {

  − let n = hdr.n() as usize;

  − if let Some(f) = fixed_size::<T, K, V>() {

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

  − let hdr_size = (HDR + al - 1) & !(al - 1);

  − let off = c.cur * f;

  − let kv_ptr = p.add(hdr_size + off);

  − core::ptr::copy(kv_ptr.add(f), kv_ptr, f * (n - c.cur - 1));

  − hdr.decr(f);

  − } else {

  − let ptr = p.add(HDR + c.cur * 2) as *mut u16;

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

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

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

  − hdr.decr(size);

  − }

  − } else {

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

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

  − let kv_ptr = p.add(off);

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

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

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

  − }};
  [3.2954]

  [3.4160]
  + unsafe {

  + if c.is_leaf {

  + let n = hdr.n() as usize;

  + if let Some(f) = fixed_size::<T, K, V>() {

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

  + let hdr_size = (HDR + al - 1) & !(al - 1);

  + let off = c.cur * f;

  + let kv_ptr = p.add(hdr_size + off);

  + core::ptr::copy(kv_ptr.add(f), kv_ptr, f * (n - c.cur - 1));

  + hdr.decr(f);

  + } else {

  + let ptr = p.add(HDR + c.cur * 2) as *mut u16;

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

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

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

  + hdr.decr(size);

  + }

  + } else {

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

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

  + let kv_ptr = p.add(off);

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

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

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

  + }

  + };
• replacement in sanakirja-core/src/btree/page.rs at line 277
  [3.16292]→[3.16292:16341](∅→∅)
  − let left_size = Self::size(&m.modified);
  [3.16292]

  [3.5228]
  + let mod_size = Self::size(&m.modified);
• replacement in sanakirja-core/src/btree/page.rs at line 282
  [3.16473]→[3.16473:16536](∅→∅),[3.16536]→[3.5303:5401](∅→∅)
  − let size = left_size + mid_size + occupied - hdr_size;

  − debug!("size = {:?} {:?} {:?} {:?} {:?}", left_size, mid_size, occupied, hdr_size, size);
  [3.16473]

  [3.16536]
  + let size = mod_size + mid_size + occupied - hdr_size;

  + debug!(

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

  + mod_size, mid_size, occupied, hdr_size, size

  + );
• replacement in sanakirja-core/src/btree/page.rs at line 303
  [3.17048]→[3.5702:5778](∅→∅)
  − let b1 = if Self::is_dirty(m.other.as_page()) { 1 } else { 0 };
  [3.17048]

  [3.17114]
  + let b1 = if Self::is_dirty(m.other.as_page()) {

  + 1

  + } else {

  + 0

  + };
• replacement in sanakirja-core/src/btree/page.rs at line 316
  [3.5920]→[3.17451:17574](∅→∅),[3.17451]→[3.17451:17574](∅→∅),[3.17574]→[2.118:187](∅→∅),[2.187]→[3.5993:6024](∅→∅),[3.5993]→[3.5993:6024](∅→∅)
  − // If we can't rebalance, return.

  − if left_size >= PAGE_SIZE / 2 || occupied - first_size < PAGE_SIZE / 2 {

  − return Ok(Op::Put(if let Some((k, v)) = m.modified.ins {

  − Self::replace(
  [3.5920]

  [3.6024]
  + // If we can't rebalance, modify and return.

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

  + if let Some((k, v)) = m.modified.ins {

  + return Ok(Op::Put(Self::replace(
• replacement in sanakirja-core/src/btree/page.rs at line 324
  [3.6162]→[3.6162:6212](∅→∅)
  − &*k,

  − &*v,
  [3.6162]

  [3.6212]
  + k,

  + v,

  + m.modified.ins2,
• replacement in sanakirja-core/src/btree/page.rs at line 329
  [2.222]→[3.6269:6288](∅→∅),[3.6269]→[3.6269:6288](∅→∅)
  − )?
  [2.222]

  [3.6288]
  + )?));
• replacement in sanakirja-core/src/btree/page.rs at line 331
  [3.6309]→[3.6309:6338](∅→∅)
  − Put::Ok(Ok {
  [3.6309]

  [3.6338]
  + return Ok(Op::Put(Put::Ok(Ok {
• replacement in sanakirja-core/src/btree/page.rs at line 334
  [3.6458]→[3.6458:6494](∅→∅)
  − })

  − }));
  [3.6458]

  [3.18250]
  + })));

  + }
• replacement in sanakirja-core/src/btree/page.rs at line 381
  [3.19408]→[3.7155:7257](∅→∅)
  − unsafe fn unchecked_current<'a>(page: crate::Page<'a>, c: &Self::Cursor) -> (&'a K, &'a V, u64) {
  [3.19408]

  [3.19505]
  + unsafe fn unchecked_current<'a>(

  + page: crate::Page<'a>,

  + c: &Self::Cursor,

  + ) -> (&'a K, &'a V, u64) {
• replacement in sanakirja-core/src/btree/page.rs at line 411
  [3.20628]→[3.7915:8017](∅→∅)
  − (u64::from_le(*(page.data.as_ptr().add(HDR + c.cur * 8) as *const u64)) & 0xfff) as usize
  [3.20628]

  [3.20721]
  + (u64::from_le(*(page.data.as_ptr().add(HDR + c.cur * 8) as *const u64)) & 0xfff)

  + as usize
• replacement in sanakirja-core/src/btree/page.rs at line 421
  [3.20957]→[3.20957:21038](∅→∅),[3.21038]→[3.8087:8228](∅→∅),[3.8228]→[3.21132:21175](∅→∅),[3.21132]→[3.21132:21175](∅→∅)
  − 2 + entry_size::<T, K, V>(

  − page.data

  − .as_ptr()

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

  − as usize),
  [3.20957]

  [3.21175]
  + 2 + entry_size::<T, K, V>(page.data.as_ptr().add(u16::from_le(

  + *(page.data.as_ptr().add(HDR) as *const u16).add(c.cur),
• edit in sanakirja-core/src/btree/page.rs at line 424
  [3.21197]

  [3.21197]
  + as usize))
• replacement in sanakirja-core/src/btree/page.rs at line 428
  [3.8295]→[3.8295:8405](∅→∅)
  − (u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur)) & 0xfff) as usize,
  [3.8295]

  [3.21394]
  + (u64::from_le(*(page.data.as_ptr().add(HDR) as *const u64).add(c.cur)) & 0xfff)

  + as usize,
• replacement in sanakirja-core/src/btree/page.rs at line 485
  [3.24989]→[3.9112:9218](∅→∅)
  − let off = u16::from_le(*(page.data.as_ptr().add(HDR + n * 2) as *const u16));
  [3.24989]

  [3.25086]
  + let off =

  + u16::from_le(*(page.data.as_ptr().add(HDR + n * 2) as *const u16));
• replacement in sanakirja-core/src/btree/page.rs at line 491
  [3.25228]→[3.9268:9370](∅→∅)
  − let off = u64::from_le(*(page.data.as_ptr().add(HDR + n * 8) as *const u64));
  [3.25228]

  [3.9370]
  + let off =

  + u64::from_le(*(page.data.as_ptr().add(HDR + n * 8) as *const u64));
• edit in sanakirja-core/src/btree/page.rs at line 528
  [3.9543]→[3.9543:9544](∅→∅),[3.9544]→[3.26192:26193](∅→∅),[3.26192]→[3.26192:26193](∅→∅)
  −

  −
• replacement in sanakirja-core/src/btree/page.rs at line 547
  [3.10186]→[3.10186:10315](∅→∅)
  − s.binary_search_by(|tup| {

  − (tup.k.ord(txn), tup.v.ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))
  [3.10186]

  [3.10315]
  + s.binary_search_by(|tup| match tup.k.compare(txn, &k0) {

  + Ordering::Equal => tup.v.compare(txn, &v0),

  + c => c,
• replacement in sanakirja-core/src/btree/page.rs at line 552
  [3.10355]→[3.10355:10471](∅→∅)
  − s.binary_search_by(|tup| {

  − (tup.k.ord(txn)).cmp(k0.ord(txn))

  − })
  [3.10355]

  [3.10471]
  + s.binary_search_by(|tup| tup.k.compare(txn, k0))
• replacement in sanakirja-core/src/btree/page.rs at line 563
  [3.10878]→[3.10878:10964](∅→∅)
  − ((&*k).ord(txn), (&*v).ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))
  [3.10878]

  [3.10964]
  + match (&*k).compare(txn, k0) {

  + Ordering::Equal => (&*v).compare(txn, v0),

  + cmp => cmp,

  + }
• replacement in sanakirja-core/src/btree/page.rs at line 572
  [3.11188]→[3.11188:11242](∅→∅)
  − ((&*k).ord(txn)).cmp(k0.ord(txn))
  [3.11188]

  [3.11242]
  + (&*k).compare(txn, k0)
• replacement in sanakirja-core/src/btree/page.rs at line 577
  [3.11298]→[3.11298:11416](∅→∅)
  − let s =

  − core::slice::from_raw_parts(page.data.as_ptr().add(HDR) as *const u64, hdr.n() as usize);
  [3.11298]

  [3.11416]
  + let s = core::slice::from_raw_parts(

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

  + hdr.n() as usize,

  + );
• replacement in sanakirja-core/src/btree/page.rs at line 585
  [3.11635]→[3.11635:11717](∅→∅)
  − ((&*k).ord(txn), (&*v).ord(txn)).cmp(&(k0.ord(txn), v0.ord(txn)))
  [3.11635]

  [3.11717]
  + match (&*k).compare(txn, k0) {

  + Ordering::Equal => (&*v).compare(txn, v0),

  + cmp => cmp,

  + }
• replacement in sanakirja-core/src/btree/page.rs at line 594
  [3.11937]→[3.11937:11987](∅→∅)
  − ((&*k).ord(txn)).cmp(k0.ord(txn))
  [3.11937]

  [3.11987]
  + (&*k).compare(txn, k0)
• edit in sanakirja-core/src/btree/page.rs at line 600
  [3.12021]→[3.12021:12029](∅→∅)
  −

  −

  −

  −

  −

  −

  −

  −
• replacement in sanakirja-core/src/btree/page.rs at line 608
  [3.12083]→[3.12083:12150](∅→∅)
  − unsafe {

  − &*(page.data.as_ptr() as *const Header)

  − }
  [3.12083]

  [3.26386]
  + unsafe { &*(page.data.as_ptr() as *const Header) }
• replacement in sanakirja-core/src/btree/page.rs at line 612
  [3.12210]→[3.12210:12272](∅→∅)
  − unsafe {

  − &mut *(page.0.data as *mut Header)

  − }
  [3.12210]

  [3.26479]
  + unsafe { &mut *(page.0.data as *mut Header) }
• replacement in sanakirja-core/src/btree/page.rs at line 616
  [3.26496]→[3.12273:12336](∅→∅),[3.12336]→[3.26566:26624](∅→∅),[3.26566]→[3.26566:26624](∅→∅),[3.26624]→[3.12337:12402](∅→∅),[3.12402]→[3.26696:26754](∅→∅),[3.26696]→[3.26696:26754](∅→∅)
  − fn can_alloc<T, K: Representable<T>, V: Representable<T>>(

  − hdr: &Header,

  − size: usize,

  − ) -> bool;

  − fn can_compact<T, K: Representable<T>, V: Representable<T>>(

  − hdr: &Header,

  − size: usize,

  − ) -> bool;
  [3.26496]

  [3.12403]
  + fn extra_size<T, K: Representable<T>, V: Representable<T>>() -> usize;

  + fn can_alloc<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool;

  + fn can_compact<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool;
• replacement in sanakirja-core/src/btree/page.rs at line 622
  [3.12507]→[3.313:442](∅→∅)
  − fn truncate_left<T, K: Representable<T>, V: Representable<T>>(page: &mut MutPage, n: usize) -> Option<(*const K, *const V)>;
  [3.12507]

  [3.12604]
  + fn truncate_left<T, K: Representable<T>, V: Representable<T>>(

  + page: &mut MutPage,

  + n: usize,

  + ) -> Option<(*const K, *const V)>;
• replacement in sanakirja-core/src/btree/page.rs at line 686
  [3.28732]→[3.13294:13357](∅→∅),[3.13357]→[3.28802:28861](∅→∅),[3.28802]→[3.28802:28861](∅→∅)
  − fn can_alloc<T, K: Representable<T>, V: Representable<T>>(

  − hdr: &Header,

  − size: usize,

  − ) -> bool {
  [3.28732]

  [3.28861]
  + fn extra_size<T, K: Representable<T>, V: Representable<T>>() -> usize {

  + if fixed_size::<T, K, V>().is_some() {

  + 0

  + } else {

  + 2

  + }

  + }

  + fn can_alloc<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {
• replacement in sanakirja-core/src/btree/page.rs at line 697
  [3.29015]→[3.13358:13442](∅→∅)
  − debug!("Leaf::can_alloc: {:?} {:?} {:?}", header_size, size, hdr.data);
  [3.29015]

  [3.29015]
  + debug!(

  + "Leaf::can_alloc: {:?} {:?} {:?}",

  + header_size, size, hdr.data

  + );
• replacement in sanakirja-core/src/btree/page.rs at line 706
  [3.29224]→[3.13443:13508](∅→∅),[3.13508]→[3.29296:29355](∅→∅),[3.29296]→[3.29296:29355](∅→∅)
  − fn can_compact<T, K: Representable<T>, V: Representable<T>>(

  − hdr: &Header,

  − size: usize,

  − ) -> bool {
  [3.29224]

  [3.29355]
  + fn can_compact<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {
• replacement in sanakirja-core/src/btree/page.rs at line 716
  [3.29731]→[3.443:573](∅→∅)
  − fn truncate_left<T, K: Representable<T>, V: Representable<T>>(page: &mut MutPage, n: usize) -> Option<(*const K, *const V)> {
  [3.29731]

  [3.13607]
  + fn truncate_left<T, K: Representable<T>, V: Representable<T>>(

  + page: &mut MutPage,

  + n: usize,

  + ) -> Option<(*const K, *const V)> {
• edit in sanakirja-core/src/btree/page.rs at line 727
  [3.575]→[3.575:576](∅→∅)
  −
• replacement in sanakirja-core/src/btree/page.rs at line 728
  [3.13936]→[3.577:679](∅→∅)
  − let mut swap: core::mem::MaybeUninit<Tuple<K, V>> = core::mem::MaybeUninit::uninit();
  [3.13936]

  [3.679]
  + let mut swap: core::mem::MaybeUninit<Tuple<K, V>> =

  + core::mem::MaybeUninit::uninit();
• replacement in sanakirja-core/src/btree/page.rs at line 731
  [3.712]→[3.712:771](∅→∅)
  − page.0.data.add(hdr_size + (n-1) * f),
  [3.712]

  [3.771]
  + page.0.data.add(hdr_size + (n - 1) * f),
• replacement in sanakirja-core/src/btree/page.rs at line 751
  [3.1173]→[3.1173:1265](∅→∅)
  − Some(read::<T, K, V>(page.0.data.add(hdr_size + (hdr_n as usize - n) * f)))
  [3.1173]

  [3.1265]
  + Some(read::<T, K, V>(

  + page.0.data.add(hdr_size + (hdr_n as usize - n) * f),

  + ))
• replacement in sanakirja-core/src/btree/page.rs at line 765
  [3.14639]→[3.14639:14790](∅→∅)
  − core::slice::from_raw_parts(

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

  − n as usize,

  − )
  [3.14639]

  [3.14790]
  + core::slice::from_raw_parts(page.0.data.add(HDR) as *const u16, n as usize)
• replacement in sanakirja-core/src/btree/page.rs at line 767
  [3.14805]→[3.14805:14990](∅→∅)
  − let deleted_size: u64 = deleted_offsets.iter().map(|&off| {

  − 2 + unsafe { entry_size::<T, K, V>(page.0.data.add(off as usize)) } as u64

  − }).sum();
  [3.14805]

  [3.14990]
  + let deleted_size: u64 = deleted_offsets

  + .iter()

  + .map(|&off| {

  + 2 + unsafe { entry_size::<T, K, V>(page.0.data.add(off as usize)) } as u64

  + })

  + .sum();
• replacement in sanakirja-core/src/btree/page.rs at line 812
  [3.15805]→[3.15805:15873](∅→∅)
  − (hdr.n(), Self::alloc(&mut *hdr, 2+size, K::ALIGN))
  [3.15805]

  [3.15873]
  + (

  + hdr.n(),

  + Self::alloc(&mut *hdr, 2 + size, K::ALIGN.max(V::ALIGN)),

  + )
• replacement in sanakirja-core/src/btree/page.rs at line 855
  [3.32088]→[3.16895:16928](∅→∅)
  − ) -> (&'a K, &'a V, u64) {
  [3.32088]

  [3.16928]
  + ) -> (&'a K, &'a V, u64) {
• replacement in sanakirja-core/src/btree/page.rs at line 858
  [3.17025]→[3.17025:17053](∅→∅)
  − (& *k, & *v, 0)
  [3.17025]

  [3.17053]
  + (&*k, &*v, 0)
• replacement in sanakirja-core/src/btree/page.rs at line 864
  [3.32259]→[3.17064:17127](∅→∅),[3.17127]→[3.32329:32388](∅→∅),[3.32329]→[3.32329:32388](∅→∅)
  − fn can_alloc<T, K: Representable<T>, V: Representable<T>>(

  − hdr: &Header,

  − size: usize,

  − ) -> bool {
  [3.32259]

  [3.17128]
  + fn extra_size<T, K: Representable<T>, V: Representable<T>>() -> usize {

  + 8

  + }

  + fn can_alloc<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {
• replacement in sanakirja-core/src/btree/page.rs at line 871
  [3.32487]→[3.17198:17263](∅→∅),[3.17263]→[3.32559:32618](∅→∅),[3.32559]→[3.32559:32618](∅→∅)
  − fn can_compact<T, K: Representable<T>, V: Representable<T>>(

  − hdr: &Header,

  − size: usize,

  − ) -> bool {
  [3.32487]

  [3.32618]
  + fn can_compact<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {
• replacement in sanakirja-core/src/btree/page.rs at line 874
  [3.32704]→[3.1345:1475](∅→∅)
  − fn truncate_left<T, K: Representable<T>, V: Representable<T>>(page: &mut MutPage, n: usize) -> Option<(*const K, *const V)> {
  [3.32704]

  [3.17362]
  + fn truncate_left<T, K: Representable<T>, V: Representable<T>>(

  + page: &mut MutPage,

  + n: usize,

  + ) -> Option<(*const K, *const V)> {
• replacement in sanakirja-core/src/btree/page.rs at line 897
  [3.18064]→[3.18064:18216](∅→∅)
  − offsets.iter().map(|&off| {

  − 8 + unsafe { entry_size::<T, K, V>(page.0.data.add(off as usize)) } as u64

  − }).sum()
  [3.18064]

  [3.18216]
  + offsets

  + .iter()

  + .map(|&off| {

  + 8 + unsafe { entry_size::<T, K, V>(page.0.data.add(off as usize)) } as u64

  + })

  + .sum()
• replacement in sanakirja-core/src/btree/page.rs at line 927
  [3.18670]→[3.18670:18746](∅→∅)
  − (hdr.n(), Self::alloc(&mut *hdr, size, K::ALIGN.max(V::ALIGN)))
  [3.18670]

  [3.18746]
  + (

  + hdr.n(),

  + Self::alloc(&mut *hdr, size, K::ALIGN.max(V::ALIGN)),

  + )
• replacement in sanakirja-core/src/btree/page.rs at line 971
  [3.34486]→[3.19924:19957](∅→∅)
  − ) -> (&'a K, &'a V, u64) {
  [3.34486]

  [3.19957]
  + ) -> (&'a K, &'a V, u64) {
• replacement in sanakirja-core/src/btree/page.rs at line 974
  [3.20054]→[3.20054:20082](∅→∅)
  − (& *k, & *v, r)
  [3.20054]

  [3.20082]
  + (&*k, &*v, r)
• replacement in sanakirja-core/src/btree/page.rs at line 979
  [3.34631]→[3.1647:1787](∅→∅)
  − unsafe fn modify<T: LoadPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(
  [3.34631]

  [3.20093]
  + unsafe fn modify<

  + T: LoadPage + core::fmt::Debug,

  + K: Representable<T> + core::fmt::Debug,

  + V: Representable<T> + core::fmt::Debug,

  + L: Alloc,

  + >(
• replacement in sanakirja-core/src/btree/page.rs at line 996
  [2.744]→[2.744:801](∅→∅)
  − alloc::<_, _, _, L>(new, &*k, &*v, m.l, m.r, n);
  [2.744]

  [3.35142]
  + if let Some((k2, v2)) = m.ins2 {

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

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

  + } else {

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

  + }
• replacement in sanakirja-core/src/btree/page.rs at line 1016
  [3.35449]→[3.1819:1958](∅→∅)
  − unsafe fn merge<T: LoadPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(
  [3.35449]

  [3.20505]
  + unsafe fn merge<

  + T: LoadPage + core::fmt::Debug,

  + K: Representable<T> + core::fmt::Debug,

  + V: Representable<T> + core::fmt::Debug,

  + L: Alloc,

  + >(
• replacement in sanakirja-core/src/btree/page.rs at line 1046
  [3.36508]→[2.802:948](∅→∅)
  − fn rebalance_left<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(
  [3.36508]

  [3.36599]
  + fn rebalance_left<

  + 'a,

  + T: AllocPage + core::fmt::Debug,

  + K: Representable<T> + core::fmt::Debug,

  + V: Representable<T> + core::fmt::Debug,

  + L: Alloc,

  + >(
• replacement in sanakirja-core/src/btree/page.rs at line 1064
  [3.36942]→[2.1059:1137](∅→∅)
  − let b = if header(m.modified.page.as_page()).is_dirty() { 1 } else { 0 };
  [3.36942]

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

  + 1

  + } else {

  + 0

  + };
• replacement in sanakirja-core/src/btree/page.rs at line 1077
  [2.1414]→[2.1414:1448](∅→∅)
  − &*k,

  − &*v,
  [2.1414]

  [2.1448]
  + k,

  + v,

  + m.modified.ins2,
• edit in sanakirja-core/src/btree/page.rs at line 1092
  [2.1803]→[2.1803:1805](∅→∅)
  −

  −
• replacement in sanakirja-core/src/btree/page.rs at line 1111
  [2.2679]→[2.2679:2701](∅→∅)
  − 1
  [2.2679]

  [2.2701]
  + 1,
• replacement in sanakirja-core/src/btree/page.rs at line 1116
  [2.2879]→[2.2879:2903](∅→∅)
  − n-1
  [2.2879]

  [2.2903]
  + n - 1,
• replacement in sanakirja-core/src/btree/page.rs at line 1118
  [2.2922]→[2.2922:3148](∅→∅)
  − let last = data.add(hdr_size + f * (n-1)) as *mut Tuple<K, V>;

  − core::ptr::copy_nonoverlapping(

  − t.as_ptr(),

  − last,

  − 1

  − );
  [2.2922]

  [2.3148]
  + let last = data.add(hdr_size + f * (n - 1)) as *mut Tuple<K, V>;

  + core::ptr::copy_nonoverlapping(t.as_ptr(), last, 1);
• replacement in sanakirja-core/src/btree/page.rs at line 1125
  [2.3301]→[2.3301:3442](∅→∅)
  − (<Page<K, V>>::del(txn, m.other, &rc, r)?,

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

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

  − }
  [2.3301]

  [3.37695]
  + (

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

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

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

  + )

  + },
• replacement in sanakirja-core/src/btree/page.rs at line 1146
  [2.3444]→[2.3444:3594](∅→∅)
  −

  −

  −

  − fn rebalance_right<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(
  [2.3444]

  [2.3594]
  + fn rebalance_right<

  + 'a,

  + T: AllocPage + core::fmt::Debug,

  + K: Representable<T> + core::fmt::Debug,

  + V: Representable<T> + core::fmt::Debug,

  + L: Alloc,

  + >(
• edit in sanakirja-core/src/btree/page.rs at line 1164
  [2.4103]→[2.4103:4104](∅→∅)
  −
• replacement in sanakirja-core/src/btree/page.rs at line 1166
  [2.4133]→[2.4133:4211](∅→∅)
  − let b = if header(m.modified.page.as_page()).is_dirty() { 1 } else { 0 };
  [2.4133]

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

  + 1

  + } else {

  + 0

  + };
• replacement in sanakirja-core/src/btree/page.rs at line 1179
  [2.4489]→[2.4489:4523](∅→∅)
  − &*k,

  − &*v,
  [2.4489]

  [2.4523]
  + k,

  + v,

  + m.modified.ins2,
• replacement in sanakirja-core/src/btree/page.rs at line 1192
  [2.4758]→[2.4758:4943](∅→∅)
  − if let Put::Ok(Ok { page, .. }) = <Page<K, V>>::put(

  − txn,

  − new_right.0,

  − true,

  − &rc,

  − m.mid.0,

  − m.mid.1,

  − r0,

  − rl,

  − )? {
  [2.4758]

  [2.4943]
  + if let Put::Ok(Ok { page, .. }) =

  + <Page<K, V>>::put(txn, new_right.0, true, &rc, m.mid.0, m.mid.1, None, r0, rl)?

  + {
• edit in sanakirja-core/src/btree/page.rs at line 1214
  [2.5466]→[2.5466:5467](∅→∅)
  −
• replacement in sanakirja-core/src/btree/page.rs at line 1263
  [3.22851]→[3.22851:22916](∅→∅)
  − let off_new = L::alloc(hdr, size, K::ALIGN);
  [3.22851]

  [3.22916]
  + let off_new = L::alloc(hdr, size, K::ALIGN.max(V::ALIGN));
• replacement in sanakirja-core/src/btree/page.rs at line 1314
  [3.40625]→[3.2101:2236](∅→∅)
  − fn put<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(
  [3.40625]

  [3.40710]
  + fn put<

  + 'a,

  + T: AllocPage + core::fmt::Debug,

  + K: Representable<T> + core::fmt::Debug,

  + V: Representable<T> + core::fmt::Debug,

  + L: Alloc,

  + >(
• edit in sanakirja-core/src/btree/page.rs at line 1327
  [3.40813]

  [3.40813]
  + k1v1: Option<(&'a K, &'a V)>,
• replacement in sanakirja-core/src/btree/page.rs at line 1331
  [3.40876]→[3.40876:40911](∅→∅)
  − let size = alloc_size(k0, v0);
  [3.40876]

  [3.24178]
  + let size = alloc_size(k0, v0)

  + + if let Some((k1, v1)) = k1v1 {

  + alloc_size(k1, v1)

  + } else {

  + 0

  + };
• replacement in sanakirja-core/src/btree/page.rs at line 1344
  [3.41135]→[3.24485:24547](∅→∅)
  − alloc::<_, _, _, L>(&mut page, k0, v0, l, r, &mut n);
  [3.41135]

  [3.41197]
  + if let Some((k1, v1)) = k1v1 {

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

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

  + } else {

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

  + }
• replacement in sanakirja-core/src/btree/page.rs at line 1360
  [3.24888]→[3.24888:24949](∅→∅)
  − alloc::<T, K, V, L>(&mut new, k0, v0, l, r, &mut n);
  [3.24888]

  [3.24949]
  + if let Some((k1, v1)) = k1v1 {

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

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

  + } else {

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

  + }
• replacement in sanakirja-core/src/btree/page.rs at line 1378
  [3.42042]→[3.25091:25186](∅→∅)
  − return split_unsized::<_, _, _, L>(txn, page.as_page(), mutable, u, k0, v0, l, r);
  [3.42042]

  [3.42127]
  + return split_unsized::<_, _, _, L>(txn, page.as_page(), u, k0, v0, k1v1, l, r);
• replacement in sanakirja-core/src/btree/page.rs at line 1383
  [3.42146]→[3.2237:2374](∅→∅)
  − fn split<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(
  [3.42146]

  [3.42233]
  + fn split<

  + 'a,

  + T: AllocPage + core::fmt::Debug,

  + K: Representable<T> + core::fmt::Debug,

  + V: Representable<T> + core::fmt::Debug,

  + L: Alloc,

  + >(
• replacement in sanakirja-core/src/btree/page.rs at line 1507
  [3.45433]→[3.28226:28314](∅→∅),[3.28314]→[3.45528:45663](∅→∅),[3.45528]→[3.45528:45663](∅→∅)
  − fn split_unsized<'a, T: AllocPage, K: Representable<T>, V: Representable<T>, L: Alloc>(

  − _txn: &mut T,

  − _page: crate::Page,

  − _mutable: bool,

  − _u: usize,

  − _k0: &'a K,

  − _v0: &'a V,

  − _l: u64,

  − _r: u64,
  [3.45433]

  [3.45663]
  + fn split_unsized<

  + 'a,

  + T: AllocPage+ core::fmt::Debug,

  + K: Representable<T> + core::fmt::Debug,

  + V: Representable<T> + core::fmt::Debug,

  + L: Alloc,

  + >(

  + txn: &mut T,

  + page: crate::Page,

  + u: usize,

  + k0: &'a K,

  + v0: &'a V,

  + k1v1: Option<(&'a K, &'a V)>,

  + l0: u64,

  + r0: u64,
• replacement in sanakirja-core/src/btree/page.rs at line 1523
  [3.45702]→[3.45702:45723](∅→∅)
  − unimplemented!()
  [3.45702]

  [3.45723]
  + let hdr = header(page);

  + let n0 = hdr.n();

  +

  + let mut left = txn.alloc_page()?;

  + <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut left);

  +

  + let mut right = txn.alloc_page()?;

  + <Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut left);

  +

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

  + L::set_right_child(&mut left, -1, left_child);

  +

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

  + let mut current_page = &mut left;

  +

  + let mut n = 0;

  + let s = unsafe {core::slice::from_raw_parts(

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

  + n0 as usize,

  + )};

  + let mut total = HDR;

  + let mut is_left = true;

  + for off in s.iter() {

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

  + unsafe {

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

  + let size = entry_size::<T, K, V>(ptr) + L::extra_size::<T, K, V>();

  + total += size;

  + if is_left && total >= PAGE_SIZE / 2 {

  + is_left = false;

  + split = ptr as *const Tuple<K, V>;

  + L::set_right_child(&mut right, -1, r);

  + current_page = &mut right;

  + } else {

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

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

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

  + }

  + }

  + n += 1;

  + if n == u as isize {

  + if let Some((k1, v1)) = k1v1 {

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

  + total += alloc_size(k0, v0) + L::extra_size::<T, K, V>();

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

  + total += alloc_size(k1, v1) + L::extra_size::<T, K, V>();

  + n += 2;

  + } else {

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

  + total += alloc_size(k0, v0) + L::extra_size::<T, K, V>();

  + n += 1;

  + }

  + }

  + }

  + assert!(!split.is_null());

  + let split = unsafe { &*split };

  + Ok(Put::Split {

  + split_key: &split.k,

  + split_value: &split.v,

  + left,

  + right,

  + freed: page.offset,

  + })
• edit in sanakirja-core/src/btree/mod.rs at line 111
  [3.48426]

  [3.48426]
  + k1v1: Option<(&'a K, &'a V)>,
• edit in sanakirja-core/src/btree/mod.rs at line 133
  [3.48906]

  [3.48906]
  + k1v1: Option<(&'a K, &'a V)>,
• replacement in sanakirja-core/src/btree/mod.rs at line 136
  [3.48938]→[3.48938:49207](∅→∅)
  − ) -> Result<Put<'a, K, V>, T::Error> {

  − // TODO: optimise this for page::Page<K, V>, since this moves

  − // all the offsets twice in this case.

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

  − Self::put(txn, new.0, mutable, c, k0, v0, l, r)

  − }
  [3.48938]

  [3.49207]
  + ) -> Result<Put<'a, K, V>, T::Error>;
• replacement in sanakirja-core/src/btree/mod.rs at line 149
  [3.30159]→[2.5508:5589](∅→∅)
  − Self::replace(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, m.r)
  [3.30159]

  [3.49773]
  + Self::replace(txn, m.page, m.mutable, &m.c1, k, v, m.ins2, m.l, m.r)
• replacement in sanakirja-core/src/btree/mod.rs at line 151
  [3.49794]→[2.5590:5667](∅→∅)
  − Self::put(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, m.r)
  [3.49794]

  [3.50115]
  + Self::put(txn, m.page, m.mutable, &m.c1, k, v, m.ins2, m.l, m.r)
• replacement in sanakirja-core/src/btree/mod.rs at line 207
  [3.50858]→[3.50858:50920](∅→∅)
  − // Replace the right child of c0's last element with `l`.
  [3.50858]

  [3.50920]
  + // If > 0, replace the right child of c0's last element with `l`.
• replacement in sanakirja-core/src/btree/mod.rs at line 209
  [3.50936]→[2.5914:5975](∅→∅)
  − // Replace the left child of c1's last element with `r`.
  [3.50936]

  [2.5975]
  + // If > 0, replace the left child of c1's last element with `r`.
• edit in sanakirja-core/src/btree/mod.rs at line 213
  [2.6029]

  [3.51022]
  + pub ins2: Option<(&'a K, &'a V)>,
• edit in sanakirja-core/src/btree/del.rs at line 68
  [3.54649]

  [3.54649]
  + ins2: None,
• edit in sanakirja-core/src/btree/del.rs at line 139
  [3.56145]

  [3.56145]
  + // If we're deleting at an internal node, the

  + // replacement has already been included in the merged

  + // page.
• edit in sanakirja-core/src/btree/del.rs at line 149
  [3.56385]

  [3.56385]
  + ins2: None,
• edit in sanakirja-core/src/btree/del.rs at line 163
  [3.56877]

  [3.57005]
  + // If we're deleting at an internal node, the

  + // replacement is already in pages `l` or `r`.
• edit in sanakirja-core/src/btree/del.rs at line 172
  [2.7092]

  [3.57241]
  + ins2: None,
• edit in sanakirja-core/src/btree/del.rs at line 186
  [3.57733]

  [2.7093]
  + // Here, no merge, split or rebalance has happened. If

  + // we're deleting at an internal node (i.e. if

  + // cursor.pointer == p0), we need to mark the

  + // replacement here.
• edit in sanakirja-core/src/btree/del.rs at line 191
  [2.7165]→[2.7165:7231](∅→∅)
  − let l = P::left_child(page.0.as_page(), &c1);
• replacement in sanakirja-core/src/btree/del.rs at line 193
  [2.7339]→[2.7339:7398](∅→∅)
  − (l, page.0.offset, Some((k, v)), true)
  [2.7339]

  [2.7398]
  + (0, page.0.offset, Some((k, v)), true)
• edit in sanakirja-core/src/btree/del.rs at line 206
  [2.7665]

  [3.57973]
  + ins2: None,
• replacement in sanakirja-core/src/btree/del.rs at line 226
  [3.58592]→[2.7699:8057](∅→∅)
  − // Here, if we are at cursor.pointer == p0, the

  − // replacement has been either inserted into one of

  − // {left, right}, or is the split key/value

  − // itself. Therefore, we just have to delete the

  − // key/value selected for deletion in page p0 (the

  − // current page).
  [3.58592]

  [3.58592]
  + let (ins, ins2, skip_first) = if cursor.pointer == p0 {

  + let k = unsafe { &*k0.as_ptr() };

  + let v = unsafe { &*v0.as_ptr() };

  + (Some((k, v)), Some((split_key, split_value)), true)

  + } else {

  + (Some((split_key, split_value)), None, false)

  + };
• replacement in sanakirja-core/src/btree/del.rs at line 239
  [2.8097]→[2.8097:8154](∅→∅)
  − ins: Some((split_key, split_value)),
  [2.8097]

  [3.58874]
  + ins,

  + ins2,
• replacement in sanakirja-core/src/btree/del.rs at line 242
  [3.58898]→[2.8155:8209](∅→∅)
  − skip_first: cursor.pointer == p0,
  [3.58898]

  [3.58937]
  + skip_first,
• edit in sanakirja-core/src/btree/del.rs at line 294
  [3.60399]

  [3.60399]
  + None,