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: There is no tree yet so no reference to it exists.
 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.
 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 dropped the
 336                     // remaining reference to the tree, ins.left.
 337                     let map = unsafe { self.dormant_map.awaken() };
 338                     let root = map.root.as_mut().unwrap(); // same as ins.left
 339                     root.push_internal_level().push(ins.kv.0, ins.kv.1, ins.right);
 340                     map.length += 1;
 341                     val_ptr
 342                 }
 343             },
 344         };
 345         // Now that we have finished growing the tree using borrowed references,
 346         // dereference the pointer to a part of it, that we picked up along the way.
 347         unsafe { &mut *out_ptr }
 348     }
 349 }
 350
 351 impl<'a, K: Ord, V> OccupiedEntry<'a, K, V> {
 352     /// Gets a reference to the key in the entry.
 353     ///
 354     /// # Examples
 355     ///
 356     /// ```
 357     /// use std::collections::BTreeMap;
 358     ///
 359     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 360     /// map.entry("poneyland").or_insert(12);
 361     /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
 362     /// ```
 363     #[must_use]
 364     #[stable(feature = "map_entry_keys", since = "1.10.0")]
 365     pub fn key(&self) -> &K {
 366         self.handle.reborrow().into_kv().0
 367     }
 368
 369     /// Take ownership of the key and value from the map.
 370     ///
 371     /// # Examples
 372     ///
 373     /// ```
 374     /// use std::collections::BTreeMap;
 375     /// use std::collections::btree_map::Entry;
 376     ///
 377     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 378     /// map.entry("poneyland").or_insert(12);
 379     ///
 380     /// if let Entry::Occupied(o) = map.entry("poneyland") {
 381     ///     // We delete the entry from the map.
 382     ///     o.remove_entry();
 383     /// }
 384     ///
 385     /// // If now try to get the value, it will panic:
 386     /// // println!("{}", map["poneyland"]);
 387     /// ```
 388     #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
 389     pub fn remove_entry(self) -> (K, V) {
 390         self.remove_kv()
 391     }
 392
 393     /// Gets a reference to the value in the entry.
 394     ///
 395     /// # Examples
 396     ///
 397     /// ```
 398     /// use std::collections::BTreeMap;
 399     /// use std::collections::btree_map::Entry;
 400     ///
 401     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 402     /// map.entry("poneyland").or_insert(12);
 403     ///
 404     /// if let Entry::Occupied(o) = map.entry("poneyland") {
 405     ///     assert_eq!(o.get(), &12);
 406     /// }
 407     /// ```
 408     #[must_use]
 409     #[stable(feature = "rust1", since = "1.0.0")]
 410     pub fn get(&self) -> &V {
 411         self.handle.reborrow().into_kv().1
 412     }
 413
 414     /// Gets a mutable reference to the value in the entry.
 415     ///
 416     /// If you need a reference to the `OccupiedEntry` that may outlive the
 417     /// destruction of the `Entry` value, see [`into_mut`].
 418     ///
 419     /// [`into_mut`]: OccupiedEntry::into_mut
 420     ///
 421     /// # Examples
 422     ///
 423     /// ```
 424     /// use std::collections::BTreeMap;
 425     /// use std::collections::btree_map::Entry;
 426     ///
 427     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 428     /// map.entry("poneyland").or_insert(12);
 429     ///
 430     /// assert_eq!(map["poneyland"], 12);
 431     /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
 432     ///     *o.get_mut() += 10;
 433     ///     assert_eq!(*o.get(), 22);
 434     ///
 435     ///     // We can use the same Entry multiple times.
 436     ///     *o.get_mut() += 2;
 437     /// }
 438     /// assert_eq!(map["poneyland"], 24);
 439     /// ```
 440     #[stable(feature = "rust1", since = "1.0.0")]
 441     pub fn get_mut(&mut self) -> &mut V {
 442         self.handle.kv_mut().1
 443     }
 444
 445     /// Converts the entry into a mutable reference to its value.
 446     ///
 447     /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
 448     ///
 449     /// [`get_mut`]: OccupiedEntry::get_mut
 450     ///
 451     /// # Examples
 452     ///
 453     /// ```
 454     /// use std::collections::BTreeMap;
 455     /// use std::collections::btree_map::Entry;
 456     ///
 457     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 458     /// map.entry("poneyland").or_insert(12);
 459     ///
 460     /// assert_eq!(map["poneyland"], 12);
 461     /// if let Entry::Occupied(o) = map.entry("poneyland") {
 462     ///     *o.into_mut() += 10;
 463     /// }
 464     /// assert_eq!(map["poneyland"], 22);
 465     /// ```
 466     #[must_use = "`self` will be dropped if the result is not used"]
 467     #[stable(feature = "rust1", since = "1.0.0")]
 468     pub fn into_mut(self) -> &'a mut V {
 469         self.handle.into_val_mut()
 470     }
 471
 472     /// Sets the value of the entry with the `OccupiedEntry`'s key,
 473     /// and returns the entry's old value.
 474     ///
 475     /// # Examples
 476     ///
 477     /// ```
 478     /// use std::collections::BTreeMap;
 479     /// use std::collections::btree_map::Entry;
 480     ///
 481     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 482     /// map.entry("poneyland").or_insert(12);
 483     ///
 484     /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
 485     ///     assert_eq!(o.insert(15), 12);
 486     /// }
 487     /// assert_eq!(map["poneyland"], 15);
 488     /// ```
 489     #[stable(feature = "rust1", since = "1.0.0")]
 490     pub fn insert(&mut self, value: V) -> V {
 491         mem::replace(self.get_mut(), value)
 492     }
 493
 494     /// Takes the value of the entry out of the map, and returns it.
 495     ///
 496     /// # Examples
 497     ///
 498     /// ```
 499     /// use std::collections::BTreeMap;
 500     /// use std::collections::btree_map::Entry;
 501     ///
 502     /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
 503     /// map.entry("poneyland").or_insert(12);
 504     ///
 505     /// if let Entry::Occupied(o) = map.entry("poneyland") {
 506     ///     assert_eq!(o.remove(), 12);
 507     /// }
 508     /// // If we try to get "poneyland"'s value, it'll panic:
 509     /// // println!("{}", map["poneyland"]);
 510     /// ```
 511     #[stable(feature = "rust1", since = "1.0.0")]
 512     pub fn remove(self) -> V {
 513         self.remove_kv().1
 514     }
 515
 516     // Body of `remove_entry`, probably separate because the name reflects the returned pair.
 517     pub(super) fn remove_kv(self) -> (K, V) {
 518         let mut emptied_internal_root = false;
 519         let (old_kv, _) = self.handle.remove_kv_tracking(|| emptied_internal_root = true);
 520         // SAFETY: we consumed the intermediate root borrow, `self.handle`.
 521         let map = unsafe { self.dormant_map.awaken() };
 522         map.length -= 1;
 523         if emptied_internal_root {
 524             let root = map.root.as_mut().unwrap();
 525             root.pop_internal_level();
 526         }
 527         old_kv
 528     }
 529 }