src/librustc/util/nodemap.rs

   1 // Copyright 2014 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.
   4 //
   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.
  10
  11 //! An efficient hash map for node IDs
  12
  13 #![allow(non_snake_case)]
  14
  15 use std::collections::{HashMap, HashSet};
  16 use std::hash::{Hasher, Hash, Writer};
  17 use syntax::ast;
  18
  19 pub type FnvHashMap<K, V> = HashMap<K, V, FnvHasher>;
  20 pub type FnvHashSet<V> = HashSet<V, FnvHasher>;
  21
  22 pub type NodeMap<T> = FnvHashMap<ast::NodeId, T>;
  23 pub type DefIdMap<T> = FnvHashMap<ast::DefId, T>;
  24
  25 pub type NodeSet = FnvHashSet<ast::NodeId>;
  26 pub type DefIdSet = FnvHashSet<ast::DefId>;
  27
  28 // Hacks to get good names
  29 pub mod FnvHashMap {
  30     use std::hash::Hash;
  31     use std::collections::HashMap;
  32     pub fn new<K: Hash<super::FnvState> + Eq, V>() -> super::FnvHashMap<K, V> {
  33         HashMap::with_hasher(super::FnvHasher)
  34     }
  35 }
  36 pub mod FnvHashSet {
  37     use std::hash::Hash;
  38     use std::collections::HashSet;
  39     pub fn new<V: Hash<super::FnvState> + Eq>() -> super::FnvHashSet<V> {
  40         HashSet::with_hasher(super::FnvHasher)
  41     }
  42 }
  43 pub mod NodeMap {
  44     pub fn new<T>() -> super::NodeMap<T> {
  45         super::FnvHashMap::new()
  46     }
  47 }
  48 pub mod DefIdMap {
  49     pub fn new<T>() -> super::DefIdMap<T> {
  50         super::FnvHashMap::new()
  51     }
  52 }
  53 pub mod NodeSet {
  54     pub fn new() -> super::NodeSet {
  55         super::FnvHashSet::new()
  56     }
  57 }
  58 pub mod DefIdSet {
  59     pub fn new() -> super::DefIdSet {
  60         super::FnvHashSet::new()
  61     }
  62 }
  63
  64 /// A speedy hash algorithm for node ids and def ids. The hashmap in
  65 /// libcollections by default uses SipHash which isn't quite as speedy as we
  66 /// want. In the compiler we're not really worried about DOS attempts, so we
  67 /// just default to a non-cryptographic hash.
  68 ///
  69 /// This uses FNV hashing, as described here:
  70 /// http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
  71 #[deriving(Clone, Copy, Default)]
  72 pub struct FnvHasher;
  73
  74 #[allow(missing_copy_implementations)]
  75 pub struct FnvState(u64);
  76
  77 impl Hasher<FnvState> for FnvHasher {
  78     fn hash<Sized? T: Hash<FnvState>>(&self, t: &T) -> u64 {
  79         let mut state = FnvState(0xcbf29ce484222325);
  80         t.hash(&mut state);
  81         let FnvState(ret) = state;
  82         return ret;
  83     }
  84 }
  85
  86 impl Writer for FnvState {
  87     fn write(&mut self, bytes: &[u8]) {
  88         let FnvState(mut hash) = *self;
  89         for byte in bytes.iter() {
  90             hash = hash ^ (*byte as u64);
  91             hash = hash * 0x100000001b3;
  92         }
  93         *self = FnvState(hash);
  94     }
  95 }