Unsized deletions + custom sizes back

Dependencies

• [2] 6UVFCERM Formatting, debugging, etc.
• [3] X3QVVQIS More debugging (del seems to work now)
• [4] QEUTVAZ4 Splitting btree::page
• [5] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
• [6] OP6SVMOD Resetting history
• [7] OTWDDJE7 Trait/type cleanup
• [8] WS4ZQM4R Debugging, tests, etc.
• [9] H3FVSQIQ Unsized pages

Change contents

• edit in sanakirja-core/src/btree/page_unsized.rs at line 37
  [3.2747]

  [3.2747]
  + type Saved = (*const K, *const V);

  + fn save_deleted_leaf_entry(k: &K, v: &V) -> Self::Saved {

  + (k as *const K, v as *const V)

  + }

  +

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

  + (&*s.0, &*s.1)

  + }

  +
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 60
  [3.3289]→[3.3289:3511](∅→∅)
  − if m.c1.is_leaf {

  − if m.ins2.is_some() {

  − occupied += 4;

  − } else {

  − occupied += 2;

  − }

  − } else if m.ins2.is_some() {
  [3.3289]

  [3.3511]
  + if m.ins2.is_some() {
• edit in sanakirja-core/src/btree/page.rs at line 22
  [3.8683]

  [3.8683]
  + fn tuple_size<K: Representable, V: Representable>() -> usize {

  + let s = ((K::SIZE.unwrap() + V::ALIGN - 1) & !(V::ALIGN - 1)) + V::SIZE.unwrap();

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

  + (s + al - 1) & !(al - 1)

  + }

  +
• replacement in sanakirja-core/src/btree/page.rs at line 29
  [3.8700]→[3.8700:8769](∅→∅)
  − pub struct Page<K, V> {

  − kv: core::marker::PhantomData<(K, V)>,

  − }
  [3.8700]

  [3.8769]
  + pub struct Page<K, V>(super::page_unsized::Page<K, V>);
• replacement in sanakirja-core/src/btree/page.rs at line 35
  [3.1301]→[3.1301:1421](∅→∅)
  − debug!("init {:?}", page);

  − let h = header_mut(page);

  − h.init();

  − debug!("init: {:?}", h);
  [3.1301]

  [3.9926]
  + <super::page_unsized::Page<K, V>>::init(page)
• replacement in sanakirja-core/src/btree/page.rs at line 39
  [3.1457]→[3.1457:1493](∅→∅),[3.1493]→[3.96:117](∅→∅)
  − let hdr = header_mut(page);

  − hdr.clean();
  [3.1457]

  [3.10094]
  + <super::page_unsized::Page<K, V>>::clean(page)

  + }

  +

  + type Saved = (K, V);

  + fn save_deleted_leaf_entry(k: &K, v: &V) -> Self::Saved {

  + unsafe {

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

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

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

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

  + (k0.assume_init(), v0.assume_init())

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

  [3.1354]
  + unsafe fn from_saved<'a>(s: &Self::Saved) -> (&'a K, &'a V) {

  + (core::mem::transmute(&s.0), core::mem::transmute(&s.1))

  + }

  +
• edit in sanakirja-core/src/btree/page.rs at line 77
  [3.44475]

  [3.44475]
  + // If m is an internal node, there is an extra cost,

  + // which doesn't exist if m is a leaf.
• replacement in sanakirja-core/src/btree/page.rs at line 151
  [3.1768]→[3.2535:2644](∅→∅),[3.2535]→[3.2535:2644](∅→∅)
  − let b = if Self::is_dirty(page.as_page()) { 1 } else { 0 };

  − freed = page.offset | b;
  [3.1768]

  [3.2644]
  + freed = page.offset | if Self::is_dirty(page.as_page()) { 1 } else { 0 };
• replacement in sanakirja-core/src/btree/page.rs at line 175
  [3.1693]→[2.5312:5373](∅→∅)
  − let f = core::mem::size_of::<Tuple<K, V>>();
  [3.1693]

  [3.1693]
  + let f = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page.rs at line 230
  [3.15906]→[3.45001:45058](∅→∅)
  − let f = core::mem::size_of::<Tuple<K, V>>();
  [3.15906]

  [3.45058]
  + let f = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page.rs at line 345
  [3.19528]→[3.45169:45226](∅→∅)
  − let f = core::mem::size_of::<Tuple<K, V>>();
  [3.19528]

  [3.45226]
  + let f = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page.rs at line 369
  [3.7817]→[3.45251:45308](∅→∅)
  − let f = core::mem::size_of::<Tuple<K, V>>();
  [3.7817]

  [3.45308]
  + let f = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page.rs at line 381
  [3.20851]→[3.45432:45484](∅→∅)
  − core::mem::size_of::<Tuple<K, V>>()
  [3.20851]

  [3.21215]
  + tuple_size::<K, V>()
• replacement in sanakirja-core/src/btree/page.rs at line 436
  [3.24688]→[3.45485:45554](∅→∅)
  − let f = core::mem::size_of::<Tuple<K, V>>();
  [3.24688]

  [3.45554]
  + let f = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page.rs at line 630
  [3.39419]→[3.46099:46159](∅→∅)
  − let size = core::mem::size_of::<Tuple<K, V>>();
  [3.39419]

  [3.39476]
  + let size = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 52
  [3.1916]→[3.46160:46209](∅→∅)
  − let f = core::mem::size_of::<Tuple<K, V>>();
  [3.1916]

  [3.46209]
  + let f = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page/put.rs at line 64
  [3.8085]→[3.47427:47480](∅→∅)
  − let s = core::mem::size_of::<Tuple<K, V>>();
  [3.8085]

  [3.47480]
  + let s = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page/alloc.rs at line 62
  [3.19432]→[3.47590:47654](∅→∅)
  − let size = core::mem::size_of::<Tuple<K, V>>();
  [3.19432]

  [3.19493]
  + let size = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page/alloc.rs at line 76
  [2.6547]→[3.47666:47719](∅→∅),[3.11190]→[3.47666:47719](∅→∅)
  − let f = core::mem::size_of::<Tuple<K, V>>();
  [2.6547]

  [3.47719]
  + let f = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page/alloc.rs at line 100
  [3.21047]→[3.48085:48138](∅→∅)
  − let f = core::mem::size_of::<Tuple<K, V>>();
  [3.21047]

  [3.48138]
  + let f = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page/alloc.rs at line 145
  [3.23632]→[3.49387:49440](∅→∅)
  − let f = core::mem::size_of::<Tuple<K, V>>();
  [3.23632]

  [2.7284]
  + let f = tuple_size::<K, V>();
• replacement in sanakirja-core/src/btree/page/alloc.rs at line 219
  [3.27048]→[3.50045:50098](∅→∅)
  − let f = core::mem::size_of::<Tuple<K, V>>();
  [3.27048]

  [2.7767]
  + let f = tuple_size::<K, V>();
• edit in sanakirja-core/src/btree/mod.rs at line 140
  [3.48665]

  [2.8946]
  + type Saved;

  + fn save_deleted_leaf_entry(k: &K, v: &V) -> Self::Saved;

  +

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

  +
• replacement in sanakirja-core/src/btree/del.rs at line 21
  [3.31281]→[3.15847:15929](∅→∅)
  − K: Representable + core::fmt::Debug,

  − V: Representable + core::fmt::Debug,
  [3.31281]

  [3.15929]
  + K: Representable + ?Sized + core::fmt::Debug,

  + V: Representable + ?Sized + core::fmt::Debug,
• replacement in sanakirja-core/src/btree/del.rs at line 40
  [3.31418]→[3.16004:16086](∅→∅)
  − K: Representable + core::fmt::Debug,

  − V: Representable + core::fmt::Debug,
  [3.31418]

  [3.16086]
  + K: Representable + ?Sized + core::fmt::Debug,

  + V: Representable + ?Sized + core::fmt::Debug,
• replacement in sanakirja-core/src/btree/del.rs at line 71
  [3.16907]→[3.16907:17066](∅→∅)
  − let mut k0 = MaybeUninit::uninit();

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

  − let (mut last_op, k0v0) = leaf_delete(txn, cursor, p0, &mut k0, &mut v0)?;
  [3.16907]

  [3.55545]
  + let (mut last_op, k0v0) = leaf_delete(txn, cursor, p0)?;
• replacement in sanakirja-core/src/btree/del.rs at line 85
  [3.17471]→[3.17471:17537](∅→∅)
  − let mut concat = concat(txn, cursor, p0, k0v0, last_op)?;
  [3.17471]

  [3.30945]
  + let mut concat = concat(txn, cursor, p0, &k0v0, last_op)?;
• replacement in sanakirja-core/src/btree/del.rs at line 97
  [3.31025]→[3.17790:17869](∅→∅)
  − last_op = handle_merge(txn, cursor, p0, k0v0, mil, merge, &mut free)?;
  [3.31025]

  [3.59562]
  + last_op = handle_merge(txn, cursor, p0, &k0v0, mil, merge, &mut free)?;
• replacement in sanakirja-core/src/btree/del.rs at line 131
  [3.61149]→[3.18162:18206](∅→∅)
  − K: Representable,

  − V: Representable,
  [3.61149]

  [3.18206]
  + K: Representable + ?Sized,

  + V: Representable + ?Sized,
• replacement in sanakirja-core/src/btree/del.rs at line 161
  [3.31607]→[3.18288:18370](∅→∅)
  − K: Representable + core::fmt::Debug,

  − V: Representable + core::fmt::Debug,
  [3.31607]

  [3.18370]
  + K: Representable + ?Sized + core::fmt::Debug,

  + V: Representable + ?Sized + core::fmt::Debug,
• replacement in sanakirja-core/src/btree/del.rs at line 168
  [3.31816]→[3.18457:18598](∅→∅)
  − k0: &'a mut MaybeUninit<K>,

  − v0: &'a mut MaybeUninit<V>,

  − ) -> Result<(ModifiedPage<'a, K, V, P>, Option<(&'a K, &'a V)>), T::Error> {
  [3.31816]

  [3.18598]
  + ) -> Result<(ModifiedPage<'a, K, V, P>, Option<P::Saved>), T::Error> {
• replacement in sanakirja-core/src/btree/del.rs at line 193
  [3.33162]→[3.18937:19272](∅→∅)
  − if K::SIZE.is_some() && V::SIZE.is_some() {

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

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

  − deleted = Some((&*k0.as_ptr(), &*v0.as_ptr()))

  − } else {

  − deleted = Some((k, v))

  − }
  [3.33162]

  [3.33296]
  + deleted = Some(P::save_deleted_leaf_entry(k, v))
• replacement in sanakirja-core/src/btree/del.rs at line 215
  [3.61838]→[3.19291:19335](∅→∅)
  − K: Representable,

  − V: Representable,
  [3.61838]

  [3.19335]
  + K: Representable + ?Sized,

  + V: Representable + ?Sized,
• replacement in sanakirja-core/src/btree/del.rs at line 222
  [3.33675]→[3.19417:19451](∅→∅)
  − k0v0: Option<(&'a K, &'a V)>,
  [3.33675]

  [3.19451]
  + k0v0: &Option<P::Saved>,
• replacement in sanakirja-core/src/btree/del.rs at line 229
  [3.33809]→[3.19537:19576](∅→∅)
  − if let Some((k0, v0)) = k0v0 {
  [3.33809]

  [3.19576]
  + if let Some(s) = k0v0 {

  + let (k0, v0) = unsafe { P::from_saved(s) };
• replacement in sanakirja-core/src/btree/del.rs at line 267
  [3.34015]→[3.20034:20078](∅→∅)
  − K: Representable,

  − V: Representable,
  [3.34015]

  [3.20078]
  + K: Representable + ?Sized,

  + V: Representable + ?Sized,
• replacement in sanakirja-core/src/btree/del.rs at line 274
  [3.34186]→[3.20160:20194](∅→∅)
  − k0v0: Option<(&'a K, &'a V)>,
  [3.34186]

  [3.34236]
  + k0v0: &Option<P::Saved>,
• replacement in sanakirja-core/src/btree/del.rs at line 321
  [3.35756]→[3.20247:20283](∅→∅)
  − last_op.ins = k0v0;
  [3.35756]

  [3.35835]
  + if let Some(k0v0) = k0v0 {

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

  + }
• replacement in sanakirja-core/src/btree/del.rs at line 350
  [3.36738]→[3.20284:20320](∅→∅)
  − last_op.ins = k0v0;
  [3.36738]

  [3.36817]
  + if let Some(k0v0) = k0v0 {

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

  + }
• replacement in sanakirja-core/src/btree/del.rs at line 369
  [3.37595]→[3.20321:20385](∅→∅)
  − let split_key_is_k0 = if let Some((k0, _)) = k0v0 {
  [3.37595]

  [3.20385]
  + let split_key_is_k0 = if let Some(k0v0) = k0v0 {

  + let (k0, _) = unsafe { P::from_saved(k0v0) };
• replacement in sanakirja-core/src/btree/del.rs at line 394
  [3.20849]→[2.10493:10588](∅→∅)
  − fn modify_rc<T: AllocPage + LoadPage, K: Representable, V: Representable, P: BTreePage<K, V>>(
  [3.20849]

  [3.62957]
  + fn modify_rc<

  + T: AllocPage + LoadPage,

  + K: Representable + ?Sized,

  + V: Representable + ?Sized,

  + P: BTreePage<K, V>,

  + >(
• replacement in sanakirja-core/src/btree/del.rs at line 483
  [3.38259]→[3.23372:23454](∅→∅)
  − K: Representable + core::fmt::Debug,

  − V: Representable + core::fmt::Debug,
  [3.38259]

  [3.23454]
  + K: Representable + ?Sized + core::fmt::Debug,

  + V: Representable + ?Sized + core::fmt::Debug,
• replacement in sanakirja-core/src/btree/del.rs at line 490
  [3.23568]→[3.23568:23596](∅→∅)
  − k0v0: Option<(&K, &V)>,
  [3.23568]

  [3.38514]
  + k0v0: Option<P::Saved>,
• replacement in sanakirja-core/src/btree/del.rs at line 535
  [3.39331]→[3.24096:24160](∅→∅)
  − let split_key_is_k0 = if let Some((k0, _)) = k0v0 {
  [3.39331]

  [3.24160]
  + let split_key_is_k0 = if let Some(ref k0v0) = k0v0 {

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