turbo_prehash/
lib.rs

1//! turbo-prehash
2//!
3//! A small wrapper around `std::hash::Hasher` that allows you to pre-hash a
4//! value before hashing it.
5//!
6//! This is useful for when you want to hash a value that is expensive to
7//! compute (e.g. a large string) but you want to avoid re-hashing it every
8//! time.
9//!
10//! # Example
11//!
12//! ```
13//! use std::hash::{BuildHasherDefault, RandomState, Hash};
14//!
15//! use rustc_hash::FxHashMap;
16//! use turbo_prehash::{BuildHasherExt, PreHashed};
17//!
18//! /// hash a key, returning a prehashed value
19//! fn hash_key<T: Hash>(key: T) -> PreHashed<T> {
20//!     RandomState::new().prehash(key)
21//! }
22//!
23//! // create hashmap to hold pre-hashed values
24//! let mut map: FxHashMap<PreHashed<String>, String> = FxHashMap::default();
25//!
26//! // insert a prehashed value
27//! let hashed_key = hash_key("hello".to_string());
28//! map.insert(hashed_key.clone(), "world".to_string());
29//!
30//! // get the value
31//! assert_eq!(map.get(&hashed_key), Some(&"world".to_string()));
32//! ```
33
34use std::{
35    fmt,
36    hash::{BuildHasher, Hash, Hasher},
37    ops::Deref,
38};
39
40/// A wrapper type that hashes some `inner` on creation, implementing [Hash]
41/// by simply returning the pre-computed hash.
42#[derive(Copy, Debug, Clone)]
43pub struct PreHashed<I, H = u64> {
44    hash: H,
45    inner: I,
46}
47
48impl<I, H> PreHashed<I, H> {
49    /// Create a new [PreHashed] value with the given hash and inner value.
50    ///
51    /// SAFETY: The hash must be a valid hash of the inner value.
52    pub fn new(hash: H, inner: I) -> Self {
53        Self { hash, inner }
54    }
55
56    /// Split the [PreHashed] value into its hash and inner value.
57    pub fn into_parts(self) -> (H, I) {
58        (self.hash, self.inner)
59    }
60
61    fn inner(&self) -> &I {
62        &self.inner
63    }
64}
65
66impl<I: Hash> PreHashed<I, u64> {
67    /// Create a new [PreHashed] value from a [BuildHasher].
68    fn new_from_builder<B: BuildHasher>(hasher: &B, inner: I) -> Self {
69        Self::new(hasher.hash_one(&inner), inner)
70    }
71}
72
73impl<I> Deref for PreHashed<I> {
74    type Target = I;
75
76    fn deref(&self) -> &Self::Target {
77        self.inner()
78    }
79}
80
81impl<I, H> AsRef<I> for PreHashed<I, H> {
82    fn as_ref(&self) -> &I {
83        self.inner()
84    }
85}
86
87impl<I, H: Hash> Hash for PreHashed<I, H> {
88    fn hash<S: Hasher>(&self, state: &mut S) {
89        self.hash.hash(state)
90    }
91}
92
93impl<I: Eq, H> Eq for PreHashed<I, H> {}
94
95impl<I: PartialEq, H> PartialEq for PreHashed<I, H> {
96    // note: we compare the values, not the hashes
97    fn eq(&self, other: &Self) -> bool {
98        self.inner.eq(&other.inner)
99    }
100}
101
102impl<I: fmt::Display, H> fmt::Display for PreHashed<I, H> {
103    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
104        self.inner.fmt(f)
105    }
106}
107
108/// An implementer of [Hash] that simply returns the pre-computed hash.
109#[derive(Copy, Clone, Debug, Default)]
110pub struct PassThroughHash(u64);
111
112impl PassThroughHash {
113    pub fn new() -> Self {
114        Default::default()
115    }
116}
117
118impl Hasher for PassThroughHash {
119    fn write(&mut self, _bytes: &[u8]) {
120        unimplemented!("do not use")
121    }
122
123    fn write_u64(&mut self, i: u64) {
124        self.0 = i;
125    }
126
127    fn finish(&self) -> u64 {
128        self.0
129    }
130}
131
132/// An extension trait for [BuildHasher] that provides the
133/// [BuildHasherExt::prehash] method.
134pub trait BuildHasherExt: BuildHasher {
135    type Hash;
136
137    fn prehash<T: Hash>(&self, value: T) -> PreHashed<T, Self::Hash>;
138}
139
140impl<B: BuildHasher> BuildHasherExt for B {
141    type Hash = u64;
142
143    fn prehash<T: Hash>(&self, value: T) -> PreHashed<T, Self::Hash> {
144        PreHashed::new_from_builder(self, value)
145    }
146}
turbo_prehash/lib.rs

turbo_prehash/
lib.rs
