reslab 0.0.0

mod entry;
mod r#ref;

use std::{
    collections::hash_map::RandomState,
    fmt::Debug,
    hash::{BuildHasher, Hash},
    ops::Deref,
    sync::Arc,
};

use dashmap::DashMap;
use sharded_slab::Slab;

#[doc(inline)]
pub use self::entry::{Entry, OccupiedEntry, VacantEntry};
#[doc(inline)]
pub use self::r#ref::{OwnedRef, Ref, RefWrapper};

/// A trait that represents a key that can be used to identify an entry.
pub trait Key: Copy + Eq + Hash {}

impl<T> Key for T where T: Copy + Eq + Hash {}

/// A trait that represents a key-identifiable value that can be stored in a
/// [`ReSlab`].
///
/// This allows for [`ReSlab::get_by`] to be used to get a reference to a value
/// by its key, without having to pay the cost of a hash lookup.
pub trait Keyed {
    /// The type of key used to identify the value.
    type Key: Key;

    /// Gets the key used to identify the value.
    fn key(&self) -> Self::Key;
}

/// A type that represents a unique index into a [`ReSlab`].
#[derive(Debug, Copy, Clone)]
pub struct Index<K: Key, V> {
    off: usize,
    key: K,
    _marker: std::marker::PhantomData<V>,
}

/// A thread-safe hash table that can be used to store objects that can be
pub struct ReSlab<K: Key, V, S = RandomState> {
    idxs: DashMap<K, usize, S>,
    slab: Arc<Slab<V>>,
}

impl<K: Key, V, S> ReSlab<K, V, S>
where
    S: Default + BuildHasher + Clone,
{
    /// Creates a new instance of [`ReSlab`].
    #[inline]
    pub fn new() -> Self {
        Self::with_capacity(0)
    }

    /// Creates a new instance of [`ReSlab`] with the provided hasher.
    #[inline]
    pub fn with_hasher(builder: S) -> Self {
        Self::with_capacity_and_hasher(0, builder)
    }

    /// Creates a new instance of [`ReSlab`] with the provided capacity.
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        Self::with_capacity_and_hasher(capacity, Default::default())
    }

    /// Creates a new instance of [`ReSlab`] with the provided capacity and
    /// hasher.
    #[inline]
    pub fn with_capacity_and_hasher(capacity: usize, builder: S) -> Self {
        Self {
            idxs: DashMap::with_capacity_and_hasher(capacity, builder.clone()),
            slab: Arc::new(Slab::new()),
        }
    }

    /// Gets an borrowed reference to the value with the provided key.
    ///
    /// # Panics
    /// This method will panic if the provided key exists, but has no associated
    /// slab slot.
    #[inline]
    pub fn get<'a>(&'a self, key: &K) -> Option<Ref<'a, K, V>> {
        self.idxs.get(key).map(|offset| {
            let entry = unsafe { self.get_direct(*offset.value()) };

            entry.expect("BUG: dangling index found in indeces map")
        })
    }

    /// Gets a borrowed reference to the value with the provided index.
    ///
    /// This method is useful when you already have an index, and don't want to
    /// pay the cost of a hash lookup.
    pub fn get_by<'a>(&'a self, index: &Index<K, V>) -> Option<Ref<'a, K, V>>
    where
        V: Keyed<Key = K>,
    {
        self.slab
            .get(index.offset())
            .filter(|i| i.deref().key() == index.key())
            .map(Ref::new)
    }

    /// Gets a borrowed reference to the value at the provided slab offset.
    ///
    /// # Safety
    /// This method is unsafe because it does not validate that the provided
    /// offset has an associated key, thus making it possible to reference
    /// dangling slab entries.
    #[inline]
    pub unsafe fn get_direct(&self, offset: usize) -> Option<Ref<'_, K, V>> {
        self.slab.get(offset).map(Ref::new)
    }

    /// Gets an owned reference to the value with the provided key.
    ///
    /// # Panics
    /// This method will panic if the provided key exists, but has no associated
    /// slab slot.
    #[inline]
    pub fn get_owned(&self, key: &K) -> Option<OwnedRef<K, V>> {
        self.idxs.get(key).map(|offset| {
            let entry = unsafe { self.get_owned_direct(*offset.value()) };

            entry.expect("BUG: dangling index found in indeces map")
        })
    }

    /// Gets an owned reference to the value with the provided index.
    ///
    /// This method is useful when you already have an index, and don't want to
    /// pay the cost of a hash lookup.
    pub fn get_owned_by(&self, index: &Index<K, V>) -> Option<OwnedRef<K, V>>
    where
        V: Keyed<Key = K>,
    {
        self.slab
            .clone()
            .get_owned(index.offset())
            .filter(|i| i.deref().key() == index.key())
            .map(OwnedRef::new)
    }

    /// Gets an owned reference to the value at the provided slab offset.
    ///
    /// # Safety
    /// This method is unsafe because it does not validate that the provided
    /// offset has an associated key, thus making it possible to reference
    /// dangling slab entries.
    #[inline]
    pub unsafe fn get_owned_direct(
        &self,
        offset: usize,
    ) -> Option<OwnedRef<K, V>> {
        self.slab.clone().get_owned(offset).map(OwnedRef::new)
    }

    /// Gets whether or not the provided key exists in the map.
    #[inline]
    pub fn contains(&self, key: &K) -> bool {
        self.idxs.contains_key(key)
    }

    /// Gets whether or not the provided index still exists in the map.
    #[inline]
    pub fn exists(&self, idx: &Index<K, V>) -> bool {
        self.idxs
            .get(&idx.key())
            .map(|offset| offset.value() == &idx.offset())
            .unwrap_or(false)
    }

    /// Creates a new instance of [`Entry`] from the provided key.
    #[inline]
    pub fn entry(&self, key: K) -> Entry<'_, K, V, S> {
        Entry::new(key, &self.idxs, &self.slab)
    }

    /// Removes the entry at the provided index.
    #[inline]
    pub fn remove(&self, idx: &Index<K, V>) -> bool {
        if let Entry::Occupied(o) = self.entry(idx.key) {
            if o.offset() != idx.offset() {
                return false;
            }

            let offset = unsafe { o.unlink() };

            assert_eq!(
                offset,
                idx.offset(),
                "invalid slab offset was detected"
            );

            let removed = self.slab.remove(offset);

            assert!(removed, "failed to remove slab entry");
        }

        false
    }

    /// Resolves the index of the provided key.
    #[inline]
    pub fn index_of(&self, key: K) -> Option<Index<K, V>> {
        self.idxs.get(&key).map(|idx| Index::new(key, *idx.value()))
    }
}

impl<K: Key, V, S> Default for ReSlab<K, V, S>
where
    S: Default + BuildHasher + Clone,
{
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

impl<K, V, S> std::fmt::Debug for ReSlab<K, V, S>
where
    K: Key + Debug,
    V: Debug,
    S: BuildHasher + Clone + Debug,
{
    #[inline]
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("ReSlab")
            .field("idxs", &self.idxs)
            .field("slab", &self.slab)
            .finish()
    }
}

impl<K: Key, V> Index<K, V> {
    /// Creates a new instance of [`Index`] with the provided index and key.
    #[inline]
    const fn new(key: K, slab_offset: usize) -> Self {
        Self {
            off: slab_offset,
            key,
            _marker: std::marker::PhantomData,
        }
    }

    /// Gets the key component for this index.
    #[inline]
    pub const fn key(&self) -> K {
        self.key
    }

    /// Gets the slab offset component for this index.
    #[inline]
    pub const fn offset(&self) -> usize {
        self.off
    }
}