bumpish 0.1.0

mod bucket;
mod entry;
mod error;
mod inner;
mod iter;

use self::bucket::{Bucket, BucketPtr};
pub use self::entry::{Entry, OccupiedEntry, VacantEntry};
pub use self::error::OccupiedError;
use self::inner::Core;
pub use self::iter::{Drain, Iter, IterMut};
use core::cell::UnsafeCell;
use core::fmt::{self, Debug};
use core::hash::{BuildHasher, Hash};
use equivalent::Equivalent;
use hashbrown::{HashTable, hash_table};

#[cfg(feature = "std")]
use std::hash::RandomState;

type Entries<K, V> = crate::stk::BumpStk<Bucket<K, V>>;

#[cfg(feature = "std")]
pub struct BumpMap<K, V, S = RandomState> {
    core: Core<K, V>,
    hasher: S,
}

#[cfg(not(feature = "std"))]
pub struct BumpMap<K, V, S> {
    core: Core<K, V>,
    hasher: S,
}

#[cfg(feature = "std")]
impl<K, V> BumpMap<K, V, RandomState> {
    /// Creates an empty `BumpMap`.
    ///
    /// The new map will not allocate until it is first pair inserted into.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let mut map: BumpMap<&str, i32> = BumpMap::new();
    /// assert_eq!(map.capacity(), 0);
    /// ```
    #[inline]
    #[must_use]
    pub fn new() -> Self {
        Default::default()
    }

    /// Creates an empty `BumpMap` with at least the specified capacity.
    ///
    /// The hash map will be able to hold at least `capacity` elements without
    /// reallocating. This method is allowed to allocate for more elements than
    /// `capacity`. If `capacity` is zero, the hash map will not allocate.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let map: BumpMap<&str, i32> = BumpMap::with_capacity(10);
    /// assert!(map.capacity() >= 10);
    /// ```
    #[inline]
    #[must_use]
    pub fn with_capacity(capacity: usize) -> Self {
        BumpMap::with_capacity_and_hasher(capacity, Default::default())
    }
}

impl<K, V, S> BumpMap<K, V, S> {
    /// Creates an empty `BumpMap` which will use the given hash builder to hash
    /// keys.
    ///
    /// The new map will not allocate until it is first pair inserted into.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    /// use std::hash::RandomState;
    ///
    /// let s = RandomState::new();
    /// let mut map = BumpMap::with_hasher(s);
    /// map.insert(1, 2);
    /// ```
    pub const fn with_hasher(hasher: S) -> Self {
        BumpMap {
            core: Core::new(),
            hasher,
        }
    }

