#
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}