rkyv_test/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 mutable value associated with the given key.
123    #[inline]
124    pub fn get_pin<Q: ?Sized>(self: Pin<&mut Self>, k: &Q) -> Option<Pin<&mut V>>
125    where
126        K: Borrow<Q>,
127        Q: Hash + Eq,
128    {
129        unsafe {
130            let hash_map = self.get_unchecked_mut();
131            hash_map
132                .find(k)
133                .map(move |index| Pin::new_unchecked(&mut hash_map.entry_mut(index).value))
134        }
135    }
136
137    /// Returns `true` if the map contains no elements.
138    #[inline]
139    pub const fn is_empty(&self) -> bool {
140        self.len() == 0
141    }
142
143    #[inline]
144    fn raw_iter(&self) -> RawIter<K, V> {
145        RawIter::new(self.entries.as_ptr().cast(), self.len())
146    }
147
148    #[inline]
149    fn raw_iter_pin(self: Pin<&mut Self>) -> RawIterPin<K, V> {
150        unsafe {
151            let hash_map = self.get_unchecked_mut();
152            RawIterPin::new(hash_map.entries.as_mut_ptr().cast(), hash_map.len())
153        }
154    }
155
156    /// Gets an iterator over the key-value entries in the hash map.
157    #[inline]
158    pub fn iter(&self) -> Iter<K, V> {
159        Iter {
160            inner: self.raw_iter(),
161        }
162    }
163
164    /// Gets an iterator over the mutable key-value entries in the hash map.
165    #[inline]
166    pub fn iter_pin(self: Pin<&mut Self>) -> IterPin<K, V> {
167        IterPin {
168            inner: self.raw_iter_pin(),
169        }
170    }
171
172    /// Gets an iterator over the keys in the hash map.
173    #[inline]
174    pub fn keys(&self) -> Keys<K, V> {
175        Keys {
176            inner: self.raw_iter(),
177        }
178    }
179
180    /// Gets an iterator over the values in the hash map.
181    #[inline]
182    pub fn values(&self) -> Values<K, V> {
183        Values {
184            inner: self.raw_iter(),
185        }
186    }
187
188    /// Gets an iterator over the mutable values in the hash map.
189    #[inline]
190    pub fn values_pin(self: Pin<&mut Self>) -> ValuesPin<K, V> {
191        ValuesPin {
192            inner: self.raw_iter_pin(),
193        }
194    }
195
196    /// Resolves an archived hash map from a given length and parameters.
197    ///
198    /// # Safety
199    ///
200    /// - `len` must be the number of elements that were serialized
201    /// - `pos` must be the position of `out` within the archive
202    /// - `resolver` must be the result of serializing a hash map
203    #[inline]
204    pub unsafe fn resolve_from_len(
205        len: usize,
206        pos: usize,
207        resolver: HashMapResolver,
208        out: *mut Self,
209    ) {
210        let (fp, fo) = out_field!(out.index);
211        ArchivedHashIndex::resolve_from_len(len, pos + fp, resolver.index_resolver, fo);
212
213        let (fp, fo) = out_field!(out.entries);
214        RelPtr::emplace(pos + fp, resolver.entries_pos, fo);
215    }
216}
217
218#[cfg(feature = "alloc")]
219const _: () = {
220    impl<K, V> ArchivedHashMap<K, V> {
221        /// Serializes an iterator of key-value pairs as a hash map.
222        ///
223        /// # Safety
224        ///
225        /// The keys returned by the iterator must be unique.
226        pub unsafe fn serialize_from_iter<'a, KU, VU, S, I>(
227            iter: I,
228            serializer: &mut S,
229        ) -> Result<HashMapResolver, S::Error>
230        where
231            KU: 'a + Serialize<S, Archived = K> + Hash + Eq,
232            VU: 'a + Serialize<S, Archived = V>,
233            S: Serializer + ScratchSpace + ?Sized,
234            I: ExactSizeIterator<Item = (&'a KU, &'a VU)>,
235        {
236            use crate::ScratchVec;
237
238            let len = iter.len();
239
240            let mut entries = ScratchVec::new(serializer, len)?;
241            entries.set_len(len);
242            let index_resolver =
243                ArchivedHashIndex::build_and_serialize(iter, serializer, &mut entries)?;
244            let mut entries = entries.assume_init();
245
246            // Serialize entries
247            let mut resolvers = ScratchVec::new(serializer, len)?;
248            for (key, value) in entries.iter() {
249                resolvers.push((key.serialize(serializer)?, value.serialize(serializer)?));
250            }
251
252            let entries_pos = serializer.align_for::<Entry<K, V>>()?;
253            for ((key, value), (key_resolver, value_resolver)) in
254                entries.drain(..).zip(resolvers.drain(..))
255            {
256                serializer
257                    .resolve_aligned(&Entry { key, value }, (key_resolver, value_resolver))?;
258            }
259
260            // Free scratch vecs
261            resolvers.free(serializer)?;
262            entries.free(serializer)?;
263
264            Ok(HashMapResolver {
265                index_resolver,
266                entries_pos,
267            })
268        }
269    }
270};
271
272impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for ArchivedHashMap<K, V> {
273    #[inline]
274    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
275        f.debug_map().entries(self.iter()).finish()
276    }
277}
278
279impl<K: Hash + Eq, V: Eq> Eq for ArchivedHashMap<K, V> {}
280
281impl<K: Eq + Hash + Borrow<Q>, Q: Eq + Hash + ?Sized, V> Index<&'_ Q> for ArchivedHashMap<K, V> {
282    type Output = V;
283
284    #[inline]
285    fn index(&self, key: &Q) -> &V {
286        self.get(key).unwrap()
287    }
288}
289
290impl<K: Hash + Eq, V: PartialEq> PartialEq for ArchivedHashMap<K, V> {
291    #[inline]
292    fn eq(&self, other: &Self) -> bool {
293        if self.len() != other.len() {
294            false
295        } else {
296            self.iter()
297                .all(|(key, value)| other.get(key).map_or(false, |v| *value == *v))
298        }
299    }
300}
301
302struct RawIter<'a, K, V> {
303    current: *const Entry<K, V>,
304    remaining: usize,
305    _phantom: PhantomData<(&'a K, &'a V)>,
306}
307
308impl<'a, K, V> RawIter<'a, K, V> {
309    #[inline]
310    fn new(pairs: *const Entry<K, V>, len: usize) -> Self {
311        Self {
312            current: pairs,
313            remaining: len,
314            _phantom: PhantomData,
315        }
316    }
317}
318
319impl<'a, K, V> Iterator for RawIter<'a, K, V> {
320    type Item = *const Entry<K, V>;
321
322    #[inline]
323    fn next(&mut self) -> Option<Self::Item> {
324        unsafe {
325            if self.remaining == 0 {
326                None
327            } else {
328                let result = self.current;
329                self.current = self.current.add(1);
330                self.remaining -= 1;
331                Some(result)
332            }
333        }
334    }
335
336    #[inline]
337    fn size_hint(&self) -> (usize, Option<usize>) {
338        (self.remaining, Some(self.remaining))
339    }
340}
341
342impl<'a, K, V> ExactSizeIterator for RawIter<'a, K, V> {}
343impl<'a, K, V> FusedIterator for RawIter<'a, K, V> {}
344
345struct RawIterPin<'a, K, V> {
346    current: *mut Entry<K, V>,
347    remaining: usize,
348    _phantom: PhantomData<(&'a K, Pin<&'a mut V>)>,
349}
350
351impl<'a, K, V> RawIterPin<'a, K, V> {
352    #[inline]
353    fn new(pairs: *mut Entry<K, V>, len: usize) -> Self {
354        Self {
355            current: pairs,
356            remaining: len,
357            _phantom: PhantomData,
358        }
359    }
360}
361
362impl<'a, K, V> Iterator for RawIterPin<'a, K, V> {
363    type Item = *mut Entry<K, V>;
364
365    #[inline]
366    fn next(&mut self) -> Option<Self::Item> {
367        unsafe {
368            if self.remaining == 0 {
369                None
370            } else {
371                let result = self.current;
372                self.current = self.current.add(1);
373                self.remaining -= 1;
374                Some(result)
375            }
376        }
377    }
378
379    #[inline]
380    fn size_hint(&self) -> (usize, Option<usize>) {
381        (self.remaining, Some(self.remaining))
382    }
383}
384
385impl<K, V> ExactSizeIterator for RawIterPin<'_, K, V> {}
386impl<K, V> FusedIterator for RawIterPin<'_, K, V> {}
387
388/// An iterator over the key-value pairs of a hash map.
389#[repr(transparent)]
390pub struct Iter<'a, K, V> {
391    inner: RawIter<'a, K, V>,
392}
393
394impl<'a, K, V> Iterator for Iter<'a, K, V> {
395    type Item = (&'a K, &'a V);
396
397    #[inline]
398    fn next(&mut self) -> Option<Self::Item> {
399        self.inner.next().map(|x| unsafe {
400            let pair = &*x;
401            (&pair.key, &pair.value)
402        })
403    }
404
405    #[inline]
406    fn size_hint(&self) -> (usize, Option<usize>) {
407        self.inner.size_hint()
408    }
409}
410
411impl<K, V> ExactSizeIterator for Iter<'_, K, V> {}
412impl<K, V> FusedIterator for Iter<'_, K, V> {}
413
414/// An iterator over the mutable key-value pairs of a hash map.
415#[repr(transparent)]
416pub struct IterPin<'a, K, V> {
417    inner: RawIterPin<'a, K, V>,
418}
419
420impl<'a, K, V> Iterator for IterPin<'a, K, V> {
421    type Item = (&'a K, Pin<&'a mut V>);
422
423    #[inline]
424    fn next(&mut self) -> Option<Self::Item> {
425        self.inner.next().map(|x| unsafe {
426            let pair = &mut *x;
427            (&pair.key, Pin::new_unchecked(&mut pair.value))
428        })
429    }
430
431    #[inline]
432    fn size_hint(&self) -> (usize, Option<usize>) {
433        self.inner.size_hint()
434    }
435}
436
437impl<K, V> ExactSizeIterator for IterPin<'_, K, V> {}
438impl<K, V> FusedIterator for IterPin<'_, K, V> {}
439
440/// An iterator over the keys of a hash map.
441#[repr(transparent)]
442pub struct Keys<'a, K, V> {
443    inner: RawIter<'a, K, V>,
444}
445
446impl<'a, K, V> Iterator for Keys<'a, K, V> {
447    type Item = &'a K;
448
449    #[inline]
450    fn next(&mut self) -> Option<Self::Item> {
451        self.inner.next().map(|x| unsafe {
452            let pair = &*x;
453            &pair.key
454        })
455    }
456
457    #[inline]
458    fn size_hint(&self) -> (usize, Option<usize>) {
459        self.inner.size_hint()
460    }
461}
462
463impl<K, V> ExactSizeIterator for Keys<'_, K, V> {}
464impl<K, V> FusedIterator for Keys<'_, K, V> {}
465
466/// An iterator over the values of a hash map.
467#[repr(transparent)]
468pub struct Values<'a, K, V> {
469    inner: RawIter<'a, K, V>,
470}
471
472impl<'a, K, V> Iterator for Values<'a, K, V> {
473    type Item = &'a V;
474
475    #[inline]
476    fn next(&mut self) -> Option<Self::Item> {
477        self.inner.next().map(|x| unsafe {
478            let pair = &*x;
479            &pair.value
480        })
481    }
482
483    #[inline]
484    fn size_hint(&self) -> (usize, Option<usize>) {
485        self.inner.size_hint()
486    }
487}
488
489impl<K, V> ExactSizeIterator for Values<'_, K, V> {}
490impl<K, V> FusedIterator for Values<'_, K, V> {}
491
492/// An iterator over the mutable values of a hash map.
493#[repr(transparent)]
494pub struct ValuesPin<'a, K, V> {
495    inner: RawIterPin<'a, K, V>,
496}
497
498impl<'a, K, V> Iterator for ValuesPin<'a, K, V> {
499    type Item = Pin<&'a mut V>;
500
501    #[inline]
502    fn next(&mut self) -> Option<Self::Item> {
503        self.inner.next().map(|x| unsafe {
504            let pair = &mut *x;
505            Pin::new_unchecked(&mut pair.value)
506        })
507    }
508
509    #[inline]
510    fn size_hint(&self) -> (usize, Option<usize>) {
511        self.inner.size_hint()
512    }
513}
514
515impl<K, V> ExactSizeIterator for ValuesPin<'_, K, V> {}
516impl<K, V> FusedIterator for ValuesPin<'_, K, V> {}
517
518/// The resolver for archived hash maps.
519pub struct HashMapResolver {
520    index_resolver: HashIndexResolver,
521    entries_pos: usize,
522}
rkyv_test/collections/hash_map/mod.rs

rkyv_test/collections/hash_map/
mod.rs
