Improving safety of cursors

Dependencies

• [2] APPY2E7M Unsized deletions + custom sizes back
• [3] AOX2XQIS Actually, with the correct functions, Unsized pages are always slower than Sized pages (especially for writing)
• [4] KMT3MF5N Drop a database
• [5] OP6SVMOD Resetting history
• [6] WS4ZQM4R Debugging, tests, etc.
• [7] 6UVFCERM Formatting, debugging, etc.
• [8] QEUTVAZ4 Splitting btree::page
• [9] 6DMPXOAT More debugging
• [10] EAAYH6BQ Debugging put
• [11] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
• [12] FMN7X4J2 Micro-improvements, now noticeably faster than std::collections::BTreeMap
• [13] ONES3V46 reference counting works for put
• [14] X3QVVQIS More debugging (del seems to work now)
• [15] OTWDDJE7 Trait/type cleanup
• [16] H3FVSQIQ Unsized pages
• [17] S4V4QZ5C Debugging reference-counting for put

Change contents

• replacement in sanakirja-core/src/btree/put.rs at line 37
  [5.4538]→[5.70:118](∅→∅)
  − cursor.pointer < cursor.first_rc_level,
  [5.4538]

  [5.4587]
  + cursor.pointer() < cursor.first_rc_level,
• replacement in sanakirja-core/src/btree/put.rs at line 80
  [5.304]→[5.304:341](∅→∅),[5.341]→[5.30:70](∅→∅),[5.5516]→[5.30:70](∅→∅)
  − cursor.pointer -= 1;

  − if cursor.pointer > 0 {
  [5.304]

  [5.70]
  + cursor.pop();

  + if cursor.pointer() > 0 {
• replacement in sanakirja-core/src/btree/put.rs at line 86
  [5.215]→[5.215:279](∅→∅)
  − cursor.pointer < cursor.first_rc_level,
  [5.215]

  [5.279]
  + cursor.pointer() < cursor.first_rc_level,
• replacement in sanakirja-core/src/btree/put.rs at line 117
  [5.470]→[5.470:507](∅→∅),[5.507]→[5.533:573](∅→∅),[5.7373]→[5.533:573](∅→∅)
  − cursor.pointer -= 1;

  − if cursor.pointer > 0 {
  [5.470]

  [5.573]
  + cursor.pop();

  + if cursor.pointer() > 0 {
• replacement in sanakirja-core/src/btree/put.rs at line 123
  [5.746]→[5.746:810](∅→∅)
  − cursor.pointer < cursor.first_rc_level,
  [5.746]

  [5.810]
  + cursor.pointer() < cursor.first_rc_level,
• replacement in sanakirja-core/src/btree/put.rs at line 151
  [5.956]→[5.956:980](∅→∅)
  − cursor.pointer,
  [5.956]

  [5.980]
  + cursor.pointer(),
• replacement in sanakirja-core/src/btree/put.rs at line 154
  [5.651]→[5.7700:7748](∅→∅),[5.1017]→[5.7700:7748](∅→∅),[5.1107]→[5.7700:7748](∅→∅),[5.7700]→[5.7700:7748](∅→∅)
  − if cursor.pointer < cursor.first_rc_level {
  [5.1017]

  [5.7748]
  + if cursor.pointer() < cursor.first_rc_level {
• replacement in sanakirja-core/src/btree/put.rs at line 156
  [5.7814]→[5.7814:7852](∅→∅)
  − free[cursor.pointer] = freed;
  [5.7814]

  [5.7852]
  + free[cursor.pointer()] = freed;
• replacement in sanakirja-core/src/btree/put.rs at line 161
  [5.92]→[5.652:705](∅→∅),[5.7865]→[5.652:705](∅→∅)
  − if cursor.pointer == cursor.first_rc_level {
  [5.92]

  [5.7918]
  + if cursor.pointer() == cursor.first_rc_level {
• replacement in sanakirja-core/src/btree/put.rs at line 163
  [5.7958]→[5.706:748](∅→∅)
  − free[cursor.pointer] = freed;
  [5.7958]

  [5.8113]
  + free[cursor.pointer()] = freed;
• replacement in sanakirja-core/src/btree/page_unsized/put.rs at line 107
  [5.30069]→[5.30069:30106](∅→∅),[5.30106]→[3.192:253](∅→∅),[3.253]→[5.30168:30203](∅→∅),[5.30168]→[5.30168:30203](∅→∅)
  − core::slice::from_raw_parts(

  − page.data.as_ptr().add(HDR) as *const L::Offset,

  − n0 as usize,

  − )
  [5.30069]

  [5.30203]
  + core::slice::from_raw_parts(page.data.as_ptr().add(HDR) as *const L::Offset, n0 as usize)
• edit in sanakirja-core/src/btree/page_unsized/put.rs at line 112
  [5.30307]→[3.254:255](∅→∅)
  −
• replacement in sanakirja-core/src/btree/mod.rs at line 392
  [4.318]→[4.318:471](∅→∅)
  − pub fn drop<T: AllocPage, K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>>(txn: &mut T, db: Db_<K, V, P>) -> Result<(), T::Error> {
  [4.318]

  [4.471]
  + pub fn drop<

  + T: AllocPage,

  + K: Representable + ?Sized,

  + V: Representable + ?Sized,

  + P: BTreePage<K, V>,

  + >(

  + txn: &mut T,

  + db: Db_<K, V, P>,

  + ) -> Result<(), T::Error> {
• replacement in sanakirja-core/src/btree/mod.rs at line 404
  [4.519]→[4.519:660](∅→∅)
  − fn drop_<T: AllocPage, K: Representable+?Sized, V: Representable+?Sized, P: BTreePage<K, V>>(txn: &mut T, p: Page) -> Result<(), T::Error> {
  [4.519]

  [4.660]
  + fn drop_<T: AllocPage, K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>>(

  + txn: &mut T,

  + p: Page,

  + ) -> Result<(), T::Error> {
• replacement in sanakirja-core/src/btree/mod.rs at line 417
  [4.922]→[4.922:948](∅→∅)
  − return Ok(())
  [4.922]

  [4.948]
  + return Ok(());
• edit in sanakirja-core/src/btree/del.rs at line 13
  [5.53046]→[5.53046:53074](∅→∅)
  − use core::mem::MaybeUninit;
• replacement in sanakirja-core/src/btree/del.rs at line 47
  [5.53969]→[5.53969:53998](∅→∅)
  − let p0 = cursor.pointer;
  [5.53969]

  [5.53998]
  + let p0 = cursor.pointer();
• replacement in sanakirja-core/src/btree/del.rs at line 54
  [5.16452]→[5.16452:16469](∅→∅)
  − unsafe {
  [5.16452]

  [5.16469]
  + let (delk, delv, _) = unsafe {
• replacement in sanakirja-core/src/btree/del.rs at line 56
  [5.16509]→[5.16509:16753](∅→∅)
  − let (delk, delv, _) =

  − P::unchecked_current(txn, cur.page.as_page(), cur.cursor.as_ref().unwrap());

  − for o in delk.page_offsets().chain(delv.page_offsets()) {

  − txn.incr_rc(o)?;

  − }
  [5.16509]

  [5.16753]
  + P::unchecked_current(txn, cur.page.as_page(), cur.cursor.as_ref().unwrap())

  + };

  + for o in delk.page_offsets().chain(delv.page_offsets()) {

  + txn.incr_rc(o)?;
• replacement in sanakirja-core/src/btree/del.rs at line 74
  [5.17134]→[5.55653:55678](∅→∅),[5.55653]→[5.55653:55678](∅→∅),[5.31882]→[5.55678:55709](∅→∅),[5.55678]→[5.55678:55709](∅→∅)
  − cursor.pointer -= 1;

  − while cursor.pointer > 0 {
  [5.17134]

  [5.17136]
  + cursor.pop();

  + while cursor.pointer() > 0 {
• replacement in sanakirja-core/src/btree/del.rs at line 96
  [5.31108]→[5.59562:59591](∅→∅),[2.2591]→[5.59562:59591](∅→∅),[5.17869]→[5.59562:59591](∅→∅),[5.59562]→[5.59562:59591](∅→∅)
  − cursor.pointer -= 1;
  [2.2591]

  [5.59591]
  + cursor.pop()
• replacement in sanakirja-core/src/btree/del.rs at line 140
  [5.31480]→[5.31480:31524](∅→∅)
  − cur.page, cursor.pointer, left_page
  [5.31480]

  [5.31524]
  + cur.page,

  + cursor.pointer(),

  + left_page
• edit in sanakirja-core/src/btree/del.rs at line 145
  [5.61472]→[5.61472:61501](∅→∅)
  − cursor.pointer += 1;
• replacement in sanakirja-core/src/btree/del.rs at line 148
  [5.32574]→[5.61639:61708](∅→∅),[5.61639]→[5.61639:61708](∅→∅)
  − cursor.stack[cursor.pointer] = MaybeUninit::new(PageCursor {
  [5.32574]

  [5.61708]
  + cursor.push(PageCursor {
• replacement in sanakirja-core/src/btree/del.rs at line 153
  [5.61776]→[5.8628:8691](∅→∅)
  − debug!("find_min: cursor.pointer = {:?}", cursor.pointer);
  [5.61776]

  [5.61776]
  + debug!("find_min: cursor.pointer = {:?}", cursor.pointer());
• replacement in sanakirja-core/src/btree/del.rs at line 168
  [2.2827]→[5.18598:18674](∅→∅),[5.18598]→[5.18598:18674](∅→∅)
  − let curs0 = unsafe { &mut *cursor.stack[cursor.pointer].as_mut_ptr() };
  [2.2827]

  [5.31983]
  + let is_rc = cursor.pointer() >= cursor.first_rc_level;

  + let del_at_internal = p0 < cursor.pointer();

  + let ref mut curs0 = cursor.last();
• replacement in sanakirja-core/src/btree/del.rs at line 172
  [5.32220]→[5.32220:32269](∅→∅)
  − if cursor.pointer >= cursor.first_rc_level {
  [5.32069]

  [5.32269]
  + if is_rc {
• replacement in sanakirja-core/src/btree/del.rs at line 185
  [5.18853]→[5.32790:32819](∅→∅),[5.32790]→[5.32790:32819](∅→∅)
  − if p0 < cursor.pointer {
  [5.18853]

  [5.32819]
  + if del_at_internal {
• replacement in sanakirja-core/src/btree/del.rs at line 187
  [5.32866]→[5.32866:32883](∅→∅),[5.32883]→[5.18854:18936](∅→∅),[5.18936]→[5.32960:33148](∅→∅),[5.32960]→[5.32960:33148](∅→∅)
  − unsafe {

  − let (k, v, _) = P::unchecked_current(txn, 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)?;

  − }
  [5.32866]

  [5.33148]
  + let (k, v, _) = unsafe { P::unchecked_current(txn, curs0.page.as_page(), &c0) };

  + if is_rc {

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

  + txn.incr_rc(o)?;
• edit in sanakirja-core/src/btree/del.rs at line 192
  [5.33162]→[2.2828:2889](∅→∅)
  − deleted = Some(P::save_deleted_leaf_entry(k, v))
• edit in sanakirja-core/src/btree/del.rs at line 193
  [5.33306]

  [5.33306]
  + deleted = Some(P::save_deleted_leaf_entry(k, v))
• replacement in sanakirja-core/src/btree/del.rs at line 198
  [5.33374]→[5.33374:33435](∅→∅)
  − mutable: cursor.pointer < cursor.first_rc_level,
  [5.33374]

  [5.33435]
  + mutable: cursor.pointer() < cursor.first_rc_level,
• replacement in sanakirja-core/src/btree/del.rs at line 224
  [5.19536]→[5.33726:33754](∅→∅),[5.62136]→[5.33726:33754](∅→∅)
  − let p = cursor.pointer;
  [5.19536]

  [5.33754]
  + let p = cursor.pointer();
• replacement in sanakirja-core/src/btree/del.rs at line 278
  [5.20246]→[5.34379:34437](∅→∅),[5.34379]→[5.34379:34437](∅→∅)
  − let mutable = cursor.pointer < cursor.first_rc_level;
  [5.20246]

  [5.34437]
  + let mutable = cursor.pointer() < cursor.first_rc_level;
• replacement in sanakirja-core/src/btree/del.rs at line 319
  [5.35718]→[5.35718:35756](∅→∅)
  − if cursor.pointer == p0 {
  [5.35718]

  [2.3165]
  + if cursor.pointer() == p0 {
• replacement in sanakirja-core/src/btree/del.rs at line 345
  [5.36543]→[5.36543:36581](∅→∅)
  − if cursor.pointer == p0 {
  [5.36543]

  [5.36581]
  + if cursor.pointer() == p0 {
• replacement in sanakirja-core/src/btree/del.rs at line 374
  [5.20503]→[5.10411:10492](∅→∅)
  − if cursor.pointer + 1 >= cursor.first_rc_level && !split_key_is_k0 {
  [5.20503]

  [5.37710]
  + if cursor.pointer() + 1 >= cursor.first_rc_level && !split_key_is_k0 {
• replacement in sanakirja-core/src/btree/del.rs at line 382
  [5.37905]→[5.37905:37991](∅→∅)
  − if cursor.pointer < cursor.first_rc_level {

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

  [5.62825]
  + if cursor.pointer() < cursor.first_rc_level {

  + free[cursor.pointer()] = freed;
• replacement in sanakirja-core/src/btree/del.rs at line 385
  [5.62831]→[5.20583:20653](∅→∅)
  − modify_rc(txn, &last_op, cursor.pointer, cursor.first_rc_level)?;
  [5.62831]

  [5.38150]
  + modify_rc(txn, &last_op, cursor.pointer(), cursor.first_rc_level)?;
• replacement in sanakirja-core/src/btree/cursor.rs at line 41
  [5.51806]→[5.24668:24741](∅→∅),[5.11010]→[5.24668:24741](∅→∅),[5.24668]→[5.24668:24741](∅→∅)
  − pub stack: [core::mem::MaybeUninit<PageCursor<K, V, P>>; N_CURSORS],
  [5.11010]

  [5.65137]
  + // Invariant: all items up to (and including) stack[pointer],

  + // except possibly 0, are initialised.

  + stack: [core::mem::MaybeUninit<PageCursor<K, V, P>>; N_CURSORS],
• replacement in sanakirja-core/src/btree/cursor.rs at line 45
  [5.65168]→[5.65168:65192](∅→∅)
  − pub pointer: usize,
  [5.65168]

  [5.65192]
  + pointer: usize,

  + }

  +

  + impl<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>>

  + core::ops::Index<usize> for Cursor<K, V, P>

  + {

  + type Output = PageCursor<K, V, P>;

  + fn index(&self, i: usize) -> &PageCursor<K, V, P> {

  + assert!(i <= self.pointer);

  + unsafe { &*self.stack.index(i).as_ptr() }

  + }

  + }

  +

  + impl<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>>

  + core::ops::IndexMut<usize> for Cursor<K, V, P>

  + {

  + fn index_mut(&mut self, i: usize) -> &mut PageCursor<K, V, P> {

  + assert!(i <= self.pointer);

  + unsafe { &mut *self.stack.index_mut(i).as_mut_ptr() }

  + }
• edit in sanakirja-core/src/btree/cursor.rs at line 72
  [5.65498]

  [5.65498]
  + cursor: None,

  + });

  + stack[0] = MaybeUninit::new(PageCursor {

  + page: CowPage::null(),
• edit in sanakirja-core/src/btree/cursor.rs at line 83
  [5.65645]

  [5.65645]
  + }

  +

  + pub fn push(&mut self, p: PageCursor<K, V, P>) {

  + self.pointer += 1;

  + self.stack[self.pointer] = MaybeUninit::new(p)
• edit in sanakirja-core/src/btree/cursor.rs at line 89
  [5.65651]

  [5.65651]
  +

  + pub fn last(&mut self) -> &mut PageCursor<K, V, P> {

  + unsafe { &mut *self.stack[self.pointer].as_mut_ptr() }

  + }
• edit in sanakirja-core/src/btree/cursor.rs at line 100
  [5.65883]

  [5.25008]
  + pub fn pointer(&self) -> usize {

  + self.pointer

  + }

  +

  + pub fn pop(&mut self) {

  + self.pointer -= 1

  + }

  +