hash-link 0.1.1

Keep elements insert order while searchable by hash
Documentation
pub trait Hashable: PartialEq {
    /// Returns the hash value of the element
    ///
    /// This function should provide fast, simple hash computation
    fn get_hash(&self) -> u32;
}

pub(crate) struct Element<T: Hashable> {
    value: T,

    /// bit 31: deleted flag
    /// bit 0..30: Seq of next element in same hash bucket, equals to element's list_index+1. 0 means end of chain.
    del_and_next: u32,
}

impl<T: Hashable + std::fmt::Debug> std::fmt::Debug for Element<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Element")
            .field("value", &self.value)
            .field("next", &self.next())
            .field("deleted", &self.is_deleted())
            .finish()
    }
}

impl<T: Hashable> Element<T> {
    pub const fn new(value: T, next: usize) -> Self {
        debug_assert!(next <= 0x7FFF_FFFF);
        Self {
            value,
            del_and_next: next as u32,
        }
    }

    #[inline(always)]
    pub const unsafe fn value(&self) -> &T {
        &self.value
    }

    #[inline(always)]
    pub const unsafe fn value_mut(&mut self) -> &mut T {
        &mut self.value
    }

    #[inline(always)]
    pub const fn next(&self) -> usize {
        (self.del_and_next & 0x7FFF_FFFF) as usize
    }

    #[inline(always)]
    pub const fn set_next(&mut self, seq: usize) {
        debug_assert!(seq <= 0x7FFF_FFFF);
        self.del_and_next = (self.del_and_next & !0x7FFF_FFFF) | seq as u32;
    }

    #[inline(always)]
    pub const fn is_deleted(&self) -> bool {
        self.del_and_next & 0x8000_0000 != 0
    }

    #[inline(always)]
    pub const fn set_deleted(&mut self) {
        self.del_and_next |= 0x8000_0000;
    }
}

//
// Implement Hashable for common types
//

impl Hashable for usize {
    #[inline(always)]
    fn get_hash(&self) -> u32 {
        // For usize, return itself as hash value directly
        *self as u32
    }
}

impl Hashable for u32 {
    #[inline(always)]
    fn get_hash(&self) -> u32 {
        *self
    }
}

impl Hashable for i32 {
    #[inline(always)]
    fn get_hash(&self) -> u32 {
        *self as u32
    }
}

impl Hashable for [u8] {
    fn get_hash(&self) -> u32 {
        let mut hash: u32 = 2166136261;
        for &byte in self {
            hash ^= byte as u32;
            hash = hash.wrapping_mul(16777619);
        }
        hash
    }
}

impl Hashable for str {
    #[inline]
    fn get_hash(&self) -> u32 {
        self.as_bytes().get_hash()
    }
}

impl Hashable for String {
    #[inline]
    fn get_hash(&self) -> u32 {
        self.as_bytes().get_hash()
    }
}

/// Element guard for safely modifying elements while maintaining hash index synchronization
pub struct ElementGuard<'a, T: Hashable> {
    /// Original hash value (captures hash before modification)
    original_hash: u32,
    /// Element index position
    index: usize,
    /// Mutable reference inside guard
    value: &'a mut T,
    /// Hash update callback function
    update_callback: Option<Box<dyn FnOnce(usize, u32) + 'a>>,
}

impl<'a, T: Hashable> std::ops::Deref for ElementGuard<'a, T> {
    type Target = T;

    #[inline(always)]
    fn deref(&self) -> &Self::Target {
        self.value
    }
}

impl<'a, T: Hashable> std::ops::DerefMut for ElementGuard<'a, T> {
    #[inline(always)]
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.value
    }
}

impl<'a, T: Hashable> Drop for ElementGuard<'a, T> {
    fn drop(&mut self) {
        // If hash was changed, need to update hash bucket
        if self.value.get_hash() != self.original_hash
            && let Some(f) = self.update_callback.take()
        {
            f(self.index, self.original_hash);
        }
    }
}

impl<'a, T: Hashable> ElementGuard<'a, T> {
    pub(super) fn new(
        index: usize,
        value: &'a mut T,
        update_fn: impl FnOnce(usize, u32) + 'a,
    ) -> Self {
        ElementGuard {
            original_hash: value.get_hash(),
            index,
            value,
            update_callback: Some(Box::new(update_fn)),
        }
    }

    /// Get original hash value
    #[inline(always)]
    pub const fn original_hash(&self) -> u32 {
        self.original_hash
    }

    /// Get current hash value
    #[inline(always)]
    pub fn current_hash(&self) -> u32 {
        self.value.get_hash()
    }

    /// Check if hash value changed
    pub fn hash_changed(&self) -> bool {
        self.current_hash() != self.original_hash()
    }
}