rkyv/collections/swiss_table/
map.rs

1//! Archived hash map implementation using an archived SwissTable.
2
3use core::{
4    borrow::Borrow,
5    fmt,
6    hash::{Hash, Hasher},
7    iter::FusedIterator,
8    marker::PhantomData,
9    ops::Index,
10};
11
12use munge::munge;
13use rancor::{Fallible, Source};
14
15use crate::{
16    collections::{
17        swiss_table::table::{ArchivedHashTable, HashTableResolver, RawIter},
18        util::{Entry, EntryAdapter},
19    },
20    hash::{hash_value, FxHasher64},
21    seal::Seal,
22    ser::{Allocator, Writer},
23    Place, Portable, Serialize,
24};
25
26/// An archived SwissTable hash map.
27#[derive(Portable)]
28#[rkyv(crate)]
29#[repr(transparent)]
30#[cfg_attr(feature = "bytecheck", derive(bytecheck::CheckBytes))]
31pub struct ArchivedHashMap<K, V, H = FxHasher64> {
32    table: ArchivedHashTable<Entry<K, V>>,
33    _phantom: PhantomData<H>,
34}
35
36impl<K, V, H> ArchivedHashMap<K, V, H> {
37    /// Returns whether the hash map is empty.
38    pub const fn is_empty(&self) -> bool {
39        self.table.is_empty()
40    }
41
42    /// Returns the number of elements in the hash map.
43    pub const fn len(&self) -> usize {
44        self.table.len()
45    }
46
47    /// Returns the total capacity of the hash map.
48    pub fn capacity(&self) -> usize {
49        self.table.capacity()
50    }
51
52    /// Returns an iterator over the key-value entries in the hash map.
53    pub fn iter(&self) -> Iter<'_, K, V, H> {
54        Iter {
55            raw: self.table.raw_iter(),
56            _phantom: PhantomData,
57        }
58    }
59
60    /// Returns an iterator over the sealed key-value entries in the hash map.
61    pub fn iter_seal(this: Seal<'_, Self>) -> IterMut<'_, K, V, H> {
62        munge!(let Self { table, .. } = this);
63        IterMut {
64            raw: ArchivedHashTable::raw_iter_seal(table),
65            _phantom: PhantomData,
66        }
67    }
68
69    /// Returns an iterator over the keys in the hash map.
70    pub fn keys(&self) -> Keys<'_, K, V, H> {
71        Keys {
72            raw: self.table.raw_iter(),
73            _phantom: PhantomData,
74        }
75    }
76
77    /// Returns an iterator over the values in the hash map.
78    pub fn values(&self) -> Values<'_, K, V, H> {
79        Values {
80            raw: self.table.raw_iter(),
81            _phantom: PhantomData,
82        }
83    }
84
85    /// Returns an iterator over the mutable values in the hash map.
86    pub fn values_seal(this: Seal<'_, Self>) -> ValuesMut<'_, K, V, H> {
87        munge!(let Self { table, .. } = this);
88        ValuesMut {
89            raw: ArchivedHashTable::raw_iter_seal(table),
90            _phantom: PhantomData,
91        }
92    }
93}
94
95impl<K, V, H: Hasher + Default> ArchivedHashMap<K, V, H> {
96    /// Returns the key-value pair corresponding to the supplied key using the
97    /// given comparison function.
98    pub fn get_key_value_with<Q, C>(&self, key: &Q, cmp: C) -> Option<(&K, &V)>
99    where
100        Q: Hash + Eq + ?Sized,
101        C: Fn(&Q, &K) -> bool,
102    {
103        let entry = self
104            .table
105            .get_with(hash_value::<Q, H>(key), |e| cmp(key, &e.key))?;
106        Some((&entry.key, &entry.value))
107    }
108
109    /// Returns the key-value pair corresponding to the supplied key.
110    pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
111    where
112        K: Borrow<Q>,
113        Q: Hash + Eq + ?Sized,
114    {
115        self.get_key_value_with(key, |q, k| q == k.borrow())
116    }
117
118    /// Returns a reference to the value corresponding to the supplied key using
119    /// the given comparison function.
120    pub fn get_with<Q, C>(&self, key: &Q, cmp: C) -> Option<&V>
121    where
122        Q: Hash + Eq + ?Sized,
123        C: Fn(&Q, &K) -> bool,
124    {
125        Some(self.get_key_value_with(key, cmp)?.1)
126    }
127
128    /// Returns a reference to the value corresponding to the supplied key.
129    pub fn get<Q>(&self, key: &Q) -> Option<&V>
130    where
131        K: Borrow<Q>,
132        Q: Hash + Eq + ?Sized,
133    {
134        Some(self.get_key_value(key)?.1)
135    }
136
137    /// Returns the mutable key-value pair corresponding to the supplied key
138    /// using the given comparison function.
139    pub fn get_key_value_seal_with<'a, Q, C>(
140        this: Seal<'a, Self>,
141        key: &Q,
142        cmp: C,
143    ) -> Option<(&'a K, Seal<'a, V>)>
144    where
145        K: Borrow<Q>,
146        Q: Hash + Eq + ?Sized,
147        C: Fn(&Q, &K) -> bool,
148    {
149        munge!(let Self { table, .. } = this);
150        let entry = ArchivedHashTable::get_seal_with(
151            table,
152            hash_value::<Q, H>(key),
153            |e| cmp(key, &e.key),
154        )?;
155        munge!(let Entry { key, value } = entry);
156        Some((key.unseal_ref(), value))
157    }
158
159    /// Returns the mutable key-value pair corresponding to the supplied key.
160    pub fn get_key_value_seal<'a, Q>(
161        this: Seal<'a, Self>,
162        key: &Q,
163    ) -> Option<(&'a K, Seal<'a, V>)>
164    where
165        K: Borrow<Q>,
166        Q: Hash + Eq + ?Sized,
167    {
168        Self::get_key_value_seal_with(this, key, |q, k| q == k.borrow())
169    }
170
171    /// Returns a mutable reference to the value corresponding to the supplied
172    /// key using the given comparison function.
173    pub fn get_seal_with<'a, Q, C>(
174        this: Seal<'a, Self>,
175        key: &Q,
176        cmp: C,
177    ) -> Option<Seal<'a, V>>
178    where
179        K: Borrow<Q>,
180        Q: Hash + Eq + ?Sized,
181        C: Fn(&Q, &K) -> bool,
182    {
183        Some(Self::get_key_value_seal_with(this, key, cmp)?.1)
184    }
185
186    /// Returns a mutable reference to the value corresponding to the supplied
187    /// key.
188    pub fn get_seal<'a, Q>(this: Seal<'a, Self>, key: &Q) -> Option<Seal<'a, V>>
189    where
190        K: Borrow<Q>,
191        Q: Hash + Eq + ?Sized,
192    {
193        Some(Self::get_key_value_seal(this, key)?.1)
194    }
195
196    /// Returns whether the hash map contains the given key.
197    pub fn contains_key<Q>(&self, key: &Q) -> bool
198    where
199        K: Borrow<Q>,
200        Q: Hash + Eq + ?Sized,
201    {
202        self.get(key).is_some()
203    }
204
205    /// Serializes an iterator of key-value pairs as a hash map.
206    pub fn serialize_from_iter<I, BKU, BVU, KU, VU, S>(
207        iter: I,
208        load_factor: (usize, usize),
209        serializer: &mut S,
210    ) -> Result<HashMapResolver, S::Error>
211    where
212        I: Clone + ExactSizeIterator<Item = (BKU, BVU)>,
213        BKU: Borrow<KU>,
214        BVU: Borrow<VU>,
215        KU: Serialize<S, Archived = K> + Hash + Eq,
216        VU: Serialize<S, Archived = V>,
217        S: Fallible + Writer + Allocator + ?Sized,
218        S::Error: Source,
219    {
220        ArchivedHashTable::<Entry<K, V>>::serialize_from_iter(
221            iter.clone()
222                .map(|(key, value)| EntryAdapter::new(key, value)),
223            iter.map(|(key, _)| hash_value::<KU, H>(key.borrow())),
224            load_factor,
225            serializer,
226        )
227        .map(HashMapResolver)
228    }
229
230    /// Resolves an archived hash map from a given length and parameters.
231    pub fn resolve_from_len(
232        len: usize,
233        load_factor: (usize, usize),
234        resolver: HashMapResolver,
235        out: Place<Self>,
236    ) {
237        munge!(let ArchivedHashMap { table, _phantom: _ } = out);
238        ArchivedHashTable::<Entry<K, V>>::resolve_from_len(
239            len,
240            load_factor,
241            resolver.0,
242            table,
243        )
244    }
245}
246
247impl<K, V, H> fmt::Debug for ArchivedHashMap<K, V, H>
248where
249    K: fmt::Debug,
250    V: fmt::Debug,
251{
252    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
253        f.debug_map().entries(self.iter()).finish()
254    }
255}
256
257impl<K, V, H> Eq for ArchivedHashMap<K, V, H>
258where
259    K: Hash + Eq,
260    V: Eq,
261    H: Default + Hasher,
262{
263}
264
265impl<K, V, H> PartialEq for ArchivedHashMap<K, V, H>
266where
267    K: Hash + Eq,
268    V: PartialEq,
269    H: Default + Hasher,
270{
271    fn eq(&self, other: &Self) -> bool {
272        if self.len() != other.len() {
273            false
274        } else {
275            self.iter().all(|(key, value)| {
276                other.get(key).is_some_and(|v| *value == *v)
277            })
278        }
279    }
280}
281
282impl<K, Q, V, H> Index<&'_ Q> for ArchivedHashMap<K, V, H>
283where
284    K: Eq + Hash + Borrow<Q>,
285    Q: Eq + Hash + ?Sized,
286    H: Default + Hasher,
287{
288    type Output = V;
289
290    fn index(&self, key: &Q) -> &V {
291        self.get(key).unwrap()
292    }
293}
294
295/// The resolver for [`ArchivedHashMap`].
296pub struct HashMapResolver(HashTableResolver);
297
298/// An iterator over the key-value pairs of an [`ArchivedHashMap`].
299pub struct Iter<'a, K, V, H> {
300    raw: RawIter<Entry<K, V>>,
301    _phantom: PhantomData<&'a ArchivedHashMap<K, V, H>>,
302}
303
304impl<'a, K, V, H> Iterator for Iter<'a, K, V, H> {
305    type Item = (&'a K, &'a V);
306
307    fn next(&mut self) -> Option<Self::Item> {
308        self.raw.next().map(|entry| {
309            let entry = unsafe { entry.as_ref() };
310            (&entry.key, &entry.value)
311        })
312    }
313}
314
315impl<K, V, H> ExactSizeIterator for Iter<'_, K, V, H> {
316    fn len(&self) -> usize {
317        self.raw.len()
318    }
319}
320
321impl<K, V, H> FusedIterator for Iter<'_, K, V, H> {}
322
323/// An iterator over the mutable key-value pairs of an [`ArchivedHashMap`].
324pub struct IterMut<'a, K, V, H> {
325    raw: RawIter<Entry<K, V>>,
326    _phantom: PhantomData<&'a ArchivedHashMap<K, V, H>>,
327}
328
329impl<'a, K, V, H> Iterator for IterMut<'a, K, V, H> {
330    type Item = (&'a K, Seal<'a, V>);
331
332    fn next(&mut self) -> Option<Self::Item> {
333        self.raw.next().map(|mut entry| {
334            let entry = unsafe { entry.as_mut() };
335            (&entry.key, Seal::new(&mut entry.value))
336        })
337    }
338}
339
340impl<K, V, H> ExactSizeIterator for IterMut<'_, K, V, H> {
341    fn len(&self) -> usize {
342        self.raw.len()
343    }
344}
345
346impl<K, V, H> FusedIterator for IterMut<'_, K, V, H> {}
347
348/// An iterator over the keys of an [`ArchivedHashMap`].
349pub struct Keys<'a, K, V, H> {
350    raw: RawIter<Entry<K, V>>,
351    _phantom: PhantomData<&'a ArchivedHashMap<K, V, H>>,
352}
353
354impl<'a, K, V, H> Iterator for Keys<'a, K, V, H> {
355    type Item = &'a K;
356
357    fn next(&mut self) -> Option<Self::Item> {
358        self.raw.next().map(|entry| {
359            let entry = unsafe { entry.as_ref() };
360            &entry.key
361        })
362    }
363}
364
365impl<K, V, H> ExactSizeIterator for Keys<'_, K, V, H> {
366    fn len(&self) -> usize {
367        self.raw.len()
368    }
369}
370
371impl<K, V, H> FusedIterator for Keys<'_, K, V, H> {}
372
373/// An iterator over the values of an [`ArchivedHashMap`].
374pub struct Values<'a, K, V, H> {
375    raw: RawIter<Entry<K, V>>,
376    _phantom: PhantomData<&'a ArchivedHashMap<K, V, H>>,
377}
378
379impl<'a, K, V, H> Iterator for Values<'a, K, V, H> {
380    type Item = &'a V;
381
382    fn next(&mut self) -> Option<Self::Item> {
383        self.raw.next().map(|entry| {
384            let entry = unsafe { entry.as_ref() };
385            &entry.value
386        })
387    }
388}
389
390impl<K, V, H> ExactSizeIterator for Values<'_, K, V, H> {
391    fn len(&self) -> usize {
392        self.raw.len()
393    }
394}
395
396impl<K, V, H> FusedIterator for Values<'_, K, V, H> {}
397
398/// An iterator over the mutable values of an [`ArchivedHashMap`].
399pub struct ValuesMut<'a, K, V, H> {
400    raw: RawIter<Entry<K, V>>,
401    _phantom: PhantomData<&'a ArchivedHashMap<K, V, H>>,
402}
403
404impl<'a, K, V, H> Iterator for ValuesMut<'a, K, V, H> {
405    type Item = Seal<'a, V>;
406
407    fn next(&mut self) -> Option<Self::Item> {
408        self.raw.next().map(|mut entry| {
409            let entry = unsafe { entry.as_mut() };
410            Seal::new(&mut entry.value)
411        })
412    }
413}
414
415impl<K, V, H> ExactSizeIterator for ValuesMut<'_, K, V, H> {
416    fn len(&self) -> usize {
417        self.raw.len()
418    }
419}
420
421impl<K, V, H> FusedIterator for ValuesMut<'_, K, V, H> {}
rkyv/collections/swiss_table/map.rs

rkyv/collections/swiss_table/
map.rs
