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: &VacantEntry<'_, K, V, A>) => f.debug_tuple(name:"Entry").field(v).finish(),
39 Occupied(ref o: &OccupiedEntry<'_, K, V, A>) => f.debug_tuple(name:"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(name:"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(name:"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&mut DebugStruct<'_, '_>.debug_struct("OccupiedError")
113 .field("key", self.entry.key())
114 .field("old_value", self.entry.get())
115 .field(name:"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: OccupiedEntry<'_, K, V, A>) => entry.into_mut(),
317 Vacant(entry: VacantEntry<'_, K, V, A>) => 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}
621