slvm/heap/
vm_hashmap.rs

1use crate::{GVm, Value};
2use bridge_types::BridgedType;
3use std::collections::HashMap;
4use std::collections::hash_map::Keys;
5use std::hash::{BuildHasher, Hash, Hasher};
6
7/**
8 * Provides a wrapper to allow us to build a hashmap with Value keys that hashes String and StringConst
9 * to the same hash.
10 * Note, this is public only to allow use of insert_id and remove_id which we need to work around
11 * borrowing issues.
12*/
13#[derive(Copy, Clone, Debug)]
14pub struct ValHash {
15    val: Value,
16    hash: u64,
17}
18
19impl ValHash {
20    /** Make a ValHash from a Value. */
21    pub fn from_value<ENV>(vm: &GVm<ENV>, val: Value) -> Self {
22        ValHash {
23            val,
24            hash: val.get_hash(vm),
25        }
26    }
27}
28
29impl PartialEq for ValHash {
30    fn eq(&self, other: &Self) -> bool {
31        self.hash == other.hash
32    }
33}
34
35impl Eq for ValHash {}
36
37impl Hash for ValHash {
38    fn hash<H: Hasher>(&self, state: &mut H) {
39        state.write_u64(self.hash);
40    }
41}
42
43#[derive(Copy, Clone, Debug, Default)]
44struct IdHasher {
45    hash: u64,
46}
47
48impl BuildHasher for IdHasher {
49    type Hasher = IdHasher;
50
51    fn build_hasher(&self) -> Self::Hasher {
52        *self
53    }
54}
55
56impl Hasher for IdHasher {
57    fn finish(&self) -> u64 {
58        self.hash
59    }
60
61    fn write(&mut self, _bytes: &[u8]) {
62        panic!("Invalid use of IdHasher!");
63    }
64
65    fn write_u64(&mut self, val: u64) {
66        self.hash = val;
67    }
68}
69
70/**
71 * Wrapper class for a HashMap<Value, Value>.  We need this because we want String and StringConst
72 * to hash to the same value (what a script user will expect) and that requires a VM so can not just
73 * implement Hash on Value (will not have access to a VM).
74 */
75#[derive(Clone, Debug)]
76pub struct VMHashMap {
77    map: HashMap<ValHash, Value, IdHasher>,
78}
79
80impl VMHashMap {
81    /** Create a new empty HashMap. */
82    pub fn new() -> Self {
83        VMHashMap {
84            map: HashMap::default(),
85        }
86    }
87
88    /** Create a new empty HashMap with an initial capacity. */
89    pub fn with_capacity(cap: usize) -> Self {
90        VMHashMap {
91            map: HashMap::with_capacity_and_hasher(cap, IdHasher::default()),
92        }
93    }
94
95    /** Get the value at key, requires the current VM for hashing. */
96    pub fn get<ENV>(&self, vm: &GVm<ENV>, key: Value) -> Option<Value> {
97        let id = ValHash::from_value(vm, key);
98        self.map.get(&id).copied()
99    }
100
101    /** Insert the value at key, requires the current VM for hashing.
102     * Returns the old value at key if it exists (None otherwise).
103     */
104    pub fn insert<ENV>(&mut self, vm: &GVm<ENV>, key: Value, val: Value) -> Option<Value> {
105        let id = ValHash::from_value(vm, key);
106        self.map.insert(id, val)
107    }
108
109    /** Insert val at the key id provided.  This allows calling code to pre-generate the ValHash.
110     * This is a borrow checker workaround.
111     */
112    pub fn insert_id(&mut self, id: ValHash, val: Value) -> Option<Value> {
113        self.map.insert(id, val)
114    }
115
116    /** Number of items in the HashMap. */
117    pub fn len(&self) -> usize {
118        self.map.len()
119    }
120
121    /** Is this HashMap empty? */
122    pub fn is_empty(&self) -> bool {
123        self.map.is_empty()
124    }
125
126    /** Does this HashMap contain key? */
127    pub fn contains_key<ENV>(&self, vm: &GVm<ENV>, key: Value) -> bool {
128        let id = ValHash::from_value(vm, key);
129        self.map.contains_key(&id)
130    }
131
132    /** Clear (remove all key/values) from the HashMap. */
133    pub fn clear(&mut self) {
134        self.map.clear();
135    }
136
137    /** Remove key from the HashMap.  Return the old value if it existed (None otherwise). */
138    pub fn remove<ENV>(&mut self, vm: &GVm<ENV>, key: Value) -> Option<Value> {
139        let id = ValHash::from_value(vm, key);
140        self.map.remove(&id)
141    }
142
143    /** Remove the key from HashMap (like remove) except caller pre-generates the ValHash.  Used to
144     * work around the borrow checker. */
145    pub fn remove_id(&mut self, id: ValHash) -> Option<Value> {
146        self.map.remove(&id)
147    }
148
149    /** Returns an iterator over all the keys in the HashMap. */
150    pub fn keys(&self) -> VMMapKeys {
151        VMMapKeys {
152            keys: self.map.keys(),
153        }
154    }
155
156    /** Return an iterator over all the (key, value) pairs in the HashMap. */
157    pub fn iter(&self) -> VMHashMapIter {
158        VMHashMapIter {
159            iter: self.map.iter(),
160        }
161    }
162}
163
164/// A [`VMHashMap`] that contains a [`BridgedType`] can be represented as a rust value.
165impl BridgedType for VMHashMap {}
166
167impl Default for VMHashMap {
168    fn default() -> Self {
169        Self::new()
170    }
171}
172
173/** Iterator over the key vals in a HashMap. */
174pub struct VMHashMapIter<'a> {
175    iter: std::collections::hash_map::Iter<'a, ValHash, Value>,
176}
177
178impl Iterator for VMHashMapIter<'_> {
179    type Item = (Value, Value);
180
181    fn next(&mut self) -> Option<Self::Item> {
182        self.iter.next().map(|(k, v)| (k.val, *v))
183    }
184}
185
186/** Iterator over the keys in a HashMap. */
187pub struct VMMapKeys<'a> {
188    keys: Keys<'a, ValHash, Value>,
189}
190
191impl Iterator for VMMapKeys<'_> {
192    type Item = Value;
193
194    fn next(&mut self) -> Option<Self::Item> {
195        self.keys.next().map(|v| v.val)
196    }
197}
198
199#[cfg(test)]
200mod tests {
201    use crate::vm_hashmap::VMHashMap;
202    use crate::{Value, Vm};
203
204    #[test]
205    fn test_map_str() {
206        let mut vm = Vm::new();
207        let mut m = VMHashMap::default();
208        let cs = Value::StringConst(vm.intern("Test String"));
209        let ds = vm.alloc_string("Test String".to_string());
210        let i: Value = 1.into();
211        m.insert(&mut vm, cs, i);
212        assert_eq!(m.get(&vm, cs).unwrap(), i);
213        assert_eq!(m.get(&vm, ds).unwrap(), i);
214        let i: Value = 10.into();
215        m.insert(&mut vm, ds, i);
216        assert_eq!(m.get(&vm, cs).unwrap(), i);
217        assert_eq!(m.get(&vm, ds).unwrap(), i);
218        let old = m.remove(&mut vm, cs).unwrap();
219        assert_eq!(old, i);
220        assert!(m.get(&vm, cs).is_none());
221        assert!(m.get(&vm, ds).is_none());
222    }
223
224    #[test]
225    fn test_map_sym_key_sanity() {
226        let mut vm = Vm::new();
227        let mut m = VMHashMap::default();
228        let sym = Value::Symbol(vm.intern("Test String"));
229        let key = Value::Keyword(vm.intern("Test String"));
230        let i: Value = 1.into();
231        m.insert(&mut vm, sym, i);
232        assert_eq!(m.get(&vm, sym).unwrap(), i);
233        assert!(m.get(&vm, key).is_none());
234        let i2: Value = 10.into();
235        m.insert(&mut vm, key, i2);
236        assert_eq!(m.get(&vm, sym).unwrap(), i);
237        assert_eq!(m.get(&vm, key).unwrap(), i2);
238        let old = m.remove(&mut vm, sym).unwrap();
239        assert_eq!(old, i);
240        assert!(m.get(&vm, sym).is_none());
241        assert_eq!(m.get(&vm, key).unwrap(), i2);
242    }
243
244    #[test]
245    fn test_map_key_iter_sanity() {
246        let mut vm = Vm::new();
247        let mut m = VMHashMap::default();
248        let key1 = Value::Keyword(vm.intern("one"));
249        let key2 = Value::Keyword(vm.intern("two"));
250        let key3 = Value::Keyword(vm.intern("three"));
251        assert_eq!(m.keys().count(), 0);
252        let i1: Value = 1.into();
253        m.insert(&mut vm, key1, i1);
254        let i2: Value = 1.into();
255        m.insert(&mut vm, key2, i2);
256        let i3: Value = 1.into();
257        m.insert(&mut vm, key3, i3);
258        assert_eq!(m.keys().count(), 3);
259        m.remove(&mut vm, key1);
260        assert_eq!(m.keys().count(), 2);
261    }
262
263    #[test]
264    fn test_map_iter_sanity() {
265        let mut vm = Vm::new();
266        let mut m = VMHashMap::default();
267        let key1 = Value::Keyword(vm.intern("one"));
268        let key2 = Value::Keyword(vm.intern("two"));
269        let key3 = Value::Keyword(vm.intern("three"));
270        assert_eq!(m.iter().count(), 0);
271        let i1: Value = 1.into();
272        m.insert(&mut vm, key1, i1);
273        let i2: Value = 1.into();
274        m.insert(&mut vm, key2, i2);
275        let i3: Value = 1.into();
276        m.insert(&mut vm, key3, i3);
277        assert_eq!(m.iter().count(), 3);
278        m.remove(&mut vm, key1);
279        assert_eq!(m.iter().count(), 2);
280    }
281}
slvm/heap/vm_hashmap.rs

slvm/heap/
vm_hashmap.rs