    /// Creates an empty `BumpMap` with at least the specified capacity, using
    /// `hasher` to hash the keys.
    ///
    /// The map will be able to hold at least `capacity` elements without
    /// reallocating. This method is allowed to allocate for more elements than
    /// `capacity`. If `capacity` is zero, the hash map will not allocate.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    /// use std::hash::RandomState;
    ///
    /// let s = RandomState::new();
    /// let mut map = BumpMap::with_capacity_and_hasher(10, s);
    /// map.insert(1, 2);
    /// assert!(map.capacity() >= 10);
    /// ```
    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
        BumpMap {
            core: Core::with_capacity(capacity),
            hasher: hash_builder,
        }
    }

    /// Returns the number of elements the map can hold without reallocating.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let map: BumpMap<i32, i32> = BumpMap::with_capacity(100);
    /// assert!(map.capacity() >= 100);
    /// ```
    #[inline]
    pub fn capacity(&self) -> usize {
        self.core.capacity()
    }

    /// Returns the number of elements in the map.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let mut a = BumpMap::new();
    /// assert_eq!(a.len(), 0);
    /// a.insert(1, "a");
    /// assert_eq!(a.len(), 1);
    /// ```
    #[inline]
    pub fn len(&self) -> usize {
        self.core.len()
    }

    /// Returns `true` if the map contains no elements.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let mut a = BumpMap::new();
    /// assert!(a.is_empty());
    /// a.insert(1, "a");
    /// assert!(!a.is_empty());
    /// ```
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Clears the map, removing all key-value pairs. Can keep some of the
    /// allocated memory for reuse.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let mut a = BumpMap::new();
    /// a.insert(1, "a");
    /// a.clear();
    /// assert!(a.is_empty());
    /// ```
    pub fn clear(&mut self) {
        self.core.clear();
    }

    /// An iterator visiting all key-value pairs in insertion order. The
    /// iterator element type is `(&'a K, &'a V)`.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    ///
    /// let map = BumpMap::from([
    ///     ("a", 1),
    ///     ("b", 2),
    ///     ("c", 3),
    /// ]);
    ///
    /// assert_eq!(
    ///     map.iter().collect::<Vec<(_, _)>>(),
    ///     [(&"a", &1), (&"b", &2), (&"c", &3)]
    /// );
    /// ```
    pub fn iter(&self) -> Iter<'_, K, V> {
        Iter::new(&self.core.entries)
    }

    /// An iterator visiting all key-value pairs in insertion order, with
    /// mutable references to the values. The iterator element type is `(&'a K,
    /// &'a mut V)`.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    ///
    /// let mut map = BumpMap::from([
    ///     ("a", 1),
    ///     ("b", 2),
    ///     ("c", 3),
    /// ]);
    ///
    /// // Update all values
    /// for (_, val) in map.iter_mut() {
    ///     *val *= 2;
    /// }
    ///
    /// assert_eq!(
    ///     map.iter().collect::<Vec<(_, _)>>(),
    ///     [(&"a", &2), (&"b", &4), (&"c", &6)]
    /// );
    /// ```
    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
        IterMut::new(&mut self.core.entries)
    }

    /// An iterator visiting all keys in insertion order. The iterator element
    /// type is `&'a K`.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    ///
    /// let map = BumpMap::from([
    ///     ("a", 1),
    ///     ("b", 2),
    ///     ("c", 3),
    /// ]);
    ///
    /// for key in map.keys() {
    ///     println!("{key}");
    /// }
    /// ```
    pub fn keys(&self) -> impl Iterator<Item = &K> {
        self.iter().map(|(k, _)| k)
    }

    /// An iterator visiting all values in insertion order. The iterator element
    /// type is `&'a V`.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    ///
    /// let map = BumpMap::from([
    ///     ("a", 1),
    ///     ("b", 2),
    ///     ("c", 3),
    /// ]);
    ///
    /// for val in map.values() {
    ///     println!("{val}");
    /// }
    /// ```
    pub fn values(&self) -> impl Iterator<Item = &V> {
        self.iter().map(|(_, v)| v)
    }

    /// An iterator visiting all values mutably in insertion order. The iterator
    /// element type is `&'a mut V`.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    ///
    /// let mut map = BumpMap::from([
    ///     ("a", 1),
    ///     ("b", 2),
    ///     ("c", 3),
    /// ]);
    ///
    /// for val in map.values_mut() {
    ///     *val = *val + 10;
    /// }
    ///
    /// for val in map.values() {
    ///     println!("{val}");
    /// }
    /// ```
    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> {
        self.iter_mut().map(|(_, v)| v)
    }
}

impl<K: Eq, V, S> BumpMap<K, V, S> {
    /// Clears the map, returning all key-value pairs as an iterator. Can keep
    /// some of the allocated memory for reuse.
    ///
    /// If the returned iterator is dropped before being fully consumed, it
    /// drops the remaining key-value pairs.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    ///
    /// let mut a = BumpMap::new();
    /// a.insert(1, "a");
    /// a.insert(2, "b");
    ///
    /// for (k, v) in a.drain().take(1) {
    ///     assert!(k == 1 || k == 2);
    ///     assert!(v == "a" || v == "b");
    /// }
    ///
    /// assert!(a.is_empty());
    /// assert!(a.capacity() > 0);
    /// ```
    pub fn drain(&mut self) -> Drain<'_, K, V> {
        Drain::new(&mut self.core)
    }
}

