1use core::fmt::{self, Debug};
2use core::marker::PhantomData;
3use core::mem;
4
5use crate::alloc::{Allocator, Global};
6
7use super::super::borrow::DormantMutRef;
8use super::super::node::{marker, Handle, NodeRef};
9use super::BTreeMap;
10
11use Entry::*;
12
13/// A view into a single entry in a map, which may either be vacant or occupied.
14///
15/// This `enum` is constructed from the [`entry`] method on [`BTreeMap`].
16///
17/// [`entry`]: BTreeMap::entry
18#[stable(feature = "rust1", since = "1.0.0")]
19#[cfg_attr(not(test), rustc_diagnostic_item = "BTreeEntry")]
20pub enum Entry<
21 'a,
22 K: 'a,
23 V: 'a,
24 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
25> {
26 /// A vacant entry.
27 #[stable(feature = "rust1", since = "1.0.0")]
28 Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V, A>),
29
30 /// An occupied entry.
31 #[stable(feature = "rust1", since = "1.0.0")]
32 Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V, A>),
33}
34
35#[stable(feature = "debug_btree_map", since = "1.12.0")]
36impl<K: Debug + Ord, V: Debug, A: Allocator + Clone> Debug for Entry<'_, K, V, A> {
37 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
38 match *self {
39 Vacant(ref v: &VacantEntry<'_, K, V, A>) => f.debug_tuple(name:"Entry").field(v).finish(),
40 Occupied(ref o: &OccupiedEntry<'_, K, V, …>) => f.debug_tuple(name:"Entry").field(o).finish(),
41 }
42 }
43}
44
45/// A view into a vacant entry in a `BTreeMap`.
46/// It is part of the [`Entry`] enum.
47#[stable(feature = "rust1", since = "1.0.0")]
48pub struct VacantEntry<
49 'a,
50 K,
51 V,
52 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
53> {
54 pub(super) key: K,
55 /// `None` for a (empty) map without root
56 pub(super) handle: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
57 pub(super) dormant_map: DormantMutRef<'a, BTreeMap<K, V, A>>,
58
59 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
60 pub(super) alloc: A,
61
62 // Be invariant in `K` and `V`
63 pub(super) _marker: PhantomData<&'a mut (K, V)>,
64}
65
66#[stable(feature = "debug_btree_map", since = "1.12.0")]
67impl<K: Debug + Ord, V, A: Allocator + Clone> Debug for VacantEntry<'_, K, V, A> {
68 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
69 f.debug_tuple(name:"VacantEntry").field(self.key()).finish()
70 }
71}
72
73/// A view into an occupied entry in a `BTreeMap`.
74/// It is part of the [`Entry`] enum.
75#[stable(feature = "rust1", since = "1.0.0")]
76pub struct OccupiedEntry<
77 'a,
78 K,
79 V,
80 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
81> {
82 pub(super) handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>,
83 pub(super) dormant_map: DormantMutRef<'a, BTreeMap<K, V, A>>,
84
85 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
86 pub(super) alloc: A,
87
88 // Be invariant in `K` and `V`
89 pub(super) _marker: PhantomData<&'a mut (K, V)>,
90}
91
92#[stable(feature = "debug_btree_map", since = "1.12.0")]
93impl<K: Debug + Ord, V: Debug, A: Allocator + Clone> Debug for OccupiedEntry<'_, K, V, A> {
94 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
95 f.debug_struct("OccupiedEntry").field("key", self.key()).field(name:"value", self.get()).finish()
96 }
97}
98
99/// The error returned by [`try_insert`](BTreeMap::try_insert) when the key already exists.
100///
101/// Contains the occupied entry, and the value that was not inserted.
102#[unstable(feature = "map_try_insert", issue = "82766")]
103pub struct OccupiedError<'a, K: 'a, V: 'a, A: Allocator + Clone = Global> {
104 /// The entry in the map that was already occupied.
105 pub entry: OccupiedEntry<'a, K, V, A>,
106 /// The value which was not inserted, because the entry was already occupied.
107 pub value: V,
108}
109
110#[unstable(feature = "map_try_insert", issue = "82766")]
111impl<K: Debug + Ord, V: Debug, A: Allocator + Clone> Debug for OccupiedError<'_, K, V, A> {
112 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
113 f&mut DebugStruct<'_, '_>.debug_struct("OccupiedError")
114 .field("key", self.entry.key())
115 .field("old_value", self.entry.get())
116 .field(name:"new_value", &self.value)
117 .finish()
118 }
119}
120
121#[unstable(feature = "map_try_insert", issue = "82766")]
122impl<'a, K: Debug + Ord, V: Debug, A: Allocator + Clone> fmt::Display
123 for OccupiedError<'a, K, V, A>
124{
125 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
126 write!(
127 f,
128 "failed to insert {:?}, key {:?} already exists with value {:?}",
129 self.value,
130 self.entry.key(),
131 self.entry.get(),
132 )
133 }
134}
135
136#[unstable(feature = "map_try_insert", issue = "82766")]
137impl<'a, K: core::fmt::Debug + Ord, V: core::fmt::Debug> core::error::Error
138 for crate::collections::btree_map::OccupiedError<'a, K, V>
139{
140 #[allow(deprecated)]
141 fn description(&self) -> &str {
142 "key already exists"
143 }
144}
145
146impl<'a, K: Ord, V, A: Allocator + Clone> Entry<'a, K, V, A> {
147 /// Ensures a value is in the entry by inserting the default if empty, and returns
148 /// a mutable reference to the value in the entry.
149 ///
150 /// # Examples
151 ///
152 /// ```
153 /// use std::collections::BTreeMap;
154 ///
155 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
156 /// map.entry("poneyland").or_insert(12);
157 ///
158 /// assert_eq!(map["poneyland"], 12);
159 /// ```
160 #[stable(feature = "rust1", since = "1.0.0")]
161 pub fn or_insert(self, default: V) -> &'a mut V {
162 match self {
163 Occupied(entry) => entry.into_mut(),
164 Vacant(entry) => entry.insert(default),
165 }
166 }
167
168 /// Ensures a value is in the entry by inserting the result of the default function if empty,
169 /// and returns a mutable reference to the value in the entry.
170 ///
171 /// # Examples
172 ///
173 /// ```
174 /// use std::collections::BTreeMap;
175 ///
176 /// let mut map: BTreeMap<&str, String> = BTreeMap::new();
177 /// let s = "hoho".to_string();
178 ///
179 /// map.entry("poneyland").or_insert_with(|| s);
180 ///
181 /// assert_eq!(map["poneyland"], "hoho".to_string());
182 /// ```
183 #[stable(feature = "rust1", since = "1.0.0")]
184 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
185 match self {
186 Occupied(entry) => entry.into_mut(),
187 Vacant(entry) => entry.insert(default()),
188 }
189 }
190
191 /// Ensures a value is in the entry by inserting, if empty, the result of the default function.
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
274impl<'a, K: Ord, V: Default, A: Allocator + Clone> Entry<'a, K, V, A> {
275 #[stable(feature = "entry_or_default", since = "1.28.0")]
276 /// Ensures a value is in the entry by inserting the default value if empty,
277 /// and returns a mutable reference to the value in the entry.
278 ///
279 /// # Examples
280 ///
281 /// ```
282 /// use std::collections::BTreeMap;
283 ///
284 /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new();
285 /// map.entry("poneyland").or_default();
286 ///
287 /// assert_eq!(map["poneyland"], None);
288 /// ```
289 pub fn or_default(self) -> &'a mut V {
290 match self {
291 Occupied(entry: OccupiedEntry<'_, K, V, A>) => entry.into_mut(),
292 Vacant(entry: VacantEntry<'_, K, V, A>) => entry.insert(Default::default()),
293 }
294 }
295}
296
297impl<'a, K: Ord, V, A: Allocator + Clone> VacantEntry<'a, K, V, A> {
298 /// Gets a reference to the key that would be used when inserting a value
299 /// through the VacantEntry.
300 ///
301 /// # Examples
302 ///
303 /// ```
304 /// use std::collections::BTreeMap;
305 ///
306 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
307 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
308 /// ```
309 #[stable(feature = "map_entry_keys", since = "1.10.0")]
310 pub fn key(&self) -> &K {
311 &self.key
312 }
313
314 /// Take ownership of the key.
315 ///
316 /// # Examples
317 ///
318 /// ```
319 /// use std::collections::BTreeMap;
320 /// use std::collections::btree_map::Entry;
321 ///
322 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
323 ///
324 /// if let Entry::Vacant(v) = map.entry("poneyland") {
325 /// v.into_key();
326 /// }
327 /// ```
328 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
329 pub fn into_key(self) -> K {
330 self.key
331 }
332
333 /// Sets the value of the entry with the `VacantEntry`'s key,
334 /// and returns a mutable reference to it.
335 ///
336 /// # Examples
337 ///
338 /// ```
339 /// use std::collections::BTreeMap;
340 /// use std::collections::btree_map::Entry;
341 ///
342 /// let mut map: BTreeMap<&str, u32> = BTreeMap::new();
343 ///
344 /// if let Entry::Vacant(o) = map.entry("poneyland") {
345 /// o.insert(37);
346 /// }
347 /// assert_eq!(map["poneyland"], 37);
348 /// ```
349 #[stable(feature = "rust1", since = "1.0.0")]
350 #[rustc_confusables("push", "put")]
351 pub fn insert(mut self, value: V) -> &'a mut V {
352 let out_ptr = match self.handle {
353 None => {
354 // SAFETY: There is no tree yet so no reference to it exists.
355 let map = unsafe { self.dormant_map.awaken() };
356 let mut root = NodeRef::new_leaf(self.alloc.clone());
357 let val_ptr = root.borrow_mut().push(self.key, value);
358 map.root = Some(root.forget_type());
359 map.length = 1;
360 val_ptr
361 }
362 Some(handle) => {
363 let new_handle =
364 handle.insert_recursing(self.key, value, self.alloc.clone(), |ins| {
365 drop(ins.left);
366 // SAFETY: Pushing a new root node doesn't invalidate
367 // handles to existing nodes.
368 let map = unsafe { self.dormant_map.reborrow() };
369 let root = map.root.as_mut().unwrap(); // same as ins.left
370 root.push_internal_level(self.alloc).push(ins.kv.0, ins.kv.1, ins.right)
371 });
372
373 // Get the pointer to the value
374 let val_ptr = new_handle.into_val_mut();
375
376 // SAFETY: We have consumed self.handle.
377 let map = unsafe { self.dormant_map.awaken() };
378 map.length += 1;
379 val_ptr
380 }
381 };
382
383 // Now that we have finished growing the tree using borrowed references,
384 // dereference the pointer to a part of it, that we picked up along the way.
385 unsafe { &mut *out_ptr }
386 }
387}
388
389impl<'a, K: Ord, V, A: Allocator + Clone> OccupiedEntry<'a, K, V, A> {
390 /// Gets a reference to the key in the entry.
391 ///
392 /// # Examples
393 ///
394 /// ```
395 /// use std::collections::BTreeMap;
396 ///
397 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
398 /// map.entry("poneyland").or_insert(12);
399 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
400 /// ```
401 #[must_use]
402 #[stable(feature = "map_entry_keys", since = "1.10.0")]
403 pub fn key(&self) -> &K {
404 self.handle.reborrow().into_kv().0
405 }
406
407 /// Take ownership of the key and value from the map.
408 ///
409 /// # Examples
410 ///
411 /// ```
412 /// use std::collections::BTreeMap;
413 /// use std::collections::btree_map::Entry;
414 ///
415 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
416 /// map.entry("poneyland").or_insert(12);
417 ///
418 /// if let Entry::Occupied(o) = map.entry("poneyland") {
419 /// // We delete the entry from the map.
420 /// o.remove_entry();
421 /// }
422 ///
423 /// // If now try to get the value, it will panic:
424 /// // println!("{}", map["poneyland"]);
425 /// ```
426 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
427 pub fn remove_entry(self) -> (K, V) {
428 self.remove_kv()
429 }
430
431 /// Gets a reference to the value in the entry.
432 ///
433 /// # Examples
434 ///
435 /// ```
436 /// use std::collections::BTreeMap;
437 /// use std::collections::btree_map::Entry;
438 ///
439 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
440 /// map.entry("poneyland").or_insert(12);
441 ///
442 /// if let Entry::Occupied(o) = map.entry("poneyland") {
443 /// assert_eq!(o.get(), &12);
444 /// }
445 /// ```
446 #[must_use]
447 #[stable(feature = "rust1", since = "1.0.0")]
448 pub fn get(&self) -> &V {
449 self.handle.reborrow().into_kv().1
450 }
451
452 /// Gets a mutable reference to the value in the entry.
453 ///
454 /// If you need a reference to the `OccupiedEntry` that may outlive the
455 /// destruction of the `Entry` value, see [`into_mut`].
456 ///
457 /// [`into_mut`]: OccupiedEntry::into_mut
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 /// assert_eq!(map["poneyland"], 12);
469 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
470 /// *o.get_mut() += 10;
471 /// assert_eq!(*o.get(), 22);
472 ///
473 /// // We can use the same Entry multiple times.
474 /// *o.get_mut() += 2;
475 /// }
476 /// assert_eq!(map["poneyland"], 24);
477 /// ```
478 #[stable(feature = "rust1", since = "1.0.0")]
479 pub fn get_mut(&mut self) -> &mut V {
480 self.handle.kv_mut().1
481 }
482
483 /// Converts the entry into a mutable reference to its value.
484 ///
485 /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
486 ///
487 /// [`get_mut`]: OccupiedEntry::get_mut
488 ///
489 /// # Examples
490 ///
491 /// ```
492 /// use std::collections::BTreeMap;
493 /// use std::collections::btree_map::Entry;
494 ///
495 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
496 /// map.entry("poneyland").or_insert(12);
497 ///
498 /// assert_eq!(map["poneyland"], 12);
499 /// if let Entry::Occupied(o) = map.entry("poneyland") {
500 /// *o.into_mut() += 10;
501 /// }
502 /// assert_eq!(map["poneyland"], 22);
503 /// ```
504 #[must_use = "`self` will be dropped if the result is not used"]
505 #[stable(feature = "rust1", since = "1.0.0")]
506 pub fn into_mut(self) -> &'a mut V {
507 self.handle.into_val_mut()
508 }
509
510 /// Sets the value of the entry with the `OccupiedEntry`'s key,
511 /// and returns the entry's old value.
512 ///
513 /// # Examples
514 ///
515 /// ```
516 /// use std::collections::BTreeMap;
517 /// use std::collections::btree_map::Entry;
518 ///
519 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
520 /// map.entry("poneyland").or_insert(12);
521 ///
522 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
523 /// assert_eq!(o.insert(15), 12);
524 /// }
525 /// assert_eq!(map["poneyland"], 15);
526 /// ```
527 #[stable(feature = "rust1", since = "1.0.0")]
528 #[rustc_confusables("push", "put")]
529 pub fn insert(&mut self, value: V) -> V {
530 mem::replace(self.get_mut(), value)
531 }
532
533 /// Takes the value of the entry out of the map, and returns it.
534 ///
535 /// # Examples
536 ///
537 /// ```
538 /// use std::collections::BTreeMap;
539 /// use std::collections::btree_map::Entry;
540 ///
541 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
542 /// map.entry("poneyland").or_insert(12);
543 ///
544 /// if let Entry::Occupied(o) = map.entry("poneyland") {
545 /// assert_eq!(o.remove(), 12);
546 /// }
547 /// // If we try to get "poneyland"'s value, it'll panic:
548 /// // println!("{}", map["poneyland"]);
549 /// ```
550 #[stable(feature = "rust1", since = "1.0.0")]
551 #[rustc_confusables("delete", "take")]
552 pub fn remove(self) -> V {
553 self.remove_kv().1
554 }
555
556 // Body of `remove_entry`, probably separate because the name reflects the returned pair.
557 pub(super) fn remove_kv(self) -> (K, V) {
558 let mut emptied_internal_root = false;
559 let (old_kv, _) =
560 self.handle.remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone());
561 // SAFETY: we consumed the intermediate root borrow, `self.handle`.
562 let map = unsafe { self.dormant_map.awaken() };
563 map.length -= 1;
564 if emptied_internal_root {
565 let root = map.root.as_mut().unwrap();
566 root.pop_internal_level(self.alloc);
567 }
568 old_kv
569 }
570}
571