1 use self::RustcEntry::*; 2 use crate::map::{make_insert_hash, Drain, HashMap, IntoIter, Iter, IterMut}; 3 use crate::raw::{Allocator, Bucket, Global, RawTable}; 4 use core::fmt::{self, Debug}; 5 use core::hash::{BuildHasher, Hash}; 6 use core::mem; 7 8 impl<K, V, S, A> HashMap<K, V, S, A> 9 where 10 K: Eq + Hash, 11 S: BuildHasher, 12 A: Allocator + Clone, 13 { 14 /// Gets the given key's corresponding entry in the map for in-place manipulation. 15 /// 16 /// # Examples 17 /// 18 /// ``` 19 /// use hashbrown::HashMap; 20 /// 21 /// let mut letters = HashMap::new(); 22 /// 23 /// for ch in "a short treatise on fungi".chars() { 24 /// let counter = letters.rustc_entry(ch).or_insert(0); 25 /// *counter += 1; 26 /// } 27 /// 28 /// assert_eq!(letters[&'s'], 2); 29 /// assert_eq!(letters[&'t'], 3); 30 /// assert_eq!(letters[&'u'], 1); 31 /// assert_eq!(letters.get(&'y'), None); 32 /// ``` 33 #[cfg_attr(feature = "inline-more", inline)] rustc_entry(&mut self, key: K) -> RustcEntry<'_, K, V, A>34 pub fn rustc_entry(&mut self, key: K) -> RustcEntry<'_, K, V, A> { 35 let hash = make_insert_hash(&self.hash_builder, &key); 36 if let Some(elem) = self.table.find(hash, |q| q.0.eq(&key)) { 37 RustcEntry::Occupied(RustcOccupiedEntry { 38 key: Some(key), 39 elem, 40 table: &mut self.table, 41 }) 42 } else { 43 // Ideally we would put this in VacantEntry::insert, but Entry is not 44 // generic over the BuildHasher and adding a generic parameter would be 45 // a breaking change. 46 self.reserve(1); 47 48 RustcEntry::Vacant(RustcVacantEntry { 49 hash, 50 key, 51 table: &mut self.table, 52 }) 53 } 54 } 55 } 56 57 /// A view into a single entry in a map, which may either be vacant or occupied. 58 /// 59 /// This `enum` is constructed from the [`entry`] method on [`HashMap`]. 60 /// 61 /// [`HashMap`]: struct.HashMap.html 62 /// [`entry`]: struct.HashMap.html#method.rustc_entry 63 pub enum RustcEntry<'a, K, V, A = Global> 64 where 65 A: Allocator + Clone, 66 { 67 /// An occupied entry. 68 Occupied(RustcOccupiedEntry<'a, K, V, A>), 69 70 /// A vacant entry. 71 Vacant(RustcVacantEntry<'a, K, V, A>), 72 } 73 74 impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for RustcEntry<'_, K, V, A> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result75 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 76 match *self { 77 Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(), 78 Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(), 79 } 80 } 81 } 82 83 /// A view into an occupied entry in a `HashMap`. 84 /// It is part of the [`RustcEntry`] enum. 85 /// 86 /// [`RustcEntry`]: enum.RustcEntry.html 87 pub struct RustcOccupiedEntry<'a, K, V, A = Global> 88 where 89 A: Allocator + Clone, 90 { 91 key: Option<K>, 92 elem: Bucket<(K, V)>, 93 table: &'a mut RawTable<(K, V), A>, 94 } 95 96 unsafe impl<K, V, A> Send for RustcOccupiedEntry<'_, K, V, A> 97 where 98 K: Send, 99 V: Send, 100 A: Allocator + Clone + Send, 101 { 102 } 103 unsafe impl<K, V, A> Sync for RustcOccupiedEntry<'_, K, V, A> 104 where 105 K: Sync, 106 V: Sync, 107 A: Allocator + Clone + Sync, 108 { 109 } 110 111 impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for RustcOccupiedEntry<'_, K, V, A> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result112 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 113 f.debug_struct("OccupiedEntry") 114 .field("key", self.key()) 115 .field("value", self.get()) 116 .finish() 117 } 118 } 119 120 /// A view into a vacant entry in a `HashMap`. 121 /// It is part of the [`RustcEntry`] enum. 122 /// 123 /// [`RustcEntry`]: enum.RustcEntry.html 124 pub struct RustcVacantEntry<'a, K, V, A = Global> 125 where 126 A: Allocator + Clone, 127 { 128 hash: u64, 129 key: K, 130 table: &'a mut RawTable<(K, V), A>, 131 } 132 133 impl<K: Debug, V, A: Allocator + Clone> Debug for RustcVacantEntry<'_, K, V, A> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result134 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 135 f.debug_tuple("VacantEntry").field(self.key()).finish() 136 } 137 } 138 139 impl<'a, K, V, A: Allocator + Clone> RustcEntry<'a, K, V, A> { 140 /// Sets the value of the entry, and returns a RustcOccupiedEntry. 141 /// 142 /// # Examples 143 /// 144 /// ``` 145 /// use hashbrown::HashMap; 146 /// 147 /// let mut map: HashMap<&str, u32> = HashMap::new(); 148 /// let entry = map.entry("horseyland").insert(37); 149 /// 150 /// assert_eq!(entry.key(), &"horseyland"); 151 /// ``` insert(self, value: V) -> RustcOccupiedEntry<'a, K, V, A>152 pub fn insert(self, value: V) -> RustcOccupiedEntry<'a, K, V, A> { 153 match self { 154 Vacant(entry) => entry.insert_entry(value), 155 Occupied(mut entry) => { 156 entry.insert(value); 157 entry 158 } 159 } 160 } 161 162 /// Ensures a value is in the entry by inserting the default if empty, and returns 163 /// a mutable reference to the value in the entry. 164 /// 165 /// # Examples 166 /// 167 /// ``` 168 /// use hashbrown::HashMap; 169 /// 170 /// let mut map: HashMap<&str, u32> = HashMap::new(); 171 /// 172 /// map.rustc_entry("poneyland").or_insert(3); 173 /// assert_eq!(map["poneyland"], 3); 174 /// 175 /// *map.rustc_entry("poneyland").or_insert(10) *= 2; 176 /// assert_eq!(map["poneyland"], 6); 177 /// ``` 178 #[cfg_attr(feature = "inline-more", inline)] or_insert(self, default: V) -> &'a mut V where K: Hash,179 pub fn or_insert(self, default: V) -> &'a mut V 180 where 181 K: Hash, 182 { 183 match self { 184 Occupied(entry) => entry.into_mut(), 185 Vacant(entry) => entry.insert(default), 186 } 187 } 188 189 /// Ensures a value is in the entry by inserting the result of the default function if empty, 190 /// and returns a mutable reference to the value in the entry. 191 /// 192 /// # Examples 193 /// 194 /// ``` 195 /// use hashbrown::HashMap; 196 /// 197 /// let mut map: HashMap<&str, String> = HashMap::new(); 198 /// let s = "hoho".to_string(); 199 /// 200 /// map.rustc_entry("poneyland").or_insert_with(|| s); 201 /// 202 /// assert_eq!(map["poneyland"], "hoho".to_string()); 203 /// ``` 204 #[cfg_attr(feature = "inline-more", inline)] or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V where K: Hash,205 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V 206 where 207 K: Hash, 208 { 209 match self { 210 Occupied(entry) => entry.into_mut(), 211 Vacant(entry) => entry.insert(default()), 212 } 213 } 214 215 /// Returns a reference to this entry's key. 216 /// 217 /// # Examples 218 /// 219 /// ``` 220 /// use hashbrown::HashMap; 221 /// 222 /// let mut map: HashMap<&str, u32> = HashMap::new(); 223 /// assert_eq!(map.rustc_entry("poneyland").key(), &"poneyland"); 224 /// ``` 225 #[cfg_attr(feature = "inline-more", inline)] key(&self) -> &K226 pub fn key(&self) -> &K { 227 match *self { 228 Occupied(ref entry) => entry.key(), 229 Vacant(ref entry) => entry.key(), 230 } 231 } 232 233 /// Provides in-place mutable access to an occupied entry before any 234 /// potential inserts into the map. 235 /// 236 /// # Examples 237 /// 238 /// ``` 239 /// use hashbrown::HashMap; 240 /// 241 /// let mut map: HashMap<&str, u32> = HashMap::new(); 242 /// 243 /// map.rustc_entry("poneyland") 244 /// .and_modify(|e| { *e += 1 }) 245 /// .or_insert(42); 246 /// assert_eq!(map["poneyland"], 42); 247 /// 248 /// map.rustc_entry("poneyland") 249 /// .and_modify(|e| { *e += 1 }) 250 /// .or_insert(42); 251 /// assert_eq!(map["poneyland"], 43); 252 /// ``` 253 #[cfg_attr(feature = "inline-more", inline)] and_modify<F>(self, f: F) -> Self where F: FnOnce(&mut V),254 pub fn and_modify<F>(self, f: F) -> Self 255 where 256 F: FnOnce(&mut V), 257 { 258 match self { 259 Occupied(mut entry) => { 260 f(entry.get_mut()); 261 Occupied(entry) 262 } 263 Vacant(entry) => Vacant(entry), 264 } 265 } 266 } 267 268 impl<'a, K, V: Default, A: Allocator + Clone> RustcEntry<'a, K, V, A> { 269 /// Ensures a value is in the entry by inserting the default value if empty, 270 /// and returns a mutable reference to the value in the entry. 271 /// 272 /// # Examples 273 /// 274 /// ``` 275 /// # fn main() { 276 /// use hashbrown::HashMap; 277 /// 278 /// let mut map: HashMap<&str, Option<u32>> = HashMap::new(); 279 /// map.rustc_entry("poneyland").or_default(); 280 /// 281 /// assert_eq!(map["poneyland"], None); 282 /// # } 283 /// ``` 284 #[cfg_attr(feature = "inline-more", inline)] or_default(self) -> &'a mut V where K: Hash,285 pub fn or_default(self) -> &'a mut V 286 where 287 K: Hash, 288 { 289 match self { 290 Occupied(entry) => entry.into_mut(), 291 Vacant(entry) => entry.insert(Default::default()), 292 } 293 } 294 } 295 296 impl<'a, K, V, A: Allocator + Clone> RustcOccupiedEntry<'a, K, V, A> { 297 /// Gets a reference to the key in the entry. 298 /// 299 /// # Examples 300 /// 301 /// ``` 302 /// use hashbrown::HashMap; 303 /// 304 /// let mut map: HashMap<&str, u32> = HashMap::new(); 305 /// map.rustc_entry("poneyland").or_insert(12); 306 /// assert_eq!(map.rustc_entry("poneyland").key(), &"poneyland"); 307 /// ``` 308 #[cfg_attr(feature = "inline-more", inline)] key(&self) -> &K309 pub fn key(&self) -> &K { 310 unsafe { &self.elem.as_ref().0 } 311 } 312 313 /// Take the ownership of the key and value from the map. 314 /// 315 /// # Examples 316 /// 317 /// ``` 318 /// use hashbrown::HashMap; 319 /// use hashbrown::hash_map::RustcEntry; 320 /// 321 /// let mut map: HashMap<&str, u32> = HashMap::new(); 322 /// map.rustc_entry("poneyland").or_insert(12); 323 /// 324 /// if let RustcEntry::Occupied(o) = map.rustc_entry("poneyland") { 325 /// // We delete the entry from the map. 326 /// o.remove_entry(); 327 /// } 328 /// 329 /// assert_eq!(map.contains_key("poneyland"), false); 330 /// ``` 331 #[cfg_attr(feature = "inline-more", inline)] remove_entry(self) -> (K, V)332 pub fn remove_entry(self) -> (K, V) { 333 unsafe { self.table.remove(self.elem) } 334 } 335 336 /// Gets a reference to the value in the entry. 337 /// 338 /// # Examples 339 /// 340 /// ``` 341 /// use hashbrown::HashMap; 342 /// use hashbrown::hash_map::RustcEntry; 343 /// 344 /// let mut map: HashMap<&str, u32> = HashMap::new(); 345 /// map.rustc_entry("poneyland").or_insert(12); 346 /// 347 /// if let RustcEntry::Occupied(o) = map.rustc_entry("poneyland") { 348 /// assert_eq!(o.get(), &12); 349 /// } 350 /// ``` 351 #[cfg_attr(feature = "inline-more", inline)] get(&self) -> &V352 pub fn get(&self) -> &V { 353 unsafe { &self.elem.as_ref().1 } 354 } 355 356 /// Gets a mutable reference to the value in the entry. 357 /// 358 /// If you need a reference to the `RustcOccupiedEntry` which may outlive the 359 /// destruction of the `RustcEntry` value, see [`into_mut`]. 360 /// 361 /// [`into_mut`]: #method.into_mut 362 /// 363 /// # Examples 364 /// 365 /// ``` 366 /// use hashbrown::HashMap; 367 /// use hashbrown::hash_map::RustcEntry; 368 /// 369 /// let mut map: HashMap<&str, u32> = HashMap::new(); 370 /// map.rustc_entry("poneyland").or_insert(12); 371 /// 372 /// assert_eq!(map["poneyland"], 12); 373 /// if let RustcEntry::Occupied(mut o) = map.rustc_entry("poneyland") { 374 /// *o.get_mut() += 10; 375 /// assert_eq!(*o.get(), 22); 376 /// 377 /// // We can use the same RustcEntry multiple times. 378 /// *o.get_mut() += 2; 379 /// } 380 /// 381 /// assert_eq!(map["poneyland"], 24); 382 /// ``` 383 #[cfg_attr(feature = "inline-more", inline)] get_mut(&mut self) -> &mut V384 pub fn get_mut(&mut self) -> &mut V { 385 unsafe { &mut self.elem.as_mut().1 } 386 } 387 388 /// Converts the RustcOccupiedEntry into a mutable reference to the value in the entry 389 /// with a lifetime bound to the map itself. 390 /// 391 /// If you need multiple references to the `RustcOccupiedEntry`, see [`get_mut`]. 392 /// 393 /// [`get_mut`]: #method.get_mut 394 /// 395 /// # Examples 396 /// 397 /// ``` 398 /// use hashbrown::HashMap; 399 /// use hashbrown::hash_map::RustcEntry; 400 /// 401 /// let mut map: HashMap<&str, u32> = HashMap::new(); 402 /// map.rustc_entry("poneyland").or_insert(12); 403 /// 404 /// assert_eq!(map["poneyland"], 12); 405 /// if let RustcEntry::Occupied(o) = map.rustc_entry("poneyland") { 406 /// *o.into_mut() += 10; 407 /// } 408 /// 409 /// assert_eq!(map["poneyland"], 22); 410 /// ``` 411 #[cfg_attr(feature = "inline-more", inline)] into_mut(self) -> &'a mut V412 pub fn into_mut(self) -> &'a mut V { 413 unsafe { &mut self.elem.as_mut().1 } 414 } 415 416 /// Sets the value of the entry, and returns the entry's old value. 417 /// 418 /// # Examples 419 /// 420 /// ``` 421 /// use hashbrown::HashMap; 422 /// use hashbrown::hash_map::RustcEntry; 423 /// 424 /// let mut map: HashMap<&str, u32> = HashMap::new(); 425 /// map.rustc_entry("poneyland").or_insert(12); 426 /// 427 /// if let RustcEntry::Occupied(mut o) = map.rustc_entry("poneyland") { 428 /// assert_eq!(o.insert(15), 12); 429 /// } 430 /// 431 /// assert_eq!(map["poneyland"], 15); 432 /// ``` 433 #[cfg_attr(feature = "inline-more", inline)] insert(&mut self, mut value: V) -> V434 pub fn insert(&mut self, mut value: V) -> V { 435 let old_value = self.get_mut(); 436 mem::swap(&mut value, old_value); 437 value 438 } 439 440 /// Takes the value out of the entry, and returns it. 441 /// 442 /// # Examples 443 /// 444 /// ``` 445 /// use hashbrown::HashMap; 446 /// use hashbrown::hash_map::RustcEntry; 447 /// 448 /// let mut map: HashMap<&str, u32> = HashMap::new(); 449 /// map.rustc_entry("poneyland").or_insert(12); 450 /// 451 /// if let RustcEntry::Occupied(o) = map.rustc_entry("poneyland") { 452 /// assert_eq!(o.remove(), 12); 453 /// } 454 /// 455 /// assert_eq!(map.contains_key("poneyland"), false); 456 /// ``` 457 #[cfg_attr(feature = "inline-more", inline)] remove(self) -> V458 pub fn remove(self) -> V { 459 self.remove_entry().1 460 } 461 462 /// Replaces the entry, returning the old key and value. The new key in the hash map will be 463 /// the key used to create this entry. 464 /// 465 /// # Examples 466 /// 467 /// ``` 468 /// use hashbrown::hash_map::{RustcEntry, HashMap}; 469 /// use std::rc::Rc; 470 /// 471 /// let mut map: HashMap<Rc<String>, u32> = HashMap::new(); 472 /// map.insert(Rc::new("Stringthing".to_string()), 15); 473 /// 474 /// let my_key = Rc::new("Stringthing".to_string()); 475 /// 476 /// if let RustcEntry::Occupied(entry) = map.rustc_entry(my_key) { 477 /// // Also replace the key with a handle to our other key. 478 /// let (old_key, old_value): (Rc<String>, u32) = entry.replace_entry(16); 479 /// } 480 /// 481 /// ``` 482 #[cfg_attr(feature = "inline-more", inline)] replace_entry(self, value: V) -> (K, V)483 pub fn replace_entry(self, value: V) -> (K, V) { 484 let entry = unsafe { self.elem.as_mut() }; 485 486 let old_key = mem::replace(&mut entry.0, self.key.unwrap()); 487 let old_value = mem::replace(&mut entry.1, value); 488 489 (old_key, old_value) 490 } 491 492 /// Replaces the key in the hash map with the key used to create this entry. 493 /// 494 /// # Examples 495 /// 496 /// ``` 497 /// use hashbrown::hash_map::{RustcEntry, HashMap}; 498 /// use std::rc::Rc; 499 /// 500 /// let mut map: HashMap<Rc<String>, u32> = HashMap::new(); 501 /// let mut known_strings: Vec<Rc<String>> = Vec::new(); 502 /// 503 /// // Initialise known strings, run program, etc. 504 /// 505 /// reclaim_memory(&mut map, &known_strings); 506 /// 507 /// fn reclaim_memory(map: &mut HashMap<Rc<String>, u32>, known_strings: &[Rc<String>] ) { 508 /// for s in known_strings { 509 /// if let RustcEntry::Occupied(entry) = map.rustc_entry(s.clone()) { 510 /// // Replaces the entry's key with our version of it in `known_strings`. 511 /// entry.replace_key(); 512 /// } 513 /// } 514 /// } 515 /// ``` 516 #[cfg_attr(feature = "inline-more", inline)] replace_key(self) -> K517 pub fn replace_key(self) -> K { 518 let entry = unsafe { self.elem.as_mut() }; 519 mem::replace(&mut entry.0, self.key.unwrap()) 520 } 521 } 522 523 impl<'a, K, V, A: Allocator + Clone> RustcVacantEntry<'a, K, V, A> { 524 /// Gets a reference to the key that would be used when inserting a value 525 /// through the `RustcVacantEntry`. 526 /// 527 /// # Examples 528 /// 529 /// ``` 530 /// use hashbrown::HashMap; 531 /// 532 /// let mut map: HashMap<&str, u32> = HashMap::new(); 533 /// assert_eq!(map.rustc_entry("poneyland").key(), &"poneyland"); 534 /// ``` 535 #[cfg_attr(feature = "inline-more", inline)] key(&self) -> &K536 pub fn key(&self) -> &K { 537 &self.key 538 } 539 540 /// Take ownership of the key. 541 /// 542 /// # Examples 543 /// 544 /// ``` 545 /// use hashbrown::HashMap; 546 /// use hashbrown::hash_map::RustcEntry; 547 /// 548 /// let mut map: HashMap<&str, u32> = HashMap::new(); 549 /// 550 /// if let RustcEntry::Vacant(v) = map.rustc_entry("poneyland") { 551 /// v.into_key(); 552 /// } 553 /// ``` 554 #[cfg_attr(feature = "inline-more", inline)] into_key(self) -> K555 pub fn into_key(self) -> K { 556 self.key 557 } 558 559 /// Sets the value of the entry with the RustcVacantEntry's key, 560 /// and returns a mutable reference to it. 561 /// 562 /// # Examples 563 /// 564 /// ``` 565 /// use hashbrown::HashMap; 566 /// use hashbrown::hash_map::RustcEntry; 567 /// 568 /// let mut map: HashMap<&str, u32> = HashMap::new(); 569 /// 570 /// if let RustcEntry::Vacant(o) = map.rustc_entry("poneyland") { 571 /// o.insert(37); 572 /// } 573 /// assert_eq!(map["poneyland"], 37); 574 /// ``` 575 #[cfg_attr(feature = "inline-more", inline)] insert(self, value: V) -> &'a mut V576 pub fn insert(self, value: V) -> &'a mut V { 577 let bucket = self.table.insert_no_grow(self.hash, (self.key, value)); 578 unsafe { &mut bucket.as_mut().1 } 579 } 580 581 /// Sets the value of the entry with the RustcVacantEntry's key, 582 /// and returns a RustcOccupiedEntry. 583 /// 584 /// # Examples 585 /// 586 /// ``` 587 /// use hashbrown::HashMap; 588 /// use hashbrown::hash_map::RustcEntry; 589 /// 590 /// let mut map: HashMap<&str, u32> = HashMap::new(); 591 /// 592 /// if let RustcEntry::Vacant(v) = map.rustc_entry("poneyland") { 593 /// let o = v.insert_entry(37); 594 /// assert_eq!(o.get(), &37); 595 /// } 596 /// ``` 597 #[cfg_attr(feature = "inline-more", inline)] insert_entry(self, value: V) -> RustcOccupiedEntry<'a, K, V, A>598 pub fn insert_entry(self, value: V) -> RustcOccupiedEntry<'a, K, V, A> { 599 let bucket = self.table.insert_no_grow(self.hash, (self.key, value)); 600 RustcOccupiedEntry { 601 key: None, 602 elem: bucket, 603 table: self.table, 604 } 605 } 606 } 607 608 impl<K, V> IterMut<'_, K, V> { 609 /// Returns a iterator of references over the remaining items. 610 #[cfg_attr(feature = "inline-more", inline)] rustc_iter(&self) -> Iter<'_, K, V>611 pub fn rustc_iter(&self) -> Iter<'_, K, V> { 612 self.iter() 613 } 614 } 615 616 impl<K, V> IntoIter<K, V> { 617 /// Returns a iterator of references over the remaining items. 618 #[cfg_attr(feature = "inline-more", inline)] rustc_iter(&self) -> Iter<'_, K, V>619 pub fn rustc_iter(&self) -> Iter<'_, K, V> { 620 self.iter() 621 } 622 } 623 624 impl<K, V> Drain<'_, K, V> { 625 /// Returns a iterator of references over the remaining items. 626 #[cfg_attr(feature = "inline-more", inline)] rustc_iter(&self) -> Iter<'_, K, V>627 pub fn rustc_iter(&self) -> Iter<'_, K, V> { 628 self.iter() 629 } 630 } 631