1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use std
::collections
::{HashMap, HashSet}
;
12 use std
::default::Default
;
13 use std
::hash
::{Hasher, Hash, BuildHasherDefault}
;
15 pub type FnvHashMap
<K
, V
> = HashMap
<K
, V
, BuildHasherDefault
<FnvHasher
>>;
16 pub type FnvHashSet
<V
> = HashSet
<V
, BuildHasherDefault
<FnvHasher
>>;
18 #[allow(non_snake_case)]
19 pub fn FnvHashMap
<K
: Hash
+ Eq
, V
>() -> FnvHashMap
<K
, V
> {
23 #[allow(non_snake_case)]
24 pub fn FnvHashSet
<V
: Hash
+ Eq
>() -> FnvHashSet
<V
> {
28 /// A speedy hash algorithm for node ids and def ids. The hashmap in
29 /// libcollections by default uses SipHash which isn't quite as speedy as we
30 /// want. In the compiler we're not really worried about DOS attempts, so we
31 /// just default to a non-cryptographic hash.
33 /// This uses FNV hashing, as described here:
34 /// http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
35 pub struct FnvHasher(u64);
37 impl Default
for FnvHasher
{
39 fn default() -> FnvHasher
{
40 FnvHasher(0xcbf29ce484222325)
44 impl Hasher
for FnvHasher
{
46 fn write(&mut self, bytes
: &[u8]) {
47 let FnvHasher(mut hash
) = *self;
49 hash
= hash ^
(*byte
as u64);
50 hash
= hash
.wrapping_mul(0x100000001b3);
52 *self = FnvHasher(hash
);
56 fn finish(&self) -> u64 {