use core::ops::{Index, RangeBounds};
use core::ptr;
+use super::borrow::DormantMutRef;
use super::node::{self, marker, ForceResult::*, Handle, InsertResult::*, NodeRef};
use super::search::{self, SearchResult::*};
use super::unwrap_unchecked;
/// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is
/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
///
-/// [`Ord`]: core::cmp::Ord
/// [`Cell`]: core::cell::Cell
/// [`RefCell`]: core::cell::RefCell
///
/// }
/// ```
///
-/// `BTreeMap` also implements an [`Entry API`](#method.entry), which allows
-/// for more complex methods of getting, setting, updating and removing keys and
-/// their values:
+/// `BTreeMap` also implements an [`Entry API`], which allows for more complex
+/// methods of getting, setting, updating and removing keys and their values:
+///
+/// [`Entry API`]: BTreeMap::entry
///
/// ```
/// use std::collections::BTreeMap;
}
fn take(&mut self, key: &Q) -> Option<K> {
- let root_node = self.root.as_mut()?.node_as_mut();
+ let (map, dormant_map) = DormantMutRef::new(self);
+ let root_node = map.root.as_mut()?.node_as_mut();
match search::search_tree(root_node, key) {
- Found(handle) => Some(
- OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData }
- .remove_kv()
- .0,
- ),
+ Found(handle) => {
+ Some(OccupiedEntry { handle, dormant_map, _marker: PhantomData }.remove_kv().0)
+ }
GoDown(_) => None,
}
}
fn replace(&mut self, key: K) -> Option<K> {
- let root = Self::ensure_is_owned(&mut self.root);
- match search::search_tree::<marker::Mut<'_>, K, (), K>(root.node_as_mut(), &key) {
+ let (map, dormant_map) = DormantMutRef::new(self);
+ let root_node = Self::ensure_is_owned(&mut map.root).node_as_mut();
+ match search::search_tree::<marker::Mut<'_>, K, (), K>(root_node, &key) {
Found(handle) => Some(mem::replace(handle.into_key_mut(), key)),
GoDown(handle) => {
- VacantEntry { key, handle, length: &mut self.length, _marker: PhantomData }
- .insert(());
+ VacantEntry { key, handle, dormant_map, _marker: PhantomData }.insert(());
None
}
}
/// A view into a vacant entry in a `BTreeMap`.
/// It is part of the [`Entry`] enum.
-///
-/// [`Entry`]: enum.Entry.html
#[stable(feature = "rust1", since = "1.0.0")]
pub struct VacantEntry<'a, K: 'a, V: 'a> {
key: K,
handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
- length: &'a mut usize,
+ dormant_map: DormantMutRef<'a, BTreeMap<K, V>>,
// Be invariant in `K` and `V`
_marker: PhantomData<&'a mut (K, V)>,
/// A view into an occupied entry in a `BTreeMap`.
/// It is part of the [`Entry`] enum.
-///
-/// [`Entry`]: enum.Entry.html
#[stable(feature = "rust1", since = "1.0.0")]
pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>,
-
- length: &'a mut usize,
+ dormant_map: DormantMutRef<'a, BTreeMap<K, V>>,
// Be invariant in `K` and `V`
_marker: PhantomData<&'a mut (K, V)>,
/// ```
#[unstable(feature = "map_first_last", issue = "62924")]
pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> {
- let root_node = self.root.as_mut()?.node_as_mut();
+ let (map, dormant_map) = DormantMutRef::new(self);
+ let root_node = map.root.as_mut()?.node_as_mut();
let kv = root_node.first_leaf_edge().right_kv().ok()?;
- Some(OccupiedEntry {
- handle: kv.forget_node_type(),
- length: &mut self.length,
- _marker: PhantomData,
- })
+ Some(OccupiedEntry { handle: kv.forget_node_type(), dormant_map, _marker: PhantomData })
}
/// Removes and returns the first element in the map.
/// ```
#[unstable(feature = "map_first_last", issue = "62924")]
pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> {
- let root_node = self.root.as_mut()?.node_as_mut();
+ let (map, dormant_map) = DormantMutRef::new(self);
+ let root_node = map.root.as_mut()?.node_as_mut();
let kv = root_node.last_leaf_edge().left_kv().ok()?;
- Some(OccupiedEntry {
- handle: kv.forget_node_type(),
- length: &mut self.length,
- _marker: PhantomData,
- })
+ Some(OccupiedEntry { handle: kv.forget_node_type(), dormant_map, _marker: PhantomData })
}
/// Removes and returns the last element in the map.
/// types that can be `==` without being identical. See the [module-level
/// documentation] for more.
///
- /// [module-level documentation]: index.html#insert-and-complex-keys
+ /// [module-level documentation]: crate::collections#insert-and-complex-keys
///
/// # Examples
///
K: Borrow<Q>,
Q: Ord,
{
- let root_node = self.root.as_mut()?.node_as_mut();
+ let (map, dormant_map) = DormantMutRef::new(self);
+ let root_node = map.root.as_mut()?.node_as_mut();
match search::search_tree(root_node, key) {
- Found(handle) => Some(
- OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData }
- .remove_entry(),
- ),
+ Found(handle) => {
+ Some(OccupiedEntry { handle, dormant_map, _marker: PhantomData }.remove_entry())
+ }
GoDown(_) => None,
}
}
#[stable(feature = "rust1", since = "1.0.0")]
pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
// FIXME(@porglezomp) Avoid allocating if we don't insert
- let root = Self::ensure_is_owned(&mut self.root);
- match search::search_tree(root.node_as_mut(), &key) {
- Found(handle) => {
- Occupied(OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData })
- }
+ let (map, dormant_map) = DormantMutRef::new(self);
+ let root_node = Self::ensure_is_owned(&mut map.root).node_as_mut();
+ match search::search_tree(root_node, &key) {
+ Found(handle) => Occupied(OccupiedEntry { handle, dormant_map, _marker: PhantomData }),
GoDown(handle) => {
- Vacant(VacantEntry { key, handle, length: &mut self.length, _marker: PhantomData })
+ Vacant(VacantEntry { key, handle, dormant_map, _marker: PhantomData })
}
}
}
}
pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner<'_, K, V> {
- let root_node = self.root.as_mut().map(|r| r.node_as_mut());
- let front = root_node.map(|rn| rn.first_leaf_edge());
- DrainFilterInner { length: &mut self.length, cur_leaf_edge: front }
+ if let Some(root) = self.root.as_mut() {
+ let (root, dormant_root) = DormantMutRef::new(root);
+ let front = root.node_as_mut().first_leaf_edge();
+ DrainFilterInner {
+ length: &mut self.length,
+ dormant_root: Some(dormant_root),
+ cur_leaf_edge: Some(front),
+ }
+ } else {
+ DrainFilterInner { length: &mut self.length, dormant_root: None, cur_leaf_edge: None }
+ }
}
/// Creates a consuming iterator visiting all the keys, in sorted order.
/// of the predicate, thus also serving for BTreeSet::DrainFilter.
pub(super) struct DrainFilterInner<'a, K: 'a, V: 'a> {
length: &'a mut usize,
+ // dormant_root is wrapped in an Option to be able to `take` it.
+ dormant_root: Option<DormantMutRef<'a, node::Root<K, V>>>,
+ // cur_leaf_edge is wrapped in an Option because maps without root lack a leaf edge.
cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
}
/// Allow Debug implementations to predict the next element.
pub(super) fn peek(&self) -> Option<(&K, &V)> {
let edge = self.cur_leaf_edge.as_ref()?;
- edge.reborrow().next_kv().ok().map(|kv| kv.into_kv())
+ edge.reborrow().next_kv().ok().map(Handle::into_kv)
}
/// Implementation of a typical `DrainFilter::next` method, given the predicate.
let (k, v) = kv.kv_mut();
if pred(k, v) {
*self.length -= 1;
- let (kv, pos) = kv.remove_kv_tracking();
+ let (kv, pos) = kv.remove_kv_tracking(|| {
+ // SAFETY: we will touch the root in a way that will not
+ // invalidate the position returned.
+ let root = unsafe { self.dormant_root.take().unwrap().awaken() };
+ root.pop_internal_level();
+ self.dormant_root = Some(DormantMutRef::new(root).1);
+ });
self.cur_leaf_edge = Some(pos);
return Some(kv);
}
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub fn insert(self, value: V) -> &'a mut V {
- *self.length += 1;
-
let out_ptr = match self.handle.insert_recursing(self.key, value) {
- (Fit(_), val_ptr) => val_ptr,
+ (Fit(_), val_ptr) => {
+ // Safety: We have consumed self.handle and the handle returned.
+ let map = unsafe { self.dormant_map.awaken() };
+ map.length += 1;
+ val_ptr
+ }
(Split(ins), val_ptr) => {
- let root = ins.left.into_root_mut();
+ drop(ins.left);
+ // Safety: We have consumed self.handle and the reference returned.
+ let map = unsafe { self.dormant_map.awaken() };
+ let root = map.root.as_mut().unwrap();
root.push_internal_level().push(ins.k, ins.v, ins.right);
+ map.length += 1;
val_ptr
}
};
/// If you need a reference to the `OccupiedEntry` that may outlive the
/// destruction of the `Entry` value, see [`into_mut`].
///
- /// [`into_mut`]: #method.into_mut
+ /// [`into_mut`]: OccupiedEntry::into_mut
///
/// # Examples
///
///
/// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
///
- /// [`get_mut`]: #method.get_mut
+ /// [`get_mut`]: OccupiedEntry::get_mut
///
/// # Examples
///
// Body of `remove_entry`, separate to keep the above implementations short.
fn remove_kv(self) -> (K, V) {
- *self.length -= 1;
-
- let (old_kv, _) = self.handle.remove_kv_tracking();
+ let mut emptied_internal_root = false;
+ let (old_kv, _) = self.handle.remove_kv_tracking(|| emptied_internal_root = true);
+ // SAFETY: we consumed the intermediate root borrow, `self.handle`.
+ let map = unsafe { self.dormant_map.awaken() };
+ map.length -= 1;
+ if emptied_internal_root {
+ let root = map.root.as_mut().unwrap();
+ root.pop_internal_level();
+ }
old_kv
}
}
impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> {
/// Removes a key/value-pair from the map, and returns that pair, as well as
/// the leaf edge corresponding to that former pair.
- fn remove_kv_tracking(
+ fn remove_kv_tracking<F: FnOnce()>(
self,
+ handle_emptied_internal_root: F,
) -> ((K, V), Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>) {
let (old_kv, mut pos, was_internal) = match self.force() {
Leaf(leaf) => {
// The parent that was just emptied must be the root,
// because nodes on a lower level would not have been
// left with a single child.
- parent.into_root_mut().pop_internal_level();
+ handle_emptied_internal_root();
break;
} else {
cur_node = parent.forget_type();
projects / rust.git / blobdiff