Two iterators (convenience functions), along with tests to move cursors (put and del still destroy cursors though)

Dependencies

• [2] KM3JAFGP Adding a test for next/prev
• [3] EAAYH6BQ Debugging put
• [4] PXF3R6SV Improving test coverage for btree::cursor
• [5] AOX2XQIS Actually, with the correct functions, Unsized pages are always slower than Sized pages (especially for writing)
• [6] W26CFMAQ Improving safety of cursors
• [7] WS4ZQM4R Debugging, tests, etc.
• [8] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
• [9] 6UVFCERM Formatting, debugging, etc.
• [10] OTWDDJE7 Trait/type cleanup
• [11] UUUVNC4D Debugging/cleanup around cursors
• [12] ONES3V46 reference counting works for put
• [13] EYNN7RLS Tests++ (including UUID)
• [14] QEUTVAZ4 Splitting btree::page
• [15] 7WJNSPEW Using the same definition of the "occupied" field uniform everywhere
• [16] OP6SVMOD Resetting history
• [17] H3FVSQIQ Unsized pages
• [18] 6DCQHIFP Minor changes after benchmarking
• [19] OFINGD26 implementing prev() on cursors (+ some cleanup)
• [20] KX3WVNZW Testing/debugging "rebalance causes split of the root"
• [*] UAQX27N4 Tests

Change contents

