cairo_lang_utils/
unordered_hash_set.rs

1#![cfg_attr(
2    feature = "std",
3    expect(
4        clippy::disallowed_types,
5        reason = "this module is the UnorderedHashSet wrapper over std::collections::HashSet"
6    )
7)]
8
9use core::borrow::Borrow;
10use core::hash::{BuildHasher, Hash};
11use core::ops::Sub;
12#[cfg(feature = "std")]
13use std::collections::HashSet;
14#[cfg(feature = "std")]
15use std::collections::hash_map::RandomState;
16
17#[cfg(not(feature = "std"))]
18use hashbrown::HashSet;
19
20/// A hash set that does not care about the order of insertion.
21///
22/// In particular, it does not support iterating, in order to guarantee deterministic compilation.
23/// For an iterable version see [OrderedHashSet](crate::ordered_hash_set::OrderedHashSet).
24#[cfg(feature = "std")]
25#[derive(Clone, Debug)]
26pub struct UnorderedHashSet<Key, BH = RandomState>(HashSet<Key, BH>);
27#[cfg(not(feature = "std"))]
28#[derive(Clone, Debug)]
29pub struct UnorderedHashSet<Key, BH = hashbrown::DefaultHashBuilder>(HashSet<Key, BH>);
30
31// This code was taken from the salsa::Update trait implementation for IndexSet.
32// It is defined privately in macro_rules! maybe_update_set in the db-ext-macro repo (with a small
33// change of using `extend_unordered` instead of `extend`).
34#[cfg(feature = "salsa")]
35unsafe impl<Key: Eq + Hash, BH: BuildHasher> salsa::Update for UnorderedHashSet<Key, BH> {
36    unsafe fn maybe_update(old_pointer: *mut Self, new_set: Self) -> bool {
37        let old_set: &mut Self = unsafe { &mut *old_pointer };
38
39        if *old_set == new_set {
40            false
41        } else {
42            old_set.clear();
43            old_set.extend_unordered(new_set);
44            true
45        }
46    }
47}
48
49impl<K, BH: Default> Default for UnorderedHashSet<K, BH> {
50    #[cfg(feature = "std")]
51    fn default() -> Self {
52        Self(Default::default())
53    }
54    #[cfg(not(feature = "std"))]
55    fn default() -> Self {
56        Self(HashSet::with_hasher(Default::default()))
57    }
58}
59
60impl<K, BH> PartialEq for UnorderedHashSet<K, BH>
61where
62    K: Eq + Hash,
63    BH: BuildHasher,
64{
65    fn eq(&self, other: &Self) -> bool {
66        self.0 == other.0
67    }
68}
69
70impl<K, BH> Eq for UnorderedHashSet<K, BH>
71where
72    K: Eq + Hash,
73    BH: BuildHasher,
74{
75}
76
77impl<Key, BH> UnorderedHashSet<Key, BH> {
78    /// Returns the number of elements in the set.
79    pub fn len(&self) -> usize {
80        self.0.len()
81    }
82
83    /// Returns true if the set contains no elements.
84    pub fn is_empty(&self) -> bool {
85        self.0.is_empty()
86    }
87
88    /// Clears the set, removing all values.
89    pub fn clear(&mut self) {
90        self.0.clear()
91    }
92}
93
94#[cfg(feature = "std")]
95impl<Key: Hash + Eq> UnorderedHashSet<Key> {
96    pub fn with_capacity(capacity: usize) -> Self {
97        Self(HashSet::with_capacity(capacity))
98    }
99}
100
101#[cfg(not(feature = "std"))]
102impl<Key: Hash + Eq> UnorderedHashSet<Key> {
103    pub fn with_capacity(capacity: usize) -> Self {
104        Self(HashSet::with_capacity_and_hasher(capacity, Default::default()))
105    }
106}
107
108impl<Key: Hash + Eq, BH: BuildHasher> UnorderedHashSet<Key, BH> {
109    /// Inserts the value into the set.
110    ///
111    /// If an equivalent item already exists in the set, returns `false`. Otherwise, returns `true`.
112    pub fn insert(&mut self, key: Key) -> bool {
113        self.0.insert(key)
114    }
115
116    /// Removes a value from the set. Returns whether the value was present in the set.
117    pub fn remove<Q: ?Sized + Hash + Eq>(&mut self, value: &Q) -> bool
118    where
119        Key: Borrow<Q>,
120    {
121        self.0.remove(value)
122    }
123
124    /// Extends the set with the content of the given iterator.
125    pub fn extend<I: IntoIterator<Item = Key>>(&mut self, iter: I) {
126        self.0.extend(iter)
127    }
128
129    /// Extends the set with the content of another set.
130    pub fn extend_unordered(&mut self, other: Self) {
131        self.0.extend(other.0)
132    }
133
134    /// Returns true if an equivalent to value exists in the set.
135    pub fn contains<Q: ?Sized + Hash + Eq>(&self, value: &Q) -> bool
136    where
137        Key: Borrow<Q>,
138    {
139        self.0.contains(value)
140    }
141}
142
143impl<Key: Hash + Eq, BH: BuildHasher + Default> FromIterator<Key> for UnorderedHashSet<Key, BH> {
144    fn from_iter<T: IntoIterator<Item = Key>>(iter: T) -> Self {
145        Self(iter.into_iter().collect())
146    }
147}
148
149impl<'a, Key, BH> Sub<&'a UnorderedHashSet<Key, BH>> for &'a UnorderedHashSet<Key, BH>
150where
151    &'a HashSet<Key, BH>: Sub<Output = HashSet<Key, BH>>,
152{
153    type Output = UnorderedHashSet<Key, BH>;
154
155    fn sub(self, rhs: Self) -> Self::Output {
156        UnorderedHashSet::<Key, BH>(&self.0 - &rhs.0)
157    }
158}
cairo_lang_utils/unordered_hash_set.rs

cairo_lang_utils/
unordered_hash_set.rs
