src/librustc_data_structures/interner.rs

   1 // Copyright 2018 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 use std::hash::Hash;
  12 use std::hash::BuildHasher;
  13 use std::hash::Hasher;
  14 use std::collections::HashMap;
  15 use std::collections::hash_map::RawEntryMut;
  16 use std::borrow::Borrow;
  17
  18 pub trait HashInterner<K: Eq + Hash> {
  19     fn intern_ref<Q: ?Sized, F: FnOnce() -> K>(&mut self, value: &Q, make: F) -> K
  20         where K: Borrow<Q>,
  21               Q: Hash + Eq;
  22
  23     fn intern<Q, F: FnOnce(Q) -> K>(&mut self, value: Q, make: F) -> K
  24         where K: Borrow<Q>,
  25               Q: Hash + Eq;
  26 }
  27
  28 impl<K: Eq + Hash + Copy, S: BuildHasher> HashInterner<K> for HashMap<K, (), S> {
  29     #[inline]
  30     fn intern_ref<Q: ?Sized, F: FnOnce() -> K>(&mut self, value: &Q, make: F) -> K
  31         where K: Borrow<Q>,
  32               Q: Hash + Eq
  33     {
  34         let mut hasher = self.hasher().build_hasher();
  35         value.hash(&mut hasher);
  36         let hash = hasher.finish();
  37         let entry = self.raw_entry_mut().from_key_hashed_nocheck(hash, value);
  38
  39         match entry {
  40             RawEntryMut::Occupied(e) => *e.key(),
  41             RawEntryMut::Vacant(e) => {
  42                 let v = make();
  43                 e.insert_hashed_nocheck(hash, v, ());
  44                 v
  45             }
  46         }
  47     }
  48
  49     #[inline]
  50     fn intern<Q, F: FnOnce(Q) -> K>(&mut self, value: Q, make: F) -> K
  51         where K: Borrow<Q>,
  52               Q: Hash + Eq
  53     {
  54         let mut hasher = self.hasher().build_hasher();
  55         value.hash(&mut hasher);
  56         let hash = hasher.finish();
  57         let entry = self.raw_entry_mut().from_key_hashed_nocheck(hash, &value);
  58
  59         match entry {
  60             RawEntryMut::Occupied(e) => *e.key(),
  61             RawEntryMut::Vacant(e) => {
  62                 let v = make(value);
  63                 e.insert_hashed_nocheck(hash, v, ());
  64                 v
  65             }
  66         }
  67     }
  68 }