oxidd_core/util/
edge_hash_map.rs

1//! [`HashMap`] mapping from edges to values of another type. Performs the
2//! necessary management of [`Edge`]s.
3
4use std::borrow::Borrow;
5use std::collections::hash_map;
6use std::collections::HashMap;
7use std::hash::BuildHasher;
8use std::mem::ManuallyDrop;
9
10use crate::Edge;
11use crate::Manager;
12
13use super::Borrowed;
14
15/// Newtype wrapper around [`ManuallyDrop`] that also implements [`Borrow<T>`]
16#[derive(Clone, Copy, PartialEq, Eq, Hash)]
17struct ManuallyDropKey<T>(ManuallyDrop<T>);
18
19impl<T> ManuallyDropKey<T> {
20    #[inline(always)]
21    fn new(inner: T) -> Self {
22        Self(ManuallyDrop::new(inner))
23    }
24
25    #[inline(always)]
26    fn into_inner(self) -> T {
27        ManuallyDrop::into_inner(self.0)
28    }
29}
30
31impl<T> Borrow<T> for ManuallyDropKey<T> {
32    #[inline(always)]
33    fn borrow(&self) -> &T {
34        &self.0
35    }
36}
37
38/// [`HashMap`] mapping from edges to values of type `V`
39///
40/// Internally, this map stores a [`Manager`] reference such that it can clone
41/// or drop edges accordingly. There is no need to manually drop all contained
42/// keys before dropping the map.
43pub struct EdgeHashMap<'a, M: Manager, V, S> {
44    manager: &'a M,
45    map: ManuallyDrop<HashMap<ManuallyDropKey<M::Edge>, V, S>>,
46}
47
48impl<'a, M: Manager, V, S: Default + BuildHasher> EdgeHashMap<'a, M, V, S> {
49    /// Create a new edge map
50    #[inline]
51    pub fn new(manager: &'a M) -> Self {
52        EdgeHashMap {
53            manager,
54            map: ManuallyDrop::new(HashMap::with_hasher(S::default())),
55        }
56    }
57
58    /// Create a new edge map with `capacity`
59    #[inline]
60    pub fn with_capacity(manager: &'a M, capacity: usize) -> Self {
61        EdgeHashMap {
62            manager,
63            map: ManuallyDrop::new(HashMap::with_capacity_and_hasher(capacity, S::default())),
64        }
65    }
66
67    /// Returns the number of elements in the map
68    #[inline]
69    pub fn len(&self) -> usize {
70        self.map.len()
71    }
72
73    /// Returns `true` iff the map has no elements
74    #[inline]
75    pub fn is_empty(&self) -> bool {
76        self.map.is_empty()
77    }
78
79    /// Reserves capacity for at least `additional` more elements
80    ///
81    /// The collection may reserve more space to speculatively avoid frequent
82    /// reallocations. After calling `reserve()`, the capacity will be greater
83    /// than or equal to `self.len() + additional`. Does nothing if capacity is
84    /// already sufficient.
85    ///
86    /// # Panics
87    ///
88    /// Panics if the new allocation size overflows [`usize`].
89    #[inline]
90    pub fn reserve(&mut self, additional: usize) {
91        self.map.reserve(additional);
92    }
93
94    /// Get a reference to the value for `edge` (if present)
95    #[inline]
96    pub fn get(&self, key: &M::Edge) -> Option<&V> {
97        self.map.get(key)
98    }
99
100    /// Get a mutable reference to the value for `edge` (if present)
101    #[inline]
102    pub fn get_mut(&mut self, key: &M::Edge) -> Option<&mut V> {
103        self.map.get_mut(key)
104    }
105
106    /// Insert a key-value pair into the map
107    ///
108    /// If the map did not have this key present, the key is cloned, and `None`
109    /// is returned. If the map did have this key present, the value is updated,
110    /// and the old value is returned.
111    pub fn insert(&mut self, key: &M::Edge, value: V) -> Option<V> {
112        let edge = key.borrowed();
113        // SAFETY: If the edge is actually inserted into the map, then we clone
114        // the edge (and forget the clone), otherwise the map forgets it.
115        let edge = unsafe { Borrowed::into_inner(edge) };
116        match self.map.insert(ManuallyDropKey(edge), value) {
117            Some(old) => Some(old),
118            None => {
119                std::mem::forget(self.manager.clone_edge(key));
120                None
121            }
122        }
123    }
124
125    /// Remove the entry for the given key (if present)
126    ///
127    /// Returns the value that was previously stored in the map, or `None`,
128    /// respectively.
129    pub fn remove(&mut self, key: &M::Edge) -> Option<V> {
130        match self.map.remove_entry(key) {
131            Some((key, value)) => {
132                self.manager.drop_edge(key.into_inner());
133                Some(value)
134            }
135            None => None,
136        }
137    }
138
139    /// Iterator visiting all key-value pairs in arbitrary order
140    ///
141    /// The item type is `(&M::Edge, &V)`.
142    pub fn iter(&self) -> Iter<'_, M, V> {
143        Iter(self.map.iter())
144    }
145
146    /// Mutable iterator visiting all key-value pairs in arbitrary order
147    ///
148    /// The item type is `(&M::Edge, &mut V)`.
149    pub fn iter_mut(&mut self) -> IterMut<'_, M, V> {
150        IterMut(self.map.iter_mut())
151    }
152}
153
154impl<'a, M: Manager, V: Clone, S: Default + BuildHasher> Clone for EdgeHashMap<'a, M, V, S> {
155    fn clone(&self) -> Self {
156        let mut map = HashMap::with_capacity_and_hasher(self.len(), S::default());
157        for (k, v) in self.map.iter() {
158            let _res = map.insert(
159                ManuallyDropKey::new(self.manager.clone_edge(k.borrow())),
160                v.clone(),
161            );
162            debug_assert!(_res.is_none());
163        }
164        Self {
165            manager: self.manager,
166            map: ManuallyDrop::new(map),
167        }
168    }
169}
170
171impl<'a, M: Manager, V, S> Drop for EdgeHashMap<'a, M, V, S> {
172    #[inline]
173    fn drop(&mut self) {
174        // SAFETY: `self.map` is never used again
175        for (k, _) in unsafe { ManuallyDrop::take(&mut self.map) } {
176            self.manager.drop_edge(k.into_inner());
177        }
178    }
179}
180
181impl<'a, M: Manager, V, S> IntoIterator for EdgeHashMap<'a, M, V, S> {
182    type Item = (M::Edge, V);
183
184    type IntoIter = IntoIter<M, V>;
185
186    #[inline]
187    fn into_iter(mut self) -> Self::IntoIter {
188        // SAFETY: `self.map` is never used again (we forget `self`)
189        let map = unsafe { ManuallyDrop::take(&mut self.map) };
190        std::mem::forget(self);
191        IntoIter(map.into_iter())
192    }
193}
194
195/// Owning iterator over the entries of an [`EdgeHashMap`]
196pub struct IntoIter<M: Manager, V>(hash_map::IntoIter<ManuallyDropKey<M::Edge>, V>);
197
198impl<M: Manager, V> Iterator for IntoIter<M, V> {
199    type Item = (M::Edge, V);
200
201    #[inline]
202    fn next(&mut self) -> Option<Self::Item> {
203        match self.0.next() {
204            Some((key, value)) => Some((key.into_inner(), value)),
205            None => None,
206        }
207    }
208}
209
210/// Iterator over the entries of an [`EdgeHashMap`]
211///
212/// Created by [`EdgeHashMap::iter()`], see its documentation for more details.
213pub struct Iter<'a, M: Manager, V>(hash_map::Iter<'a, ManuallyDropKey<M::Edge>, V>);
214
215impl<'a, M: Manager, V> Iterator for Iter<'a, M, V> {
216    type Item = (&'a M::Edge, &'a V);
217
218    #[inline]
219    fn next(&mut self) -> Option<Self::Item> {
220        match self.0.next() {
221            Some((key, value)) => Some((key.borrow(), value)),
222            None => None,
223        }
224    }
225}
226
227impl<'a, 'b, M: Manager, V, S> IntoIterator for &'b EdgeHashMap<'a, M, V, S> {
228    type Item = (&'b M::Edge, &'b V);
229
230    type IntoIter = Iter<'b, M, V>;
231
232    #[inline]
233    fn into_iter(self) -> Self::IntoIter {
234        Iter(self.map.iter())
235    }
236}
237
238/// Mutable iterator over the entries of an [`EdgeHashMap`]
239///
240/// Created by [`EdgeHashMap::iter_mut()`], see its documentation for more
241/// details.
242pub struct IterMut<'a, M: Manager, V>(hash_map::IterMut<'a, ManuallyDropKey<M::Edge>, V>);
243
244impl<'a, M: Manager, V> Iterator for IterMut<'a, M, V> {
245    type Item = (&'a M::Edge, &'a mut V);
246
247    #[inline]
248    fn next(&mut self) -> Option<Self::Item> {
249        match self.0.next() {
250            Some((key, value)) => Some((key.borrow(), value)),
251            None => None,
252        }
253    }
254}
255
256impl<'a, 'b, M: Manager, V, S> IntoIterator for &'b mut EdgeHashMap<'a, M, V, S> {
257    type Item = (&'b M::Edge, &'b mut V);
258
259    type IntoIter = IterMut<'b, M, V>;
260
261    #[inline]
262    fn into_iter(self) -> Self::IntoIter {
263        IterMut(self.map.iter_mut())
264    }
265}
oxidd_core/util/edge_hash_map.rs

oxidd_core/util/
edge_hash_map.rs
