netsblox_vm/
vecmap.rs

1//! A map type implemented as a sorted list of key/value pairs.
2//! 
3//! For a small numbers of smallish elements, this is faster than other associative structures like `BTreeMap` and `HashMap`.
4//! Because of this, it is used as the collection type for symbol tables in the vm.
5//! 
6//! As a general benchmark, it was found that the break even point for a worst case scenario with
7//! `String` keys and `16`-byte values (as the vm uses) was over 80 elements, vastly more than we expect to have in practice.
8//! Additionally, that was only for insertion; actual lookup time was around 2x faster (compared to `BTreeMap` as was used previously).
9
10use alloc::vec::Vec;
11use alloc::borrow::Borrow;
12
13#[cfg(feature = "serde")]
14use serde::{Serialize, Deserialize};
15
16use crate::gc::*;
17
18#[derive(Collect, Debug)]
19#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
20#[collect(no_drop, bound = "where V: Collect")]
21pub struct Entry<K: Ord + 'static, V> {
22    #[collect(require_static)] pub key: K,
23                               pub value: V,
24}
25/// A map type implemented as a list of key/value pairs.
26/// 
27/// If the const generic `SORTED` is set to `true`, keys will be sorted in ascending order, lookups are `O(log(n))`, and insertions are `O(n)`.
28/// If `SORTED` is set to `false`, keys will be sorted in insertion order, lookups are `O(n)`, and insertions are `O(1)`.
29#[derive(Collect, Debug)]
30#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
31#[collect(no_drop, bound = "where V: Collect")]
32pub struct VecMap<K: Ord + 'static, V, const SORTED: bool> {
33    values: Vec<Entry<K, V>>,
34}
35impl<K: Ord + 'static, V, const SORTED: bool> VecMap<K, V, SORTED> {
36    /// Creates a new, empty map.
37    pub fn new() -> Self {
38        Self { values: vec![] }
39    }
40    /// Creates a new, empty map with the specified capacity.
41    pub fn with_capacity(cap: usize) -> Self {
42        Self { values: Vec::with_capacity(cap) }
43    }
44    /// Gets an immutable reference to a stored value, if it exists.
45    pub fn get<Q: ?Sized + Ord>(&self, key: &Q) -> Option<&V> where K: Borrow<Q> {
46        match SORTED {
47            true => self.values.binary_search_by(|x| x.key.borrow().cmp(key)).ok().map(|i| &self.values[i].value),
48            false => self.values.iter().find(|x| x.key.borrow() == key).map(|x| &x.value),
49        }
50    }
51    /// Gets a mutable reference to a stored value, if it exists.
52    pub fn get_mut<Q: ?Sized + Ord>(&mut self, key: &Q) -> Option<&mut V> where K: Borrow<Q> {
53        match SORTED {
54            true => self.values.binary_search_by(|x| x.key.borrow().cmp(key)).ok().map(|i| &mut self.values[i].value),
55            false => self.values.iter_mut().find(|x| x.key.borrow() == key).map(|x| &mut x.value),
56        }
57    }
58    /// Inserts a new value into the map.
59    /// If an entry with the same key already exists, the previous value is returned.
60    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
61        match SORTED {
62            true => match self.values.binary_search_by(|x| x.key.cmp(&key)) {
63                Ok(i) => Some(core::mem::replace(&mut self.values[i].value, value)),
64                Err(i) => {
65                    self.values.insert(i, Entry { key, value });
66                    None
67                }
68            }
69            false => match self.get_mut(&key) {
70                Some(x) => Some(core::mem::replace(x, value)),
71                None => {
72                    self.values.push(Entry { key, value });
73                    None
74                }
75            }
76        }
77    }
78    /// Gets the number of values stored in the map.
79    pub fn len(&self) -> usize {
80        self.values.len()
81    }
82    /// Checks if the map is currently empty (no values).
83    pub fn is_empty(&self) -> bool {
84        self.values.is_empty()
85    }
86    /// Iterates through the map.
87    pub fn iter(&self) -> Iter<K, V> {
88        Iter(self.values.iter())
89    }
90    /// Iterates through the map.
91    pub fn iter_mut(&mut self) -> IterMut<K, V> {
92        IterMut(self.values.iter_mut())
93    }
94    /// Gets a raw slice of the entries stored in the map.
95    pub fn as_slice(&self) -> &[Entry<K, V>] {
96        self.values.as_slice()
97    }
98}
99
100impl<K: Ord + 'static, V, const SORTED: bool> Default for VecMap<K, V, SORTED> {
101    fn default() -> Self {
102        Self::new()
103    }
104}
105
106impl<K: Ord + 'static, V, const SORTED: bool> IntoIterator for VecMap<K, V, SORTED> {
107    type Item = (K, V);
108    type IntoIter = IntoIter<K, V>;
109    fn into_iter(self) -> Self::IntoIter {
110        IntoIter(self.values.into_iter())
111    }
112}
113
114pub struct IntoIter<K: Ord + 'static, V>(alloc::vec::IntoIter<Entry<K, V>>);
115impl<K: Ord + 'static, V> Iterator for IntoIter<K, V> {
116    type Item = (K, V);
117    fn next(&mut self) -> Option<Self::Item> {
118        self.0.next().map(|x| (x.key, x.value))
119    }
120}
121
122pub struct Iter<'a, K: Ord + 'static, V>(core::slice::Iter<'a, Entry<K, V>>);
123impl<'a, K: Ord + 'static, V> Iterator for Iter<'a, K, V> {
124    type Item = (&'a K, &'a V);
125    fn next(&mut self) -> Option<Self::Item> {
126        self.0.next().map(|x| (&x.key, &x.value))
127    }
128}
129
130pub struct IterMut<'a, K: Ord + 'static, V>(core::slice::IterMut<'a, Entry<K, V>>);
131impl<'a, K: Ord + 'static, V> Iterator for IterMut<'a, K, V> {
132    type Item = (&'a K, &'a mut V);
133    fn next(&mut self) -> Option<Self::Item> {
134        self.0.next().map(|x| (&x.key, &mut x.value))
135    }
136}
137
138impl<K: Ord + 'static, V, const SORTED: bool> FromIterator<(K, V)> for VecMap<K, V, SORTED> {
139    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
140        let mut res = VecMap::<K, V, SORTED>::new();
141        for (k, v) in iter {
142            res.insert(k, v);
143        }
144        res
145    }
146}
147
148#[test]
149fn test_vecmap_sorted() {
150    let mut v = VecMap::<usize, usize, true>::new();
151    assert_eq!(v.len(), 0);
152    assert_eq!(v.as_slice().len(), 0);
153    assert_eq!(v.is_empty(), true);
154    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), []);
155
156    assert_eq!(v.insert(45, 12), None);
157    assert_eq!(v.len(), 1);
158    assert_eq!(v.as_slice().len(), 1);
159    assert_eq!(v.is_empty(), false);
160    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 12)]);
161
162    assert_eq!(v.insert(56, 6), None);
163    assert_eq!(v.len(), 2);
164    assert_eq!(v.as_slice().len(), 2);
165    assert_eq!(v.is_empty(), false);
166    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 12), (56, 6)]);
167
168    assert_eq!(v.insert(80, 3), None);
169    assert_eq!(v.len(), 3);
170    assert_eq!(v.as_slice().len(), 3);
171    assert_eq!(v.is_empty(), false);
172    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 12), (56, 6), (80, 3)]);
173
174    assert_eq!(v.insert(2, 654), None);
175    assert_eq!(v.len(), 4);
176    assert_eq!(v.as_slice().len(), 4);
177    assert_eq!(v.is_empty(), false);
178    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(2, 654), (45, 12), (56, 6), (80, 3)]);
179
180    assert_eq!(v.insert(56, 98), Some(6));
181    assert_eq!(v.len(), 4);
182    assert_eq!(v.as_slice().len(), 4);
183    assert_eq!(v.is_empty(), false);
184    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(2, 654), (45, 12), (56, 98), (80, 3)]);
185
186    *v.get_mut(&80).unwrap() = 13;
187    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(2, 654), (45, 12), (56, 98), (80, 13)]);
188    *v.get_mut(&45).unwrap() = 444;
189    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(2, 654), (45, 444), (56, 98), (80, 13)]);
190
191    assert_eq!(v.get_mut(&2).map(|x| *x), Some(654));
192    assert_eq!(v.get_mut(&45).map(|x| *x), Some(444));
193    assert_eq!(v.get_mut(&56).map(|x| *x), Some(98));
194    assert_eq!(v.get_mut(&80).map(|x| *x), Some(13));
195    assert_eq!(v.get_mut(&81).map(|x| *x), None);
196    assert_eq!(v.get_mut(&69).map(|x| *x), None);
197    assert_eq!(v.get_mut(&0).map(|x| *x), None);
198    assert_eq!(v.get_mut(&21).map(|x| *x), None);
199    assert_eq!(v.get_mut(&50).map(|x| *x), None);
200
201    assert_eq!(v.get(&2).map(|x| *x), Some(654));
202    assert_eq!(v.get(&45).map(|x| *x), Some(444));
203    assert_eq!(v.get(&56).map(|x| *x), Some(98));
204    assert_eq!(v.get(&80).map(|x| *x), Some(13));
205    assert_eq!(v.get(&81).map(|x| *x), None);
206    assert_eq!(v.get(&69).map(|x| *x), None);
207    assert_eq!(v.get(&0).map(|x| *x), None);
208    assert_eq!(v.get(&21).map(|x| *x), None);
209    assert_eq!(v.get(&50).map(|x| *x), None);
210
211    assert_eq!(v.insert(50, 3), None);
212    assert_eq!(v.len(), 5);
213    assert_eq!(v.as_slice().len(), 5);
214    assert_eq!(v.is_empty(), false);
215    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(2, 654), (45, 444), (50, 3), (56, 98), (80, 13)]);
216}
217
218#[test]
219fn test_vecmap_unsorted() {
220    let mut v = VecMap::<usize, usize, false>::new();
221    assert_eq!(v.len(), 0);
222    assert_eq!(v.as_slice().len(), 0);
223    assert_eq!(v.is_empty(), true);
224    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), []);
225
226    assert_eq!(v.insert(45, 12), None);
227    assert_eq!(v.len(), 1);
228    assert_eq!(v.as_slice().len(), 1);
229    assert_eq!(v.is_empty(), false);
230    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 12)]);
231
232    assert_eq!(v.insert(56, 6), None);
233    assert_eq!(v.len(), 2);
234    assert_eq!(v.as_slice().len(), 2);
235    assert_eq!(v.is_empty(), false);
236    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 12), (56, 6)]);
237
238    assert_eq!(v.insert(80, 3), None);
239    assert_eq!(v.len(), 3);
240    assert_eq!(v.as_slice().len(), 3);
241    assert_eq!(v.is_empty(), false);
242    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 12), (56, 6), (80, 3)]);
243
244    assert_eq!(v.insert(2, 654), None);
245    assert_eq!(v.len(), 4);
246    assert_eq!(v.as_slice().len(), 4);
247    assert_eq!(v.is_empty(), false);
248    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 12), (56, 6), (80, 3), (2, 654)]);
249
250    assert_eq!(v.insert(56, 98), Some(6));
251    assert_eq!(v.len(), 4);
252    assert_eq!(v.as_slice().len(), 4);
253    assert_eq!(v.is_empty(), false);
254    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 12), (56, 98), (80, 3), (2, 654)]);
255
256    *v.get_mut(&80).unwrap() = 13;
257    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 12), (56, 98), (80, 13), (2, 654)]);
258    *v.get_mut(&45).unwrap() = 444;
259    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 444), (56, 98), (80, 13), (2, 654)]);
260
261    assert_eq!(v.get_mut(&2).map(|x| *x), Some(654));
262    assert_eq!(v.get_mut(&45).map(|x| *x), Some(444));
263    assert_eq!(v.get_mut(&56).map(|x| *x), Some(98));
264    assert_eq!(v.get_mut(&80).map(|x| *x), Some(13));
265    assert_eq!(v.get_mut(&81).map(|x| *x), None);
266    assert_eq!(v.get_mut(&69).map(|x| *x), None);
267    assert_eq!(v.get_mut(&0).map(|x| *x), None);
268    assert_eq!(v.get_mut(&21).map(|x| *x), None);
269    assert_eq!(v.get_mut(&50).map(|x| *x), None);
270
271    assert_eq!(v.get(&2).map(|x| *x), Some(654));
272    assert_eq!(v.get(&45).map(|x| *x), Some(444));
273    assert_eq!(v.get(&56).map(|x| *x), Some(98));
274    assert_eq!(v.get(&80).map(|x| *x), Some(13));
275    assert_eq!(v.get(&81).map(|x| *x), None);
276    assert_eq!(v.get(&69).map(|x| *x), None);
277    assert_eq!(v.get(&0).map(|x| *x), None);
278    assert_eq!(v.get(&21).map(|x| *x), None);
279    assert_eq!(v.get(&50).map(|x| *x), None);
280
281    assert_eq!(v.insert(50, 3), None);
282    assert_eq!(v.len(), 5);
283    assert_eq!(v.as_slice().len(), 5);
284    assert_eq!(v.is_empty(), false);
285    assert_eq!(v.iter().map(|x| (*x.0, *x.1)).collect::<Vec<_>>(), [(45, 444), (56, 98), (80, 13), (2, 654), (50, 3)]);
286}
netsblox_vm/vecmap.rs

netsblox_vm/
vecmap.rs
