kevy_map/
set.rs

1//! `HashSet`-shaped wrapper over [`KevyMap<K, ()>`] — same per-shard /
2//! single-trust-domain assumptions; exposes the underlying map's bucket-addr
3//! API via [`KevySet::as_map`].
4
5use core::borrow::Borrow;
6use core::fmt;
7
8use kevy_hash::KevyHash;
9
10use crate::iter::Iter;
11use crate::map::KevyMap;
12
13/// `HashSet`-shaped wrapper over [`KevyMap<K, ()>`].
14///
15/// Carries the same per-shard / single-trust-domain assumptions; differs from
16/// `std::HashSet` only by hashing through [`KevyHash`] (one-call inlinable)
17/// and exposing the underlying `KevyMap`'s bucket-address API via
18/// [`KevySet::as_map`] for callers that want prefetch.
19#[derive(Clone)]
20pub struct KevySet<K>(KevyMap<K, ()>);
21
22impl<K> KevySet<K> {
23    /// Construct an empty set without allocating.
24    pub fn new() -> Self {
25        Self(KevyMap::new())
26    }
27
28    /// Construct a set sized for `cap_hint` members without growing.
29    pub fn with_capacity(cap_hint: usize) -> Self {
30        Self(KevyMap::with_capacity(cap_hint))
31    }
32
33    /// Live member count.
34    #[inline]
35    pub fn len(&self) -> usize {
36        self.0.len()
37    }
38    /// Whether `len() == 0`.
39    #[inline]
40    pub fn is_empty(&self) -> bool {
41        self.0.is_empty()
42    }
43    /// Allocated slot count of the underlying map.
44    #[inline]
45    pub fn capacity(&self) -> usize {
46        self.0.capacity()
47    }
48    /// Drop every member and reset the metadata. Keeps the allocation.
49    pub fn clear(&mut self) {
50        self.0.clear();
51    }
52
53    /// `&K` iterator over all members (unspecified order).
54    pub fn iter(&self) -> SetIter<'_, K> {
55        SetIter(self.0.iter())
56    }
57
58    /// Borrow the underlying map (gives access to the bucket-addr / prefetch
59    /// API).
60    /// An iterator that begins at slot `start` and wraps once around the whole
61    /// table. Take the first element for an arbitrary member in O(1) expected
62    /// time — the pattern SPOP and SRANDMEMBER need, and the one Redis's
63    /// `dictGetRandomKey` uses.
64    ///
65    /// Not perfectly uniform: a member sitting after a long run of empty slots
66    /// is likelier to be picked than one in a dense cluster. Redis has the same
67    /// bias for the same reason, and the contract is "arbitrary", not "uniform".
68    /// What it is NOT is the identical member every single time, which is what
69    /// `iter().next()` gives you.
70    pub fn iter_from_slot(&self, start: usize) -> impl Iterator<Item = &K> {
71        let cap = self.0.capacity();
72        let start = if cap == 0 { 0 } else { start % cap };
73        self.0
74            .iter_from_bucket(start)
75            .chain(self.0.iter().take(start))
76            .map(|(k, ())| k)
77    }
78
79    /// The backing map, for callers that want its bucket addresses (prefetch).
80    pub fn as_map(&self) -> &KevyMap<K, ()> {
81        &self.0
82    }
83}
84
85impl<K: KevyHash + Eq> KevySet<K> {
86    /// Insert `key`. Returns `true` if newly added, `false` if it was already
87    /// present (matches `HashSet::insert`).
88    pub fn insert(&mut self, key: K) -> bool {
89        self.0.insert(key, ()).is_none()
90    }
91}
92
93impl<K> KevySet<K> {
94    /// Whether `key` is a member of the set.
95    pub fn contains<Q>(&self, key: &Q) -> bool
96    where
97        K: Borrow<Q>,
98        Q: KevyHash + Eq + ?Sized,
99    {
100        self.0.contains_key(key)
101    }
102
103    /// Remove `key`; returns `true` if it was present (matches `HashSet::remove`).
104    pub fn remove<Q>(&mut self, key: &Q) -> bool
105    where
106        K: Borrow<Q>,
107        Q: KevyHash + Eq + ?Sized,
108    {
109        self.0.remove(key).is_some()
110    }
111}
112
113impl<K> Default for KevySet<K> {
114    fn default() -> Self {
115        Self::new()
116    }
117}
118
119impl<K: fmt::Debug> fmt::Debug for KevySet<K> {
120    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
121        f.debug_set().entries(self.iter()).finish()
122    }
123}
124
125/// `&K` iterator over all members of a [`KevySet`]; order unspecified.
126pub struct SetIter<'a, K>(Iter<'a, K, ()>);
127
128impl<'a, K> Iterator for SetIter<'a, K> {
129    type Item = &'a K;
130    fn next(&mut self) -> Option<Self::Item> {
131        self.0.next().map(|(k, ())| k)
132    }
133}
134
135impl<'a, K> IntoIterator for &'a KevySet<K> {
136    type Item = &'a K;
137    type IntoIter = SetIter<'a, K>;
138    fn into_iter(self) -> Self::IntoIter {
139        self.iter()
140    }
141}
142
143impl<K: KevyHash + Eq> FromIterator<K> for KevySet<K> {
144    fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self {
145        let iter = iter.into_iter();
146        let mut s = match iter.size_hint() {
147            (lo, Some(hi)) if hi <= lo.saturating_mul(2) => Self::with_capacity(hi),
148            (lo, _) => Self::with_capacity(lo),
149        };
150        for k in iter {
151            s.insert(k);
152        }
153        s
154    }
155}
156
157impl<K: KevyHash + Eq> Extend<K> for KevySet<K> {
158    fn extend<I: IntoIterator<Item = K>>(&mut self, iter: I) {
159        for k in iter {
160            self.insert(k);
161        }
162    }
163}
kevy_map/set.rs

kevy_map/
set.rs
