bevy_platform/
hash.rs

1//! Provides replacements for `std::hash` items using [`foldhash`].
2//!
3//! Also provides some additional items beyond the standard library.
4
5use core::{
6    fmt::Debug,
7    hash::{BuildHasher, Hash, Hasher},
8    marker::PhantomData,
9    ops::Deref,
10};
11
12pub use foldhash::fast::{FixedState, FoldHasher as DefaultHasher, RandomState};
13
14/// For when you want a deterministic hasher.
15///
16/// Seed was randomly generated with a fair dice roll. Guaranteed to be random:
17/// <https://github.com/bevyengine/bevy/pull/1268/files#r560918426>
18const FIXED_HASHER: FixedState =
19    FixedState::with_seed(0b1001010111101110000001001100010000000011001001101011001001111000);
20
21/// Deterministic hasher based upon a random but fixed state.
22#[derive(Copy, Clone, Default, Debug)]
23pub struct FixedHasher;
24impl BuildHasher for FixedHasher {
25    type Hasher = DefaultHasher<'static>;
26
27    #[inline]
28    fn build_hasher(&self) -> Self::Hasher {
29        FIXED_HASHER.build_hasher()
30    }
31}
32
33/// Hashes one value with the deterministic [`FixedHasher`].
34pub fn fixed_hash_one(x: impl Hash) -> u64 {
35    FixedHasher.hash_one(x)
36}
37
38/// A pre-hashed value of a specific type. Pre-hashing enables memoization of hashes that are expensive to compute.
39///
40/// It also enables faster [`PartialEq`] comparisons by short circuiting on hash equality.
41/// See [`PassHash`] and [`PassHasher`] for a "pass through" [`BuildHasher`] and [`Hasher`] implementation
42/// designed to work with [`Hashed`]
43/// See `PreHashMap` for a hashmap pre-configured to use [`Hashed`] keys.
44pub struct Hashed<V, S = FixedHasher> {
45    hash: u64,
46    value: V,
47    marker: PhantomData<S>,
48}
49
50impl<V: Hash, H: BuildHasher + Default> Hashed<V, H> {
51    /// Pre-hashes the given value using the [`BuildHasher`] configured in the [`Hashed`] type.
52    pub fn new(value: V) -> Self {
53        Self {
54            hash: H::default().hash_one(&value),
55            value,
56            marker: PhantomData,
57        }
58    }
59
60    /// Mutates the current value and re-computes the hash.
61    pub fn mutate(&mut self, func: impl FnOnce(&mut V)) {
62        func(&mut self.value);
63        self.hash = H::default().hash_one(&self.value);
64    }
65
66    /// The pre-computed hash.
67    #[inline]
68    pub fn hash(&self) -> u64 {
69        self.hash
70    }
71}
72
73impl<V, H> Hash for Hashed<V, H> {
74    #[inline]
75    fn hash<R: Hasher>(&self, state: &mut R) {
76        state.write_u64(self.hash);
77    }
78}
79
80impl<V: Hash, H: BuildHasher + Default> From<V> for Hashed<V, H> {
81    fn from(value: V) -> Self {
82        Self::new(value)
83    }
84}
85
86impl<V, H> Deref for Hashed<V, H> {
87    type Target = V;
88
89    #[inline]
90    fn deref(&self) -> &Self::Target {
91        &self.value
92    }
93}
94
95impl<V: PartialEq, H> PartialEq for Hashed<V, H> {
96    /// A fast impl of [`PartialEq`] that first checks that `other`'s pre-computed hash
97    /// matches this value's pre-computed hash.
98    #[inline]
99    fn eq(&self, other: &Self) -> bool {
100        self.hash == other.hash && self.value.eq(&other.value)
101    }
102}
103
104impl<V: Debug, H> Debug for Hashed<V, H> {
105    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
106        f.debug_struct("Hashed")
107            .field("hash", &self.hash)
108            .field("value", &self.value)
109            .finish()
110    }
111}
112
113impl<V: Clone, H> Clone for Hashed<V, H> {
114    #[inline]
115    fn clone(&self) -> Self {
116        Self {
117            hash: self.hash,
118            value: self.value.clone(),
119            marker: PhantomData,
120        }
121    }
122}
123
124impl<V: Copy, H> Copy for Hashed<V, H> {}
125
126impl<V: Eq, H> Eq for Hashed<V, H> {}
127
128/// A [`BuildHasher`] that results in a [`PassHasher`].
129#[derive(Default, Clone)]
130pub struct PassHash;
131
132impl BuildHasher for PassHash {
133    type Hasher = PassHasher;
134
135    fn build_hasher(&self) -> Self::Hasher {
136        PassHasher::default()
137    }
138}
139
140/// A no-op hash that only works on `u64`s. Will panic if attempting to
141/// hash a type containing non-u64 fields.
142#[derive(Debug, Default)]
143pub struct PassHasher {
144    hash: u64,
145}
146
147impl Hasher for PassHasher {
148    #[inline]
149    fn finish(&self) -> u64 {
150        self.hash
151    }
152
153    fn write(&mut self, _bytes: &[u8]) {
154        panic!("can only hash u64 using PassHasher");
155    }
156
157    #[inline]
158    fn write_u64(&mut self, i: u64) {
159        self.hash = i;
160    }
161}
162
163/// [`BuildHasher`] for types that already contain a high-quality hash.
164#[derive(Clone, Default)]
165pub struct NoOpHash;
166
167impl BuildHasher for NoOpHash {
168    type Hasher = NoOpHasher;
169
170    fn build_hasher(&self) -> Self::Hasher {
171        NoOpHasher(0)
172    }
173}
174
175#[doc(hidden)]
176pub struct NoOpHasher(u64);
177
178// This is for types that already contain a high-quality hash and want to skip
179// re-hashing that hash.
180impl Hasher for NoOpHasher {
181    fn finish(&self) -> u64 {
182        self.0
183    }
184
185    fn write(&mut self, bytes: &[u8]) {
186        // This should never be called by consumers. Prefer to call `write_u64` instead.
187        // Don't break applications (slower fallback, just check in test):
188        self.0 = bytes.iter().fold(self.0, |hash, b| {
189            hash.rotate_left(8).wrapping_add(*b as u64)
190        });
191    }
192
193    #[inline]
194    fn write_u64(&mut self, i: u64) {
195        self.0 = i;
196    }
197}
bevy_platform/hash.rs

bevy_platform/
hash.rs
