bumpish 0.2.0

use super::bucket::{Bucket, BucketPtr};
use super::entry::{Entry, OccupiedEntry, VacantEntry};
use core::cell::UnsafeCell;
use core::hash::Hash;
use equivalent::Equivalent;
use hashbrown::{HashTable, hash_table};

pub(super) type Entries<K, V> = crate::stk::BumpStk<Bucket<K, V>>;

pub(super) struct Core<K, V> {
    pub(super) hash_table: UnsafeCell<HashTable<BucketPtr<K, V>>>,
    pub(super) entries: Entries<K, V>,
}

impl<K, V> Core<K, V> {
    pub(super) const fn new() -> Self {
        Self {
            hash_table: UnsafeCell::new(HashTable::new()),
            entries: Entries::new(),
        }
    }

    pub(super) fn with_capacity(n: usize) -> Self {
        Self {
            hash_table: UnsafeCell::new(HashTable::with_capacity(n)),
            entries: Entries::with_capacity(n),
        }
    }

    pub(super) fn capacity(&self) -> usize {
        usize::min(
            self.entries.capacity(),
            unsafe { self.hashtab() }.capacity(),
        )
    }

    pub(super) fn clear(&mut self) {
        self.hash_table.get_mut().clear();
        self.entries.clear();
    }

    pub(super) fn len(&self) -> usize {
        assert_eq!(self.entries.len(), unsafe { self.hashtab() }.len());
        self.entries.len()
    }

    /// > **N.B.** The `Q` type must hash like `K`.
    pub(super) fn contains_key<F, Q>(&self, hasher: F, key: &Q) -> bool
    where
        F: Fn() -> u64,
        Q: ?Sized + Hash + Equivalent<K>,
    {
        let hash_table = unsafe { self.hashtab() };
        if hash_table.is_empty() {
            false
        } else {
            hash_table.find(hasher(), eq_fn(key)).is_some()
        }
    }

    pub(super) fn get_key_value<Q>(&self, hash: u64, key: &Q) -> Option<(&K, &V)>
    where
        Q: ?Sized + Hash + Equivalent<K>,
    {
        let hash_table = unsafe { self.hashtab() };
        if let Some(ptr) = hash_table.find(hash, eq_fn(key)) {
            let bucket = unsafe { ptr.as_ref() };
            Some(bucket.as_tuple())
        } else {
            None
        }
    }

    pub(super) fn get_mut<Q>(&mut self, hash: u64, key: &Q) -> Option<&mut V>
    where
        Q: ?Sized + Hash + Equivalent<K>,
    {
        let hash_table = self.hash_table.get_mut();
        if let Some(ptr) = hash_table.find_mut(hash, eq_fn(key)) {
            let bucket = unsafe { ptr.as_mut() };
            Some(bucket.as_tuple_mut().1)
        } else {
            None
        }
    }

    pub(super) fn insert_unique(&self, hash: u64, key: K, value: V) -> BucketPtr<K, V> {
        let bucket = Bucket::new(hash, key, value);
        let bucket_ptr = self.entries.push_ptr(|| bucket);
        let hash_table = unsafe { &mut *self.hash_table.get() };
        hash_table.insert_unique(hash, bucket_ptr, hash_fn());
        bucket_ptr
    }

    unsafe fn hashtab(&self) -> &HashTable<BucketPtr<K, V>> {
        unsafe { &*self.hash_table.get() }
    }
}

impl<K: Eq, V> Core<K, V> {
    pub(super) fn pop(&mut self) -> Option<Bucket<K, V>> {
        if let Some(bucket) = self.entries.pop() {
            let hash_table = self.hash_table.get_mut();
            let entry = hash_table.find_entry(bucket.hash, eq_fn(&bucket.key));
            unsafe { entry.unwrap_unchecked().remove() };
            Some(bucket)
        } else {
            None
        }
    }

