More debugging (del seems to work now)
[?]
Feb 1, 2021, 5:33 PM
X3QVVQIS7B7L3XYZAWL3OOBUXOJ6RMOKQ45YMLLGAHYPEEKZ45ZACDependencies
- [2]
EAAYH6BQDebugging put - [3]
UAQX27N4Tests - [4]
OP6SVMODResetting history - [5]
EHJFNMB2Debugging - [6]
WS4ZQM4RDebugging, tests, etc.
Change contents
- edit in sanakirja-core/src/btree/page.rs at line 3
use core::mem::MaybeUninit; - replacement in sanakirja-core/src/btree/page.rs at line 12
#[derive(PartialEq, Eq, PartialOrd, Ord)]#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)] - replacement in sanakirja-core/src/btree/page.rs at line 93
if let Some((k, v, _)) = m.ins {if let Some((k, v)) = m.ins { - replacement in sanakirja-core/src/btree/page.rs at line 273
return Ok(Op::Put(if let Some((k, v, r)) = m.modified.ins {return Ok(Op::Put(if let Some((k, v)) = m.modified.ins { - replacement in sanakirja-core/src/btree/page.rs at line 282
r,m.modified.r, - replacement in sanakirja-core/src/btree/page.rs at line 291
if m.modified.c0.is_leaf {rebalance::<_, _, _, Leaf>(txn, m)if m.mod_is_left {if m.modified.c0.is_leaf {rebalance_left::<_, _, _, Leaf>(txn, m)} else {rebalance_left::<_, _, _, Internal>(txn, m)} - replacement in sanakirja-core/src/btree/page.rs at line 298
rebalance::<_, _, _, Internal>(txn, m)if m.modified.c0.is_leaf {rebalance_right::<_, _, _, Leaf>(txn, m)} else {rebalance_right::<_, _, _, Internal>(txn, m)} - edit in sanakirja-core/src/btree/page.rs at line 426
debug!("set_cursor, {:?} lookup = {:?}", page.offset, lookup); - replacement in sanakirja-core/src/btree/page.rs at line 930
if let Some((k, v, r)) = m.ins {alloc::<_, _, _, L>(new, &*k, &*v, m.l, r, n);if let Some((k, v)) = m.ins {alloc::<_, _, _, L>(new, &*k, &*v, m.l, m.r, n); - replacement in sanakirja-core/src/btree/page.rs at line 971
fn rebalance<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>(fn rebalance_left<'a, T: AllocPage + core::fmt::Debug, K: Representable<T> + core::fmt::Debug, V: Representable<T> + core::fmt::Debug, L: Alloc>( - edit in sanakirja-core/src/btree/page.rs at line 975
assert!(m.mod_is_left);// First element of the right page. We'll rotate it to the left// page. - replacement in sanakirja-core/src/btree/page.rs at line 983[4.36942]→[4.21693:21835](∅→∅),[4.21835]→[4.37068:37118](∅→∅),[4.37068]→[4.37068:37118](∅→∅),[4.37118]→[4.21836:21909](∅→∅),[4.21909]→[4.37195:37208](∅→∅),[4.37195]→[4.37195:37208](∅→∅)
let new_left = if header(m.modified.page.as_page()).is_dirty() {let mut page = unsafe { core::mem::transmute(m.modified.page) };let mut n = m.modified.c1.total as isize;alloc::<T, K, V, L>(&mut page, m.mid.0, m.mid.1, 0, rl, &mut n);pagelet 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.l,m.modified.r,)? {page} else {unreachable!()} - replacement in sanakirja-core/src/btree/page.rs at line 1002[4.37221]→[4.21910:22085](∅→∅),[4.22085]→[4.37418:37441](∅→∅),[4.37418]→[4.37418:37441](∅→∅),[4.37441]→[4.22086:22235](∅→∅)
let mut new = txn.alloc_page()?;<Page<K, V> as BTreeMutPage<T, K, V>>::init(&mut new);let s = L::offset_slice::<T, K, V>(m.modified.page.as_page());let mut n = 0;clone::<T, K, V, L>(m.modified.page.as_page(), &mut new, s, &mut n);alloc::<T, K, V, L>(&mut new, m.mid.0, m.mid.1, 0, rl, &mut n);<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); - replacement in sanakirja-core/src/btree/page.rs at line 1009
let b = if header(m.modified.page.as_page()).is_dirty() { 1 } else { 0 };freed[0] = m.modified.page.offset | b;newlet 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))} - edit in sanakirja-core/src/btree/page.rs at line 1050
let new_right = <Page<K, V>>::del(txn, m.other, &rc, r)?; - edit in sanakirja-core/src/btree/page.rs at line 1063
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) }; - edit in sanakirja-core/src/btree/page.rs at line 1076
// 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.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,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,})} - replacement in sanakirja-core/src/btree/mod.rs at line 150
if let Some((k, v, r)) = m.ins {if let Some((k, v)) = m.ins { - replacement in sanakirja-core/src/btree/mod.rs at line 152
Self::replace(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, r)Self::replace(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, m.r) - replacement in sanakirja-core/src/btree/mod.rs at line 154
Self::put(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, r)Self::put(txn, m.page, m.mutable, &m.c1, &*k, &*v, m.l, m.r) - replacement in sanakirja-core/src/btree/mod.rs at line 167
} else {} else if m.l > 0 { - edit in sanakirja-core/src/btree/mod.rs at line 169
} else {let mut c1 = m.c1.clone();Self::move_next(m.page.as_page(), &mut c1);Ok(Put::Ok(Self::update_left_child(txn, m.page, m.mutable, &c1, m.r)?)) - edit in sanakirja-core/src/btree/mod.rs at line 212
// Replace the left child of c1's last element with `r`.pub r: u64, - replacement in sanakirja-core/src/btree/mod.rs at line 215
pub ins: Option<(&'a K, &'a V, u64)>,pub ins: Option<(&'a K, &'a V)>, - edit in sanakirja-core/src/btree/del.rs at line 60
- edit in sanakirja-core/src/btree/del.rs at line 66
r: 0, - edit in sanakirja-core/src/btree/del.rs at line 72
debug!("decr_rc"); - edit in sanakirja-core/src/btree/del.rs at line 74
debug!("/decr_rc"); - replacement in sanakirja-core/src/btree/del.rs at line 88
if p0 < cursor.pointer && cursor.pointer >= cursor.first_rc_level {debug!("pointer = {:?}", cursor.pointer);let mut k0 = MaybeUninit::uninit();let mut v0 = MaybeUninit::uninit();if p0 < cursor.pointer { - replacement in sanakirja-core/src/btree/del.rs at line 96
for o in (&*k).page_offsets().chain((&*v).page_offsets()) {txn.incr_rc(o)?;if cursor.pointer >= cursor.first_rc_level {for o in (&*k).page_offsets().chain((&*v).page_offsets()) {txn.incr_rc(o)?;} - edit in sanakirja-core/src/btree/del.rs at line 101
core::ptr::copy_nonoverlapping(k, k0.as_mut_ptr(), 1);core::ptr::copy_nonoverlapping(v, v0.as_mut_ptr(), 1); - edit in sanakirja-core/src/btree/del.rs at line 110
debug!("cursor.pointer = {:?}", cursor.pointer); - replacement in sanakirja-core/src/btree/del.rs at line 115
concat(txn, curs, if p == p0 { Some(&curs0) } else { None }, last_op)?let kv = if p == p0 {unsafe { Some((&*k0.as_ptr(),&*v0.as_ptr())) }} else {None};concat(txn, curs, kv, last_op)? - edit in sanakirja-core/src/btree/del.rs at line 126
debug!("candidate: {:?}", concat); - edit in sanakirja-core/src/btree/del.rs at line 128
debug!("page = {:?}, c0 = {:?}, c1 = {:?}", curs.page.offset, c0, c1);debug!("concat = {:?}" ,concat); - replacement in sanakirja-core/src/btree/del.rs at line 131
debug!("merge = {:?}", merge);debug!("merge: {:?}", merge); - edit in sanakirja-core/src/btree/del.rs at line 143
r: 0, - replacement in sanakirja-core/src/btree/del.rs at line 163
ins: Some((k, v, r)),r,ins: Some((k, v)), - edit in sanakirja-core/src/btree/del.rs at line 178
let (l, r, ins, skip_first) = if cursor.pointer == p0 {let l = P::left_child(page.0.as_page(), &c1);let k = unsafe { &*k0.as_ptr() };let v = unsafe { &*v0.as_ptr() };(l, 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)}; - replacement in sanakirja-core/src/btree/del.rs at line 192
l: page.0.offset,ins: None,l,r,ins, - replacement in sanakirja-core/src/btree/del.rs at line 196
skip_first: false,skip_first, - edit in sanakirja-core/src/btree/del.rs at line 214
// Here, if we are at cursor.pointer == p0, the// replacement has been either inserted into one of// {left, right}, or is the split key/value// itself. Therefore, we just have to delete the// key/value selected for deletion in page p0 (the// current page). - replacement in sanakirja-core/src/btree/del.rs at line 225
ins: Some((split_key, split_value, right.0.offset)),r: right.0.offset,ins: Some((split_key, split_value)), - replacement in sanakirja-core/src/btree/del.rs at line 228
skip_first: false,skip_first: cursor.pointer == p0, - replacement in sanakirja-core/src/btree/del.rs at line 238
if cursor.pointer + 1 >= cursor.first_rc_level {// 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() { - edit in sanakirja-core/src/btree/del.rs at line 318
debug!("find_min: {:?} {:?} {:?}", cur.page, cursor.pointer, left_page); - edit in sanakirja-core/src/btree/del.rs at line 329
debug!("find_min: cursor.pointer = {:?}", cursor.pointer); - replacement in sanakirja-core/src/btree/del.rs at line 342
curs0: Option<&PageCursor<T, K, V, P>>,curs0: Option<(&'a K, &'a V)>, - replacement in sanakirja-core/src/btree/del.rs at line 346
if let Some(curs0) = curs0 {if let Some((k0, v0)) = curs0 { - edit in sanakirja-core/src/btree/del.rs at line 348
let (k, v, _) =unsafe { P::unchecked_current(curs0.page.as_page(), curs0.cursor.as_ref().unwrap()) }; - replacement in sanakirja-core/src/btree/del.rs at line 350
mid: unsafe { (core::mem::transmute(k), core::mem::transmute(v)) },mid: (k0, v0), - edit in sanakirja-core/src/btree/del.rs at line 357
// Not the last element of the page. - edit in sanakirja-core/src/btree/del.rs at line 360
// Last element of the page. - edit in sanakirja-core/src/btree/cursor.rs at line 4
use log::*; - edit in sanakirja/src/tests.rs at line 101
/* - replacement in sanakirja/src/tests.rs at line 102
let d = 10;for i in 0..d {debug!("deleting {:?}", (i*i)%1_000_000);debug::debug(&txn, &db, &format!("debug{}", i), true);del(&mut txn, &mut db, &((i * i) % 1_000_000), None).unwrap();}debug::debug(&txn, &db, "debug_final", true);txn.commit().unwrap();*/ - edit in sanakirja/src/tests.rs at line 177
- edit in sanakirja/src/tests.rs at line 181
pub fn del_mid() {type B = btree::page::Page<u64, ()>;env_logger::try_init().unwrap_or(());let env = Env::new_anon(409600000).unwrap();let mut txn = Env::mut_txn_begin(&env).unwrap();let mut db: Db<_, u64, (), B> = create_db(&mut txn).unwrap();let n = 2_000 as u64;let now = std::time::SystemTime::now();let mut values = Vec::with_capacity(n as usize);for i in 0..n - 1 {if put(&mut txn, &mut db, &i, &()).unwrap() {values.push(i);}}debug!("==============================");debug::debug(&txn, &db, "debug_pre", true);del(&mut txn, &mut db, &1274, None).unwrap();debug::debug(&txn, &db, "debug_post", true);debug!("==============================");del(&mut txn, &mut db, &1529, None).unwrap();debug::debug(&txn, &db, "debug_post2", true);assert!(!del(&mut txn, &mut db, &(n + 1), None).unwrap());// for i in 0..400 {// debug!("============== {:?}", i);// del(&mut txn, &mut db, &i, None).unwrap();// }}#[test] - replacement in sanakirja/src/tests.rs at line 217
let n = 1000 as u64;let n = 2_000 as u64; - edit in sanakirja/src/tests.rs at line 259
debug!("==============================");debug::debug(&txn, &db, "debug_pre", true);del(&mut txn, &mut db, &1019, None).unwrap();debug::debug(&txn, &db, "debug_post", true);for i in 0..512 {debug!("============== {:?}", i);del(&mut txn, &mut db, &i, None).unwrap();}debug!("================= done");let _db3 = fork_db(&mut txn, &db).unwrap();for i in 1530..1531 {debug!("============== {:?}", i);debug::debug(&txn, &db, "debug_pre", true);del(&mut txn, &mut db, &i, None).unwrap();debug::debug(&txn, &db, "debug_post", true);}debug!("================= done"); - edit in sanakirja/src/tests.rs at line 279