rkyv/collections/
index_set.rs

1//! Archived index set implementation.
2//!
3//! During archiving, index sets are built into minimal perfect index sets using
4//! [compress, hash and displace](http://cmph.sourceforge.net/papers/esa09.pdf).
5
6use crate::{
7    collections::{
8        hash_index::HashBuilder,
9        index_map::{ArchivedIndexMap, IndexMapResolver, Keys},
10    },
11    out_field,
12};
13use core::{borrow::Borrow, fmt, hash::Hash};
14
15/// An archived `IndexSet`.
16#[cfg_attr(feature = "validation", derive(bytecheck::CheckBytes))]
17#[repr(transparent)]
18pub struct ArchivedIndexSet<K> {
19    inner: ArchivedIndexMap<K, ()>,
20}
21
22impl<K> ArchivedIndexSet<K> {
23    /// Returns whether a key is present in the hash set.
24    #[inline]
25    pub fn contains<Q: ?Sized>(&self, k: &Q) -> bool
26    where
27        K: Borrow<Q>,
28        Q: Hash + Eq,
29    {
30        self.inner.contains_key(k)
31    }
32
33    /// Returns the first key.
34    #[inline]
35    pub fn first(&self) -> Option<&K> {
36        self.inner.first().map(|(k, _)| k)
37    }
38
39    /// Returns the value stored in the set, if any.
40    #[inline]
41    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&K>
42    where
43        K: Borrow<Q>,
44        Q: Hash + Eq,
45    {
46        self.inner.get_full(k).map(|(_, k, _)| k)
47    }
48
49    /// Returns the item index and value stored in the set, if any.
50    #[inline]
51    pub fn get_full<Q: ?Sized>(&self, k: &Q) -> Option<(usize, &K)>
52    where
53        K: Borrow<Q>,
54        Q: Hash + Eq,
55    {
56        self.inner.get_full(k).map(|(i, k, _)| (i, k))
57    }
58
59    /// Gets a key by index.
60    #[inline]
61    pub fn get_index(&self, index: usize) -> Option<&K> {
62        self.inner.get_index(index).map(|(k, _)| k)
63    }
64
65    /// Returns the index of a key if it exists in the set.
66    #[inline]
67    pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize>
68    where
69        K: Borrow<Q>,
70        Q: Hash + Eq,
71    {
72        self.inner.get_index_of(key)
73    }
74
75    /// Gets the hasher for this index set.
76    #[inline]
77    pub fn hasher(&self) -> HashBuilder {
78        self.inner.hasher()
79    }
80
81    /// Returns whether the index set contains no values.
82    #[inline]
83    pub fn is_empty(&self) -> bool {
84        self.inner.is_empty()
85    }
86
87    /// Returns an iterator over the keys of the index set in order.
88    #[inline]
89    pub fn iter(&self) -> Keys<K, ()> {
90        self.inner.keys()
91    }
92
93    /// Returns the last key.
94    #[inline]
95    pub fn last(&self) -> Option<&K> {
96        self.inner.last().map(|(k, _)| k)
97    }
98
99    /// Returns the number of elements in the index set.
100    #[inline]
101    pub fn len(&self) -> usize {
102        self.inner.len()
103    }
104
105    /// Resolves an archived index map from a given length and parameters.
106    ///
107    /// # Safety
108    ///
109    /// - `len` must be the number of elements that were serialized
110    /// - `pos` must be the position of `out` within the archive
111    /// - `resolver` must be the result of serializing a hash map
112    #[inline]
113    pub unsafe fn resolve_from_len(
114        len: usize,
115        pos: usize,
116        resolver: IndexSetResolver,
117        out: *mut Self,
118    ) {
119        let (fp, fo) = out_field!(out.inner);
120        ArchivedIndexMap::resolve_from_len(len, pos + fp, resolver.0, fo);
121    }
122}
123
124#[cfg(feature = "alloc")]
125const _: () = {
126    use crate::{
127        ser::{ScratchSpace, Serializer},
128        Serialize,
129    };
130
131    impl<K> ArchivedIndexSet<K> {
132        /// Serializes an iterator of keys as an index set.
133        ///
134        /// # Safety
135        ///
136        /// - The keys returned by the iterator must be unique
137        /// - The index function must return the index of the given key within the iterator
138        #[inline]
139        pub unsafe fn serialize_from_iter_index<'a, UK, I, F, S>(
140            iter: I,
141            index: F,
142            serializer: &mut S,
143        ) -> Result<IndexSetResolver, S::Error>
144        where
145            UK: 'a + Hash + Eq + Serialize<S, Archived = K>,
146            I: Clone + ExactSizeIterator<Item = &'a UK>,
147            F: Fn(&UK) -> usize,
148            S: ScratchSpace + Serializer + ?Sized,
149        {
150            Ok(IndexSetResolver(
151                ArchivedIndexMap::serialize_from_iter_index(
152                    iter.map(|k| (k, &())),
153                    index,
154                    serializer,
155                )?,
156            ))
157        }
158    }
159};
160
161impl<K: fmt::Debug> fmt::Debug for ArchivedIndexSet<K> {
162    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
163        f.debug_set().entries(self.iter()).finish()
164    }
165}
166
167impl<K: PartialEq> PartialEq for ArchivedIndexSet<K> {
168    fn eq(&self, other: &Self) -> bool {
169        self.iter().eq(other.iter())
170    }
171}
172
173/// The resolver for `IndexSet`.
174pub struct IndexSetResolver(IndexMapResolver);
rkyv/collections/index_set.rs

rkyv/collections/
index_set.rs
