use std::{
any::Any,
cell::RefCell,
collections::HashMap,
hash::{BuildHasher, BuildHasherDefault, Hash},
marker::PhantomData,
};
use crate::fast_hash::{FastBuildHasher, FastHasher};
pub struct StoreMap<K, V> {
entries: Entries,
_types: PhantomData<(K, V)>,
}
impl<K, V> Default for StoreMap<K, V> {
fn default() -> Self {
Self::new()
}
}
impl<K, V> StoreMap<K, V> {
pub const fn new() -> Self {
Self {
entries: Entries(RefCell::new(
HashMap::with_hasher(BuildHasherDefault::new()),
)),
_types: PhantomData,
}
}
}
impl<K: 'static, V: Clone + 'static> StoreMap<K, V> {
pub fn get_or_create(
&self,
arguments: &impl Hash,
is_key: impl Fn(&K) -> bool,
key: impl FnOnce() -> K,
create: impl FnOnce() -> V,
) -> V {
let hash = BuildHasherDefault::<FastHasher>::new().hash_one(arguments);
self.get_or_create_hashed(hash, is_key, key, create)
}
fn get_or_create_hashed(
&self,
hash: u64,
is_key: impl Fn(&K) -> bool,
key: impl FnOnce() -> K,
create: impl FnOnce() -> V,
) -> V {
let mut found = None;
self.entries
.find(hash, &mut |entry| match entry.downcast_ref::<(K, V)>() {
Some((stored, value)) if is_key(stored) => {
found = Some(value.clone());
true
}
_ => false,
});
if let Some(value) = found {
return value;
}
let value = create();
self.entries.insert(hash, Box::new((key(), value.clone())));
value
}
pub fn values(&self) -> Vec<V> {
let mut values = Vec::new();
self.entries.each(&mut |entry| {
if let Some((_, value)) = entry.downcast_ref::<(K, V)>() {
values.push(value.clone());
}
});
values
}
}
struct Entries(RefCell<HashMap<u64, Box<dyn Any>, FastBuildHasher>>);
impl Entries {
fn find(&self, mut hash: u64, take: &mut dyn FnMut(&dyn Any) -> bool) {
let entries = self.0.borrow();
while let Some(entry) = entries.get(&hash) {
if take(&**entry) {
return;
}
hash = hash.wrapping_add(1);
}
}
fn each(&self, visit: &mut dyn FnMut(&dyn Any)) {
for entry in self.0.borrow().values() {
visit(&**entry);
}
}
fn insert(&self, mut hash: u64, entry: Box<dyn Any>) {
let mut entries = self.0.borrow_mut();
while entries.contains_key(&hash) {
hash = hash.wrapping_add(1);
}
entries.insert(hash, entry);
}
}
#[cfg(test)]
mod tests {
use std::cell::Cell;
use super::*;
type Names = StoreMap<(String,), String>;
fn get(map: &Names, hash: u64, name: &str, created: &Cell<u32>) -> String {
map.get_or_create_hashed(
hash,
|stored| stored.0 == name,
|| (name.to_string(),),
|| {
created.set(created.get() + 1);
format!("value of {name}")
},
)
}
#[test]
fn creates_once_per_key() {
let map = Names::new();
let created = Cell::new(0);
for name in ["a", "b", "a", "b", "a"] {
let value = map.get_or_create(
&(name,),
|stored| stored.0 == name,
|| (name.to_string(),),
|| {
created.set(created.get() + 1);
format!("value of {name}")
},
);
assert_eq!(value, format!("value of {name}"));
}
assert_eq!(created.get(), 2);
}
#[test]
fn keys_sharing_a_hash_stay_apart() {
let map = Names::new();
let created = Cell::new(0);
for name in ["a", "b", "c", "b", "a", "c"] {
assert_eq!(get(&map, 7, name, &created), format!("value of {name}"));
}
assert_eq!(created.get(), 3);
assert_eq!(get(&map, 8, "d", &created), "value of d");
assert_eq!(get(&map, 7, "c", &created), "value of c");
assert_eq!(created.get(), 4);
}
#[test]
fn values_of_all_keys() {
let map = Names::new();
let created = Cell::new(0);
assert!(map.values().is_empty());
for name in ["a", "b", "c", "a"] {
get(&map, 7, name, &created);
}
get(&map, 3, "d", &created);
let mut values = map.values();
values.sort();
assert_eq!(
values,
["value of a", "value of b", "value of c", "value of d"]
);
}
#[test]
fn body_may_ask_for_other_arguments() {
let map = StoreMap::<(u32,), u32>::new();
fn depth(map: &StoreMap<(u32,), u32>, n: u32) -> u32 {
map.get_or_create(
&(n,),
|stored| stored.0 == n,
|| (n,),
|| match n {
0 => 0,
_ => depth(map, n - 1) + 1,
},
)
}
assert_eq!(depth(&map, 5), 5);
assert_eq!(map.entries.0.borrow().len(), 6);
}
}