cairo_lang_utils/
ordered_hash_map.rs

1use core::hash::{BuildHasher, Hash};
2
3use indexmap::IndexMap;
4use itertools::zip_eq;
5
6#[cfg(feature = "std")]
7type BHImpl = std::collections::hash_map::RandomState;
8#[cfg(not(feature = "std"))]
9type BHImpl = hashbrown::DefaultHashBuilder;
10
11#[derive(Clone, Debug)]
12#[cfg_attr(
13    feature = "serde",
14    derive(serde::Deserialize, serde::Serialize),
15    serde(transparent),
16    serde(bound(
17        serialize = "Key: serde::Serialize, Value: serde::Serialize",
18        deserialize = "Key: serde::Deserialize<'de> + Hash + Eq, Value: serde::Deserialize<'de>, \
19                       BH: BuildHasher + Default"
20    ))
21)]
22pub struct OrderedHashMap<Key, Value, BH = BHImpl>(IndexMap<Key, Value, BH>);
23
24impl<Key, Value, BH> core::ops::Deref for OrderedHashMap<Key, Value, BH> {
25    type Target = IndexMap<Key, Value, BH>;
26
27    fn deref(&self) -> &Self::Target {
28        &self.0
29    }
30}
31
32impl<Key, Value, BH> core::ops::DerefMut for OrderedHashMap<Key, Value, BH> {
33    fn deref_mut(&mut self) -> &mut Self::Target {
34        &mut self.0
35    }
36}
37
38#[cfg(feature = "salsa")]
39unsafe impl<Key: salsa::Update + Eq + Hash, Value: salsa::Update, BH: BuildHasher> salsa::Update
40    for OrderedHashMap<Key, Value, BH>
41{
42    // This code was taken from the salsa::Update trait implementation for IndexMap.
43    // It is defined privately in macro_rules! maybe_update_map in the db-ext-macro repo.
44    unsafe fn maybe_update(old_pointer: *mut Self, new_map: Self) -> bool {
45        let old_map: &mut Self = unsafe { &mut *old_pointer };
46
47        // To be considered "equal", the set of keys
48        // must be the same between the two maps.
49        let same_keys =
50            old_map.len() == new_map.len() && old_map.keys().all(|k| new_map.contains_key(k));
51
52        // If the set of keys has changed, then just pull in the new values
53        // from new_map and discard the old ones.
54        if !same_keys {
55            old_map.clear();
56            old_map.extend(new_map);
57            return true;
58        }
59
60        // Otherwise, recursively descend to the values.
61        // We do not invoke `K::update` because we assume
62        // that if the values are `Eq` they must not need
63        // updating (see the trait criteria).
64        let mut changed = false;
65        for (key, new_value) in new_map.into_iter() {
66            let old_value = old_map.get_mut(&key).unwrap();
67            changed |= unsafe { Value::maybe_update(old_value, new_value) };
68        }
69        changed
70    }
71}
72
73impl<Key, Value, BH: Default> Default for OrderedHashMap<Key, Value, BH> {
74    #[cfg(feature = "std")]
75    fn default() -> Self {
76        Self(Default::default())
77    }
78    #[cfg(not(feature = "std"))]
79    fn default() -> Self {
80        Self(IndexMap::with_hasher(Default::default()))
81    }
82}
83
84impl<Key, Value, BH> OrderedHashMap<Key, Value, BH> {
85    /// Returns true if the map contains no elements.
86    pub fn is_empty(&self) -> bool {
87        self.0.is_empty()
88    }
89}
90
91impl<Key: Eq + Hash, Value, BH: BuildHasher> OrderedHashMap<Key, Value, BH> {
92    /// Returns true if the maps are equal, ignoring the order of the entries.
93    pub fn eq_unordered(&self, other: &Self) -> bool
94    where
95        Value: Eq,
96    {
97        if self.len() != other.len() {
98            return false;
99        };
100        self.iter().all(|(k, v)| other.get(k) == Some(v))
101    }
102}
103
104/// Entry for an existing key-value pair or a vacant location to insert one.
105pub type Entry<'a, Key, Value> = indexmap::map::Entry<'a, Key, Value>;
106
107impl<Key, Value, BH> IntoIterator for OrderedHashMap<Key, Value, BH> {
108    type Item = (Key, Value);
109    type IntoIter = indexmap::map::IntoIter<Key, Value>;
110    fn into_iter(self) -> Self::IntoIter {
111        let OrderedHashMap(inner) = self;
112        inner.into_iter()
113    }
114}
115
116impl<Key: Eq, Value: Eq, BH> PartialEq for OrderedHashMap<Key, Value, BH> {
117    fn eq(&self, other: &Self) -> bool {
118        if self.len() != other.len() {
119            return false;
120        };
121
122        zip_eq(self.iter(), other.iter()).all(|(a, b)| a == b)
123    }
124}
125
126impl<Key: Hash + Eq, Value: Eq, BH: BuildHasher> Eq for OrderedHashMap<Key, Value, BH> {}
127
128impl<Key: Hash, Value: Hash, BH> Hash for OrderedHashMap<Key, Value, BH> {
129    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
130        self.len().hash(state);
131        for e in self.iter() {
132            e.hash(state);
133        }
134    }
135}
136
137impl<Key: Hash + Eq, Value, BH: BuildHasher + Default> FromIterator<(Key, Value)>
138    for OrderedHashMap<Key, Value, BH>
139{
140    fn from_iter<T: IntoIterator<Item = (Key, Value)>>(iter: T) -> Self {
141        Self(iter.into_iter().collect())
142    }
143}
144
145impl<Key: Hash + Eq, Value, BH: BuildHasher + Default, const N: usize> From<[(Key, Value); N]>
146    for OrderedHashMap<Key, Value, BH>
147{
148    fn from(init_map: [(Key, Value); N]) -> Self {
149        Self(IndexMap::from_iter(init_map))
150    }
151}
152
153#[cfg(feature = "serde")]
154mod impl_serde {
155    use indexmap::map::serde_seq;
156    use serde::{Deserialize, Deserializer, Serialize, Serializer};
157
158    use super::*;
159
160    pub fn serialize_ordered_hashmap_vec<K, V, BH, S>(
161        v: &OrderedHashMap<K, V, BH>,
162        serializer: S,
163    ) -> Result<S::Ok, S::Error>
164    where
165        S: Serializer,
166        K: Serialize + Hash + Eq,
167        V: Serialize,
168    {
169        serde_seq::serialize(&v.0, serializer)
170    }
171
172    pub fn deserialize_ordered_hashmap_vec<'de, K, V, BH: BuildHasher + Default, D>(
173        deserializer: D,
174    ) -> Result<OrderedHashMap<K, V, BH>, D::Error>
175    where
176        D: Deserializer<'de>,
177        K: Deserialize<'de> + Hash + Eq,
178        V: Deserialize<'de>,
179    {
180        Ok(OrderedHashMap(serde_seq::deserialize(deserializer)?))
181    }
182}
183#[cfg(feature = "serde")]
184pub use impl_serde::*;
cairo_lang_utils/ordered_hash_map.rs

cairo_lang_utils/
ordered_hash_map.rs