impl<K, V, S> BumpMap<K, V, S>
where
    S: BuildHasher,
{
    /// Returns a reference to the map's [`BuildHasher`].
    ///
    /// [`BuildHasher`]: https://doc.rust-lang.org/beta/std/hash/trait.BuildHasher.html
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    /// use std::hash::RandomState;
    ///
    /// let hasher = RandomState::new();
    /// let map: BumpMap<i32, i32> = BumpMap::with_hasher(hasher);
    /// let hasher: &RandomState = map.hasher();
    /// ```
    pub fn hasher(&self) -> &S {
        &self.hasher
    }

    /// Returns `true` if the map contains a value with an equivalent key to `key`.
    ///
    /// The `Q` type **must** hash like `K`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let mut map = BumpMap::new();
    /// map.insert("a".to_owned(), 1);
    /// assert_eq!(map.contains_key("a"), true);
    /// assert_eq!(map.contains_key(&"a".to_owned()), true);
    /// assert_eq!(map.contains_key("b"), false);
    /// ```
    pub fn contains_key<Q>(&self, key: &Q) -> bool
    where
        Q: ?Sized + Hash + Equivalent<K>,
    {
        self.core.contains_key(|| self.hasher.hash_one(key), key)
    }

    /// Returns a reference to the value corresponding to the key.
    ///
    /// The `Q` type **must** hash like `K`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let mut map = BumpMap::new();
    /// map.insert(1, "a");
    /// assert_eq!(map.get(&1), Some(&"a"));
    /// assert_eq!(map.get(&2), None);
    /// ```
    pub fn get<Q>(&self, key: &Q) -> Option<&V>
    where
        Q: ?Sized + Hash + Equivalent<K>,
    {
        let hash = self.hasher.hash_one(key);
        self.core.get_key_value(hash, key).map(|(_, value)| value)
    }

    /// Returns the key-value pair corresponding to the supplied key. This is
    /// potentially useful:
    /// - for key types where non-identical keys can be considered equal;
    /// - for getting the `&K` stored key value from an equivalent `&Q` lookup key; or
    /// - for getting a reference to a key with the same lifetime as the collection.
    ///
    /// The `Q` type **must** hash like `K`.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    /// use std::hash::{Hash, Hasher};
    ///
    /// #[derive(Clone, Copy, Debug)]
    /// struct S {
    ///     id: u32,
    /// #   #[allow(unused)]
    ///     name: &'static str, // ignored by equality and hashing operations
    /// }
    ///
    /// impl PartialEq for S {
    ///     fn eq(&self, other: &S) -> bool {
    ///         self.id == other.id
    ///     }
    /// }
    ///
    /// impl Eq for S {}
    ///
    /// impl Hash for S {
    ///     fn hash<H: Hasher>(&self, state: &mut H) {
    ///         self.id.hash(state);
    ///     }
    /// }
    ///
    /// let j_a = S { id: 1, name: "Jessica" };
    /// let j_b = S { id: 1, name: "Jess" };
    /// let p = S { id: 2, name: "Paul" };
    /// assert_eq!(j_a, j_b);
    ///
    /// let mut map = BumpMap::new();
    /// map.insert(j_a, "Paris");
    /// assert_eq!(map.get_key_value(&j_a), Some((&j_a, &"Paris")));
    /// assert_eq!(map.get_key_value(&j_b), Some((&j_a, &"Paris"))); // the notable case
    /// assert_eq!(map.get_key_value(&p), None);
    /// ```
    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
    where
        Q: ?Sized + Hash + Equivalent<K>,
    {
        let hash = self.hasher.hash_one(key);
        self.core.get_key_value(hash, key)
    }

    /// Returns a mutable reference to the value corresponding to the key.
    ///
    /// The `Q` type **must** hash like `K`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    ///
    /// let mut map = BumpMap::new();
    /// map.insert(1, "a");
    /// if let Some(x) = map.get_mut(&1) {
    ///     *x = "b";
    /// }
    /// assert_eq!(map[&1], "b");
    /// ```
    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
    where
        Q: ?Sized + Hash + Equivalent<K>,
    {
        let hash = self.hasher.hash_one(key);
        self.core.get_mut(hash, key)
    }
}

