Splitting btree::page

Dependencies

• [2] ONES3V46 reference counting works for put
• [3] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
• [4] OP6SVMOD Resetting history
• [5] UAQX27N4 Tests
• [6] YWFYZNLZ Cleanup + inter-process concurrency
• [7] R5AJGJPT Minor performance improvement
• [8] X3QVVQIS More debugging (del seems to work now)
• [9] FMN7X4J2 Micro-improvements, now noticeably faster than std::collections::BTreeMap
• [10] EHJFNMB2 Debugging
• [11] EAAYH6BQ Debugging put
• [12] WS4ZQM4R Debugging, tests, etc.

Change contents

• edit in sanakirja-core/src/btree/page.rs at line 3
  [3.269]→[3.269:297](∅→∅)
  − use core::mem::MaybeUninit;
• edit in sanakirja-core/src/btree/page.rs at line 5
  [4.8651]

  [4.8651]
  + mod put;

  + mod alloc;

  + use alloc::*;

  + mod header;

  + use header::*;

  + mod rebalance;

  + use rebalance::*;

  +
• edit in sanakirja-core/src/btree/page.rs at line 27
  [4.8867]→[4.1201:1218](∅→∅),[4.1218]→[4.8867:8997](∅→∅),[4.8867]→[4.8867:8997](∅→∅),[4.8997]→[4.1219:1266](∅→∅),[4.1266]→[4.9031:9723](∅→∅),[4.9031]→[4.9031:9723](∅→∅)
  − #[derive(Debug)]

  − #[repr(C)]

  − struct Header {

  − n: u16,

  − data: u16,

  − crc: u32,

  − left_page: u64,

  − }

  −

  − impl Header {

  − fn init(&mut self) {

  − self.n = (1u16).to_le(); // dirty page

  − self.data = 4096_u16.to_le();

  − self.crc = 0;

  − self.left_page = 0;

  − }

  −

  − fn n(&self) -> u16 {

  − u16::from_le(self.n) >> 4

  − }

  −

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

  − let dirty = u16::from_le(self.n) & 1;

  − self.n = ((n << 4) | dirty).to_le()

  − }

  −

  − fn is_dirty(&self) -> bool {

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

  − }

  −

  − fn left_page(&self) -> u64 {

  − u64::from_le(self.left_page)

  − }

  −

  − fn decr(&mut self, s: usize) {

  − self.left_page = (self.left_page() - s as u64).to_le();

  − }

  −

  − fn is_leaf(&self) -> bool {

  − u64::from_le(self.left_page) <= 0xfff

  − }

  − }

  −

  − const HDR: usize = core::mem::size_of::<Header>();

  −
• replacement in sanakirja-core/src/btree/page.rs at line 42
  [4.1493]→[4.1493:1547](∅→∅)
  − hdr.n = (u16::from_le(hdr.n) & 0xfff).to_le()
  [4.1493]

  [4.10094]
  + hdr.clean();
• replacement in sanakirja-core/src/btree/page.rs at line 93
  [4.1844]→[3.896:976](∅→∅)
  − put::<_, _, _, Leaf>(txn, page, mutable, c.cur, k0, v0, k1v1, 0, 0)
  [4.1844]

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

  [4.11455]
  + put::put::<_, _, _, Internal>(txn, page, mutable, c.cur, k0, v0, k1v1, l, r)
• edit in sanakirja-core/src/btree/page.rs at line 111
  [3.1380]→[3.1380:1404](∅→∅)
  − assert!(l > 0);
• replacement in sanakirja-core/src/btree/page.rs at line 139
  [2.364]→[2.364:403](∅→∅)
  − hdr.left_page = l.to_le();
  [2.364]

  [4.2360]
  + hdr.set_left_page(l);
