Some page splits were not properly handled in deletions

[?]

May 16, 2021, 8:02 PM

GGEFV4YYK7E6J3544XSXN5CBASQI3QE6LTFZCJAGOXHEEKD6BRCQC

Dependencies

[2] 77TAHKV4 Fixing a logical error (again) in del
[3] LSQ6V7M6 Cleanup + docs
[4] PUOGOIJ3 Debugging, impls and version bump
[5] W2MIZD5B Single file databases + CRC for the root pages (checking the other pages makes everything very slow)
[6] 7T2CCH3P Fixing a segfault (wrong offset in page_unsized::del)
[7] JIQOPUYH Fixing a logical error causing a panic in some very rare cases
[8] W26CFMAQ Improving safety of cursors
[9] OTWDDJE7 Trait/type cleanup
[10] GPP7KJSF Version bump
[11] 73Z2UB3J Cleanup + comments
[12] OP6SVMOD Resetting history
[13] QEUTVAZ4 Splitting btree::page
[14] DEKK3RUI Fixing a bug when splitting unsized pages
[15] 2ZRCQBXP Version bump
[16] J7LJZBME Setting reverse cursor to last by default
[17] HN6Z5DU4 Cleanup
[18] APPY2E7M Unsized deletions + custom sizes back
[19] Z33OHFPA Version bump
[20] T73WR2BX Cleaner RC increments for keys and values containing references + more comments in `del`
[21] DASFQGOR Debugging
[*] TSMS6W4D Fully commented implementation of Sized nodes + massive cleanup

Change contents

edit in sanakirja-core/src/btree/del.rs at line 54

[23.36569]

[23.36569]

// Whether the page we just modified is `self.l`.
pub mod_is_left: bool,
edit in sanakirja-core/src/btree/del.rs at line 269

[3.33534]

[3.33580]

// The following (`mod_is_left`) is meaningless in this
// context, and isn't actually used: indeed, the only
// place where this field is used is when modifying the
// root, when `ins.is_some()`.
mod_is_left: true,
replacement in sanakirja-core/src/btree/del.rs at line 380

[3.3164]→[3.34236:34259](∅→∅),[3.7480]→[3.34236:34259](∅→∅),[3.20194]→[3.34236:34259](∅→∅),[3.34236]→[3.34236:34259](∅→∅)

mod_is_left: bool,

[3.7480]

[3.34259]

mod_is_left: bool, // The modified page in the `merge` is the left one.
edit in sanakirja-core/src/btree/del.rs at line 402

[3.34827]

[3.34827]

mod_is_left,
replacement in sanakirja-core/src/btree/del.rs at line 501

[3.36543]→[3.16764:16826](∅→∅)

let split_key_is_k0 = if cursor.len() + 1 == p0 {

[3.36543]

[3.36581]

let split_key_is_k0 = if cursor.len() == p0 {
replacement in sanakirja-core/src/btree/del.rs at line 514

[3.1]→[3.1:66](∅→∅),[3.66]→[2.0:187](∅→∅)

// If this split isn't at the root, and the page
// modified in the last step is the one on the right
// of the current entry, move right one step before
// inserting the split key/value.

[3.1]

[3.243]

// If the page modified in the last step is the one on
// the right of the current entry, move right one step
// before inserting the split key/value.
edit in sanakirja-core/src/btree/del.rs at line 750

[3.13175]

[3.12618]

let mut c1 = m.c1.clone();
if !m.skip_first && !m.mod_is_left {
// This means that the page below just split, since we
// have to insert an extra entry on the root page.
//
// However, the extra entry is to be inserted (by
// `P::put`) *before* `c1`'s first element, which is
// incorrect since the page that split is the right child
// of `c1`'s first element. Therefore, we need to move
// `c1` one notch to the right.
assert!(m.ins2.is_none());
P::move_next(&mut c1);
}
replacement in sanakirja-core/src/btree/del.rs at line 768

[3.12720]→[3.12720:12739](∅→∅)

&m.c1,

[3.12720]

[3.12739]

&c1,
replacement in sanakirja-core/Cargo.toml at line 3

[3.70812]→[2.570:588](∅→∅)

version = "1.2.7"

[3.70812]

[3.70847]

version = "1.2.8"