pub(crate) mod bucket;
pub(crate) mod bucket_array_ref;
use bucket::BucketArray;
use bucket_array_ref::BucketArrayRef;
use std::{
borrow::Borrow,
collections::hash_map::RandomState,
hash::{BuildHasher, Hash},
sync::atomic::{self, AtomicUsize, Ordering},
};
use crossbeam_epoch::{self, Atomic};
pub type DefaultHashBuilder = RandomState;
#[derive(Default)]
pub struct HashMap<K, V, S = DefaultHashBuilder> {
bucket_array: Atomic<bucket::BucketArray<K, V>>,
build_hasher: S,
len: AtomicUsize,
}
impl<K, V> HashMap<K, V, DefaultHashBuilder> {
pub fn new() -> HashMap<K, V, DefaultHashBuilder> {
HashMap::with_capacity_and_hasher(0, DefaultHashBuilder::default())
}
pub fn with_capacity(capacity: usize) -> HashMap<K, V, DefaultHashBuilder> {
HashMap::with_capacity_and_hasher(capacity, DefaultHashBuilder::default())
}
}
impl<K, V, S> HashMap<K, V, S> {
pub fn with_hasher(build_hasher: S) -> HashMap<K, V, S> {
HashMap::with_capacity_and_hasher(0, build_hasher)
}
pub fn with_capacity_and_hasher(capacity: usize, build_hasher: S) -> HashMap<K, V, S> {
let bucket_array = if capacity == 0 {
Atomic::null()
} else {
Atomic::new(BucketArray::with_length(
0,
(capacity * 2).next_power_of_two(),
))
};
Self {
bucket_array,
build_hasher,
len: AtomicUsize::new(0),
}
}
pub fn len(&self) -> usize {
self.len.load(Ordering::Relaxed)
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn capacity(&self) -> usize {
let guard = &crossbeam_epoch::pin();
let bucket_array_ptr = self.bucket_array.load_consume(guard);
unsafe { bucket_array_ptr.as_ref() }
.map(BucketArray::capacity)
.unwrap_or(0)
}
}
impl<K: Hash + Eq, V, S: BuildHasher> HashMap<K, V, S> {
#[inline]
pub fn get<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
V: Clone,
{
self.get_key_value_and(key, |_, v| v.clone())
}
#[inline]
pub fn get_key_value<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q> + Clone,
V: Clone,
{
self.get_key_value_and(key, |k, v| (k.clone(), v.clone()))
}
#[inline]
pub fn get_and<Q: Hash + Eq + ?Sized, F: FnOnce(&V) -> T, T>(
&self,
key: &Q,
with_value: F,
) -> Option<T>
where
K: Borrow<Q>,
{
self.get_key_value_and(key, move |_, v| with_value(v))
}
#[inline]
pub fn get_key_value_and<Q: Hash + Eq + ?Sized, F: FnOnce(&K, &V) -> T, T>(
&self,
key: &Q,
with_entry: F,
) -> Option<T>
where
K: Borrow<Q>,
{
let hash = bucket::hash(&self.build_hasher, &key);
self.bucket_array_ref()
.get_key_value_and(key, hash, with_entry)
}
#[inline]
pub fn insert(&self, key: K, value: V) -> Option<V>
where
V: Clone,
{
self.insert_entry_and(key, value, |_, v| v.clone())
}
#[inline]
pub fn insert_entry(&self, key: K, value: V) -> Option<(K, V)>
where
K: Clone,
V: Clone,
{
self.insert_entry_and(key, value, |k, v| (k.clone(), v.clone()))
}
#[inline]
pub fn insert_and<F: FnOnce(&V) -> T, T>(
&self,
key: K,
value: V,
with_previous_value: F,
) -> Option<T> {
self.insert_entry_and(key, value, move |_, v| with_previous_value(v))
}
#[inline]
pub fn insert_entry_and<F: FnOnce(&K, &V) -> T, T>(
&self,
key: K,
value: V,
with_previous_entry: F,
) -> Option<T> {
let hash = bucket::hash(&self.build_hasher, &key);
self.bucket_array_ref()
.insert_entry_and(key, hash, value, with_previous_entry)
}
#[inline]
pub fn remove<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
V: Clone,
{
self.remove_entry_if_and(key, |_, _| true, |_, v| v.clone())
}
#[inline]
pub fn remove_entry<Q: Hash + Eq + ?Sized>(&self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q> + Clone,
V: Clone,
{
self.remove_entry_if_and(key, |_, _| true, |k, v| (k.clone(), v.clone()))
}
#[inline]
pub fn remove_and<Q: Hash + Eq + ?Sized, F: FnOnce(&V) -> T, T>(
&self,
key: &Q,
with_previous_value: F,
) -> Option<T>
where
K: Borrow<Q>,
{
self.remove_entry_if_and(key, |_, _| true, move |_, v| with_previous_value(v))
}
#[inline]
pub fn remove_entry_and<Q: Hash + Eq + ?Sized, F: FnOnce(&K, &V) -> T, T>(
&self,
key: &Q,
with_previous_entry: F,
) -> Option<T>
where
K: Borrow<Q>,
{
self.remove_entry_if_and(key, |_, _| true, with_previous_entry)
}
pub fn remove_if<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool>(
&self,
key: &Q,
condition: F,
) -> Option<V>
where
K: Borrow<Q>,
V: Clone,
{
self.remove_entry_if_and(key, condition, move |_, v| v.clone())
}
#[inline]
pub fn remove_entry_if<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool>(
&self,
key: &Q,
condition: F,
) -> Option<(K, V)>
where
K: Clone + Borrow<Q>,
V: Clone,
{
self.remove_entry_if_and(key, condition, move |k, v| (k.clone(), v.clone()))
}
#[inline]
pub fn remove_if_and<Q: Hash + Eq + ?Sized, F: FnMut(&K, &V) -> bool, G: FnOnce(&V) -> T, T>(
&self,
key: &Q,
condition: F,
with_previous_value: G,
) -> Option<T>
where
K: Borrow<Q>,
{
self.remove_entry_if_and(key, condition, move |_, v| with_previous_value(v))
}
#[inline]
pub fn remove_entry_if_and<
Q: Hash + Eq + ?Sized,
F: FnMut(&K, &V) -> bool,
G: FnOnce(&K, &V) -> T,
T,
>(
&self,
key: &Q,
condition: F,
with_previous_entry: G,
) -> Option<T>
where
K: Borrow<Q>,
{
let hash = bucket::hash(&self.build_hasher, &key);
self.bucket_array_ref()
.remove_entry_if_and(key, hash, condition, with_previous_entry)
}
#[inline]
pub fn insert_or_modify<F: FnMut(&K, &V) -> V>(
&self,
key: K,
value: V,
on_modify: F,
) -> Option<V>
where
V: Clone,
{
self.insert_with_or_modify_entry_and(key, move || value, on_modify, |_, v| v.clone())
}
#[inline]
pub fn insert_or_modify_entry<F: FnMut(&K, &V) -> V>(
&self,
key: K,
value: V,
on_modify: F,
) -> Option<(K, V)>
where
K: Clone,
V: Clone,
{
self.insert_with_or_modify_entry_and(
key,
move || value,
on_modify,
|k, v| (k.clone(), v.clone()),
)
}
#[inline]
pub fn insert_with_or_modify<F: FnOnce() -> V, G: FnMut(&K, &V) -> V>(
&self,
key: K,
on_insert: F,
on_modify: G,
) -> Option<V>
where
V: Clone,
{
self.insert_with_or_modify_entry_and(key, on_insert, on_modify, |_, v| v.clone())
}
#[inline]
pub fn insert_with_or_modify_entry<F: FnOnce() -> V, G: FnMut(&K, &V) -> V>(
&self,
key: K,
on_insert: F,
on_modify: G,
) -> Option<(K, V)>
where
K: Clone,
V: Clone,
{
self.insert_with_or_modify_entry_and(key, on_insert, on_modify, |k, v| {
(k.clone(), v.clone())
})
}
#[inline]
pub fn insert_or_modify_and<F: FnMut(&K, &V) -> V, G: FnOnce(&V) -> T, T>(
&self,
key: K,
value: V,
on_modify: F,
with_old_value: G,
) -> Option<T> {
self.insert_with_or_modify_entry_and(
key,
move || value,
on_modify,
move |_, v| with_old_value(v),
)
}
#[inline]
pub fn insert_or_modify_entry_and<F: FnMut(&K, &V) -> V, G: FnOnce(&K, &V) -> T, T>(
&self,
key: K,
value: V,
on_modify: F,
with_old_entry: G,
) -> Option<T> {
self.insert_with_or_modify_entry_and(key, move || value, on_modify, with_old_entry)
}
#[inline]
pub fn insert_with_or_modify_and<
F: FnOnce() -> V,
G: FnMut(&K, &V) -> V,
H: FnOnce(&V) -> T,
T,
>(
&self,
key: K,
on_insert: F,
on_modify: G,
with_old_value: H,
) -> Option<T> {
self.insert_with_or_modify_entry_and(key, on_insert, on_modify, move |_, v| {
with_old_value(v)
})
}
#[inline]
pub fn insert_with_or_modify_entry_and<
F: FnOnce() -> V,
G: FnMut(&K, &V) -> V,
H: FnOnce(&K, &V) -> T,
T,
>(
&self,
key: K,
on_insert: F,
on_modify: G,
with_old_entry: H,
) -> Option<T> {
let hash = bucket::hash(&self.build_hasher, &key);
self.bucket_array_ref().insert_with_or_modify_entry_and(
key,
hash,
on_insert,
on_modify,
with_old_entry,
)
}
#[inline]
pub fn modify<F: FnMut(&K, &V) -> V>(&self, key: K, on_modify: F) -> Option<V>
where
V: Clone,
{
self.modify_entry_and(key, on_modify, |_, v| v.clone())
}
#[inline]
pub fn modify_entry<F: FnMut(&K, &V) -> V>(&self, key: K, on_modify: F) -> Option<(K, V)>
where
K: Clone,
V: Clone,
{
self.modify_entry_and(key, on_modify, |k, v| (k.clone(), v.clone()))
}
#[inline]
pub fn modify_and<F: FnMut(&K, &V) -> V, G: FnOnce(&V) -> T, T>(
&self,
key: K,
on_modify: F,
with_old_value: G,
) -> Option<T> {
self.modify_entry_and(key, on_modify, move |_, v| with_old_value(v))
}
#[inline]
pub fn modify_entry_and<F: FnMut(&K, &V) -> V, G: FnOnce(&K, &V) -> T, T>(
&self,
key: K,
on_modify: F,
with_old_entry: G,
) -> Option<T> {
let hash = bucket::hash(&self.build_hasher, &key);
self.bucket_array_ref()
.modify_entry_and(key, hash, on_modify, with_old_entry)
}
}
impl<K, V, S> HashMap<K, V, S> {
#[inline]
fn bucket_array_ref(&'_ self) -> BucketArrayRef<'_, K, V, S> {
BucketArrayRef {
bucket_array: &self.bucket_array,
build_hasher: &self.build_hasher,
len: &self.len,
}
}
}
impl<K, V, S> Drop for HashMap<K, V, S> {
fn drop(&mut self) {
let guard = unsafe { &crossbeam_epoch::unprotected() };
atomic::fence(Ordering::Acquire);
let mut current_ptr = self.bucket_array.load(Ordering::Relaxed, guard);
while let Some(current_ref) = unsafe { current_ptr.as_ref() } {
let next_ptr = current_ref.next.load(Ordering::Relaxed, guard);
for this_bucket_ptr in current_ref
.buckets
.iter()
.map(|b| b.load(Ordering::Relaxed, guard))
.filter(|p| !p.is_null())
.filter(|p| next_ptr.is_null() || p.tag() & bucket::TOMBSTONE_TAG == 0)
{
unsafe { bucket::defer_acquire_destroy(guard, this_bucket_ptr) };
}
unsafe { bucket::defer_acquire_destroy(guard, current_ptr) };
current_ptr = next_ptr;
}
}
}
#[cfg(test)]
mod tests {
use crate::write_test_cases_for_me;
use super::*;
write_test_cases_for_me!(HashMap);
}