-// ignore-tidy-filelength
-
use core::borrow::Borrow;
use core::cmp::Ordering;
-use core::fmt::Debug;
+use core::fmt::{self, Debug};
use core::hash::{Hash, Hasher};
use core::iter::{FromIterator, FusedIterator, Peekable};
use core::marker::PhantomData;
use core::mem::{self, ManuallyDrop};
use core::ops::Bound::{Excluded, Included, Unbounded};
use core::ops::{Index, RangeBounds};
-use core::{fmt, ptr};
+use core::ptr;
use super::node::{self, marker, ForceResult::*, Handle, InsertResult::*, NodeRef};
use super::search::{self, SearchResult::*};
{
let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped
- let mut out_node = match root.as_mut().force() {
+ let mut out_node = match root.node_as_mut().force() {
Leaf(leaf) => leaf,
Internal(_) => unreachable!(),
};
// Ord` constraint, which this method lacks.
BTreeMap { root: None, length: 0 }
} else {
- clone_subtree(self.root.as_ref().unwrap().as_ref()) // unwrap succeeds because not empty
+ clone_subtree(self.root.as_ref().unwrap().node_as_ref()) // unwrap succeeds because not empty
}
}
}
type Key = K;
fn get(&self, key: &Q) -> Option<&K> {
- match search::search_tree(self.root.as_ref()?.as_ref(), key) {
+ let root_node = self.root.as_ref()?.node_as_ref();
+ match search::search_tree(root_node, key) {
Found(handle) => Some(handle.into_kv().0),
GoDown(_) => None,
}
}
fn take(&mut self, key: &Q) -> Option<K> {
- match search::search_tree(self.root.as_mut()?.as_mut(), key) {
+ let root_node = self.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()
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.as_mut(), &key) {
+ match search::search_tree::<marker::Mut<'_>, K, (), K>(root.node_as_mut(), &key) {
Found(handle) => Some(mem::replace(handle.into_kv_mut().0, key)),
GoDown(handle) => {
VacantEntry { key, handle, length: &mut self.length, _marker: PhantomData }
/// See its documentation for more.
///
/// [`into_keys`]: BTreeMap::into_keys
-#[unstable(feature = "map_into_keys_values", issue = "55214")]
+#[unstable(feature = "map_into_keys_values", issue = "75294")]
#[derive(Debug)]
pub struct IntoKeys<K, V> {
inner: IntoIter<K, V>,
/// See its documentation for more.
///
/// [`into_values`]: BTreeMap::into_values
-#[unstable(feature = "map_into_keys_values", issue = "55214")]
+#[unstable(feature = "map_into_keys_values", issue = "75294")]
#[derive(Debug)]
pub struct IntoValues<K, V> {
inner: IntoIter<K, V>,
K: Borrow<Q>,
Q: Ord,
{
- match search::search_tree(self.root.as_ref()?.as_ref(), key) {
+ let root_node = self.root.as_ref()?.node_as_ref();
+ match search::search_tree(root_node, key) {
Found(handle) => Some(handle.into_kv().1),
GoDown(_) => None,
}
K: Borrow<Q>,
Q: Ord,
{
- match search::search_tree(self.root.as_ref()?.as_ref(), k) {
+ let root_node = self.root.as_ref()?.node_as_ref();
+ match search::search_tree(root_node, k) {
Found(handle) => Some(handle.into_kv()),
GoDown(_) => None,
}
/// ```
#[unstable(feature = "map_first_last", issue = "62924")]
pub fn first_key_value(&self) -> Option<(&K, &V)> {
- let front = self.root.as_ref()?.as_ref().first_leaf_edge();
- front.right_kv().ok().map(Handle::into_kv)
+ let root_node = self.root.as_ref()?.node_as_ref();
+ root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv)
}
/// Returns the first entry in the map for in-place manipulation.
/// ```
#[unstable(feature = "map_first_last", issue = "62924")]
pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> {
- let front = self.root.as_mut()?.as_mut().first_leaf_edge();
- let kv = front.right_kv().ok()?;
+ let root_node = self.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,
/// ```
#[unstable(feature = "map_first_last", issue = "62924")]
pub fn last_key_value(&self) -> Option<(&K, &V)> {
- let back = self.root.as_ref()?.as_ref().last_leaf_edge();
- back.left_kv().ok().map(Handle::into_kv)
+ let root_node = self.root.as_ref()?.node_as_ref();
+ root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv)
}
/// Returns the last entry in the map for in-place manipulation.
/// ```
#[unstable(feature = "map_first_last", issue = "62924")]
pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> {
- let back = self.root.as_mut()?.as_mut().last_leaf_edge();
- let kv = back.left_kv().ok()?;
+ let root_node = self.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,
K: Borrow<Q>,
Q: Ord,
{
- match search::search_tree(self.root.as_mut()?.as_mut(), key) {
+ let root_node = self.root.as_mut()?.node_as_mut();
+ match search::search_tree(root_node, key) {
Found(handle) => Some(handle.into_kv_mut().1),
GoDown(_) => None,
}
K: Borrow<Q>,
Q: Ord,
{
- match search::search_tree(self.root.as_mut()?.as_mut(), key) {
+ let root_node = self.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(),
R: RangeBounds<T>,
{
if let Some(root) = &self.root {
- let (f, b) = range_search(root.as_ref(), range);
+ let (f, b) = range_search(root.node_as_ref(), range);
Range { front: Some(f), back: Some(b) }
} else {
R: RangeBounds<T>,
{
if let Some(root) = &mut self.root {
- let (f, b) = range_search(root.as_mut(), range);
+ let (f, b) = range_search(root.node_as_mut(), range);
RangeMut { front: Some(f), back: Some(b), _marker: PhantomData }
} else {
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.as_mut(), &key) {
+ match search::search_tree(root.node_as_mut(), &key) {
Found(handle) => {
Occupied(OccupiedEntry { handle, length: &mut self.length, _marker: PhantomData })
}
fn from_sorted_iter<I: Iterator<Item = (K, V)>>(&mut self, iter: I) {
let root = Self::ensure_is_owned(&mut self.root);
- let mut cur_node = root.as_mut().last_leaf_edge().into_node();
+ let mut cur_node = root.node_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.
fn fix_right_edge(root: &mut node::Root<K, V>) {
// Handle underfull nodes, start from the top.
- let mut cur_node = root.as_mut();
+ let mut cur_node = root.node_as_mut();
while let Internal(internal) = cur_node.force() {
// Check if right-most child is underfull.
let mut last_edge = internal.last_edge();
}
{
- let mut left_node = left_root.as_mut();
- let mut right_node = right_root.as_mut();
+ let mut left_node = left_root.node_as_mut();
+ let mut right_node = right_root.node_as_mut();
loop {
let mut split_edge = match search::search_node(left_node, key) {
DrainFilter { pred, inner: self.drain_filter_inner() }
}
pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner<'_, K, V> {
- let front = self.root.as_mut().map(|r| r.as_mut().first_leaf_edge());
- DrainFilterInner {
- length: &mut self.length,
- cur_leaf_edge: front,
- emptied_internal_root: false,
- }
+ 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 }
}
/// Calculates the number of elements if it is incorrect.
res
}
- self.length = dfs(self.root.as_ref().unwrap().as_ref());
+ self.length = dfs(self.root.as_ref().unwrap().node_as_ref());
}
/// Creates a consuming iterator visiting all the keys, in sorted order.
/// assert_eq!(keys, [1, 2]);
/// ```
#[inline]
- #[unstable(feature = "map_into_keys_values", issue = "55214")]
+ #[unstable(feature = "map_into_keys_values", issue = "75294")]
pub fn into_keys(self) -> IntoKeys<K, V> {
IntoKeys { inner: self.into_iter() }
}
- /// Creates a consuming iterator visiting all the values, in sorted order.
+ /// Creates a consuming iterator visiting all the values, in order by key.
/// The map cannot be used after calling this.
/// The iterator element type is `V`.
///
/// assert_eq!(values, ["hello", "goodbye"]);
/// ```
#[inline]
- #[unstable(feature = "map_into_keys_values", issue = "55214")]
+ #[unstable(feature = "map_into_keys_values", issue = "75294")]
pub fn into_values(self) -> IntoValues<K, V> {
IntoValues { inner: self.into_iter() }
}
pub(super) struct DrainFilterInner<'a, K: 'a, V: 'a> {
length: &'a mut usize,
cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
- emptied_internal_root: bool,
}
#[unstable(feature = "btree_drain_filter", issue = "70530")]
}
}
-impl<K, V> Drop for DrainFilterInner<'_, K, V> {
- fn drop(&mut self) {
- if self.emptied_internal_root {
- if let Some(handle) = self.cur_leaf_edge.take() {
- let root = handle.into_node().into_root_mut();
- root.pop_internal_level();
- }
- }
- }
-}
-
impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> {
/// Allow Debug implementations to predict the next element.
pub(super) fn peek(&self) -> Option<(&K, &V)> {
let (k, v) = kv.kv_mut();
if pred(k, v) {
*self.length -= 1;
- let RemoveResult { old_kv, pos, emptied_internal_root } = kv.remove_kv_tracking();
+ let (kv, pos) = kv.remove_kv_tracking();
self.cur_leaf_edge = Some(pos);
- self.emptied_internal_root |= emptied_internal_root;
- return Some(old_kv);
+ return Some(kv);
}
self.cur_leaf_edge = Some(kv.next_leaf_edge());
}
}
}
-#[unstable(feature = "map_into_keys_values", issue = "55214")]
+#[unstable(feature = "map_into_keys_values", issue = "75294")]
impl<K, V> Iterator for IntoKeys<K, V> {
type Item = K;
}
}
-#[unstable(feature = "map_into_keys_values", issue = "55214")]
+#[unstable(feature = "map_into_keys_values", issue = "75294")]
impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
fn next_back(&mut self) -> Option<K> {
self.inner.next_back().map(|(k, _)| k)
}
}
-#[unstable(feature = "map_into_keys_values", issue = "55214")]
+#[unstable(feature = "map_into_keys_values", issue = "75294")]
impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
fn len(&self) -> usize {
self.inner.len()
}
}
-#[unstable(feature = "map_into_keys_values", issue = "55214")]
+#[unstable(feature = "map_into_keys_values", issue = "75294")]
impl<K, V> FusedIterator for IntoKeys<K, V> {}
-#[unstable(feature = "map_into_keys_values", issue = "55214")]
+#[unstable(feature = "map_into_keys_values", issue = "75294")]
impl<K, V> Iterator for IntoValues<K, V> {
type Item = V;
fn last(mut self) -> Option<V> {
self.next_back()
}
-
- fn min(mut self) -> Option<V> {
- self.next()
- }
-
- fn max(mut self) -> Option<V> {
- self.next_back()
- }
}
-#[unstable(feature = "map_into_keys_values", issue = "55214")]
+#[unstable(feature = "map_into_keys_values", issue = "75294")]
impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
fn next_back(&mut self) -> Option<V> {
self.inner.next_back().map(|(_, v)| v)
}
}
-#[unstable(feature = "map_into_keys_values", issue = "55214")]
+#[unstable(feature = "map_into_keys_values", issue = "75294")]
impl<K, V> ExactSizeIterator for IntoValues<K, V> {
fn len(&self) -> usize {
self.inner.len()
}
}
-#[unstable(feature = "map_into_keys_values", issue = "55214")]
+#[unstable(feature = "map_into_keys_values", issue = "75294")]
impl<K, V> FusedIterator for IntoValues<K, V> {}
#[stable(feature = "btree_range", since = "1.17.0")]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn iter(&self) -> Iter<'_, K, V> {
if let Some(root) = &self.root {
- let (f, b) = full_range_search(root.as_ref());
+ let (f, b) = full_range_search(root.node_as_ref());
Iter { range: Range { front: Some(f), back: Some(b) }, length: self.length }
} else {
#[stable(feature = "rust1", since = "1.0.0")]
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
if let Some(root) = &mut self.root {
- let (f, b) = full_range_search(root.as_mut());
+ let (f, b) = full_range_search(root.node_as_mut());
IterMut {
range: RangeMut { front: Some(f), back: Some(b), _marker: PhantomData },
fn remove_kv(self) -> (K, V) {
*self.length -= 1;
- let RemoveResult { old_kv, pos, emptied_internal_root } = self.handle.remove_kv_tracking();
- let root = pos.into_node().into_root_mut();
- if emptied_internal_root {
- root.pop_internal_level();
- }
+ let (old_kv, _) = self.handle.remove_kv_tracking();
old_kv
}
}
-struct RemoveResult<'a, K, V> {
- // Key and value removed.
- old_kv: (K, V),
- // Unique location at the leaf level that the removed KV lopgically collapsed into.
- pos: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>,
- // Whether the remove left behind and empty internal root node, that should be removed
- // using `pop_internal_level`.
- emptied_internal_root: bool,
-}
-
impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> {
- /// Removes a key/value-pair from the tree, and returns that pair, as well as
- /// the leaf edge corresponding to that former pair. It's possible this leaves
- /// an empty internal root node, which the caller should subsequently pop from
- /// the map holding the tree. The caller should also decrement the map's length.
- fn remove_kv_tracking(self) -> RemoveResult<'a, K, V> {
- let (mut pos, old_key, old_val, was_internal) = match self.force() {
+ /// 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(
+ self,
+ ) -> ((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) => {
- let (hole, old_key, old_val) = leaf.remove();
- (hole, old_key, old_val, false)
+ let (old_kv, pos) = leaf.remove();
+ (old_kv, pos, false)
}
Internal(mut internal) => {
- // Replace the location freed in the internal node with the next KV,
- // and remove that next KV from its leaf.
+ // Replace the location freed in the internal node with an
+ // adjacent KV, and remove that adjacent KV from its leaf.
+ // Always choose the adjacent KV on the left side because
+ // it is typically faster to pop an element from the end
+ // of the KV arrays without needing to shift other elements.
let key_loc = internal.kv_mut().0 as *mut K;
let val_loc = internal.kv_mut().1 as *mut V;
- // Deleting from the left side is typically faster since we can
- // just pop an element from the end of the KV array without
- // needing to shift the other values.
let to_remove = internal.left_edge().descend().last_leaf_edge().left_kv().ok();
let to_remove = unsafe { unwrap_unchecked(to_remove) };
- let (hole, key, val) = to_remove.remove();
+ let (kv, pos) = to_remove.remove();
- let old_key = unsafe { mem::replace(&mut *key_loc, key) };
- let old_val = unsafe { mem::replace(&mut *val_loc, val) };
+ let old_key = unsafe { mem::replace(&mut *key_loc, kv.0) };
+ let old_val = unsafe { mem::replace(&mut *val_loc, kv.1) };
- (hole, old_key, old_val, true)
+ ((old_key, old_val), pos, true)
}
};
// Handle underflow
- let mut emptied_internal_root = false;
let mut cur_node = unsafe { ptr::read(&pos).into_node().forget_type() };
let mut at_leaf = true;
while cur_node.len() < node::MIN_LEN {
let parent = edge.into_node();
if parent.len() == 0 {
- // This empty parent must be the root, and should be popped off the tree.
- emptied_internal_root = true;
+ // 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();
break;
} else {
cur_node = parent.forget_type();
pos = unsafe { unwrap_unchecked(pos.next_kv().ok()).next_leaf_edge() };
}
- RemoveResult { old_kv: (old_key, old_val), pos, emptied_internal_root }
+ (old_kv, pos)
}
}
impl<K, V> node::Root<K, V> {
/// Removes empty levels on the top, but keep an empty leaf if the entire tree is empty.
fn fix_top(&mut self) {
- while self.height() > 0 && self.as_ref().len() == 0 {
+ while self.height() > 0 && self.node_as_ref().len() == 0 {
self.pop_internal_level();
}
}
self.fix_top();
{
- let mut cur_node = self.as_mut();
+ let mut cur_node = self.node_as_mut();
while let Internal(node) = cur_node.force() {
let mut last_kv = node.last_kv();
self.fix_top();
{
- let mut cur_node = self.as_mut();
+ let mut cur_node = self.node_as_mut();
while let Internal(node) = cur_node.force() {
let mut first_kv = node.first_kv();
Err(_) => return AtRoot,
};
+ // Prefer the left KV if it exists. Merging with the left side is faster,
+ // since merging happens towards the left and `node` has fewer elements.
+ // Stealing from the left side is faster, since we can pop from the end of
+ // the KV arrays.
let (is_left, mut handle) = match parent.left_kv() {
Ok(left) => (true, left),
Err(parent) => {
- match parent.right_kv() {
- Ok(right) => (false, right),
- Err(_) => {
- // The underfull node has an empty parent, so it is the only child
- // of an empty root. It is destined to become the new root, thus
- // allowed to be underfull. The empty parent should be removed later
- // by `pop_internal_level`.
- return AtRoot;
- }
- }
+ let right = unsafe { unwrap_unchecked(parent.right_kv().ok()) };
+ (false, right)
}
};
projects / rust.git / blobdiff