library/alloc/src/collections/btree/navigate.rs

   1 use core::intrinsics;
   2 use core::mem;
   3 use core::ptr;
   4
   5 use super::node::{marker, ForceResult::*, Handle, NodeRef};
   6 use super::unwrap_unchecked;
   7
   8 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
   9     /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
  10     /// on the right side, which is either in the same leaf node or in an ancestor node.
  11     /// If the leaf edge is the last one in the tree, returns [`Result::Err`] with the root node.
  12     pub fn next_kv(
  13         self,
  14     ) -> Result<
  15         Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
  16         NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
  17     > {
  18         let mut edge = self.forget_node_type();
  19         loop {
  20             edge = match edge.right_kv() {
  21                 Ok(internal_kv) => return Ok(internal_kv),
  22                 Err(last_edge) => match last_edge.into_node().ascend() {
  23                     Ok(parent_edge) => parent_edge.forget_node_type(),
  24                     Err(root) => return Err(root),
  25                 },
  26             }
  27         }
  28     }
  29
  30     /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
  31     /// on the left side, which is either in the same leaf node or in an ancestor node.
  32     /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node.
  33     pub fn next_back_kv(
  34         self,
  35     ) -> Result<
  36         Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
  37         NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
  38     > {
  39         let mut edge = self.forget_node_type();
  40         loop {
  41             edge = match edge.left_kv() {
  42                 Ok(internal_kv) => return Ok(internal_kv),
  43                 Err(last_edge) => match last_edge.into_node().ascend() {
  44                     Ok(parent_edge) => parent_edge.forget_node_type(),
  45                     Err(root) => return Err(root),
  46                 },
  47             }
  48         }
  49     }
  50 }
  51
  52 macro_rules! def_next_kv_uncheched_dealloc {
  53     { unsafe fn $name:ident : $adjacent_kv:ident } => {
  54         /// Given a leaf edge handle into an owned tree, returns a handle to the next KV,
  55         /// while deallocating any node left behind.
  56         /// Unsafe for two reasons:
  57         /// - The caller must ensure that the leaf edge is not the last one in the tree.
  58         /// - The node pointed at by the given handle, and its ancestors, may be deallocated,
  59         ///   while the reference to those nodes in the surviving ancestors is left dangling;
  60         ///   thus using the returned handle to navigate further is dangerous.
  61         unsafe fn $name <K, V>(
  62             leaf_edge: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
  63         ) -> Handle<NodeRef<marker::Owned, K, V, marker::LeafOrInternal>, marker::KV> {
  64             let mut edge = leaf_edge.forget_node_type();
  65             loop {
  66                 edge = match edge.$adjacent_kv() {
  67                     Ok(internal_kv) => return internal_kv,
  68                     Err(last_edge) => {
  69                         unsafe {
  70                             let parent_edge = last_edge.into_node().deallocate_and_ascend();
  71                             unwrap_unchecked(parent_edge).forget_node_type()
  72                         }
  73                     }
  74                 }
  75             }
  76         }
  77     };
  78 }
  79
  80 def_next_kv_uncheched_dealloc! {unsafe fn next_kv_unchecked_dealloc: right_kv}
  81 def_next_kv_uncheched_dealloc! {unsafe fn next_back_kv_unchecked_dealloc: left_kv}
  82
  83 /// This replaces the value behind the `v` unique reference by calling the
  84 /// relevant function, and returns a result obtained along the way.
  85 ///
  86 /// If a panic occurs in the `change` closure, the entire process will be aborted.
  87 #[inline]
  88 fn replace<T, R>(v: &mut T, change: impl FnOnce(T) -> (T, R)) -> R {
  89     struct PanicGuard;
  90     impl Drop for PanicGuard {
  91         fn drop(&mut self) {
  92             intrinsics::abort()
  93         }
  94     }
  95     let guard = PanicGuard;
  96     let value = unsafe { ptr::read(v) };
  97     let (new_value, ret) = change(value);
  98     unsafe {
  99         ptr::write(v, new_value);
 100     }
 101     mem::forget(guard);
 102     ret
 103 }
 104
 105 impl<'a, K, V> Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge> {
 106     /// Moves the leaf edge handle to the next leaf edge and returns references to the
 107     /// key and value in between.
 108     /// Unsafe because the caller must ensure that the leaf edge is not the last one in the tree.
 109     pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
 110         replace(self, |leaf_edge| {
 111             let kv = leaf_edge.next_kv();
 112             let kv = unsafe { unwrap_unchecked(kv.ok()) };
 113             (kv.next_leaf_edge(), kv.into_kv())
 114         })
 115     }
 116
 117     /// Moves the leaf edge handle to the previous leaf edge and returns references to the
 118     /// key and value in between.
 119     /// Unsafe because the caller must ensure that the leaf edge is not the first one in the tree.
 120     pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
 121         replace(self, |leaf_edge| {
 122             let kv = leaf_edge.next_back_kv();
 123             let kv = unsafe { unwrap_unchecked(kv.ok()) };
 124             (kv.next_back_leaf_edge(), kv.into_kv())
 125         })
 126     }
 127 }
 128
 129 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
 130     /// Moves the leaf edge handle to the next leaf edge and returns references to the
 131     /// key and value in between.
 132     /// Unsafe for two reasons:
 133     /// - The caller must ensure that the leaf edge is not the last one in the tree.
 134     /// - Using the updated handle may well invalidate the returned references.
 135     pub unsafe fn next_unchecked(&mut self) -> (&'a mut K, &'a mut V) {
 136         let kv = replace(self, |leaf_edge| {
 137             let kv = leaf_edge.next_kv();
 138             let kv = unsafe { unwrap_unchecked(kv.ok()) };
 139             (unsafe { ptr::read(&kv) }.next_leaf_edge(), kv)
 140         });
 141         // Doing the descend (and perhaps another move) invalidates the references
 142         // returned by `into_kv_mut`, so we have to do this last.
 143         kv.into_kv_mut()
 144     }
 145
 146     /// Moves the leaf edge handle to the previous leaf and returns references to the
 147     /// key and value in between.
 148     /// Unsafe for two reasons:
 149     /// - The caller must ensure that the leaf edge is not the first one in the tree.
 150     /// - Using the updated handle may well invalidate the returned references.
 151     pub unsafe fn next_back_unchecked(&mut self) -> (&'a mut K, &'a mut V) {
 152         let kv = replace(self, |leaf_edge| {
 153             let kv = leaf_edge.next_back_kv();
 154             let kv = unsafe { unwrap_unchecked(kv.ok()) };
 155             (unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv)
 156         });
 157         // Doing the descend (and perhaps another move) invalidates the references
 158         // returned by `into_kv_mut`, so we have to do this last.
 159         kv.into_kv_mut()
 160     }
 161 }
 162
 163 impl<K, V> Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge> {
 164     /// Moves the leaf edge handle to the next leaf edge and returns the key and value
 165     /// in between, while deallocating any node left behind.
 166     /// Unsafe for two reasons:
 167     /// - The caller must ensure that the leaf edge is not the last one in the tree
 168     ///   and is not a handle previously resulting from counterpart `next_back_unchecked`.
 169     /// - Further use of the updated leaf edge handle is very dangerous. In particular,
 170     ///   if the leaf edge is the last edge of a node, that node and possibly ancestors
 171     ///   will be deallocated, while the reference to those nodes in the surviving ancestor
 172     ///   is left dangling.
 173     ///   The only safe way to proceed with the updated handle is to compare it, drop it,
 174     ///   call this method again subject to both preconditions listed in the first point,
 175     ///   or call counterpart `next_back_unchecked` subject to its preconditions.
 176     pub unsafe fn next_unchecked(&mut self) -> (K, V) {
 177         replace(self, |leaf_edge| {
 178             let kv = unsafe { next_kv_unchecked_dealloc(leaf_edge) };
 179             let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
 180             let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
 181             (kv.next_leaf_edge(), (k, v))
 182         })
 183     }
 184
 185     /// Moves the leaf edge handle to the previous leaf edge and returns the key
 186     /// and value in between, while deallocating any node left behind.
 187     /// Unsafe for two reasons:
 188     /// - The caller must ensure that the leaf edge is not the first one in the tree
 189     ///   and is not a handle previously resulting from counterpart `next_unchecked`.
 190     /// - Further use of the updated leaf edge handle is very dangerous. In particular,
 191     ///   if the leaf edge is the first edge of a node, that node and possibly ancestors
 192     ///   will be deallocated, while the reference to those nodes in the surviving ancestor
 193     ///   is left dangling.
 194     ///   The only safe way to proceed with the updated handle is to compare it, drop it,
 195     ///   call this method again subject to both preconditions listed in the first point,
 196     ///   or call counterpart `next_unchecked` subject to its preconditions.
 197     pub unsafe fn next_back_unchecked(&mut self) -> (K, V) {
 198         replace(self, |leaf_edge| {
 199             let kv = unsafe { next_back_kv_unchecked_dealloc(leaf_edge) };
 200             let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
 201             let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
 202             (kv.next_back_leaf_edge(), (k, v))
 203         })
 204     }
 205 }
 206
 207 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
 208     /// Returns the leftmost leaf edge in or underneath a node - in other words, the edge
 209     /// you need first when navigating forward (or last when navigating backward).
 210     #[inline]
 211     pub fn first_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
 212         let mut node = self;
 213         loop {
 214             match node.force() {
 215                 Leaf(leaf) => return leaf.first_edge(),
 216                 Internal(internal) => node = internal.first_edge().descend(),
 217             }
 218         }
 219     }
 220
 221     /// Returns the rightmost leaf edge in or underneath a node - in other words, the edge
 222     /// you need last when navigating forward (or first when navigating backward).
 223     #[inline]
 224     pub fn last_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
 225         let mut node = self;
 226         loop {
 227             match node.force() {
 228                 Leaf(leaf) => return leaf.last_edge(),
 229                 Internal(internal) => node = internal.last_edge().descend(),
 230             }
 231         }
 232     }
 233 }
 234
 235 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
 236     /// Returns the leaf edge closest to a KV for forward navigation.
 237     pub fn next_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
 238         match self.force() {
 239             Leaf(leaf_kv) => leaf_kv.right_edge(),
 240             Internal(internal_kv) => {
 241                 let next_internal_edge = internal_kv.right_edge();
 242                 next_internal_edge.descend().first_leaf_edge()
 243             }
 244         }
 245     }
 246
 247     /// Returns the leaf edge closest to a KV for backward navigation.
 248     pub fn next_back_leaf_edge(
 249         self,
 250     ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
 251         match self.force() {
 252             Leaf(leaf_kv) => leaf_kv.left_edge(),
 253             Internal(internal_kv) => {
 254                 let next_internal_edge = internal_kv.left_edge();
 255                 next_internal_edge.descend().last_leaf_edge()
 256             }
 257         }
 258     }
 259 }