cairo_lang_utils/
small_ordered_map.rs

1/// A mapping optimized for very small maps.
2///
3/// Wraps the `vector_map::VecMap` structure.
4#[derive(Clone, Debug)]
5#[cfg_attr(
6    feature = "serde",
7    derive(serde::Deserialize, serde::Serialize),
8    serde(transparent),
9    serde(bound(
10        serialize = "Key: serde::Serialize + Eq, Value: serde::Serialize",
11        deserialize = "Key: serde::Deserialize<'de> + Eq, Value: serde::Deserialize<'de>",
12    ))
13)]
14pub struct SmallOrderedMap<Key, Value>(vector_map::VecMap<Key, Value>);
15impl<Key: Eq, Value> SmallOrderedMap<Key, Value> {
16    /// Creates a new empty map.
17    pub fn new() -> Self {
18        Self(vector_map::VecMap::new())
19    }
20    /// Creates a new map with the given capacity.
21    pub fn with_capacity(capacity: usize) -> Self {
22        Self(vector_map::VecMap::with_capacity(capacity))
23    }
24}
25impl<Key: Eq, Value: Eq> SmallOrderedMap<Key, Value> {
26    /// Checks if the two maps have the same keys and values.
27    pub fn eq_unordered(&self, other: &Self) -> bool {
28        self.0 == other.0
29    }
30}
31impl<Key: Eq, Value: Eq> PartialEq for SmallOrderedMap<Key, Value> {
32    fn eq(&self, other: &Self) -> bool {
33        self.0.iter().eq(other.0.iter())
34    }
35}
36impl<Key: Eq, Value: Eq> Eq for SmallOrderedMap<Key, Value> {}
37impl<Key: Eq, Value> Default for SmallOrderedMap<Key, Value> {
38    fn default() -> Self {
39        Self::new()
40    }
41}
42impl<Key: Eq, Value> FromIterator<(Key, Value)> for SmallOrderedMap<Key, Value> {
43    fn from_iter<T: IntoIterator<Item = (Key, Value)>>(iter: T) -> Self {
44        Self(iter.into_iter().collect())
45    }
46}
47impl<Key, Value> IntoIterator for SmallOrderedMap<Key, Value> {
48    type Item = (Key, Value);
49    type IntoIter = vector_map::IntoIter<Key, Value>;
50
51    fn into_iter(self) -> Self::IntoIter {
52        self.0.into_iter()
53    }
54}
55impl<Key, Value> core::ops::Deref for SmallOrderedMap<Key, Value> {
56    type Target = vector_map::VecMap<Key, Value>;
57
58    fn deref(&self) -> &Self::Target {
59        &self.0
60    }
61}
62impl<Key, Value> core::ops::DerefMut for SmallOrderedMap<Key, Value> {
63    fn deref_mut(&mut self) -> &mut Self::Target {
64        &mut self.0
65    }
66}
67
68#[cfg(feature = "salsa")]
69unsafe impl<Key: salsa::Update + Eq, Value: salsa::Update> salsa::Update
70    for SmallOrderedMap<Key, Value>
71{
72    // This code was taken from the salsa::Update trait implementation for IndexMap.
73    // It is defined privately in macro_rules! maybe_update_map in the db-ext-macro repo.
74    unsafe fn maybe_update(old_pointer: *mut Self, new_map: Self) -> bool {
75        let old_map: &mut Self = unsafe { &mut *old_pointer };
76
77        // To be considered "equal", the set of keys
78        // must be the same between the two maps.
79        let same_keys =
80            old_map.len() == new_map.len() && old_map.keys().all(|k| new_map.contains_key(k));
81
82        // If the set of keys has changed, then just pull in the new values
83        // from new_map and discard the old ones.
84        if !same_keys {
85            old_map.clear();
86            old_map.extend(new_map);
87            return true;
88        }
89
90        // Otherwise, recursively descend to the values.
91        // We do not invoke `K::update` because we assume
92        // that if the values are `Eq` they must not need
93        // updating (see the trait criteria).
94        let mut changed = false;
95        for (key, new_value) in new_map.into_iter() {
96            let old_value = old_map.get_mut(&key).unwrap();
97            changed |= unsafe { Value::maybe_update(old_value, new_value) };
98        }
99        changed
100    }
101}
102/// Entry for an existing key-value pair or a vacant location to insert one.
103pub type Entry<'a, Key, Value> = vector_map::Entry<'a, Key, Value>;
cairo_lang_utils/small_ordered_map.rs

cairo_lang_utils/
small_ordered_map.rs
