luaur_common/records/
dense_hash_set.rs

1//! Faithful port of `Luau::DenseHashSet` — a fast `unordered_set` alternative
2//! that does not support erasing. Reference:
3//! `luau/Common/include/Luau/DenseHash.h:471-556`.
4//!
5//! Construction takes an `empty_key` sentinel that must never be inserted as a
6//! real key (it marks free slots).
7
8use crate::records::const_iterator::ConstIterator;
9use crate::records::dense_hash_table::{
10    DenseEq, DenseEqDefault, DenseHashTable, DenseHasher, ItemInterfaceSet,
11};
12use crate::type_aliases::dense_hash_default::DenseHashDefault;
13
14type SetImpl<K, H, E> = DenseHashTable<K, K, ItemInterfaceSet<K>, H, E>;
15
16pub struct DenseHashSet<K, H = DenseHashDefault<K>, E = DenseEqDefault<K>> {
17    pub(crate) impl_: SetImpl<K, H, E>,
18}
19
20impl<K: Clone, H: Clone, E: Clone> Clone for DenseHashSet<K, H, E> {
21    fn clone(&self) -> Self {
22        DenseHashSet {
23            impl_: self.impl_.clone(),
24        }
25    }
26}
27
28impl<K: core::fmt::Debug, H, E> core::fmt::Debug for DenseHashSet<K, H, E> {
29    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
30        f.debug_struct("DenseHashSet")
31            .field("impl_", &self.impl_)
32            .finish()
33    }
34}
35
36impl<K, H, E> DenseHashSet<K, H, E>
37where
38    K: Clone,
39    H: DenseHasher<K> + Default,
40    E: DenseEq<K> + Default,
41{
42    /// `DenseHashSet(empty_key, buckets = 0)`. Reference: `DenseHash.h:482-485`.
43    pub fn new(empty_key: K) -> Self {
44        DenseHashSet {
45            impl_: DenseHashTable::new(empty_key, 0),
46        }
47    }
48
49    /// `insert` — inserts `key` if absent and returns a reference to the stored
50    /// key. Reference: `DenseHash.h:492-496`.
51    pub fn insert(&mut self, key: K) -> &K {
52        self.impl_.rehash_if_full(&key);
53        let idx = self.impl_.insert_unsafe(key);
54        &self.impl_.data[idx]
55    }
56
57    /// `const Key* find(const Key&) const`. Reference: `DenseHash.h:498-501`.
58    pub fn find(&self, key: &K) -> Option<&K> {
59        self.impl_.find(key).map(|idx| &self.impl_.data[idx])
60    }
61
62    /// std-style alias for generated Rust that spelled C++ `find` as `get`.
63    pub fn get(&self, key: &K) -> Option<&K> {
64        self.find(key)
65    }
66
67    /// Mutable analogue of `insert`: inserts `key` if absent and returns a
68    /// mutable reference to the stored key. C++ `insert` returns `const Key&`
69    /// and callers reach for `const_cast<Key&>` when they need to fix up a
70    /// stored entry in place (e.g. `AstNameTable::getOrAddWithType` rewriting a
71    /// non-owned name pointer to an allocator-owned copy of the same bytes —
72    /// the hash/eq are unchanged so the slot stays valid). This exposes that
73    /// mutation soundly. Not a separate C++ method; the mutable access is the
74    /// faithful Rust spelling of the `const_cast` idiom.
75    pub fn insert_mut(&mut self, key: K) -> &mut K {
76        self.impl_.rehash_if_full(&key);
77        let idx = self.impl_.insert_unsafe(key);
78        &mut self.impl_.data[idx]
79    }
80
81    /// Mutable analogue of `find`.
82    pub fn find_mut(&mut self, key: &K) -> Option<&mut K> {
83        match self.impl_.find(key) {
84            Some(idx) => Some(&mut self.impl_.data[idx]),
85            None => None,
86        }
87    }
88
89    /// `contains`. Reference: `DenseHash.h:503-506`.
90    pub fn contains(&self, key: &K) -> bool {
91        self.impl_.find(key).is_some()
92    }
93
94    /// `size`. Reference: `DenseHash.h:508-511`.
95    pub fn size(&self) -> usize {
96        self.impl_.size()
97    }
98
99    /// `empty`. Reference: `DenseHash.h:513-516`.
100    pub fn empty(&self) -> bool {
101        self.impl_.size() == 0
102    }
103
104    /// `clear`. Reference: `DenseHash.h:487-490`.
105    pub fn clear(&mut self) {
106        self.impl_.clear();
107    }
108
109    /// `begin()/end()` iteration, yielding `&Key`.
110    pub fn iter(&self) -> ConstIterator<'_, K, K, ItemInterfaceSet<K>, H, E> {
111        ConstIterator {
112            table: &self.impl_,
113            index: self.impl_.first_occupied(),
114        }
115    }
116}
117
118/// `operator==` / `operator!=` — set equality. Reference: `DenseHash.h:538-555`.
119impl<K, H, E> PartialEq for DenseHashSet<K, H, E>
120where
121    K: Clone,
122    H: DenseHasher<K> + Default,
123    E: DenseEq<K> + Default,
124{
125    fn eq(&self, other: &Self) -> bool {
126        if self.size() != other.size() {
127            return false;
128        }
129        for k in self.iter() {
130            if !other.contains(k) {
131                return false;
132            }
133        }
134        true
135    }
136}
137
138/// C++ members declare their empty key inline (`DenseHashSet<T> x{emptyT}`);
139/// Rust `#[derive(Default)]` on containing structs needs this. The empty key
140/// comes from the element's DenseDefault sentinel.
141impl<K, H, E> Default for DenseHashSet<K, H, E>
142where
143    K: Clone + crate::records::dense_hash_table::DenseDefault,
144    H: DenseHasher<K> + Default,
145    E: DenseEq<K> + Default,
146{
147    fn default() -> Self {
148        Self::new(K::dense_default())
149    }
150}
luaur_common/records/dense_hash_set.rs

luaur_common/records/
dense_hash_set.rs
