iddqd/id_hash_map/

imp.rs

use super::{
    Entry, IdHashItem, IntoIter, Iter, IterMut, OccupiedEntry, RefMut,
    VacantEntry, tables::IdHashMapTables,
};
use crate::{
    DefaultHashBuilder,
    errors::DuplicateItem,
    internal::{ValidateCompact, ValidationError},
    support::{
        ItemIndex,
        alloc::{Allocator, Global, global_alloc},
        hash_table,
        item_set::ItemSet,
        map_hash::MapHash,
    },
};
use core::{
    fmt,
    hash::{BuildHasher, Hash},
};
use equivalent::Equivalent;

/// A hash map where the key is part of the value.
///
/// The storage mechanism is a list of items with an embedded free chain, with
/// indexes to occupied slots stored in a hash table. This allows for efficient
/// lookups by the key and prevents duplicates.
///
/// # Examples
///
/// ```
/// # #[cfg(feature = "default-hasher")] {
/// use iddqd::{IdHashItem, IdHashMap, id_upcast};
///
/// // Define a struct with a key.
/// #[derive(Debug, PartialEq, Eq, Hash)]
/// struct MyItem {
///     id: String,
///     value: u32,
/// }
///
/// // Implement IdHashItem for the struct.
/// impl IdHashItem for MyItem {
///     // Keys can borrow from the item.
///     type Key<'a> = &'a str;
///
///     fn key(&self) -> Self::Key<'_> {
///         &self.id
///     }
///
///     id_upcast!();
/// }
///
/// // Create an IdHashMap and insert items.
/// let mut map = IdHashMap::new();
/// map.insert_unique(MyItem { id: "foo".to_string(), value: 42 }).unwrap();
/// map.insert_unique(MyItem { id: "bar".to_string(), value: 20 }).unwrap();
///
/// // Look up items by their keys.
/// assert_eq!(map.get("foo").unwrap().value, 42);
/// assert_eq!(map.get("bar").unwrap().value, 20);
/// assert!(map.get("baz").is_none());
/// # }
/// ```
#[derive(Clone)]
pub struct IdHashMap<T, S = DefaultHashBuilder, A: Allocator = Global> {
    pub(super) items: ItemSet<T, A>,
    pub(super) tables: IdHashMapTables<S, A>,
}

impl<T: IdHashItem, S: Default, A: Allocator + Default> Default
    for IdHashMap<T, S, A>
{
    fn default() -> Self {
        Self {
            items: ItemSet::with_capacity_in(0, A::default()),
            tables: IdHashMapTables::default(),
        }
    }
}

#[cfg(feature = "default-hasher")]
impl<T: IdHashItem> IdHashMap<T> {
    /// Creates a new, empty `IdHashMap`.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let map: IdHashMap<Item> = IdHashMap::new();
    /// assert!(map.is_empty());
    /// assert_eq!(map.len(), 0);
    /// # }
    /// ```
    #[inline]
    pub fn new() -> Self {
        Self { items: ItemSet::new(), tables: IdHashMapTables::default() }
    }

    /// Creates a new `IdHashMap` with the given capacity.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let map: IdHashMap<Item> = IdHashMap::with_capacity(10);
    /// assert!(map.capacity() >= 10);
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            items: ItemSet::with_capacity_in(capacity, global_alloc()),
            tables: IdHashMapTables::with_capacity_and_hasher_in(
                capacity,
                DefaultHashBuilder::default(),
                global_alloc(),
            ),
        }
    }
}

impl<T: IdHashItem, S: BuildHasher> IdHashMap<T, S> {
    /// Creates a new, empty `IdHashMap` with the given hasher.
    ///
    /// # Examples
    ///
    /// ```
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    /// use std::collections::hash_map::RandomState;
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let hasher = RandomState::new();
    /// let map: IdHashMap<Item, _> = IdHashMap::with_hasher(hasher);
    /// assert!(map.is_empty());
    /// ```
    pub const fn with_hasher(hasher: S) -> Self {
        Self {
            items: ItemSet::new(),
            tables: IdHashMapTables::with_hasher_in(hasher, global_alloc()),
        }
    }

    /// Creates a new `IdHashMap` with the given capacity and hasher.
    ///
    /// # Examples
    ///
    /// ```
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    /// use std::collections::hash_map::RandomState;
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let hasher = RandomState::new();
    /// let map: IdHashMap<Item, _> =
    ///     IdHashMap::with_capacity_and_hasher(10, hasher);
    /// assert!(map.capacity() >= 10);
    /// assert!(map.is_empty());
    /// ```
    pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
        Self {
            items: ItemSet::with_capacity_in(capacity, global_alloc()),
            tables: IdHashMapTables::with_capacity_and_hasher_in(
                capacity,
                hasher,
                global_alloc(),
            ),
        }
    }
}

#[cfg(feature = "default-hasher")]
impl<T: IdHashItem, A: Clone + Allocator> IdHashMap<T, DefaultHashBuilder, A> {
    /// Creates a new empty `IdHashMap` using the given allocator.
    ///
    /// Requires the `allocator-api2` feature to be enabled.
    ///
    /// # Examples
    ///
    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
    ///
    /// ```
    /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
    /// use iddqd::{IdHashMap, IdHashItem, id_upcast};
    /// # use iddqd_test_utils::bumpalo;
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> { &self.id }
    ///     id_upcast!();
    /// }
    ///
    /// // Define a new allocator.
    /// let bump = bumpalo::Bump::new();
    /// // Create a new IdHashMap using the allocator.
    /// let map: IdHashMap<Item, _, &bumpalo::Bump> = IdHashMap::new_in(&bump);
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn new_in(alloc: A) -> Self {
        Self {
            items: ItemSet::with_capacity_in(0, alloc.clone()),
            tables: IdHashMapTables::with_capacity_and_hasher_in(
                0,
                DefaultHashBuilder::default(),
                alloc,
            ),
        }
    }