impl<K, V, S> BumpMap<K, V, S>
where
    K: Hash + Eq,
    S: BuildHasher,
{
    /// Inserts a key-value pair into the map.
    ///
    /// If the map did not have this key present, [`None`] is returned.
    ///
    /// If the map did have an equivalent key present, the value is updated, and
    /// the old value is returned. The key is not updated in any case.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let mut map = BumpMap::new();
    /// assert_eq!(map.insert(37, "a"), None);
    ///
    /// map.insert(37, "b");
    /// assert_eq!(map.insert(37, "c"), Some("b"));
    /// assert_eq!(map[&37], "c");
    /// ```
    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
        let hash = self.hasher.hash_one(&key);
        self.core.insert(hash, key, value)
    }

    /// Tries to insert a key-value pair into the map, and returns a mutable
    /// reference to the value in the entry.
    ///
    /// If the map already has this key present, nothing is updated, and an
    /// error containing the occupied entry and the value is returned.
    ///
    /// Because of there is bump allocation under the hood, this method doesn't
    /// require a mutable reference to self.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let map = BumpMap::new();
    /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
    ///
    /// let err = map.try_insert(37, "b").unwrap_err();
    /// assert_eq!(err.entry.key(), &37);
    /// assert_eq!(err.entry.get(), &"a");
    /// assert_eq!(err.value, "b");
    /// ```
    pub fn try_insert(&self, key: K, value: V) -> Result<&V, OccupiedError<'_, K, V>> {
        let hash = self.hasher.hash_one(&key);
        self.core.try_insert(hash, key, value)
    }

    /// Gets the given key's corresponding entry in the map.
    ///
    /// As distinct from standard `HashMap::entry`, this method returns an
    /// `Entry` that can't be used to modify the value associated with the key.
    /// That allows to call `entry` method with a shared reference to the map.
    ///
    /// But this still allows to insert a new key-value pair into the vacant
    /// entry.
    ///
    /// # Examples
    ///
    /// ```
    /// use bumpish::BumpMap;
    ///
    /// let mut letters = BumpMap::new();
    ///
    /// for ch in "a short treatise on fungi".chars() {
    ///     letters.entry(ch).or_insert(true);
    /// }
    ///
    /// assert_eq!(letters[&'s'], true);
    /// assert_eq!(letters[&'t'], true);
    /// assert_eq!(letters[&'u'], true);
    /// assert_eq!(letters.get(&'y'), None);
    /// ```
    pub fn entry(&self, key: K) -> Entry<'_, K, V> {
        let hash = self.hasher.hash_one(&key);
        self.core.entry(hash, key)
    }
}

impl<K, V, S> BumpMap<K, V, S>
where
    K: Eq + Hash,
    S: BuildHasher,
{
    /// Extends the map with the contents of an iterator. If a key already
    /// exists in this map, the key and corresponding value are dropped.
    pub fn extend_absent<I>(&self, iter: I)
    where
        I: IntoIterator<Item = (K, V)>,
    {
        for (k, v) in iter {
            let hash = self.hasher.hash_one(&k);
            _ = self.core.try_insert(hash, k, v);
        }
    }
}

impl<K, V, S> core::clone::Clone for BumpMap<K, V, S>
where
    K: Clone,
    V: Clone,
    S: Clone,
{
    fn clone(&self) -> Self {
        Self {
            core: self.core.clone(),
            hasher: self.hasher.clone(),
        }
    }
}

