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;
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, H> Deref for Hashed<V, H> {
70    type Target = V;
71
72    #[inline]
73    fn deref(&self) -> &Self::Target {
74        &self.value
75    }
76}
77
78impl<V: PartialEq, H> PartialEq for Hashed<V, H> {
79    /// A fast impl of [`PartialEq`] that first checks that `other`'s pre-computed hash
80    /// matches this value's pre-computed hash.
81    #[inline]
82    fn eq(&self, other: &Self) -> bool {
83        self.hash == other.hash && self.value.eq(&other.value)
84    }
85}
86
87impl<V: Debug, H> Debug for Hashed<V, H> {
88    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
89        f.debug_struct("Hashed")
90            .field("hash", &self.hash)
91            .field("value", &self.value)
92            .finish()
93    }
94}
95
96impl<V: Clone, H> Clone for Hashed<V, H> {
97    #[inline]
98    fn clone(&self) -> Self {
99        Self {
100            hash: self.hash,
101            value: self.value.clone(),
102            marker: PhantomData,
103        }
104    }
105}
106
107impl<V: Copy, H> Copy for Hashed<V, H> {}
108
109impl<V: Eq, H> Eq for Hashed<V, H> {}
110
111/// A [`BuildHasher`] that results in a [`PassHasher`].
112#[derive(Default, Clone)]
113pub struct PassHash;
114
115impl BuildHasher for PassHash {
116    type Hasher = PassHasher;
117
118    fn build_hasher(&self) -> Self::Hasher {
119        PassHasher::default()
120    }
121}
122
123/// A no-op hash that only works on `u64`s. Will panic if attempting to
124/// hash a type containing non-u64 fields.
125#[derive(Debug, Default)]
126pub struct PassHasher {
127    hash: u64,
128}
129
130impl Hasher for PassHasher {
131    #[inline]
132    fn finish(&self) -> u64 {
133        self.hash
134    }
135
136    fn write(&mut self, _bytes: &[u8]) {
137        panic!("can only hash u64 using PassHasher");
138    }
139
140    #[inline]
141    fn write_u64(&mut self, i: u64) {
142        self.hash = i;
143    }
144}
145
146/// [`BuildHasher`] for types that already contain a high-quality hash.
147#[derive(Clone, Default)]
148pub struct NoOpHash;
149
150impl BuildHasher for NoOpHash {
151    type Hasher = NoOpHasher;
152
153    fn build_hasher(&self) -> Self::Hasher {
154        NoOpHasher(0)
155    }
156}
157
158#[doc(hidden)]
159pub struct NoOpHasher(u64);
160
161// This is for types that already contain a high-quality hash and want to skip
162// re-hashing that hash.
163impl Hasher for NoOpHasher {
164    fn finish(&self) -> u64 {
165        self.0
166    }
167
168    fn write(&mut self, bytes: &[u8]) {
169        // This should never be called by consumers. Prefer to call `write_u64` instead.
170        // Don't break applications (slower fallback, just check in test):
171        self.0 = bytes.iter().fold(self.0, |hash, b| {
172            hash.rotate_left(8).wrapping_add(*b as u64)
173        });
174    }
175
176    #[inline]
177    fn write_u64(&mut self, i: u64) {
178        self.0 = i;
179    }
180}
bevy_platform/hash.rs

bevy_platform/
hash.rs