    /// Creates an empty `IdHashMap` with the specified capacity using the given
    /// allocator.
    ///
    /// Requires the `allocator-api2` feature to be enabled.
    ///
    /// # Examples
    ///
    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
    ///
    /// ```
    /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
    /// use iddqd::{IdHashMap, IdHashItem, id_upcast};
    /// # use iddqd_test_utils::bumpalo;
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> { &self.id }
    ///     id_upcast!();
    /// }
    ///
    /// // Define a new allocator.
    /// let bump = bumpalo::Bump::new();
    /// // Create a new IdHashMap with capacity using the allocator.
    /// let map: IdHashMap<Item, _, &bumpalo::Bump> = IdHashMap::with_capacity_in(10, &bump);
    /// assert!(map.capacity() >= 10);
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
        Self {
            items: ItemSet::with_capacity_in(capacity, alloc.clone()),
            tables: IdHashMapTables::with_capacity_and_hasher_in(
                capacity,
                DefaultHashBuilder::default(),
                alloc,
            ),
        }
    }
}

impl<T: IdHashItem, S: BuildHasher, A: Clone + Allocator> IdHashMap<T, S, A> {
    /// Creates a new, empty `IdHashMap` with the given hasher and allocator.
    ///
    /// Requires the `allocator-api2` feature to be enabled.
    ///
    /// # Examples
    ///
    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
    ///
    /// ```
    /// # #[cfg(feature = "allocator-api2")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    /// use std::collections::hash_map::RandomState;
    /// # use iddqd_test_utils::bumpalo;
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// // Define a new allocator.
    /// let bump = bumpalo::Bump::new();
    /// let hasher = RandomState::new();
    /// // Create a new IdHashMap with hasher using the allocator.
    /// let map: IdHashMap<Item, _, &bumpalo::Bump> =
    ///     IdHashMap::with_hasher_in(hasher, &bump);
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn with_hasher_in(hasher: S, alloc: A) -> Self {
        Self {
            items: ItemSet::new_in(alloc.clone()),
            tables: IdHashMapTables::with_hasher_in(hasher, alloc),
        }
    }

    /// Creates a new, empty `IdHashMap` with the given capacity, hasher, and
    /// allocator.
    ///
    /// Requires the `allocator-api2` feature to be enabled.
    ///
    /// # Examples
    ///
    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
    ///
    /// ```
    /// # #[cfg(feature = "allocator-api2")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    /// use std::collections::hash_map::RandomState;
    /// # use iddqd_test_utils::bumpalo;
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// // Define a new allocator.
    /// let bump = bumpalo::Bump::new();
    /// let hasher = RandomState::new();
    /// // Create a new IdHashMap with capacity and hasher using the allocator.
    /// let map: IdHashMap<Item, _, &bumpalo::Bump> =
    ///     IdHashMap::with_capacity_and_hasher_in(10, hasher, &bump);
    /// assert!(map.capacity() >= 10);
    /// assert!(map.is_empty());
    /// # }
    /// ```
    pub fn with_capacity_and_hasher_in(
        capacity: usize,
        hasher: S,
        alloc: A,
    ) -> Self {
        Self {
            items: ItemSet::with_capacity_in(capacity, alloc.clone()),
            tables: IdHashMapTables::with_capacity_and_hasher_in(
                capacity, hasher, alloc,
            ),
        }
    }
}

