signal_hook_registry/
vec_map.rs

1use std::mem;
2
3/// A small map backed by an unsorted vector.
4///
5/// Maintains key uniqueness at cost of O(n) lookup/insert/remove. Maintains insertion order
6/// (`insert` calls that overwrite an existing value don't change order).
7#[derive(Clone, Default)]
8pub struct VecMap<K, V>(Vec<(K, V)>);
9
10impl<K: Eq, V> VecMap<K, V> {
11    pub fn new() -> Self {
12        VecMap(Vec::new())
13    }
14
15    pub fn is_empty(&self) -> bool {
16        self.0.is_empty()
17    }
18
19    pub fn clear(&mut self) {
20        self.0.clear();
21    }
22
23    fn find(&self, key: &K) -> Option<usize> {
24        for (i, (k, _)) in self.0.iter().enumerate() {
25            if k == key {
26                return Some(i);
27            }
28        }
29        None
30    }
31
32    pub fn contains(&self, key: &K) -> bool {
33        self.find(key).is_some()
34    }
35
36    pub fn get(&self, key: &K) -> Option<&V> {
37        match self.find(key) {
38            Some(i) => Some(&self.0[i].1),
39            None => None,
40        }
41    }
42
43    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
44        match self.find(key) {
45            Some(i) => Some(&mut self.0[i].1),
46            None => None,
47        }
48    }
49
50    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
51        if let Some(old) = self.get_mut(&key) {
52            return Some(mem::replace(old, value));
53        }
54        self.0.push((key, value));
55        None
56    }
57
58    pub fn remove(&mut self, key: &K) -> Option<V> {
59        match self.find(key) {
60            Some(i) => Some(self.0.remove(i).1),
61            None => None,
62        }
63    }
64
65    pub fn values(&self) -> impl Iterator<Item = &V> {
66        self.0.iter().map(|kv| &kv.1)
67    }
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn empty() {
76        let m: VecMap<char, u32> = VecMap::new();
77        assert!(m.is_empty());
78        assert!(!m.contains(&'a'));
79        assert!(m.values().next().is_none());
80    }
81
82    #[test]
83    fn insert_update_get() {
84        let mut m: VecMap<char, u32> = VecMap::new();
85        assert!(m.insert('a', 1).is_none());
86        assert!(m.insert('b', 2).is_none());
87        assert_eq!(m.get(&'a'), Some(&1));
88        assert_eq!(m.get(&'b'), Some(&2));
89        *m.get_mut(&'a').unwrap() += 10;
90        assert_eq!(m.get(&'a'), Some(&11));
91        assert_eq!(m.get(&'b'), Some(&2));
92    }
93
94    #[test]
95    fn insert_overwrite() {
96        let mut m = VecMap::new();
97        assert_eq!(m.insert('a', 1), None);
98        assert_eq!(m.insert('b', 2), None);
99        assert_eq!(m.insert('a', 3), Some(1));
100        assert_eq!(m.insert('a', 4), Some(3));
101        assert_eq!(m.get(&'a').copied(), Some(4));
102        assert_eq!(m.get(&'b').copied(), Some(2));
103        assert_eq!(m.insert('b', 5), Some(2));
104        assert_eq!(m.get(&'a').copied(), Some(4));
105        assert_eq!(m.get(&'b').copied(), Some(5));
106    }
107
108    #[test]
109    fn insert_remove() {
110        let mut m: VecMap<char, u32> = VecMap::new();
111        assert_eq!(m.remove(&'a'), None);
112        m.insert('a', 1);
113        m.insert('b', 2);
114        assert_eq!(m.remove(&'a'), Some(1));
115        assert_eq!(m.remove(&'a'), None);
116        assert_eq!(m.remove(&'b'), Some(2));
117        assert!(m.is_empty());
118    }
119
120    #[test]
121    fn insertion_order() {
122        let mut m: VecMap<char, u32> = VecMap::new();
123        let values = |m: &VecMap<char, u32>| -> Vec<u32> { m.values().copied().collect() };
124        m.insert('b', 2);
125        m.insert('a', 1);
126        m.insert('c', 3);
127        assert_eq!(values(&m), vec![2, 1, 3]);
128        m.insert('a', 11);
129        m.remove(&'b');
130        assert_eq!(values(&m), vec![11, 3]);
131        m.insert('b', 2);
132        assert_eq!(values(&m), vec![11, 3, 2]);
133    }
134
135    #[test]
136    fn containment_equivalences() {
137        let mut m = VecMap::new();
138        for i in 0u8..=255 {
139            if i % 10 < 3 {
140                m.insert(i, i);
141            }
142        }
143        for i in 0u8..=255 {
144            if m.contains(&i) {
145                assert_eq!(m.get(&i).copied(), Some(i));
146                assert_eq!(m.get_mut(&i).copied(), Some(i));
147                assert_eq!(m.insert(i, i), Some(i));
148                assert_eq!(m.remove(&i), Some(i));
149            } else {
150                assert!(m.get(&i).is_none());
151                assert!(m.get_mut(&i).is_none());
152                assert!(m.remove(&i).is_none());
153                assert!(m.insert(i, i).is_none());
154            }
155        }
156    }
157
158    #[test]
159    fn clear() {
160        let mut m = VecMap::new();
161        m.clear();
162        assert!(m.is_empty());
163        m.insert('a', 1);
164        m.insert('b', 2);
165        assert!(!m.is_empty());
166        m.clear();
167        assert!(m.is_empty());
168        m.insert('c', 3);
169        assert!(!m.is_empty());
170    }
171}
signal_hook_registry/vec_map.rs

signal_hook_registry/
vec_map.rs
