Auto merge of #67073 - ssomers:btree_navigation, r=cuviper

Bundle and document 6 BTreeMap navigation algorithms

- Expose a function to step through trees, without necessarily extracting the KV pair, that helps future operations like drain/retain (as demonstrated in [this drain_filter implementation](https://github.com/ssomers/rust/compare/btree_navigation_v3...ssomers:btree_drain_filter?expand=1))
- ~~Also aligns the implementation of the 2 x 3 iterators already using such navigation:~~
  - ~~Delay the moment the K,V references are plucked from the tree, for the 4 iterators on immutable and owned maps, just for symmetry. The same had to be done to the two iterators for mutable maps in #58431.~~
  - ~~Always explicitly use ptr::read to derive two handles from one handle. While the existing implementations for immutable maps (i.e. Range::next_unchecked and Range::next_back_unchecked) rely on implicit copying. There's no change in unsafe tags because these two functions were already (erroneously? prophetically?) tagged unsafe. I don't know whether they should be tagged unsafe. I guess they should be for mutable and owned maps, because you can change the map through one handle and leave the other handle invalid.~~
  - Preserve the way two handles are (temporarily) derived from one handle: implementations for immutable maps (i.e. Range::next_unchecked and Range::next_back_unchecked) rely on copying (implicitly before, explicitly now) and the others do `ptr::read`.
  - ~~I think the functions that support iterators on immutable trees (i.e. `Range::next_unchecked` and `Range::next_back_unchecked`) are erroneously tagged unsafe since you can already create multiple instances of such ranges, thus obtain multiple handles into the same tree. I did not change that but removed unsafe from the functions underneath.~~

Tested with miri in liballoc/tests/btree, except those that should_panic.

cargo benchcmp the best of 3 samples of all btree benchmarks before and after this PR:
```
name                                           old1.txt ns/iter  new2.txt ns/iter  diff ns/iter  diff %  speedup
btree::map::find_rand_100                      17                17                           0   0.00%   x 1.00
btree::map::find_rand_10_000                   57                55                          -2  -3.51%   x 1.04
btree::map::find_seq_100                       17                17                           0   0.00%   x 1.00
btree::map::find_seq_10_000                    42                39                          -3  -7.14%   x 1.08
btree::map::first_and_last_0                   14                14                           0   0.00%   x 1.00
btree::map::first_and_last_100                 36                37                           1   2.78%   x 0.97
btree::map::first_and_last_10k                 52                52                           0   0.00%   x 1.00
btree::map::insert_rand_100                    34                34                           0   0.00%   x 1.00
btree::map::insert_rand_10_000                 34                34                           0   0.00%   x 1.00
btree::map::insert_seq_100                     46                46                           0   0.00%   x 1.00
btree::map::insert_seq_10_000                  90                89                          -1  -1.11%   x 1.01
btree::map::iter_1000                          2,811             2,771                      -40  -1.42%   x 1.01
btree::map::iter_100000                        360,635           355,995                 -4,640  -1.29%   x 1.01
btree::map::iter_20                            39                42                           3   7.69%   x 0.93
btree::map::iter_mut_1000                      2,662             2,864                      202   7.59%   x 0.93
btree::map::iter_mut_100000                    336,825           346,550                  9,725   2.89%   x 0.97
btree::map::iter_mut_20                        40                43                           3   7.50%   x 0.93
btree::set::build_and_clear                    4,184             3,994                     -190  -4.54%   x 1.05
btree::set::build_and_drop                     4,151             3,976                     -175  -4.22%   x 1.04
btree::set::build_and_into_iter                4,196             4,155                      -41  -0.98%   x 1.01
btree::set::build_and_pop_all                  5,176             5,241                       65   1.26%   x 0.99
btree::set::build_and_remove_all               6,868             6,903                       35   0.51%   x 0.99
btree::set::difference_random_100_vs_100       721               691                        -30  -4.16%   x 1.04
btree::set::difference_random_100_vs_10k       2,420             2,411                       -9  -0.37%   x 1.00
btree::set::difference_random_10k_vs_100       54,726            52,215                  -2,511  -4.59%   x 1.05
btree::set::difference_random_10k_vs_10k       164,384           170,256                  5,872   3.57%   x 0.97
btree::set::difference_staggered_100_vs_100    739               709                        -30  -4.06%   x 1.04
btree::set::difference_staggered_100_vs_10k    2,320             2,265                      -55  -2.37%   x 1.02
btree::set::difference_staggered_10k_vs_10k    68,020            70,246                   2,226   3.27%   x 0.97
btree::set::intersection_100_neg_vs_100_pos    23                24                           1   4.35%   x 0.96
btree::set::intersection_100_neg_vs_10k_pos    28                29                           1   3.57%   x 0.97
btree::set::intersection_100_pos_vs_100_neg    24                24                           0   0.00%   x 1.00
btree::set::intersection_100_pos_vs_10k_neg    28                28                           0   0.00%   x 1.00
btree::set::intersection_10k_neg_vs_100_pos    27                27                           0   0.00%   x 1.00
btree::set::intersection_10k_neg_vs_10k_pos    30                29                          -1  -3.33%   x 1.03
btree::set::intersection_10k_pos_vs_100_neg    27                28                           1   3.70%   x 0.96
btree::set::intersection_10k_pos_vs_10k_neg    29                29                           0   0.00%   x 1.00
btree::set::intersection_random_100_vs_100     592               572                        -20  -3.38%   x 1.03
btree::set::intersection_random_100_vs_10k     2,271             2,269                       -2  -0.09%   x 1.00
btree::set::intersection_random_10k_vs_100     2,301             2,333                       32   1.39%   x 0.99
btree::set::intersection_random_10k_vs_10k     147,879           150,148                  2,269   1.53%   x 0.98
btree::set::intersection_staggered_100_vs_100  622               632                         10   1.61%   x 0.98
btree::set::intersection_staggered_100_vs_10k  2,101             2,032                      -69  -3.28%   x 1.03
btree::set::intersection_staggered_10k_vs_10k  60,341            61,834                   1,493   2.47%   x 0.98
btree::set::is_subset_100_vs_100               417               426                          9   2.16%   x 0.98
btree::set::is_subset_100_vs_10k               1,281             1,324                       43   3.36%   x 0.97
btree::set::is_subset_10k_vs_100               2                 2                            0   0.00%   x 1.00
btree::set::is_subset_10k_vs_10k               41,054            41,612                     558   1.36%   x 0.99
```

r? cuviper

4 files changed, 314 insertions, 236 deletions

diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs
index 399df33d2b9..8eabc177304 100644
--- a/src/liballoc/collections/btree/map.rs
+++ b/src/liballoc/collections/btree/map.rs
@@ -6,10 +6,11 @@ use core::iter::{FromIterator, FusedIterator, Peekable};
 use core::marker::PhantomData;
 use core::ops::Bound::{Excluded, Included, Unbounded};
 use core::ops::{Index, RangeBounds};
-use core::{fmt, intrinsics, mem, ptr};
+use core::{fmt, mem, ptr};
 
 use super::node::{self, marker, ForceResult::*, Handle, InsertResult::*, NodeRef};
 use super::search::{self, SearchResult::*};
+use super::unwrap_unchecked;
 
 use Entry::*;
 use UnderflowResult::*;
@@ -645,7 +646,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
         T: Ord,
         K: Borrow<T>,
     {
-        let front = first_leaf_edge(self.root.as_ref());
+        let front = self.root.as_ref().first_leaf_edge();
         front.right_kv().ok().map(Handle::into_kv)
     }
 
@@ -706,7 +707,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
         T: Ord,
         K: Borrow<T>,
     {
-        let back = last_leaf_edge(self.root.as_ref());
+        let back = self.root.as_ref().last_leaf_edge();
         back.left_kv().ok().map(Handle::into_kv)
     }
 
@@ -1073,7 +1074,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
 
     fn from_sorted_iter<I: Iterator<Item = (K, V)>>(&mut self, iter: I) {
         self.ensure_root_is_owned();
-        let mut cur_node = last_leaf_edge(self.root.as_mut()).into_node();
+        let mut cur_node = self.root.as_mut().last_leaf_edge().into_node();
         // Iterate through all key-value pairs, pushing them into nodes at the right level.
         for (key, value) in iter {
             // Try to push key-value pair into the current leaf node.
@@ -1113,7 +1114,7 @@ impl<K: Ord, V> BTreeMap<K, V> {
                 open_node.push(key, value, right_tree);
 
                 // Go down to the right-most leaf again.
-                cur_node = last_leaf_edge(open_node.forget_type()).into_node();
+                cur_node = open_node.forget_type().last_leaf_edge().into_node();
             }
 
             self.length += 1;
@@ -1411,10 +1412,8 @@ impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
             None
         } else {
             self.length -= 1;
-            unsafe {
-                let (k, v) = self.range.next_unchecked();
-                Some((k, v)) // coerce k from `&mut K` to `&K`
-            }
+            let (k, v) = unsafe { self.range.next_unchecked() };
+            Some((k, v)) // coerce k from `&mut K` to `&K`
         }
     }
 
@@ -1434,7 +1433,8 @@ impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
             None
         } else {
             self.length -= 1;
-            unsafe { Some(self.range.next_back_unchecked()) }
+            let (k, v) = unsafe { self.range.next_back_unchecked() };
+            Some((k, v)) // coerce k from `&mut K` to `&K`
         }
     }
 }
