Use raw_entry for more efficient interning

2 files changed, 70 insertions, 0 deletions

diff --git a/src/librustc_data_structures/interner.rs b/src/librustc_data_structures/interner.rs
new file mode 100644
index 00000000000..29e5aefee7f
--- /dev/null
+++ b/src/librustc_data_structures/interner.rs
@@ -0,0 +1,68 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use std::hash::Hash;
+use std::hash::BuildHasher;
+use std::hash::Hasher;
+use std::collections::HashMap;
+use std::collections::hash_map::RawEntryMut;
+use std::borrow::Borrow;
+
+pub trait HashInterner<K: Eq + Hash> {
+    fn intern_ref<Q: ?Sized, F: FnOnce() -> K>(&mut self, value: &Q, make: F) -> K
+        where K: Borrow<Q>,
+              Q: Hash + Eq;
+
+    fn intern<Q, F: FnOnce(Q) -> K>(&mut self, value: Q, make: F) -> K
+        where K: Borrow<Q>,
+              Q: Hash + Eq;
+}
+
+impl<K: Eq + Hash + Copy, S: BuildHasher> HashInterner<K> for HashMap<K, (), S> {
+    #[inline]
+    fn intern_ref<Q: ?Sized, F: FnOnce() -> K>(&mut self, value: &Q, make: F) -> K
+        where K: Borrow<Q>,
+              Q: Hash + Eq
+    {
+        let mut hasher = self.hasher().build_hasher();
+        value.hash(&mut hasher);
+        let hash = hasher.finish();
+        let entry = self.raw_entry_mut().from_key_hashed_nocheck(hash, value);
+
+        match entry {
+            RawEntryMut::Occupied(e) => *e.key(),
+            RawEntryMut::Vacant(e) => {
+                let v = make();
+                e.insert_hashed_nocheck(hash, v, ());
+                v
+            }
+        }
+    }
+
+    #[inline]
+    fn intern<Q, F: FnOnce(Q) -> K>(&mut self, value: Q, make: F) -> K
+        where K: Borrow<Q>,
+              Q: Hash + Eq
+    {
+        let mut hasher = self.hasher().build_hasher();
+        value.hash(&mut hasher);
+        let hash = hasher.finish();
+        let entry = self.raw_entry_mut().from_key_hashed_nocheck(hash, &value);
+
+        match entry {
+            RawEntryMut::Occupied(e) => *e.key(),
+            RawEntryMut::Vacant(e) => {
+                let v = make(value);
+                e.insert_hashed_nocheck(hash, v, ());
+                v
+            }
+        }
+    }
+}
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 135abebdacb..96cb235a933 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -29,6 +29,7 @@
 #![feature(nll)]
 #![feature(allow_internal_unstable)]
 #![feature(vec_resize_with)]
+#![feature(hash_raw_entry)]
 
 #![cfg_attr(unix, feature(libc))]
 #![cfg_attr(test, feature(test))]
@@ -66,6 +67,7 @@ pub mod flock;
 pub mod fx;
 pub mod graph;
 pub mod indexed_vec;
+pub mod interner;
 pub mod obligation_forest;
 pub mod owning_ref;
 pub mod ptr_key;