library/alloc/src/collections/btree/map/entry.rs

   1 use core::fmt::{self, Debug};
   2 use core::marker::PhantomData;
   3 use core::mem;
   4
   5 use super::super::borrow::DormantMutRef;
   6 use super::super::node::{marker, Handle, NodeRef};
   7 use super::BTreeMap;
   8
   9 use Entry::*;
  10
  11 /// A view into a single entry in a map, which may either be vacant or occupied.
  12 ///
  13 /// This `enum` is constructed from the [`entry`] method on [`BTreeMap`].
  14 ///
  15 /// [`entry`]: BTreeMap::entry
  16 #[stable(feature = "rust1", since = "1.0.0")]
  17 #[cfg_attr(not(test), rustc_diagnostic_item = "BTreeEntry")]
  18 pub enum Entry<'a, K: 'a, V: 'a> {
  19     /// A vacant entry.
  20     #[stable(feature = "rust1", since = "1.0.0")]
  21     Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>),
  22
  23     /// An occupied entry.
  24     #[stable(feature = "rust1", since = "1.0.0")]
  25     Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>),
  26 }
  27
  28 #[stable(feature = "debug_btree_map", since = "1.12.0")]
  29 impl<K: Debug + Ord, V: Debug> Debug for Entry<'_, K, V> {
  30     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  31         match *self {
  32             Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
  33             Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
  34         }
  35     }
  36 }
  37
  38 /// A view into a vacant entry in a `BTreeMap`.
  39 /// It is part of the [`Entry`] enum.
  40 #[stable(feature = "rust1", since = "1.0.0")]
  41 pub struct VacantEntry<'a, K: 'a, V: 'a> {
  42     pub(super) key: K,
  43     /// `None` for a (empty) map without root
  44     pub(super) handle: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
  45     pub(super) dormant_map: DormantMutRef<'a, BTreeMap<K, V>>,
  46
  47     // Be invariant in `K` and `V`
  48     pub(super) _marker: PhantomData<&'a mut (K, V)>,
  49 }
  50
  51 #[stable(feature = "debug_btree_map", since = "1.12.0")]
  52 impl<K: Debug + Ord, V> Debug for VacantEntry<'_, K, V> {
  53     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  54         f.debug_tuple("VacantEntry").field(self.key()).finish()
  55     }
  56 }
  57
  58 /// A view into an occupied entry in a `BTreeMap`.
  59 /// It is part of the [`Entry`] enum.
  60 #[stable(feature = "rust1", since = "1.0.0")]
  61 pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
  62     pub(super) handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>,
  63     pub(super) dormant_map: DormantMutRef<'a, BTreeMap<K, V>>,
  64
  65     // Be invariant in `K` and `V`
  66     pub(super) _marker: PhantomData<&'a mut (K, V)>,
  67 }
  68
  69 #[stable(feature = "debug_btree_map", since = "1.12.0")]
  70 impl<K: Debug + Ord, V: Debug> Debug for OccupiedEntry<'_, K, V> {
  71     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  72         f.debug_struct("OccupiedEntry").field("key", self.key()).field("value", self.get()).finish()
  73     }
  74 }
  75
  76 /// The error returned by [`try_insert`](BTreeMap::try_insert) when the key already exists.
  77 ///
  78 /// Contains the occupied entry, and the value that was not inserted.
  79 #[unstable(feature = "map_try_insert", issue = "82766")]
  80 pub struct OccupiedError<'a, K: 'a, V: 'a> {
  81     /// The entry in the map that was already occupied.
  82     pub entry: OccupiedEntry<'a, K, V>,
  83     /// The value which was not inserted, because the entry was already occupied.
  84     pub value: V,
  85 }
  86
  87 #[unstable(feature = "map_try_insert", issue = "82766")]
  88 impl<K: Debug + Ord, V: Debug> Debug for OccupiedError<'_, K, V> {
  89     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  90         f.debug_struct("OccupiedError")
  91             .field("key", self.entry.key())
  92             .field("old_value", self.entry.get())
  93             .field("new_value", &self.value)
  94             .finish()
  95     }
  96 }
  97
  98 #[unstable(feature = "map_try_insert", issue = "82766")]
  99 impl<'a, K: Debug + Ord, V: Debug> fmt::Display for OccupiedError<'a, K, V> {
 100     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 101         write!(
 102             f,
 103             "failed to insert {:?}, key {:?} already exists with value {:?}",
 104             self.value,
 105             self.entry.key(),
 106             self.entry.get(),
 107         )
 108     }
 109 }
 110
 111 impl<'a, K: Ord, V> Entry<'a, K, V> {
 112     /// Ensures a value is in the entry by inserting the default if empty, and returns
 113     /// a mutable reference to the value in the entry.
 114     ///
 115     /// # Examples
 116     ///
 117     /// ```
 118     /// use std::collections::BTreeMap;
 119     ///
 120     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 121     /// map.entry("poneyland").or_insert(12);
 122     ///
 123     /// assert_eq!(map["poneyland"], 12);
 124     /// ```
 125     #[stable(feature = "rust1", since = "1.0.0")]
 126     pub fn or_insert(self, default: V) -> &'a mut V {
 127         match self {
 128             Occupied(entry) => entry.into_mut(),
 129             Vacant(entry) => entry.insert(default),
 130         }
 131     }
 132
 133     /// Ensures a value is in the entry by inserting the result of the default function if empty,
 134     /// and returns a mutable reference to the value in the entry.
 135     ///
 136     /// # Examples
 137     ///
 138     /// ```
 139     /// use std::collections::BTreeMap;
 140     ///
 141     /// let mut map: BTreeMap<&str, String> = BTreeMap::new();
 142     /// let s = "hoho".to_string();
 143     ///
 144     /// map.entry("poneyland").or_insert_with(|| s);
 145     ///
 146     /// assert_eq!(map["poneyland"], "hoho".to_string());
 147     /// ```
 148     #[stable(feature = "rust1", since = "1.0.0")]
 149     pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
 150         match self {
 151             Occupied(entry) => entry.into_mut(),
 152             Vacant(entry) => entry.insert(default()),
 153         }
 154     }
 155
 156     /// Ensures a value is in the entry by inserting, if empty, the result of the default function.
 157     /// This method allows for generating key-derived values for insertion by providing the default
 158     /// function a reference to the key that was moved during the `.entry(key)` method call.
 159     ///
 160     /// The reference to the moved key is provided so that cloning or copying the key is
 161     /// unnecessary, unlike with `.or_insert_with(|| ... )`.
 162     ///
 163     /// # Examples
 164     ///
 165     /// ```
 166     /// use std::collections::BTreeMap;
 167     ///
 168     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 169     ///
 170     /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
 171     ///
 172     /// assert_eq!(map["poneyland"], 9);
 173     /// ```
 174     #[inline]
 175     #[stable(feature = "or_insert_with_key", since = "1.50.0")]
 176     pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
 177         match self {
 178             Occupied(entry) => entry.into_mut(),
 179             Vacant(entry) => {
 180                 let value = default(entry.key());
 181                 entry.insert(value)
 182             }
 183         }
 184     }
 185
 186     /// Returns a reference to this entry's key.
 187     ///
 188     /// # Examples
 189     ///
 190     /// ```
 191     /// use std::collections::BTreeMap;
 192     ///
 193     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 194     /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
 195     /// ```
 196     #[stable(feature = "map_entry_keys", since = "1.10.0")]
 197     pub fn key(&self) -> &K {
 198         match *self {
 199             Occupied(ref entry) => entry.key(),
 200             Vacant(ref entry) => entry.key(),
 201         }
 202     }
 203
 204     /// Provides in-place mutable access to an occupied entry before any
 205     /// potential inserts into the map.
 206     ///
 207     /// # Examples
 208     ///
 209     /// ```
 210     /// use std::collections::BTreeMap;
 211     ///
 212     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 213     ///
 214     /// map.entry("poneyland")
 215     ///    .and_modify(|e| { *e += 1 })
 216     ///    .or_insert(42);
 217     /// assert_eq!(map["poneyland"], 42);
 218     ///
 219     /// map.entry("poneyland")
 220     ///    .and_modify(|e| { *e += 1 })
 221     ///    .or_insert(42);
 222     /// assert_eq!(map["poneyland"], 43);
 223     /// ```
 224     #[stable(feature = "entry_and_modify", since = "1.26.0")]
 225     pub fn and_modify<F>(self, f: F) -> Self
 226     where
 227         F: FnOnce(&mut V),
 228     {
 229         match self {
 230             Occupied(mut entry) => {
 231                 f(entry.get_mut());
 232                 Occupied(entry)
 233             }
 234             Vacant(entry) => Vacant(entry),
 235         }
 236     }
 237 }
 238
 239 impl<'a, K: Ord, V: Default> Entry<'a, K, V> {
 240     #[stable(feature = "entry_or_default", since = "1.28.0")]
 241     /// Ensures a value is in the entry by inserting the default value if empty,
 242     /// and returns a mutable reference to the value in the entry.
 243     ///
 244     /// # Examples
 245     ///
 246     /// ```
 247     /// use std::collections::BTreeMap;
 248     ///
 249     /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new();
 250     /// map.entry("poneyland").or_default();
 251     ///
 252     /// assert_eq!(map["poneyland"], None);
 253     /// ```
 254     pub fn or_default(self) -> &'a mut V {
 255         match self {
 256             Occupied(entry) => entry.into_mut(),
 257             Vacant(entry) => entry.insert(Default::default()),
 258         }
 259     }
 260 }
 261
 262 impl<'a, K: Ord, V> VacantEntry<'a, K, V> {
 263     /// Gets a reference to the key that would be used when inserting a value
 264     /// through the VacantEntry.
 265     ///
 266     /// # Examples
 267     ///
 268     /// ```
 269     /// use std::collections::BTreeMap;
 270     ///
 271     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 272     /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
 273     /// ```
 274     #[stable(feature = "map_entry_keys", since = "1.10.0")]
 275     pub fn key(&self) -> &K {
 276         &self.key
 277     }
 278
 279     /// Take ownership of the key.
 280     ///
 281     /// # Examples
 282     ///
 283     /// ```
 284     /// use std::collections::BTreeMap;
 285     /// use std::collections::btree_map::Entry;
 286     ///
 287     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 288     ///
 289     /// if let Entry::Vacant(v) = map.entry("poneyland") {
 290     ///     v.into_key();
 291     /// }
 292     /// ```
 293     #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
 294     pub fn into_key(self) -> K {
 295         self.key
 296     }
 297
 298     /// Sets the value of the entry with the `VacantEntry`'s key,
 299     /// and returns a mutable reference to it.
 300     ///
 301     /// # Examples
 302     ///
 303     /// ```
 304     /// use std::collections::BTreeMap;
 305     /// use std::collections::btree_map::Entry;
 306     ///
 307     /// let mut map: BTreeMap<&str, u32> = BTreeMap::new();
 308     ///
 309     /// if let Entry::Vacant(o) = map.entry("poneyland") {
 310     ///     o.insert(37);
 311     /// }
 312     /// assert_eq!(map["poneyland"], 37);
 313     /// ```
 314     #[stable(feature = "rust1", since = "1.0.0")]
 315     pub fn insert(self, value: V) -> &'a mut V {
 316         let out_ptr = match self.handle {
 317             None => {
 318                 // SAFETY: We have consumed self.handle and the reference returned.
 319                 let map = unsafe { self.dormant_map.awaken() };
 320                 let mut root = NodeRef::new_leaf();
 321                 let val_ptr = root.borrow_mut().push(self.key, value) as *mut V;
 322                 map.root = Some(root.forget_type());
 323                 map.length = 1;
 324                 val_ptr
 325             }
 326             Some(handle) => match handle.insert_recursing(self.key, value) {
 327                 (None, val_ptr) => {
 328                     // SAFETY: We have consumed self.handle and the handle returned.
 329                     let map = unsafe { self.dormant_map.awaken() };
 330                     map.length += 1;
 331                     val_ptr
 332                 }
 333                 (Some(ins), val_ptr) => {
 334                     drop(ins.left);
 335                     // SAFETY: We have consumed self.handle and the reference returned.
 336                     let map = unsafe { self.dormant_map.awaken() };
 337                     let root = map.root.as_mut().unwrap();
 338                     root.push_internal_level().push(ins.kv.0, ins.kv.1, ins.right);
 339                     map.length += 1;
 340                     val_ptr
 341                 }
 342             },
 343         };
 344         // Now that we have finished growing the tree using borrowed references,
 345         // dereference the pointer to a part of it, that we picked up along the way.
 346         unsafe { &mut *out_ptr }
 347     }
 348 }
 349
 350 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
 351     /// Gets a reference to the key in the entry.
 352     ///
 353     /// # Examples
 354     ///
 355     /// ```
 356     /// use std::collections::BTreeMap;
 357     ///
 358     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 359     /// map.entry("poneyland").or_insert(12);
 360     /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
 361     /// ```
 362     #[must_use]
 363     #[stable(feature = "map_entry_keys", since = "1.10.0")]
 364     pub fn key(&self) -> &K {
 365         self.handle.reborrow().into_kv().0
 366     }
 367
 368     /// Take ownership of the key and value from the map.
 369     ///
 370     /// # Examples
 371     ///
 372     /// ```
 373     /// use std::collections::BTreeMap;
 374     /// use std::collections::btree_map::Entry;
 375     ///
 376     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 377     /// map.entry("poneyland").or_insert(12);
 378     ///
 379     /// if let Entry::Occupied(o) = map.entry("poneyland") {
 380     ///     // We delete the entry from the map.
 381     ///     o.remove_entry();
 382     /// }
 383     ///
 384     /// // If now try to get the value, it will panic:
 385     /// // println!("{}", map["poneyland"]);
 386     /// ```
 387     #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
 388     pub fn remove_entry(self) -> (K, V) {
 389         self.remove_kv()
 390     }
 391
 392     /// Gets a reference to the value in the entry.
 393     ///
 394     /// # Examples
 395     ///
 396     /// ```
 397     /// use std::collections::BTreeMap;
 398     /// use std::collections::btree_map::Entry;
 399     ///
 400     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 401     /// map.entry("poneyland").or_insert(12);
 402     ///
 403     /// if let Entry::Occupied(o) = map.entry("poneyland") {
 404     ///     assert_eq!(o.get(), &12);
 405     /// }
 406     /// ```
 407     #[must_use]
 408     #[stable(feature = "rust1", since = "1.0.0")]
 409     pub fn get(&self) -> &V {
 410         self.handle.reborrow().into_kv().1
 411     }
 412
 413     /// Gets a mutable reference to the value in the entry.
 414     ///
 415     /// If you need a reference to the `OccupiedEntry` that may outlive the
 416     /// destruction of the `Entry` value, see [`into_mut`].
 417     ///
 418     /// [`into_mut`]: OccupiedEntry::into_mut
 419     ///
 420     /// # Examples
 421     ///
 422     /// ```
 423     /// use std::collections::BTreeMap;
 424     /// use std::collections::btree_map::Entry;
 425     ///
 426     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 427     /// map.entry("poneyland").or_insert(12);
 428     ///
 429     /// assert_eq!(map["poneyland"], 12);
 430     /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
 431     ///     *o.get_mut() += 10;
 432     ///     assert_eq!(*o.get(), 22);
 433     ///
 434     ///     // We can use the same Entry multiple times.
 435     ///     *o.get_mut() += 2;
 436     /// }
 437     /// assert_eq!(map["poneyland"], 24);
 438     /// ```
 439     #[stable(feature = "rust1", since = "1.0.0")]
 440     pub fn get_mut(&mut self) -> &mut V {
 441         self.handle.kv_mut().1
 442     }
 443
 444     /// Converts the entry into a mutable reference to its value.
 445     ///
 446     /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
 447     ///
 448     /// [`get_mut`]: OccupiedEntry::get_mut
 449     ///
 450     /// # Examples
 451     ///
 452     /// ```
 453     /// use std::collections::BTreeMap;
 454     /// use std::collections::btree_map::Entry;
 455     ///
 456     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 457     /// map.entry("poneyland").or_insert(12);
 458     ///
 459     /// assert_eq!(map["poneyland"], 12);
 460     /// if let Entry::Occupied(o) = map.entry("poneyland") {
 461     ///     *o.into_mut() += 10;
 462     /// }
 463     /// assert_eq!(map["poneyland"], 22);
 464     /// ```
 465     #[must_use = "`self` will be dropped if the result is not used"]
 466     #[stable(feature = "rust1", since = "1.0.0")]
 467     pub fn into_mut(self) -> &'a mut V {
 468         self.handle.into_val_mut()
 469     }
 470
 471     /// Sets the value of the entry with the `OccupiedEntry`'s key,
 472     /// and returns the entry's old value.
 473     ///
 474     /// # Examples
 475     ///
 476     /// ```
 477     /// use std::collections::BTreeMap;
 478     /// use std::collections::btree_map::Entry;
 479     ///
 480     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 481     /// map.entry("poneyland").or_insert(12);
 482     ///
 483     /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
 484     ///     assert_eq!(o.insert(15), 12);
 485     /// }
 486     /// assert_eq!(map["poneyland"], 15);
 487     /// ```
 488     #[stable(feature = "rust1", since = "1.0.0")]
 489     pub fn insert(&mut self, value: V) -> V {
 490         mem::replace(self.get_mut(), value)
 491     }
 492
 493     /// Takes the value of the entry out of the map, and returns it.
 494     ///
 495     /// # Examples
 496     ///
 497     /// ```
 498     /// use std::collections::BTreeMap;
 499     /// use std::collections::btree_map::Entry;
 500     ///
 501     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 502     /// map.entry("poneyland").or_insert(12);
 503     ///
 504     /// if let Entry::Occupied(o) = map.entry("poneyland") {
 505     ///     assert_eq!(o.remove(), 12);
 506     /// }
 507     /// // If we try to get "poneyland"'s value, it'll panic:
 508     /// // println!("{}", map["poneyland"]);
 509     /// ```
 510     #[stable(feature = "rust1", since = "1.0.0")]
 511     pub fn remove(self) -> V {
 512         self.remove_kv().1
 513     }
 514
 515     // Body of `remove_entry`, probably separate because the name reflects the returned pair.
 516     pub(super) fn remove_kv(self) -> (K, V) {
 517         let mut emptied_internal_root = false;
 518         let (old_kv, _) = self.handle.remove_kv_tracking(|| emptied_internal_root = true);
 519         // SAFETY: we consumed the intermediate root borrow, `self.handle`.
 520         let map = unsafe { self.dormant_map.awaken() };
 521         map.length -= 1;
 522         if emptied_internal_root {
 523             let root = map.root.as_mut().unwrap();
 524             root.pop_internal_level();
 525         }
 526         old_kv
 527     }
 528 }