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

cairo_lang_utils/
small_ordered_map.rs