• edit in sanakirja-core/src/btree/page.rs at line 566
  [4.26296]→[4.26296:26299](∅→∅),[4.26299]→[4.12030:12083](∅→∅),[4.12083]→[3.5425:5480](∅→∅),[3.5480]→[4.26386:26388](∅→∅),[4.12150]→[4.26386:26388](∅→∅),[4.26386]→[4.26386:26388](∅→∅),[4.26388]→[4.12151:12210](∅→∅),[4.12210]→[3.5481:5531](∅→∅),[3.5531]→[4.26479:26496](∅→∅),[4.12272]→[4.26479:26496](∅→∅),[4.26479]→[4.26479:26496](∅→∅),[4.26496]→[3.5532:5805](∅→∅),[3.5805]→[4.12403:12507](∅→∅),[4.26754]→[4.12403:12507](∅→∅),[4.12507]→[3.5806:5958](∅→∅),[3.5958]→[4.12604:12698](∅→∅),[4.442]→[4.12604:12698](∅→∅),[4.12604]→[4.12604:12698](∅→∅),[4.12698]→[4.26949:27025](∅→∅),[4.26949]→[4.26949:27025](∅→∅),[4.27025]→[4.12699:12826](∅→∅),[4.12826]→[4.27156:27217](∅→∅),[4.27156]→[4.27156:27217](∅→∅),[4.27217]→[4.12827:12928](∅→∅),[4.12928]→[4.27321:27357](∅→∅),[4.27321]→[4.27321:27357](∅→∅),[4.27357]→[4.12929:12989](∅→∅),[4.12989]→[4.27424:27476](∅→∅),[4.27424]→[4.27424:27476](∅→∅),[4.27476]→[4.12990:13020](∅→∅),[4.13020]→[4.27514:27750](∅→∅),[4.27514]→[4.27514:27750](∅→∅),[4.27750]→[4.13021:13134](∅→∅),[4.13134]→[4.27785:27886](∅→∅),[4.27785]→[4.27785:27886](∅→∅),[4.27886]→[4.13135:13293](∅→∅),[4.13293]→[4.27886:28060](∅→∅),[4.27886]→[4.27886:28060](∅→∅),[4.28218]→[4.28218:28732](∅→∅),[4.28732]→[3.5959:6242](∅→∅),[3.6242]→[4.28861:29015](∅→∅),[4.28861]→[4.28861:29015](∅→∅),[4.29015]→[3.6243:6373](∅→∅),[3.6373]→[4.29015:29224](∅→∅),[4.13442]→[4.29015:29224](∅→∅),[4.29015]→[4.29015:29224](∅→∅),[4.29224]→[3.6374:6475](∅→∅),[3.6475]→[4.29355:29731](∅→∅),[4.29355]→[4.29355:29731](∅→∅),[4.29731]→[3.6476:6629](∅→∅),[3.6629]→[4.13607:13915](∅→∅),[4.573]→[4.13607:13915](∅→∅),[4.13607]→[4.13607:13915](∅→∅),[4.13915]→[4.574:575](∅→∅),[4.576]→[4.13915:13936](∅→∅),[4.13915]→[4.13915:13936](∅→∅),[4.13936]→[3.6630:6752](∅→∅),[3.6752]→[4.679:712](∅→∅),[4.679]→[4.679:712](∅→∅),[4.712]→[3.6753:6814](∅→∅),[3.6814]→[4.771:863](∅→∅),[4.771]→[4.771:863](∅→∅),[4.863]→[4.13936:14071](∅→∅),[4.13936]→[4.13936:14071](∅→∅),[4.14071]→[4.864:1105](∅→∅),[4.1105]→[4.14098:14131](∅→∅),[4.14098]→[4.14098:14131](∅→∅),[4.14131]→[4.1106:1151](∅→∅),[4.1151]→[4.14174:14327](∅→∅),[4.14174]→[4.14174:14327](∅→∅),[4.14327]→[4.1152:1173](∅→∅),[4.1173]→[3.6815:6946](∅→∅),[3.6946]→[4.1265:1279](∅→∅),[4.1265]→[4.1265:1279](∅→∅),[4.1279]→[4.14327:14536](∅→∅),[4.14327]→[4.14327:14536](∅→∅),[4.14536]→[4.1280:1326](∅→∅),[4.1326]→[4.14563:14639](∅→∅),[4.14563]→[4.14563:14639](∅→∅),[4.14639]→[3.6947:7039](∅→∅),[3.7039]→[4.14790:14805](∅→∅),[4.14790]→[4.14790:14805](∅→∅),[4.14805]→[3.7040:7284](∅→∅),[3.7284]→[4.14990:15141](∅→∅),[4.14990]→[4.14990:15141](∅→∅),[4.15141]→[4.1327:1344](∅→∅),[4.1344]→[4.15141:15224](∅→∅),[4.15141]→[4.15141:15224](∅→∅),[4.15224]→[4.29805:29866](∅→∅),[4.29805]→[4.29805:29866](∅→∅),[4.29866]→[4.15225:15264](∅→∅),[4.45]→[4.29905:30054](∅→∅),[4.15264]→[4.29905:30054](∅→∅),[4.29905]→[4.29905:30054](∅→∅),[4.30054]→[4.15265:15358](∅→∅),[4.15358]→[4.30176:30404](∅→∅),[4.30176]→[4.30176:30404](∅→∅),[4.30404]→[4.2447:2506](∅→∅),[4.2506]→[4.15359:15724](∅→∅),[4.15724]→[4.30688:30848](∅→∅),[4.30688]→[4.30688:30848](∅→∅),[4.30848]→[4.15725:15805](∅→∅),[4.15805]→[3.7285:7428](∅→∅),[3.7428]→[4.15873:16210](∅→∅),[4.15873]→[4.15873:16210](∅→∅),[4.16210]→[4.31184:31229](∅→∅),[4.31184]→[4.31184:31229](∅→∅),[4.31229]→[4.16211:16412](∅→∅),[4.16412]→[4.31397:31403](∅→∅),[4.31397]→[4.31397:31403](∅→∅),[4.31403]→[4.16413:16474](∅→∅),[4.16474]→[4.31466:31496](∅→∅),[4.31466]→[4.31466:31496](∅→∅),[4.31496]→[4.16475:16577](∅→∅),[4.16577]→[4.31600:31637](∅→∅),[4.31600]→[4.31600:31637](∅→∅),[4.31637]→[4.16578:16610](∅→∅),[4.16610]→[4.31672:31786](∅→∅),[4.31672]→[4.31672:31786](∅→∅),[4.31786]→[4.16611:16833](∅→∅),[4.16833]→[4.31948:31964](∅→∅),[4.31948]→[4.31948:31964](∅→∅),[4.31964]→[4.16834:16894](∅→∅),[4.16894]→[4.32031:32088](∅→∅),[4.32031]→[4.32031:32088](∅→∅),[4.32088]→[3.7429:7460](∅→∅),[3.7460]→[4.16928:17025](∅→∅),[4.16928]→[4.16928:17025](∅→∅),[4.17025]→[3.7461:7487](∅→∅),[3.7487]→[4.17053:17063](∅→∅),[4.17053]→[4.17053:17063](∅→∅),[4.17063]→[4.32224:32259](∅→∅),[4.32224]→[4.32224:32259](∅→∅),[4.32259]→[3.7488:7679](∅→∅),[3.7679]→[4.17128:17197](∅→∅),[4.32388]→[4.17128:17197](∅→∅),[4.17197]→[4.32388:32487](∅→∅),[4.32388]→[4.32388:32487](∅→∅),[4.32487]→[3.7680:7781](∅→∅),[3.7781]→[4.32618:32704](∅→∅),[4.32618]→[4.32618:32704](∅→∅),[4.32704]→[3.7782:7935](∅→∅),[3.7935]→[4.17362:17471](∅→∅),[4.1475]→[4.17362:17471](∅→∅),[4.17362]→[4.17362:17471](∅→∅),[4.17471]→[4.1476:1518](∅→∅),[4.1518]→[4.17471:17611](∅→∅),[4.17471]→[4.17471:17611](∅→∅),[4.17611]→[4.1519:1565](∅→∅),[4.1565]→[4.17640:17665](∅→∅),[4.17640]→[4.17640:17665](∅→∅),[4.17707]→[4.17707:18064](∅→∅),[4.18064]→[3.7936:8147](∅→∅),[3.8147]→[4.18216:18300](∅→∅),[4.18216]→[4.18216:18300](∅→∅),[4.18300]→[4.1566:1632](∅→∅),[4.1632]→[4.18300:18369](∅→∅),[4.18300]→[4.18300:18369](∅→∅),[4.18369]→[4.1633:1646](∅→∅),[4.1646]→[4.18370:18503](∅→∅),[4.18370]→[4.18370:18503](∅→∅),[4.18503]→[4.32778:33027](∅→∅),[4.32778]→[4.32778:33027](∅→∅),[4.33027]→[4.18504:18597](∅→∅),[4.18597]→[4.33149:33226](∅→∅),[4.33149]→[4.33149:33226](∅→∅),[4.33226]→[4.18598:18670](∅→∅),[4.18670]→[3.8148:8271](∅→∅),[3.8271]→[4.18746:19047](∅→∅),[4.18746]→[4.18746:19047](∅→∅),[4.19047]→[4.33548:33579](∅→∅),[4.33548]→[4.33548:33579](∅→∅),[4.33579]→[4.19048:19262](∅→∅),[4.19262]→[4.33760:33766](∅→∅),[4.33760]→[4.33760:33766](∅→∅),[4.33766]→[4.19263:19524](∅→∅),[4.19524]→[4.33990:34030](∅→∅),[4.33990]→[4.33990:34030](∅→∅),[4.34030]→[4.19525:19627](∅→∅),[4.19627]→[4.34134:34171](∅→∅),[4.34134]→[4.34134:34171](∅→∅),[4.34171]→[4.19628:19862](∅→∅),[4.19862]→[4.34356:34362](∅→∅),[4.34356]→[4.34356:34362](∅→∅),[4.34362]→[4.19863:19923](∅→∅),[4.19923]→[4.34429:34486](∅→∅),[4.34429]→[4.34429:34486](∅→∅),[4.34486]→[3.8272:8303](∅→∅),[3.8303]→[4.19957:20054](∅→∅),[4.19957]→[4.19957:20054](∅→∅),[4.20054]→[3.8304:8330](∅→∅),[3.8330]→[4.20082:20092](∅→∅),[4.20082]→[4.20082:20092](∅→∅),[4.20092]→[4.34622:34628](∅→∅),[4.34622]→[4.34622:34628](∅→∅)
  − }

  −

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

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

  − }

  −

  − fn header_mut(page: &mut crate::MutPage) -> &mut Header {

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

  − }

  −

  − trait Alloc {

  − 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;

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

  −

  − // n = number of items to remove

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

  − page: &mut MutPage,

  − n: usize,

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

  −

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

  − new: &mut MutPage,

  − n: &mut isize,

  − size: usize,

  − r: u64,

  − ) -> usize;

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

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

  − type Offset: Into<(u64, u16)> + Copy + core::fmt::Debug;

  − fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(

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

  − ) -> Offsets<'a, Self::Offset>;

  − fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

  − page: crate::Page,

  − off: (u64, u16),

  − ) -> (&'a K, &'a V, u64);

  − }

  −

  − #[derive(Debug, Clone)]

  − enum Offsets<'a, A> {

  − Slice(&'a [A]),

  − Range(core::ops::Range<usize>),

  − }

  −

  − impl<'a, A: Into<(u64, u16)> + Copy> Offsets<'a, A> {

  − fn split_at(&self, mid: usize) -> (Self, Self) {

  − match self {

  − Offsets::Slice(s) if mid < s.len() => {

  − debug!("split_at: {:?} {:?}", s.len(), mid);

  − let (a, b) = s.split_at(mid);

  − (Offsets::Slice(a), Offsets::Slice(b))

  − }

  − Offsets::Slice(s) => {

  − debug_assert_eq!(mid, s.len());

  − (Offsets::Slice(s), Offsets::Slice(&[][..]))

  − }

  − Offsets::Range(r) => (

  − Offsets::Range(r.start..r.start + mid),

  − Offsets::Range(r.start + mid..r.end),

  − ),

  − }

  − }

  − fn first<T, K: Representable<T>, V: Representable<T>>(&self) -> (u64, u16) {

  − match self {

  − Offsets::Slice(s) => s[0].into(),

  − Offsets::Range(r) => {

  − let size = fixed_size::<T, K, V>().unwrap();

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

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

  − (0, (hdr_size + r.start * size) as u16)

  − }

  − }

  − }

  − }

  −

  − struct Leaf {}

  − struct Internal {}

  −

  − impl Alloc for Leaf {

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

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

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

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

  − debug!(

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

  − header_size, size, hdr.data

  − );

  − header_size + (hdr.n() as usize) * f + size < u16::from_le(hdr.data) as usize

  − } else {

  − HDR + (hdr.n() as usize) * 2 + 2 + size < u16::from_le(hdr.data) as usize

  − }

  − }

  − fn can_compact<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {

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

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

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

  − header_size + ((hdr.left_page() & 0xfff) as usize) + size

  − < u16::from_le(hdr.data) as usize

  − } else {

  − HDR + ((hdr.left_page() & 0xfff) as usize) + 2 + size < 4096

  − }

  − }

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

  − page: &mut MutPage,

  − n: usize,

  − ) -> Option<(*const K, *const V)> {

  − debug!("truncate_left {:?} {:?}", page, n);

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

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

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

  − // debug!("{:?} {:?} {:?}", new, hdr.n(), *n);

  − let hdr_n = header_mut(page).n();

  −

  − unsafe {

  − let mut swap: core::mem::MaybeUninit<Tuple<K, V>> =

  − core::mem::MaybeUninit::uninit();

  − core::ptr::copy(

  − page.0.data.add(hdr_size + (n - 1) * f),

  − swap.as_mut_ptr() as *mut u8,

  − f,

  − );

  − core::ptr::copy(

  − page.0.data.add(hdr_size + n * f),

  − page.0.data.add(hdr_size),

  − (hdr_n as usize - n) * f,

  − );

  − core::ptr::copy(

  − swap.as_ptr() as *mut u8,

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

  − f,

  − );

  − }

  − debug!("{:?} - {:?}", hdr_n, n);

  − let hdr = header_mut(page);

  − hdr.set_n(hdr_n - n as u16);

  − hdr.left_page = (hdr.left_page() - (n * f) as u64).to_le();

  − unsafe {

  − Some(read::<T, K, V>(

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

  − ))

  − }

  − } else {

  − let hdr_n = header_mut(page).n();

  − unsafe {

  − core::ptr::copy(

  − page.0.data.add(HDR + n * 2),

  − page.0.data.add(HDR),

  − (hdr_n as usize - n) * 2,

  − );

  − }

  − let deleted_offsets = unsafe {

  − core::slice::from_raw_parts(page.0.data.add(HDR) as *const u16, n as usize)

  − };

  − let deleted_size: u64 = deleted_offsets

  − .iter()

  − .map(|&off| {

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

  − })

  − .sum();

  − let hdr = header_mut(page);

  − hdr.set_n(hdr_n - n as u16);

  − hdr.left_page = (hdr.left_page() - deleted_size).to_le();

  − None

  − }

  − }

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

  − let mut data = u16::from_le(hdr.data) - size as u16;

  − data &= !((align - 1) as u16);

  − hdr.data = data.to_le();

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

  − hdr.left_page = (hdr.left_page() + size as u64).to_le();

  − data

  − }

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

  − new: &mut MutPage,

  − n: &mut isize,

  − size: usize,

  − _: u64,

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

  − // debug!("{:?} {:?} {:?}", new, hdr.n(), *n);

  − let hdr_n = header_mut(new).n();

  − unsafe {

  − core::ptr::copy(

  − new.0.data.add(hdr_size + (*n as usize) * f),

  − new.0.data.add(hdr_size + (*n as usize) * f + f),

  − (hdr_n as usize - (*n as usize)) * f,

  − );

  − }

  − let hdr = header_mut(new);

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

  − hdr.left_page = (hdr.left_page() + f as u64).to_le();

  − hdr_size + (*n as usize) * f

  − } else {

  − let (hdr_n, off_new) = {

  − let hdr = header_mut(new);

  − (

  − hdr.n(),

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

  − )

  − };

  − unsafe {

  − core::ptr::copy(

  − new.0.data.add(HDR + (*n as usize) * 2),

  − new.0.data.add(HDR + (*n as usize) * 2 + 2),

  − (hdr_n as usize - (*n as usize)) * 2,

  − );

  − }

  − Self::set_offset(new, *n, 0, off_new);

  − off_new as usize

  − }

  − }

  − fn set_offset(new: &mut MutPage, n: isize, _: u64, off: u16) {

  − unsafe {

  − let ptr = new.0.data.offset(HDR as isize + n * 2) as *mut u16;

  − *ptr = off.to_le();

  − }

  − }

  − fn set_right_child(_: &mut MutPage, _: isize, _: u64) {}

  − type Offset = LeafOffset;

  −

  − fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(

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

  − ) -> Offsets<'a, Self::Offset> {

  − let hdr = header(page);

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

  − Offsets::Range(0..(hdr.n() as usize))

  − } else {

  − unsafe {

  − Offsets::Slice(core::slice::from_raw_parts(

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

  − hdr.n() as usize,

  − ))

  − }

  − }

  − }

  − fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

  − page: crate::Page,

  − (_, off): (u64, u16),

  − ) -> (&'a K, &'a V, u64) {

  − unsafe {

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

  − (&*k, &*v, 0)

  − }

  − }

  − }

  −

  − impl Alloc for Internal {

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

  − debug!("Internal::can_alloc: {:?} {:?}", hdr.n(), hdr.data);

  − (HDR as usize) + (hdr.n() as usize) * 8 + 8 + size < u16::from_le(hdr.data) as usize

  − }

  − fn can_compact<T, K: Representable<T>, V: Representable<T>>(hdr: &Header, size: usize) -> bool {

  − (HDR as usize) + ((hdr.left_page() & 0xfff) as usize) + 8 + size < 4096

  − }

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

  − page: &mut MutPage,

  − n: usize,

  − ) -> Option<(*const K, *const V)> {

  − // The following line copies the left child of the last entry

  − // (hence the `- 8` and `- 1`)

  − let hdr_n = header_mut(page).n();

  − unsafe {

  − core::ptr::copy(

  − page.0.data.add(HDR + (n - 1) * 8),

  − page.0.data.add(HDR - 8),

  − (hdr_n as usize - n + 1) * 8,

  − );

  − }

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

  − ((8 + f) * (hdr_n as usize - n)) as u64

  − } else {

  − let offsets = unsafe {

  − core::slice::from_raw_parts(

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

  − hdr_n as usize - n as usize,

  − )

  − };

  − offsets

  − .iter()

  − .map(|&off| {

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

  − })

  − .sum()

  − };

  − let hdr = header_mut(page);

  − hdr.set_n(hdr_n - n as u16);

  − debug!("truncate_left {:?} {:?}", hdr.left_page(), size);

  − hdr.left_page = ((hdr.left_page() & !0xfff) | size).to_le();

  − None

  − }

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

  − debug!("data = {:?}, size = {:?}", hdr.data, size);

  − let mut data = u16::from_le(hdr.data) - size as u16;

  − data -= data % (align as u16);

  − hdr.data = data.to_le();

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

  − hdr.left_page = (hdr.left_page() + size as u64).to_le();

  − data

  − }

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

  − new: &mut MutPage,

  − n: &mut isize,

  − size: usize,

  − r: u64,

  − ) -> usize {

  − let (hdr_n, off_new) = {

  − let hdr = header_mut(new);

  − (

  − hdr.n(),

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

  − )

  − };

  − unsafe {

  − core::ptr::copy(

  − new.0.data.add(HDR + (*n as usize) * 8),

  − new.0.data.add(HDR + (*n as usize) * 8 + 8),

  − (hdr_n as usize - (*n as usize)) * 8,

  − );

  − }

  − Self::set_offset(new, *n, r, off_new);

  − off_new as usize

  − }

  − fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16) {

  − unsafe {

  − let ptr = new.0.data.offset(HDR as isize + n * 8) as *mut u64;

  − *ptr = (r | off as u64).to_le();

  − }

  − }

  − fn set_right_child(page: &mut MutPage, n: isize, r: u64) {

  − unsafe {

  − let ptr = page.0.data.offset(HDR as isize + n * 8) as *mut u64;

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

  − *ptr = (r | off as u64).to_le();

  − }

  − }

  − type Offset = InternalOffset;

  −

  − fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(

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

  − ) -> Offsets<'a, Self::Offset> {

  − let hdr = header(page);

  − unsafe {

  − Offsets::Slice(core::slice::from_raw_parts(

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

  − hdr.n() as usize,

  − ))

  − }

  − }

  − fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

  − page: crate::Page,

  − (r, off): (u64, u16),

  − ) -> (&'a K, &'a V, u64) {

  − unsafe {

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

  − (&*k, &*v, r)

  − }

  − }