• replacement in sanakirja-core/src/btree/page_unsized.rs at line 68
  [3.3738]→[3.3738:3758](∅→∅)
  − c: &Cursor,
  [3.3738]

  [3.3758]
  + c: &PageCursor,
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 135
  [3.1267]→[3.1267:1287](∅→∅)
  − c: &Cursor,
  [3.1267]

  [3.1287]
  + c: &PageCursor,
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 241
  [3.10222]→[3.1162:1214](∅→∅)
  − let rc = Cursor::new(m.other.as_page(), 0);
  [3.10222]

  [3.10286]
  + let rc = PageCursor::new(m.other.as_page(), 0);
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 292
  [3.1334]→[3.11864:11890](∅→∅),[3.11864]→[3.11864:11890](∅→∅)
  − type Cursor = Cursor;
  [3.1334]

  [3.1335]
  + type Cursor = PageCursor;
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 294
  [3.1390]→[3.1390:1417](∅→∅)
  − Cursor::new(p, -1)
  [3.1390]

  [3.12093]
  + PageCursor::new(p, -1)
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 297
  [3.1472]→[3.1472:1497](∅→∅)
  − Cursor::after(p)
  [3.1472]

  [3.12329]
  + PageCursor::after(p)
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 389
  [3.15139]→[3.15139:15163](∅→∅)
  − c: &mut Cursor,
  [3.15139]

  [3.15163]
  + c: &mut PageCursor,
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 427
  [3.16379]→[3.16379:16400](∅→∅)
  − Cursor {
  [3.16379]

  [3.16400]
  + PageCursor {
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 440
  [3.16651]→[3.16651:16671](∅→∅)
  − c: &mut Cursor,
  [3.16651]

  [3.16671]
  + c: &mut PageCursor,
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 503
  [3.18897]→[3.18897:18917](∅→∅)
  − pub struct Cursor {
  [3.18897]

  [3.3377]
  + pub struct PageCursor {
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 509
  [3.3475]→[3.3475:3554](∅→∅)
  − impl Cursor {

  − pub(in super) fn new(p: crate::Page, cur: isize) -> Cursor {
  [3.3475]

  [3.3554]
  + impl PageCursor {

  + pub(in super) fn new(p: crate::Page, cur: isize) -> Self {
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 513
  [3.3624]→[3.3624:3641](∅→∅)
  − Cursor {
  [3.3624]

  [3.3641]
  + PageCursor {
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 519
  [3.3747]→[3.3747:3802](∅→∅)
  − pub(in super) fn after(p: crate::Page) -> Cursor {
  [3.3747]

  [3.3802]
  + pub(in super) fn after(p: crate::Page) -> Self {
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 522
  [3.3860]→[3.3860:3877](∅→∅)
  − Cursor {
  [3.3860]

  [3.3877]
  + PageCursor {
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 528
  [3.3997]→[3.3997:4051](∅→∅)
  − pub(in super) fn last(p: crate::Page) -> Cursor {
  [3.3997]

  [3.4051]
  + pub(in super) fn last(p: crate::Page) -> Self {
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 531
  [3.4109]→[3.4109:4126](∅→∅)
  − Cursor {
  [3.4109]

  [3.4126]
  + PageCursor {
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 590
  [3.20399]→[3.4253:4309](∅→∅)
  − let mut rc = Cursor::new(m.other.as_page(), 0);
  [3.20399]

  [3.20467]
  + let mut rc = PageCursor::new(m.other.as_page(), 0);
• replacement in sanakirja-core/src/btree/page_unsized.rs at line 597
  [3.20764]→[3.4310:4366](∅→∅)
  − let mut rc = Cursor::new(m.other.as_page(), 0);
  [3.20764]

  [3.20832]
  + let mut rc = PageCursor::new(m.other.as_page(), 0);
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 18
  [3.23324]→[3.4415:4470](∅→∅)
  − let rc = super::Cursor::new(m.other.as_page(), 0);
  [3.23324]

  [3.23384]
  + let rc = super::PageCursor::new(m.other.as_page(), 0);
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 51
  [3.24242]→[3.4553:4608](∅→∅)
  − let lc = Cursor::after(m.modified.page.as_page());
  [3.24242]

  [3.656]
  + let lc = PageCursor::after(m.modified.page.as_page());
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 101
  [3.25320]→[3.4609:4662](∅→∅)
  − let lc = super::Cursor::last(m.other.as_page());
  [3.25320]

  [3.4662]
  + let lc = super::PageCursor::last(m.other.as_page());
• replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 105
  [3.25516]→[3.4747:4810](∅→∅)
  − let rc = super::Cursor::new(m.modified.page.as_page(), 0);
  [3.25516]

  [3.25584]
  + let rc = super::PageCursor::new(m.modified.page.as_page(), 0);
• replacement in sanakirja-core/src/btree/page.rs at line 12
  [3.94]→[3.4811:4848](∅→∅)
  − pub use super::page_unsized::Cursor;
  [3.94]

  [3.94]
  + pub use super::page_unsized::PageCursor;
• replacement in sanakirja-core/src/btree/page.rs at line 86
  [3.11010]→[3.11010:11030](∅→∅)
  − c: &Cursor,
  [3.11010]

  [3.11030]
  + c: &PageCursor,
• replacement in sanakirja-core/src/btree/page.rs at line 152
  [3.5238]→[3.5238:5258](∅→∅)
  − c: &Cursor,
  [3.5238]

  [3.5258]
  + c: &PageCursor,
• replacement in sanakirja-core/src/btree/page.rs at line 256
  [3.17328]→[3.5635:5687](∅→∅)
  − let rc = Cursor::new(m.other.as_page(), 0);
  [3.17328]

  [3.5843]
  + let rc = PageCursor::new(m.other.as_page(), 0);
• replacement in sanakirja-core/src/btree/page.rs at line 307
  [3.18825]→[3.18825:18851](∅→∅)
  − type Cursor = Cursor;
  [3.18825]

  [3.5807]
  + type Cursor = PageCursor;
• replacement in sanakirja-core/src/btree/page.rs at line 309
  [3.5862]→[3.5862:5889](∅→∅)
  − Cursor::new(p, -1)
  [3.5862]

  [3.19108]
  + PageCursor::new(p, -1)
• replacement in sanakirja-core/src/btree/page.rs at line 312
  [3.5944]→[3.5944:5969](∅→∅)
  − Cursor::after(p)
  [3.5944]

  [3.19402]
  + PageCursor::after(p)
• replacement in sanakirja-core/src/btree/page.rs at line 413
  [3.9008]→[3.22221:22245](∅→∅),[3.22221]→[3.22221:22245](∅→∅)
  − c: &mut Cursor,
  [3.9008]

  [3.22245]
  + c: &mut PageCursor,
• replacement in sanakirja-core/src/btree/page.rs at line 452
  [3.25720]→[3.25720:25741](∅→∅)
  − Cursor {
  [3.25720]

  [3.25741]
  + PageCursor {
• replacement in sanakirja-core/src/btree/page.rs at line 481
  [3.9644]→[3.9644:9664](∅→∅)
  − c: &mut Cursor,
  [3.9644]

  [3.9664]
  + c: &mut PageCursor,
• replacement in sanakirja-core/src/btree/page.rs at line 583
  [3.6207]→[3.7864:7920](∅→∅)
  − let mut rc = Cursor::new(m.other.as_page(), 0);
  [3.6207]

  [3.20657]
  + let mut rc = PageCursor::new(m.other.as_page(), 0);
• replacement in sanakirja-core/src/btree/page.rs at line 590
  [3.36081]→[3.7921:7977](∅→∅)
  − let mut rc = Cursor::new(m.other.as_page(), 0);
  [3.36081]

  [3.21005]
  + let mut rc = PageCursor::new(m.other.as_page(), 0);
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 17
  [3.823]→[3.7978:8033](∅→∅)
  − let rc = super::Cursor::new(m.other.as_page(), 0);
  [3.823]

  [3.883]
  + let rc = super::PageCursor::new(m.other.as_page(), 0);
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 50
  [3.1736]→[3.8116:8171](∅→∅)
  − let lc = Cursor::after(m.modified.page.as_page());
  [3.1736]

  [3.2392]
  + let lc = PageCursor::after(m.modified.page.as_page());
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 131
  [3.4231]→[3.8172:8218](∅→∅)
  − let lc = Cursor::last(m.other.as_page());
  [3.4231]

  [3.8218]
  + let lc = PageCursor::last(m.other.as_page());
• replacement in sanakirja-core/src/btree/page/rebalance.rs at line 135
  [3.4422]→[3.8303:8366](∅→∅)
  − let rc = super::Cursor::new(m.modified.page.as_page(), 0);
  [3.4422]

  [3.4490]
  + let rc = super::PageCursor::new(m.modified.page.as_page(), 0);
• edit in sanakirja-core/src/btree/mod.rs at line 3
  [3.45766]

  [3.45766]
  + pub use cursor::{Cursor, iter, rev_iter, Iter, RevIter};
• edit in sanakirja-core/src/btree/cursor.rs at line 6
  [3.63767]→[3.63767:63782](∅→∅)
  − #[doc(hidden)]
• replacement in sanakirja-core/src/btree/cursor.rs at line 7
  [3.63799]→[3.10646:10744](∅→∅)
  − pub struct PageCursor<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>> {
  [3.63799]

  [3.33799]
  + pub(in super) struct PageCursor<K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>> {
• edit in sanakirja-core/src/btree/cursor.rs at line 46
  [3.2674]→[3.2674:3300](∅→∅)
  − }

  −

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

  − }
• replacement in sanakirja-core/src/btree/cursor.rs at line 63
  [3.3431]→[3.3431:3484](∅→∅)
  − pub fn push(&mut self, p: PageCursor<K, V, P>) {
  [3.3431]

  [3.3484]
  + pub(in super) fn push(&mut self, p: PageCursor<K, V, P>) {
• replacement in sanakirja-core/src/btree/cursor.rs at line 68
  [3.3568]→[3.3568:3625](∅→∅)
  − pub fn last(&mut self) -> &mut PageCursor<K, V, P> {
  [3.3568]

  [3.3625]
  + pub(in super) fn last(&mut self) -> &mut PageCursor<K, V, P> {
• replacement in sanakirja-core/src/btree/cursor.rs at line 74
  [3.11210]→[3.24955:25007](∅→∅),[3.65766]→[3.24955:25007](∅→∅)
  − pub fn current(&self) -> &PageCursor<K, V, P> {
  [3.11210]

  [3.65821]
  + pub(in super) fn current(&self) -> &PageCursor<K, V, P> {
• replacement in sanakirja-core/src/btree/cursor.rs at line 78
  [3.65883]→[3.3695:3732](∅→∅)
  − pub fn pointer(&self) -> usize {
  [3.65883]

  [3.3732]
  + pub(in super) fn pointer(&self) -> usize {
• replacement in sanakirja-core/src/btree/cursor.rs at line 82
  [3.3760]→[3.3760:3788](∅→∅)
  − pub fn pop(&mut self) {
  [3.3760]

  [3.672]
  + pub(in super) fn pop(&mut self) {
• replacement in sanakirja-core/src/btree/cursor.rs at line 87
  [3.3821]→[3.25008:25072](∅→∅),[3.65883]→[3.25008:25072](∅→∅)
  − pub fn current_mut(&mut self) -> &mut PageCursor<K, V, P> {
  [3.3821]

  [3.33974]
  + pub(in super) fn current_mut(&mut self) -> &mut PageCursor<K, V, P> {
• edit in sanakirja-core/src/btree/cursor.rs at line 107
  [3.66515]→[3.11057:11101](∅→∅),[3.11101]→[3.34164:34236](∅→∅),[3.66557]→[3.34164:34236](∅→∅),[3.34236]→[3.11102:11118](∅→∅)
  − /*if current.cursor.is_none() {

  − current.cursor = Some(P::first_cursor(page.as_page()));

  − }*/
• edit in sanakirja-core/src/btree/cursor.rs at line 177
  [3.3619]

  [3.11964]
  +

  + // Cursor invariant: the lower levels (in the tree, upper levels

  + // on the stack) are the left children of the cursor's position on

  + // a page.

  +
• replacement in sanakirja-core/src/btree/cursor.rs at line 189
  [2.84]→[3.12287:12354](∅→∅),[3.12287]→[3.12287:12354](∅→∅)
  − // Then visit the right child (if any), i.e. push.
  [2.84]

  [3.12354]
  + P::move_next(current.page.as_page(), &mut current.cursor);

  + // Then visit the left child of the page (if any), i.e. push.
• edit in sanakirja-core/src/btree/cursor.rs at line 197
  [3.12600]→[2.85:189](∅→∅)
  − } else {

  − P::move_next(current.page.as_page(), &mut current.cursor);
• edit in sanakirja-core/src/btree/cursor.rs at line 199
  [3.12721]

  [3.12796]
  + P::move_next(current.page.as_page(), &mut current.cursor);
• edit in sanakirja-core/src/btree/cursor.rs at line 206
  [3.13035]→[2.190:294](∅→∅)
  − } else {

  − P::move_next(current.page.as_page(), &mut current.cursor);
• edit in sanakirja-core/src/btree/cursor.rs at line 210
  [3.13146]→[2.295:456](∅→∅)
  − let current = unsafe { &mut *self.stack[self.pointer].as_mut_ptr() };

  − P::move_next(current.page.as_page(), &mut current.cursor);
• replacement in sanakirja-core/src/btree/cursor.rs at line 223
  [2.614]→[3.13473:13719](∅→∅),[3.13473]→[3.13473:13719](∅→∅)
  − P::move_prev(current.page.as_page(), &mut current.cursor);

  − let right = P::right_child(current.page.as_page(), &current.cursor);

  − if right != 0 {

  − let page = txn.load_page(right)?;
  [2.614]

  [3.1360]
  + let left = P::left_child(current.page.as_page(), &current.cursor);

  + if left != 0 {

  + let page = txn.load_page(left)?;
• edit in sanakirja-core/src/btree/cursor.rs at line 230
  [3.13838]

  [3.13838]
  + } else {

  + P::move_prev(current.page.as_page(), &mut current.cursor);
• replacement in sanakirja-core/src/btree/cursor.rs at line 235
  [2.668]→[3.13959:14115](∅→∅),[3.13959]→[3.13959:14115](∅→∅)
  − P::move_prev(current.page.as_page(), &mut current.cursor);

  − let l = P::right_child(current.page.as_page(), &current.cursor);
  [2.668]

  [3.14115]
  + let l = P::left_child(current.page.as_page(), &current.cursor);
• edit in sanakirja-core/src/btree/cursor.rs at line 242
  [3.1289]

  [3.70713]
  + } else {

  + P::move_prev(current.page.as_page(), &mut current.cursor);
• edit in sanakirja-core/src/btree/cursor.rs at line 249
  [3.14441]

  [3.14441]
  + let current = unsafe { &mut *self.stack[self.pointer].as_mut_ptr() };

  + P::move_prev(current.page.as_page(), &mut current.cursor);
• edit in sanakirja-core/src/btree/cursor.rs at line 256
  [3.70761]

  [3.14496]
  + }
• edit in sanakirja-core/src/btree/cursor.rs at line 258
  [3.14497]

  [3.14497]
  + pub struct Iter<'a, T: LoadPage, K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>> {

  + txn: &'a T,

  + cursor: Cursor<K, V, P>,

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

  [3.70761]
  + pub fn iter<'a, T, K, V, P>(

  + txn: &'a T,

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

  + origin: Option<(&K, Option<&V>)>

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

  + where T: LoadPage, K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V> {

  + let mut cursor = Cursor::new(txn, db)?;

  + cursor.set(txn, origin)?;

  + Ok(Iter {

  + cursor,

  + txn,

  + })
• edit in sanakirja-core/src/btree/cursor.rs at line 276
  [3.70763]
  +

  + impl<'a, T: LoadPage, K: Representable + ?Sized + 'a, V: Representable + ?Sized + 'a, P: BTreePage<K, V> + 'a> Iterator for Iter<'a, T, K, V, P> {

  + type Item = Result<(&'a K, &'a V), T::Error>;

  + fn next(&mut self) -> Option<Self::Item> {

  + self.cursor.next(self.txn).transpose()

  + }

  + }

  +

  + pub struct RevIter<'a, T: LoadPage, K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>> {

  + txn: &'a T,

  + cursor: Cursor<K, V, P>,

  + }

  +

  + pub fn rev_iter<'a, T, K, V, P>(

  + txn: &'a T,

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

  + origin: Option<(&K, Option<&V>)>

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

  + where T: LoadPage, K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V> {

  + let mut cursor = Cursor::new(txn, db)?;

  + cursor.set(txn, origin)?;

  + Ok(RevIter {

  + cursor,

  + txn,

  + })

  + }

  +

  + impl<'a, T: LoadPage, K: Representable + ?Sized + 'a, V: Representable + ?Sized + 'a, P: BTreePage<K, V> + 'a> Iterator for RevIter<'a, T, K, V, P> {

  + type Item = Result<(&'a K, &'a V), T::Error>;

  + fn next(&mut self) -> Option<Self::Item> {

  + self.cursor.prev(self.txn).transpose()

  + }

  + }
• edit in sanakirja/src/tests.rs at line 756
  [2.1140]

  [2.1140]
  + crate::debug::debug(&txn, &[&db], "debug", true);
• edit in sanakirja/src/tests.rs at line 759
  [2.1219]

  [2.1219]
  + debug!("a {:?} {:?}", i, k);
• edit in sanakirja/src/tests.rs at line 762
  [2.1277]→[2.1277:1304](∅→∅)
  − debug!("{:?}", i);
• edit in sanakirja/src/tests.rs at line 763
  [3.3677]→[2.1305:1382](∅→∅)
  − crate::debug::debug(&txn, &[&db], "debug", true);

  − debug!("=======");
• replacement in sanakirja/src/tests.rs at line 765
  [2.1470]→[2.1470:1505](∅→∅)
  − debug!("{:?} {:?}", i, k);
  [2.1470]

  [2.1505]
  + debug!("b {:?} {:?}", i, k);
• edit in sanakirja/src/tests.rs at line 769
  [2.1569]→[2.1569:1592](∅→∅)
  − debug!("=======");
• edit in sanakirja/src/tests.rs at line 771
  [2.1672]

  [2.1672]
  + debug!("c {:?} {:?}", i, k);
• replacement in sanakirja/src/tests.rs at line 774
  [2.1730]→[2.1730:1757](∅→∅)
  − debug!("{:?}", i);
  [2.1730]

  [2.1757]
  + }

  + for i in (0..75).rev() {

  + let (k, v) = cursor.prev(&txn).unwrap().unwrap();

  + debug!("d {:?} {:?}", i, k);

  + assert_eq!(*k, i);

  + assert_eq!(v.0[0], i);

  + }

  + crate::debug::debug(&txn, &[&db], "debug", true);

  + let i0 = 30;

  + for (kv, n) in btree::rev_iter(&txn, &db, Some((&i0, None)))

  + .unwrap()

  + .zip((0..=i0).rev())

  + {

  + let (k, v) = kv.unwrap();

  + assert_eq!(*k, n);

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

  + }

  + let i0 = 40;

  + for (kv, n) in btree::iter(&txn, &db, Some((&i0, None))).unwrap().zip(i0..) {

  + let (k, v) = kv.unwrap();

  + assert_eq!(*k, n);

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