use core::borrow::Borrow;
+use core::hint;
use core::ops::RangeBounds;
use core::ptr;
impl<'a, K, V> LeafRange<marker::Immut<'a>, K, V> {
#[inline]
pub fn next_checked(&mut self) -> Option<(&'a K, &'a V)> {
- if self.is_empty() { None } else { Some(unsafe { self.next_unchecked() }) }
+ self.perform_next_checked(|kv| kv.into_kv())
}
#[inline]
pub fn next_back_checked(&mut self) -> Option<(&'a K, &'a V)> {
- if self.is_empty() { None } else { Some(unsafe { self.next_back_unchecked() }) }
+ self.perform_next_back_checked(|kv| kv.into_kv())
}
+}
+impl<'a, K, V> LeafRange<marker::ValMut<'a>, K, V> {
#[inline]
- pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
- unsafe { self.front.as_mut().unwrap().next_unchecked() }
+ pub fn next_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
+ self.perform_next_checked(|kv| unsafe { ptr::read(kv) }.into_kv_valmut())
}
#[inline]
- pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
- unsafe { self.back.as_mut().unwrap().next_back_unchecked() }
+ pub fn next_back_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
+ self.perform_next_back_checked(|kv| unsafe { ptr::read(kv) }.into_kv_valmut())
}
}
-impl<'a, K, V> LeafRange<marker::ValMut<'a>, K, V> {
+impl<BorrowType: marker::BorrowType, K, V> LeafRange<BorrowType, K, V> {
+ /// If possible, extract some result from the following KV and move to the edge beyond it.
+ fn perform_next_checked<F, R>(&mut self, f: F) -> Option<R>
+ where
+ F: Fn(&Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>) -> R,
+ {
+ if self.is_empty() {
+ None
+ } else {
+ super::mem::replace(self.front.as_mut().unwrap(), |front| {
+ let kv = front.next_kv().ok().unwrap();
+ let result = f(&kv);
+ (kv.next_leaf_edge(), Some(result))
+ })
+ }
+ }
+
+ /// If possible, extract some result from the preceding KV and move to the edge beyond it.
+ fn perform_next_back_checked<F, R>(&mut self, f: F) -> Option<R>
+ where
+ F: Fn(&Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>) -> R,
+ {
+ if self.is_empty() {
+ None
+ } else {
+ super::mem::replace(self.back.as_mut().unwrap(), |back| {
+ let kv = back.next_back_kv().ok().unwrap();
+ let result = f(&kv);
+ (kv.next_back_leaf_edge(), Some(result))
+ })
+ }
+ }
+}
+
+enum LazyLeafHandle<BorrowType, K, V> {
+ Root(NodeRef<BorrowType, K, V, marker::LeafOrInternal>), // not yet descended
+ Edge(Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>),
+}
+
+impl<'a, K: 'a, V: 'a> Clone for LazyLeafHandle<marker::Immut<'a>, K, V> {
+ fn clone(&self) -> Self {
+ match self {
+ LazyLeafHandle::Root(root) => LazyLeafHandle::Root(*root),
+ LazyLeafHandle::Edge(edge) => LazyLeafHandle::Edge(*edge),
+ }
+ }
+}
+
+impl<BorrowType, K, V> LazyLeafHandle<BorrowType, K, V> {
+ fn reborrow(&self) -> LazyLeafHandle<marker::Immut<'_>, K, V> {
+ match self {
+ LazyLeafHandle::Root(root) => LazyLeafHandle::Root(root.reborrow()),
+ LazyLeafHandle::Edge(edge) => LazyLeafHandle::Edge(edge.reborrow()),
+ }
+ }
+}
+
+// `front` and `back` are always both `None` or both `Some`.
+pub struct LazyLeafRange<BorrowType, K, V> {
+ front: Option<LazyLeafHandle<BorrowType, K, V>>,
+ back: Option<LazyLeafHandle<BorrowType, K, V>>,
+}
+
+impl<'a, K: 'a, V: 'a> Clone for LazyLeafRange<marker::Immut<'a>, K, V> {
+ fn clone(&self) -> Self {
+ LazyLeafRange { front: self.front.clone(), back: self.back.clone() }
+ }
+}
+
+impl<BorrowType, K, V> LazyLeafRange<BorrowType, K, V> {
+ pub fn none() -> Self {
+ LazyLeafRange { front: None, back: None }
+ }
+
+ /// Temporarily takes out another, immutable equivalent of the same range.
+ pub fn reborrow(&self) -> LazyLeafRange<marker::Immut<'_>, K, V> {
+ LazyLeafRange {
+ front: self.front.as_ref().map(|f| f.reborrow()),
+ back: self.back.as_ref().map(|b| b.reborrow()),
+ }
+ }
+}
+
+impl<'a, K, V> LazyLeafRange<marker::Immut<'a>, K, V> {
#[inline]
- pub fn next_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
- if self.is_empty() { None } else { Some(unsafe { self.next_unchecked() }) }
+ pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
+ unsafe { self.init_front().unwrap().next_unchecked() }
}
#[inline]
- pub fn next_back_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
- if self.is_empty() { None } else { Some(unsafe { self.next_back_unchecked() }) }
+ pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
+ unsafe { self.init_back().unwrap().next_back_unchecked() }
}
+}
+impl<'a, K, V> LazyLeafRange<marker::ValMut<'a>, K, V> {
#[inline]
pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
- unsafe { self.front.as_mut().unwrap().next_unchecked() }
+ unsafe { self.init_front().unwrap().next_unchecked() }
}
#[inline]
pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
- unsafe { self.back.as_mut().unwrap().next_back_unchecked() }
+ unsafe { self.init_back().unwrap().next_back_unchecked() }
}
}
-impl<K, V> LeafRange<marker::Dying, K, V> {
- #[inline]
- pub fn take_front(
+impl<K, V> LazyLeafRange<marker::Dying, K, V> {
+ fn take_front(
&mut self,
) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge>> {
- self.front.take()
+ match self.front.take()? {
+ LazyLeafHandle::Root(root) => Some(root.first_leaf_edge()),
+ LazyLeafHandle::Edge(edge) => Some(edge),
+ }
}
#[inline]
&mut self,
) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
debug_assert!(self.front.is_some());
- let front = self.front.as_mut().unwrap();
+ let front = self.init_front().unwrap();
unsafe { front.deallocating_next_unchecked() }
}
&mut self,
) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
debug_assert!(self.back.is_some());
- let back = self.back.as_mut().unwrap();
+ let back = self.init_back().unwrap();
unsafe { back.deallocating_next_back_unchecked() }
}
+
+ #[inline]
+ pub fn deallocating_end(&mut self) {
+ if let Some(front) = self.take_front() {
+ front.deallocating_end()
+ }
+ }
+}
+
+impl<BorrowType: marker::BorrowType, K, V> LazyLeafRange<BorrowType, K, V> {
+ fn init_front(
+ &mut self,
+ ) -> Option<&mut Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>> {
+ if let Some(LazyLeafHandle::Root(root)) = &self.front {
+ self.front = Some(LazyLeafHandle::Edge(unsafe { ptr::read(root) }.first_leaf_edge()));
+ }
+ match &mut self.front {
+ None => None,
+ Some(LazyLeafHandle::Edge(edge)) => Some(edge),
+ // SAFETY: the code above would have replaced it.
+ Some(LazyLeafHandle::Root(_)) => unsafe { hint::unreachable_unchecked() },
+ }
+ }
+
+ fn init_back(
+ &mut self,
+ ) -> Option<&mut Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>> {
+ if let Some(LazyLeafHandle::Root(root)) = &self.back {
+ self.back = Some(LazyLeafHandle::Edge(unsafe { ptr::read(root) }.last_leaf_edge()));
+ }
+ match &mut self.back {
+ None => None,
+ Some(LazyLeafHandle::Edge(edge)) => Some(edge),
+ // SAFETY: the code above would have replaced it.
+ Some(LazyLeafHandle::Root(_)) => unsafe { hint::unreachable_unchecked() },
+ }
+ }
}
impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
}
}
-/// Equivalent to `(root1.first_leaf_edge(), root2.last_leaf_edge())` but more efficient.
fn full_range<BorrowType: marker::BorrowType, K, V>(
root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
-) -> LeafRange<BorrowType, K, V> {
- let mut min_node = root1;
- let mut max_node = root2;
- loop {
- let front = min_node.first_edge();
- let back = max_node.last_edge();
- match (front.force(), back.force()) {
- (Leaf(f), Leaf(b)) => {
- return LeafRange { front: Some(f), back: Some(b) };
- }
- (Internal(min_int), Internal(max_int)) => {
- min_node = min_int.descend();
- max_node = max_int.descend();
- }
- _ => unreachable!("BTreeMap has different depths"),
- };
+) -> LazyLeafRange<BorrowType, K, V> {
+ LazyLeafRange {
+ front: Some(LazyLeafHandle::Root(root1)),
+ back: Some(LazyLeafHandle::Root(root2)),
}
}
}
/// Finds the pair of leaf edges delimiting an entire tree.
- pub fn full_range(self) -> LeafRange<marker::Immut<'a>, K, V> {
+ pub fn full_range(self) -> LazyLeafRange<marker::Immut<'a>, K, V> {
full_range(self, self)
}
}
/// Splits a unique reference into a pair of leaf edges delimiting the full range of the tree.
/// The results are non-unique references allowing mutation (of values only), so must be used
/// with care.
- pub fn full_range(self) -> LeafRange<marker::ValMut<'a>, K, V> {
+ pub fn full_range(self) -> LazyLeafRange<marker::ValMut<'a>, K, V> {
// We duplicate the root NodeRef here -- we will never visit the same KV
// twice, and never end up with overlapping value references.
let self2 = unsafe { ptr::read(&self) };
/// Splits a unique reference into a pair of leaf edges delimiting the full range of the tree.
/// The results are non-unique references allowing massively destructive mutation, so must be
/// used with the utmost care.
- pub fn full_range(self) -> LeafRange<marker::Dying, K, V> {
+ pub fn full_range(self) -> LazyLeafRange<marker::Dying, K, V> {
// We duplicate the root NodeRef here -- we will never access it in a way
// that overlaps references obtained from the root.
let self2 = unsafe { ptr::read(&self) };
/// both sides of the tree, and have hit the same edge. As it is intended
/// only to be called when all keys and values have been returned,
/// no cleanup is done on any of the keys or values.
- pub fn deallocating_end(self) {
+ fn deallocating_end(self) {
let mut edge = self.forget_node_type();
while let Some(parent_edge) = unsafe { edge.into_node().deallocate_and_ascend() } {
edge = parent_edge.forget_node_type();
///
/// The only safe way to proceed with the updated handle is to compare it, drop it,
/// or call this method or counterpart `deallocating_next_back_unchecked` again.
- pub unsafe fn deallocating_next_unchecked(
+ unsafe fn deallocating_next_unchecked(
&mut self,
) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
super::mem::replace(self, |leaf_edge| unsafe { leaf_edge.deallocating_next().unwrap() })
projects / rustc.git / blobdiff