• edit in sanakirja-core/src/btree/page.rs at line 635
  [4.36508]→[3.8888:9057](∅→∅),[3.9057]→[4.36599:36616](∅→∅),[4.21434]→[4.36599:36616](∅→∅),[4.948]→[4.36599:36616](∅→∅),[4.2100]→[4.36599:36616](∅→∅),[4.36599]→[4.36599:36616](∅→∅),[4.36616]→[4.21435:21480](∅→∅),[4.21480]→[4.36657:36698](∅→∅),[4.36657]→[4.36657:36698](∅→∅),[4.36698]→[4.949:1058](∅→∅),[4.1058]→[4.21481:21692](∅→∅),[4.36698]→[4.21481:21692](∅→∅)
  − fn rebalance_left<

  − 'a,

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

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

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

  − L: Alloc,

  − >(

  − txn: &mut T,

  − m: &mut Concat<'a, T, K, V, Page<K, V>>,

  − ) -> Result<Op<'a, T, K, V>, T::Error> {

  − assert!(m.mod_is_left);

  − // First element of the right page. We'll rotate it to the left

  − // page.

  − let rc = <Page<K, V>>::first_cursor(m.other.as_page());

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

  − let (k, v, r) = unsafe { <Page<K, V>>::unchecked_current(m.other.as_page(), &rc) };
• edit in sanakirja-core/src/btree/page.rs at line 636
  [4.36914]→[4.36914:36942](∅→∅),[4.36942]→[3.9058:9160](∅→∅),[3.9160]→[4.1137:1414](∅→∅),[4.1137]→[4.1137:1414](∅→∅),[4.1414]→[3.9161:9220](∅→∅),[3.9220]→[4.1448:1584](∅→∅),[4.1448]→[4.1448:1584](∅→∅),[4.1584]→[4.37208:37221](∅→∅),[4.37208]→[4.37208:37221](∅→∅),[4.37221]→[4.1585:1803](∅→∅),[4.1805]→[4.22235:22236](∅→∅),[4.22235]→[4.22235:22236](∅→∅),[4.22236]→[4.1806:2679](∅→∅),[4.2679]→[3.9221:9244](∅→∅),[3.9244]→[4.2701:2879](∅→∅),[4.2701]→[4.2701:2879](∅→∅),[4.2879]→[3.9245:9272](∅→∅),[3.9272]→[4.2903:2922](∅→∅),[4.2903]→[4.2903:2922](∅→∅),[4.2922]→[3.9273:9423](∅→∅),[3.9423]→[4.3148:3301](∅→∅),[4.3148]→[4.3148:3301](∅→∅),[4.3301]→[3.9424:9603](∅→∅),[3.9603]→[4.37695:37702](∅→∅),[4.3442]→[4.37695:37702](∅→∅),[4.37695]→[4.37695:37702](∅→∅),[4.37764]→[4.37764:37810](∅→∅),[4.37810]→[4.22319:22366](∅→∅),[4.22366]→[4.37848:38029](∅→∅),[4.37848]→[4.37848:38029](∅→∅),[4.38029]→[4.22367:22461](∅→∅),[4.22461]→[4.38051:38075](∅→∅),[4.38051]→[4.38051:38075](∅→∅),[4.38075]→[4.3443:3444](∅→∅),[4.3444]→[3.9604:9774](∅→∅),[3.9774]→[4.3594:3923](∅→∅),[4.3594]→[4.3594:3923](∅→∅),[4.3923]→[4.38075:38076](∅→∅),[4.38075]→[4.38075:38076](∅→∅),[4.38076]→[4.3924:4103](∅→∅),[4.4104]→[4.4104:4133](∅→∅),[4.4133]→[3.9775:9877](∅→∅),[3.9877]→[4.4211:4489](∅→∅),[4.4211]→[4.4211:4489](∅→∅),[4.4489]→[3.9878:9937](∅→∅),[3.9937]→[4.4523:4758](∅→∅),[4.4523]→[4.4523:4758](∅→∅),[4.4758]→[3.9938:10070](∅→∅),[3.10070]→[4.4943:5466](∅→∅),[4.4943]→[4.4943:5466](∅→∅),[4.5467]→[4.5467:5468](∅→∅),[4.5468]→[4.38076:38647](∅→∅),[4.38076]→[4.38076:38647](∅→∅)
  − let mut freed = [0, 0];

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

  − 1

  − } else {

  − 0

  − };

  − freed[0] = m.modified.page.offset | b;

  −

  − let mut new_left = if let Some((k, v)) = m.modified.ins {

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

  − txn,

  − m.modified.page,

  − m.modified.mutable,

  − &m.modified.c1,

  − k,

  − v,

  − m.modified.ins2,

  − m.modified.l,

  − m.modified.r,

  − )? {

  − page

  − } else {

  − unreachable!()

  − }

  − } else {

  − <Page<K, V>>::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?

  − };

  − let mut n = header(new_left.0.as_page()).n() as isize;

  − alloc::<T, K, V, L>(&mut new_left, m.mid.0, m.mid.1, 0, rl, &mut n);

  −

  − let right_hdr = header(m.other.as_page());

  − let (new_right, k, v) = match fixed_size::<T, K, V>() {

  − Some(f) if r == 0 && right_hdr.is_dirty() => {

  − // Rewrite the deleted element at the end of the page, so that

  − // the pointer is still valid.

  − let data = m.other.data;

  − let mut other = MutPage(m.other);

  − let right_hdr = header_mut(&mut other);

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

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

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

  − right_hdr.decr(f);

  − right_hdr.set_n((n - 1) as u16);

  − let mut t: MaybeUninit<Tuple<K, V>> = MaybeUninit::uninit();

  − unsafe {

  − core::ptr::copy_nonoverlapping(

  − data.add(hdr_size) as *mut Tuple<K, V>,

  − t.as_mut_ptr(),

  − 1,

  − );

  − core::ptr::copy(

  − data.add(hdr_size + f) as *const Tuple<K, V>,

  − data.add(hdr_size) as *mut Tuple<K, V>,

  − n - 1,

  − );

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

  − core::ptr::copy_nonoverlapping(t.as_ptr(), last, 1);

  − debug!("tuple = {:?}", t.assume_init());

  − (other, &(&*last).k, &(&*last).v)

  − }

  − }

  − _ => unsafe {

  − (

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

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

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

  − )

  − },

  − };

  − 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

  − }

  − Ok(Op::Rebalanced {

  − l: new_left.0.offset,

  − r: new_right.0.offset,

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

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

  − freed,

  − })

  − }

  −

  − fn rebalance_right<

  − 'a,

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

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

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

  − L: Alloc,

  − >(

  − txn: &mut T,

  − m: &mut Concat<'a, T, K, V, Page<K, V>>,

  − ) -> Result<Op<'a, T, K, V>, T::Error> {

  − assert!(!m.mod_is_left);

  − // Take the last element of the left page.

  − let lc = <Page<K, V>>::last_cursor(m.other.as_page());

  − let (k0, v0, r0) = unsafe { <Page<K, V>>::unchecked_current(m.other.as_page(), &lc) };

  −

  − // First element of the right page.

  − let rc = <Page<K, V>>::first_cursor(m.modified.page.as_page());

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

  −

  − let mut freed = [0, 0];

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

  − 1

  − } else {

  − 0

  − };

  − freed[0] = m.modified.page.offset | b;

  −

  − let mut new_right = if let Some((k, v)) = m.modified.ins {

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

  − txn,

  − m.modified.page,

  − m.modified.mutable,

  − &m.modified.c1,

  − k,

  − v,

  − m.modified.ins2,

  − m.modified.l,

  − m.modified.r,

  − )? {

  − page

  − } else {

  − unreachable!()

  − }

  − } else {

  − <Page<K, V>>::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?

  − };

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

  − {

  − new_right = page

  − } else {

  − unreachable!()

  − };

  −

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

  − if new_left.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

  − }

  − Ok(Op::Rebalanced {

  − l: new_left.0.offset,

  − r: new_right.0.offset,

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

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

  − freed,

  − })

  − }

  −

  − #[derive(Debug, Clone, Copy)]

  − #[repr(C)]

  − struct LeafOffset(u16);

  −

  − impl Into<(u64, u16)> for LeafOffset {

  − fn into(self) -> (u64, u16) {

  − (0, self.0)

  − }

  − }

  −

  − impl Into<usize> for LeafOffset {

  − fn into(self) -> usize {

  − self.0 as usize

  − }

  − }

  −

  − #[derive(Debug, Clone, Copy)]

  − #[repr(C)]

  − struct InternalOffset(u64);

  −

  − impl Into<(u64, u16)> for InternalOffset {

  − fn into(self) -> (u64, u16) {

  − (self.0 & !0xfff, (self.0 & 0xfff) as u16)

  − }

  − }

  −

  − impl Into<usize> for InternalOffset {

  − fn into(self) -> usize {

  − self.0 as usize

  − }

  − }

  −
• replacement in sanakirja-core/src/btree/page.rs at line 675
  [4.23543]→[4.23543:23620](∅→∅)
  − hdr.left_page = (hdr.left_page() + (size * len) as u64).to_le();
  [4.23543]

  [4.39972]
  + hdr.incr(size * len);