impl<T: IdHashItem, S: Default + Clone + BuildHasher, A: Allocator + Default>
    IdHashMap<T, S, A>
{
    /// Creates a new `IdHashMap` from an iterator of values, rejecting
    /// duplicates.
    ///
    /// To overwrite duplicates instead, use [`IdHashMap::from_iter`].
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let items = vec![
    ///     Item { id: "foo".to_string(), value: 42 },
    ///     Item { id: "bar".to_string(), value: 99 },
    /// ];
    ///
    /// // Successful creation with unique keys.
    /// let map: IdHashMap<Item> = IdHashMap::from_iter_unique(items).unwrap();
    /// assert_eq!(map.len(), 2);
    /// assert_eq!(map.get("foo").unwrap().value, 42);
    ///
    /// // Error with duplicate keys.
    /// let duplicate_items = vec![
    ///     Item { id: "foo".to_string(), value: 42 },
    ///     Item { id: "foo".to_string(), value: 99 },
    /// ];
    /// assert!(IdHashMap::<Item>::from_iter_unique(duplicate_items).is_err());
    /// # }
    /// ```
    pub fn from_iter_unique<I: IntoIterator<Item = T>>(
        iter: I,
    ) -> Result<Self, DuplicateItem<T>> {
        let iter = iter.into_iter();
        let mut map = Self::default();
        map.reserve(iter.size_hint().0);
        for value in iter {
            // It would be nice to use insert_unique here, but that would return
            // a `DuplicateItem<T, &T>`, which can only be converted into an
            // owned value if T: Clone. Doing this via the Entry API means we
            // can return a `DuplicateItem<T>` without requiring T to be Clone.
            match map.entry(value.key()) {
                Entry::Occupied(entry) => {
                    let duplicate = entry.remove();
                    return Err(DuplicateItem::__internal_new(
                        value,
                        vec![duplicate],
                    ));
                }
                Entry::Vacant(entry) => {
                    entry.insert_known_unique(value);
                }
            }
        }

        Ok(map)
    }
}

impl<T: IdHashItem, S: Clone + BuildHasher, A: Allocator> IdHashMap<T, S, A> {
    #[cfg(feature = "daft")]
    pub(crate) fn hasher(&self) -> &S {
        self.tables.hasher()
    }

    /// Returns the allocator.
    ///
    /// Requires the `allocator-api2` feature to be enabled.
    ///
    /// # Examples
    ///
    /// Using the [`bumpalo`](https://docs.rs/bumpalo) allocator:
    ///
    /// ```
    /// # #[cfg(all(feature = "default-hasher", feature = "allocator-api2"))] {
    /// use iddqd::{IdHashMap, IdHashItem, id_upcast};
    /// # use iddqd_test_utils::bumpalo;
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> { &self.id }
    ///     id_upcast!();
    /// }
    ///
    /// // Define a new allocator.
    /// let bump = bumpalo::Bump::new();
    /// // Create a new IdHashMap using the allocator.
    /// let map: IdHashMap<Item, _, &bumpalo::Bump> = IdHashMap::new_in(&bump);
    /// let _allocator = map.allocator();
    /// # }
    /// ```
    pub fn allocator(&self) -> &A {
        self.items.allocator()
    }

    /// Returns the currently allocated capacity of the map.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let map: IdHashMap<Item> = IdHashMap::with_capacity(10);
    /// assert!(map.capacity() >= 10);
    /// # }
    /// ```
    pub fn capacity(&self) -> usize {
        // items and tables.capacity might theoretically diverge: use
        // items.capacity.
        self.items.capacity()
    }

    /// Returns true if the map is empty.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// assert!(map.is_empty());
    ///
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    /// assert!(!map.is_empty());
    /// # }
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.items.is_empty()
    }

    /// Returns the number of items in the map.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// assert_eq!(map.len(), 0);
    ///
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    /// assert_eq!(map.len(), 1);
    ///
    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
    /// assert_eq!(map.len(), 2);
    /// # }
    /// ```
    #[inline]
    pub fn len(&self) -> usize {
        self.items.len()
    }

    /// Clears the map, removing all items.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
    /// assert_eq!(map.len(), 2);
    ///
    /// map.clear();
    /// assert!(map.is_empty());
    /// assert_eq!(map.len(), 0);
    /// # }
    /// ```
    pub fn clear(&mut self) {
        // Clear the internal index before dropping items. This way, if a user
        // `Drop` panics during `self.items.clear()`, `key_to_item` cannot retain
        // indexes pointing to removed item slots.
        self.tables.key_to_item.clear();
        self.items.clear();
    }

    /// Reserves capacity for at least `additional` more elements to be inserted
    /// in the `IdHashMap`. The collection may reserve more space to
    /// speculatively avoid frequent reallocations. After calling `reserve`,
    /// capacity will be greater than or equal to `self.len() + additional`.
    /// Does nothing if capacity is already sufficient.
    ///
    /// # Panics
    ///
    /// Panics if the new capacity overflows [`isize::MAX`] bytes, and
    /// [`abort`]s the program in case of an allocation error. Use
    /// [`try_reserve`](Self::try_reserve) instead if you want to handle memory
    /// allocation failure.
    ///
    /// [`isize::MAX`]: https://doc.rust-lang.org/std/primitive.isize.html
    /// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map: IdHashMap<Item> = IdHashMap::new();
    /// map.reserve(100);
    /// assert!(map.capacity() >= 100);
    /// # }
    /// ```
    pub fn reserve(&mut self, additional: usize) {
        self.items.reserve(additional);
        self.tables.key_to_item.reserve(additional);
    }

    /// Tries to reserve capacity for at least `additional` more elements to be
    /// inserted in the `IdHashMap`. The collection may reserve more space to
    /// speculatively avoid frequent reallocations. After calling `try_reserve`,
    /// capacity will be greater than or equal to `self.len() + additional` if
    /// it returns `Ok(())`. Does nothing if capacity is already sufficient.
    ///
    /// # Errors
    ///
    /// If the capacity overflows, or the allocator reports a failure, then an
    /// error is returned.
    ///
    /// # Notes
    ///
    /// If reservation fails partway through, some internal structures may have
    /// already increased their capacity. The map remains in a valid state but
    /// may have uneven capacities across its internal structures.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map: IdHashMap<Item> = IdHashMap::new();
    /// map.try_reserve(100).expect("allocation should succeed");
    /// assert!(map.capacity() >= 100);
    /// # }
    /// ```
    pub fn try_reserve(
        &mut self,
        additional: usize,
    ) -> Result<(), crate::errors::TryReserveError> {
        self.items.try_reserve(additional)?;
        self.tables
            .key_to_item
            .try_reserve(additional)
            .map_err(crate::errors::TryReserveError::from_hashbrown)?;
        Ok(())
    }

    /// Shrinks the capacity of the map as much as possible. It will drop
    /// down as much as possible while maintaining the internal rules
    /// and possibly leaving some space in accordance with the resize policy.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map: IdHashMap<Item> = IdHashMap::with_capacity(100);
    /// map.insert_unique(Item { id: "foo".to_string(), value: 1 }).unwrap();
    /// map.insert_unique(Item { id: "bar".to_string(), value: 2 }).unwrap();
    /// assert!(map.capacity() >= 100);
    /// map.shrink_to_fit();
    /// assert!(map.capacity() >= 2);
    /// # }
    /// ```
    pub fn shrink_to_fit(&mut self) {
        // Sequence this carefully.
        //
        // * First, compact the item set. This does not allocate through A
        //   (it allocates a small remap buffer through the global allocator),
        //   and returns a remapper.
        // * Then, remap the tables using the remapper.
        // * Finally, shrink the capacities of the tables and items.
        //
        // An allocator panic during either capacity shrink leaves the tables
        // and items already in sync, because remap has already been committed.
        let remap = self.items.compact();
        if !remap.is_identity() {
            self.tables.key_to_item.remap_indexes(&remap);
        }
        self.items.shrink_capacity_to_fit();
        self.tables.key_to_item.shrink_to_fit();
    }

    /// Shrinks the capacity of the map with a lower limit. It will drop
    /// down no lower than the supplied limit while maintaining the internal
    /// rules and possibly leaving some space in accordance with the resize
    /// policy.
    ///
    /// If the current capacity is less than the lower limit, this is a no-op.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map: IdHashMap<Item> = IdHashMap::with_capacity(100);
    /// map.insert_unique(Item { id: "foo".to_string(), value: 1 }).unwrap();
    /// map.insert_unique(Item { id: "bar".to_string(), value: 2 }).unwrap();
    /// assert!(map.capacity() >= 100);
    /// map.shrink_to(10);
    /// assert!(map.capacity() >= 10);
    /// map.shrink_to(0);
    /// assert!(map.capacity() >= 2);
    /// # }
    /// ```
    pub fn shrink_to(&mut self, min_capacity: usize) {
        // See `shrink_to_fit` for the rationale behind the sequence.
        let remap = self.items.compact();
        if !remap.is_identity() {
            self.tables.key_to_item.remap_indexes(&remap);
        }
        self.items.shrink_capacity_to(min_capacity);
        self.tables.key_to_item.shrink_to(min_capacity);
    }

    /// Iterates over the items in the map.
    ///
    /// Similar to [`HashMap`], the iteration order is arbitrary and not
    /// guaranteed to be stable.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
    ///
    /// let mut values: Vec<u32> = map.iter().map(|item| item.value).collect();
    /// values.sort();
    /// assert_eq!(values, vec![20, 42]);
    /// # }
    /// ```
    ///
    /// [`HashMap`]: std::collections::HashMap
    #[inline]
    pub fn iter(&self) -> Iter<'_, T> {
        Iter::new(&self.items)
    }

    /// Iterates over the items in the map, allowing for mutation.
    ///
    /// Similar to [`HashMap`], the iteration order is arbitrary and not
    /// guaranteed to be stable.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
    ///
    /// for mut item in map.iter_mut() {
    ///     item.value *= 2;
    /// }
    ///
    /// assert_eq!(map.get("foo").unwrap().value, 84);
    /// assert_eq!(map.get("bar").unwrap().value, 40);
    /// # }
    /// ```
    ///
    /// [`HashMap`]: std::collections::HashMap
    #[inline]
    pub fn iter_mut(&mut self) -> IterMut<'_, T, S, A> {
        IterMut::new(&self.tables, &mut self.items)
    }

    /// Checks general invariants of the map.
    ///
    /// The code below always upholds these invariants, but it's useful to have
    /// an explicit check for tests.
    #[doc(hidden)]
    pub fn validate(
        &self,
        compactness: ValidateCompact,
    ) -> Result<(), ValidationError>
    where
        T: fmt::Debug,
    {
        self.validate_structural(compactness)?;

        // Check that the indexes are all correct.
        //
        // Unlike the structural checks above, this re-looks up each key through
        // the user `Hash`, so it only holds when that `Hash` is lawful.
        for (ix, item) in self.items.iter() {
            let key = item.key();
            let Some(ix1) = self.find_index(&key) else {
                return Err(ValidationError::general(format!(
                    "item at index {ix} has no key1 index"
                )));
            };

            if ix1 != ix {
                return Err(ValidationError::General(format!(
                    "item at index {ix} has mismatched indexes: ix1: {ix1}",
                )));
            }
        }

        Ok(())
    }

    /// Checks the structural invariants of the map:
    ///
    /// * The item set is well-formed.
    /// * The hash table holds exactly one entry per live item, with no
    ///   duplicate `ItemIndex`es.
    ///
    /// Unlike [`validate`](Self::validate), this does not re-look-up keys
    /// through the user `Hash`, so it holds regardless of whether that `Hash`
    /// is lawful. A buggy hasher can desync the logical key→item mapping, but
    /// it must never break these structural invariants! Doing so would be
    /// unsoundness, e.g. duplicate indexes enabling mutable aliasing.
    #[doc(hidden)]
    pub fn validate_structural(
        &self,
        compactness: ValidateCompact,
    ) -> Result<(), ValidationError> {
        self.items.validate(compactness)?;
        self.tables.validate(self.len(), compactness)?;
        Ok(())
    }

    /// Inserts a value into the map, removing and returning the conflicting
    /// item, if any.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    ///
    /// // First insertion returns None
    /// let old = map.insert_overwrite(Item { id: "foo".to_string(), value: 42 });
    /// assert!(old.is_none());
    ///
    /// // Second insertion with same key returns the old value
    /// let old = map.insert_overwrite(Item { id: "foo".to_string(), value: 100 });
    /// assert_eq!(old.unwrap().value, 42);
    /// assert_eq!(map.get("foo").unwrap().value, 100);
    /// # }
    /// ```
    #[doc(alias = "insert")]
    pub fn insert_overwrite(&mut self, value: T) -> Option<T> {
        // Go through the entry API so all user code is called before any table
        // mutation. A panic in user code therefore leaves the map in its
        // pre-call state.
        //
        // In the vacant case, the Entry lookup has already established that the
        // key is unique. Calling `vacant.insert_entry` would route back through
        // `insert_unique_impl` and check for duplicates again, while
        // `vacant.insert` would also create a `RefMut` and re-hash the key. We
        // use `vacant.insert_known_unique` instead, which avoids both.
        match self.entry(value.key()) {
            Entry::Occupied(mut occupied) => Some(occupied.insert(value)),
            Entry::Vacant(vacant) => {
                vacant.insert_known_unique(value);
                None
            }
        }
    }

    /// Inserts a value into the set, returning an error if any duplicates were
    /// added.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    ///
    /// // First insertion succeeds
    /// assert!(
    ///     map.insert_unique(Item { id: "foo".to_string(), value: 42 }).is_ok()
    /// );
    ///
    /// // Second insertion with different key succeeds
    /// assert!(
    ///     map.insert_unique(Item { id: "bar".to_string(), value: 20 }).is_ok()
    /// );
    ///
    /// // Third insertion with duplicate key fails
    /// assert!(
    ///     map.insert_unique(Item { id: "foo".to_string(), value: 100 }).is_err()
    /// );
    /// # }
    /// ```
    pub fn insert_unique(
        &mut self,
        value: T,
    ) -> Result<(), DuplicateItem<T, &T>> {
        let _ = self.insert_unique_impl(value)?;
        Ok(())
    }

    /// Returns true if the map contains the given key.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    ///
    /// assert!(map.contains_key("foo"));
    /// assert!(!map.contains_key("bar"));
    /// # }
    /// ```
    pub fn contains_key<'a, Q>(&'a self, key1: &Q) -> bool
    where
        Q: ?Sized + Hash + Equivalent<T::Key<'a>>,
    {
        self.find_index(key1).is_some()
    }

    /// Gets a reference to the value associated with the given key.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    ///
    /// assert_eq!(map.get("foo").unwrap().value, 42);
    /// assert!(map.get("bar").is_none());
    /// # }
    /// ```
    pub fn get<'a, Q>(&'a self, key: &Q) -> Option<&'a T>
    where
        Q: ?Sized + Hash + Equivalent<T::Key<'a>>,
    {
        self.find_index(key).map(|ix| &self.items[ix])
    }

    /// Gets a mutable reference to the value associated with the given key.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    ///
    /// if let Some(mut item) = map.get_mut("foo") {
    ///     item.value = 100;
    /// }
    ///
    /// assert_eq!(map.get("foo").unwrap().value, 100);
    /// assert!(map.get_mut("bar").is_none());
    /// # }
    /// ```
    pub fn get_mut(&mut self, key: T::Key<'_>) -> Option<RefMut<'_, T, S>> {
        let index = self.find_index_by_key(key)?;
        self.get_by_index_mut(index)
    }

    /// Removes an item from the map by its key.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    ///
    /// let removed = map.remove("foo");
    /// assert_eq!(removed.unwrap().value, 42);
    /// assert!(map.is_empty());
    ///
    /// // Removing non-existent key returns None
    /// assert!(map.remove("bar").is_none());
    /// # }
    /// ```
    pub fn remove(&mut self, key: T::Key<'_>) -> Option<T> {
        let remove_index = self.find_index_by_key(key)?;
        self.remove_by_index(remove_index)
    }

    /// Retrieves an entry by its key.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    ///
    /// // Use entry API for conditional insertion
    /// map.entry("foo").or_insert(Item { id: "foo".to_string(), value: 42 });
    /// map.entry("bar").or_insert(Item { id: "bar".to_string(), value: 20 });
    ///
    /// assert_eq!(map.len(), 2);
    /// # }
    /// ```
    pub fn entry(&mut self, key: T::Key<'_>) -> Entry<'_, T, S, A> {
        // See the "Mutable lookups take owned keys" section in the crate docs
        // for why this takes `T::Key<'_>` rather than a `Q`.
        let key = T::upcast_key(key);
        if let Some(index) = self.find_index(&key) {
            drop(key);
            return Entry::Occupied(OccupiedEntry::new(self, index));
        }
        let hash = self.make_key_hash(&key);
        drop(key);
        Entry::Vacant(VacantEntry::new(self, hash))
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all items `T` for which `f(RefMut<T>)` returns
    /// false. The elements are visited in an arbitrary order.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
    /// map.insert_unique(Item { id: "baz".to_string(), value: 99 }).unwrap();
    ///
    /// // Retain only items where value is greater than 30
    /// map.retain(|item| item.value > 30);
    ///
    /// assert_eq!(map.len(), 2);
    /// assert_eq!(map.get("foo").unwrap().value, 42);
    /// assert_eq!(map.get("baz").unwrap().value, 99);
    /// assert!(map.get("bar").is_none());
    /// # }
    /// ```
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: for<'b> FnMut(RefMut<'b, T, S>) -> bool,
    {
        let hash_state = self.tables.state.clone();
        let items = &mut self.items;
        // This variable is:
        //
        // * None, if the last time `f` was called, it returned true.
        // * Some with the previous index, if the last time `f` was called,
        //   it returned false.
        let mut pending_remove: Option<ItemIndex> = None;

        self.tables.key_to_item.retain(|index| {
            // If `f` returned false last time, remove that item from `items`
            // now, one call later. We do this because of how
            // `HashTable::retain` sequences its work:
            //
            // 1. It calls this closure.
            // 2. If the closure returns false, it erases the entry.
            // 3. It calls this closure again for the next entry.
            //
            // If we removed the item from `items` during step 1, then between
            // steps 1 and 2 `key_to_item` would hold an index whose slot is
            // vacant. Only hashbrown code runs in that gap today, so nothing
            // can panic there. But if something ever did, the map would be
            // left with a stale index in the table. A later insert could then
            // reuse the vacant slot, and the table would hold the same index
            // twice.
            //
            // Unlike `IdOrdMap`, the hash maps re-check every index they turn
            // into a `&mut T`, so a duplicate would panic rather than alias.
            // We defer the removal anyway so all four `retain` methods work
            // the same way.
            //
            // Removing the item here, during step 3, closes the gap. The
            // table entry is already gone, so if `items.remove` or the user
            // `Drop` below panics, the tables and `items` are still in sync.
            if let Some(prev) = pending_remove.take() {
                drop(
                    items
                        .remove(prev)
                        .expect("all indexes are present in self.items"),
                );
            }

            let retain = {
                let item = items
                    .get_mut(index)
                    .expect("all indexes are present in self.items");
                // Use T::key(item) rather than item.key() to force the key
                // trait function to be called for T rather than &mut T.
                let hash = MapHash::new(hash_state.hash_one(T::key(item)));
                f(RefMut::new(hash_state.clone(), hash, item))
            };

            if retain {
                true
            } else {
                pending_remove = Some(index);
                false
            }
        });

        // The last rejected item, if any, is freed and dropped now that its
        // table entry is gone.
        if let Some(prev) = pending_remove {
            drop(
                items
                    .remove(prev)
                    .expect("all indexes are present in self.items"),
            );
        }
    }

    fn find_index<'a, Q>(&'a self, k: &Q) -> Option<ItemIndex>
    where
        Q: Hash + Equivalent<T::Key<'a>> + ?Sized,
    {
        self.tables
            .key_to_item
            .find_index(&self.tables.state, k, |index| self.items[index].key())
    }

    /// Looks up an owned key, borrowing `self` only for as long as the
    /// upcast key lives.
    ///
    /// The `&mut self` methods use this rather than `find_index` so that the
    /// caller's key never observes a borrow at the mutable lifetime. See the
    /// "Mutable lookups take owned keys" section in the crate docs.
    fn find_index_by_key(&self, key: T::Key<'_>) -> Option<ItemIndex> {
        let key = T::upcast_key(key);
        self.find_index(&key)
    }

    fn make_hash(&self, item: &T) -> MapHash {
        self.tables.make_hash(item)
    }

    fn make_key_hash(&self, key: &T::Key<'_>) -> MapHash {
        self.tables.make_key_hash::<T>(key)
    }

    pub(super) fn get_by_index(&self, index: ItemIndex) -> Option<&T> {
        self.items.get(index)
    }

    pub(super) fn get_by_index_mut(
        &mut self,
        index: ItemIndex,
    ) -> Option<RefMut<'_, T, S>> {
        let state = self.tables.state.clone();
        let hashes = self.make_hash(&self.items[index]);
        let item = &mut self.items[index];
        Some(RefMut::new(state, hashes, item))
    }

    pub(super) fn insert_unique_impl(
        &mut self,
        value: T,
    ) -> Result<ItemIndex, DuplicateItem<T, &T>> {
        // Check for duplicates *before* inserting the new item, because we
        // don't want to partially insert the new item and then have to roll
        // back.
        let key = value.key();
        let state = &self.tables.state;

        let entry = match self
            .tables
            .key_to_item
            .entry(state, key, |index| self.items[index].key())
        {
            hash_table::Entry::Occupied(slot) => {
                let index = slot.get();
                return Err(DuplicateItem::__internal_new(
                    value,
                    vec![&self.items[index]],
                ));
            }
            hash_table::Entry::Vacant(slot) => slot,
        };

        let next_index = self.items.assert_can_grow().insert(value);
        entry.insert(next_index);

        Ok(next_index)
    }

    pub(super) fn try_reserve_insert_overwrite_commit(
        &mut self,
    ) -> Result<(), crate::errors::TryReserveError> {
        self.items.try_reserve(1)?;
        self.tables
            .key_to_item
            .try_reserve(1)
            .map_err(crate::errors::TryReserveError::from_hashbrown)?;
        Ok(())
    }

    pub(super) fn remove_by_index(
        &mut self,
        remove_index: ItemIndex,
    ) -> Option<T> {
        // For panic safety, compute the key hash and look up the table entry
        // while `self.items` still holds the value, then remove from the table
        // and items in sequence. This lookup deliberately matches by
        // `ItemIndex` rather than by user `Eq`: at this point we already know
        // which item is being removed, and user `Eq` might be pathological.
        //
        // hashbrown's `find_entry_by_hash` is panic-safe because the table is
        // not mutated until `OccupiedEntry::remove` is called, so a panic while
        // hashing leaves both items and the table unmodified. (Unlike the
        // IdOrdMap path, we don't need a separate two-phase commit: the
        // BTreeMap analog has to guard against a user-`Ord` panic during the
        // tree walk, but the hash walk here never invokes user code.)
        //
        // If the hash lookup misses, which can happen when `mem::forget` is
        // called on a `RefMut` after the ID was changed, the item's current key
        // now hashes to a different bucket than the one its entry sits in. In
        // that case, we fall back to a linear scan by `ItemIndex`. This keeps
        // the table and item set consistent with each other across silent key
        // mutations, mirroring `MapBTreeTable::remove_exact`.
        //
        // This is not expected to be the common case (why are you calling
        // mem::forget on a RefMut?), but guarding against it explicitly makes
        // our invariants easier to reason about.
        let item = self.items.get(remove_index)?;
        let state = &self.tables.state;
        let hash = state.hash_one(item.key());
        match self
            .tables
            .key_to_item
            .find_entry_by_hash(hash, |index| index == remove_index)
        {
            Ok(entry) => entry.remove(),
            Err(()) => self.tables.key_to_item.remove_by_index(remove_index),
        }
        Some(
            self.items
                .remove(remove_index)
                .expect("items[remove_index] was Occupied above"),
        )
    }

    pub(super) fn replace_at_index(&mut self, index: ItemIndex, value: T) -> T {
        // We check the key before removing it, to avoid leaving the map in an
        // inconsistent state.
        let old_key =
            self.get_by_index(index).expect("index is known to be valid").key();
        if T::upcast_key(old_key) != value.key() {
            panic!(
                "must insert a value with \
                 the same key used to create the entry"
            );
        }

        // Now that we know the key is the same, we can replace the value
        // directly without needing to tweak any tables.
        self.items.replace(index, value)
    }
}

