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