@@ -1460,7 +1460,7 @@ impl<K, V> IntoIterator for BTreeMap<K, V> {
         let len = self.length;
         mem::forget(self);
 
-        IntoIter { front: first_leaf_edge(root1), back: last_leaf_edge(root2), length: len }
+        IntoIter { front: root1.first_leaf_edge(), back: root2.last_leaf_edge(), length: len }
     }
 }
 
@@ -1475,9 +1475,9 @@ impl<K, V> Drop for IntoIter<K, V> {
             }
 
             if let Some(first_parent) = leaf_node.deallocate_and_ascend() {
-                let mut cur_node = first_parent.into_node();
-                while let Some(parent) = cur_node.deallocate_and_ascend() {
-                    cur_node = parent.into_node()
+                let mut cur_internal_node = first_parent.into_node();
+                while let Some(parent) = cur_internal_node.deallocate_and_ascend() {
+                    cur_internal_node = parent.into_node()
                 }
             }
         }
@@ -1490,37 +1490,10 @@ impl<K, V> Iterator for IntoIter<K, V> {
 
     fn next(&mut self) -> Option<(K, V)> {
         if self.length == 0 {
-            return None;
+            None
         } else {
             self.length -= 1;
-        }
-
-        let handle = unsafe { ptr::read(&self.front) };
-
-        let mut cur_handle = match handle.right_kv() {
-            Ok(kv) => {
-                let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
-                let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
-                self.front = kv.right_edge();
-                return Some((k, v));
-            }
-            Err(last_edge) => unsafe {
-                unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
-            },
-        };
-
-        loop {
-            match cur_handle.right_kv() {
-                Ok(kv) => {
-                    let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
-                    let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
-                    self.front = first_leaf_edge(kv.right_edge().descend());
-                    return Some((k, v));
-                }
-                Err(last_edge) => unsafe {
-                    cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
-                },
-            }
+            Some(unsafe { self.front.next_unchecked() })
         }
     }
 
@@ -1533,37 +1506,10 @@ impl<K, V> Iterator for IntoIter<K, V> {
 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
     fn next_back(&mut self) -> Option<(K, V)> {
         if self.length == 0 {
-            return None;
+            None
         } else {
             self.length -= 1;
-        }
-
-        let handle = unsafe { ptr::read(&self.back) };
-
-        let mut cur_handle = match handle.left_kv() {
-            Ok(kv) => {
-                let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
-                let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
-                self.back = kv.left_edge();
-                return Some((k, v));
-            }
-            Err(last_edge) => unsafe {
-                unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
-            },
-        };
-
-        loop {
-            match cur_handle.left_kv() {
-                Ok(kv) => {
-                    let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
-                    let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
-                    self.back = last_leaf_edge(kv.left_edge().descend());
-                    return Some((k, v));
-                }
-                Err(last_edge) => unsafe {
-                    cur_handle = unwrap_unchecked(last_edge.into_node().deallocate_and_ascend());
-                },
-            }
+            Some(unsafe { self.back.next_back_unchecked() })
         }
     }
 }
@@ -1665,7 +1611,7 @@ impl<'a, K, V> Iterator for Range<'a, K, V> {
     type Item = (&'a K, &'a V);
 
     fn next(&mut self) -> Option<(&'a K, &'a V)> {
-        if self.front == self.back { None } else { unsafe { Some(self.next_unchecked()) } }
+        if self.is_empty() { None } else { unsafe { Some(self.next_unchecked()) } }
     }
 
     fn last(mut self) -> Option<(&'a K, &'a V)> {
@@ -1708,73 +1654,25 @@ impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
 impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
 
 impl<'a, K, V> Range<'a, K, V> {
-    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
-        let handle = self.front;
-
-        let mut cur_handle = match handle.right_kv() {
-            Ok(kv) => {
-                let ret = kv.into_kv();
-                self.front = kv.right_edge();
-                return ret;
-            }
-            Err(last_edge) => {
-                let next_level = last_edge.into_node().ascend().ok();
-                unwrap_unchecked(next_level)
-            }
-        };
+    fn is_empty(&self) -> bool {
+        self.front == self.back
+    }
 
-        loop {
-            match cur_handle.right_kv() {
-                Ok(kv) => {
-                    let ret = kv.into_kv();
-                    self.front = first_leaf_edge(kv.right_edge().descend());
-                    return ret;
-                }
-                Err(last_edge) => {
-                    let next_level = last_edge.into_node().ascend().ok();
-                    cur_handle = unwrap_unchecked(next_level);
-                }
-            }
-        }
+    unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
+        self.front.next_unchecked()
     }
 }
 
 #[stable(feature = "btree_range", since = "1.17.0")]
 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
-        if self.front == self.back { None } else { unsafe { Some(self.next_back_unchecked()) } }
+        if self.is_empty() { None } else { Some(unsafe { self.next_back_unchecked() }) }
     }
 }
 
 impl<'a, K, V> Range<'a, K, V> {
     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
-        let handle = self.back;
-
-        let mut cur_handle = match handle.left_kv() {
-            Ok(kv) => {
-                let ret = kv.into_kv();
-                self.back = kv.left_edge();
-                return ret;
-            }
-            Err(last_edge) => {
-                let next_level = last_edge.into_node().ascend().ok();
-                unwrap_unchecked(next_level)
-            }
-        };
-
-        loop {
-            match cur_handle.left_kv() {
-                Ok(kv) => {
-                    let ret = kv.into_kv();
-                    self.back = last_leaf_edge(kv.left_edge().descend());
-                    return ret;
-                }
-                Err(last_edge) => {
-                    let next_level = last_edge.into_node().ascend().ok();
-                    cur_handle = unwrap_unchecked(next_level);
-                }
-            }
-        }
+        self.back.next_back_unchecked()
     }
 }
 