impl<T: IdHashItem + fmt::Debug, S, A: Allocator> IdHashMap<T, S, A> {
    /// Returns a value that formats the map as `{key: item, ...}`, in
    /// arbitrary order.
    ///
    /// The [`Debug`](fmt::Debug) impl for `IdHashMap` formats items only, as
    /// a set, and requires just `T: Debug`. This method also requires the key
    /// type to be `Debug` for the lifetime of the borrow.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    ///
    /// assert_eq!(
    ///     format!("{:?}", map.debug_with_keys()),
    ///     "{\"foo\": Item { id: \"foo\", value: 42 }}",
    /// );
    /// assert_eq!(format!("{map:?}"), "{Item { id: \"foo\", value: 42 }}");
    /// # }
    /// ```
    pub fn debug_with_keys<'a>(&'a self) -> impl fmt::Debug + 'a
    where
        T::Key<'a>: fmt::Debug,
    {
        struct DebugWithKeys<'a, T: IdHashItem, S, A: Allocator>(
            &'a IdHashMap<T, S, A>,
        );

        impl<'a, T, S, A> fmt::Debug for DebugWithKeys<'a, T, S, A>
        where
            T: IdHashItem + fmt::Debug,
            T::Key<'a>: fmt::Debug,
            A: Allocator,
        {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                let mut map = f.debug_map();
                for item in self.0.items.values() {
                    // `self.0` is borrowed for 'a, so `item: &'a T` and the
                    // key is `T::Key<'a>` without any lifetime extension.
                    let key: T::Key<'a> = item.key();
                    map.entry(&key, item);
                }
                map.finish()
            }
        }

        DebugWithKeys(self)
    }
}