• edit in sanakirja-core/src/btree/page.rs at line 702
  [4.40624]→[4.40624:40625](∅→∅),[4.40625]→[3.10151:10309](∅→∅),[3.10309]→[4.40710:40727](∅→∅),[4.24157]→[4.40710:40727](∅→∅),[4.2236]→[4.40710:40727](∅→∅),[4.40710]→[4.40710:40727](∅→∅),[4.40727]→[4.24158:24177](∅→∅),[4.24177]→[4.40750:40813](∅→∅),[4.40750]→[4.40750:40813](∅→∅),[4.40813]→[3.10310:10344](∅→∅),[3.10344]→[4.40813:40876](∅→∅),[4.40813]→[4.40813:40876](∅→∅),[4.40876]→[3.10345:10493](∅→∅),[3.10493]→[4.24178:24484](∅→∅),[4.40911]→[4.24178:24484](∅→∅),[4.24484]→[4.41103:41135](∅→∅),[4.41103]→[4.41103:41135](∅→∅),[4.41135]→[3.10494:10758](∅→∅),[3.10758]→[4.41197:41293](∅→∅),[4.24547]→[4.41197:41293](∅→∅),[4.41197]→[4.41197:41293](∅→∅),[4.41293]→[4.24548:24820](∅→∅),[4.24820]→[4.41438:41485](∅→∅),[4.41438]→[4.41438:41485](∅→∅),[4.41526]→[4.41526:41549](∅→∅),[4.41549]→[4.24821:24888](∅→∅),[4.24888]→[3.10759:11020](∅→∅),[3.11020]→[4.24949:25064](∅→∅),[4.24949]→[4.24949:25064](∅→∅),[4.25064]→[4.41777:41894](∅→∅),[4.41777]→[4.41777:41894](∅→∅),[4.41894]→[4.25065:25090](∅→∅),[4.25090]→[4.41894:42042](∅→∅),[4.41894]→[4.41894:42042](∅→∅),[4.42042]→[3.11021:11113](∅→∅),[3.11113]→[4.42127:42146](∅→∅),[4.25186]→[4.42127:42146](∅→∅),[4.42127]→[4.42127:42146](∅→∅),[4.42146]→[3.11114:11274](∅→∅),[3.11274]→[4.42233:42250](∅→∅),[4.25267]→[4.42233:42250](∅→∅),[4.2374]→[4.42233:42250](∅→∅),[4.42233]→[4.42233:42250](∅→∅),[4.42250]→[4.25268:25287](∅→∅),[4.25287]→[4.42273:42416](∅→∅),[4.42273]→[4.42273:42416](∅→∅),[4.42416]→[4.25288:25344](∅→∅),[4.25344]→[4.42552:42614](∅→∅),[4.42552]→[4.42552:42614](∅→∅),[4.42614]→[4.2375:2400](∅→∅),[4.2400]→[4.42685:42704](∅→∅),[4.42685]→[4.42685:42704](∅→∅),[4.42704]→[4.2401:2413](∅→∅),[4.2413]→[4.25345:25401](∅→∅),[4.42704]→[4.25345:25401](∅→∅),[4.98]→[4.42731:42774](∅→∅),[4.25401]→[4.42731:42774](∅→∅),[4.42731]→[4.42731:42774](∅→∅),[4.42774]→[4.2414:2551](∅→∅),[4.2551]→[4.42888:43024](∅→∅),[4.42888]→[4.42888:43024](∅→∅),[4.43024]→[4.25402:25473](∅→∅),[4.25473]→[4.2552:2687](∅→∅),[4.2687]→[4.43112:43142](∅→∅),[4.43112]→[4.43112:43142](∅→∅),[4.43142]→[4.25474:26872](∅→∅),[4.26872]→[4.2688:2941](∅→∅),[4.2941]→[4.26912:27193](∅→∅),[4.26912]→[4.26912:27193](∅→∅),[4.27193]→[4.43517:43564](∅→∅),[4.43517]→[4.43517:43564](∅→∅),[4.43564]→[4.27194:27318](∅→∅),[4.27318]→[4.2942:3101](∅→∅),[4.3101]→[4.27404:27473](∅→∅),[4.27404]→[4.27404:27473](∅→∅),[4.27473]→[4.3102:3164](∅→∅),[4.3164]→[4.27535:27656](∅→∅),[4.27535]→[4.27535:27656](∅→∅),[4.27657]→[4.27657:27755](∅→∅),[4.27755]→[4.3165:3390](∅→∅),[4.3390]→[4.27820:27843](∅→∅),[4.27820]→[4.27820:27843](∅→∅),[4.27843]→[4.44378:44395](∅→∅),[4.44378]→[4.44378:44395](∅→∅),[4.44395]→[4.27844:27952](∅→∅),[4.27952]→[4.44441:44468](∅→∅),[4.44441]→[4.44441:44468](∅→∅),[4.44468]→[4.27953:28085](∅→∅),[4.28085]→[4.44530:44588](∅→∅),[4.44530]→[4.44530:44588](∅→∅),[4.44588]→[4.28086:28225](∅→∅),[4.28225]→[4.44588:44594](∅→∅),[4.44588]→[4.44588:44594](∅→∅),[4.45430]→[4.45430:45433](∅→∅),[4.45433]→[3.11275:11586](∅→∅),[3.11586]→[4.45663:45702](∅→∅),[4.45663]→[4.45663:45702](∅→∅),[4.45702]→[3.11587:13873](∅→∅),[3.13873]→[4.45723:45725](∅→∅),[4.45723]→[4.45723:45725](∅→∅)
  −

  − fn put<

  − 'a,

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

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

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

  − L: Alloc,

  − >(

  − txn: &mut T,

  − page: CowPage,

  − mutable: bool,

  − u: usize,

  − k0: &'a K,

  − v0: &'a V,

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

  − l: u64,

  − r: u64,

  − ) -> Result<Put<'a, K, V>, T::Error> {

  − let size = alloc_size(k0, v0)

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

  − alloc_size(k1, v1)

  − } else {

  − 0

  − };

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

  − let is_dirty = hdr.is_dirty();

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

  − if mutable && is_dirty && L::can_alloc::<T, K, V>(header(page.as_page()), size) {

  − debug!("can alloc");

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

  − let mut n = u as isize;

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

  − }

  − Ok(Put::Ok(Ok { page, freed: 0 }))

  − } else if L::can_compact::<T, K, V>(hdr, size) {

  − let mut new = txn.alloc_page()?;

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

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

  − L::set_right_child(&mut new, -1, hdr.left_page & !0xfff);

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

  − let (s0, s1) = s.split_at(u as usize);

  − let mut n = 0;

  − clone::<T, K, V, L>(page.as_page(), &mut new, s0, &mut n);

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

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

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

  − } else {

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

  − }

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

  −

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

  − return Ok(Put::Ok(Ok {

  − page: new,

  − freed: page.offset | b0,

  − }));

  − } else {

  − debug!("split");

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

  − return split::<_, _, _, L>(txn, page, mutable, s, u, k0, v0, l, r);

  − } else {

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

  − }

  − }

  − }

  −

  − fn split<

  − 'a,

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

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

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

  − L: Alloc,

  − >(

  − txn: &mut T,

  − page: CowPage,

  − mutable: bool,

  − size: usize,

  − u: usize,

  − k0: &'a K,

  − v0: &'a V,

  − l: u64,

  − r: u64,

  − ) -> Result<Put<'a, K, V>, T::Error> {

  − let mut left;

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

  −

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

  −

  − let mut n = hdr.n();

  − let k = n / 2;

  − n += 1;

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

  − let (s0, s1) = s.split_at(k as usize);

  − debug!("u = {:?}, k = {:?} {:?} {:?}", u, k, s0, s1);

  − let (mut split_key, mut split_value, mid_child, s1) = if u == k as usize {

  − // The inserted element is exactly in the middle.

  − (k0, v0, r, s1)

  − } else {

  − let (s1a, s1b) = s1.split_at(1);

  − let (k, v, r) = L::kv(page.as_page(), s1a.first::<T, K, V>());

  − debug!("k = {:?}, v = {:?} r = {:?}", k, v, r);

  − debug!("k = {:?}", k as *const K as *const u8);

  − (k, v, r, s1b)

  − };

  − let mut freed = 0;

  − if u >= k as usize {

  − if mutable && hdr.is_dirty() {

  − debug!("mutable dirty {:?} >= {:?}", u, k);

  − // (k0, v0) is to be inserted on the right-hand side of

  − // the split, hence we don't have to clone the left-hand

  − // side, we can just truncate it.

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

  − let hdr = header_mut(&mut left);

  − hdr.set_n(k);

  − hdr.decr((n - 1 - k) as usize * size);

  − } else {

  − left = txn.alloc_page()?;

  − debug!("immutable {:?} >= {:?}", u, k);

  − let mut n = 0;

  − clone::<T, K, V, L>(page.as_page(), &mut left, s0, &mut n);

  − freed = page.offset | page_is_dirty

  − }

  − // If we are here, u >= k, i.e. the insertion is in the right-hand

  − // side of the split.

  − let mut n = 0;

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

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

  − if u > k as usize {

  − let kk = u as usize - k as usize - 1;

  − let (s1a, s1b) = s1.split_at(kk);

  − L::set_right_child(&mut right, -1, mid_child);

  − clone::<T, K, V, L>(page.as_page(), &mut right, s1a, &mut n);

  − alloc::<T, K, V, L>(&mut right, k0, v0, l, r, &mut n);

  − clone::<T, K, V, L>(page.as_page(), &mut right, s1b, &mut n);

  − } else {

  − // Insertion in the middle:

  − // - `l` becomes the right child of the last element on `left`.

  − L::set_right_child(&mut left, k as isize - 1, l);

  − // - `r` (i.e. `mid_child`) becomes the left child of `right`.

  − L::set_right_child(&mut right, -1, mid_child);

  − clone::<T, K, V, L>(page.as_page(), &mut right, s1, &mut n);

  − }

  − Ok(Put::Split {

  − split_key,

  − split_value,

  − left,

  − right,

  − freed,

  − })

  − } else {

  − left = txn.alloc_page()?;

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

  − debug!("{:?} < {:?}", u, k);

  − let mut n = 0;

  − let ll = header(page.as_page()).left_page() & !0xfff;

  − L::set_right_child(&mut left, -1, ll);

  − let (s0a, s0b) = s0.split_at(u as usize);

  − clone::<T, K, V, L>(page.as_page(), &mut left, s0a, &mut n);

  − alloc::<T, K, V, L>(&mut left, k0, v0, l, r, &mut n);

  − clone::<T, K, V, L>(page.as_page(), &mut left, s0b, &mut n);

  −

  − let mut right: MutPage;

  − let freed;

  − if mutable && hdr.is_dirty() {

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

  − if let Some((k, v)) = L::truncate_left::<T, K, V>(&mut right, k as usize + 1) {

  − unsafe {

  − split_key = &*k;

  − split_value = &*v;

  − }

  − }

  − freed = 0;

  − } else {

  − right = txn.alloc_page()?;

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

  − let mut n = 0;

  − L::set_right_child(&mut right, -1, mid_child);

  − clone::<T, K, V, L>(page.as_page(), &mut right, s1, &mut n);

  − freed = page.offset | page_is_dirty

  − }

  − Ok(Put::Split {

  − split_key,

  − split_value,

  − left,

  − right,

  − freed,

  − })

  − }

  − }

  −

  − 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,

  − ) -> Result<Put<'a, K, V>, T::Error> {

  − 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,

  − })

  − }
• file addition: page (dxwrx-rx-r)
  [4.3438]
