compiler/rustc_data_structures/src/mini_map.rs

   1 use crate::fx::FxHashMap;
   2 use arrayvec::ArrayVec;
   3
   4 use std::hash::Hash;
   5
   6 /// Small-storage-optimized implementation of a map
   7 /// made specifically for caching results.
   8 ///
   9 /// Stores elements in a small array up to a certain length
  10 /// and switches to `HashMap` when that length is exceeded.
  11 pub enum MiniMap<K, V> {
  12     Array(ArrayVec<[(K, V); 8]>),
  13     Map(FxHashMap<K, V>),
  14 }
  15
  16 impl<K: Eq + Hash, V> MiniMap<K, V> {
  17     /// Creates an empty `MiniMap`.
  18     pub fn new() -> Self {
  19         MiniMap::Array(ArrayVec::new())
  20     }
  21
  22     /// Inserts or updates value in the map.
  23     pub fn insert(&mut self, key: K, value: V) {
  24         match self {
  25             MiniMap::Array(array) => {
  26                 for pair in array.iter_mut() {
  27                     if pair.0 == key {
  28                         pair.1 = value;
  29                         return;
  30                     }
  31                 }
  32                 if let Err(error) = array.try_push((key, value)) {
  33                     let mut map: FxHashMap<K, V> = array.drain(..).collect();
  34                     let (key, value) = error.element();
  35                     map.insert(key, value);
  36                     *self = MiniMap::Map(map);
  37                 }
  38             }
  39             MiniMap::Map(map) => {
  40                 map.insert(key, value);
  41             }
  42         }
  43     }
  44
  45     /// Return value by key if any.
  46     pub fn get(&self, key: &K) -> Option<&V> {
  47         match self {
  48             MiniMap::Array(array) => {
  49                 for pair in array {
  50                     if pair.0 == *key {
  51                         return Some(&pair.1);
  52                     }
  53                 }
  54                 return None;
  55             }
  56             MiniMap::Map(map) => {
  57                 return map.get(key);
  58             }
  59         }
  60     }
  61 }