impl<T: IdHashItem + fmt::Debug, S, A: Allocator> fmt::Debug
    for IdHashMap<T, S, A>
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_set().entries(self.items.values()).finish()
    }
}

impl<T: IdHashItem + PartialEq, S: Clone + BuildHasher, A: Allocator> PartialEq
    for IdHashMap<T, S, A>
{
    fn eq(&self, other: &Self) -> bool {
        // Implementing PartialEq for IdHashMap is tricky because IdHashMap is
        // not semantically like an IndexMap: two maps are equivalent even if
        // their items are in a different order. In other words, any permutation
        // of items is equivalent.
        //
        // We also can't sort the items because they're not necessarily Ord.
        //
        // So we write a custom equality check that checks that each key in one
        // map points to the same item as in the other map.

        if self.items.len() != other.items.len() {
            return false;
        }

        // Walk over all the items in the first map and check that they point to
        // the same item in the second map.
        for item in self.items.values() {
            let k1 = item.key();

            // Check that the indexes are the same in the other map.
            let Some(other_ix) = other.find_index(&k1) else {
                return false;
            };

            // Check that the other map's item is the same as this map's
            // item. (This is what we use the `PartialEq` bound on T for.)
            //
            // Because we've checked that other_ix is Some, we know that it is
            // valid and points to the expected item.
            let other_item = &other.items[other_ix];
            if item != other_item {
                return false;
            }
        }

        true
    }
}

