use std::cell::RefCell;
use std::collections::{HashMap, HashSet};
use std::fmt::{self, Debug, Formatter};
use std::hash::{Hash, Hasher, BuildHasher};
use std::ops::{Deref, DerefMut};
use std::iter::FromIterator;
thread_local!(static BUFFER: RefCell<Vec<u64>> = RefCell::new(Vec::with_capacity(100)));
#[derive(Clone)]
pub struct HashableHashSet<V, S = ahash::RandomState>(HashSet<V, S>);
#[cfg(test)]
fn hash<T: Hash>(value: &T) -> u64 {
let mut hasher = ahash::AHasher::default();
value.hash(&mut hasher);
hasher.finish()
}
impl<V> HashableHashSet<V> {
#[inline]
pub fn new() -> HashableHashSet<V> {
Default::default()
}
}
impl<V, S> HashableHashSet<V, S> {
#[inline]
pub fn with_hasher(hasher: S) -> Self {
HashableHashSet(HashSet::with_hasher(hasher))
}
}
impl<V: Debug, S> Debug for HashableHashSet<V, S> {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
self.0.fmt(f)
}
}
impl<V, S: Default> Default for HashableHashSet<V, S> {
#[inline]
fn default() -> HashableHashSet<V, S> {
HashableHashSet::with_hasher(S::default())
}
}
impl<V, S> Deref for HashableHashSet<V, S> {
type Target = HashSet<V, S>;
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl<V, S> DerefMut for HashableHashSet<V, S> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.0
}
}
impl<V: Hash + Eq, S: BuildHasher> Eq for HashableHashSet<V, S> {}
impl<V: Eq + Hash, S: BuildHasher + Default> FromIterator<V> for HashableHashSet<V, S> {
fn from_iter<T: IntoIterator<Item=V>>(iter: T) -> Self {
HashableHashSet(HashSet::from_iter(iter))
}
}
impl<V: Hash, S> Hash for HashableHashSet<V, S> {
fn hash<H: Hasher>(&self, hasher: &mut H) {
BUFFER.with(|buffer| {
let fallback = RefCell::new(Vec::new());
let mut buffer = buffer.try_borrow_mut()
.unwrap_or_else(|_| fallback.borrow_mut());
buffer.clear();
buffer.extend(self.0.iter().map(|v| {
let mut inner_hasher = ahash::AHasher::default();
v.hash(&mut inner_hasher);
inner_hasher.finish()
}));
buffer.sort_unstable();
for v in &*buffer {
hasher.write_u64(*v);
}
});
}
}
impl<'a, V, S> IntoIterator for &'a HashableHashSet<V, S> {
type Item = &'a V;
type IntoIter = std::collections::hash_set::Iter<'a, V>;
#[inline]
fn into_iter(self) -> std::collections::hash_set::Iter<'a, V> {
self.0.iter()
}
}
impl<V: Hash + Eq, S: BuildHasher> PartialEq for HashableHashSet<V, S> {
fn eq(&self, other: &Self) -> bool {
self.0.eq(&other.0)
}
}
impl<V, S> serde::Serialize for HashableHashSet<V, S>
where V: Eq + Hash + serde::Serialize,
S: BuildHasher,
{
fn serialize<Ser: serde::Serializer>(&self, ser: Ser) -> Result<Ser::Ok, Ser::Error> {
self.0.serialize(ser)
}
}
#[cfg(test)]
mod hashable_hash_set_test {
use crate::hash;
use super::HashableHashSet;
#[test]
fn different_hash_if_items_differ() {
let mut set = HashableHashSet::new();
set.insert("one");
set.insert("two");
set.insert("three");
let fp1 = hash(&set);
let mut set = HashableHashSet::new();
set.insert("four");
set.insert("five");
set.insert("six");
let fp2 = hash(&set);
assert_ne!(fp1, fp2);
}
#[test]
fn insertion_order_is_irrelevant() {
let mut set = HashableHashSet::new();
set.insert("one");
set.insert("two");
set.insert("three");
let fp1 = hash(&set);
let mut set = HashableHashSet::new();
set.insert("three");
set.insert("one");
set.insert("two");
let fp2 = hash(&set);
assert_eq!(fp1, fp2);
}
#[test]
fn can_hash_set_of_sets() {
let mut set = HashableHashSet::new();
set.insert({
let mut set = HashableHashSet::new();
set.insert("value");
set
});
hash(&set);
}
}
#[derive(Clone)]
pub struct HashableHashMap<K, V, S = ahash::RandomState>(HashMap<K, V, S>);
impl<K, V> HashableHashMap<K, V> {
#[inline]
pub fn new() -> HashableHashMap<K, V, ahash::RandomState> {
Default::default()
}
}
impl<K, V, S> HashableHashMap<K, V, S> {
#[inline]
pub fn with_hasher(hasher: S) -> Self {
HashableHashMap(HashMap::with_hasher(hasher))
}
}
impl<K: Debug, V: Debug, S> Debug for HashableHashMap<K, V, S> {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
self.0.fmt(f)
}
}
impl<K, V, S: Default> Default for HashableHashMap<K, V, S> {
#[inline]
fn default() -> Self {
HashableHashMap::with_hasher(S::default())
}
}
impl<K, V, S> Deref for HashableHashMap<K, V, S> {
type Target = HashMap<K, V, S>;
fn deref(&self) -> &Self::Target {
&self.0
}
}
impl<K, V, S> DerefMut for HashableHashMap<K, V, S> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.0
}
}
impl<K: Eq + Hash, V: Eq, S: BuildHasher> Eq for HashableHashMap<K, V, S> {}
impl<K: Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)> for HashableHashMap<K, V, S> {
fn from_iter<T: IntoIterator<Item=(K, V)>>(iter: T) -> Self {
HashableHashMap(HashMap::from_iter(iter))
}
}
impl<K: Hash, V: Hash, S> Hash for HashableHashMap<K, V, S> {
fn hash<H: Hasher>(&self, state: &mut H) {
BUFFER.with(|buffer| {
let fallback = RefCell::new(Vec::new());
let mut buffer = buffer.try_borrow_mut()
.unwrap_or_else(|_| fallback.borrow_mut());
buffer.clear();
buffer.extend(self.0.iter().map(|(k, v)| {
let mut inner_hasher = ahash::AHasher::default();
k.hash(&mut inner_hasher);
v.hash(&mut inner_hasher);
inner_hasher.finish()
}));
buffer.sort_unstable();
for hash in &*buffer {
state.write_u64(*hash);
}
});
}
}
impl<'a, K, V, S> IntoIterator for &'a HashableHashMap<K, V, S> {
type Item = (&'a K, &'a V);
type IntoIter = std::collections::hash_map::Iter<'a, K, V>;
#[inline]
fn into_iter(self) -> std::collections::hash_map::Iter<'a, K, V> {
self.0.iter()
}
}
impl<K: Hash + Eq, V: PartialEq, S: BuildHasher> PartialEq for HashableHashMap<K, V, S> {
fn eq(&self, other: &Self) -> bool {
self.0.eq(&other.0)
}
}
impl<K, V, S> serde::Serialize for HashableHashMap<K, V, S>
where K: Eq + Hash + serde::Serialize,
V: serde::Serialize,
S: BuildHasher,
{
fn serialize<Ser: serde::Serializer>(&self, ser: Ser) -> Result<Ser::Ok, Ser::Error> {
self.0.serialize(ser)
}
}
#[cfg(test)]
mod hashable_hash_map_test {
use crate::hash;
use super::HashableHashMap;
#[test]
fn different_hash_if_items_differ() {
let mut map = HashableHashMap::new();
map.insert("one", 1);
map.insert("two", 2);
map.insert("three", 3);
let fp1 = hash(&map);
let mut map = HashableHashMap::new();
map.insert("one", 4);
map.insert("two", 5);
map.insert("three", 6);
let fp2 = hash(&map);
let mut map = HashableHashMap::new();
map.insert("four", 1);
map.insert("five", 2);
map.insert("six", 3);
let fp3 = hash(&map);
assert_ne!(fp1, fp2);
assert_ne!(fp1, fp3);
assert_ne!(fp2, fp3);
}
#[test]
fn insertion_order_is_irrelevant() {
let mut map = HashableHashMap::new();
map.insert("one", 1);
map.insert("two", 2);
map.insert("three", 3);
let fp1 = hash(&map);
let mut map = HashableHashMap::new();
map.insert("three", 3);
map.insert("one", 1);
map.insert("two", 2);
let fp2 = hash(&map);
assert_eq!(fp1, fp2);
}
#[test]
fn can_hash_map_of_maps() {
let mut map = HashableHashMap::new();
map.insert({
let mut map = HashableHashMap::new();
map.insert("key", "value");
map
}, "value");
hash(&map);
}
}