• file addition: rebalance.rs (-xw-x--x--)
  [0.371]
  + use super::*;

  + use core::mem::MaybeUninit;

  +

  + pub(crate) fn rebalance_left<

  + 'a,

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

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

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

  + L: Alloc,

  + >(

  + txn: &mut T,

  + m: &mut Concat<'a, T, K, V, Page<K, V>>,

  + ) -> Result<Op<'a, T, K, V>, T::Error> {

  + assert!(m.mod_is_left);

  + // First element of the right page. We'll rotate it to the left

  + // page.

  + let rc = <Page<K, V>>::first_cursor(m.other.as_page());

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

  + let (k, v, r) = unsafe { <Page<K, V>>::unchecked_current(m.other.as_page(), &rc) };

  +

  + let mut freed = [0, 0];

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

  + 1

  + } else {

  + 0

  + };

  + freed[0] = m.modified.page.offset | b;

  +

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

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

  + txn,

  + m.modified.page,

  + m.modified.mutable,

  + &m.modified.c1,

  + k,

  + v,

  + m.modified.ins2,

  + m.modified.l,

  + m.modified.r,

  + )? {

  + page

  + } else {

  + unreachable!()

  + }

  + } else {

  + <Page<K, V>>::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?

  + };

  + let mut n = header(new_left.0.as_page()).n() as isize;

  + alloc::<T, K, V, L>(&mut new_left, m.mid.0, m.mid.1, 0, rl, &mut n);

  +

  + let right_hdr = header(m.other.as_page());

  + let (new_right, k, v) = match fixed_size::<T, K, V>() {

  + Some(f) if r == 0 && right_hdr.is_dirty() => {

  + // Rewrite the deleted element at the end of the page, so that

  + // the pointer is still valid.

  + let data = m.other.data;

  + let mut other = MutPage(m.other);

  + let right_hdr = header_mut(&mut other);

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

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

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

  + right_hdr.decr(f);

  + right_hdr.set_n((n - 1) as u16);

  + let mut t: MaybeUninit<Tuple<K, V>> = MaybeUninit::uninit();

  + unsafe {

  + core::ptr::copy_nonoverlapping(

  + data.add(hdr_size) as *mut Tuple<K, V>,

  + t.as_mut_ptr(),

  + 1,

  + );

  + core::ptr::copy(

  + data.add(hdr_size + f) as *const Tuple<K, V>,

  + data.add(hdr_size) as *mut Tuple<K, V>,

  + n - 1,

  + );

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

  + core::ptr::copy_nonoverlapping(t.as_ptr(), last, 1);

  + debug!("tuple = {:?}", t.assume_init());

  + (other, &(&*last).k, &(&*last).v)

  + }

  + }

  + _ => unsafe {

  + (

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

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

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

  + )

  + },

  + };

  + 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

  + }

  + Ok(Op::Rebalanced {

  + l: new_left.0.offset,

  + r: new_right.0.offset,

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

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

  + freed,

  + })

  + }

  +

  + pub(crate) fn rebalance_right<

  + 'a,

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

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

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

  + L: Alloc,

  + >(

  + txn: &mut T,

  + m: &mut Concat<'a, T, K, V, Page<K, V>>,

  + ) -> Result<Op<'a, T, K, V>, T::Error> {

  + assert!(!m.mod_is_left);

  + // Take the last element of the left page.

  + let lc = <Page<K, V>>::last_cursor(m.other.as_page());

  + let (k0, v0, r0) = unsafe { <Page<K, V>>::unchecked_current(m.other.as_page(), &lc) };

  +

  + // First element of the right page.

  + let rc = <Page<K, V>>::first_cursor(m.modified.page.as_page());

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

  +

  + let mut freed = [0, 0];

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

  + 1

  + } else {

  + 0

  + };

  + freed[0] = m.modified.page.offset | b;

  +

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

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

  + txn,

  + m.modified.page,

  + m.modified.mutable,

  + &m.modified.c1,

  + k,

  + v,

  + m.modified.ins2,

  + m.modified.l,

  + m.modified.r,

  + )? {

  + page

  + } else {

  + unreachable!()

  + }

  + } else {

  + <Page<K, V>>::del(txn, m.modified.page, &m.modified.c1, m.modified.l)?

  + };

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

  + {

  + new_right = page

  + } else {

  + unreachable!()

  + };

  +

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

  + if new_left.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

  + }

  + Ok(Op::Rebalanced {

  + l: new_left.0.offset,

  + r: new_right.0.offset,

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

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

  + freed,

  + })

  + }
• file addition: put.rs (-xw-x--x--)
  [0.371]
  + use super::*;

  +

  + pub(crate) fn put<

  + 'a,

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

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

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

  + L: Alloc,

  + >(

  + txn: &mut T,

  + page: CowPage,

  + mutable: bool,

  + u: usize,

  + k0: &'a K,

  + v0: &'a V,

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

  + l: u64,

  + r: u64,

  + ) -> Result<Put<'a, K, V>, T::Error> {

  + let size = alloc_size(k0, v0)

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

  + alloc_size(k1, v1)

  + } else {

  + 0

  + };

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

  + let is_dirty = hdr.is_dirty();

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

  + if mutable && is_dirty && L::can_alloc::<T, K, V>(header(page.as_page()), size) {

  + debug!("can alloc");

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

  + let mut n = u as isize;

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

  + }

  + Ok(Put::Ok(Ok { page, freed: 0 }))

  + } else if L::can_compact::<T, K, V>(hdr, size) {

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

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

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

  + L::set_right_child(&mut new, -1, hdr.left_page() & !0xfff);

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

  + let (s0, s1) = s.split_at(u as usize);

  + let mut n = 0;

  + clone::<T, K, V, L>(page.as_page(), &mut new, s0, &mut n);

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

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

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

  + } else {

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

  + }

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

  +

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

  + return Ok(Put::Ok(Ok {

  + page: new,

  + freed: page.offset | b0,

  + }));

  + } else {

  + debug!("split");

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

  + assert!(k1v1.is_none());

  + return split::<_, _, _, L>(txn, page, mutable, s, u, k0, v0, l, r);

  + } else {

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

  + }

  + }

  + }

  +

  + fn split<

  + 'a,

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

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

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

  + L: Alloc,

  + >(

  + txn: &mut T,

  + page: CowPage,

  + mutable: bool,

  + size: usize,

  + u: usize,

  + k0: &'a K,

  + v0: &'a V,

  + l: u64,

  + r: u64,

  + ) -> Result<Put<'a, K, V>, T::Error> {

  + let mut left;

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

  +

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

  +

  + let mut n = hdr.n();

  + let k = n / 2;

  + n += 1;

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

  + let (s0, s1) = s.split_at(k as usize);

  + debug!("u = {:?}, k = {:?} {:?} {:?}", u, k, s0, s1);

  + let (mut split_key, mut split_value, mid_child, s1) = if u == k as usize {

  + // The inserted element is exactly in the middle.

  + (k0, v0, r, s1)

  + } else {

  + let (s1a, s1b) = s1.split_at(1);

  + let (k, v, r) = L::kv(page.as_page(), s1a.first::<T, K, V>());

  + debug!("k = {:?}, v = {:?} r = {:?}", k, v, r);

  + debug!("k = {:?}", k as *const K as *const u8);

  + (k, v, r, s1b)

  + };

  + let mut freed = 0;

  + if u >= k as usize {

  + if mutable && hdr.is_dirty() {

  + debug!("mutable dirty {:?} >= {:?}", u, k);

  + // (k0, v0) is to be inserted on the right-hand side of

  + // the split, hence we don't have to clone the left-hand

  + // side, we can just truncate it.

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

  + let hdr = header_mut(&mut left);

  + hdr.set_n(k);

  + hdr.decr((n - 1 - k) as usize * size);

  + } else {

  + left = txn.alloc_page()?;

  + debug!("immutable {:?} >= {:?}", u, k);

  + let mut n = 0;

  + clone::<T, K, V, L>(page.as_page(), &mut left, s0, &mut n);

  + freed = page.offset | page_is_dirty

  + }

  + // If we are here, u >= k, i.e. the insertion is in the right-hand

  + // side of the split.

  + let mut n = 0;

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

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

  + if u > k as usize {

  + let kk = u as usize - k as usize - 1;

  + let (s1a, s1b) = s1.split_at(kk);

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

  + clone::<T, K, V, L>(page.as_page(), &mut right, s1a, &mut n);

  + alloc::<T, K, V, L>(&mut right, k0, v0, l, r, &mut n);

  + clone::<T, K, V, L>(page.as_page(), &mut right, s1b, &mut n);

  + } else {

  + // Insertion in the middle:

  + // - `l` becomes the right child of the last element on `left`.

  + L::set_right_child(&mut left, k as isize - 1, l);

  + // - `r` (i.e. `mid_child`) becomes the left child of `right`.

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

  + clone::<T, K, V, L>(page.as_page(), &mut right, s1, &mut n);

  + }

  + Ok(Put::Split {

  + split_key,

  + split_value,

  + left,

  + right,

  + freed,

  + })

  + } else {

  + left = txn.alloc_page()?;

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

  + debug!("{:?} < {:?}", u, k);

  + let mut n = 0;

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

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

  + let (s0a, s0b) = s0.split_at(u as usize);

  + clone::<T, K, V, L>(page.as_page(), &mut left, s0a, &mut n);

  + alloc::<T, K, V, L>(&mut left, k0, v0, l, r, &mut n);

  + clone::<T, K, V, L>(page.as_page(), &mut left, s0b, &mut n);

  +

  + let mut right: MutPage;

  + let freed;

  + if mutable && hdr.is_dirty() {

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

  + if let Some((k, v)) = L::truncate_left::<T, K, V>(&mut right, k as usize + 1) {

  + unsafe {

  + split_key = &*k;

  + split_value = &*v;

  + }

  + }

  + freed = 0;

  + } else {

  + right = txn.alloc_page()?;

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

  + let mut n = 0;

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

  + clone::<T, K, V, L>(page.as_page(), &mut right, s1, &mut n);

  + freed = page.offset | page_is_dirty

  + }

  + Ok(Put::Split {

  + split_key,

  + split_value,

  + left,

  + right,

  + freed,

  + })

  + }

  + }

  +

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

  + ) -> Result<Put<'a, K, V>, T::Error> {

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

  + })

  + }
• file addition: header.rs (-xw-x--x--)
  [0.371]
  + #[derive(Debug)]

  + #[repr(C)]

  + pub struct Header {

  + n: u16,

  + data: u16,

  + crc: u32,

  + left_page: u64,

  + }

  +

  + impl Header {

  + pub fn init(&mut self) {

  + self.n = (1u16).to_le(); // dirty page

  + self.data = 4096_u16.to_le();

  + self.crc = 0;

  + self.left_page = 0;

  + }

  +

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

  + u16::from_le(self.n) >> 4

  + }

  +

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

  + let dirty = u16::from_le(self.n) & 1;

  + self.n = ((n << 4) | dirty).to_le()

  + }

  +

  + pub fn is_dirty(&self) -> bool {

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

  + }

  +

  + pub fn left_page(&self) -> u64 {

  + u64::from_le(self.left_page)

  + }

  +

  + pub fn set_left_page(&mut self, l: u64) {

  + self.left_page = l.to_le()

  + }

  +

  + pub fn data(&self) -> u16 {

  + u16::from_le(self.data)

  + }

  +

  + pub fn set_data(&mut self, d: u16) {

  + self.data = d.to_le()

  + }

  +

  + pub fn decr(&mut self, s: usize) {

  + self.left_page = (self.left_page() - s as u64).to_le();

  + }

  +

  + pub fn set_occupied(&mut self, size: u64) {

  + self.left_page = ((self.left_page() & !0xfff) | size).to_le()

  + }

  +

  + pub fn incr(&mut self, s: usize) {

  + self.left_page = (self.left_page() + s as u64).to_le();

  + }

  +

  + pub fn is_leaf(&self) -> bool {

  + u64::from_le(self.left_page) <= 0xfff

  + }

  +

  + pub fn clean(&mut self) {

  + self.n = (u16::from_le(self.n) & 0xfff).to_le()

  + }

  + }

  +

  + pub const HDR: usize = core::mem::size_of::<Header>();

  +

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

  + unsafe { &*(page.data.as_ptr() as *const Header) }

  + }

  +

  + pub fn header_mut(page: &mut crate::MutPage) -> &mut Header {

  + unsafe { &mut *(page.0.data as *mut Header) }

  + }