// The Eq bound on T ensures that the TriHashMap forms an equivalence class.
impl<T: IdHashItem + Eq, S: Clone + BuildHasher, A: Allocator> Eq
    for IdHashMap<T, S, A>
{
}

/// The `Extend` implementation overwrites duplicates. In the future, there will
/// also be an `extend_unique` method that will return an error.
///
/// # Examples
///
/// ```
/// # #[cfg(feature = "default-hasher")] {
/// use iddqd::{IdHashItem, IdHashMap, id_upcast};
///
/// #[derive(Debug, PartialEq, Eq, Hash)]
/// struct Item {
///     id: String,
///     value: u32,
/// }
///
/// impl IdHashItem for Item {
///     type Key<'a> = &'a str;
///     fn key(&self) -> Self::Key<'_> {
///         &self.id
///     }
///     id_upcast!();
/// }
///
/// let mut map = IdHashMap::new();
/// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
///
/// let new_items = vec![
///     Item { id: "foo".to_string(), value: 100 }, // overwrites existing
///     Item { id: "bar".to_string(), value: 20 },  // new item
/// ];
///
/// map.extend(new_items);
/// assert_eq!(map.len(), 2);
/// assert_eq!(map.get("foo").unwrap().value, 100); // overwritten
/// assert_eq!(map.get("bar").unwrap().value, 20); // new
///
/// # }
/// ```
impl<T: IdHashItem, S: Clone + BuildHasher, A: Allocator> Extend<T>
    for IdHashMap<T, S, A>
{
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        // Keys may already be present in the map, or multiple times in the
        // iterator. Reserve the entire hint lower bound if the map is empty.
        // Otherwise reserve half the hint (rounded up), so the map will only
        // resize twice in the worst case.
        let iter = iter.into_iter();
        let reserve = if self.is_empty() {
            iter.size_hint().0
        } else {
            iter.size_hint().0.div_ceil(2)
        };
        self.reserve(reserve);
        for item in iter {
            self.insert_overwrite(item);
        }
    }
}

