cairo_lang_utils/
small_ordered_map.rs

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

cairo_lang_utils/
small_ordered_map.rs