• file addition: alloc.rs (-xw-x--x--)
  [0.371]
  + use super::*;

  +

  + pub(crate) trait Alloc {

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

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

  +

  + // n = number of items to remove

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

  + page: &mut MutPage,

  + n: usize,

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

  +

  + fn alloc_insert<T, K: Representable<T>, V: Representable<T>>(

  + new: &mut MutPage,

  + n: &mut isize,

  + size: usize,

  + r: u64,

  + ) -> usize;

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

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

  + type Offset: Into<(u64, u16)> + Copy + core::fmt::Debug;

  + fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(

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

  + ) -> Offsets<'a, Self::Offset>;

  + fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

  + page: crate::Page,

  + off: (u64, u16),

  + ) -> (&'a K, &'a V, u64);

  + }

  +

  + #[derive(Debug, Clone)]

  + pub enum Offsets<'a, A> {

  + Slice(&'a [A]),

  + Range(core::ops::Range<usize>),

  + }

  +

  + impl<'a, A: Into<(u64, u16)> + Copy> Offsets<'a, A> {

  + pub fn split_at(&self, mid: usize) -> (Self, Self) {

  + match self {

  + Offsets::Slice(s) if mid < s.len() => {

  + debug!("split_at: {:?} {:?}", s.len(), mid);

  + let (a, b) = s.split_at(mid);

  + (Offsets::Slice(a), Offsets::Slice(b))

  + }

  + Offsets::Slice(s) => {

  + debug_assert_eq!(mid, s.len());

  + (Offsets::Slice(s), Offsets::Slice(&[][..]))

  + }

  + Offsets::Range(r) => (

  + Offsets::Range(r.start..r.start + mid),

  + Offsets::Range(r.start + mid..r.end),

  + ),

  + }

  + }

  + pub fn first<T, K: Representable<T>, V: Representable<T>>(&self) -> (u64, u16) {

  + match self {

  + Offsets::Slice(s) => s[0].into(),

  + Offsets::Range(r) => {

  + let size = fixed_size::<T, K, V>().unwrap();

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

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

  + (0, (hdr_size + r.start * size) as u16)

  + }

  + }

  + }

  + }

  +

  + pub struct Leaf {}

  + pub struct Internal {}

  +

  + impl Alloc for Leaf {

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

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

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

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

  + header_size + (hdr.n() as usize) * f + size < hdr.data() as usize

  + } else {

  + HDR + (hdr.n() as usize) * 2 + 2 + size < hdr.data() as usize

  + }

  + }

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

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

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

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

  + header_size + ((hdr.left_page() & 0xfff) as usize) + size

  + < hdr.data() as usize

  + } else {

  + HDR + ((hdr.left_page() & 0xfff) as usize) + 2 + size < 4096

  + }

  + }

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

  + page: &mut MutPage,

  + n: usize,

  + ) -> Option<(*const K, *const V)> {

  + debug!("truncate_left {:?} {:?}", page, n);

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

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

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

  + // debug!("{:?} {:?} {:?}", new, hdr.n(), *n);

  + let hdr_n = header_mut(page).n();

  +

  + unsafe {

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

  + core::mem::MaybeUninit::uninit();

  + core::ptr::copy(

  + page.0.data.add(hdr_size + (n - 1) * f),

  + swap.as_mut_ptr() as *mut u8,

  + f,

  + );

  + core::ptr::copy(

  + page.0.data.add(hdr_size + n * f),

  + page.0.data.add(hdr_size),

  + (hdr_n as usize - n) * f,

  + );

  + core::ptr::copy(

  + swap.as_ptr() as *mut u8,

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

  + f,

  + );

  + }

  + debug!("{:?} - {:?}", hdr_n, n);

  + let hdr = header_mut(page);

  + hdr.set_n(hdr_n - n as u16);

  + hdr.decr(n * f);

  + unsafe {

  + Some(read::<T, K, V>(

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

  + ))

  + }

  + } else {

  + let hdr_n = header_mut(page).n();

  + unsafe {

  + core::ptr::copy(

  + page.0.data.add(HDR + n * 2),

  + page.0.data.add(HDR),

  + (hdr_n as usize - n) * 2,

  + );

  + }

  + let deleted_offsets = unsafe {

  + core::slice::from_raw_parts(page.0.data.add(HDR) as *const u16, n as usize)

  + };

  + let deleted_size: u64 = deleted_offsets

  + .iter()

  + .map(|&off| {

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

  + })

  + .sum();

  + let hdr = header_mut(page);

  + hdr.set_n(hdr_n - n as u16);

  + hdr.decr(deleted_size as usize);

  + None

  + }

  + }

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

  + let mut data = hdr.data() - size as u16;

  + data &= !((align - 1) as u16);

  + hdr.set_data(data);

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

  + hdr.incr(size);

  + data

  + }

  + fn alloc_insert<T, K: Representable<T>, V: Representable<T>>(

  + new: &mut MutPage,

  + n: &mut isize,

  + size: usize,

  + _: u64,

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

  + // debug!("{:?} {:?} {:?}", new, hdr.n(), *n);

  + let hdr_n = header_mut(new).n();

  + unsafe {

  + core::ptr::copy(

  + new.0.data.add(hdr_size + (*n as usize) * f),

  + new.0.data.add(hdr_size + (*n as usize) * f + f),

  + (hdr_n as usize - (*n as usize)) * f,

  + );

  + }

  + let hdr = header_mut(new);

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

  + hdr.incr(f);

  + hdr_size + (*n as usize) * f

  + } else {

  + let (hdr_n, off_new) = {

  + let hdr = header_mut(new);

  + (

  + hdr.n(),

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

  + )

  + };

  + unsafe {

  + core::ptr::copy(

  + new.0.data.add(HDR + (*n as usize) * 2),

  + new.0.data.add(HDR + (*n as usize) * 2 + 2),

  + (hdr_n as usize - (*n as usize)) * 2,

  + );

  + }

  + Self::set_offset(new, *n, 0, off_new);

  + off_new as usize

  + }

  + }

  + fn set_offset(new: &mut MutPage, n: isize, _: u64, off: u16) {

  + unsafe {

  + let ptr = new.0.data.offset(HDR as isize + n * 2) as *mut u16;

  + *ptr = off.to_le();

  + }

  + }

  + fn set_right_child(_: &mut MutPage, _: isize, _: u64) {}

  + type Offset = LeafOffset;

  +

  + fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(

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

  + ) -> Offsets<'a, Self::Offset> {

  + let hdr = header(page);

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

  + Offsets::Range(0..(hdr.n() as usize))

  + } else {

  + unsafe {

  + Offsets::Slice(core::slice::from_raw_parts(

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

  + hdr.n() as usize,

  + ))

  + }

  + }

  + }

  + fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

  + page: crate::Page,

  + (_, off): (u64, u16),

  + ) -> (&'a K, &'a V, u64) {

  + unsafe {

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

  + (&*k, &*v, 0)

  + }

  + }

  + }

  +

  + impl Alloc for Internal {

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

  + (HDR as usize) + (hdr.n() as usize) * 8 + 8 + size < hdr.data() as usize

  + }

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

  + (HDR as usize) + ((hdr.left_page() & 0xfff) as usize) + 8 + size < 4096

  + }

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

  + page: &mut MutPage,

  + n: usize,

  + ) -> Option<(*const K, *const V)> {

  + // The following line copies the left child of the last entry

  + // (hence the `- 8` and `- 1`)

  + let hdr_n = header_mut(page).n();

  + unsafe {

  + core::ptr::copy(

  + page.0.data.add(HDR + (n - 1) * 8),

  + page.0.data.add(HDR - 8),

  + (hdr_n as usize - n + 1) * 8,

  + );

  + }

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

  + ((8 + f) * (hdr_n as usize - n)) as u64

  + } else {

  + let offsets = unsafe {

  + core::slice::from_raw_parts(

  + page.0.data.add(HDR + n * 8) as *const u16,

  + hdr_n as usize - n as usize,

  + )

  + };

  + offsets

  + .iter()

  + .map(|&off| {

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

  + })

  + .sum()

  + };

  + let hdr = header_mut(page);

  + hdr.set_n(hdr_n - n as u16);

  + debug!("truncate_left {:?} {:?}", hdr.left_page(), size);

  + hdr.set_occupied(size);

  + None

  + }

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

  + let mut data = hdr.data() - size as u16;

  + data -= data % (align as u16);

  + hdr.set_data(data);

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

  + hdr.incr(size);

  + data

  + }

  + fn alloc_insert<T, K: Representable<T>, V: Representable<T>>(

  + new: &mut MutPage,

  + n: &mut isize,

  + size: usize,

  + r: u64,

  + ) -> usize {

  + let (hdr_n, off_new) = {

  + let hdr = header_mut(new);

  + (

  + hdr.n(),

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

  + )

  + };

  + unsafe {

  + core::ptr::copy(

  + new.0.data.add(HDR + (*n as usize) * 8),

  + new.0.data.add(HDR + (*n as usize) * 8 + 8),

  + (hdr_n as usize - (*n as usize)) * 8,

  + );

  + }

  + Self::set_offset(new, *n, r, off_new);

  + off_new as usize

  + }

  + fn set_offset(new: &mut MutPage, n: isize, r: u64, off: u16) {

  + unsafe {

  + let ptr = new.0.data.offset(HDR as isize + n * 8) as *mut u64;

  + *ptr = (r | off as u64).to_le();

  + }

  + }

  + fn set_right_child(page: &mut MutPage, n: isize, r: u64) {

  + unsafe {

  + let ptr = page.0.data.offset(HDR as isize + n * 8) as *mut u64;

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

  + *ptr = (r | off as u64).to_le();

  + }

  + }

  + type Offset = InternalOffset;

  +

  + fn offset_slice<'a, T, K: Representable<T>, V: Representable<T>>(

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

  + ) -> Offsets<'a, Self::Offset> {

  + let hdr = header(page);

  + unsafe {

  + Offsets::Slice(core::slice::from_raw_parts(

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

  + hdr.n() as usize,

  + ))

  + }

  + }

  + fn kv<'a, T, K: Representable<T>, V: Representable<T>>(

  + page: crate::Page,

  + (r, off): (u64, u16),

  + ) -> (&'a K, &'a V, u64) {

  + unsafe {

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

  + (&*k, &*v, r)

  + }

  + }

  + }

  + #[derive(Debug, Clone, Copy)]

  + #[repr(C)]

  + pub struct LeafOffset(u16);

  +

  + impl Into<(u64, u16)> for LeafOffset {

  + fn into(self) -> (u64, u16) {

  + (0, self.0)

  + }

  + }

  +

  + impl Into<usize> for LeafOffset {

  + fn into(self) -> usize {

  + self.0 as usize

  + }

  + }

  +

  + #[derive(Debug, Clone, Copy)]

  + #[repr(C)]

  + pub struct InternalOffset(u64);

  +

  + impl Into<(u64, u16)> for InternalOffset {

  + fn into(self) -> (u64, u16) {

  + (self.0 & !0xfff, (self.0 & 0xfff) as u16)

  + }

  + }

  +

  + impl Into<usize> for InternalOffset {

  + fn into(self) -> usize {

  + self.0 as usize

  + }

  + }
• replacement in sanakirja-core/src/btree/mod.rs at line 203
  [4.30691]→[4.50700:50760](∅→∅),[4.50700]→[4.50700:50760](∅→∅)
  − /// Whether the page can be written to (useful for RC).
  [4.30691]

  [4.50760]
  + // Whether the page can be written to (used for RC).
• replacement in sanakirja-core/src/btree/del.rs at line 50
  [4.53999]→[4.53999:54094](∅→∅)
  − // Find the leftmost page in the right subtree, that is where

  − // the "replacement" is.
  [4.53999]

  [4.54094]
  + // Find the leftmost page in the right subtree, that is where the

  + // "replacement" is.