impl<K, V, S> Debug for BumpMap<K, V, S>
where
    K: Debug,
    V: Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_map().entries(self.iter()).finish()
    }
}

impl<K, V, S> Default for BumpMap<K, V, S>
where
    S: Default,
{
    /// Creates an empty `BumpMap<K, V, S>`, with the `Default` value for the hasher.
    #[inline]
    fn default() -> Self {
        Self::with_hasher(Default::default())
    }
}

impl<K, V, S> Eq for BumpMap<K, V, S>
where
    K: Eq + Hash,
    V: Eq,
    S: BuildHasher,
{
}

impl<K, V, S> PartialEq for BumpMap<K, V, S>
where
    K: Eq + Hash,
    V: PartialEq,
    S: BuildHasher,
{
    fn eq(&self, other: &Self) -> bool {
        if self.len() != other.len() {
            return false;
        }
        self.iter().all(|(k, v)| other.get(k) == Some(v))
    }
}

#[cfg(feature = "std")]
impl<K, V, const N: usize> From<[(K, V); N]> for BumpMap<K, V, RandomState>
where
    K: Eq + Hash,
{
    /// Converts a `[(K, V); N]` into a `BumpMap<K, V>`.
    ///
    /// If any entries in the array have equal keys, all but one of the
    /// corresponding values will be dropped.
    ///
    /// # Examples
    ///
    /// ```
    /// # use bumpish::BumpMap;
    /// let map1 = BumpMap::from([(1, 2), (3, 4)]);
    /// let map2: BumpMap<_, _> = [(1, 2), (3, 4)].into();
    /// assert_eq!(map1, map2);
    /// ```
    fn from(arr: [(K, V); N]) -> Self {
        Self::from_iter(arr)
    }
}

impl<K, V, S> FromIterator<(K, V)> for BumpMap<K, V, S>
where
    K: Eq + Hash,
    S: BuildHasher + Default,
{
    /// Constructs a `BumpMap<K, V>` from an iterator of key-value pairs.
    ///
    /// If the iterator produces any pairs with equal keys, all but one of the
    /// corresponding values will be dropped.
    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
        let map = Self::with_hasher(Default::default());
        for (k, v) in iter {
            _ = map.try_insert(k, v);
        }
        map
    }
}

impl<'a, K, V, S> Extend<(&'a K, &'a V)> for BumpMap<K, V, S>
where
    K: Eq + Hash + Copy,
    V: Copy,
    S: BuildHasher,
{
    fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
        self.extend(iter.into_iter().map(|(k, v)| (*k, *v)));
    }
}

impl<K, V, S> Extend<(K, V)> for BumpMap<K, V, S>
where
    K: Eq + Hash,
    S: BuildHasher,
{
    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
        for (k, v) in iter {
            self.insert(k, v);
        }
    }
}

impl<K, Q: ?Sized, V, S> core::ops::Index<&Q> for BumpMap<K, V, S>
where
    K: Eq + Hash,
    Q: Eq + Hash + Equivalent<K>,
    S: BuildHasher,
{
    type Output = V;

    /// Returns a reference to the value corresponding to the supplied key.
    ///
    /// # Panics
    ///
    /// Panics if the key is not present in the `BumpMap`.
    #[inline]
    fn index(&self, key: &Q) -> &Self::Output {
        self.get(key).expect("no entry found for key")
    }
}

impl<'a, K, V, S> IntoIterator for &'a BumpMap<K, V, S> {
    type Item = (&'a K, &'a V);
    type IntoIter = Iter<'a, K, V>;

    #[inline]
    fn into_iter(self) -> Iter<'a, K, V> {
        self.iter()
    }
}

impl<'a, K, V, S> IntoIterator for &'a mut BumpMap<K, V, S> {
    type Item = (&'a K, &'a mut V);
    type IntoIter = IterMut<'a, K, V>;

    #[inline]
    fn into_iter(self) -> IterMut<'a, K, V> {
        self.iter_mut()
    }
}