    pub(super) fn entry(&self, hash: u64, key: K) -> Entry<'_, K, V> {
        let hash_table = unsafe { &mut *self.hash_table.get() };
        match hash_table.entry(hash, eq_fn(&key), hash_fn()) {
            hash_table::Entry::Occupied(entry) => {
                Entry::Occupied(unsafe { OccupiedEntry::new(*entry.get()) })
            }
            hash_table::Entry::Vacant(_) => Entry::Vacant(VacantEntry::new(hash, key, self)),
        }
    }

    /// Inserts a new entry if there is no entry corresponding to `hash`/`key`,
    /// and returns reference to the new value.
    pub(super) fn insert(
        &self,
        hash: u64,
        key: K,
        value: V,
    ) -> Result<BucketPtr<K, V>, InsertionError<'_, K, V>> {
        let hash_table = unsafe { &mut *self.hash_table.get() };
        match hash_table.find_entry(hash, eq_fn(&key)) {
            Ok(entry) => {
                let bucket_ptr = *entry.get();
                Err(InsertionError::new(key, value, bucket_ptr))
            }
            Err(absent_entry) => {
                let new_bucket = Bucket::new(hash, key, value);
                let bucket_ptr = self.entries.push_ptr(|| new_bucket);
                let table = absent_entry.into_table();
                table.insert_unique(hash, bucket_ptr, hash_fn());
                Ok(bucket_ptr)
            }
        }
    }

    /// Update both key and value corresponding to `hash`/`key` within this map.
    /// If the `key`'s entry does not exist, insert a new `key`/`value` pair.
    ///
    /// If the entry were updated, returns both old key and value. Otherwise,
    /// returns `None`.
    ///
    /// Can preallocate memory for a possible new insertion.
    pub(super) fn update_full(&mut self, hash: u64, key: K, value: V) -> Option<(K, V)> {
        let hash_table = self.hash_table.get_mut();
        match hash_table.entry(hash, eq_fn(&key), hash_fn()) {
            hash_table::Entry::Occupied(mut entry) => {
                let ptr = entry.get_mut();
                let bucket = unsafe { ptr.as_mut() };
                let mut new_bucket = Bucket::new(hash, key, value);
                core::mem::swap(&mut bucket.key, &mut new_bucket.key);
                core::mem::swap(&mut bucket.value, &mut new_bucket.value);
                Some((new_bucket.key, new_bucket.value))
            }
            hash_table::Entry::Vacant(entry) => {
                let new_bucket = Bucket::new(hash, key, value);
                let bucket_ptr = self.entries.push_ptr(|| new_bucket);
                entry.insert(bucket_ptr);
                None
            }
        }
    }

    /// Update a value corresponding to `hash`/`key` within this map. If the
    /// `key`'s entry does not exist, insert a new `key`/`value` pair.
    ///
    /// If the entry were updated, returns the old value. Otherwise, returns
    /// `None`.
    ///
    /// Can preallocate memory for a possible new insertion.
    pub(super) fn update(&mut self, hash: u64, k: K, v: V) -> Option<V> {
        let hash_table = self.hash_table.get_mut();
        match hash_table.entry(hash, eq_fn(&k), hash_fn()) {
            hash_table::Entry::Occupied(mut entry) => {
                let ptr = entry.get_mut();
                let bucket = unsafe { ptr.as_mut() };
                let mut new_bucket = Bucket::new(hash, k, v);
                core::mem::swap(&mut bucket.value, &mut new_bucket.value);
                Some(new_bucket.value)
            }
            hash_table::Entry::Vacant(entry) => {
                let new_bucket = Bucket::new(hash, k, v);
                let bucket_ptr = self.entries.push_ptr(|| new_bucket);
                entry.insert(bucket_ptr);
                None
            }
        }
    }
}

fn hash_fn<K, V>() -> impl Fn(&BucketPtr<K, V>) -> u64 {
    |ptr: &BucketPtr<K, V>| -> u64 {
        let bucket = unsafe { ptr.as_ref() };
        bucket.hash
    }
}

fn eq_fn<K, Q, V>(key: &Q) -> impl FnMut(&BucketPtr<K, V>) -> bool
where
    Q: ?Sized + Equivalent<K>,
{
    |ptr: &BucketPtr<K, V>| -> bool {
        let bucket = unsafe { ptr.as_ref() };
        Equivalent::equivalent(key, &bucket.key)
    }
}

impl<K, V> core::clone::Clone for Core<K, V>
where
    K: Clone,
    V: Clone,
{
    fn clone(&self) -> Self {
        let hash_table = unsafe { self.hashtab() };
        Self {
            hash_table: UnsafeCell::new(hash_table.clone()),
            entries: self.entries.clone(),
        }
    }
}

#[derive(PartialEq, Eq)]
pub(super) struct InsertionError<'a, K, V> {
    pub(super) key: K,
    pub(super) new_value: V,
    pub(super) old_bucket_ptr: BucketPtr<K, V>,
    phantom: std::marker::PhantomData<(&'a K, &'a V)>,
}

impl<'a, K, V> InsertionError<'a, K, V> {
    pub(super) fn new(key: K, new_value: V, old_bucket_ptr: BucketPtr<K, V>) -> Self {
        Self {
            key,
            new_value,
            old_bucket_ptr,
            phantom: std::marker::PhantomData,
        }
    }
}