alloc/collections/btree/map/
entry.rs

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