use std::hash::Hash;
#[cfg(test)]
mod tests {
use super::*;
use std::cell::Cell;
use std::hash::{Hash, Hasher};
#[derive(Clone)]
struct Key<'a>(u32, &'a Cell<usize>);
impl PartialEq for Key<'_> {
fn eq(&self, other: &Self) -> bool {
self.0 == other.0
}
}
impl Eq for Key<'_> {}
impl Hash for Key<'_> {
fn hash<H: Hasher>(&self, hasher: &mut H) {
self.1.set(self.1.get() + 1);
self.0.hash(hasher);
}
}
#[test]
fn retract_from_surviving_bucket_probes_once() {
let calls = Cell::new(0);
let mut index = HashIndex::new();
let first = RowHandle::new(0, 0);
let second = RowHandle::new(1, 0);
index.insert(first, Key(7, &calls));
index.insert(second, Key(7, &calls));
calls.set(0);
index.remove(first);
assert_eq!(calls.get(), 1, "a surviving bucket must stay in the table");
assert_eq!(index.lookup(&Key(7, &calls)), &[second]);
index.remove(second);
assert!(index.lookup(&Key(7, &calls)).is_empty());
index.insert(first, Key(9, &calls));
index.insert(first, Key(10, &calls));
assert!(index.lookup(&Key(9, &calls)).is_empty());
assert_eq!(index.lookup(&Key(10, &calls)), &[first]);
}
}
use super::super::{identity::RowHandle, FastMap, HandleMap};
#[derive(Clone, Debug)]
pub struct HashIndex<K> {
by_key: FastMap<K, Vec<RowHandle>>,
key_of: HandleMap<(K, usize)>,
retired: Vec<Vec<RowHandle>>,
}
impl<K> HashIndex<K>
where
K: Eq + Hash + Clone,
{
pub fn new() -> HashIndex<K> {
HashIndex {
by_key: FastMap::default(),
key_of: HandleMap::new(),
retired: Vec::new(),
}
}
fn remove_from_bucket(&mut self, handle: RowHandle, key: K, position: usize) {
if let std::collections::hash_map::Entry::Occupied(mut entry) = self.by_key.entry(key) {
let bucket = entry.get_mut();
debug_assert_eq!(bucket[position], handle);
bucket.swap_remove(position);
if let Some(&moved) = bucket.get(position) {
self.key_of.get_mut(moved).expect("moved index member").1 = position;
}
if bucket.is_empty() {
self.retired.push(entry.remove());
}
}
}
pub fn insert(&mut self, handle: RowHandle, key: K) {
if self.key_of.get(handle).is_some_and(|(old, _)| *old == key) {
return;
}
self.remove(handle);
let bucket = self
.by_key
.entry(key.clone())
.or_insert_with(|| self.retired.pop().unwrap_or_default());
let position = bucket.len();
bucket.push(handle);
self.key_of.insert(handle, (key, position));
}
pub(crate) fn insert_transient(&mut self, handle: RowHandle, key: K) {
self.by_key
.entry(key)
.or_insert_with(|| self.retired.pop().unwrap_or_default())
.push(handle);
}
pub fn remove(&mut self, handle: RowHandle) {
let Some((key, position)) = self.key_of.remove(handle) else {
return;
};
self.remove_from_bucket(handle, key, position);
}
pub fn clear(&mut self) {
self.by_key.clear();
self.key_of.clear();
self.retired.clear();
}
#[inline]
pub fn lookup(&self, key: &K) -> &[RowHandle] {
self.by_key.get(key).map(Vec::as_slice).unwrap_or(&[])
}
#[inline]
pub fn key_of(&self, handle: RowHandle) -> Option<&K> {
self.key_of.get(handle).map(|(key, _)| key)
}
}