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 use collections::{HashMap, HashSet};
14 use std::hash::{Hasher, Hash};
15 use std::io;
16 use syntax::ast;
17
18 pub type FnvHashMap<K, V> = HashMap<K, V, FnvHasher>;
19 pub type FnvHashSet<V> = HashSet<V, FnvHasher>;
20
21 pub type NodeMap<T> = FnvHashMap<ast::NodeId, T>;
22 pub type DefIdMap<T> = FnvHashMap<ast::DefId, T>;
23
24 pub type NodeSet = FnvHashSet<ast::NodeId>;
25 pub type DefIdSet = FnvHashSet<ast::DefId>;
26
27 // Hacks to get good names
28 pub mod FnvHashMap {
29 use std::hash::Hash;
30 use collections::HashMap;
31 pub fn new<K: Hash<super::FnvState> + TotalEq, V>() -> super::FnvHashMap<K, V> {
32 HashMap::with_hasher(super::FnvHasher)
33 }
34 }
35 pub mod FnvHashSet {
36 use std::hash::Hash;
37 use collections::HashSet;
38 pub fn new<V: Hash<super::FnvState> + TotalEq>() -> super::FnvHashSet<V> {
39 HashSet::with_hasher(super::FnvHasher)
40 }
41 }
42 pub mod NodeMap {
43 pub fn new<T>() -> super::NodeMap<T> {
44 super::FnvHashMap::new()
45 }
46 }
47 pub mod DefIdMap {
48 pub fn new<T>() -> super::DefIdMap<T> {
49 super::FnvHashMap::new()
50 }
51 }
52 pub mod NodeSet {
53 pub fn new() -> super::NodeSet {
54 super::FnvHashSet::new()
55 }
56 }
57 pub mod DefIdSet {
58 pub fn new() -> super::DefIdSet {
59 super::FnvHashSet::new()
60 }
61 }
62
63 /// A speedy hash algorithm for node ids and def ids. The hashmap in
64 /// libcollections by default uses SipHash which isn't quite as speedy as we
65 /// want. In the compiler we're not really worried about DOS attempts, so we
66 /// just default to a non-cryptographic hash.
67 ///
68 /// This uses FNV hashing, as described here:
69 /// http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
70 #[deriving(Clone)]
71 pub struct FnvHasher;
72
73 pub struct FnvState(u64);
74
75 impl Hasher<FnvState> for FnvHasher {
76 fn hash<T: Hash<FnvState>>(&self, t: &T) -> u64 {
77 let mut state = FnvState(0xcbf29ce484222325);
78 t.hash(&mut state);
79 let FnvState(ret) = state;
80 return ret;
81 }
82 }
83
84 impl Writer for FnvState {
85 fn write(&mut self, bytes: &[u8]) -> io::IoResult<()> {
86 let FnvState(mut hash) = *self;
87 for byte in bytes.iter() {
88 hash = hash ^ (*byte as u64);
89 hash = hash * 0x100000001b3;
90 }
91 *self = FnvState(hash);
92 Ok(())
93 }
94 }
librustc/util/nodemap.rs:58:4-58:4 -fn- definition:
pub fn new() -> super::DefIdSet {
super::FnvHashSet::new()
}
references:- 4librustc/middle/ty.rs:
1121: impl_vtables: RefCell::new(DefIdMap::new()),
1122: populated_external_types: RefCell::new(DefIdSet::new()),
1123: populated_external_traits: RefCell::new(DefIdSet::new()),
1124: upvar_borrow_map: RefCell::new(HashMap::new()),
librustc/middle/resolve.rs:
846: used_imports: HashSet::new(),
847: external_exports: DefIdSet::new(),
848: last_private: NodeMap::new(),
librustc/util/nodemap.rs:31:4-31:4 -fn- definition:
pub fn new<K: Hash<super::FnvState> + TotalEq, V>() -> super::FnvHashMap<K, V> {
HashMap::with_hasher(super::FnvHasher)
}
references:- 848: pub fn new<T>() -> super::DefIdMap<T> {
49: super::FnvHashMap::new()
50: }
librustc/middle/ty.rs:
1126: extern_const_variants: RefCell::new(DefIdMap::new()),
1127: method_map: RefCell::new(FnvHashMap::new()),
1128: vtable_map: RefCell::new(FnvHashMap::new()),
1129: dependency_formats: RefCell::new(HashMap::new()),
librustc/middle/resolve.rs:
824: method_map: RefCell::new(FnvHashMap::new()),
825: structs: HashSet::new(),
librustc/middle/typeck/check/mod.rs:
273: method_map: RefCell::new(FnvHashMap::new()),
274: vtable_map: RefCell::new(FnvHashMap::new()),
275: upvar_borrow_map: RefCell::new(HashMap::new()),
librustc/util/nodemap.rs:43:4-43:4 -fn- definition:
pub fn new<T>() -> super::NodeMap<T> {
super::FnvHashMap::new()
}
references:- 35librustc/middle/trans/context.rs:
librustc/middle/trans/base.rs:
librustc/middle/ty.rs:
librustc/middle/resolve.rs:
librustc/middle/resolve_lifetime.rs:
librustc/middle/typeck/check/mod.rs:
librustc/middle/dataflow.rs:
librustc/middle/liveness.rs:
librustc/middle/freevars.rs:
librustc/middle/region.rs:
librustc/middle/privacy.rs:
librustc/middle/cfg/construct.rs:
librustc/driver/driver.rs:
librustc/middle/resolve.rs:
librustc/util/nodemap.rs:53:4-53:4 -fn- definition:
pub fn new() -> super::NodeSet {
super::FnvHashSet::new()
}
references:- 8librustc/middle/trans/context.rs:
177: external_srcs: RefCell::new(NodeMap::new()),
178: non_inlineable_statics: RefCell::new(NodeSet::new()),
179: monomorphized: RefCell::new(HashMap::new()),
librustc/middle/ty.rs:
1119: used_unsafe: RefCell::new(NodeSet::new()),
1120: used_mut_nodes: RefCell::new(NodeSet::new()),
1121: impl_vtables: RefCell::new(DefIdMap::new()),
librustc/middle/freevars.rs:
98: let mut v = CollectFreevarsVisitor {
99: seen: NodeSet::new(),
100: refs: Vec::new(),
librustc/middle/privacy.rs:
1442: public_items: NodeSet::new(),
1443: reexports: NodeSet::new(),
1444: exp_map2: exp_map2,
librustc/middle/reachable.rs:
168: tcx: tcx,
169: reachable_symbols: NodeSet::new(),
170: worklist: Vec::new(),
librustc/util/nodemap.rs:21:50-21:50 -NK_AS_STR_TODO- definition:
pub type NodeMap<T> = FnvHashMap<ast::NodeId, T>;
pub type DefIdMap<T> = FnvHashMap<ast::DefId, T>;
pub type NodeSet = FnvHashSet<ast::NodeId>;
references:- 2647: pub mod DefIdMap {
48: pub fn new<T>() -> super::DefIdMap<T> {
49: super::FnvHashMap::new()
librustc/middle/trans/context.rs:
100: /// Cache of external const values
101: pub extern_const_values: RefCell<DefIdMap<ValueRef>>,
librustc/middle/ty.rs:
268: // A cache for the trait_methods() routine
269: pub trait_methods_cache: RefCell<DefIdMap<Rc<Vec<Rc<Method>>>>>,
--
1068: pub type type_cache = RefCell<DefIdMap<ty_param_bounds_and_ty>>;
--
3499: def_id: ast::DefId,
3500: map: &mut DefIdMap<V>,
3501: load_external: || -> V) -> V {
librustc/middle/typeck/mod.rs:
240: pub type impl_vtable_map = RefCell<DefIdMap<impl_res>>;
librustc/middle/const_eval.rs:
68: type constness_cache = DefIdMap<constness>;
librustc/middle/ty.rs:
309: // Maps a trait onto a list of impls of that trait.
310: pub trait_impls: RefCell<DefIdMap<Rc<RefCell<Vec<ast::DefId>>>>>,
librustc/util/nodemap.rs:23:1-23:1 -NK_AS_STR_TODO- definition:
pub type NodeSet = FnvHashSet<ast::NodeId>;
pub type DefIdSet = FnvHashSet<ast::DefId>;
// Hacks to get good names
references:- 1852: pub mod NodeSet {
53: pub fn new() -> super::NodeSet {
54: super::FnvHashSet::new()
librustc/middle/trans/context.rs:
77: /// that is generated
78: pub non_inlineable_statics: RefCell<NodeSet>,
79: /// Cache instances of monomorphized functions
--
133: link_meta: LinkMeta,
134: reachable: NodeSet)
135: -> CrateContext {
librustc/middle/ty.rs:
324: // present in this set can be warned about.
325: pub used_unsafe: RefCell<NodeSet>,
librustc/middle/freevars.rs:
43: struct CollectFreevarsVisitor<'a> {
44: seen: NodeSet,
45: refs: Vec<freevar_entry>,
librustc/middle/privacy.rs:
42: /// reexporting a public struct doesn't inline the doc).
43: pub type PublicItems = NodeSet;
--
155: // destination must also be exported.
156: reexports: NodeSet,
librustc/middle/reachable.rs:
349: exported_items: &privacy::ExportedItems)
350: -> NodeSet {
351: let mut reachable_context = ReachableContext::new(tcx);
librustc/middle/dead.rs:
405: exported_items: &privacy::ExportedItems,
406: reachable_symbols: &NodeSet,
407: krate: &ast::Crate) {
librustc/metadata/encoder.rs:
84: pub item_symbols: &'a RefCell<NodeMap<~str>>,
85: pub non_inlineable_statics: &'a RefCell<NodeSet>,
86: pub link_meta: &'a LinkMeta,
librustc/driver/driver.rs:
279: pub ty_cx: ty::ctxt,
280: pub reachable: NodeSet,
281: }
librustc/middle/ty.rs:
329: // about.
330: pub used_mut_nodes: RefCell<NodeSet>,
librustc/util/nodemap.rs:18:54-18:54 -NK_AS_STR_TODO- definition:
pub type FnvHashMap<K, V> = HashMap<K, V, FnvHasher>;
pub type FnvHashSet<V> = HashSet<V, FnvHasher>;
pub type NodeMap<T> = FnvHashMap<ast::NodeId, T>;
references:- 337: use collections::HashSet;
38: pub fn new<V: Hash<super::FnvState> + TotalEq>() -> super::FnvHashSet<V> {
39: HashSet::with_hasher(super::FnvHasher)
librustc/util/nodemap.rs:17:1-17:1 -NK_AS_STR_TODO- definition:
pub type FnvHashMap<K, V> = HashMap<K, V, FnvHasher>;
pub type FnvHashSet<V> = HashSet<V, FnvHasher>;
pub type NodeMap<T> = FnvHashMap<ast::NodeId, T>;
references:- 721: pub type NodeMap<T> = FnvHashMap<ast::NodeId, T>;
22: pub type DefIdMap<T> = FnvHashMap<ast::DefId, T>;
--
30: use collections::HashMap;
31: pub fn new<K: Hash<super::FnvState> + TotalEq, V>() -> super::FnvHashMap<K, V> {
32: HashMap::with_hasher(super::FnvHasher)
librustc/middle/ty.rs:
241: // quite often.
242: pub interner: RefCell<FnvHashMap<intern_key, Box<t_box_>>>,
243: pub next_id: Cell<uint>,
librustc/middle/typeck/mod.rs:
218: pub type vtable_map = RefCell<FnvHashMap<MethodCall, vtable_res>>;
librustc/middle/resolve.rs:
863: method_map: RefCell<FnvHashMap<(Name, DefId), ast::ExplicitSelf_>>,
864: structs: HashSet<DefId>,
librustc/util/nodemap.rs:48:4-48:4 -fn- definition:
pub fn new<T>() -> super::DefIdMap<T> {
super::FnvHashMap::new()
}
references:- 24librustc/middle/trans/context.rs:
184: const_values: RefCell::new(NodeMap::new()),
185: extern_const_values: RefCell::new(DefIdMap::new()),
186: impl_method_cache: RefCell::new(HashMap::new()),
librustc/middle/ty.rs:
1111: supertraits: RefCell::new(DefIdMap::new()),
1112: superstructs: RefCell::new(DefIdMap::new()),
1113: struct_fields: RefCell::new(DefIdMap::new()),
1114: destructor_for_type: RefCell::new(DefIdMap::new()),
1115: destructors: RefCell::new(DefIdSet::new()),
--
1117: inherent_impls: RefCell::new(DefIdMap::new()),
1118: impl_methods: RefCell::new(DefIdMap::new()),
1119: used_unsafe: RefCell::new(NodeSet::new()),
1120: used_mut_nodes: RefCell::new(NodeSet::new()),
1121: impl_vtables: RefCell::new(DefIdMap::new()),
1122: populated_external_types: RefCell::new(DefIdSet::new()),
--
1125: extern_const_statics: RefCell::new(DefIdMap::new()),
1126: extern_const_variants: RefCell::new(DefIdMap::new()),
1127: method_map: RefCell::new(FnvHashMap::new()),
librustc/middle/const_eval.rs:
275: tcx: tcx,
276: ccache: DefIdMap::new(),
277: };
librustc/middle/ty.rs:
1100: ast_ty_to_ty_cache: RefCell::new(NodeMap::new()),
1101: enum_var_cache: RefCell::new(DefIdMap::new()),
1102: methods: RefCell::new(DefIdMap::new()),
librustc/util/nodemap.rs:72:1-72:1 -struct- definition:
pub struct FnvState(u64);
impl Hasher<FnvState> for FnvHasher {
fn hash<T: Hash<FnvState>>(&self, t: &T) -> u64 {
references:- 575: impl Hasher<FnvState> for FnvHasher {
76: fn hash<T: Hash<FnvState>>(&self, t: &T) -> u64 {
--
84: impl Writer for FnvState {
85: fn write(&mut self, bytes: &[u8]) -> io::IoResult<()> {
librustc/util/nodemap.rs:70:19-70:19 -struct- definition:
pub struct FnvHasher;
pub struct FnvState(u64);
impl Hasher<FnvState> for FnvHasher {
references:- 569: /// http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
71: pub struct FnvHasher;
--
75: impl Hasher<FnvState> for FnvHasher {
76: fn hash<T: Hash<FnvState>>(&self, t: &T) -> u64 {
librustc/util/nodemap.rs:20:1-20:1 -NK_AS_STR_TODO- definition:
pub type NodeMap<T> = FnvHashMap<ast::NodeId, T>;
pub type DefIdMap<T> = FnvHashMap<ast::DefId, T>;
pub type NodeSet = FnvHashSet<ast::NodeId>;
references:- 44librustc/middle/trans/common.rs:
librustc/middle/trans/context.rs:
librustc/middle/ty.rs:
librustc/middle/resolve.rs:
librustc/middle/resolve_lifetime.rs:
librustc/middle/typeck/check/mod.rs:
librustc/middle/typeck/check/regionck.rs:
librustc/middle/dataflow.rs:
librustc/middle/mem_categorization.rs:
librustc/middle/liveness.rs:
librustc/middle/freevars.rs:
librustc/middle/region.rs:
librustc/middle/privacy.rs:
librustc/middle/cfg/mod.rs:
librustc/middle/cfg/construct.rs:
librustc/metadata/encoder.rs:
librustc/driver/session.rs:
librustc/middle/trans/expr.rs:
librustc/util/nodemap.rs:38:4-38:4 -fn- definition:
pub fn new<V: Hash<super::FnvState> + TotalEq>() -> super::FnvHashSet<V> {
HashSet::with_hasher(super::FnvHasher)
}
references:- 253: pub fn new() -> super::NodeSet {
54: super::FnvHashSet::new()
55: }
--
58: pub fn new() -> super::DefIdSet {
59: super::FnvHashSet::new()
60: }
librustc/util/nodemap.rs:24:44-24:44 -NK_AS_STR_TODO- definition:
pub type NodeSet = FnvHashSet<ast::NodeId>;
pub type DefIdSet = FnvHashSet<ast::DefId>;
// Hacks to get good names
references:- 557: pub mod DefIdSet {
58: pub fn new() -> super::DefIdSet {
59: super::FnvHashSet::new()
librustc/middle/ty.rs:
306: // A method will be in this list if and only if it is a destructor.
307: pub destructors: RefCell<DefIdSet>,
--
336: // This is used for lazy resolution of methods.
337: pub populated_external_types: RefCell<DefIdSet>,
librustc/middle/resolve.rs:
65: // not contain any entries from local crates.
66: pub type ExternalExports = DefIdSet;
librustc/middle/ty.rs:
340: // is used for lazy resolution of traits.
341: pub populated_external_traits: RefCell<DefIdSet>,