rkyv/collections/hash_map/
mod.rs

1//! Archived hash map implementation.
2//!
3//! During archiving, hashmaps are built into minimal perfect hashmaps using
4//! [compress, hash and displace](http://cmph.sourceforge.net/papers/esa09.pdf).
5
6#[cfg(feature = "validation")]
7pub mod validation;
8
9use crate::{
10    collections::{
11        hash_index::{ArchivedHashIndex, HashIndexResolver},
12        util::Entry,
13    },
14    RelPtr,
15};
16#[cfg(feature = "alloc")]
17use crate::{
18    ser::{ScratchSpace, Serializer},
19    Serialize,
20};
21use core::{
22    borrow::Borrow, fmt, hash::Hash, iter::FusedIterator, marker::PhantomData, ops::Index, pin::Pin,
23};
24
25/// An archived `HashMap`.
26#[cfg_attr(feature = "strict", repr(C))]
27pub struct ArchivedHashMap<K, V> {
28    index: ArchivedHashIndex,
29    entries: RelPtr<Entry<K, V>>,
30}
31
32impl<K, V> ArchivedHashMap<K, V> {
33    /// Gets the number of items in the hash map.
34    #[inline]
35    pub const fn len(&self) -> usize {
36        self.index.len()
37    }
38
39    /// Gets the hasher for this hashmap. The hasher for all archived hashmaps is the same for
40    /// reproducibility.
41    #[inline]
42    pub fn hasher(&self) -> seahash::SeaHasher {
43        self.index.hasher()
44    }
45
46    #[inline]
47    unsafe fn entry(&self, index: usize) -> &Entry<K, V> {
48        &*self.entries.as_ptr().add(index)
49    }
50
51    #[inline]
52    unsafe fn entry_mut(&mut self, index: usize) -> &mut Entry<K, V> {
53        &mut *self.entries.as_mut_ptr().add(index)
54    }
55
56    #[inline]
57    fn find<Q: ?Sized>(&self, k: &Q) -> Option<usize>
58    where
59        K: Borrow<Q>,
60        Q: Hash + Eq,
61    {
62        self.index.index(k).and_then(|i| {
63            let entry = unsafe { self.entry(i) };
64            if entry.key.borrow() == k {
65                Some(i)
66            } else {
67                None
68            }
69        })
70    }
71
72    /// Finds the key-value entry for a key.
73    #[inline]
74    pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
75    where
76        K: Borrow<Q>,
77        Q: Hash + Eq,
78    {
79        self.find(k).map(move |index| {
80            let entry = unsafe { self.entry(index) };
81            (&entry.key, &entry.value)
82        })
83    }
84
85    /// Finds the mutable key-value entry for a key.
86    #[inline]
87    pub fn get_key_value_pin<Q: ?Sized>(self: Pin<&mut Self>, k: &Q) -> Option<(&K, Pin<&mut V>)>
88    where
89        K: Borrow<Q>,
90        Q: Hash + Eq,
91    {
92        unsafe {
93            let hash_map = self.get_unchecked_mut();
94            hash_map.find(k).map(move |index| {
95                let entry = hash_map.entry_mut(index);
96                (&entry.key, Pin::new_unchecked(&mut entry.value))
97            })
98        }
99    }
100
101    /// Returns whether a key is present in the hash map.
102    #[inline]
103    pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
104    where
105        K: Borrow<Q>,
106        Q: Hash + Eq,
107    {
108        self.find(k).is_some()
109    }
110
111    /// Gets the value associated with the given key.
112    #[inline]
113    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
114    where
115        K: Borrow<Q>,
116        Q: Hash + Eq,
117    {
118        self.find(k)
119            .map(|index| unsafe { &self.entry(index).value })
120    }
121
122    /// Gets the value associated with the given key, and matching the given predicate `F`.
123    ///
124    /// This method uses the hash of the given key and the provided comparison function to find a
125    /// matching element in the hash map. This is intended to be used when you are unable to
126    /// construct a key that fulfils the criteria of `get`.
127    ///
128    /// Note that hashes are not always guaranteed to match between Archived and non-archived
129    /// versions of the same struct. This is also the case for Archived types that are automatically
130    /// generated by `#[derive(Archive)]`. You should ensure that the hashing method matches between
131    /// your types, otherwise this method might not return any value even though a value matching
132    /// `comparison_predicate` exists.
133    ///
134    /// # Examples
135    ///
136    /// ```no_run
137    /// # use rkyv::string::ArchivedString;
138    /// # use rkyv::collections::ArchivedHashMap;
139    /// # fn get_your_hashmap() -> ArchivedHashMap<(ArchivedString, ArchivedString), ArchivedString> {
140    /// # panic!("Just some way of getting a hashmap that compiles");
141    /// # }
142    /// let your_hashmap: ArchivedHashMap<(ArchivedString, ArchivedString), ArchivedString> = get_your_hashmap();
143    /// let your_value = your_hashmap.get_with(
144    ///      &("my", "key"),
145    ///      |hashmap_key, your_key| &(hashmap_key.0.as_str(), hashmap_key.1.as_str()) == your_key
146    ///     );
147    /// ```
148    ///
149    #[inline]
150    pub fn get_with<Q: Hash + ?Sized, F: Fn(&K, &Q) -> bool>(
151        &self,
152        key: &Q,
153        comparison_predicate: F,
154    ) -> Option<&V> {
155        // Code adapted from self.find
156        self.index.index(key).and_then(|i| {
157            // Safety: We know the index for self.entry() here is right
158            // as it's returned by the underlying index, which should guarantee this invariant.
159            let entry = unsafe { self.entry(i) };
160            if comparison_predicate(&entry.key, key) {
161                Some(&entry.value)
162            } else {
163                None
164            }
165        })
166    }
167
168    /// Gets the mutable value associated with the given key.
169    #[inline]
170    pub fn get_pin<Q: ?Sized>(self: Pin<&mut Self>, k: &Q) -> Option<Pin<&mut V>>
171    where
172        K: Borrow<Q>,
173        Q: Hash + Eq,
174    {
175        unsafe {
176            let hash_map = self.get_unchecked_mut();
177            hash_map
178                .find(k)
179                .map(move |index| Pin::new_unchecked(&mut hash_map.entry_mut(index).value))
180        }
181    }
182
183    /// Returns `true` if the map contains no elements.
184    #[inline]
185    pub const fn is_empty(&self) -> bool {
186        self.len() == 0
187    }
188
189    #[inline]
190    fn raw_iter(&self) -> RawIter<K, V> {
191        RawIter::new(self.entries.as_ptr().cast(), self.len())
192    }
193
194    #[inline]
195    fn raw_iter_pin(self: Pin<&mut Self>) -> RawIterPin<K, V> {
196        unsafe {
197            let hash_map = self.get_unchecked_mut();
198            RawIterPin::new(hash_map.entries.as_mut_ptr().cast(), hash_map.len())
199        }
200    }
201
202    /// Gets an iterator over the key-value entries in the hash map.
203    #[inline]
204    pub fn iter(&self) -> Iter<K, V> {
205        Iter {
206            inner: self.raw_iter(),
207        }
208    }
209
210    /// Gets an iterator over the mutable key-value entries in the hash map.
211    #[inline]
212    pub fn iter_pin(self: Pin<&mut Self>) -> IterPin<K, V> {
213        IterPin {
214            inner: self.raw_iter_pin(),
215        }
216    }
217
218    /// Gets an iterator over the keys in the hash map.
219    #[inline]
220    pub fn keys(&self) -> Keys<K, V> {
221        Keys {
222            inner: self.raw_iter(),
223        }
224    }
225
226    /// Gets an iterator over the values in the hash map.
227    #[inline]
228    pub fn values(&self) -> Values<K, V> {
229        Values {
230            inner: self.raw_iter(),
231        }
232    }
233
234    /// Gets an iterator over the mutable values in the hash map.
235    #[inline]
236    pub fn values_pin(self: Pin<&mut Self>) -> ValuesPin<K, V> {
237        ValuesPin {
238            inner: self.raw_iter_pin(),
239        }
240    }
241
242    /// Resolves an archived hash map from a given length and parameters.
243    ///
244    /// # Safety
245    ///
246    /// - `len` must be the number of elements that were serialized
247    /// - `pos` must be the position of `out` within the archive
248    /// - `resolver` must be the result of serializing a hash map
249    #[inline]
250    pub unsafe fn resolve_from_len(
251        len: usize,
252        pos: usize,
253        resolver: HashMapResolver,
254        out: *mut Self,
255    ) {
256        let (fp, fo) = out_field!(out.index);
257        ArchivedHashIndex::resolve_from_len(len, pos + fp, resolver.index_resolver, fo);
258
259        let (fp, fo) = out_field!(out.entries);
260        RelPtr::emplace(pos + fp, resolver.entries_pos, fo);
261    }
262}
263
264#[cfg(feature = "alloc")]
265const _: () = {
266    impl<K, V> ArchivedHashMap<K, V> {
267        /// Serializes an iterator of key-value pairs as a hash map.
268        ///
269        /// # Safety
270        ///
271        /// The keys returned by the iterator must be unique.
272        pub unsafe fn serialize_from_iter<'a, KU, VU, S, I>(
273            iter: I,
274            serializer: &mut S,
275        ) -> Result<HashMapResolver, S::Error>
276        where
277            KU: 'a + Serialize<S, Archived = K> + Hash + Eq,
278            VU: 'a + Serialize<S, Archived = V>,
279            S: Serializer + ScratchSpace + ?Sized,
280            I: ExactSizeIterator<Item = (&'a KU, &'a VU)>,
281        {
282            use crate::ScratchVec;
283
284            let len = iter.len();
285
286            let mut entries = ScratchVec::new(serializer, len)?;
287            entries.set_len(len);
288            let index_resolver =
289                ArchivedHashIndex::build_and_serialize(iter, serializer, &mut entries)?;
290            let mut entries = entries.assume_init();
291
292            // Serialize entries
293            let mut resolvers = ScratchVec::new(serializer, len)?;
294            for (key, value) in entries.iter() {
295                resolvers.push((key.serialize(serializer)?, value.serialize(serializer)?));
296            }
297
298            let entries_pos = serializer.align_for::<Entry<K, V>>()?;
299            for ((key, value), (key_resolver, value_resolver)) in
300                entries.drain(..).zip(resolvers.drain(..))
301            {
302                serializer
303                    .resolve_aligned(&Entry { key, value }, (key_resolver, value_resolver))?;
304            }
305
306            // Free scratch vecs
307            resolvers.free(serializer)?;
308            entries.free(serializer)?;
309
310            Ok(HashMapResolver {
311                index_resolver,
312                entries_pos,
313            })
314        }
315    }
316};
317
318impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for ArchivedHashMap<K, V> {
319    #[inline]
320    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
321        f.debug_map().entries(self.iter()).finish()
322    }
323}
324
325impl<K: Hash + Eq, V: Eq> Eq for ArchivedHashMap<K, V> {}
326
327impl<K: Eq + Hash + Borrow<Q>, Q: Eq + Hash + ?Sized, V> Index<&'_ Q> for ArchivedHashMap<K, V> {
328    type Output = V;
329
330    #[inline]
331    fn index(&self, key: &Q) -> &V {
332        self.get(key).unwrap()
333    }
334}
335
336impl<K: Hash + Eq, V: PartialEq> PartialEq for ArchivedHashMap<K, V> {
337    #[inline]
338    fn eq(&self, other: &Self) -> bool {
339        if self.len() != other.len() {
340            false
341        } else {
342            self.iter()
343                .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
344        }
345    }
346}
347
348struct RawIter<'a, K, V> {
349    current: *const Entry<K, V>,
350    remaining: usize,
351    _phantom: PhantomData<(&'a K, &'a V)>,
352}
353
354impl<'a, K, V> RawIter<'a, K, V> {
355    #[inline]
356    fn new(pairs: *const Entry<K, V>, len: usize) -> Self {
357        Self {
358            current: pairs,
359            remaining: len,
360            _phantom: PhantomData,
361        }
362    }
363}
364
365impl<'a, K, V> Iterator for RawIter<'a, K, V> {
366    type Item = *const Entry<K, V>;
367
368    #[inline]
369    fn next(&mut self) -> Option<Self::Item> {
370        unsafe {
371            if self.remaining == 0 {
372                None
373            } else {
374                let result = self.current;
375                self.current = self.current.add(1);
376                self.remaining -= 1;
377                Some(result)
378            }
379        }
380    }
381
382    #[inline]
383    fn size_hint(&self) -> (usize, Option<usize>) {
384        (self.remaining, Some(self.remaining))
385    }
386}
387
388impl<'a, K, V> ExactSizeIterator for RawIter<'a, K, V> {}
389impl<'a, K, V> FusedIterator for RawIter<'a, K, V> {}
390
391struct RawIterPin<'a, K, V> {
392    current: *mut Entry<K, V>,
393    remaining: usize,
394    _phantom: PhantomData<(&'a K, Pin<&'a mut V>)>,
395}
396
397impl<'a, K, V> RawIterPin<'a, K, V> {
398    #[inline]
399    fn new(pairs: *mut Entry<K, V>, len: usize) -> Self {
400        Self {
401            current: pairs,
402            remaining: len,
403            _phantom: PhantomData,
404        }
405    }
406}
407
408impl<'a, K, V> Iterator for RawIterPin<'a, K, V> {
409    type Item = *mut Entry<K, V>;
410
411    #[inline]
412    fn next(&mut self) -> Option<Self::Item> {
413        unsafe {
414            if self.remaining == 0 {
415                None
416            } else {
417                let result = self.current;
418                self.current = self.current.add(1);
419                self.remaining -= 1;
420                Some(result)
421            }
422        }
423    }
424
425    #[inline]
426    fn size_hint(&self) -> (usize, Option<usize>) {
427        (self.remaining, Some(self.remaining))
428    }
429}
430
431impl<K, V> ExactSizeIterator for RawIterPin<'_, K, V> {}
432impl<K, V> FusedIterator for RawIterPin<'_, K, V> {}
433
434/// An iterator over the key-value pairs of a hash map.
435#[repr(transparent)]
436pub struct Iter<'a, K, V> {
437    inner: RawIter<'a, K, V>,
438}
439
440impl<'a, K, V> Iterator for Iter<'a, K, V> {
441    type Item = (&'a K, &'a V);
442
443    #[inline]
444    fn next(&mut self) -> Option<Self::Item> {
445        self.inner.next().map(|x| unsafe {
446            let pair = &*x;
447            (&pair.key, &pair.value)
448        })
449    }
450
451    #[inline]
452    fn size_hint(&self) -> (usize, Option<usize>) {
453        self.inner.size_hint()
454    }
455}
456
457impl<K, V> ExactSizeIterator for Iter<'_, K, V> {}
458impl<K, V> FusedIterator for Iter<'_, K, V> {}
459
460/// An iterator over the mutable key-value pairs of a hash map.
461#[repr(transparent)]
462pub struct IterPin<'a, K, V> {
463    inner: RawIterPin<'a, K, V>,
464}
465
466impl<'a, K, V> Iterator for IterPin<'a, K, V> {
467    type Item = (&'a K, Pin<&'a mut V>);
468
469    #[inline]
470    fn next(&mut self) -> Option<Self::Item> {
471        self.inner.next().map(|x| unsafe {
472            let pair = &mut *x;
473            (&pair.key, Pin::new_unchecked(&mut pair.value))
474        })
475    }
476
477    #[inline]
478    fn size_hint(&self) -> (usize, Option<usize>) {
479        self.inner.size_hint()
480    }
481}
482
483impl<K, V> ExactSizeIterator for IterPin<'_, K, V> {}
484impl<K, V> FusedIterator for IterPin<'_, K, V> {}
485
486/// An iterator over the keys of a hash map.
487#[repr(transparent)]
488pub struct Keys<'a, K, V> {
489    inner: RawIter<'a, K, V>,
490}
491
492impl<'a, K, V> Iterator for Keys<'a, K, V> {
493    type Item = &'a K;
494
495    #[inline]
496    fn next(&mut self) -> Option<Self::Item> {
497        self.inner.next().map(|x| unsafe {
498            let pair = &*x;
499            &pair.key
500        })
501    }
502
503    #[inline]
504    fn size_hint(&self) -> (usize, Option<usize>) {
505        self.inner.size_hint()
506    }
507}
508
509impl<K, V> ExactSizeIterator for Keys<'_, K, V> {}
510impl<K, V> FusedIterator for Keys<'_, K, V> {}
511
512/// An iterator over the values of a hash map.
513#[repr(transparent)]
514pub struct Values<'a, K, V> {
515    inner: RawIter<'a, K, V>,
516}
517
518impl<'a, K, V> Iterator for Values<'a, K, V> {
519    type Item = &'a V;
520
521    #[inline]
522    fn next(&mut self) -> Option<Self::Item> {
523        self.inner.next().map(|x| unsafe {
524            let pair = &*x;
525            &pair.value
526        })
527    }
528
529    #[inline]
530    fn size_hint(&self) -> (usize, Option<usize>) {
531        self.inner.size_hint()
532    }
533}
534
535impl<K, V> ExactSizeIterator for Values<'_, K, V> {}
536impl<K, V> FusedIterator for Values<'_, K, V> {}
537
538/// An iterator over the mutable values of a hash map.
539#[repr(transparent)]
540pub struct ValuesPin<'a, K, V> {
541    inner: RawIterPin<'a, K, V>,
542}
543
544impl<'a, K, V> Iterator for ValuesPin<'a, K, V> {
545    type Item = Pin<&'a mut V>;
546
547    #[inline]
548    fn next(&mut self) -> Option<Self::Item> {
549        self.inner.next().map(|x| unsafe {
550            let pair = &mut *x;
551            Pin::new_unchecked(&mut pair.value)
552        })
553    }
554
555    #[inline]
556    fn size_hint(&self) -> (usize, Option<usize>) {
557        self.inner.size_hint()
558    }
559}
560
561impl<K, V> ExactSizeIterator for ValuesPin<'_, K, V> {}
562impl<K, V> FusedIterator for ValuesPin<'_, K, V> {}
563
564/// The resolver for archived hash maps.
565pub struct HashMapResolver {
566    index_resolver: HashIndexResolver,
567    entries_pos: usize,
568}
rkyv/collections/hash_map/mod.rs

rkyv/collections/hash_map/
mod.rs
