integer_hasher/
lib.rs

1// Copyright 2018-2020 Parity Technologies (UK) Ltd.
2//
3// Licensed under the Apache License, Version 2.0 or MIT license, at your option.
4//
5// A copy of the Apache License, Version 2.0 is included in the software as
6// LICENSE-APACHE and a copy of the MIT license is included in the software
7// as LICENSE-MIT. You may also obtain a copy of the Apache License, Version 2.0
8// at https://www.apache.org/licenses/LICENSE-2.0 and a copy of the MIT license
9// at https://opensource.org/licenses/MIT.
10
11// only enables the nightly `doc_cfg` feature when
12// the `docsrs` configuration attribute is defined
13#![cfg_attr(docsrs, feature(doc_auto_cfg))]
14#![cfg_attr(not(feature = "std"), no_std)]
15
16use core::{
17    hash::{BuildHasherDefault, Hasher},
18    marker::PhantomData,
19    num,
20};
21
22/// A `HashMap` with an integer domain, using `IntHasher` to perform no hashing at all.
23///
24/// # Examples
25///
26/// See [`IsEnabled`] for use with custom types.
27///
28/// ```
29/// use integer_hasher::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, BuildIntHasher<K>>;
41
42/// A `HashSet` of integers, using `IntHasher` to perform no hashing at all.
43///
44/// # Examples
45///
46/// See [`IsEnabled`] for use with custom types.
47///
48/// ```
49/// use integer_hasher::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, BuildIntHasher<T>>;
61
62/// An alias for `BuildHasherDefault` for use with `IntHasher`.
63///
64/// # Examples
65///
66/// See also [`IntMap`] and [`IntSet`] for some easier usage examples.
67///
68/// ```
69/// use integer_hasher::BuildIntHasher;
70/// use std::collections::HashMap;
71///
72/// let mut m: HashMap::<u8, char, BuildIntHasher<u8>> =
73///     HashMap::with_capacity_and_hasher(2, BuildIntHasher::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 BuildIntHasher<T> = BuildHasherDefault<IntHasher<T>>;
82
83/// For an enabled type `T`, a `IntHasher<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/// `IntHasher` 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/// `IntHasher` is enabled for `u8`, `u16`, `u32`, `u64`, `usize`, `i8`, `i16`,
90/// `i32`, `i64`, and `isize`. Types that should be used with `IntHasher` need
91/// to implement [`IsEnabled`] 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 [`BuildIntHasher`], [`IntMap`] and [`IntSet`] for some easier
98/// usage examples. See [`IsEnabled`] for use with custom types.
99///
100/// ```
101/// use integer_hasher::IntHasher;
102/// use std::{collections::HashMap, hash::BuildHasherDefault};
103///
104/// let mut m: HashMap::<u8, char, BuildHasherDefault<IntHasher<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#[derive(Debug)]
114pub struct IntHasher<T>(u64, #[cfg(debug_assertions)] bool, PhantomData<T>);
115
116impl<T> Copy for IntHasher<T> {}
117
118impl<T> Clone for IntHasher<T> {
119    fn clone(&self) -> Self {
120        *self
121    }
122}
123
124impl<T> Default for IntHasher<T> {
125    fn default() -> Self {
126        Self(
127            0,
128            #[cfg(debug_assertions)]
129            false,
130            PhantomData,
131        )
132    }
133}
134
135/// Types which are safe to use with `IntHasher`.
136///
137/// This marker trait is an option for types to enable themselves for use
138/// with `IntHasher`. In order to be safe, the `Hash` impl needs to
139/// satisfy the following constraint:
140///
141/// > **One of the `Hasher::write_{u8,u16,u32,u64,usize,i8,i16,i32,i64,isize}`
142/// methods is invoked exactly once.**
143///
144/// The best way to ensure this is to write a custom `Hash` impl even when
145/// deriving `Hash` for a simple newtype of a single type which itself
146/// implements `IsEnabled` may work as well.
147///
148/// # Example
149///
150/// ```
151/// #[derive(PartialEq, Eq)]
152/// struct SomeType(u32);
153///
154/// impl std::hash::Hash for SomeType {
155///     fn hash<H: std::hash::Hasher>(&self, hasher: &mut H) {
156///         hasher.write_u32(self.0)
157///     }
158/// }
159///
160/// impl integer_hasher::IsEnabled for SomeType {}
161///
162/// let mut m = integer_hasher::IntMap::default();
163///
164/// m.insert(SomeType(1), 't');
165/// m.insert(SomeType(0), 'f');
166///
167/// assert_eq!(Some(&'t'), m.get(&SomeType(1)));
168/// assert_eq!(Some(&'f'), m.get(&SomeType(0)));
169/// ```
170pub trait IsEnabled {}
171
172impl IsEnabled for u8 {}
173impl IsEnabled for u16 {}
174impl IsEnabled for u32 {}
175impl IsEnabled for u64 {}
176impl IsEnabled for usize {}
177
178impl IsEnabled for i8 {}
179impl IsEnabled for i16 {}
180impl IsEnabled for i32 {}
181impl IsEnabled for i64 {}
182impl IsEnabled for isize {}
183
184impl IsEnabled for num::NonZeroU8 {}
185impl IsEnabled for num::NonZeroU16 {}
186impl IsEnabled for num::NonZeroU32 {}
187impl IsEnabled for num::NonZeroU64 {}
188impl IsEnabled for num::NonZeroUsize {}
189
190impl IsEnabled for num::NonZeroI8 {}
191impl IsEnabled for num::NonZeroI16 {}
192impl IsEnabled for num::NonZeroI32 {}
193impl IsEnabled for num::NonZeroI64 {}
194impl IsEnabled for num::NonZeroIsize {}
195
196impl IsEnabled for num::Wrapping<u8> {}
197impl IsEnabled for num::Wrapping<u16> {}
198impl IsEnabled for num::Wrapping<u32> {}
199impl IsEnabled for num::Wrapping<u64> {}
200impl IsEnabled for num::Wrapping<usize> {}
201
202impl IsEnabled for num::Wrapping<i8> {}
203impl IsEnabled for num::Wrapping<i16> {}
204impl IsEnabled for num::Wrapping<i32> {}
205impl IsEnabled for num::Wrapping<i64> {}
206impl IsEnabled for num::Wrapping<isize> {}
207
208impl<T> IntHasher<T> {
209    fn precond_check(&mut self) {
210        #[cfg(debug_assertions)]
211        {
212            assert!(!self.1, "IntHasher: second write attempt detected.");
213            self.1 = true
214        }
215    }
216}
217
218impl<T: IsEnabled> Hasher for IntHasher<T> {
219    fn write(&mut self, _: &[u8]) {
220        panic!("Invalid use of IntHasher")
221    }
222
223    fn write_u8(&mut self, n: u8) {
224        self.precond_check();
225        self.0 = u64::from(n)
226    }
227    fn write_u16(&mut self, n: u16) {
228        self.precond_check();
229        self.0 = u64::from(n)
230    }
231    fn write_u32(&mut self, n: u32) {
232        self.precond_check();
233        self.0 = u64::from(n)
234    }
235    fn write_u64(&mut self, n: u64) {
236        self.precond_check();
237        self.0 = n
238    }
239    fn write_usize(&mut self, n: usize) {
240        self.precond_check();
241        self.0 = n as u64
242    }
243
244    fn write_i8(&mut self, n: i8) {
245        self.precond_check();
246        self.0 = n as u64
247    }
248    fn write_i16(&mut self, n: i16) {
249        self.precond_check();
250        self.0 = n as u64
251    }
252    fn write_i32(&mut self, n: i32) {
253        self.precond_check();
254        self.0 = n as u64
255    }
256    fn write_i64(&mut self, n: i64) {
257        self.precond_check();
258        self.0 = n as u64
259    }
260    fn write_isize(&mut self, n: isize) {
261        self.precond_check();
262        self.0 = n as u64
263    }
264
265    fn finish(&self) -> u64 {
266        #[cfg(debug_assertions)]
267        {
268            assert!(self.1, "IntHasher: no write is called before finish()");
269        }
270
271        self.0
272    }
273}
274
275#[cfg(test)]
276mod tests {
277    use super::*;
278
279    #[test]
280    fn ok() {
281        let mut h1 = IntHasher::<u8>::default();
282        h1.write_u8(42);
283        assert_eq!(42, h1.finish());
284
285        let mut h2 = IntHasher::<u16>::default();
286        h2.write_u16(42);
287        assert_eq!(42, h2.finish());
288
289        let mut h3 = IntHasher::<u32>::default();
290        h3.write_u32(42);
291        assert_eq!(42, h3.finish());
292
293        let mut h4 = IntHasher::<u64>::default();
294        h4.write_u64(42);
295        assert_eq!(42, h4.finish());
296
297        let mut h5 = IntHasher::<usize>::default();
298        h5.write_usize(42);
299        assert_eq!(42, h5.finish());
300
301        let mut h6 = IntHasher::<i8>::default();
302        h6.write_i8(42);
303        assert_eq!(42, h6.finish());
304
305        let mut h7 = IntHasher::<i16>::default();
306        h7.write_i16(42);
307        assert_eq!(42, h7.finish());
308
309        let mut h8 = IntHasher::<i32>::default();
310        h8.write_i32(42);
311        assert_eq!(42, h8.finish());
312
313        let mut h9 = IntHasher::<i64>::default();
314        h9.write_i64(42);
315        assert_eq!(42, h9.finish());
316
317        let mut h10 = IntHasher::<isize>::default();
318        h10.write_isize(42);
319        assert_eq!(42, h10.finish())
320    }
321
322    #[cfg(debug_assertions)]
323    #[test]
324    #[should_panic]
325    fn u8_double_usage() {
326        let mut h = IntHasher::<u8>::default();
327        h.write_u8(42);
328        h.write_u8(43);
329    }
330
331    #[cfg(debug_assertions)]
332    #[test]
333    #[should_panic]
334    fn u16_double_usage() {
335        let mut h = IntHasher::<u16>::default();
336        h.write_u16(42);
337        h.write_u16(43);
338    }
339
340    #[cfg(debug_assertions)]
341    #[test]
342    #[should_panic]
343    fn u32_double_usage() {
344        let mut h = IntHasher::<u32>::default();
345        h.write_u32(42);
346        h.write_u32(43);
347    }
348
349    #[cfg(debug_assertions)]
350    #[test]
351    #[should_panic]
352    fn u64_double_usage() {
353        let mut h = IntHasher::<u64>::default();
354        h.write_u64(42);
355        h.write_u64(43);
356    }
357
358    #[cfg(debug_assertions)]
359    #[test]
360    #[should_panic]
361    fn usize_double_usage() {
362        let mut h = IntHasher::<usize>::default();
363        h.write_usize(42);
364        h.write_usize(43);
365    }
366
367    #[cfg(debug_assertions)]
368    #[test]
369    #[should_panic]
370    fn i8_double_usage() {
371        let mut h = IntHasher::<i8>::default();
372        h.write_i8(42);
373        h.write_i8(43);
374    }
375
376    #[cfg(debug_assertions)]
377    #[test]
378    #[should_panic]
379    fn i16_double_usage() {
380        let mut h = IntHasher::<i16>::default();
381        h.write_i16(42);
382        h.write_i16(43);
383    }
384
385    #[cfg(debug_assertions)]
386    #[test]
387    #[should_panic]
388    fn i32_double_usage() {
389        let mut h = IntHasher::<i32>::default();
390        h.write_i32(42);
391        h.write_i32(43);
392    }
393
394    #[cfg(debug_assertions)]
395    #[test]
396    #[should_panic]
397    fn i64_double_usage() {
398        let mut h = IntHasher::<i64>::default();
399        h.write_i64(42);
400        h.write_i64(43);
401    }
402
403    #[cfg(debug_assertions)]
404    #[test]
405    #[should_panic]
406    fn isize_double_usage() {
407        let mut h = IntHasher::<isize>::default();
408        h.write_isize(42);
409        h.write_isize(43);
410    }
411}
integer_hasher/lib.rs

integer_hasher/
lib.rs
