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)
}
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
}
fn update_hash_index(&mut self, index: usize, old_hash: u32) {
debug_assert!(index < self.chunk.list_count);
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 {
let next = (&*list_ptr.add(index)).next();
if prev_seq == 0 {
*hash_buckets_ptr.add(old_hash_index) = next; } else {
(&mut *list_ptr.add(prev_seq - 1)).set_next(next);
}
break;
}
prev_seq = seq;
seq = (&*list_ptr.add(idx)).next();
}
}
unsafe {
let element = &*self.chunk.list_base_ptr().add(index);
let hash = (element.value().get_hash() as usize) & self.chunk.hash_mask();
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);
};
}
#[inline(always)]
pub fn push(&mut self, value: T) -> usize {
self.chunk.append(value).unwrap()
}
#[inline(always)]
pub fn index_of(&self, value: &T) -> Option<usize> {
self.chunk.index_of(value)
}
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
}
}
#[inline]
pub fn remove(&mut self, value: &T) -> bool {
self.index_of(value).is_some_and(|i| self.remove_index(i))
}
#[inline(always)]
pub fn compact(&mut self) {
self.chunk.compact();
}
#[inline(always)]
pub const fn count(&self) -> usize {
self.chunk.list_count - self.chunk.count_deleted
}
#[inline(always)]
pub const fn len(&self) -> usize {
self.chunk.list_count
}
pub const fn is_empty(&self) -> bool {
self.count() == 0
}
#[inline(always)]
pub const fn capacity(&self) -> usize {
self.chunk.list_capacity
}
#[inline(always)]
pub const fn hash_bucket_count(&self) -> usize {
self.chunk.hash_count
}
#[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) }
}
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
}
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
}
}
pub fn first(&self) -> Option<&T> {
for i in 0..self.chunk.list_count {
if !self.chunk.is_deleted(i) {
return self.get(i);
}
}
None
}
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();
}
pub fn contains(&self, value: &T) -> bool {
self.index_of(value).is_some()
}
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(())
}
}
#[inline(always)]
pub fn reserve(&mut self, additional: usize) {
self.try_reserve(additional).unwrap()
}
#[inline(always)]
pub fn shrink_to_fit(&mut self) {
self.chunk.shrink_to_fit().unwrap();
}
pub const fn iter(&self) -> HashLinkIter<'_, T> {
HashLinkIter {
container: self,
index: 0,
}
}
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,
}
}
}
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
}
}
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();
if el.value().get_hash() == self.expected_hash && !el.is_deleted() {
return Some((index, el.value()));
}
}
} else {
self.seq = 0; }
}
None
}
}