musli_zerocopy/swiss/
set.rs

1//! A set which implements a hash-set like interface, where values can be looked
2//! up by keys.
3//!
4//! This set are implemented using a perfect hash functions, and are inserted
5//! into a buffering using [`swiss::store_set`].
6//!
7//! There's two types provided by this module:
8//! * [`Set<T>`] which is a *bound* reference to a set, providing a convenient
9//!   set-like access.
10//! * [`SetRef<T>`] which is the *pointer* of the set. This is what you store in
11//!   [`ZeroCopy`] types and is what is returned by [`swiss::store_set`].
12//!
13//! [`swiss::store_set`]: crate::swiss::store_set
14
15use core::borrow::Borrow;
16use core::hash::{Hash, Hasher};
17
18use crate::ZeroCopy;
19use crate::buf::{Bindable, Buf, Visit};
20use crate::endian::{ByteOrder, Native};
21use crate::error::Error;
22use crate::pointer::{DefaultSize, Size};
23use crate::sip::SipHasher13;
24use crate::swiss::map::{RawTable, RawTableRef};
25
26/// A set bound to a [`Buf`] through [`Buf::bind`] for convenience.
27///
28/// ## Examples
29///
30/// ```
31/// use musli_zerocopy::OwnedBuf;
32/// use musli_zerocopy::swiss;
33///
34/// let mut buf = OwnedBuf::new();
35///
36/// let set = swiss::store_set(&mut buf, [1, 2])?;
37/// let set = buf.bind(set)?;
38///
39/// assert!(set.contains(&1)?);
40/// assert!(set.contains(&2)?);
41/// assert!(!set.contains(&3)?);
42/// # Ok::<_, musli_zerocopy::Error>(())
43/// ```
44pub struct Set<'a, T> {
45    key: u64,
46    table: RawTable<'a, T>,
47    buf: &'a Buf,
48}
49
50impl<T> Set<'_, T>
51where
52    T: ZeroCopy,
53{
54    /// Test if the set contains the given `value`.
55    ///
56    /// ## Examples
57    ///
58    /// ```
59    /// use musli_zerocopy::OwnedBuf;
60    /// use musli_zerocopy::swiss;
61    ///
62    /// let mut buf = OwnedBuf::new();
63    ///
64    /// let set = swiss::store_set(&mut buf, [1, 2])?;
65    /// let set = buf.bind(set)?;
66    ///
67    /// assert!(set.contains(&1)?);
68    /// assert!(set.contains(&2)?);
69    /// assert!(!set.contains(&3)?);
70    /// # Ok::<_, musli_zerocopy::Error>(())
71    /// ```
72    pub fn contains<Q>(&self, value: &Q) -> Result<bool, Error>
73    where
74        Q: ?Sized + Visit,
75        Q::Target: Eq + Hash,
76        T: Visit,
77        T::Target: Borrow<Q::Target>,
78    {
79        let hash = value.visit(self.buf, |k| self.hash(k))?;
80
81        let entry = self.table.find(hash, |e| {
82            value.visit(self.buf, |b| e.visit(self.buf, |a| a.borrow() == b))?
83        })?;
84
85        Ok(entry.is_some())
86    }
87
88    fn hash<H>(&self, value: &H) -> u64
89    where
90        H: ?Sized + Hash,
91    {
92        let mut hasher = SipHasher13::new_with_keys(0, self.key);
93        value.hash(&mut hasher);
94        hasher.finish()
95    }
96}
97
98/// Bind a [`SetRef`] into a [`Set`].
99impl<T, E, O> Bindable for SetRef<T, E, O>
100where
101    T: ZeroCopy,
102    E: ByteOrder,
103    O: Size,
104{
105    type Bound<'a>
106        = Set<'a, T>
107    where
108        Self: 'a;
109
110    #[inline]
111    fn bind(self, buf: &Buf) -> Result<Self::Bound<'_>, Error> {
112        Ok(Set {
113            key: self.key,
114            table: self.table.bind(buf)?,
115            buf,
116        })
117    }
118}
119
120/// A stored reference to a set.
121///
122/// Note that operating over the methods provided in [`SetRef`] does not demand
123/// that the entire contents of the set is validated as would be the case when
124/// [`bind()`] is used and might result in better performance if the data is
125/// infrequently accessed.
126///
127/// Constructed through [`swiss::store_set`].
128///
129/// [`swiss::store_set`]: crate::swiss::store_set
130/// [`bind()`]: crate::buf::Buf::bind
131///
132/// ## Examples
133///
134/// ```
135/// use musli_zerocopy::OwnedBuf;
136/// use musli_zerocopy::swiss;
137///
138/// let mut buf = OwnedBuf::new();
139///
140/// let set = swiss::store_set(&mut buf, [1, 2])?;
141///
142/// assert!(set.contains(&buf, &1)?);
143/// assert!(!set.contains(&buf, &3)?);
144/// # Ok::<_, musli_zerocopy::Error>(())
145/// ```
146#[derive(Debug, ZeroCopy)]
147#[repr(C)]
148#[zero_copy(crate)]
149pub struct SetRef<T, E = Native, O = DefaultSize>
150where
151    T: ZeroCopy,
152    E: ByteOrder,
153    O: Size,
154{
155    key: u64,
156    table: RawTableRef<T, E, O>,
157}
158
159impl<T, E, O> SetRef<T, E, O>
160where
161    T: ZeroCopy,
162    E: ByteOrder,
163    O: Size,
164{
165    #[cfg(feature = "alloc")]
166    pub(crate) fn new(key: u64, table: RawTableRef<T, E, O>) -> Self {
167        Self { key, table }
168    }
169
170    /// Test if the set contains the given `key`.
171    ///
172    /// ## Examples
173    ///
174    /// ```
175    /// use musli_zerocopy::OwnedBuf;
176    /// use musli_zerocopy::swiss;
177    ///
178    /// let mut buf = OwnedBuf::new();
179    ///
180    /// let set = swiss::store_set(&mut buf, [1, 2])?;
181    ///
182    /// assert!(set.contains(&buf, &1)?);
183    /// assert!(set.contains(&buf, &2)?);
184    /// assert!(!set.contains(&buf, &3)?);
185    /// # Ok::<_, musli_zerocopy::Error>(())
186    /// ```
187    pub fn contains<Q>(&self, buf: &Buf, key: &Q) -> Result<bool, Error>
188    where
189        Q: ?Sized + Visit,
190        Q::Target: Eq + Hash,
191        T: Visit,
192        T::Target: Borrow<Q::Target>,
193    {
194        let hash = key.visit(buf, |key| self.hash(key))?;
195
196        let entry = self.table.find(buf, hash, |e| {
197            key.visit(buf, |b| e.visit(buf, |a| a.borrow() == b))?
198        })?;
199
200        Ok(entry.is_some())
201    }
202
203    fn hash<H>(&self, value: &H) -> u64
204    where
205        H: ?Sized + Hash,
206    {
207        let mut hasher = SipHasher13::new_with_keys(0, self.key);
208        value.hash(&mut hasher);
209        hasher.finish()
210    }
211}
musli_zerocopy/swiss/set.rs

musli_zerocopy/swiss/
set.rs
