hash-link 0.1.1

Keep elements insert order while searchable by hash
Documentation
use std::collections::TryReserveError;

use crate::{
    element::{Element, ElementGuard, Hashable},
    mem::MemChunk,
};

#[derive(Debug)]
pub struct HashList<T: Hashable> {
    chunk: MemChunk<T>,
}

impl<T: Hashable> HashList<T> {
    pub fn new() -> Self {
        Self::with_capacity(4, 2)
    }

    /// Constructor with specified initial capacity
    pub fn with_capacity(hash_size: usize, list_capacity: usize) -> Self {
        let chunk = MemChunk::<T>::new(hash_size, list_capacity);
        Self { chunk }
    }

    pub fn from_vec(vec: Vec<T>) -> Self {
        let n = vec.len();
        let mut list = Self::with_capacity(n.max(1).next_power_of_two(), n);
        for value in vec {
            list.push(value);
        }
        list
    }

    /// Update element's hash index (internal method, called by ElementGuard)
    fn update_hash_index(&mut self, index: usize, old_hash: u32) {
        debug_assert!(index < self.chunk.list_count);

        // Remove element from old hash bucket
        let old_hash_index = (old_hash as usize) & self.chunk.hash_mask();
        let hash_buckets_ptr = self.chunk.hash_buckets_base_mut_ptr();
        let list_ptr = self.chunk.list_base_mut_ptr();

        unsafe {
            let mut seq = *hash_buckets_ptr.add(old_hash_index);
            let mut prev_seq = 0;

            while seq != 0 {
                let idx = seq - 1;
                if idx == index {
                    // Find element to remove
                    let next = (&*list_ptr.add(index)).next();
                    if prev_seq == 0 {
                        *hash_buckets_ptr.add(old_hash_index) = next; // Is list head
                    } else {
                        (&mut *list_ptr.add(prev_seq - 1)).set_next(next);
                    }
                    break;
                }

                prev_seq = seq;
                seq = (&*list_ptr.add(idx)).next();
            }
        }

        unsafe {
            // Add element to new hash bucket
            let element = &*self.chunk.list_base_ptr().add(index);
            let hash = (element.value().get_hash() as usize) & self.chunk.hash_mask();

            // Head insertion: insert element at head of new hash bucket
            let next =
                std::ptr::replace(self.chunk.hash_buckets_base_mut_ptr().add(hash), index + 1);

            (&mut *self.chunk.list_base_mut_ptr().add(index)).set_next(next);
        };
    }

    /// Append a new element, returns element index
    #[inline(always)]
    pub fn push(&mut self, value: T) -> usize {
        self.chunk.append(value).unwrap()
    }

    /// Find index of given `value`.
    #[inline(always)]
    pub fn index_of(&self, value: &T) -> Option<usize> {
        self.chunk.index_of(value)
    }

    /// Remove by index
    pub const fn remove_index(&mut self, index: usize) -> bool {
        if index < self.chunk.list_count && !self.chunk.is_deleted(index) {
            self.chunk.mark_deleted(index);
            true
        } else {
            false
        }
    }

    /// Remove by value
    #[inline]
    pub fn remove(&mut self, value: &T) -> bool {
        self.index_of(value).is_some_and(|i| self.remove_index(i))
    }

    /// Compact list, purge deleted elements
    #[inline(always)]
    pub fn compact(&mut self) {
        self.chunk.compact();
    }

    /// Get count of valid elements
    #[inline(always)]
    pub const fn count(&self) -> usize {
        self.chunk.list_count - self.chunk.count_deleted
    }

    /// Get count of list valid + deleted elements
    #[inline(always)]
    pub const fn len(&self) -> usize {
        self.chunk.list_count
    }

    /// Check if empty
    pub const fn is_empty(&self) -> bool {
        self.count() == 0
    }

    /// Get list capacity
    #[inline(always)]
    pub const fn capacity(&self) -> usize {
        self.chunk.list_capacity
    }

    /// Get hash bucket count
    #[inline(always)]
    pub const fn hash_bucket_count(&self) -> usize {
        self.chunk.hash_count
    }

    /// Get number of deleted elements
    #[inline(always)]
    pub const fn count_deleted(&self) -> usize {
        self.chunk.count_deleted
    }

    #[inline(always)]
    pub(super) const unsafe fn get_mut_unchecked(&mut self, index: usize) -> &mut Element<T> {
        unsafe { self.chunk.element_mut(index) }
    }

