phf_shared/
lib.rs

1#![doc(html_root_url = "https://docs.rs/phf_shared/0.7")]
2#![cfg_attr(not(feature = "std"), no_std)]
3
4#[cfg(feature = "std")]
5extern crate std as core;
6
7extern crate siphasher;
8
9#[cfg(feature = "unicase")]
10extern crate unicase;
11
12use core::fmt;
13use core::hash::{Hasher, Hash};
14use core::num::Wrapping;
15use siphasher::sip128::{Hash128, Hasher128, SipHasher13};
16
17pub struct Hashes {
18    pub g: u32,
19    pub f1: u32,
20    pub f2: u32,
21    _priv: (),
22}
23
24/// A central typedef for hash keys
25///
26/// Makes experimentation easier by only needing to be updated here.
27pub type HashKey = u64;
28
29#[inline]
30pub fn displace(f1: u32, f2: u32, d1: u32, d2: u32) -> u32 {
31    (Wrapping(d2) + Wrapping(f1) * Wrapping(d1) + Wrapping(f2)).0
32}
33
34/// `key` is from `phf_generator::HashState`.
35#[inline]
36pub fn hash<T: ?Sized + PhfHash>(x: &T, key: &HashKey) -> Hashes {
37    let mut hasher = SipHasher13::new_with_keys(0, *key);
38    x.phf_hash(&mut hasher);
39
40    let Hash128 { h1: lower, h2: upper} = hasher.finish128();
41
42    Hashes {
43        g: (lower >> 32) as u32,
44        f1: lower as u32,
45        f2: upper as u32,
46        _priv: (),
47    }
48}
49
50/// Return an index into `phf_generator::HashState::map`.
51///
52/// * `hash` is from `hash()` in this crate.
53/// * `disps` is from `phf_generator::HashState::disps`.
54/// * `len` is the length of `phf_generator::HashState::map`.
55#[inline]
56pub fn get_index(hashes: &Hashes, disps: &[(u32, u32)], len: usize) -> u32 {
57    let (d1, d2) = disps[(hashes.g % (disps.len() as u32)) as usize];
58    displace(hashes.f1, hashes.f2, d1, d2) % (len as u32)
59}
60
61/// A trait implemented by types which can be used in PHF data structures.
62///
63/// This differs from the standard library's `Hash` trait in that `PhfHash`'s
64/// results must be architecture independent so that hashes will be consistent
65/// between the host and target when cross compiling.
66pub trait PhfHash {
67    /// Feeds the value into the state given, updating the hasher as necessary.
68    fn phf_hash<H: Hasher>(&self, state: &mut H);
69
70    /// Feeds a slice of this type into the state provided.
71    fn phf_hash_slice<H: Hasher>(data: &[Self], state: &mut H)
72        where Self: Sized
73    {
74        for piece in data {
75            piece.phf_hash(state);
76        }
77    }
78}
79
80/// Trait for printing types with `const` constructors, used by `phf_codegen` and `phf_macros`.
81pub trait FmtConst {
82    /// Print a `const` expression representing this value.
83    fn fmt_const(&self, f: &mut fmt::Formatter) -> fmt::Result;
84}
85
86/// Create an impl of `FmtConst` delegating to `fmt::Debug` for types that can deal with it.
87///
88/// Ideally with specialization this could be just one default impl and then specialized where
89/// it doesn't apply.
90macro_rules! delegate_debug (
91    ($ty:ty) => {
92        impl FmtConst for $ty {
93            fn fmt_const(&self, f: &mut fmt::Formatter) -> fmt::Result {
94                write!(f, "{:?}", self)
95            }
96        }
97    }
98);
99
100delegate_debug!(str);
101delegate_debug!(char);
102delegate_debug!(u8);
103delegate_debug!(i8);
104delegate_debug!(u16);
105delegate_debug!(i16);
106delegate_debug!(u32);
107delegate_debug!(i32);
108delegate_debug!(u64);
109delegate_debug!(i64);
110delegate_debug!(u128);
111delegate_debug!(i128);
112delegate_debug!(bool);
113
114#[cfg(feature = "std")]
115impl PhfHash for String {
116    #[inline]
117    fn phf_hash<H: Hasher>(&self, state: &mut H) {
118        (**self).phf_hash(state)
119    }
120}
121
122#[cfg(feature = "std")]
123impl PhfHash for Vec<u8> {
124    #[inline]
125    fn phf_hash<H: Hasher>(&self, state: &mut H) {
126        (**self).phf_hash(state)
127    }
128}
129
130impl<'a, T: 'a + PhfHash + ?Sized> PhfHash for &'a T {
131    fn phf_hash<H: Hasher>(&self, state: &mut H) {
132        (*self).phf_hash(state)
133    }
134}
135
136impl<'a, T: 'a + FmtConst + ?Sized> FmtConst for &'a T {
137    fn fmt_const(&self, f: &mut fmt::Formatter) -> fmt::Result {
138        (*self).fmt_const(f)
139    }
140}
141
142impl PhfHash for str {
143    #[inline]
144    fn phf_hash<H: Hasher>(&self, state: &mut H) {
145        self.as_bytes().phf_hash(state)
146    }
147}
148
149impl PhfHash for [u8] {
150    #[inline]
151    fn phf_hash<H: Hasher>(&self, state: &mut H) {
152        state.write(self);
153    }
154}
155
156impl FmtConst for [u8] {
157    #[inline]
158    fn fmt_const(&self, f: &mut fmt::Formatter) -> fmt::Result {
159        // slices need a leading reference
160        write!(f, "&{:?}", self)
161    }
162}
163
164#[cfg(feature = "unicase")]
165impl<S> PhfHash for unicase::UniCase<S>
166    where unicase::UniCase<S>: Hash {
167    #[inline]
168    fn phf_hash<H: Hasher>(&self, state: &mut H) {
169        self.hash(state)
170    }
171}
172
173#[cfg(feature = "unicase")]
174impl<S> FmtConst for unicase::UniCase<S> where S: AsRef<str> {
175    fn fmt_const(&self, f: &mut fmt::Formatter) -> fmt::Result {
176        if self.is_ascii() {
177            f.write_str("UniCase::ascii(")?;
178        } else {
179            f.write_str("UniCase::unicode(")?;
180        }
181
182        self.as_ref().fmt_const(f)?;
183        f.write_str(")")
184    }
185}
186
187macro_rules! sip_impl (
188    (le $t:ty) => (
189        impl PhfHash for $t {
190            #[inline]
191            fn phf_hash<H: Hasher>(&self, state: &mut H) {
192                self.to_le().hash(state);
193            }
194        }
195    );
196    ($t:ty) => (
197        impl PhfHash for $t {
198            #[inline]
199            fn phf_hash<H: Hasher>(&self, state: &mut H) {
200                self.hash(state);
201            }
202        }
203    )
204);
205
206sip_impl!(u8);
207sip_impl!(i8);
208sip_impl!(le u16);
209sip_impl!(le i16);
210sip_impl!(le u32);
211sip_impl!(le i32);
212sip_impl!(le u64);
213sip_impl!(le i64);
214sip_impl!(le u128);
215sip_impl!(le i128);
216sip_impl!(bool);
217
218impl PhfHash for char {
219    #[inline]
220    fn phf_hash<H: Hasher>(&self, state: &mut H) {
221        (*self as u32).phf_hash(state)
222    }
223}
224
225// minimize duplicated code since formatting drags in quite a bit
226fn fmt_array(array: &[u8], f: &mut fmt::Formatter) -> fmt::Result {
227    write!(f, "{:?}", array)
228}
229
230macro_rules! array_impl (
231    ($t:ty, $n:expr) => (
232        impl PhfHash for [$t; $n] {
233            #[inline]
234            fn phf_hash<H: Hasher>(&self, state: &mut H) {
235                state.write(self);
236            }
237        }
238
239        impl FmtConst for [$t; $n] {
240            fn fmt_const(&self, f: &mut fmt::Formatter) -> fmt::Result {
241                fmt_array(self, f)
242            }
243        }
244    )
245);
246
247array_impl!(u8, 1);
248array_impl!(u8, 2);
249array_impl!(u8, 3);
250array_impl!(u8, 4);
251array_impl!(u8, 5);
252array_impl!(u8, 6);
253array_impl!(u8, 7);
254array_impl!(u8, 8);
255array_impl!(u8, 9);
256array_impl!(u8, 10);
257array_impl!(u8, 11);
258array_impl!(u8, 12);
259array_impl!(u8, 13);
260array_impl!(u8, 14);
261array_impl!(u8, 15);
262array_impl!(u8, 16);
263array_impl!(u8, 17);
264array_impl!(u8, 18);
265array_impl!(u8, 19);
266array_impl!(u8, 20);
267array_impl!(u8, 21);
268array_impl!(u8, 22);
269array_impl!(u8, 23);
270array_impl!(u8, 24);
271array_impl!(u8, 25);
272array_impl!(u8, 26);
273array_impl!(u8, 27);
274array_impl!(u8, 28);
275array_impl!(u8, 29);
276array_impl!(u8, 30);
277array_impl!(u8, 31);
278array_impl!(u8, 32);