@@ -1796,10 +1694,8 @@ impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
         if self.is_empty() {
             None
         } else {
-            unsafe {
-                let (k, v) = self.next_unchecked();
-                Some((k, v)) // coerce k from `&mut K` to `&K`
-            }
+            let (k, v) = unsafe { self.next_unchecked() };
+            Some((k, v)) // coerce k from `&mut K` to `&K`
         }
     }
 
@@ -1814,42 +1710,19 @@ impl<'a, K, V> RangeMut<'a, K, V> {
     }
 
     unsafe fn next_unchecked(&mut self) -> (&'a mut K, &'a mut V) {
-        let handle = ptr::read(&self.front);
-
-        let mut cur_handle = match handle.right_kv() {
-            Ok(kv) => {
-                self.front = ptr::read(&kv).right_edge();
-                // Doing the descend invalidates the references returned by `into_kv_mut`,
-                // so we have to do this last.
-                return kv.into_kv_mut();
-            }
-            Err(last_edge) => {
-                let next_level = last_edge.into_node().ascend().ok();
-                unwrap_unchecked(next_level)
-            }
-        };
-
-        loop {
-            match cur_handle.right_kv() {
-                Ok(kv) => {
-                    self.front = first_leaf_edge(ptr::read(&kv).right_edge().descend());
-                    // Doing the descend invalidates the references returned by `into_kv_mut`,
-                    // so we have to do this last.
-                    return kv.into_kv_mut();
-                }
-                Err(last_edge) => {
-                    let next_level = last_edge.into_node().ascend().ok();
-                    cur_handle = unwrap_unchecked(next_level);
-                }
-            }
-        }
+        self.front.next_unchecked()
     }
 }
 
 #[stable(feature = "btree_range", since = "1.17.0")]
 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
