1 use core::borrow::Borrow;
2 use core::cmp::Ordering;
5 use core::ops::Bound::{Excluded, Included, Unbounded};
6 use core::ops::RangeBounds;
9 use super::node::{marker, ForceResult::*, Handle, NodeRef};
10 use super::search::{self, SearchResult};
11 use super::unwrap_unchecked;
13 /// Finds the leaf edges delimiting a specified range in or underneath a node.
14 fn range_search<BorrowType, K, V, Q, R>(
15 root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
16 root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
19 Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>,
20 Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>,
27 match (range.start_bound(), range.end_bound()) {
28 (Excluded(s), Excluded(e)) if s == e => {
29 panic!("range start and end are equal and excluded in BTreeMap")
31 (Included(s) | Excluded(s), Included(e) | Excluded(e)) if s > e => {
32 panic!("range start is greater than range end in BTreeMap")
37 let mut min_node = root1;
38 let mut max_node = root2;
39 let mut min_found = false;
40 let mut max_found = false;
43 let front = match (min_found, range.start_bound()) {
44 (false, Included(key)) => match search::search_node(min_node, key) {
45 SearchResult::Found(kv) => {
49 SearchResult::GoDown(edge) => edge,
51 (false, Excluded(key)) => match search::search_node(min_node, key) {
52 SearchResult::Found(kv) => {
56 SearchResult::GoDown(edge) => edge,
58 (true, Included(_)) => min_node.last_edge(),
59 (true, Excluded(_)) => min_node.first_edge(),
60 (_, Unbounded) => min_node.first_edge(),
63 let back = match (max_found, range.end_bound()) {
64 (false, Included(key)) => match search::search_node(max_node, key) {
65 SearchResult::Found(kv) => {
69 SearchResult::GoDown(edge) => edge,
71 (false, Excluded(key)) => match search::search_node(max_node, key) {
72 SearchResult::Found(kv) => {
76 SearchResult::GoDown(edge) => edge,
78 (true, Included(_)) => max_node.first_edge(),
79 (true, Excluded(_)) => max_node.last_edge(),
80 (_, Unbounded) => max_node.last_edge(),
83 if front.partial_cmp(&back) == Some(Ordering::Greater) {
84 panic!("Ord is ill-defined in BTreeMap range");
86 match (front.force(), back.force()) {
87 (Leaf(f), Leaf(b)) => {
90 (Internal(min_int), Internal(max_int)) => {
91 min_node = min_int.descend();
92 max_node = max_int.descend();
94 _ => unreachable!("BTreeMap has different depths"),
99 /// Equivalent to `range_search(k, v, ..)` but without the `Ord` bound.
100 fn full_range<BorrowType, K, V>(
101 root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
102 root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
104 Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>,
105 Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>,
107 let mut min_node = root1;
108 let mut max_node = root2;
110 let front = min_node.first_edge();
111 let back = max_node.last_edge();
112 match (front.force(), back.force()) {
113 (Leaf(f), Leaf(b)) => {
116 (Internal(min_int), Internal(max_int)) => {
117 min_node = min_int.descend();
118 max_node = max_int.descend();
120 _ => unreachable!("BTreeMap has different depths"),
125 impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
126 /// Creates a pair of leaf edges delimiting a specified range in or underneath a node.
127 pub fn range_search<Q, R>(
131 Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
132 Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
139 range_search(self, self, range)
142 /// Returns (self.first_leaf_edge(), self.last_leaf_edge()), but more efficiently.
146 Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
147 Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>,
149 full_range(self, self)
153 impl<'a, K: 'a, V: 'a> NodeRef<marker::ValMut<'a>, K, V, marker::LeafOrInternal> {
154 /// Splits a unique reference into a pair of leaf edges delimiting a specified range.
155 /// The result are non-unique references allowing (some) mutation, which must be used
157 pub fn range_search<Q, R>(
161 Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge>,
162 Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge>,
169 // We duplicate the root NodeRef here -- we will never visit the same KV
170 // twice, and never end up with overlapping value references.
171 let self2 = unsafe { ptr::read(&self) };
172 range_search(self, self2, range)
175 /// Splits a unique reference into a pair of leaf edges delimiting the full range of the tree.
176 /// The results are non-unique references allowing mutation (of values only), so must be used
181 Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge>,
182 Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge>,
184 // We duplicate the root NodeRef here -- we will never visit the same KV
185 // twice, and never end up with overlapping value references.
186 let self2 = unsafe { ptr::read(&self) };
187 full_range(self, self2)
191 impl<K, V> NodeRef<marker::Owned, K, V, marker::LeafOrInternal> {
192 /// Splits a unique reference into a pair of leaf edges delimiting the full range of the tree.
193 /// The results are non-unique references allowing massively destructive mutation, so must be
194 /// used with the utmost care.
198 Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
199 Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
201 // We duplicate the root NodeRef here -- we will never access it in a way
202 // that overlaps references obtained from the root.
203 let self2 = unsafe { ptr::read(&self) };
204 full_range(self, self2)
208 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
209 /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
210 /// on the right side, which is either in the same leaf node or in an ancestor node.
211 /// If the leaf edge is the last one in the tree, returns [`Result::Err`] with the root node.
215 Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
216 NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
218 let mut edge = self.forget_node_type();
220 edge = match edge.right_kv() {
221 Ok(kv) => return Ok(kv),
222 Err(last_edge) => match last_edge.into_node().ascend() {
223 Ok(parent_edge) => parent_edge.forget_node_type(),
224 Err(root) => return Err(root),
230 /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
231 /// on the left side, which is either in the same leaf node or in an ancestor node.
232 /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node.
236 Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
237 NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
239 let mut edge = self.forget_node_type();
241 edge = match edge.left_kv() {
242 Ok(kv) => return Ok(kv),
243 Err(last_edge) => match last_edge.into_node().ascend() {
244 Ok(parent_edge) => parent_edge.forget_node_type(),
245 Err(root) => return Err(root),
252 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge> {
253 /// Given an internal edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
254 /// on the right side, which is either in the same internal node or in an ancestor node.
255 /// If the internal edge is the last one in the tree, returns [`Result::Err`] with the root node.
259 Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>,
260 NodeRef<BorrowType, K, V, marker::Internal>,
264 edge = match edge.right_kv() {
265 Ok(internal_kv) => return Ok(internal_kv),
266 Err(last_edge) => match last_edge.into_node().ascend() {
267 Ok(parent_edge) => parent_edge,
268 Err(root) => return Err(root),
275 macro_rules! def_next_kv_uncheched_dealloc {
276 { unsafe fn $name:ident : $adjacent_kv:ident } => {
277 /// Given a leaf edge handle into an owned tree, returns a handle to the next KV,
278 /// while deallocating any node left behind yet leaving the corresponding edge
279 /// in its parent node dangling.
282 /// - The leaf edge must not be the last one in the direction travelled.
283 /// - The node carrying the next KV returned must not have been deallocated by a
284 /// previous call on any handle obtained for this tree.
285 unsafe fn $name <K, V>(
286 leaf_edge: Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge>,
287 ) -> Handle<NodeRef<marker::Owned, K, V, marker::LeafOrInternal>, marker::KV> {
288 let mut edge = leaf_edge.forget_node_type();
290 edge = match edge.$adjacent_kv() {
291 Ok(internal_kv) => return internal_kv,
294 let parent_edge = last_edge.into_node().deallocate_and_ascend();
295 unwrap_unchecked(parent_edge).forget_node_type()
304 def_next_kv_uncheched_dealloc! {unsafe fn next_kv_unchecked_dealloc: right_kv}
305 def_next_kv_uncheched_dealloc! {unsafe fn next_back_kv_unchecked_dealloc: left_kv}
307 /// This replaces the value behind the `v` unique reference by calling the
308 /// relevant function.
310 /// If a panic occurs in the `change` closure, the entire process will be aborted.
312 fn take_mut<T>(v: &mut T, change: impl FnOnce(T) -> T) {
313 replace(v, |value| (change(value), ()))
316 /// This replaces the value behind the `v` unique reference by calling the
317 /// relevant function, and returns a result obtained along the way.
319 /// If a panic occurs in the `change` closure, the entire process will be aborted.
321 fn replace<T, R>(v: &mut T, change: impl FnOnce(T) -> (T, R)) -> R {
323 impl Drop for PanicGuard {
328 let guard = PanicGuard;
329 let value = unsafe { ptr::read(v) };
330 let (new_value, ret) = change(value);
332 ptr::write(v, new_value);
338 impl<'a, K, V> Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge> {
339 /// Moves the leaf edge handle to the next leaf edge and returns references to the
340 /// key and value in between.
343 /// There must be another KV in the direction travelled.
344 pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
345 replace(self, |leaf_edge| {
346 let kv = leaf_edge.next_kv();
347 let kv = unsafe { unwrap_unchecked(kv.ok()) };
348 (kv.next_leaf_edge(), kv.into_kv())
352 /// Moves the leaf edge handle to the previous leaf edge and returns references to the
353 /// key and value in between.
356 /// There must be another KV in the direction travelled.
357 pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
358 replace(self, |leaf_edge| {
359 let kv = leaf_edge.next_back_kv();
360 let kv = unsafe { unwrap_unchecked(kv.ok()) };
361 (kv.next_back_leaf_edge(), kv.into_kv())
366 impl<'a, K, V> Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge> {
367 /// Moves the leaf edge handle to the next leaf edge and returns references to the
368 /// key and value in between.
371 /// There must be another KV in the direction travelled.
372 pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
373 let kv = replace(self, |leaf_edge| {
374 let kv = leaf_edge.next_kv();
375 let kv = unsafe { unwrap_unchecked(kv.ok()) };
376 (unsafe { ptr::read(&kv) }.next_leaf_edge(), kv)
378 // Doing this last is faster, according to benchmarks.
382 /// Moves the leaf edge handle to the previous leaf and returns references to the
383 /// key and value in between.
386 /// There must be another KV in the direction travelled.
387 pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
388 let kv = replace(self, |leaf_edge| {
389 let kv = leaf_edge.next_back_kv();
390 let kv = unsafe { unwrap_unchecked(kv.ok()) };
391 (unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv)
393 // Doing this last is faster, according to benchmarks.
398 impl<'a, K, V> Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> {
399 /// Moves the leaf edge handle to the next leaf edge.
402 /// There must be another KV in the direction travelled.
403 pub unsafe fn move_next_unchecked(&mut self) {
404 take_mut(self, |leaf_edge| {
405 let kv = leaf_edge.next_kv();
406 let kv = unsafe { unwrap_unchecked(kv.ok()) };
412 impl<K, V> Handle<NodeRef<marker::Owned, K, V, marker::Leaf>, marker::Edge> {
413 /// Moves the leaf edge handle to the next leaf edge and returns the key and value
414 /// in between, deallocating any node left behind while leaving the corresponding
415 /// edge in its parent node dangling.
418 /// - There must be another KV in the direction travelled.
419 /// - That KV was not previously returned by counterpart `next_back_unchecked`
420 /// on any copy of the handles being used to traverse the tree.
422 /// The only safe way to proceed with the updated handle is to compare it, drop it,
423 /// call this method again subject to its safety conditions, or call counterpart
424 /// `next_back_unchecked` subject to its safety conditions.
425 pub unsafe fn next_unchecked(&mut self) -> (K, V) {
426 replace(self, |leaf_edge| {
427 let kv = unsafe { next_kv_unchecked_dealloc(leaf_edge) };
428 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
429 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
430 (kv.next_leaf_edge(), (k, v))
434 /// Moves the leaf edge handle to the previous leaf edge and returns the key and value
435 /// in between, deallocating any node left behind while leaving the corresponding
436 /// edge in its parent node dangling.
439 /// - There must be another KV in the direction travelled.
440 /// - That leaf edge was not previously returned by counterpart `next_unchecked`
441 /// on any copy of the handles being used to traverse the tree.
443 /// The only safe way to proceed with the updated handle is to compare it, drop it,
444 /// call this method again subject to its safety conditions, or call counterpart
445 /// `next_unchecked` subject to its safety conditions.
446 pub unsafe fn next_back_unchecked(&mut self) -> (K, V) {
447 replace(self, |leaf_edge| {
448 let kv = unsafe { next_back_kv_unchecked_dealloc(leaf_edge) };
449 let k = unsafe { ptr::read(kv.reborrow().into_kv().0) };
450 let v = unsafe { ptr::read(kv.reborrow().into_kv().1) };
451 (kv.next_back_leaf_edge(), (k, v))
456 impl<BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
457 /// Returns the leftmost leaf edge in or underneath a node - in other words, the edge
458 /// you need first when navigating forward (or last when navigating backward).
460 pub fn first_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
464 Leaf(leaf) => return leaf.first_edge(),
465 Internal(internal) => node = internal.first_edge().descend(),
470 /// Returns the rightmost leaf edge in or underneath a node - in other words, the edge
471 /// you need last when navigating forward (or first when navigating backward).
473 pub fn last_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
477 Leaf(leaf) => return leaf.last_edge(),
478 Internal(internal) => node = internal.last_edge().descend(),
484 pub enum Position<BorrowType, K, V> {
485 Leaf(NodeRef<BorrowType, K, V, marker::Leaf>),
486 Internal(NodeRef<BorrowType, K, V, marker::Internal>),
487 InternalKV(Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>),
490 impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
491 /// Visits leaf nodes and internal KVs in order of ascending keys, and also
492 /// visits internal nodes as a whole in a depth first order, meaning that
493 /// internal nodes precede their individual KVs and their child nodes.
494 pub fn visit_nodes_in_order<F>(self, mut visit: F)
496 F: FnMut(Position<marker::Immut<'a>, K, V>),
499 Leaf(leaf) => visit(Position::Leaf(leaf)),
500 Internal(internal) => {
501 visit(Position::Internal(internal));
502 let mut edge = internal.first_edge();
504 edge = match edge.descend().force() {
506 visit(Position::Leaf(leaf));
507 match edge.next_kv() {
509 visit(Position::InternalKV(kv));
515 Internal(internal) => {
516 visit(Position::Internal(internal));
517 internal.first_edge()
525 /// Calculates the number of elements in a (sub)tree.
526 pub fn calc_length(self) -> usize {
528 self.visit_nodes_in_order(|pos| match pos {
529 Position::Leaf(node) => result += node.len(),
530 Position::Internal(node) => result += node.len(),
531 Position::InternalKV(_) => (),
537 impl<BorrowType, K, V> Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV> {
538 /// Returns the leaf edge closest to a KV for forward navigation.
539 pub fn next_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
541 Leaf(leaf_kv) => leaf_kv.right_edge(),
542 Internal(internal_kv) => {
543 let next_internal_edge = internal_kv.right_edge();
544 next_internal_edge.descend().first_leaf_edge()
549 /// Returns the leaf edge closest to a KV for backward navigation.
550 pub fn next_back_leaf_edge(
552 ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
554 Leaf(leaf_kv) => leaf_kv.left_edge(),
555 Internal(internal_kv) => {
556 let next_internal_edge = internal_kv.left_edge();
557 next_internal_edge.descend().last_leaf_edge()