impl<'a, T: IdHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
    for &'a IdHashMap<T, S, A>
{
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    /// Creates an iterator over references to the items in the map.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
    ///
    /// let mut values: Vec<u32> =
    ///     (&map).into_iter().map(|item| item.value).collect();
    /// values.sort();
    /// assert_eq!(values, vec![20, 42]);
    /// # }
    /// ```
    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<'a, T: IdHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
    for &'a mut IdHashMap<T, S, A>
{
    type Item = RefMut<'a, T, S>;
    type IntoIter = IterMut<'a, T, S, A>;

    /// Creates an iterator over mutable references to the items in the map.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
    ///
    /// for mut item in &mut map {
    ///     item.value *= 2;
    /// }
    ///
    /// assert_eq!(map.get("foo").unwrap().value, 84);
    /// assert_eq!(map.get("bar").unwrap().value, 40);
    /// # }
    /// ```
    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

impl<T: IdHashItem, S: Clone + BuildHasher, A: Allocator> IntoIterator
    for IdHashMap<T, S, A>
{
    type Item = T;
    type IntoIter = IntoIter<T, A>;

    /// Consumes the map and creates an iterator over the owned items.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "default-hasher")] {
    /// use iddqd::{IdHashItem, IdHashMap, id_upcast};
    ///
    /// #[derive(Debug, PartialEq, Eq, Hash)]
    /// struct Item {
    ///     id: String,
    ///     value: u32,
    /// }
    ///
    /// impl IdHashItem for Item {
    ///     type Key<'a> = &'a str;
    ///     fn key(&self) -> Self::Key<'_> {
    ///         &self.id
    ///     }
    ///     id_upcast!();
    /// }
    ///
    /// let mut map = IdHashMap::new();
    /// map.insert_unique(Item { id: "foo".to_string(), value: 42 }).unwrap();
    /// map.insert_unique(Item { id: "bar".to_string(), value: 20 }).unwrap();
    ///
    /// let mut values: Vec<u32> = map.into_iter().map(|item| item.value).collect();
    /// values.sort();
    /// assert_eq!(values, vec![20, 42]);
    /// # }
    /// ```
    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        IntoIter::new(self.items)
    }
}

/// The `FromIterator` implementation for `IdHashMap` overwrites duplicate
/// items.
///
/// To reject duplicates, use [`IdHashMap::from_iter_unique`].
///
/// # Examples
///
/// ```
/// # #[cfg(feature = "default-hasher")] {
/// use iddqd::{IdHashItem, IdHashMap, id_upcast};
///
/// #[derive(Debug, PartialEq, Eq, Hash)]
/// struct Item {
///     id: String,
///     value: u32,
/// }
///
/// impl IdHashItem for Item {
///     type Key<'a> = &'a str;
///     fn key(&self) -> Self::Key<'_> {
///         &self.id
///     }
///     id_upcast!();
/// }
///
/// let items = vec![
///     Item { id: "foo".to_string(), value: 42 },
///     Item { id: "bar".to_string(), value: 20 },
///     Item { id: "foo".to_string(), value: 100 }, // duplicate key, overwrites
/// ];
///
/// let map: IdHashMap<Item> = items.into_iter().collect();
/// assert_eq!(map.len(), 2);
/// assert_eq!(map.get("foo").unwrap().value, 100); // last value wins
/// assert_eq!(map.get("bar").unwrap().value, 20);
/// # }
/// ```
impl<T: IdHashItem, S: Default + Clone + BuildHasher, A: Allocator + Default>
    FromIterator<T> for IdHashMap<T, S, A>
{
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut map = IdHashMap::default();
        map.extend(iter);
        map
    }
}