-        if self.is_empty() { None } else { unsafe { Some(self.next_back_unchecked()) } }
+        if self.is_empty() {
+            None
+        } else {
+            let (k, v) = unsafe { self.next_back_unchecked() };
+            Some((k, v)) // coerce k from `&mut K` to `&K`
+        }
     }
 }
 
@@ -1857,38 +1730,8 @@ impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
 impl<K, V> FusedIterator for RangeMut<'_, K, V> {}
 
 impl<'a, K, V> RangeMut<'a, K, V> {
-    unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
-        let handle = ptr::read(&self.back);
-
-        let mut cur_handle = match handle.left_kv() {
-            Ok(kv) => {
-                self.back = ptr::read(&kv).left_edge();
-                // Doing the descend invalidates the references returned by `into_kv_mut`,
-                // so we have to do this last.
-                let (k, v) = kv.into_kv_mut();
-                return (k, v); // coerce k from `&mut K` to `&K`
-            }
-            Err(last_edge) => {
-                let next_level = last_edge.into_node().ascend().ok();
-                unwrap_unchecked(next_level)
-            }
-        };
-
-        loop {
-            match cur_handle.left_kv() {
-                Ok(kv) => {
-                    self.back = last_leaf_edge(ptr::read(&kv).left_edge().descend());
-                    // Doing the descend invalidates the references returned by `into_kv_mut`,
-                    // so we have to do this last.
-                    let (k, v) = kv.into_kv_mut();
-                    return (k, v); // coerce k from `&mut K` to `&K`
-                }
-                Err(last_edge) => {
-                    let next_level = last_edge.into_node().ascend().ok();
-                    cur_handle = unwrap_unchecked(next_level);
-                }
-            }
-        }
+    unsafe fn next_back_unchecked(&mut self) -> (&'a mut K, &'a mut V) {
+        self.back.next_back_unchecked()
     }
 }
 
