identity_hash/
lib.rs

1// Copyright 2018-2020 Parity Technologies (UK) Ltd.
2// Copyright 2023 Team Offsetting
3//
4// Licensed under the Apache License, Version 2.0 or MIT license, at your option.
5//
6// A copy of the Apache License, Version 2.0 is included in the software as
7// LICENSE-APACHE and a copy of the MIT license is included in the software
8// as LICENSE-MIT. You may also obtain a copy of the Apache License, Version 2.0
9// at https://www.apache.org/licenses/LICENSE-2.0 and a copy of the MIT license
10// at https://opensource.org/licenses/MIT.
11
12#![cfg_attr(not(feature = "std"), no_std)]
13
14//! This is a fork of the inactive project [paritytech/nohash-hasher](https://github.com/paritytech/nohash-hasher).
15
16use core::{
17  fmt,
18  hash::{BuildHasherDefault, Hasher},
19  marker::PhantomData,
20};
21
22/// A `HashMap` with an integer domain, using `IdentityHasher` to perform no hashing at all.
23///
24/// # Examples
25///
26/// See [`IdentityHashable`] for use with custom types.
27///
28/// ```
29/// use identity_hash::IntMap;
30///
31/// let mut m: IntMap<u32, bool> = IntMap::default();
32///
33/// m.insert(0, false);
34/// m.insert(1, true);
35///
36/// assert!(m.contains_key(&0));
37/// assert!(m.contains_key(&1));
38/// ```
39#[cfg(feature = "std")]
40pub type IntMap<K, V> = std::collections::HashMap<K, V, BuildIdentityHasher<K>>;
41
42/// A `HashSet` of integers, using `IdentityHasher` to perform no hashing at all.
43///
44/// # Examples
45///
46/// See [`IdentityHashable`] for use with custom types.
47///
48/// ```
49/// use identity_hash::IntSet;
50///
51/// let mut m = IntSet::default();
52///
53/// m.insert(0u32);
54/// m.insert(1u32);
55///
56/// assert!(m.contains(&0));
57/// assert!(m.contains(&1));
58/// ```
59#[cfg(feature = "std")]
60pub type IntSet<T> = std::collections::HashSet<T, BuildIdentityHasher<T>>;
61
62/// An alias for `BuildHasherDefault` for use with `IdentityHasher`.
63///
64/// # Examples
65///
66/// See also [`IntMap`] and [`IntSet`] for some easier usage examples.
67///
68/// ```
69/// use identity_hash::BuildIdentityHasher;
70/// use std::collections::HashMap;
71///
72/// let mut m: HashMap::<u8, char, BuildIdentityHasher<u8>> =
73///     HashMap::with_capacity_and_hasher(2, BuildIdentityHasher::default());
74///
75/// m.insert(0, 'a');
76/// m.insert(1, 'b');
77///
78/// assert_eq!(Some(&'a'), m.get(&0));
79/// assert_eq!(Some(&'b'), m.get(&1));
80/// ```
81pub type BuildIdentityHasher<T> = BuildHasherDefault<IdentityHasher<T>>;
82
83/// For an enabled type `T`, a `IdentityHasher<T>` implements `std::hash::Hasher` and
84/// uses the value set by one of the `write_{u8, u16, u32, u64, usize, i8, i16, i32,
85/// i64, isize}` methods as its hash output.
86///
87/// `IdentityHasher` does not implement any hashing algorithm and can only be used
88/// with types which can be mapped directly to a numeric value. Out of the box
89/// `IdentityHasher` is enabled for `u8`, `u16`, `u32`, `u64`, `usize`, `i8`, `i16`,
90/// `i32`, `i64`, and `isize`. Types that should be used with `IdentityHasher` need
91/// to implement [`IdentityHashable`] and by doing so assert that their `Hash` impl invokes
92/// *only one* of the `Hasher::write_{u8, u16, u32, u64, usize, i8, i16, i32, i64,
93/// isize}` methods *exactly once*.
94///
95/// # Examples
96///
97/// See also [`BuildIdentityHasher`], [`IntMap`] and [`IntSet`] for some easier
98/// usage examples. See [`IdentityHashable`] for use with custom types.
99///
100/// ```
101/// use identity_hash::IdentityHasher;
102/// use std::{collections::HashMap, hash::BuildHasherDefault};
103///
104/// let mut m: HashMap::<u8, char, BuildHasherDefault<IdentityHasher<u8>>> =
105///     HashMap::with_capacity_and_hasher(2, BuildHasherDefault::default());
106///
107/// m.insert(0, 'a');
108/// m.insert(1, 'b');
109///
110/// assert_eq!(Some(&'a'), m.get(&0));
111/// assert_eq!(Some(&'b'), m.get(&1));
112/// ```
113#[cfg(debug_assertions)]
114pub struct IdentityHasher<T>(u64, bool, PhantomData<T>);
115
116#[cfg(not(debug_assertions))]
117pub struct IdentityHasher<T>(u64, PhantomData<T>);
118
119impl<T> fmt::Debug for IdentityHasher<T> {
120  #[cfg(debug_assertions)]
121  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
122    f.debug_tuple("IdentityHasher")
123      .field(&self.0)
124      .field(&self.1)
125      .finish()
126  }
127
128  #[cfg(not(debug_assertions))]
129  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
130    f.debug_tuple("IdentityHasher").field(&self.0).finish()
131  }
132}
133
134impl<T> Default for IdentityHasher<T> {
135  #[cfg(debug_assertions)]
136  fn default() -> Self {
137    IdentityHasher(0, false, PhantomData)
138  }
139
140  #[cfg(not(debug_assertions))]
141  fn default() -> Self {
142    IdentityHasher(0, PhantomData)
143  }
144}
145
146impl<T> Clone for IdentityHasher<T> {
147  #[cfg(debug_assertions)]
148  fn clone(&self) -> Self {
149    IdentityHasher(self.0, self.1, self.2)
150  }
151
152  #[cfg(not(debug_assertions))]
153  fn clone(&self) -> Self {
154    IdentityHasher(self.0, self.1)
155  }
156}
157
158impl<T> Copy for IdentityHasher<T> {}
159
160/// Types which are safe to use with `IdentityHasher`.
161///
162/// This marker trait is an option for types to enable themselves for use
163/// with `IdentityHasher`. In order to be safe, the `Hash` impl needs to
164/// satisfy the following constraint:
165///
166/// > **One of the `Hasher::write_{u8,u16,u32,u64,usize,i8,i16,i32,i64,isize}`
167/// methods is invoked exactly once.**
168///
169/// The best way to ensure this is to write a custom `Hash` impl even when
170/// deriving `Hash` for a simple new type of a single type which itself
171/// implements `IsEnabled` may work as well.
172///
173/// # Example
174///
175/// ```
176/// #[derive(PartialEq, Eq)]
177/// struct SomeType(u32);
178///
179/// impl std::hash::Hash for SomeType {
180///     fn hash<H: std::hash::Hasher>(&self, hasher: &mut H) {
181///         hasher.write_u32(self.0)
182///     }
183/// }
184///
185/// impl identity_hash::IdentityHashable for SomeType {}
186///
187/// let mut m = identity_hash::IntMap::default();
188///
189/// m.insert(SomeType(1), 't');
190/// m.insert(SomeType(0), 'f');
191///
192/// assert_eq!(Some(&'t'), m.get(&SomeType(1)));
193/// assert_eq!(Some(&'f'), m.get(&SomeType(0)));
194/// ```
195pub trait IdentityHashable {}
196
197impl IdentityHashable for u8 {}
198
199impl IdentityHashable for u16 {}
200
201impl IdentityHashable for u32 {}
202
203impl IdentityHashable for u64 {}
204
205impl IdentityHashable for usize {}
206
207impl IdentityHashable for i8 {}
208
209impl IdentityHashable for i16 {}
210
211impl IdentityHashable for i32 {}
212
213impl IdentityHashable for i64 {}
214
215impl IdentityHashable for isize {}
216
217#[cfg(not(debug_assertions))]
218impl<T: IdentityHashable> Hasher for IdentityHasher<T> {
219  fn write(&mut self, _: &[u8]) {
220    panic!("Invalid use of IdentityHasher")
221  }
222
223  fn write_u8(&mut self, n: u8) {
224    self.0 = u64::from(n)
225  }
226  fn write_u16(&mut self, n: u16) {
227    self.0 = u64::from(n)
228  }
229  fn write_u32(&mut self, n: u32) {
230    self.0 = u64::from(n)
231  }
232  fn write_u64(&mut self, n: u64) {
233    self.0 = n
234  }
235  fn write_usize(&mut self, n: usize) {
236    self.0 = n as u64
237  }
238
239  fn write_i8(&mut self, n: i8) {
240    self.0 = n as u64
241  }
242  fn write_i16(&mut self, n: i16) {
243    self.0 = n as u64
244  }
245  fn write_i32(&mut self, n: i32) {
246    self.0 = n as u64
247  }
248  fn write_i64(&mut self, n: i64) {
249    self.0 = n as u64
250  }
251  fn write_isize(&mut self, n: isize) {
252    self.0 = n as u64
253  }
254
255  fn finish(&self) -> u64 {
256    self.0
257  }
258}
259
260#[cfg(debug_assertions)]
261impl<T: IdentityHashable> Hasher for IdentityHasher<T> {
262  fn write(&mut self, _: &[u8]) {
263    panic!("Invalid use of IdentityHasher")
264  }
265
266  fn write_u8(&mut self, n: u8) {
267    assert!(!self.1, "IdentityHasher: second write attempt detected.");
268    self.0 = u64::from(n);
269    self.1 = true
270  }
271
272  fn write_u16(&mut self, n: u16) {
273    assert!(!self.1, "IdentityHasher: second write attempt detected.");
274    self.0 = u64::from(n);
275    self.1 = true
276  }
277
278  fn write_u32(&mut self, n: u32) {
279    assert!(!self.1, "IdentityHasher: second write attempt detected.");
280    self.0 = u64::from(n);
281    self.1 = true
282  }
283
284  fn write_u64(&mut self, n: u64) {
285    assert!(!self.1, "IdentityHasher: second write attempt detected.");
286    self.0 = n;
287    self.1 = true
288  }
289
290  fn write_usize(&mut self, n: usize) {
291    assert!(!self.1, "IdentityHasher: second write attempt detected.");
292    self.0 = n as u64;
293    self.1 = true
294  }
295
296  fn write_i8(&mut self, n: i8) {
297    assert!(!self.1, "IdentityHasher: second write attempt detected.");
298    self.0 = n as u64;
299    self.1 = true
300  }
301
302  fn write_i16(&mut self, n: i16) {
303    assert!(!self.1, "IdentityHasher: second write attempt detected.");
304    self.0 = n as u64;
305    self.1 = true
306  }
307
308  fn write_i32(&mut self, n: i32) {
309    assert!(!self.1, "IdentityHasher: second write attempt detected.");
310    self.0 = n as u64;
311    self.1 = true
312  }
313
314  fn write_i64(&mut self, n: i64) {
315    assert!(!self.1, "IdentityHasher: second write attempt detected.");
316    self.0 = n as u64;
317    self.1 = true
318  }
319
320  fn write_isize(&mut self, n: isize) {
321    assert!(!self.1, "IdentityHasher: second write attempt detected.");
322    self.0 = n as u64;
323    self.1 = true
324  }
325
326  fn finish(&self) -> u64 {
327    self.0
328  }
329}
330
331#[cfg(test)]
332mod tests {
333  use super::*;
334
335  #[test]
336  fn ok() {
337    let mut h1 = IdentityHasher::<u8>::default();
338    h1.write_u8(42);
339    assert_eq!(42, h1.finish());
340
341    let mut h2 = IdentityHasher::<u16>::default();
342    h2.write_u16(42);
343    assert_eq!(42, h2.finish());
344
345    let mut h3 = IdentityHasher::<u32>::default();
346    h3.write_u32(42);
347    assert_eq!(42, h3.finish());
348
349    let mut h4 = IdentityHasher::<u64>::default();
350    h4.write_u64(42);
351    assert_eq!(42, h4.finish());
352
353    let mut h5 = IdentityHasher::<usize>::default();
354    h5.write_usize(42);
355    assert_eq!(42, h5.finish());
356
357    let mut h6 = IdentityHasher::<i8>::default();
358    h6.write_i8(42);
359    assert_eq!(42, h6.finish());
360
361    let mut h7 = IdentityHasher::<i16>::default();
362    h7.write_i16(42);
363    assert_eq!(42, h7.finish());
364
365    let mut h8 = IdentityHasher::<i32>::default();
366    h8.write_i32(42);
367    assert_eq!(42, h8.finish());
368
369    let mut h9 = IdentityHasher::<i64>::default();
370    h9.write_i64(42);
371    assert_eq!(42, h9.finish());
372
373    let mut h10 = IdentityHasher::<isize>::default();
374    h10.write_isize(42);
375    assert_eq!(42, h10.finish())
376  }
377
378  #[cfg(debug_assertions)]
379  #[test]
380  #[should_panic]
381  fn u8_double_usage() {
382    let mut h = IdentityHasher::<u8>::default();
383    h.write_u8(42);
384    h.write_u8(43);
385  }
386
387  #[cfg(debug_assertions)]
388  #[test]
389  #[should_panic]
390  fn u16_double_usage() {
391    let mut h = IdentityHasher::<u16>::default();
392    h.write_u16(42);
393    h.write_u16(43);
394  }
395
396  #[cfg(debug_assertions)]
397  #[test]
398  #[should_panic]
399  fn u32_double_usage() {
400    let mut h = IdentityHasher::<u32>::default();
401    h.write_u32(42);
402    h.write_u32(43);
403  }
404
405  #[cfg(debug_assertions)]
406  #[test]
407  #[should_panic]
408  fn u64_double_usage() {
409    let mut h = IdentityHasher::<u64>::default();
410    h.write_u64(42);
411    h.write_u64(43);
412  }
413
414  #[cfg(debug_assertions)]
415  #[test]
416  #[should_panic]
417  fn usize_double_usage() {
418    let mut h = IdentityHasher::<usize>::default();
419    h.write_usize(42);
420    h.write_usize(43);
421  }
422
423  #[cfg(debug_assertions)]
424  #[test]
425  #[should_panic]
426  fn i8_double_usage() {
427    let mut h = IdentityHasher::<i8>::default();
428    h.write_i8(42);
429    h.write_i8(43);
430  }
431
432  #[cfg(debug_assertions)]
433  #[test]
434  #[should_panic]
435  fn i16_double_usage() {
436    let mut h = IdentityHasher::<i16>::default();
437    h.write_i16(42);
438    h.write_i16(43);
439  }
440
441  #[cfg(debug_assertions)]
442  #[test]
443  #[should_panic]
444  fn i32_double_usage() {
445    let mut h = IdentityHasher::<i32>::default();
446    h.write_i32(42);
447    h.write_i32(43);
448  }
449
450  #[cfg(debug_assertions)]
451  #[test]
452  #[should_panic]
453  fn i64_double_usage() {
454    let mut h = IdentityHasher::<i64>::default();
455    h.write_i64(42);
456    h.write_i64(43);
457  }
458
459  #[cfg(debug_assertions)]
460  #[test]
461  #[should_panic]
462  fn isize_double_usage() {
463    let mut h = IdentityHasher::<isize>::default();
464    h.write_isize(42);
465    h.write_isize(43);
466  }
467}
identity_hash/lib.rs

identity_hash/
lib.rs
