| use crate::hash_map::{equivalent, make_hash, make_hasher}; |
| use crate::raw::{Allocator, Bucket, Global, RawTable}; |
| use crate::{Equivalent, HashMap}; |
| use core::fmt::{self, Debug}; |
| use core::hash::{BuildHasher, Hash}; |
| use core::mem; |
| |
| impl<K, V, S, A: Allocator> HashMap<K, V, S, A> { |
| /// Creates a raw entry builder for the `HashMap`. |
| /// |
| /// Raw entries provide the lowest level of control for searching and |
| /// manipulating a map. They must be manually initialized with a hash and |
| /// then manually searched. After this, insertions into a vacant entry |
| /// still require an owned key to be provided. |
| /// |
| /// Raw entries are useful for such exotic situations as: |
| /// |
| /// * Hash memoization |
| /// * Deferring the creation of an owned key until it is known to be required |
| /// * Using a search key that doesn't work with the Borrow trait |
| /// * Using custom comparison logic without newtype wrappers |
| /// |
| /// Because raw entries provide much more low-level control, it's much easier |
| /// to put the `HashMap` into an inconsistent state which, while memory-safe, |
| /// will cause the map to produce seemingly random results. Higher-level and |
| /// more foolproof APIs like `entry` should be preferred when possible. |
| /// |
| /// In particular, the hash used to initialized the raw entry must still be |
| /// consistent with the hash of the key that is ultimately stored in the entry. |
| /// This is because implementations of `HashMap` may need to recompute hashes |
| /// when resizing, at which point only the keys are available. |
| /// |
| /// Raw entries give mutable access to the keys. This must not be used |
| /// to modify how the key would compare or hash, as the map will not re-evaluate |
| /// where the key should go, meaning the keys may become "lost" if their |
| /// location does not reflect their state. For instance, if you change a key |
| /// so that the map now contains keys which compare equal, search may start |
| /// acting erratically, with two keys randomly masking each other. Implementations |
| /// are free to assume this doesn't happen (within the limits of memory-safety). |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map = HashMap::new(); |
| /// map.extend([("a", 100), ("b", 200), ("c", 300)]); |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// // Existing key (insert and update) |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => unreachable!(), |
| /// RawEntryMut::Occupied(mut view) => { |
| /// assert_eq!(view.get(), &100); |
| /// let v = view.get_mut(); |
| /// let new_v = (*v) * 10; |
| /// *v = new_v; |
| /// assert_eq!(view.insert(1111), 1000); |
| /// } |
| /// } |
| /// |
| /// assert_eq!(map[&"a"], 1111); |
| /// assert_eq!(map.len(), 3); |
| /// |
| /// // Existing key (take) |
| /// let hash = compute_hash(map.hasher(), &"c"); |
| /// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &"c") { |
| /// RawEntryMut::Vacant(_) => unreachable!(), |
| /// RawEntryMut::Occupied(view) => { |
| /// assert_eq!(view.remove_entry(), ("c", 300)); |
| /// } |
| /// } |
| /// assert_eq!(map.raw_entry().from_key(&"c"), None); |
| /// assert_eq!(map.len(), 2); |
| /// |
| /// // Nonexistent key (insert and update) |
| /// let key = "d"; |
| /// let hash = compute_hash(map.hasher(), &key); |
| /// match map.raw_entry_mut().from_hash(hash, |q| *q == key) { |
| /// RawEntryMut::Occupied(_) => unreachable!(), |
| /// RawEntryMut::Vacant(view) => { |
| /// let (k, value) = view.insert("d", 4000); |
| /// assert_eq!((*k, *value), ("d", 4000)); |
| /// *value = 40000; |
| /// } |
| /// } |
| /// assert_eq!(map[&"d"], 40000); |
| /// assert_eq!(map.len(), 3); |
| /// |
| /// match map.raw_entry_mut().from_hash(hash, |q| *q == key) { |
| /// RawEntryMut::Vacant(_) => unreachable!(), |
| /// RawEntryMut::Occupied(view) => { |
| /// assert_eq!(view.remove_entry(), ("d", 40000)); |
| /// } |
| /// } |
| /// assert_eq!(map.get(&"d"), None); |
| /// assert_eq!(map.len(), 2); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S, A> { |
| RawEntryBuilderMut { map: self } |
| } |
| |
| /// Creates a raw immutable entry builder for the `HashMap`. |
| /// |
| /// Raw entries provide the lowest level of control for searching and |
| /// manipulating a map. They must be manually initialized with a hash and |
| /// then manually searched. |
| /// |
| /// This is useful for |
| /// * Hash memoization |
| /// * Using a search key that doesn't work with the Borrow trait |
| /// * Using custom comparison logic without newtype wrappers |
| /// |
| /// Unless you are in such a situation, higher-level and more foolproof APIs like |
| /// `get` should be preferred. |
| /// |
| /// Immutable raw entries have very limited use; you might instead want `raw_entry_mut`. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::HashMap; |
| /// |
| /// let mut map = HashMap::new(); |
| /// map.extend([("a", 100), ("b", 200), ("c", 300)]); |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// for k in ["a", "b", "c", "d", "e", "f"] { |
| /// let hash = compute_hash(map.hasher(), k); |
| /// let v = map.get(&k).cloned(); |
| /// let kv = v.as_ref().map(|v| (&k, v)); |
| /// |
| /// println!("Key: {} and value: {:?}", k, v); |
| /// |
| /// assert_eq!(map.raw_entry().from_key(&k), kv); |
| /// assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv); |
| /// assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv); |
| /// } |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S, A> { |
| RawEntryBuilder { map: self } |
| } |
| } |
| |
| /// A builder for computing where in a [`HashMap`] a key-value pair would be stored. |
| /// |
| /// See the [`HashMap::raw_entry_mut`] docs for usage examples. |
| /// |
| /// [`HashMap::raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{RawEntryBuilderMut, RawEntryMut::Vacant, RawEntryMut::Occupied}; |
| /// use hashbrown::HashMap; |
| /// use core::hash::{BuildHasher, Hash}; |
| /// |
| /// let mut map = HashMap::new(); |
| /// map.extend([(1, 11), (2, 12), (3, 13), (4, 14), (5, 15), (6, 16)]); |
| /// assert_eq!(map.len(), 6); |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// let builder: RawEntryBuilderMut<_, _, _> = map.raw_entry_mut(); |
| /// |
| /// // Existing key |
| /// match builder.from_key(&6) { |
| /// Vacant(_) => unreachable!(), |
| /// Occupied(view) => assert_eq!(view.get(), &16), |
| /// } |
| /// |
| /// for key in 0..12 { |
| /// let hash = compute_hash(map.hasher(), &key); |
| /// let value = map.get(&key).cloned(); |
| /// let key_value = value.as_ref().map(|v| (&key, v)); |
| /// |
| /// println!("Key: {} and value: {:?}", key, value); |
| /// |
| /// match map.raw_entry_mut().from_key(&key) { |
| /// Occupied(mut o) => assert_eq!(Some(o.get_key_value()), key_value), |
| /// Vacant(_) => assert_eq!(value, None), |
| /// } |
| /// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &key) { |
| /// Occupied(mut o) => assert_eq!(Some(o.get_key_value()), key_value), |
| /// Vacant(_) => assert_eq!(value, None), |
| /// } |
| /// match map.raw_entry_mut().from_hash(hash, |q| *q == key) { |
| /// Occupied(mut o) => assert_eq!(Some(o.get_key_value()), key_value), |
| /// Vacant(_) => assert_eq!(value, None), |
| /// } |
| /// } |
| /// |
| /// assert_eq!(map.len(), 6); |
| /// ``` |
| pub struct RawEntryBuilderMut<'a, K, V, S, A: Allocator = Global> { |
| map: &'a mut HashMap<K, V, S, A>, |
| } |
| |
| /// A view into a single entry in a map, which may either be vacant or occupied. |
| /// |
| /// This is a lower-level version of [`Entry`]. |
| /// |
| /// This `enum` is constructed through the [`raw_entry_mut`] method on [`HashMap`], |
| /// then calling one of the methods of that [`RawEntryBuilderMut`]. |
| /// |
| /// [`HashMap`]: struct.HashMap.html |
| /// [`Entry`]: enum.Entry.html |
| /// [`raw_entry_mut`]: struct.HashMap.html#method.raw_entry_mut |
| /// [`RawEntryBuilderMut`]: struct.RawEntryBuilderMut.html |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut, RawOccupiedEntryMut}; |
| /// |
| /// let mut map = HashMap::new(); |
| /// map.extend([('a', 1), ('b', 2), ('c', 3)]); |
| /// assert_eq!(map.len(), 3); |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// // Existing key (insert) |
| /// let raw: RawEntryMut<_, _, _> = map.raw_entry_mut().from_key(&'a'); |
| /// let _raw_o: RawOccupiedEntryMut<_, _, _> = raw.insert('a', 10); |
| /// assert_eq!(map.len(), 3); |
| /// |
| /// // Nonexistent key (insert) |
| /// map.raw_entry_mut().from_key(&'d').insert('d', 40); |
| /// assert_eq!(map.len(), 4); |
| /// |
| /// // Existing key (or_insert) |
| /// let hash = compute_hash(map.hasher(), &'b'); |
| /// let kv = map |
| /// .raw_entry_mut() |
| /// .from_key_hashed_nocheck(hash, &'b') |
| /// .or_insert('b', 20); |
| /// assert_eq!(kv, (&mut 'b', &mut 2)); |
| /// *kv.1 = 20; |
| /// assert_eq!(map.len(), 4); |
| /// |
| /// // Nonexistent key (or_insert) |
| /// let hash = compute_hash(map.hasher(), &'e'); |
| /// let kv = map |
| /// .raw_entry_mut() |
| /// .from_key_hashed_nocheck(hash, &'e') |
| /// .or_insert('e', 50); |
| /// assert_eq!(kv, (&mut 'e', &mut 50)); |
| /// assert_eq!(map.len(), 5); |
| /// |
| /// // Existing key (or_insert_with) |
| /// let hash = compute_hash(map.hasher(), &'c'); |
| /// let kv = map |
| /// .raw_entry_mut() |
| /// .from_hash(hash, |q| q == &'c') |
| /// .or_insert_with(|| ('c', 30)); |
| /// assert_eq!(kv, (&mut 'c', &mut 3)); |
| /// *kv.1 = 30; |
| /// assert_eq!(map.len(), 5); |
| /// |
| /// // Nonexistent key (or_insert_with) |
| /// let hash = compute_hash(map.hasher(), &'f'); |
| /// let kv = map |
| /// .raw_entry_mut() |
| /// .from_hash(hash, |q| q == &'f') |
| /// .or_insert_with(|| ('f', 60)); |
| /// assert_eq!(kv, (&mut 'f', &mut 60)); |
| /// assert_eq!(map.len(), 6); |
| /// |
| /// println!("Our HashMap: {:?}", map); |
| /// |
| /// let mut vec: Vec<_> = map.iter().map(|(&k, &v)| (k, v)).collect(); |
| /// // The `Iter` iterator produces items in arbitrary order, so the |
| /// // items must be sorted to test them against a sorted array. |
| /// vec.sort_unstable(); |
| /// assert_eq!(vec, [('a', 10), ('b', 20), ('c', 30), ('d', 40), ('e', 50), ('f', 60)]); |
| /// ``` |
| pub enum RawEntryMut<'a, K, V, S, A: Allocator = Global> { |
| /// An occupied entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::{hash_map::RawEntryMut, HashMap}; |
| /// let mut map: HashMap<_, _> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => unreachable!(), |
| /// RawEntryMut::Occupied(_) => { } |
| /// } |
| /// ``` |
| Occupied(RawOccupiedEntryMut<'a, K, V, S, A>), |
| /// A vacant entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::{hash_map::RawEntryMut, HashMap}; |
| /// let mut map: HashMap<&str, i32> = HashMap::new(); |
| /// |
| /// match map.raw_entry_mut().from_key("a") { |
| /// RawEntryMut::Occupied(_) => unreachable!(), |
| /// RawEntryMut::Vacant(_) => { } |
| /// } |
| /// ``` |
| Vacant(RawVacantEntryMut<'a, K, V, S, A>), |
| } |
| |
| /// A view into an occupied entry in a `HashMap`. |
| /// It is part of the [`RawEntryMut`] enum. |
| /// |
| /// [`RawEntryMut`]: enum.RawEntryMut.html |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut, RawOccupiedEntryMut}; |
| /// |
| /// let mut map = HashMap::new(); |
| /// map.extend([("a", 10), ("b", 20), ("c", 30)]); |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// let _raw_o: RawOccupiedEntryMut<_, _, _> = map.raw_entry_mut().from_key(&"a").insert("a", 100); |
| /// assert_eq!(map.len(), 3); |
| /// |
| /// // Existing key (insert and update) |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => unreachable!(), |
| /// RawEntryMut::Occupied(mut view) => { |
| /// assert_eq!(view.get(), &100); |
| /// let v = view.get_mut(); |
| /// let new_v = (*v) * 10; |
| /// *v = new_v; |
| /// assert_eq!(view.insert(1111), 1000); |
| /// } |
| /// } |
| /// |
| /// assert_eq!(map[&"a"], 1111); |
| /// assert_eq!(map.len(), 3); |
| /// |
| /// // Existing key (take) |
| /// let hash = compute_hash(map.hasher(), &"c"); |
| /// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &"c") { |
| /// RawEntryMut::Vacant(_) => unreachable!(), |
| /// RawEntryMut::Occupied(view) => { |
| /// assert_eq!(view.remove_entry(), ("c", 30)); |
| /// } |
| /// } |
| /// assert_eq!(map.raw_entry().from_key(&"c"), None); |
| /// assert_eq!(map.len(), 2); |
| /// |
| /// let hash = compute_hash(map.hasher(), &"b"); |
| /// match map.raw_entry_mut().from_hash(hash, |q| *q == "b") { |
| /// RawEntryMut::Vacant(_) => unreachable!(), |
| /// RawEntryMut::Occupied(view) => { |
| /// assert_eq!(view.remove_entry(), ("b", 20)); |
| /// } |
| /// } |
| /// assert_eq!(map.get(&"b"), None); |
| /// assert_eq!(map.len(), 1); |
| /// ``` |
| pub struct RawOccupiedEntryMut<'a, K, V, S, A: Allocator = Global> { |
| elem: Bucket<(K, V)>, |
| table: &'a mut RawTable<(K, V), A>, |
| hash_builder: &'a S, |
| } |
| |
| unsafe impl<K, V, S, A> Send for RawOccupiedEntryMut<'_, K, V, S, A> |
| where |
| K: Send, |
| V: Send, |
| S: Send, |
| A: Send + Allocator, |
| { |
| } |
| unsafe impl<K, V, S, A> Sync for RawOccupiedEntryMut<'_, K, V, S, A> |
| where |
| K: Sync, |
| V: Sync, |
| S: Sync, |
| A: Sync + Allocator, |
| { |
| } |
| |
| /// A view into a vacant entry in a `HashMap`. |
| /// It is part of the [`RawEntryMut`] enum. |
| /// |
| /// [`RawEntryMut`]: enum.RawEntryMut.html |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut, RawVacantEntryMut}; |
| /// |
| /// let mut map = HashMap::<&str, i32>::new(); |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// let raw_v: RawVacantEntryMut<_, _, _> = match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(view) => view, |
| /// RawEntryMut::Occupied(_) => unreachable!(), |
| /// }; |
| /// raw_v.insert("a", 10); |
| /// assert!(map[&"a"] == 10 && map.len() == 1); |
| /// |
| /// // Nonexistent key (insert and update) |
| /// let hash = compute_hash(map.hasher(), &"b"); |
| /// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &"b") { |
| /// RawEntryMut::Occupied(_) => unreachable!(), |
| /// RawEntryMut::Vacant(view) => { |
| /// let (k, value) = view.insert("b", 2); |
| /// assert_eq!((*k, *value), ("b", 2)); |
| /// *value = 20; |
| /// } |
| /// } |
| /// assert!(map[&"b"] == 20 && map.len() == 2); |
| /// |
| /// let hash = compute_hash(map.hasher(), &"c"); |
| /// match map.raw_entry_mut().from_hash(hash, |q| *q == "c") { |
| /// RawEntryMut::Occupied(_) => unreachable!(), |
| /// RawEntryMut::Vacant(view) => { |
| /// assert_eq!(view.insert("c", 30), (&mut "c", &mut 30)); |
| /// } |
| /// } |
| /// assert!(map[&"c"] == 30 && map.len() == 3); |
| /// ``` |
| pub struct RawVacantEntryMut<'a, K, V, S, A: Allocator = Global> { |
| table: &'a mut RawTable<(K, V), A>, |
| hash_builder: &'a S, |
| } |
| |
| /// A builder for computing where in a [`HashMap`] a key-value pair would be stored. |
| /// |
| /// See the [`HashMap::raw_entry`] docs for usage examples. |
| /// |
| /// [`HashMap::raw_entry`]: struct.HashMap.html#method.raw_entry |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryBuilder}; |
| /// use core::hash::{BuildHasher, Hash}; |
| /// |
| /// let mut map = HashMap::new(); |
| /// map.extend([(1, 10), (2, 20), (3, 30)]); |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// for k in 0..6 { |
| /// let hash = compute_hash(map.hasher(), &k); |
| /// let v = map.get(&k).cloned(); |
| /// let kv = v.as_ref().map(|v| (&k, v)); |
| /// |
| /// println!("Key: {} and value: {:?}", k, v); |
| /// let builder: RawEntryBuilder<_, _, _> = map.raw_entry(); |
| /// assert_eq!(builder.from_key(&k), kv); |
| /// assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv); |
| /// assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv); |
| /// } |
| /// ``` |
| pub struct RawEntryBuilder<'a, K, V, S, A: Allocator = Global> { |
| map: &'a HashMap<K, V, S, A>, |
| } |
| |
| impl<'a, K, V, S, A: Allocator> RawEntryBuilderMut<'a, K, V, S, A> { |
| /// Creates a `RawEntryMut` from the given key. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = HashMap::new(); |
| /// let key = "a"; |
| /// let entry: RawEntryMut<&str, u32, _> = map.raw_entry_mut().from_key(&key); |
| /// entry.insert(key, 100); |
| /// assert_eq!(map[&"a"], 100); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| #[allow(clippy::wrong_self_convention)] |
| pub fn from_key<Q>(self, k: &Q) -> RawEntryMut<'a, K, V, S, A> |
| where |
| S: BuildHasher, |
| Q: Hash + Equivalent<K> + ?Sized, |
| { |
| let hash = make_hash::<Q, S>(&self.map.hash_builder, k); |
| self.from_key_hashed_nocheck(hash, k) |
| } |
| |
| /// Creates a `RawEntryMut` from the given key and its hash. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// let mut map: HashMap<&str, u32> = HashMap::new(); |
| /// let key = "a"; |
| /// let hash = compute_hash(map.hasher(), &key); |
| /// let entry: RawEntryMut<&str, u32, _> = map.raw_entry_mut().from_key_hashed_nocheck(hash, &key); |
| /// entry.insert(key, 100); |
| /// assert_eq!(map[&"a"], 100); |
| /// ``` |
| #[inline] |
| #[allow(clippy::wrong_self_convention)] |
| pub fn from_key_hashed_nocheck<Q>(self, hash: u64, k: &Q) -> RawEntryMut<'a, K, V, S, A> |
| where |
| Q: Equivalent<K> + ?Sized, |
| { |
| self.from_hash(hash, equivalent(k)) |
| } |
| } |
| |
| impl<'a, K, V, S, A: Allocator> RawEntryBuilderMut<'a, K, V, S, A> { |
| /// Creates a `RawEntryMut` from the given hash and matching function. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// let mut map: HashMap<&str, u32> = HashMap::new(); |
| /// let key = "a"; |
| /// let hash = compute_hash(map.hasher(), &key); |
| /// let entry: RawEntryMut<&str, u32, _> = map.raw_entry_mut().from_hash(hash, |k| k == &key); |
| /// entry.insert(key, 100); |
| /// assert_eq!(map[&"a"], 100); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| #[allow(clippy::wrong_self_convention)] |
| pub fn from_hash<F>(self, hash: u64, is_match: F) -> RawEntryMut<'a, K, V, S, A> |
| where |
| for<'b> F: FnMut(&'b K) -> bool, |
| { |
| self.search(hash, is_match) |
| } |
| |
| #[cfg_attr(feature = "inline-more", inline)] |
| fn search<F>(self, hash: u64, mut is_match: F) -> RawEntryMut<'a, K, V, S, A> |
| where |
| for<'b> F: FnMut(&'b K) -> bool, |
| { |
| match self.map.table.find(hash, |(k, _)| is_match(k)) { |
| Some(elem) => RawEntryMut::Occupied(RawOccupiedEntryMut { |
| elem, |
| table: &mut self.map.table, |
| hash_builder: &self.map.hash_builder, |
| }), |
| None => RawEntryMut::Vacant(RawVacantEntryMut { |
| table: &mut self.map.table, |
| hash_builder: &self.map.hash_builder, |
| }), |
| } |
| } |
| } |
| |
| impl<'a, K, V, S, A: Allocator> RawEntryBuilder<'a, K, V, S, A> { |
| /// Access an immutable entry by key. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::HashMap; |
| /// |
| /// let map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// let key = "a"; |
| /// assert_eq!(map.raw_entry().from_key(&key), Some((&"a", &100))); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| #[allow(clippy::wrong_self_convention)] |
| pub fn from_key<Q>(self, k: &Q) -> Option<(&'a K, &'a V)> |
| where |
| S: BuildHasher, |
| Q: Hash + Equivalent<K> + ?Sized, |
| { |
| let hash = make_hash::<Q, S>(&self.map.hash_builder, k); |
| self.from_key_hashed_nocheck(hash, k) |
| } |
| |
| /// Access an immutable entry by a key and its hash. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::HashMap; |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// let map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// let key = "a"; |
| /// let hash = compute_hash(map.hasher(), &key); |
| /// assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &key), Some((&"a", &100))); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| #[allow(clippy::wrong_self_convention)] |
| pub fn from_key_hashed_nocheck<Q>(self, hash: u64, k: &Q) -> Option<(&'a K, &'a V)> |
| where |
| Q: Equivalent<K> + ?Sized, |
| { |
| self.from_hash(hash, equivalent(k)) |
| } |
| |
| #[cfg_attr(feature = "inline-more", inline)] |
| fn search<F>(self, hash: u64, mut is_match: F) -> Option<(&'a K, &'a V)> |
| where |
| F: FnMut(&K) -> bool, |
| { |
| match self.map.table.get(hash, |(k, _)| is_match(k)) { |
| Some((key, value)) => Some((key, value)), |
| None => None, |
| } |
| } |
| |
| /// Access an immutable entry by hash and matching function. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::HashMap; |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// let map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// let key = "a"; |
| /// let hash = compute_hash(map.hasher(), &key); |
| /// assert_eq!(map.raw_entry().from_hash(hash, |k| k == &key), Some((&"a", &100))); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| #[allow(clippy::wrong_self_convention)] |
| pub fn from_hash<F>(self, hash: u64, is_match: F) -> Option<(&'a K, &'a V)> |
| where |
| F: FnMut(&K) -> bool, |
| { |
| self.search(hash, is_match) |
| } |
| } |
| |
| impl<'a, K, V, S, A: Allocator> RawEntryMut<'a, K, V, S, A> { |
| /// Sets the value of the entry, and returns a `RawOccupiedEntryMut`. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::HashMap; |
| /// |
| /// let mut map: HashMap<&str, u32> = HashMap::new(); |
| /// let entry = map.raw_entry_mut().from_key("horseyland").insert("horseyland", 37); |
| /// |
| /// assert_eq!(entry.remove_entry(), ("horseyland", 37)); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn insert(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S, A> |
| where |
| K: Hash, |
| S: BuildHasher, |
| { |
| match self { |
| RawEntryMut::Occupied(mut entry) => { |
| entry.insert(value); |
| entry |
| } |
| RawEntryMut::Vacant(entry) => entry.insert_entry(key, value), |
| } |
| } |
| |
| /// Ensures a value is in the entry by inserting the default if empty, and returns |
| /// mutable references to the key and value in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::HashMap; |
| /// |
| /// let mut map: HashMap<&str, u32> = HashMap::new(); |
| /// |
| /// map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 3); |
| /// assert_eq!(map["poneyland"], 3); |
| /// |
| /// *map.raw_entry_mut().from_key("poneyland").or_insert("poneyland", 10).1 *= 2; |
| /// assert_eq!(map["poneyland"], 6); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn or_insert(self, default_key: K, default_val: V) -> (&'a mut K, &'a mut V) |
| where |
| K: Hash, |
| S: BuildHasher, |
| { |
| match self { |
| RawEntryMut::Occupied(entry) => entry.into_key_value(), |
| RawEntryMut::Vacant(entry) => entry.insert(default_key, default_val), |
| } |
| } |
| |
| /// Ensures a value is in the entry by inserting the result of the default function if empty, |
| /// and returns mutable references to the key and value in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::HashMap; |
| /// |
| /// let mut map: HashMap<&str, String> = HashMap::new(); |
| /// |
| /// map.raw_entry_mut().from_key("poneyland").or_insert_with(|| { |
| /// ("poneyland", "hoho".to_string()) |
| /// }); |
| /// |
| /// assert_eq!(map["poneyland"], "hoho".to_string()); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn or_insert_with<F>(self, default: F) -> (&'a mut K, &'a mut V) |
| where |
| F: FnOnce() -> (K, V), |
| K: Hash, |
| S: BuildHasher, |
| { |
| match self { |
| RawEntryMut::Occupied(entry) => entry.into_key_value(), |
| RawEntryMut::Vacant(entry) => { |
| let (k, v) = default(); |
| entry.insert(k, v) |
| } |
| } |
| } |
| |
| /// Provides in-place mutable access to an occupied entry before any |
| /// potential inserts into the map. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::HashMap; |
| /// |
| /// let mut map: HashMap<&str, u32> = HashMap::new(); |
| /// |
| /// map.raw_entry_mut() |
| /// .from_key("poneyland") |
| /// .and_modify(|_k, v| { *v += 1 }) |
| /// .or_insert("poneyland", 42); |
| /// assert_eq!(map["poneyland"], 42); |
| /// |
| /// map.raw_entry_mut() |
| /// .from_key("poneyland") |
| /// .and_modify(|_k, v| { *v += 1 }) |
| /// .or_insert("poneyland", 0); |
| /// assert_eq!(map["poneyland"], 43); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn and_modify<F>(self, f: F) -> Self |
| where |
| F: FnOnce(&mut K, &mut V), |
| { |
| match self { |
| RawEntryMut::Occupied(mut entry) => { |
| { |
| let (k, v) = entry.get_key_value_mut(); |
| f(k, v); |
| } |
| RawEntryMut::Occupied(entry) |
| } |
| RawEntryMut::Vacant(entry) => RawEntryMut::Vacant(entry), |
| } |
| } |
| |
| /// Provides shared access to the key and owned access to the value of |
| /// an occupied entry and allows to replace or remove it based on the |
| /// value of the returned option. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::HashMap; |
| /// use hashbrown::hash_map::RawEntryMut; |
| /// |
| /// let mut map: HashMap<&str, u32> = HashMap::new(); |
| /// |
| /// let entry = map |
| /// .raw_entry_mut() |
| /// .from_key("poneyland") |
| /// .and_replace_entry_with(|_k, _v| panic!()); |
| /// |
| /// match entry { |
| /// RawEntryMut::Vacant(_) => {}, |
| /// RawEntryMut::Occupied(_) => panic!(), |
| /// } |
| /// |
| /// map.insert("poneyland", 42); |
| /// |
| /// let entry = map |
| /// .raw_entry_mut() |
| /// .from_key("poneyland") |
| /// .and_replace_entry_with(|k, v| { |
| /// assert_eq!(k, &"poneyland"); |
| /// assert_eq!(v, 42); |
| /// Some(v + 1) |
| /// }); |
| /// |
| /// match entry { |
| /// RawEntryMut::Occupied(e) => { |
| /// assert_eq!(e.key(), &"poneyland"); |
| /// assert_eq!(e.get(), &43); |
| /// }, |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// } |
| /// |
| /// assert_eq!(map["poneyland"], 43); |
| /// |
| /// let entry = map |
| /// .raw_entry_mut() |
| /// .from_key("poneyland") |
| /// .and_replace_entry_with(|_k, _v| None); |
| /// |
| /// match entry { |
| /// RawEntryMut::Vacant(_) => {}, |
| /// RawEntryMut::Occupied(_) => panic!(), |
| /// } |
| /// |
| /// assert!(!map.contains_key("poneyland")); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn and_replace_entry_with<F>(self, f: F) -> Self |
| where |
| F: FnOnce(&K, V) -> Option<V>, |
| { |
| match self { |
| RawEntryMut::Occupied(entry) => entry.replace_entry_with(f), |
| RawEntryMut::Vacant(_) => self, |
| } |
| } |
| } |
| |
| impl<'a, K, V, S, A: Allocator> RawOccupiedEntryMut<'a, K, V, S, A> { |
| /// Gets a reference to the key in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(o) => assert_eq!(o.key(), &"a") |
| /// } |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn key(&self) -> &K { |
| unsafe { &self.elem.as_ref().0 } |
| } |
| |
| /// Gets a mutable reference to the key in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// use std::rc::Rc; |
| /// |
| /// let key_one = Rc::new("a"); |
| /// let key_two = Rc::new("a"); |
| /// |
| /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new(); |
| /// map.insert(key_one.clone(), 10); |
| /// |
| /// assert_eq!(map[&key_one], 10); |
| /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1); |
| /// |
| /// match map.raw_entry_mut().from_key(&key_one) { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(mut o) => { |
| /// *o.key_mut() = key_two.clone(); |
| /// } |
| /// } |
| /// assert_eq!(map[&key_two], 10); |
| /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn key_mut(&mut self) -> &mut K { |
| unsafe { &mut self.elem.as_mut().0 } |
| } |
| |
| /// Converts the entry into a mutable reference to the key in the entry |
| /// with a lifetime bound to the map itself. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// use std::rc::Rc; |
| /// |
| /// let key_one = Rc::new("a"); |
| /// let key_two = Rc::new("a"); |
| /// |
| /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new(); |
| /// map.insert(key_one.clone(), 10); |
| /// |
| /// assert_eq!(map[&key_one], 10); |
| /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1); |
| /// |
| /// let inside_key: &mut Rc<&str>; |
| /// |
| /// match map.raw_entry_mut().from_key(&key_one) { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(o) => inside_key = o.into_key(), |
| /// } |
| /// *inside_key = key_two.clone(); |
| /// |
| /// assert_eq!(map[&key_two], 10); |
| /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn into_key(self) -> &'a mut K { |
| unsafe { &mut self.elem.as_mut().0 } |
| } |
| |
| /// Gets a reference to the value in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(o) => assert_eq!(o.get(), &100), |
| /// } |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn get(&self) -> &V { |
| unsafe { &self.elem.as_ref().1 } |
| } |
| |
| /// Converts the `OccupiedEntry` into a mutable reference to the value in the entry |
| /// with a lifetime bound to the map itself. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// let value: &mut u32; |
| /// |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(o) => value = o.into_mut(), |
| /// } |
| /// *value += 900; |
| /// |
| /// assert_eq!(map[&"a"], 1000); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn into_mut(self) -> &'a mut V { |
| unsafe { &mut self.elem.as_mut().1 } |
| } |
| |
| /// Gets a mutable reference to the value in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(mut o) => *o.get_mut() += 900, |
| /// } |
| /// |
| /// assert_eq!(map[&"a"], 1000); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn get_mut(&mut self) -> &mut V { |
| unsafe { &mut self.elem.as_mut().1 } |
| } |
| |
| /// Gets a reference to the key and value in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(o) => assert_eq!(o.get_key_value(), (&"a", &100)), |
| /// } |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn get_key_value(&self) -> (&K, &V) { |
| unsafe { |
| let (key, value) = self.elem.as_ref(); |
| (key, value) |
| } |
| } |
| |
| /// Gets a mutable reference to the key and value in the entry. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// use std::rc::Rc; |
| /// |
| /// let key_one = Rc::new("a"); |
| /// let key_two = Rc::new("a"); |
| /// |
| /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new(); |
| /// map.insert(key_one.clone(), 10); |
| /// |
| /// assert_eq!(map[&key_one], 10); |
| /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1); |
| /// |
| /// match map.raw_entry_mut().from_key(&key_one) { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(mut o) => { |
| /// let (inside_key, inside_value) = o.get_key_value_mut(); |
| /// *inside_key = key_two.clone(); |
| /// *inside_value = 100; |
| /// } |
| /// } |
| /// assert_eq!(map[&key_two], 100); |
| /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn get_key_value_mut(&mut self) -> (&mut K, &mut V) { |
| unsafe { |
| let &mut (ref mut key, ref mut value) = self.elem.as_mut(); |
| (key, value) |
| } |
| } |
| |
| /// Converts the `OccupiedEntry` into a mutable reference to the key and value in the entry |
| /// with a lifetime bound to the map itself. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// use std::rc::Rc; |
| /// |
| /// let key_one = Rc::new("a"); |
| /// let key_two = Rc::new("a"); |
| /// |
| /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new(); |
| /// map.insert(key_one.clone(), 10); |
| /// |
| /// assert_eq!(map[&key_one], 10); |
| /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1); |
| /// |
| /// let inside_key: &mut Rc<&str>; |
| /// let inside_value: &mut u32; |
| /// match map.raw_entry_mut().from_key(&key_one) { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(o) => { |
| /// let tuple = o.into_key_value(); |
| /// inside_key = tuple.0; |
| /// inside_value = tuple.1; |
| /// } |
| /// } |
| /// *inside_key = key_two.clone(); |
| /// *inside_value = 100; |
| /// assert_eq!(map[&key_two], 100); |
| /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn into_key_value(self) -> (&'a mut K, &'a mut V) { |
| unsafe { |
| let &mut (ref mut key, ref mut value) = self.elem.as_mut(); |
| (key, value) |
| } |
| } |
| |
| /// Sets the value of the entry, and returns the entry's old value. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(mut o) => assert_eq!(o.insert(1000), 100), |
| /// } |
| /// |
| /// assert_eq!(map[&"a"], 1000); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn insert(&mut self, value: V) -> V { |
| mem::replace(self.get_mut(), value) |
| } |
| |
| /// Sets the value of the entry, and returns the entry's old value. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// use std::rc::Rc; |
| /// |
| /// let key_one = Rc::new("a"); |
| /// let key_two = Rc::new("a"); |
| /// |
| /// let mut map: HashMap<Rc<&str>, u32> = HashMap::new(); |
| /// map.insert(key_one.clone(), 10); |
| /// |
| /// assert_eq!(map[&key_one], 10); |
| /// assert!(Rc::strong_count(&key_one) == 2 && Rc::strong_count(&key_two) == 1); |
| /// |
| /// match map.raw_entry_mut().from_key(&key_one) { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(mut o) => { |
| /// let old_key = o.insert_key(key_two.clone()); |
| /// assert!(Rc::ptr_eq(&old_key, &key_one)); |
| /// } |
| /// } |
| /// assert_eq!(map[&key_two], 10); |
| /// assert!(Rc::strong_count(&key_one) == 1 && Rc::strong_count(&key_two) == 2); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn insert_key(&mut self, key: K) -> K { |
| mem::replace(self.key_mut(), key) |
| } |
| |
| /// Takes the value out of the entry, and returns it. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(o) => assert_eq!(o.remove(), 100), |
| /// } |
| /// assert_eq!(map.get(&"a"), None); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn remove(self) -> V { |
| self.remove_entry().1 |
| } |
| |
| /// Take the ownership of the key and value from the map. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(o) => assert_eq!(o.remove_entry(), ("a", 100)), |
| /// } |
| /// assert_eq!(map.get(&"a"), None); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn remove_entry(self) -> (K, V) { |
| unsafe { self.table.remove(self.elem).0 } |
| } |
| |
| /// Provides shared access to the key and owned access to the value of |
| /// the entry and allows to replace or remove it based on the |
| /// value of the returned option. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// let raw_entry = match map.raw_entry_mut().from_key(&"a") { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(o) => o.replace_entry_with(|k, v| { |
| /// assert_eq!(k, &"a"); |
| /// assert_eq!(v, 100); |
| /// Some(v + 900) |
| /// }), |
| /// }; |
| /// let raw_entry = match raw_entry { |
| /// RawEntryMut::Vacant(_) => panic!(), |
| /// RawEntryMut::Occupied(o) => o.replace_entry_with(|k, v| { |
| /// assert_eq!(k, &"a"); |
| /// assert_eq!(v, 1000); |
| /// None |
| /// }), |
| /// }; |
| /// match raw_entry { |
| /// RawEntryMut::Vacant(_) => { }, |
| /// RawEntryMut::Occupied(_) => panic!(), |
| /// }; |
| /// assert_eq!(map.get(&"a"), None); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn replace_entry_with<F>(self, f: F) -> RawEntryMut<'a, K, V, S, A> |
| where |
| F: FnOnce(&K, V) -> Option<V>, |
| { |
| unsafe { |
| let still_occupied = self |
| .table |
| .replace_bucket_with(self.elem.clone(), |(key, value)| { |
| f(&key, value).map(|new_value| (key, new_value)) |
| }); |
| |
| if still_occupied { |
| RawEntryMut::Occupied(self) |
| } else { |
| RawEntryMut::Vacant(RawVacantEntryMut { |
| table: self.table, |
| hash_builder: self.hash_builder, |
| }) |
| } |
| } |
| } |
| } |
| |
| impl<'a, K, V, S, A: Allocator> RawVacantEntryMut<'a, K, V, S, A> { |
| /// Sets the value of the entry with the `VacantEntry`'s key, |
| /// and returns a mutable reference to it. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// |
| /// match map.raw_entry_mut().from_key(&"c") { |
| /// RawEntryMut::Occupied(_) => panic!(), |
| /// RawEntryMut::Vacant(v) => assert_eq!(v.insert("c", 300), (&mut "c", &mut 300)), |
| /// } |
| /// |
| /// assert_eq!(map[&"c"], 300); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn insert(self, key: K, value: V) -> (&'a mut K, &'a mut V) |
| where |
| K: Hash, |
| S: BuildHasher, |
| { |
| let hash = make_hash::<K, S>(self.hash_builder, &key); |
| self.insert_hashed_nocheck(hash, key, value) |
| } |
| |
| /// Sets the value of the entry with the `VacantEntry`'s key, |
| /// and returns a mutable reference to it. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// fn compute_hash<K: Hash + ?Sized, S: BuildHasher>(hash_builder: &S, key: &K) -> u64 { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// |
| /// let mut map: HashMap<&str, u32> = [("a", 100), ("b", 200)].into(); |
| /// let key = "c"; |
| /// let hash = compute_hash(map.hasher(), &key); |
| /// |
| /// match map.raw_entry_mut().from_key_hashed_nocheck(hash, &key) { |
| /// RawEntryMut::Occupied(_) => panic!(), |
| /// RawEntryMut::Vacant(v) => assert_eq!( |
| /// v.insert_hashed_nocheck(hash, key, 300), |
| /// (&mut "c", &mut 300) |
| /// ), |
| /// } |
| /// |
| /// assert_eq!(map[&"c"], 300); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| #[allow(clippy::shadow_unrelated)] |
| pub fn insert_hashed_nocheck(self, hash: u64, key: K, value: V) -> (&'a mut K, &'a mut V) |
| where |
| K: Hash, |
| S: BuildHasher, |
| { |
| let &mut (ref mut k, ref mut v) = self.table.insert_entry( |
| hash, |
| (key, value), |
| make_hasher::<_, V, S>(self.hash_builder), |
| ); |
| (k, v) |
| } |
| |
| /// Set the value of an entry with a custom hasher function. |
| /// |
| /// # Examples |
| /// |
| /// ``` |
| /// use core::hash::{BuildHasher, Hash}; |
| /// use hashbrown::hash_map::{HashMap, RawEntryMut}; |
| /// |
| /// fn make_hasher<K, S>(hash_builder: &S) -> impl Fn(&K) -> u64 + '_ |
| /// where |
| /// K: Hash + ?Sized, |
| /// S: BuildHasher, |
| /// { |
| /// move |key: &K| { |
| /// use core::hash::Hasher; |
| /// let mut state = hash_builder.build_hasher(); |
| /// key.hash(&mut state); |
| /// state.finish() |
| /// } |
| /// } |
| /// |
| /// let mut map: HashMap<&str, u32> = HashMap::new(); |
| /// let key = "a"; |
| /// let hash_builder = map.hasher().clone(); |
| /// let hash = make_hasher(&hash_builder)(&key); |
| /// |
| /// match map.raw_entry_mut().from_hash(hash, |q| q == &key) { |
| /// RawEntryMut::Occupied(_) => panic!(), |
| /// RawEntryMut::Vacant(v) => assert_eq!( |
| /// v.insert_with_hasher(hash, key, 100, make_hasher(&hash_builder)), |
| /// (&mut "a", &mut 100) |
| /// ), |
| /// } |
| /// map.extend([("b", 200), ("c", 300), ("d", 400), ("e", 500), ("f", 600)]); |
| /// assert_eq!(map[&"a"], 100); |
| /// ``` |
| #[cfg_attr(feature = "inline-more", inline)] |
| pub fn insert_with_hasher<H>( |
| self, |
| hash: u64, |
| key: K, |
| value: V, |
| hasher: H, |
| ) -> (&'a mut K, &'a mut V) |
| where |
| H: Fn(&K) -> u64, |
| { |
| let &mut (ref mut k, ref mut v) = self |
| .table |
| .insert_entry(hash, (key, value), |x| hasher(&x.0)); |
| (k, v) |
| } |
| |
| #[cfg_attr(feature = "inline-more", inline)] |
| fn insert_entry(self, key: K, value: V) -> RawOccupiedEntryMut<'a, K, V, S, A> |
| where |
| K: Hash, |
| S: BuildHasher, |
| { |
| let hash = make_hash::<K, S>(self.hash_builder, &key); |
| let elem = self.table.insert( |
| hash, |
| (key, value), |
| make_hasher::<_, V, S>(self.hash_builder), |
| ); |
| RawOccupiedEntryMut { |
| elem, |
| table: self.table, |
| hash_builder: self.hash_builder, |
| } |
| } |
| } |
| |
| impl<K, V, S, A: Allocator> Debug for RawEntryBuilderMut<'_, K, V, S, A> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| f.debug_struct("RawEntryBuilder").finish() |
| } |
| } |
| |
| impl<K: Debug, V: Debug, S, A: Allocator> Debug for RawEntryMut<'_, K, V, S, A> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| match *self { |
| RawEntryMut::Vacant(ref v) => f.debug_tuple("RawEntry").field(v).finish(), |
| RawEntryMut::Occupied(ref o) => f.debug_tuple("RawEntry").field(o).finish(), |
| } |
| } |
| } |
| |
| impl<K: Debug, V: Debug, S, A: Allocator> Debug for RawOccupiedEntryMut<'_, K, V, S, A> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| f.debug_struct("RawOccupiedEntryMut") |
| .field("key", self.key()) |
| .field("value", self.get()) |
| .finish() |
| } |
| } |
| |
| impl<K, V, S, A: Allocator> Debug for RawVacantEntryMut<'_, K, V, S, A> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| f.debug_struct("RawVacantEntryMut").finish() |
| } |
| } |
| |
| impl<K, V, S, A: Allocator> Debug for RawEntryBuilder<'_, K, V, S, A> { |
| fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| f.debug_struct("RawEntryBuilder").finish() |
| } |
| } |
| |
| #[cfg(test)] |
| mod test_map { |
| use super::HashMap; |
| use super::RawEntryMut; |
| |
| #[test] |
| fn test_raw_occupied_entry_replace_entry_with() { |
| let mut a = HashMap::new(); |
| |
| let key = "a key"; |
| let value = "an initial value"; |
| let new_value = "a new value"; |
| |
| let entry = a |
| .raw_entry_mut() |
| .from_key(&key) |
| .insert(key, value) |
| .replace_entry_with(|k, v| { |
| assert_eq!(k, &key); |
| assert_eq!(v, value); |
| Some(new_value) |
| }); |
| |
| match entry { |
| RawEntryMut::Occupied(e) => { |
| assert_eq!(e.key(), &key); |
| assert_eq!(e.get(), &new_value); |
| } |
| RawEntryMut::Vacant(_) => panic!(), |
| } |
| |
| assert_eq!(a[key], new_value); |
| assert_eq!(a.len(), 1); |
| |
| let entry = match a.raw_entry_mut().from_key(&key) { |
| RawEntryMut::Occupied(e) => e.replace_entry_with(|k, v| { |
| assert_eq!(k, &key); |
| assert_eq!(v, new_value); |
| None |
| }), |
| RawEntryMut::Vacant(_) => panic!(), |
| }; |
| |
| match entry { |
| RawEntryMut::Vacant(_) => {} |
| RawEntryMut::Occupied(_) => panic!(), |
| } |
| |
| assert!(!a.contains_key(key)); |
| assert_eq!(a.len(), 0); |
| } |
| |
| #[test] |
| fn test_raw_entry_and_replace_entry_with() { |
| let mut a = HashMap::new(); |
| |
| let key = "a key"; |
| let value = "an initial value"; |
| let new_value = "a new value"; |
| |
| let entry = a |
| .raw_entry_mut() |
| .from_key(&key) |
| .and_replace_entry_with(|_, _| panic!()); |
| |
| match entry { |
| RawEntryMut::Vacant(_) => {} |
| RawEntryMut::Occupied(_) => panic!(), |
| } |
| |
| a.insert(key, value); |
| |
| let entry = a |
| .raw_entry_mut() |
| .from_key(&key) |
| .and_replace_entry_with(|k, v| { |
| assert_eq!(k, &key); |
| assert_eq!(v, value); |
| Some(new_value) |
| }); |
| |
| match entry { |
| RawEntryMut::Occupied(e) => { |
| assert_eq!(e.key(), &key); |
| assert_eq!(e.get(), &new_value); |
| } |
| RawEntryMut::Vacant(_) => panic!(), |
| } |
| |
| assert_eq!(a[key], new_value); |
| assert_eq!(a.len(), 1); |
| |
| let entry = a |
| .raw_entry_mut() |
| .from_key(&key) |
| .and_replace_entry_with(|k, v| { |
| assert_eq!(k, &key); |
| assert_eq!(v, new_value); |
| None |
| }); |
| |
| match entry { |
| RawEntryMut::Vacant(_) => {} |
| RawEntryMut::Occupied(_) => panic!(), |
| } |
| |
| assert!(!a.contains_key(key)); |
| assert_eq!(a.len(), 0); |
| } |
| |
| #[test] |
| fn test_raw_entry() { |
| use super::RawEntryMut::{Occupied, Vacant}; |
| |
| let xs = [(1_i32, 10_i32), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; |
| |
| let mut map: HashMap<_, _> = xs.iter().copied().collect(); |
| |
| let compute_hash = |map: &HashMap<i32, i32>, k: i32| -> u64 { |
| super::make_hash::<i32, _>(map.hasher(), &k) |
| }; |
| |
| // Existing key (insert) |
| match map.raw_entry_mut().from_key(&1) { |
| Vacant(_) => unreachable!(), |
| Occupied(mut view) => { |
| assert_eq!(view.get(), &10); |
| assert_eq!(view.insert(100), 10); |
| } |
| } |
| let hash1 = compute_hash(&map, 1); |
| assert_eq!(map.raw_entry().from_key(&1).unwrap(), (&1, &100)); |
| assert_eq!( |
| map.raw_entry().from_hash(hash1, |k| *k == 1).unwrap(), |
| (&1, &100) |
| ); |
| assert_eq!( |
| map.raw_entry().from_key_hashed_nocheck(hash1, &1).unwrap(), |
| (&1, &100) |
| ); |
| assert_eq!(map.len(), 6); |
| |
| // Existing key (update) |
| match map.raw_entry_mut().from_key(&2) { |
| Vacant(_) => unreachable!(), |
| Occupied(mut view) => { |
| let v = view.get_mut(); |
| let new_v = (*v) * 10; |
| *v = new_v; |
| } |
| } |
| let hash2 = compute_hash(&map, 2); |
| assert_eq!(map.raw_entry().from_key(&2).unwrap(), (&2, &200)); |
| assert_eq!( |
| map.raw_entry().from_hash(hash2, |k| *k == 2).unwrap(), |
| (&2, &200) |
| ); |
| assert_eq!( |
| map.raw_entry().from_key_hashed_nocheck(hash2, &2).unwrap(), |
| (&2, &200) |
| ); |
| assert_eq!(map.len(), 6); |
| |
| // Existing key (take) |
| let hash3 = compute_hash(&map, 3); |
| match map.raw_entry_mut().from_key_hashed_nocheck(hash3, &3) { |
| Vacant(_) => unreachable!(), |
| Occupied(view) => { |
| assert_eq!(view.remove_entry(), (3, 30)); |
| } |
| } |
| assert_eq!(map.raw_entry().from_key(&3), None); |
| assert_eq!(map.raw_entry().from_hash(hash3, |k| *k == 3), None); |
| assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash3, &3), None); |
| assert_eq!(map.len(), 5); |
| |
| // Nonexistent key (insert) |
| match map.raw_entry_mut().from_key(&10) { |
| Occupied(_) => unreachable!(), |
| Vacant(view) => { |
| assert_eq!(view.insert(10, 1000), (&mut 10, &mut 1000)); |
| } |
| } |
| assert_eq!(map.raw_entry().from_key(&10).unwrap(), (&10, &1000)); |
| assert_eq!(map.len(), 6); |
| |
| // Ensure all lookup methods produce equivalent results. |
| for k in 0..12 { |
| let hash = compute_hash(&map, k); |
| let v = map.get(&k).copied(); |
| let kv = v.as_ref().map(|v| (&k, v)); |
| |
| assert_eq!(map.raw_entry().from_key(&k), kv); |
| assert_eq!(map.raw_entry().from_hash(hash, |q| *q == k), kv); |
| assert_eq!(map.raw_entry().from_key_hashed_nocheck(hash, &k), kv); |
| |
| match map.raw_entry_mut().from_key(&k) { |
| Occupied(o) => assert_eq!(Some(o.get_key_value()), kv), |
| Vacant(_) => assert_eq!(v, None), |
| } |
| match map.raw_entry_mut().from_key_hashed_nocheck(hash, &k) { |
| Occupied(o) => assert_eq!(Some(o.get_key_value()), kv), |
| Vacant(_) => assert_eq!(v, None), |
| } |
| match map.raw_entry_mut().from_hash(hash, |q| *q == k) { |
| Occupied(o) => assert_eq!(Some(o.get_key_value()), kv), |
| Vacant(_) => assert_eq!(v, None), |
| } |
| } |
| } |
| |
| #[test] |
| fn test_key_without_hash_impl() { |
| #[derive(Debug)] |
| struct IntWrapper(u64); |
| |
| let mut m: HashMap<IntWrapper, (), ()> = HashMap::default(); |
| { |
| assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_none()); |
| } |
| { |
| let vacant_entry = match m.raw_entry_mut().from_hash(0, |k| k.0 == 0) { |
| RawEntryMut::Occupied(..) => panic!("Found entry for key 0"), |
| RawEntryMut::Vacant(e) => e, |
| }; |
| vacant_entry.insert_with_hasher(0, IntWrapper(0), (), |k| k.0); |
| } |
| { |
| assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_some()); |
| assert!(m.raw_entry().from_hash(1, |k| k.0 == 1).is_none()); |
| assert!(m.raw_entry().from_hash(2, |k| k.0 == 2).is_none()); |
| } |
| { |
| let vacant_entry = match m.raw_entry_mut().from_hash(1, |k| k.0 == 1) { |
| RawEntryMut::Occupied(..) => panic!("Found entry for key 1"), |
| RawEntryMut::Vacant(e) => e, |
| }; |
| vacant_entry.insert_with_hasher(1, IntWrapper(1), (), |k| k.0); |
| } |
| { |
| assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_some()); |
| assert!(m.raw_entry().from_hash(1, |k| k.0 == 1).is_some()); |
| assert!(m.raw_entry().from_hash(2, |k| k.0 == 2).is_none()); |
| } |
| { |
| let occupied_entry = match m.raw_entry_mut().from_hash(0, |k| k.0 == 0) { |
| RawEntryMut::Occupied(e) => e, |
| RawEntryMut::Vacant(..) => panic!("Couldn't find entry for key 0"), |
| }; |
| occupied_entry.remove(); |
| } |
| assert!(m.raw_entry().from_hash(0, |k| k.0 == 0).is_none()); |
| assert!(m.raw_entry().from_hash(1, |k| k.0 == 1).is_some()); |
| assert!(m.raw_entry().from_hash(2, |k| k.0 == 2).is_none()); |
| } |
| } |
