| use core::fmt::{self, Debug}; |
| use core::marker::PhantomData; |
| use core::mem; |
| |
| use crate::alloc::{Allocator, Global}; |
| |
| use super::super::borrow::DormantMutRef; |
| use super::super::node::{marker, Handle, NodeRef}; |
| use super::BTreeMap; |
| |
| use Entry::*; |
| |
| /// A view into a single entry in a map, which may either be vacant or occupied. |
| /// |
| /// This `enum` is constructed from the [`entry`] method on [`BTreeMap`]. |
| /// |
| /// [`entry`]: BTreeMap::entry |
| #[stable(feature = "rust1", since = "1.0.0")] |
| #[cfg_attr(not(test), rustc_diagnostic_item = "BTreeEntry")] |
| pub enum Entry< |
| 'a, |
| K: 'a, |
| V: 'a, |
| #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global, |
| > { |
| /// A vacant entry. |
| #[stable(feature = "rust1", since = "1.0.0")] |
| Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V, A>), |
| |
| /// An occupied entry. |
| #[stable(feature = "rust1", since = "1.0.0")] |
| Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V, A>), |
| } |
| |
| #[stable(feature = "debug_btree_map", since = "1.12.0")] |
| impl<K: Debug + Ord, V: Debug, A: Allocator + Clone> Debug for Entry<'_, K, V, A> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| match *self { |
| Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(), |
| Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(), |
| } |
| } |
| } |
| |
| /// A view into a vacant entry in a `BTreeMap`. |
| /// It is part of the [`Entry`] enum. |
| #[stable(feature = "rust1", since = "1.0.0")] |
| pub struct VacantEntry< |
| 'a, |
| K, |
| V, |
| #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global, |
| > { |
| pub(super) key: K, |
| /// `None` for a (empty) map without root |
| pub(super) handle: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>, |
| pub(super) dormant_map: DormantMutRef<'a, BTreeMap<K, V, A>>, |
| |
| /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`. |
| pub(super) alloc: A, |
| |
| // Be invariant in `K` and `V` |
| pub(super) _marker: PhantomData<&'a mut (K, V)>, |
| } |
| |
| #[stable(feature = "debug_btree_map", since = "1.12.0")] |
| impl<K: Debug + Ord, V, A: Allocator + Clone> Debug for VacantEntry<'_, K, V, A> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| f.debug_tuple("VacantEntry").field(self.key()).finish() |
| } |
| } |
| |
| /// A view into an occupied entry in a `BTreeMap`. |
| /// It is part of the [`Entry`] enum. |
| #[stable(feature = "rust1", since = "1.0.0")] |
| pub struct OccupiedEntry< |
| 'a, |
| K, |
| V, |
| #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global, |
| > { |
| pub(super) handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>, |
| pub(super) dormant_map: DormantMutRef<'a, BTreeMap<K, V, A>>, |
| |
| /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`. |
| pub(super) alloc: A, |
| |
| // Be invariant in `K` and `V` |
| pub(super) _marker: PhantomData<&'a mut (K, V)>, |
| } |
| |
| #[stable(feature = "debug_btree_map", since = "1.12.0")] |
| impl<K: Debug + Ord, V: Debug, A: Allocator + Clone> Debug for OccupiedEntry<'_, K, V, A> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| f.debug_struct("OccupiedEntry").field("key", self.key()).field("value", self.get()).finish() |
| } |
| } |
| |
| /// The error returned by [`try_insert`](BTreeMap::try_insert) when the key already exists. |
| /// |
| /// Contains the occupied entry, and the value that was not inserted. |
| #[unstable(feature = "map_try_insert", issue = "82766")] |
| pub struct OccupiedError<'a, K: 'a, V: 'a, A: Allocator + Clone = Global> { |
| /// The entry in the map that was already occupied. |
| pub entry: OccupiedEntry<'a, K, V, A>, |
| /// The value which was not inserted, because the entry was already occupied. |
| pub value: V, |
| } |
| |
| #[unstable(feature = "map_try_insert", issue = "82766")] |
| impl<K: Debug + Ord, V: Debug, A: Allocator + Clone> Debug for OccupiedError<'_, K, V, A> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| f.debug_struct("OccupiedError") |
| .field("key", self.entry.key()) |
| .field("old_value", self.entry.get()) |
| .field("new_value", &self.value) |
| .finish() |
| } |
| } |
| |
| #[unstable(feature = "map_try_insert", issue = "82766")] |
| impl<'a, K: Debug + Ord, V: Debug, A: Allocator + Clone> fmt::Display |
| for OccupiedError<'a, K, V, A> |
| { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| write!( |
| f, |
| "failed to insert {:?}, key {:?} already exists with value {:?}", |
| self.value, |
| self.entry.key(), |
| self.entry.get(), |
| ) |
| } |
| } |
| |
| #[unstable(feature = "map_try_insert", issue = "82766")] |
| impl<'a, K: core::fmt::Debug + Ord, V: core::fmt::Debug> core::error::Error |
| for crate::collections::btree_map::OccupiedError<'a, K, V> |
| { |
| #[allow(deprecated)] |
| fn description(&self) -> &str { |
| "key already exists" |
| } |
| } |
| |
| impl<'a, K: Ord, V, A: Allocator + Clone> Entry<'a, K, V, A> { |
| /// Ensures a value is in the entry by inserting the default if empty, and returns |
| /// a mutable reference to the value in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// map.entry("poneyland").or_insert(12); |
| /// |
| /// assert_eq!(map["poneyland"], 12); |
| /// ``` |
| #[stable(feature = "rust1", since = "1.0.0")] |
| pub fn or_insert(self, default: V) -> &'a mut V { |
| match self { |
| Occupied(entry) => entry.into_mut(), |
| Vacant(entry) => entry.insert(default), |
| } |
| } |
| |
| /// Ensures a value is in the entry by inserting the result of the default function if empty, |
| /// and returns a mutable reference to the value in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// |
| /// let mut map: BTreeMap<&str, String> = BTreeMap::new(); |
| /// let s = "hoho".to_string(); |
| /// |
| /// map.entry("poneyland").or_insert_with(|| s); |
| /// |
| /// assert_eq!(map["poneyland"], "hoho".to_string()); |
| /// ``` |
| #[stable(feature = "rust1", since = "1.0.0")] |
| pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V { |
| match self { |
| Occupied(entry) => entry.into_mut(), |
| Vacant(entry) => entry.insert(default()), |
| } |
| } |
| |
| /// Ensures a value is in the entry by inserting, if empty, the result of the default function. |
| /// This method allows for generating key-derived values for insertion by providing the default |
| /// function a reference to the key that was moved during the `.entry(key)` method call. |
| /// |
| /// The reference to the moved key is provided so that cloning or copying the key is |
| /// unnecessary, unlike with `.or_insert_with(|| ... )`. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// |
| /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count()); |
| /// |
| /// assert_eq!(map["poneyland"], 9); |
| /// ``` |
| #[inline] |
| #[stable(feature = "or_insert_with_key", since = "1.50.0")] |
| pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V { |
| match self { |
| Occupied(entry) => entry.into_mut(), |
| Vacant(entry) => { |
| let value = default(entry.key()); |
| entry.insert(value) |
| } |
| } |
| } |
| |
| /// Returns a reference to this entry's key. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); |
| /// ``` |
| #[stable(feature = "map_entry_keys", since = "1.10.0")] |
| pub fn key(&self) -> &K { |
| match *self { |
| Occupied(ref entry) => entry.key(), |
| Vacant(ref entry) => entry.key(), |
| } |
| } |
| |
| /// Provides in-place mutable access to an occupied entry before any |
| /// potential inserts into the map. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// |
| /// map.entry("poneyland") |
| /// .and_modify(|e| { *e += 1 }) |
| /// .or_insert(42); |
| /// assert_eq!(map["poneyland"], 42); |
| /// |
| /// map.entry("poneyland") |
| /// .and_modify(|e| { *e += 1 }) |
| /// .or_insert(42); |
| /// assert_eq!(map["poneyland"], 43); |
| /// ``` |
| #[stable(feature = "entry_and_modify", since = "1.26.0")] |
| pub fn and_modify<F>(self, f: F) -> Self |
| where |
| F: FnOnce(&mut V), |
| { |
| match self { |
| Occupied(mut entry) => { |
| f(entry.get_mut()); |
| Occupied(entry) |
| } |
| Vacant(entry) => Vacant(entry), |
| } |
| } |
| } |
| |
| impl<'a, K: Ord, V: Default, A: Allocator + Clone> Entry<'a, K, V, A> { |
| #[stable(feature = "entry_or_default", since = "1.28.0")] |
| /// Ensures a value is in the entry by inserting the default value if empty, |
| /// and returns a mutable reference to the value in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// |
| /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new(); |
| /// map.entry("poneyland").or_default(); |
| /// |
| /// assert_eq!(map["poneyland"], None); |
| /// ``` |
| pub fn or_default(self) -> &'a mut V { |
| match self { |
| Occupied(entry) => entry.into_mut(), |
| Vacant(entry) => entry.insert(Default::default()), |
| } |
| } |
| } |
| |
| impl<'a, K: Ord, V, A: Allocator + Clone> VacantEntry<'a, K, V, A> { |
| /// Gets a reference to the key that would be used when inserting a value |
| /// through the VacantEntry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); |
| /// ``` |
| #[stable(feature = "map_entry_keys", since = "1.10.0")] |
| pub fn key(&self) -> &K { |
| &self.key |
| } |
| |
| /// Take ownership of the key. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// use std::collections::btree_map::Entry; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// |
| /// if let Entry::Vacant(v) = map.entry("poneyland") { |
| /// v.into_key(); |
| /// } |
| /// ``` |
| #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")] |
| pub fn into_key(self) -> K { |
| self.key |
| } |
| |
| /// Sets the value of the entry with the `VacantEntry`'s key, |
| /// and returns a mutable reference to it. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// use std::collections::btree_map::Entry; |
| /// |
| /// let mut map: BTreeMap<&str, u32> = BTreeMap::new(); |
| /// |
| /// if let Entry::Vacant(o) = map.entry("poneyland") { |
| /// o.insert(37); |
| /// } |
| /// assert_eq!(map["poneyland"], 37); |
| /// ``` |
| #[stable(feature = "rust1", since = "1.0.0")] |
| pub fn insert(self, value: V) -> &'a mut V { |
| let out_ptr = match self.handle { |
| None => { |
| // SAFETY: There is no tree yet so no reference to it exists. |
| let map = unsafe { self.dormant_map.awaken() }; |
| let mut root = NodeRef::new_leaf(self.alloc.clone()); |
| let val_ptr = root.borrow_mut().push(self.key, value) as *mut V; |
| map.root = Some(root.forget_type()); |
| map.length = 1; |
| val_ptr |
| } |
| Some(handle) => match handle.insert_recursing(self.key, value, self.alloc.clone()) { |
| (None, val_ptr) => { |
| // SAFETY: We have consumed self.handle. |
| let map = unsafe { self.dormant_map.awaken() }; |
| map.length += 1; |
| val_ptr |
| } |
| (Some(ins), val_ptr) => { |
| drop(ins.left); |
| // SAFETY: We have consumed self.handle and dropped the |
| // remaining reference to the tree, ins.left. |
| let map = unsafe { self.dormant_map.awaken() }; |
| let root = map.root.as_mut().unwrap(); // same as ins.left |
| root.push_internal_level(self.alloc).push(ins.kv.0, ins.kv.1, ins.right); |
| map.length += 1; |
| val_ptr |
| } |
| }, |
| }; |
| // Now that we have finished growing the tree using borrowed references, |
| // dereference the pointer to a part of it, that we picked up along the way. |
| unsafe { &mut *out_ptr } |
| } |
| } |
| |
| impl<'a, K: Ord, V, A: Allocator + Clone> OccupiedEntry<'a, K, V, A> { |
| /// Gets a reference to the key in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// map.entry("poneyland").or_insert(12); |
| /// assert_eq!(map.entry("poneyland").key(), &"poneyland"); |
| /// ``` |
| #[must_use] |
| #[stable(feature = "map_entry_keys", since = "1.10.0")] |
| pub fn key(&self) -> &K { |
| self.handle.reborrow().into_kv().0 |
| } |
| |
| /// Take ownership of the key and value from the map. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// use std::collections::btree_map::Entry; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// map.entry("poneyland").or_insert(12); |
| /// |
| /// if let Entry::Occupied(o) = map.entry("poneyland") { |
| /// // We delete the entry from the map. |
| /// o.remove_entry(); |
| /// } |
| /// |
| /// // If now try to get the value, it will panic: |
| /// // println!("{}", map["poneyland"]); |
| /// ``` |
| #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")] |
| pub fn remove_entry(self) -> (K, V) { |
| self.remove_kv() |
| } |
| |
| /// Gets a reference to the value in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// use std::collections::btree_map::Entry; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// map.entry("poneyland").or_insert(12); |
| /// |
| /// if let Entry::Occupied(o) = map.entry("poneyland") { |
| /// assert_eq!(o.get(), &12); |
| /// } |
| /// ``` |
| #[must_use] |
| #[stable(feature = "rust1", since = "1.0.0")] |
| pub fn get(&self) -> &V { |
| self.handle.reborrow().into_kv().1 |
| } |
| |
| /// Gets a mutable reference to the value in the entry. |
| /// |
| /// If you need a reference to the `OccupiedEntry` that may outlive the |
| /// destruction of the `Entry` value, see [`into_mut`]. |
| /// |
| /// [`into_mut`]: OccupiedEntry::into_mut |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// use std::collections::btree_map::Entry; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// map.entry("poneyland").or_insert(12); |
| /// |
| /// assert_eq!(map["poneyland"], 12); |
| /// if let Entry::Occupied(mut o) = map.entry("poneyland") { |
| /// *o.get_mut() += 10; |
| /// assert_eq!(*o.get(), 22); |
| /// |
| /// // We can use the same Entry multiple times. |
| /// *o.get_mut() += 2; |
| /// } |
| /// assert_eq!(map["poneyland"], 24); |
| /// ``` |
| #[stable(feature = "rust1", since = "1.0.0")] |
| pub fn get_mut(&mut self) -> &mut V { |
| self.handle.kv_mut().1 |
| } |
| |
| /// Converts the entry into a mutable reference to its value. |
| /// |
| /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`]. |
| /// |
| /// [`get_mut`]: OccupiedEntry::get_mut |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// use std::collections::btree_map::Entry; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// map.entry("poneyland").or_insert(12); |
| /// |
| /// assert_eq!(map["poneyland"], 12); |
| /// if let Entry::Occupied(o) = map.entry("poneyland") { |
| /// *o.into_mut() += 10; |
| /// } |
| /// assert_eq!(map["poneyland"], 22); |
| /// ``` |
| #[must_use = "`self` will be dropped if the result is not used"] |
| #[stable(feature = "rust1", since = "1.0.0")] |
| pub fn into_mut(self) -> &'a mut V { |
| self.handle.into_val_mut() |
| } |
| |
| /// Sets the value of the entry with the `OccupiedEntry`'s key, |
| /// and returns the entry's old value. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// use std::collections::btree_map::Entry; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// map.entry("poneyland").or_insert(12); |
| /// |
| /// if let Entry::Occupied(mut o) = map.entry("poneyland") { |
| /// assert_eq!(o.insert(15), 12); |
| /// } |
| /// assert_eq!(map["poneyland"], 15); |
| /// ``` |
| #[stable(feature = "rust1", since = "1.0.0")] |
| pub fn insert(&mut self, value: V) -> V { |
| mem::replace(self.get_mut(), value) |
| } |
| |
| /// Takes the value of the entry out of the map, and returns it. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use std::collections::BTreeMap; |
| /// use std::collections::btree_map::Entry; |
| /// |
| /// let mut map: BTreeMap<&str, usize> = BTreeMap::new(); |
| /// map.entry("poneyland").or_insert(12); |
| /// |
| /// if let Entry::Occupied(o) = map.entry("poneyland") { |
| /// assert_eq!(o.remove(), 12); |
| /// } |
| /// // If we try to get "poneyland"'s value, it'll panic: |
| /// // println!("{}", map["poneyland"]); |
| /// ``` |
| #[stable(feature = "rust1", since = "1.0.0")] |
| pub fn remove(self) -> V { |
| self.remove_kv().1 |
| } |
| |
| // Body of `remove_entry`, probably separate because the name reflects the returned pair. |
| pub(super) fn remove_kv(self) -> (K, V) { |
| let mut emptied_internal_root = false; |
| let (old_kv, _) = |
| self.handle.remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone()); |
| // 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(self.alloc); |
| } |
| old_kv |
| } |
| } |