• edit in sanakirja-core/src/btree/del.rs at line 53
  [4.54122]→[4.54122:54407](∅→∅),[4.54407]→[4.31507:31593](∅→∅),[4.31593]→[4.6030:6031](∅→∅),[4.31593]→[4.54484:54630](∅→∅),[4.6031]→[4.54484:54630](∅→∅),[4.54484]→[4.54484:54630](∅→∅),[4.54630]→[4.6032:6046](∅→∅),[4.6046]→[4.54630:54649](∅→∅),[4.54630]→[4.54630:54649](∅→∅),[4.54649]→[3.14343:14363](∅→∅),[3.14363]→[4.54649:54743](∅→∅),[4.54649]→[4.54649:54743](∅→∅),[4.54743]→[4.6047:6074](∅→∅),[4.6074]→[4.54743:54784](∅→∅),[4.54743]→[4.54743:54784](∅→∅),[4.54784]→[4.6075:6103](∅→∅),[4.6103]→[4.54784:54905](∅→∅),[4.54784]→[4.54784:54905](∅→∅),[4.54905]→[4.31594:31647](∅→∅),[4.31647]→[4.54949:54985](∅→∅),[4.54949]→[4.54949:54985](∅→∅),[4.54985]→[4.31648:31750](∅→∅),[4.31750]→[4.55069:55206](∅→∅),[4.55069]→[4.55069:55206](∅→∅),[4.55206]→[4.6104:6150](∅→∅)
  −

  − // Mark the replacement for deletion in the leaf. This is all

  − // lazy, so we don't do anything for now, in order to avoid

  − // duplicate work in case the page can be merged or

  − // rebalanced.

  − let ref mut curs0 = unsafe { cursor.stack[cursor.pointer].assume_init() };

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

  −

  − let mut last_op = ModifiedPage {

  − page: curs0.page,

  − mutable: cursor.pointer < cursor.first_rc_level,

  − c0,

  − l: 0,

  − r: 0,

  − ins: None,

  − ins2: None,

  − c1,

  − skip_first: true,

  − };

  − if cursor.pointer == cursor.first_rc_level {

  − debug!("decr_rc");

  − txn.decr_rc(curs0.page.offset)?;

  − debug!("/decr_rc");

  − }

  − if cursor.pointer >= cursor.first_rc_level {

  − let mut c0 = c0.clone();

  − let mut c1 = c1.clone();

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

  − while let Some((k, v, _)) =

  − P::next(curs0.page.as_page(), &mut c0).or_else(|| P::next(curs0.page.as_page(), &mut c1))

  − {

  − for o in k.page_offsets().chain(v.page_offsets()) {

  − txn.incr_rc(o)?;

  − }

  − }

  − }

  − debug!("pointer = {:?}", cursor.pointer);
• replacement in sanakirja-core/src/btree/del.rs at line 54
  [4.6151]→[4.6151:6260](∅→∅),[4.6260]→[4.55278:55342](∅→∅),[4.55278]→[4.55278:55342](∅→∅),[4.55342]→[4.31751:31828](∅→∅),[4.31828]→[4.6261:6449](∅→∅),[4.6449]→[4.55515:55529](∅→∅),[4.55515]→[4.55515:55529](∅→∅),[4.55529]→[4.6450:6584](∅→∅),[4.6584]→[4.55529:55545](∅→∅),[4.55529]→[4.55529:55545](∅→∅)
  − let mut k0 = MaybeUninit::uninit();

  − let mut v0 = MaybeUninit::uninit();

  − if p0 < cursor.pointer {

  − // increase the RC of the replacement.

  − unsafe {

  − let (k, v, _) = P::unchecked_current(curs0.page.as_page(), &c0);

  − if cursor.pointer >= cursor.first_rc_level {

  − for o in (&*k).page_offsets().chain((&*v).page_offsets()) {

  − txn.incr_rc(o)?;

  − }

  − }

  − core::ptr::copy_nonoverlapping(k, k0.as_mut_ptr(), 1);

  − core::ptr::copy_nonoverlapping(v, v0.as_mut_ptr(), 1);

  − }

  − }
  [4.6151]

  [4.55545]
  + // Mark the replacement for deletion in the leaf, and copy it into

  + // (k0, v0) if we're in an internal node.

  + let (mut last_op, k0, v0) = leaf_delete(txn, cursor, p0)?;
• replacement in sanakirja-core/src/btree/del.rs at line 64
  [4.55759]→[4.31883:31991](∅→∅),[4.31991]→[4.6585:6842](∅→∅),[4.6842]→[4.32074:32122](∅→∅),[4.32074]→[4.32074:32122](∅→∅),[4.32165]→[4.55800:55847](∅→∅),[4.55800]→[4.55800:55847](∅→∅),[4.55847]→[4.32166:32226](∅→∅),[4.32226]→[4.6843:6963](∅→∅)
  − let mut concat = {

  − let p = cursor.pointer;

  − let curs = cursor.current_mut();

  − let kv = if p == p0 {

  − unsafe { Some((

  − &*k0.as_ptr(),

  − &*v0.as_ptr()

  − )) }

  − } else {

  − None

  − };

  − concat(txn, curs, kv, last_op)?

  − };

  − let curs = cursor.current();

  − let c = curs.cursor.as_ref().unwrap();

  − let (c0, c1) = P::split_at(curs.page.as_page(), c);

  − debug!("page = {:?}, c0 = {:?}, c1 = {:?}", curs.page.offset, c0, c1);

  − debug!("concat = {:?}" ,concat);
  [4.55759]

  [4.4202]
  + let mut concat = concat(txn, cursor, p0, &k0, &v0, last_op)?;

  + debug!("concat = {:?}", concat);
• replacement in sanakirja-core/src/btree/del.rs at line 68
  [4.7002]→[4.4303:4325](∅→∅),[4.4303]→[4.4303:4325](∅→∅),[4.4325]→[4.56029:56145](∅→∅),[4.56029]→[4.56029:56145](∅→∅),[4.56145]→[3.14364:14522](∅→∅),[3.14522]→[4.56145:56354](∅→∅),[4.56145]→[4.56145:56354](∅→∅),[4.56354]→[4.7003:7029](∅→∅),[4.7029]→[4.56354:56385](∅→∅),[4.56354]→[4.56354:56385](∅→∅),[4.56385]→[3.14523:14555](∅→∅),[3.14555]→[4.56385:56877](∅→∅),[4.56385]→[4.56385:56877](∅→∅),[4.56877]→[3.14556:14681](∅→∅),[3.14681]→[4.57005:57199](∅→∅),[4.57005]→[4.57005:57199](∅→∅),[4.57199]→[4.7030:7092](∅→∅),[4.7092]→[3.14682:14714](∅→∅),[3.14714]→[4.57241:57733](∅→∅),[4.7092]→[4.57241:57733](∅→∅),[4.57241]→[4.57241:57733](∅→∅),[4.57733]→[3.14715:14948](∅→∅),[3.14948]→[4.7093:7165](∅→∅),[4.57733]→[4.7093:7165](∅→∅),[4.7231]→[4.7231:7339](∅→∅),[4.7339]→[3.14949:15008](∅→∅),[3.15008]→[4.7398:7593](∅→∅),[4.7398]→[4.7398:7593](∅→∅),[4.7593]→[4.57733:57904](∅→∅),[4.57733]→[4.57733:57904](∅→∅),[4.57904]→[4.7594:7665](∅→∅),[4.7665]→[3.15009:15041](∅→∅),[3.15041]→[4.57973:57997](∅→∅),[4.7665]→[4.57973:57997](∅→∅),[4.57973]→[4.57973:57997](∅→∅),[4.57997]→[4.7666:7698](∅→∅),[4.7698]→[4.58036:58592](∅→∅),[4.58036]→[4.58036:58592](∅→∅),[4.58592]→[3.15042:15405](∅→∅),[3.15405]→[4.58592:58801](∅→∅),[4.8057]→[4.58592:58801](∅→∅),[4.58592]→[4.58592:58801](∅→∅),[4.58801]→[4.8058:8097](∅→∅),[4.8097]→[3.15406:15457](∅→∅),[3.15457]→[4.58874:58898](∅→∅),[4.8154]→[4.58874:58898](∅→∅),[4.58874]→[4.58874:58898](∅→∅),[4.58898]→[3.15458:15490](∅→∅),[3.15490]→[4.58937:59302](∅→∅),[4.8209]→[4.58937:59302](∅→∅),[4.58937]→[4.58937:59302](∅→∅),[4.59302]→[4.8210:8549](∅→∅),[4.8549]→[4.59367:59562](∅→∅),[4.59367]→[4.59367:59562](∅→∅)
  − match merge {

  − Op::Merged {

  − page,

  − freed,

  − marker: _,

  − } => {

  − // If we're deleting at an internal node, the

  − // replacement has already been included in the merged

  − // page.

  − last_op = ModifiedPage {

  − page: curs.page,

  − mutable: cursor.pointer < cursor.first_rc_level,

  − c0,

  − l: page.0.offset,

  − r: 0,

  − ins: None,

  − ins2: None,

  − c1,

  − skip_first: true,

  − };

  − if cursor.pointer < cursor.first_rc_level {

  − free[cursor.pointer] = freed;

  − } else {

  − if cursor.pointer == cursor.first_rc_level {

  − txn.decr_rc(curs.page.offset)?;

  − }

  − modify_rc(txn, &last_op)?;

  − }

  − }

  − Op::Rebalanced { k, v, l, r, freed } => {

  − // If we're deleting at an internal node, the

  − // replacement is already in pages `l` or `r`.

  − last_op = ModifiedPage {

  − page: curs.page,

  − mutable: cursor.pointer < cursor.first_rc_level,

  − c0,

  − l,

  − r,

  − ins: Some((k, v)),

  − ins2: None,

  − c1,

  − skip_first: true,

  − };

  − if cursor.pointer < cursor.first_rc_level {

  − free[cursor.pointer] = freed;

  − } else {

  − if cursor.pointer == cursor.first_rc_level {

  − txn.decr_rc(curs.page.offset)?;

  − }

  − modify_rc(txn, &last_op)?;

  − }

  − }

  − Op::Put(Put::Ok(Ok { page, freed })) => {

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

  − let (l, r, ins, skip_first) = if cursor.pointer == p0 {

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

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

  − (0, page.0.offset, Some((k, v)), true)

  − } else if concat.mod_is_left {

  − (page.0.offset, 0, None, false)

  − } else {

  − (0, page.0.offset, None, false)

  − };

  − last_op = ModifiedPage {

  − page: curs.page,

  − mutable: cursor.pointer < cursor.first_rc_level,

  − c0,

  − l,

  − r,

  − ins,

  − ins2: None,

  − c1,

  − skip_first,

  − };

  − if cursor.pointer < cursor.first_rc_level {

  − free[cursor.pointer][0] = freed;

  − } else {

  − if cursor.pointer == cursor.first_rc_level {

  − txn.decr_rc(curs.page.offset)?;

  − }

  − modify_rc(txn, &last_op)?;

  − }

  − }

  − Op::Put(Put::Split {

  − left,

  − right,

  − split_key,

  − split_value,

  − freed,

  − }) => {

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

  − };

  − last_op = ModifiedPage {

  − page: curs.page,

  − mutable: cursor.pointer < cursor.first_rc_level,

  − c0,

  − l: left.0.offset,

  − r: right.0.offset,

  − ins,

  − ins2,

  − c1,

  − skip_first,

  − };

  − if cursor.pointer < cursor.first_rc_level {

  − free[cursor.pointer][0] = freed;

  − } else {

  − if cursor.pointer == cursor.first_rc_level {

  − txn.decr_rc(curs.page.offset)?;

  − }

  − modify_rc(txn, &last_op)?;

  − }

  − // If the split key is the replacement element, we

  − // have already increased its counter when we deleted

  − // it from its original position at the bottom of the

  − // tree.

  − if cursor.pointer + 1 >= cursor.first_rc_level && (split_key as *const K) != k0.as_ptr() {

  − for o in split_key.page_offsets().chain(split_value.page_offsets()) {

  − txn.incr_rc(o)?;

  − }

  − }

  − }

  − }
  [4.7002]

  [4.59562]
  + let mil = concat.mod_is_left;

  + last_op = handle_merge(txn, cursor, p0, &k0, &v0, mil, merge, &mut free)?;
• edit in sanakirja-core/src/btree/del.rs at line 76
  [4.4366]

  [4.59685]
  + if P::is_dirty(last_op.page.as_page()) {

  + txn.decr_rc_owned(last_op.page.offset)?

  + } else {

  + txn.decr_rc(last_op.page.offset)?

  + }