@@ -1987,32 +1830,6 @@ where
     }
 }
 
-fn first_leaf_edge<BorrowType, K, V>(
-    mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
-) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
-    loop {
-        match node.force() {
-            Leaf(leaf) => return leaf.first_edge(),
-            Internal(internal) => {
-                node = internal.first_edge().descend();
-            }
-        }
-    }
-}
-
-fn last_leaf_edge<BorrowType, K, V>(
-    mut node: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
-) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
-    loop {
-        match node.force() {
-            Leaf(leaf) => return leaf.last_edge(),
-            Internal(internal) => {
-                node = internal.last_edge().descend();
-            }
-        }
-    }
-}
-
 fn range_search<BorrowType, K, V, Q: ?Sized, R: RangeBounds<Q>>(
     root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
     root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
@@ -2116,17 +1933,6 @@ where
     }
 }
 
-#[inline(always)]
-unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
-    val.unwrap_or_else(|| {
-        if cfg!(debug_assertions) {
-            panic!("'unchecked' unwrap on None in BTreeMap");
-        } else {
-            intrinsics::unreachable();
-        }
-    })
-}
-
 impl<K, V> BTreeMap<K, V> {
     /// Gets an iterator over the entries of the map, sorted by key.
     ///
@@ -2153,8 +1959,8 @@ impl<K, V> BTreeMap<K, V> {
     pub fn iter(&self) -> Iter<'_, K, V> {
         Iter {
             range: Range {
-                front: first_leaf_edge(self.root.as_ref()),
-                back: last_leaf_edge(self.root.as_ref()),
+                front: self.root.as_ref().first_leaf_edge(),
+                back: self.root.as_ref().last_leaf_edge(),
             },
             length: self.length,
         }
@@ -2187,8 +1993,8 @@ impl<K, V> BTreeMap<K, V> {
         let root2 = unsafe { ptr::read(&root1) };
         IterMut {
             range: RangeMut {
-                front: first_leaf_edge(root1),
-                back: last_leaf_edge(root2),
+                front: root1.first_leaf_edge(),
+                back: root2.last_leaf_edge(),
                 _marker: PhantomData,
             },
             length: self.length,
@@ -2691,7 +2497,7 @@ impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
                 let key_loc = internal.kv_mut().0 as *mut K;
                 let val_loc = internal.kv_mut().1 as *mut V;
 
-                let to_remove = first_leaf_edge(internal.right_edge().descend()).right_kv().ok();
+                let to_remove = internal.right_edge().descend().first_leaf_edge().right_kv().ok();
                 let to_remove = unsafe { unwrap_unchecked(to_remove) };
 
                 let (hole, key, val) = to_remove.remove();
diff --git a/src/liballoc/collections/btree/mod.rs b/src/liballoc/collections/btree/mod.rs
index f73a24d0991..fb5825ee21a 100644
--- a/src/liballoc/collections/btree/mod.rs
+++ b/src/liballoc/collections/btree/mod.rs
@@ -1,4 +1,5 @@
 pub mod map;
+mod navigate;
 mod node;
 mod search;
 pub mod set;
@@ -11,3 +12,14 @@ trait Recover<Q: ?Sized> {
     fn take(&mut self, key: &Q) -> Option<Self::Key>;
     fn replace(&mut self, key: Self::Key) -> Option<Self::Key>;
 }
+
+#[inline(always)]
+pub unsafe fn unwrap_unchecked<T>(val: Option<T>) -> T {
+    val.unwrap_or_else(|| {
+        if cfg!(debug_assertions) {
+            panic!("'unchecked' unwrap on None in BTreeMap");
+        } else {
+            core::intrinsics::unreachable();
+        }
+    })
+}
diff --git a/src/liballoc/collections/btree/navigate.rs b/src/liballoc/collections/btree/navigate.rs
new file mode 100644
index 00000000000..65321897231
--- /dev/null
+++ b/src/liballoc/collections/btree/navigate.rs
@@ -0,0 +1,244 @@
+use core::ptr;
+
+use super::node::{marker, ForceResult::*, Handle, NodeRef};
+use super::unwrap_unchecked;
+
+macro_rules! def_next {
+    { unsafe fn $name:ident : $next_kv:ident $next_edge:ident $initial_leaf_edge:ident } => {
+        /// Given a leaf edge handle into an immutable tree, returns a handle to the next
+        /// leaf edge and references to the key and value between these edges.
+        /// Unsafe because the caller must ensure that the given leaf edge has a successor.
+        unsafe fn $name <'a, K: 'a, V: 'a>(
+            leaf_edge: Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
+        ) -> (Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>, &'a K, &'a V) {
+            let mut cur_handle = match leaf_edge.$next_kv() {
+                Ok(leaf_kv) => {
+                    let (k, v) = leaf_kv.into_kv();
+                    let next_leaf_edge = leaf_kv.$next_edge();
+                    return (next_leaf_edge, k, v);
+                }
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    unwrap_unchecked(next_level)
+                }
+            };
+
+            loop {
+                cur_handle = match cur_handle.$next_kv() {
+                    Ok(internal_kv) => {
+                        let (k, v) = internal_kv.into_kv();
+                        let next_internal_edge = internal_kv.$next_edge();
+                        let next_leaf_edge = next_internal_edge.descend().$initial_leaf_edge();
+                        return (next_leaf_edge, k, v);
+                    }
+                    Err(last_edge) => {
+                        let next_level = last_edge.into_node().ascend().ok();
+                        unwrap_unchecked(next_level)
+                    }
+                }
+            }
+        }
+    };
+}
+
+macro_rules! def_next_mut {
+    { unsafe fn $name:ident : $next_kv:ident $next_edge:ident $initial_leaf_edge:ident } => {
+        /// Given a leaf edge handle into a mutable tree, returns handles to the next
+        /// leaf edge and to the KV between these edges.
+        /// Unsafe for two reasons:
+        /// - the caller must ensure that the given leaf edge has a successor;
+        /// - both returned handles represent mutable references into the same tree
+        ///   that can easily invalidate each other, even on immutable use.
+        unsafe fn $name <'a, K: 'a, V: 'a>(
+            leaf_edge: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+        ) -> (Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
+              Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>) {
+            let mut cur_handle = match leaf_edge.$next_kv() {
+                Ok(leaf_kv) => {
+                    let next_leaf_edge = ptr::read(&leaf_kv).$next_edge();
+                    return (next_leaf_edge, leaf_kv.forget_node_type());
+                }
+                Err(last_edge) => {
+                    let next_level = last_edge.into_node().ascend().ok();
+                    unwrap_unchecked(next_level)
+                }
+            };
+
+            loop {
+                cur_handle = match cur_handle.$next_kv() {
+                    Ok(internal_kv) => {
+                        let next_internal_edge = ptr::read(&internal_kv).$next_edge();
+                        let next_leaf_edge = next_internal_edge.descend().$initial_leaf_edge();
+                        return (next_leaf_edge, internal_kv.forget_node_type());
+                    }
+                    Err(last_edge) => {
+                        let next_level = last_edge.into_node().ascend().ok();
+                        unwrap_unchecked(next_level)
+                    }
+                }
+            }
+        }
+    };
+}
+
+macro_rules! def_next_dealloc {
+    { unsafe fn $name:ident : $next_kv:ident $next_edge:ident $initial_leaf_edge:ident } => {
+        /// Given a leaf edge handle into an owned tree, returns a handle to the next
+        /// leaf edge and the key and value between these edges, while deallocating
+        /// any node left behind.
+        /// Unsafe for two reasons:
+        /// - the caller must ensure that the given leaf edge has a successor;
+        /// - the node pointed at by the given handle, and its ancestors, may be deallocated,
+        ///   while the reference to those nodes in the surviving ancestors is left dangling;
+        ///   thus using the returned handle is dangerous.
+        unsafe fn $name <K, V>(
+            leaf_edge: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
+        ) -> (Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>, K, V) {
+            let mut cur_handle = match leaf_edge.$next_kv() {
+                Ok(leaf_kv) => {
+                    let k = ptr::read(leaf_kv.reborrow().into_kv().0);
+                    let v = ptr::read(leaf_kv.reborrow().into_kv().1);
+                    let next_leaf_edge = leaf_kv.$next_edge();
+                    return (next_leaf_edge, k, v);
+                }
+                Err(last_edge) => {
+                    unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
+                }
+            };
+
+            loop {
+                cur_handle = match cur_handle.$next_kv() {
+                    Ok(internal_kv) => {
+                        let k = ptr::read(internal_kv.reborrow().into_kv().0);
+                        let v = ptr::read(internal_kv.reborrow().into_kv().1);
+                        let next_internal_edge = internal_kv.$next_edge();
+                        let next_leaf_edge = next_internal_edge.descend().$initial_leaf_edge();
+                        return (next_leaf_edge, k, v);
+                    }
+                    Err(last_edge) => {
+                        unwrap_unchecked(last_edge.into_node().deallocate_and_ascend())
+                    }
+                }
+            }
+        }
+    };
+}
+
+def_next! {unsafe fn next_unchecked: right_kv right_edge first_leaf_edge}
+def_next! {unsafe fn next_back_unchecked: left_kv left_edge last_leaf_edge}
+def_next_mut! {unsafe fn next_unchecked_mut: right_kv right_edge first_leaf_edge}
+def_next_mut! {unsafe fn next_back_unchecked_mut: left_kv left_edge last_leaf_edge}
+def_next_dealloc! {unsafe fn next_unchecked_deallocating: right_kv right_edge first_leaf_edge}
+def_next_dealloc! {unsafe fn next_back_unchecked_deallocating: left_kv left_edge last_leaf_edge}
+
+impl<'a, K, V> Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge> {
+    /// Moves the leaf edge handle to the next leaf edge and returns references to the
+    /// key and value in between.
+    /// Unsafe because the caller must ensure that the leaf edge is not the last one in the tree.
+    pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
+        let (next_edge, k, v) = next_unchecked(*self);
+        *self = next_edge;
+        (k, v)
+    }
+
+    /// Moves the leaf edge handle to the previous leaf edge and returns references to the
+    /// key and value in between.
+    /// Unsafe because the caller must ensure that the leaf edge is not the first one in the tree.
+    pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
+        let (next_edge, k, v) = next_back_unchecked(*self);
+        *self = next_edge;
+        (k, v)
+    }
+}
+
+impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
+    /// Moves the leaf edge handle to the next leaf edge and returns references to the
+    /// key and value in between.
+    /// Unsafe for two reasons:
+    /// - The caller must ensure that the leaf edge is not the last one in the tree.
+    /// - Using the updated handle may well invalidate the returned references.
+    pub unsafe fn next_unchecked(&mut self) -> (&'a mut K, &'a mut V) {
+        let (next_edge, kv) = next_unchecked_mut(ptr::read(self));
+        *self = next_edge;
+        // Doing the descend (and perhaps another move) invalidates the references
+        // returned by `into_kv_mut`, so we have to do this last.
+        kv.into_kv_mut()
+    }
+
+    /// Moves the leaf edge handle to the previous leaf and returns references to the
+    /// key and value in between.
+    /// Unsafe for two reasons:
+    /// - The caller must ensure that the leaf edge is not the first one in the tree.
+    /// - Using the updated handle may well invalidate the returned references.
+    pub unsafe fn next_back_unchecked(&mut self) -> (&'a mut K, &'a mut V) {
+        let (next_edge, kv) = next_back_unchecked_mut(ptr::read(self));
+        *self = next_edge;
+        // Doing the descend (and perhaps another move) invalidates the references
+        // returned by `into_kv_mut`, so we have to do this last.
+        kv.into_kv_mut()
+    }
+}
+
+impl<K, V> Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge> {
+    /// Moves the leaf edge handle to the next leaf edge and returns the key and value
+    /// in between, while deallocating any node left behind.
+    /// Unsafe for three reasons:
+    /// - The caller must ensure that the leaf edge is not the last one in the tree
+    ///   and is not a handle previously resulting from counterpart `next_back_unchecked`.
+    /// - If the leaf edge is the last edge of a node, that node and possibly ancestors
+    ///   will be deallocated, while the reference to those nodes in the surviving ancestor
+    ///   is left dangling; thus further use of the leaf edge handle is dangerous.
+    ///   It is, however, safe to call this method again on the updated handle.
+    ///   if the two preconditions above hold.
+    /// - Using the updated handle may well invalidate the returned references.
+    pub unsafe fn next_unchecked(&mut self) -> (K, V) {
+        let (next_edge, k, v) = next_unchecked_deallocating(ptr::read(self));
+        *self = next_edge;
+        (k, v)
+    }
+
+    /// Moves the leaf edge handle to the previous leaf edge and returns the key
+    /// and value in between, while deallocating any node left behind.
+    /// Unsafe for three reasons:
+    /// - The caller must ensure that the leaf edge is not the first one in the tree
+    ///   and is not a handle previously resulting from counterpart `next_unchecked`.
+    /// - If the lead edge is the first edge of a node, that node and possibly ancestors
+    ///   will be deallocated, while the reference to those nodes in the surviving ancestor
+    ///   is left dangling; thus further use of the leaf edge handle is dangerous.
+    ///   It is, however, safe to call this method again on the updated handle.
+    ///   if the two preconditions above hold.
+    /// - Using the updated handle may well invalidate the returned references.
+    pub unsafe fn next_back_unchecked(&mut self) -> (K, V) {
+        let (next_edge, k, v) = next_back_unchecked_deallocating(ptr::read(self));
+        *self = next_edge;
+        (k, v)
+    }
+}
+
+impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+    /// Returns the leftmost leaf edge in or underneath a node - in other words, the edge
+    /// you need first when navigating forward (or last when navigating backward).
+    #[inline]
+    pub fn first_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+        let mut node = self;
+        loop {
+            match node.force() {
+                Leaf(leaf) => return leaf.first_edge(),
+                Internal(internal) => node = internal.first_edge().descend(),
+            }
+        }
+    }
+
+    /// Returns the rightmost leaf edge in or underneath a node - in other words, the edge
+    /// you need last when navigating forward (or first when navigating backward).
+    #[inline]
+    pub fn last_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+        let mut node = self;
+        loop {
+            match node.force() {
+                Leaf(leaf) => return leaf.last_edge(),
+                Internal(internal) => node = internal.last_edge().descend(),
+            }
+        }
+    }
+}
diff --git a/src/liballoc/collections/btree/node.rs b/src/liballoc/collections/btree/node.rs
index d85a263b5d5..e4123c9a20b 100644
--- a/src/liballoc/collections/btree/node.rs
+++ b/src/liballoc/collections/btree/node.rs
@@ -1418,6 +1418,22 @@ unsafe fn move_edges<K, V>(
     dest.correct_childrens_parent_links(dest_offset, dest_offset + count);
 }
 
+impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::KV> {
+    pub fn forget_node_type(
+        self,
+    ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
+        unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
+    }
+}
+
+impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV> {
+    pub fn forget_node_type(
+        self,
+    ) -> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
+        unsafe { Handle::new_kv(self.node.forget_type(), self.idx) }
+    }
+}
+
 impl<BorrowType, K, V, HandleType>
     Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, HandleType>
 {