1 //! `ScopedHashMap` 2 //! 3 //! This module defines a struct `ScopedHashMap<K, V>` which defines a `FxHashMap`-like 4 //! container that has a concept of scopes that can be entered and exited, such that 5 //! values inserted while inside a scope aren't visible outside the scope. 6 7 use crate::fx::FxHashMap; 8 use core::hash::Hash; 9 use core::mem; 10 11 #[cfg(not(feature = "std"))] 12 use crate::fx::FxHasher; 13 #[cfg(not(feature = "std"))] 14 type Hasher = core::hash::BuildHasherDefault<FxHasher>; 15 16 struct Val<K, V> { 17 value: V, 18 next_key: Option<K>, 19 depth: usize, 20 } 21 22 /// A view into an occupied entry in a `ScopedHashMap`. It is part of the `Entry` enum. 23 pub struct OccupiedEntry<'a, K: 'a, V: 'a> { 24 #[cfg(feature = "std")] 25 entry: super::hash_map::OccupiedEntry<'a, K, Val<K, V>>, 26 #[cfg(not(feature = "std"))] 27 entry: super::hash_map::OccupiedEntry<'a, K, Val<K, V>, Hasher>, 28 } 29 30 impl<'a, K, V> OccupiedEntry<'a, K, V> { 31 /// Gets a reference to the value in the entry. get(&self) -> &V32 pub fn get(&self) -> &V { 33 &self.entry.get().value 34 } 35 } 36 37 /// A view into a vacant entry in a `ScopedHashMap`. It is part of the `Entry` enum. 38 pub struct VacantEntry<'a, K: 'a, V: 'a> { 39 #[cfg(feature = "std")] 40 entry: super::hash_map::VacantEntry<'a, K, Val<K, V>>, 41 #[cfg(not(feature = "std"))] 42 entry: super::hash_map::VacantEntry<'a, K, Val<K, V>, Hasher>, 43 next_key: Option<K>, 44 depth: usize, 45 } 46 47 impl<'a, K: Hash, V> VacantEntry<'a, K, V> { 48 /// Sets the value of the entry with the `VacantEntry`'s key. insert(self, value: V)49 pub fn insert(self, value: V) { 50 self.entry.insert(Val { 51 value, 52 next_key: self.next_key, 53 depth: self.depth, 54 }); 55 } 56 } 57 58 /// A view into a single entry in a map, which may either be vacant or occupied. 59 /// 60 /// This enum is constructed from the `entry` method on `ScopedHashMap`. 61 pub enum Entry<'a, K: 'a, V: 'a> { 62 Occupied(OccupiedEntry<'a, K, V>), 63 Vacant(VacantEntry<'a, K, V>), 64 } 65 66 /// A wrapper around a `FxHashMap` which adds the concept of scopes. Items inserted 67 /// within a scope are removed when the scope is exited. 68 /// 69 /// Shadowing, where one scope has entries with the same keys as a containing scope, 70 /// is not supported in this implementation. 71 pub struct ScopedHashMap<K, V> { 72 map: FxHashMap<K, Val<K, V>>, 73 last_insert: Option<K>, 74 current_depth: usize, 75 } 76 77 impl<K, V> ScopedHashMap<K, V> 78 where 79 K: PartialEq + Eq + Hash + Clone, 80 { 81 /// Creates an empty `ScopedHashMap`. new() -> Self82 pub fn new() -> Self { 83 Self { 84 map: FxHashMap(), 85 last_insert: None, 86 current_depth: 0, 87 } 88 } 89 90 /// Similar to `FxHashMap::entry`, gets the given key's corresponding entry in the map for 91 /// in-place manipulation. entry(&mut self, key: K) -> Entry<K, V>92 pub fn entry(&mut self, key: K) -> Entry<K, V> { 93 use super::hash_map::Entry::*; 94 match self.map.entry(key) { 95 Occupied(entry) => Entry::Occupied(OccupiedEntry { entry }), 96 Vacant(entry) => { 97 let clone_key = entry.key().clone(); 98 Entry::Vacant(VacantEntry { 99 entry, 100 next_key: mem::replace(&mut self.last_insert, Some(clone_key)), 101 depth: self.current_depth, 102 }) 103 } 104 } 105 } 106 107 /// Enter a new scope. increment_depth(&mut self)108 pub fn increment_depth(&mut self) { 109 // Increment the depth. 110 self.current_depth = self.current_depth.checked_add(1).unwrap(); 111 } 112 113 /// Exit the current scope. decrement_depth(&mut self)114 pub fn decrement_depth(&mut self) { 115 // Remove all elements inserted at the current depth. 116 while let Some(key) = self.last_insert.clone() { 117 use crate::hash_map::Entry::*; 118 match self.map.entry(key) { 119 Occupied(entry) => { 120 if entry.get().depth != self.current_depth { 121 break; 122 } 123 self.last_insert = entry.remove_entry().1.next_key; 124 } 125 Vacant(_) => panic!(), 126 } 127 } 128 129 // Decrement the depth. 130 self.current_depth = self.current_depth.checked_sub(1).unwrap(); 131 } 132 } 133 134 #[cfg(test)] 135 mod tests { 136 use super::*; 137 138 #[test] basic()139 fn basic() { 140 let mut map: ScopedHashMap<i32, i32> = ScopedHashMap::new(); 141 142 match map.entry(0) { 143 Entry::Occupied(_entry) => panic!(), 144 Entry::Vacant(entry) => entry.insert(1), 145 } 146 match map.entry(2) { 147 Entry::Occupied(_entry) => panic!(), 148 Entry::Vacant(entry) => entry.insert(8), 149 } 150 match map.entry(2) { 151 Entry::Occupied(entry) => assert!(*entry.get() == 8), 152 Entry::Vacant(_entry) => panic!(), 153 } 154 map.increment_depth(); 155 match map.entry(2) { 156 Entry::Occupied(entry) => assert!(*entry.get() == 8), 157 Entry::Vacant(_entry) => panic!(), 158 } 159 match map.entry(1) { 160 Entry::Occupied(_entry) => panic!(), 161 Entry::Vacant(entry) => entry.insert(3), 162 } 163 match map.entry(1) { 164 Entry::Occupied(entry) => assert!(*entry.get() == 3), 165 Entry::Vacant(_entry) => panic!(), 166 } 167 match map.entry(0) { 168 Entry::Occupied(entry) => assert!(*entry.get() == 1), 169 Entry::Vacant(_entry) => panic!(), 170 } 171 match map.entry(2) { 172 Entry::Occupied(entry) => assert!(*entry.get() == 8), 173 Entry::Vacant(_entry) => panic!(), 174 } 175 map.decrement_depth(); 176 match map.entry(0) { 177 Entry::Occupied(entry) => assert!(*entry.get() == 1), 178 Entry::Vacant(_entry) => panic!(), 179 } 180 match map.entry(2) { 181 Entry::Occupied(entry) => assert!(*entry.get() == 8), 182 Entry::Vacant(_entry) => panic!(), 183 } 184 map.increment_depth(); 185 match map.entry(2) { 186 Entry::Occupied(entry) => assert!(*entry.get() == 8), 187 Entry::Vacant(_entry) => panic!(), 188 } 189 match map.entry(1) { 190 Entry::Occupied(_entry) => panic!(), 191 Entry::Vacant(entry) => entry.insert(4), 192 } 193 match map.entry(1) { 194 Entry::Occupied(entry) => assert!(*entry.get() == 4), 195 Entry::Vacant(_entry) => panic!(), 196 } 197 match map.entry(2) { 198 Entry::Occupied(entry) => assert!(*entry.get() == 8), 199 Entry::Vacant(_entry) => panic!(), 200 } 201 map.decrement_depth(); 202 map.increment_depth(); 203 map.increment_depth(); 204 map.increment_depth(); 205 match map.entry(2) { 206 Entry::Occupied(entry) => assert!(*entry.get() == 8), 207 Entry::Vacant(_entry) => panic!(), 208 } 209 match map.entry(1) { 210 Entry::Occupied(_entry) => panic!(), 211 Entry::Vacant(entry) => entry.insert(5), 212 } 213 match map.entry(1) { 214 Entry::Occupied(entry) => assert!(*entry.get() == 5), 215 Entry::Vacant(_entry) => panic!(), 216 } 217 match map.entry(2) { 218 Entry::Occupied(entry) => assert!(*entry.get() == 8), 219 Entry::Vacant(_entry) => panic!(), 220 } 221 map.decrement_depth(); 222 map.decrement_depth(); 223 map.decrement_depth(); 224 match map.entry(2) { 225 Entry::Occupied(entry) => assert!(*entry.get() == 8), 226 Entry::Vacant(_entry) => panic!(), 227 } 228 match map.entry(1) { 229 Entry::Occupied(_entry) => panic!(), 230 Entry::Vacant(entry) => entry.insert(3), 231 } 232 } 233 } 234