    /// Get value by index (if exists and not deleted)
    pub const fn get(&self, index: usize) -> Option<&T> {
        if index < self.chunk.list_count {
            unsafe {
                let el = self.chunk.element(index);
                if !el.is_deleted() {
                    return Some(el.value());
                }
            }
        }
        None
    }

    /// Get value mutable by index (if exists and not deleted)
    pub fn get_mut(&mut self, index: usize) -> Option<ElementGuard<'_, T>> {
        if index < self.chunk.list_count && !self.chunk.is_deleted(index) {
            let this_ptr = self as *mut Self;

            unsafe {
                let el = self.get_mut_unchecked(index);
                Some(ElementGuard::new(
                    index,
                    el.value_mut(),
                    move |idx: usize, old_hash: u32| {
                        let this = &mut *this_ptr;
                        this.update_hash_index(idx, old_hash);
                    },
                ))
            }
        } else {
            None
        }
    }

    /// Get reference to first valid element
    pub fn first(&self) -> Option<&T> {
        // Find first non-deleted element from front to back
        for i in 0..self.chunk.list_count {
            if !self.chunk.is_deleted(i) {
                return self.get(i);
            }
        }
        None
    }

    /// Get reference to last valid element
    pub fn last(&self) -> Option<&T> {
        for i in (0..self.chunk.list_count).rev() {
            if !self.chunk.is_deleted(i) {
                return self.get(i);
            }
        }
        None
    }

    #[inline(always)]
    pub fn clear(&mut self) {
        self.chunk.clear();
    }

    /// Check if contains specified element
    pub fn contains(&self, value: &T) -> bool {
        self.index_of(value).is_some()
    }

    /// Try to reserve capacity for at least additional more elements
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
        let cap = self.chunk.list_count + additional;
        if cap > self.chunk.list_capacity {
            self.chunk.resize(self.chunk.hash_count, cap)
        } else {
            Ok(())
        }
    }

    /// List capacity reservation
    #[inline(always)]
    pub fn reserve(&mut self, additional: usize) {
        self.try_reserve(additional).unwrap()
    }

    /// List capacity shrink
    #[inline(always)]
    pub fn shrink_to_fit(&mut self) {
        self.chunk.shrink_to_fit().unwrap();
    }

    /// Iterate valid values with its index, in insertion order
    pub const fn iter(&self) -> HashLinkIter<'_, T> {
        HashLinkIter {
            container: self,
            index: 0,
        }
    }

    /// Iterate values matching given hash.
    /// Note: will actually iterator in reversed order of insertion, if many elements match the same hash.
    pub const fn find_hash(&self, hash: u32) -> HashLinkFindIter<'_, T> {
        HashLinkFindIter {
            container: self,
            seq: unsafe {
                *self
                    .chunk
                    .hash_buckets_base_ptr()
                    .add(hash as usize & self.chunk.hash_mask())
            },
            expected_hash: hash,
        }
    }
}

/// HashList indexed iterator, traverses valid elements and their indices in insertion order
pub struct HashLinkIter<'a, T: Hashable> {
    container: &'a HashList<T>,
    index: usize,
}

impl<'a, T: Hashable> Iterator for HashLinkIter<'a, T> {
    type Item = (usize, &'a T);

    fn next(&mut self) -> Option<Self::Item> {
        while self.index < self.container.chunk.list_count {
            let i = self.index;
            self.index += 1;

            unsafe {
                let el = self.container.chunk.element(i);
                if !el.is_deleted() {
                    return Some((i, el.value()));
                }
            }
        }

        None
    }
}

/// Iterator for finding elements by hash value
pub struct HashLinkFindIter<'a, T: Hashable> {
    container: &'a HashList<T>,
    seq: usize,
    expected_hash: u32,
}

impl<'a, T: Hashable> Iterator for HashLinkFindIter<'a, T> {
    type Item = (usize, &'a T);

    fn next(&mut self) -> Option<Self::Item> {
        while self.seq != 0 {
            let index = self.seq - 1;

            if index < self.container.chunk.list_count {
                unsafe {
                    let el = self.container.chunk.element(index);
                    self.seq = el.next();
                    // Buckets are selected by masked hash bits only, so the chain can
                    // still contain entries whose full hash differs from expected_hash.
                    if el.value().get_hash() == self.expected_hash && !el.is_deleted() {
                        return Some((index, el.value()));
                    }
                }
            } else {
                self.seq = 0; // iter is end
            }
        }

        None
    }
}