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

Provided by KDAB

Privacy Policy