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/// A pre-hashed value of a specific type. Pre-hashing enables memoization of hashes that are expensive to compute.
34///
35/// It also enables faster [`PartialEq`] comparisons by short circuiting on hash equality.
36/// See [`PassHash`] and [`PassHasher`] for a "pass through" [`BuildHasher`] and [`Hasher`] implementation
37/// designed to work with [`Hashed`]
38/// See `PreHashMap` for a hashmap pre-configured to use [`Hashed`] keys.
39pub struct Hashed<V, S = FixedHasher> {
40    hash: u64,
41    value: V,
42    marker: PhantomData<S>,
43}
44
45impl<V: Hash, H: BuildHasher + Default> Hashed<V, H> {
46    /// Pre-hashes the given value using the [`BuildHasher`] configured in the [`Hashed`] type.
47    pub fn new(value: V) -> Self {
48        Self {
49            hash: H::default().hash_one(&value),
50            value,
51            marker: PhantomData,
52        }
53    }
54
55    /// The pre-computed hash.
56    #[inline]
57    pub fn hash(&self) -> u64 {
58        self.hash
59    }
60}
61
62impl<V, H> Hash for Hashed<V, H> {
63    #[inline]
64    fn hash<R: Hasher>(&self, state: &mut R) {
65        state.write_u64(self.hash);
66    }
67}
68
69impl<V: Hash, H: BuildHasher + Default> From<V> for Hashed<V, H> {
70    fn from(value: V) -> Self {
71        Self::new(value)
72    }
73}
74
75impl<V, H> Deref for Hashed<V, H> {
76    type Target = V;
77
78    #[inline]
79    fn deref(&self) -> &Self::Target {
80        &self.value
81    }
82}
83
84impl<V: PartialEq, H> PartialEq for Hashed<V, H> {
85    /// A fast impl of [`PartialEq`] that first checks that `other`'s pre-computed hash
86    /// matches this value's pre-computed hash.
87    #[inline]
88    fn eq(&self, other: &Self) -> bool {
89        self.hash == other.hash && self.value.eq(&other.value)
90    }
91}
92
93impl<V: Debug, H> Debug for Hashed<V, H> {
94    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
95        f.debug_struct("Hashed")
96            .field("hash", &self.hash)
97            .field("value", &self.value)
98            .finish()
99    }
100}
101
102impl<V: Clone, H> Clone for Hashed<V, H> {
103    #[inline]
104    fn clone(&self) -> Self {
105        Self {
106            hash: self.hash,
107            value: self.value.clone(),
108            marker: PhantomData,
109        }
110    }
111}
112
113impl<V: Copy, H> Copy for Hashed<V, H> {}
114
115impl<V: Eq, H> Eq for Hashed<V, H> {}
116
117/// A [`BuildHasher`] that results in a [`PassHasher`].
118#[derive(Default, Clone)]
119pub struct PassHash;
120
121impl BuildHasher for PassHash {
122    type Hasher = PassHasher;
123
124    fn build_hasher(&self) -> Self::Hasher {
125        PassHasher::default()
126    }
127}
128
129/// A no-op hash that only works on `u64`s. Will panic if attempting to
130/// hash a type containing non-u64 fields.
131#[derive(Debug, Default)]
132pub struct PassHasher {
133    hash: u64,
134}
135
136impl Hasher for PassHasher {
137    #[inline]
138    fn finish(&self) -> u64 {
139        self.hash
140    }
141
142    fn write(&mut self, _bytes: &[u8]) {
143        panic!("can only hash u64 using PassHasher");
144    }
145
146    #[inline]
147    fn write_u64(&mut self, i: u64) {
148        self.hash = i;
149    }
150}
151
152/// [`BuildHasher`] for types that already contain a high-quality hash.
153#[derive(Clone, Default)]
154pub struct NoOpHash;
155
156impl BuildHasher for NoOpHash {
157    type Hasher = NoOpHasher;
158
159    fn build_hasher(&self) -> Self::Hasher {
160        NoOpHasher(0)
161    }
162}
163
164#[doc(hidden)]
165pub struct NoOpHasher(u64);
166
167// This is for types that already contain a high-quality hash and want to skip
168// re-hashing that hash.
169impl Hasher for NoOpHasher {
170    fn finish(&self) -> u64 {
171        self.0
172    }
173
174    fn write(&mut self, bytes: &[u8]) {
175        // This should never be called by consumers. Prefer to call `write_u64` instead.
176        // Don't break applications (slower fallback, just check in test):
177        self.0 = bytes.iter().fold(self.0, |hash, b| {
178            hash.rotate_left(8).wrapping_add(*b as u64)
179        });
180    }
181
182    #[inline]
183    fn write_u64(&mut self, i: u64) {
184        self.0 = i;
185    }
186}
bevy_platform/hash.rs

bevy_platform/
hash.rs
