#![allow(clippy::needless_doctest_main)]
use std::{
collections::{HashMap, HashSet},
hash::{BuildHasher, Hash, Hasher},
ops::{Deref, DerefMut},
};
pub mod hashers;
pub mod a_hash {
#[cfg(feature = "with_ahash")]
pub type HConSet<T> = super::HConSet<T, super::hashers::a_hash::Builder>;
#[cfg(feature = "with_ahash")]
pub type HConMap<K, V> = super::HConMap<K, V, super::hashers::a_hash::Builder>;
}
pub mod sip_hash {
pub type HConSet<T> = super::HConSet<T, super::hashers::sip_hash::Builder>;
pub type HConMap<K, V> = super::HConMap<K, V, super::hashers::sip_hash::Builder>;
}
pub mod p_hash {
pub type HConSet<T> = super::HConSet<T, super::hashers::p_hash::Builder>;
pub type HConMap<K, V> = super::HConMap<K, V, super::hashers::p_hash::Builder>;
}
pub mod id_hash {
pub type HConSet<T> = super::HConSet<T, super::hashers::id_hash::Builder>;
pub type HConMap<K, V> = super::HConMap<K, V, super::hashers::id_hash::Builder>;
}
pub mod default {
pub use super::p_hash::*;
}
use crate::{HConsed, HashConsed};
#[derive(Clone, Debug)]
pub struct HConSet<T, S = self::hashers::p_hash::Builder>
where
T: HashConsed,
T::Inner: Eq + Hash,
{
set: HashSet<HConsed<T::Inner>, S>,
}
impl<T, S> PartialEq for HConSet<T, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
S: BuildHasher,
{
fn eq(&self, other: &Self) -> bool {
self.len() == other.len() && self.iter().zip(other.iter()).all(|(e_1, e_2)| e_1 == e_2)
}
}
impl<T, S> Eq for HConSet<T, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
S: BuildHasher,
{
}
impl<T, S> Hash for HConSet<T, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
S: BuildHasher,
{
fn hash<H>(&self, h: &mut H)
where
H: Hasher,
{
for elem in self {
elem.hash(h)
}
}
}
impl<T, S> Default for HConSet<T, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
S: Default,
{
fn default() -> Self {
HConSet {
set: HashSet::with_hasher(S::default()),
}
}
}
macro_rules! hashplement {
{$(
$(#[$meta:meta])*
$hcoll_name:ident <
$key_t_param:ident
$(, $val_t_param:ident)?
> for $hasher:ty ;
)*} => {$(
$(#[$meta])*
impl<$key_t_param $(, $val_t_param)?> $hcoll_name<
$key_t_param $(, $val_t_param)?, $hasher
>
where
$key_t_param: HashConsed,
$key_t_param::Inner: Eq + Hash,
{
#[inline]
pub fn new() -> Self {
$hcoll_name::with_hasher(<$hasher>::new())
}
pub fn with_capacity(capa: usize) -> Self {
$hcoll_name::with_capacity_and_hasher(capa, <$hasher>::new())
}
}
)*};
}
hashplement! {
#[cfg(feature = "with_ahash")]
HConSet<T> for self::hashers::a_hash::Builder;
HConSet<T> for self::hashers::sip_hash::Builder;
HConSet<T> for self::hashers::p_hash::Builder;
HConSet<T> for self::hashers::id_hash::Builder;
}
impl<T, S> HConSet<T, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
S: BuildHasher,
{
#[inline]
pub fn with_hasher(build_hasher: S) -> Self {
HConSet {
set: HashSet::with_hasher(build_hasher),
}
}
#[inline]
pub fn with_capacity_and_hasher(capa: usize, build_hasher: S) -> Self {
HConSet {
set: HashSet::with_capacity_and_hasher(capa, build_hasher),
}
}
}
impl<T, S> HConSet<T, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
{
#[inline]
pub fn iter(&self) -> ::std::collections::hash_set::Iter<HConsed<T::Inner>> {
self.set.iter()
}
}
impl<'a, T, S> IntoIterator for &'a HConSet<T, S>
where
T: HashConsed,
T::Inner: Hash + Eq,
{
type Item = &'a HConsed<T::Inner>;
type IntoIter = ::std::collections::hash_set::Iter<'a, HConsed<T::Inner>>;
fn into_iter(self) -> Self::IntoIter {
self.set.iter()
}
}
impl<T, S> IntoIterator for HConSet<T, S>
where
T: HashConsed,
T::Inner: Hash + Eq,
{
type Item = HConsed<T::Inner>;
type IntoIter = ::std::collections::hash_set::IntoIter<HConsed<T::Inner>>;
fn into_iter(self) -> Self::IntoIter {
self.set.into_iter()
}
}
impl<T, S> ::std::iter::FromIterator<HConsed<T::Inner>> for HConSet<T, S>
where
T: HashConsed,
T::Inner: Hash + Eq,
S: BuildHasher + Default,
{
fn from_iter<I: IntoIterator<Item = HConsed<T::Inner>>>(iter: I) -> Self {
HConSet {
set: HashSet::from_iter(iter),
}
}
}
impl<T, S> Deref for HConSet<T, S>
where
T: HashConsed,
T::Inner: Hash + Eq,
{
type Target = HashSet<HConsed<T::Inner>, S>;
fn deref(&self) -> &Self::Target {
&self.set
}
}
impl<T, S> DerefMut for HConSet<T, S>
where
T: HashConsed,
T::Inner: Hash + Eq,
{
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.set
}
}
impl<T, Src, S> From<Src> for HConSet<HConsed<T>, S>
where
T: Hash + Eq,
Src: Iterator<Item = HConsed<T>>,
S: Default + BuildHasher,
{
fn from(src: Src) -> Self {
let mut set = HConSet::default();
for elem in src {
set.insert(elem);
}
set
}
}
#[derive(Clone, Debug)]
pub struct HConMap<T, V, S = self::hashers::p_hash::Builder>
where
T: HashConsed,
T::Inner: Hash + Eq,
{
map: HashMap<HConsed<T::Inner>, V, S>,
}
impl<T, V, S> PartialEq for HConMap<T, V, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
V: Eq,
S: BuildHasher,
{
fn eq(&self, other: &Self) -> bool {
self.len() == other.len()
&& self
.iter()
.zip(other.iter())
.all(|((k_1, v_1), (k_2, v_2))| k_1 == k_2 && v_1 == v_2)
}
}
impl<T, V, S> Eq for HConMap<T, V, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
V: Eq,
S: BuildHasher,
{
}
impl<T, V, S> Hash for HConMap<T, V, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
V: Hash,
S: BuildHasher,
{
fn hash<H>(&self, h: &mut H)
where
H: Hasher,
{
for (key, value) in self {
key.hash(h);
value.hash(h)
}
}
}
impl<T, V, S> Default for HConMap<T, V, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
S: Default,
{
fn default() -> Self {
HConMap {
map: HashMap::default(),
}
}
}
hashplement! {
#[cfg(feature = "with_ahash")]
HConMap<K, V> for self::hashers::a_hash::Builder;
HConMap<K, V> for self::hashers::sip_hash::Builder;
HConMap<K, V> for self::hashers::p_hash::Builder;
HConMap<K, V> for self::hashers::id_hash::Builder;
}
impl<T, V, S> HConMap<T, V, S>
where
T: HashConsed,
T::Inner: Eq + Hash,
S: BuildHasher,
{
#[inline]
pub fn with_hasher(build_hasher: S) -> Self {
HConMap {
map: HashMap::with_hasher(build_hasher),
}
}
#[inline]
pub fn with_capacity_and_hasher(capa: usize, build_hasher: S) -> Self {
HConMap {
map: HashMap::with_capacity_and_hasher(capa, build_hasher),
}
}
}
impl<T: HashConsed, V, S> HConMap<T, V, S>
where
T::Inner: Hash + Eq,
{
#[inline]
pub fn iter(&self) -> ::std::collections::hash_map::Iter<HConsed<T::Inner>, V> {
self.map.iter()
}
#[inline]
pub fn iter_mut(&mut self) -> ::std::collections::hash_map::IterMut<HConsed<T::Inner>, V> {
self.map.iter_mut()
}
}
impl<'a, T, V, S> IntoIterator for &'a HConMap<T, V, S>
where
T: HashConsed,
T::Inner: Hash + Eq,
{
type Item = (&'a HConsed<T::Inner>, &'a V);
type IntoIter = ::std::collections::hash_map::Iter<'a, HConsed<T::Inner>, V>;
fn into_iter(self) -> Self::IntoIter {
self.map.iter()
}
}
impl<'a, T, V, S> IntoIterator for &'a mut HConMap<T, V, S>
where
T: HashConsed,
T::Inner: Hash + Eq,
{
type Item = (&'a HConsed<T::Inner>, &'a mut V);
type IntoIter = ::std::collections::hash_map::IterMut<'a, HConsed<T::Inner>, V>;
fn into_iter(self) -> Self::IntoIter {
self.map.iter_mut()
}
}
impl<T, V, S> IntoIterator for HConMap<T, V, S>
where
T: HashConsed,
T::Inner: Hash + Eq,
{
type Item = (HConsed<T::Inner>, V);
type IntoIter = ::std::collections::hash_map::IntoIter<HConsed<T::Inner>, V>;
fn into_iter(self) -> Self::IntoIter {
self.map.into_iter()
}
}
impl<T, V, S> ::std::iter::FromIterator<(HConsed<T::Inner>, V)> for HConMap<T, V, S>
where
T: HashConsed,
T::Inner: Hash + Eq,
S: Default + BuildHasher,
{
fn from_iter<I: IntoIterator<Item = (HConsed<T::Inner>, V)>>(iter: I) -> Self {
HConMap {
map: HashMap::from_iter(iter),
}
}
}
impl<T: HashConsed, V, S> Deref for HConMap<T, V, S>
where
T::Inner: Hash + Eq,
{
type Target = HashMap<HConsed<T::Inner>, V, S>;
fn deref(&self) -> &Self::Target {
&self.map
}
}
impl<T: HashConsed, V, S> DerefMut for HConMap<T, V, S>
where
T::Inner: Hash + Eq,
{
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.map
}
}
impl<T, V, Src, S> From<Src> for HConMap<HConsed<T>, V, S>
where
T: Hash + Eq,
Src: Iterator<Item = (HConsed<T>, V)>,
S: BuildHasher + Default,
{
fn from(src: Src) -> Self {
let mut set = HConMap::default();
for (elem, value) in src {
set.insert(elem, value);
}
set
}
}
mod hash {
use std::hash::{BuildHasher, Hasher};
#[derive(Clone, Default)]
pub struct BuildHashU64 {}
impl BuildHashU64 {
#[allow(dead_code)]
pub fn new() -> Self {
Self {}
}
}
impl BuildHasher for BuildHashU64 {
type Hasher = HashU64;
fn build_hasher(&self) -> HashU64 {
HashU64 { buf: [0; 8] }
}
}
pub struct HashU64 {
buf: [u8; 8],
}
impl HashU64 {
#[cfg(debug)]
#[inline(always)]
fn test_bytes(bytes: &[u8]) {
if bytes.len() != 8 {
panic!(
"[illegal] `HashU64::hash` \
called with non-`u64` argument ({} bytes, expected {})",
bytes.len(),
8
)
}
}
#[cfg(not(debug))]
#[inline(always)]
fn test_bytes(_: &[u8]) {}
}
impl Hasher for HashU64 {
fn finish(&self) -> u64 {
let block: u64 = unsafe { ::std::mem::transmute(self.buf) };
block.wrapping_mul(0xDA5DF7A7BD02F2C7u64)
}
fn write(&mut self, bytes: &[u8]) {
Self::test_bytes(bytes);
self.buf[..8].clone_from_slice(&bytes[..8])
}
}
}