rkyv/collections/
hash_set.rs

1//! Archived hash set implementation.
2//!
3//! During archiving, hashsets are built into minimal perfect hashsets using
4//! [compress, hash and displace](http://cmph.sourceforge.net/papers/esa09.pdf).
5
6use crate::collections::hash_map::{ArchivedHashMap, HashMapResolver, Keys};
7#[cfg(feature = "alloc")]
8use crate::{
9    ser::{ScratchSpace, Serializer},
10    Serialize,
11};
12use core::{borrow::Borrow, fmt, hash::Hash};
13
14/// An archived `HashSet`. This is a wrapper around a hash map with the same key and a value of
15/// `()`.
16#[cfg_attr(feature = "validation", derive(bytecheck::CheckBytes))]
17#[repr(transparent)]
18pub struct ArchivedHashSet<K>(ArchivedHashMap<K, ()>);
19
20impl<K> ArchivedHashSet<K> {
21    /// Gets the number of items in the hash set.
22    #[inline]
23    pub const fn len(&self) -> usize {
24        self.0.len()
25    }
26
27    /// Gets the key corresponding to the given key in the hash set.
28    #[inline]
29    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&K>
30    where
31        K: Borrow<Q>,
32        Q: Hash + Eq,
33    {
34        self.0.get_key_value(k).map(|(k, _)| k)
35    }
36
37    /// Returns whether the given key is in the hash set.
38    #[inline]
39    pub fn contains<Q: ?Sized>(&self, k: &Q) -> bool
40    where
41        K: Borrow<Q>,
42        Q: Hash + Eq,
43    {
44        self.0.contains_key(k)
45    }
46
47    /// Gets the hasher for the underlying hash map.
48    #[cfg(feature = "alloc")]
49    #[inline]
50    pub fn hasher(&self) -> seahash::SeaHasher {
51        self.0.hasher()
52    }
53
54    /// Returns whether there are no items in the hash set.
55    #[inline]
56    pub const fn is_empty(&self) -> bool {
57        self.0.is_empty()
58    }
59
60    /// Gets an iterator over the keys of the underlying hash map.
61    #[inline]
62    pub fn iter(&self) -> Keys<K, ()> {
63        self.0.keys()
64    }
65
66    /// Resolves an archived hash set from the given length and parameters.
67    ///
68    /// # Safety
69    ///
70    /// - `len` must be the number of elements that were serialized
71    /// - `pos` must be the position of `out` within the archive
72    /// - `resolver` must be the result of serializing a hash map
73    #[inline]
74    pub unsafe fn resolve_from_len(
75        len: usize,
76        pos: usize,
77        resolver: HashSetResolver,
78        out: *mut Self,
79    ) {
80        let (fp, fo) = out_field!(out.0);
81        ArchivedHashMap::resolve_from_len(len, pos + fp, resolver.0, fo);
82    }
83
84    /// Serializes an iterator of keys as a hash set.
85    ///
86    /// # Safety
87    ///
88    /// The keys returned by the iterator must be unique.
89    #[cfg(feature = "alloc")]
90    #[inline]
91    pub unsafe fn serialize_from_iter<'a, KU, S, I>(
92        iter: I,
93        serializer: &mut S,
94    ) -> Result<HashSetResolver, S::Error>
95    where
96        KU: 'a + Serialize<S, Archived = K> + Hash + Eq,
97        S: Serializer + ScratchSpace + ?Sized,
98        I: ExactSizeIterator<Item = &'a KU>,
99    {
100        Ok(HashSetResolver(ArchivedHashMap::serialize_from_iter(
101            iter.map(|x| (x, &())),
102            serializer,
103        )?))
104    }
105}
106
107impl<K: fmt::Debug> fmt::Debug for ArchivedHashSet<K> {
108    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
109        f.debug_set().entries(self.iter()).finish()
110    }
111}
112
113/// The resolver for archived hash sets.
114pub struct HashSetResolver(HashMapResolver);
115
116impl<K: Hash + Eq> PartialEq for ArchivedHashSet<K> {
117    #[inline]
118    fn eq(&self, other: &Self) -> bool {
119        self.0 == other.0
120    }
121}
122
123impl<K: Hash + Eq> Eq for ArchivedHashSet<K> {}
rkyv/collections/hash_set.rs

rkyv/collections/
hash_set.rs