#[cfg(all(test, feature = "std"))]
mod tests {
    use super::*;
    use core::{cell::Cell, hash::Hasher};

    std::thread_local! {
        static USER_HASH_CALLS: Cell<u32> = const { Cell::new(0) };
    }

    #[derive(Debug)]
    struct CountedKey(u32);

    impl Hash for CountedKey {
        fn hash<H: Hasher>(&self, state: &mut H) {
            USER_HASH_CALLS.with(|c| c.set(c.get() + 1));
            self.0.hash(state);
        }
    }

    impl PartialEq for CountedKey {
        fn eq(&self, other: &Self) -> bool {
            self.0 == other.0
        }
    }
    impl Eq for CountedKey {}

    #[derive(Debug)]
    struct CountedItem {
        id: u32,
    }

    impl IdHashItem for CountedItem {
        type Key<'a> = CountedKey;
        fn key(&self) -> Self::Key<'_> {
            CountedKey(self.id)
        }
        id_upcast!();
    }

    // This is a unit test and not an integration test to ensure rehashing
    // actually happens. (Rehashing is not externally observable in integration
    // tests.)
    #[test]
    fn reserve_rehash_uses_cached_hash() {
        let mut map = IdHashMap::<CountedItem, _>::with_hasher(
            foldhash::fast::FixedState::with_seed(0),
        );
        // Insert items (legitimately calls user Hash).
        for id in [
            0u32, 17, 1, 12, 5, 21, 8, 10, 18, 4, 16, 22, 9, 24, 23, 13, 7, 25,
            26, 20, 31, 11, 14, 2, 6,
        ] {
            let _ = map.insert_overwrite(CountedItem { id });
        }
        // Drop most entries, leaving the table heavy with tombstones so the
        // next reserve favors `rehash_in_place` over a fresh-allocation grow.
        map.retain(|item| item.id % 2 == 1 && item.id % 3 != 0);

        USER_HASH_CALLS.with(|c| c.set(0));
        let rehash_calls = map.tables.key_to_item.reserve_counting_rehash(10);
        let user_calls = USER_HASH_CALLS.with(Cell::get);

        assert!(
            rehash_calls > 0,
            "expected reserve to invoke the rehash callback at least once \
             (setup did not actually trigger a rehash; if hashbrown's \
             growth/rehash heuristic changed, retune the constants)",
        );
        assert_eq!(
            user_calls, 0,
            "reserve must not invoke user `Hash` during rehash; got \
             {user_calls} call(s) for {rehash_calls} rehash-callback \
             invocation(s)",
        );

        map.validate(ValidateCompact::NonCompact)
            .expect("map remains valid after reserve");
    }
}