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.iter_from_bucket(start).chain(self.0.iter().take(start)).map(|(k, ())| k)
74    }
75
76    /// The backing map, for callers that want its bucket addresses (prefetch).
77    pub fn as_map(&self) -> &KevyMap<K, ()> {
78        &self.0
79    }
80}
81
82impl<K: KevyHash + Eq> KevySet<K> {
83    /// Insert `key`. Returns `true` if newly added, `false` if it was already
84    /// present (matches `HashSet::insert`).
85    pub fn insert(&mut self, key: K) -> bool {
86        self.0.insert(key, ()).is_none()
87    }
88}
89
90impl<K> KevySet<K> {
91    /// Whether `key` is a member of the set.
92    pub fn contains<Q>(&self, key: &Q) -> bool
93    where
94        K: Borrow<Q>,
95        Q: KevyHash + Eq + ?Sized,
96    {
97        self.0.contains_key(key)
98    }
99
100    /// Remove `key`; returns `true` if it was present (matches `HashSet::remove`).
101    pub fn remove<Q>(&mut self, key: &Q) -> bool
102    where
103        K: Borrow<Q>,
104        Q: KevyHash + Eq + ?Sized,
105    {
106        self.0.remove(key).is_some()
107    }
108}
109
110impl<K> Default for KevySet<K> {
111    fn default() -> Self {
112        Self::new()
113    }
114}
115
116impl<K: fmt::Debug> fmt::Debug for KevySet<K> {
117    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
118        f.debug_set().entries(self.iter()).finish()
119    }
120}
121
122/// `&K` iterator over all members of a [`KevySet`]; order unspecified.
123pub struct SetIter<'a, K>(Iter<'a, K, ()>);
124
125impl<'a, K> Iterator for SetIter<'a, K> {
126    type Item = &'a K;
127    fn next(&mut self) -> Option<Self::Item> {
128        self.0.next().map(|(k, ())| k)
129    }
130}
131
132impl<'a, K> IntoIterator for &'a KevySet<K> {
133    type Item = &'a K;
134    type IntoIter = SetIter<'a, K>;
135    fn into_iter(self) -> Self::IntoIter {
136        self.iter()
137    }
138}
139
140impl<K: KevyHash + Eq> FromIterator<K> for KevySet<K> {
141    fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self {
142        let iter = iter.into_iter();
143        let mut s = match iter.size_hint() {
144            (lo, Some(hi)) if hi <= lo.saturating_mul(2) => Self::with_capacity(hi),
145            (lo, _) => Self::with_capacity(lo),
146        };
147        for k in iter {
148            s.insert(k);
149        }
150        s
151    }
152}
153
154impl<K: KevyHash + Eq> Extend<K> for KevySet<K> {
155    fn extend<I: IntoIterator<Item = K>>(&mut self, iter: I) {
156        for k in iter {
157            self.insert(k);
158        }
159    }
160}
kevy_map/set.rs

kevy_map/
set.rs
