xref: /external/rust/android-crates-io/crates/hashbrown/src/raw_entry.rs

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());
    }
}