• replacement in sanakirja-core/src/btree/del.rs at line 83
  [4.59732]→[4.4367:4407](∅→∅),[4.4407]→[4.59732:60108](∅→∅),[4.59732]→[4.59732:60108](∅→∅),[4.60108]→[4.32229:32315](∅→∅),[4.32315]→[4.60185:60288](∅→∅),[4.60185]→[4.60185:60288](∅→∅),[4.60288]→[4.32316:32372](∅→∅),[4.32372]→[4.60335:60399](∅→∅),[4.60335]→[4.60335:60399](∅→∅),[4.60399]→[3.15491:15517](∅→∅),[3.15517]→[4.60399:60764](∅→∅),[4.60399]→[4.60399:60764](∅→∅)
  − debug!("modify {:?}", last_op);

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

  − Put::Ok(Ok { page, freed }) => {

  − free[0][0] = freed;

  − db.db = page.0

  − }

  − Put::Split {

  − split_key,

  − split_value,

  − left,

  − right,

  − freed,

  − } => {

  − free[0][0] = freed;

  − let mut page = txn.alloc_page()?;

  − P::init(&mut page);

  − P::put(

  − txn,

  − page.0,

  − true,

  − &P::first_cursor(page.0.as_page()),

  − split_key,

  − split_value,

  − None,

  − left.0.offset,

  − right.0.offset,

  − )?;

  − if cursor.first_rc_level <= 1 {

  − for o in split_key.page_offsets().chain(split_value.page_offsets()) {

  − txn.incr_rc(o)?;

  − }

  − }

  − db.db = page.0

  − }

  − }
  [4.59732]

  [4.60764]
  + update_root(txn, db, last_op, &k0, cursor.first_rc_level <= 1, &mut free)?
• replacement in sanakirja-core/src/btree/del.rs at line 89
  [4.60894]→[4.60894:60931](∅→∅)
  − txn.decr_rc_owned(p[0])?
  [4.60894]

  [4.60931]
  + txn.decr_rc(p[0])?
• replacement in sanakirja-core/src/btree/del.rs at line 94
  [4.61038]→[4.61038:61075](∅→∅)
  − txn.decr_rc_owned(p[1])?
  [4.61038]

  [4.61075]
  + txn.decr_rc(p[1])?
• replacement in sanakirja-core/src/btree/del.rs at line 111
  [4.32463]→[4.8550:8627](∅→∅)
  − debug!("find_min: {:?} {:?} {:?}", cur.page, cursor.pointer, left_page);
  [4.32463]

  [4.61446]
  + debug!(

  + "find_min: {:?} {:?} {:?}",

  + cur.page, cursor.pointer, left_page

  + );
• edit in sanakirja-core/src/btree/del.rs at line 127
  [4.61787]

  [4.61787]
  + }

  +

  + fn leaf_delete<

  + 'a,

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

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

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

  + P: BTreeMutPage<T, K, V> + core::fmt::Debug,

  + >(

  + txn: &mut T,

  + cursor: &mut Cursor<T, K, V, P>,

  + p0: usize,

  + ) -> Result<(ModifiedPage<'a, T, K, V, P>, MaybeUninit<K>, MaybeUninit<V>), T::Error> {

  + let ref mut curs0 = unsafe { cursor.stack[cursor.pointer].assume_init() };

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

  + if cursor.pointer == cursor.first_rc_level {

  + debug!("decr_rc");

  + txn.decr_rc(curs0.page.offset)?;

  + debug!("/decr_rc");

  + }

  + if cursor.pointer >= cursor.first_rc_level {

  + let mut c0 = c0.clone();

  + let mut c1 = c1.clone();

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

  + while let Some((k, v, _)) = P::next(curs0.page.as_page(), &mut c0)

  + .or_else(|| P::next(curs0.page.as_page(), &mut c1))

  + {

  + for o in k.page_offsets().chain(v.page_offsets()) {

  + txn.incr_rc(o)?;

  + }

  + }

  + }

  + debug!("pointer = {:?}", cursor.pointer);

  + let mut k0 = MaybeUninit::uninit();

  + let mut v0 = MaybeUninit::uninit();

  + if p0 < cursor.pointer {

  + // increase the RC of the replacement.

  + unsafe {

  + let (k, v, _) = P::unchecked_current(curs0.page.as_page(), &c0);

  + if cursor.pointer >= cursor.first_rc_level {

  + for o in (&*k).page_offsets().chain((&*v).page_offsets()) {

  + txn.incr_rc(o)?;

  + }

  + }

  + core::ptr::copy_nonoverlapping(k, k0.as_mut_ptr(), 1);

  + core::ptr::copy_nonoverlapping(v, v0.as_mut_ptr(), 1);

  + }

  + }

  + Ok((

  + ModifiedPage {

  + page: curs0.page,

  + mutable: cursor.pointer < cursor.first_rc_level,

  + c0,

  + l: 0,

  + r: 0,

  + ins: None,

  + ins2: None,

  + c1,

  + skip_first: true,

  + },

  + k0,

  + v0,

  + ))
• replacement in sanakirja-core/src/btree/del.rs at line 200
  [4.61957]→[4.32575:32614](∅→∅),[4.32614]→[4.8692:8727](∅→∅)
  − curs: &mut PageCursor<T, K, V, P>,

  − curs0: Option<(&'a K, &'a V)>,
  [4.61957]

  [4.32658]
  + cursor: &mut Cursor<T, K, V, P>,

  + p0: usize,

  + k0: &MaybeUninit<K>,

  + v0: &MaybeUninit<V>,
• edit in sanakirja-core/src/btree/del.rs at line 206
  [4.62136]

  [4.32702]
  + let p = cursor.pointer;

  + let curs = cursor.current_mut();
• replacement in sanakirja-core/src/btree/del.rs at line 209
  [4.32745]→[4.8728:8764](∅→∅)
  − if let Some((k0, v0)) = curs0 {
  [4.32745]

  [4.32778]
  + if p == p0 {
• replacement in sanakirja-core/src/btree/del.rs at line 213
  [4.62477]→[4.8765:8792](∅→∅)
  − mid: (k0, v0),
  [4.62477]

  [4.62502]
  + mid: unsafe { (&*k0.as_ptr(), &*v0.as_ptr()) },
• replacement in sanakirja-core/src/btree/del.rs at line 233
  [4.62739]→[4.33413:33492](∅→∅)
  − mid: unsafe { (core::mem::transmute(k), core::mem::transmute(v))},
  [4.62739]

  [4.62764]
  + mid: unsafe { (core::mem::transmute(k), core::mem::transmute(v)) },
• edit in sanakirja-core/src/btree/del.rs at line 237
  [4.62825]

  [4.62825]
  + }

  + }

  +

  + fn handle_merge<

  + 'a,

  + T: AllocPage + LoadPage,

  + K: Representable<T>,

  + V: Representable<T>,

  + P: BTreeMutPage<T, K, V> + core::fmt::Debug,

  + >(

  + txn: &mut T,

  + cursor: &mut Cursor<T, K, V, P>,

  + p0: usize,

  + k0: &MaybeUninit<K>,

  + v0: &MaybeUninit<V>,

  + mod_is_left: bool,

  + merge: Op<'a, T, K, V>,

  + free: &mut [[u64; 2]; N_CURSORS],

  + ) -> Result<ModifiedPage<'a, T, K, V, P>, T::Error> {

  + let mutable = cursor.pointer < cursor.first_rc_level;

  + let mut last_op = {

  + let curs = cursor.current_mut();

  + let c = curs.cursor.as_ref().unwrap();

  + let (c0, c1) = P::split_at(curs.page.as_page(), c);

  + ModifiedPage {

  + page: curs.page,

  + mutable,

  + c0,

  + l: 0,

  + r: 0,

  + ins: None,

  + ins2: None,

  + c1,

  + skip_first: true,

  + }

  + };

  + let freed = match merge {

  + Op::Merged {

  + page,

  + freed,

  + marker: _,

  + } => {

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

  + // replacement has already been included in the merged

  + // page.

  + last_op.l = page.0.offset;

  + freed

  + }

  + Op::Rebalanced { k, v, l, r, freed } => {

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

  + // replacement is already in pages `l` or `r`.

  + last_op.l = l;

  + last_op.r = r;

  + last_op.ins = Some((k, v));

  + freed

  + }

  + Op::Put(Put::Ok(Ok { page, freed })) => {

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

  + if cursor.pointer == p0 {

  + last_op.ins = unsafe { Some((&*k0.as_ptr(), &*v0.as_ptr())) };

  + last_op.r = page.0.offset;

  + } else {

  + last_op.skip_first = false;

  + if mod_is_left {

  + last_op.l = page.0.offset;

  + } else {

  + last_op.r = page.0.offset;

  + }

  + }

  + [freed, 0]

  + }

  + Op::Put(Put::Split {

  + left,

  + right,

  + split_key,

  + split_value,

  + freed,

  + }) => {

  + // This case only happens if `(K, V)` is not `Sized`, when

  + // either (1) a rebalance replaces a key/value pair with a

  + // larger one or (2) another split has happened in a page

  + // below.

  + if cursor.pointer == p0 {

  + // In this case, ins2 comes after ins, since the

  + // replacement is in the right child of the deleted

  + // key.

  + last_op.ins = unsafe { Some((&*k0.as_ptr(), &*v0.as_ptr())) };

  + last_op.ins2 = Some((split_key, split_value))

  + } else {

  + last_op.ins = Some((split_key, split_value));

  + last_op.skip_first = false

  + }

  + // The `l` and `r` fields are relative to `ins2` if

  + // `ins2.is_some()` or to `ins` else.

  + last_op.l = left.0.offset;

  + last_op.r = right.0.offset;

  + // If the split key is the replacement element, we have

  + // already increased its counter when we deleted it from

  + // its original position at the bottom of the tree.

  + //

  + // This can happen if we replaced an element and that

  + // replacement caused a split with the replacement as the

  + // middle element.

  + if cursor.pointer + 1 >= cursor.first_rc_level && (split_key as *const K) != k0.as_ptr()

  + {

  + for o in split_key.page_offsets().chain(split_value.page_offsets()) {

  + txn.incr_rc(o)?;

  + }

  + }

  + [freed, 0]

  + }

  + };

  + if cursor.pointer < cursor.first_rc_level {

  + free[cursor.pointer] = freed;

  + } else {

  + if cursor.pointer == cursor.first_rc_level {

  + txn.decr_rc(last_op.page.offset)?;

  + }

  + modify_rc(txn, &last_op)?;
• edit in sanakirja-core/src/btree/del.rs at line 359
  [4.62831]

  [4.62831]
  + Ok(last_op)
• edit in sanakirja-core/src/btree/del.rs at line 391
  [4.63650]

  [4.63650]
  + }

  + Ok(())

  + }

  +

  + fn update_root<

  + 'a,

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

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

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

  + P: BTreeMutPage<T, K, V> + core::fmt::Debug,

  + >(

  + txn: &mut T,

  + db: &mut Db_<T, K, V, P>,

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

  + k0: &MaybeUninit<K>,

  + is_rc: bool,

  + free: &mut [[u64; 2]; N_CURSORS],

  + ) -> Result<(), T::Error> {

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

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

  + Put::Ok(Ok { page, freed }) => {

  + free[0][0] = freed;

  + db.db = page.0

  + }

  + Put::Split {

  + split_key,

  + split_value,

  + left,

  + right,

  + freed,

  + } => {

  + free[0][0] = freed;

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

  + P::init(&mut page);

  + P::put(

  + txn,

  + page.0,

  + true,

  + &P::first_cursor(page.0.as_page()),

  + split_key,

  + split_value,

  + None,

  + left.0.offset,

  + right.0.offset,

  + )?;

  + if is_rc && (split_key as *const K) != k0.as_ptr() {

  + for o in split_key.page_offsets().chain(split_value.page_offsets()) {

  + txn.incr_rc(o)?;

  + }

  + }

  + db.db = page.0

  + }
• replacement in sanakirja/src/tests.rs at line 28
  [4.813]→[4.813:897](∅→∅)
  − type Ord = [u64; 100];

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

  − &self.0
  [4.813]

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

  + self.0.cmp(&b.0)