kevy_store/small_set.rs
1//! `SmallSetData` — valkey-style inline-listpack encoding for tiny sets.
2//!
3//! Mirrors valkey's `OBJ_ENCODING_LISTPACK` for sets of size
4//! 1–N (`t_set.c::setTypeMaybeConvert`). valkey starts a fresh set as a
5//! 1-entry listpack inside one cache line; once cardinality grows past
6//! `set-max-listpack-entries` (128 default) OR a single member exceeds the
7//! per-entry size cap, it converts to `OBJ_ENCODING_HT`. kevy's analogue:
8//! [`SmallSetData`] for tiny sets, upgrade to [`crate::value::SetData`]
9//! (Swiss-table `KevySet<SmallBytes>`) on overflow.
10//!
11//! ## Layout
12//!
13//! Exactly 24 bytes, mirroring [`kevy_bytes::SmallBytes`] so the
14//! `Value::SmallSetInline(SmallSetData)` variant body matches the size
15//! of `Value::Str(SmallBytes)` and the
16//! `assert!(size_of::<Value>() <= 32)` in `value.rs:162` still holds:
17//!
18//! ```text
19//! offset: 0 1 23
20//! +----+----+----+----+----+ ... +-----+
21//! | n | u | buf[22] |
22//! +----+----+----+----+----+ ... +-----+
23//! ```
24//!
25//! - `n` (u8): member count (`0..=22`, capped well below to leave room).
26//! - `u` (u8): bytes used in `buf` (sum of `1 + len_i` over all members).
27//! - `buf` ([u8; 22]): packed `[len_i: u8][member_i: u8; len_i]` entries.
28//!
29//! Per-entry length prefix is one byte → a single member is at most 21
30//! bytes (need 1 byte for the length itself). For 20-byte
31//! `element:__rand_int__` (the redis-benchmark default SADD member shape),
32//! one entry consumes 21 bytes — fits with 1 spare. For shorter members,
33//! 4-5 fit comfortably.
34//!
35//! ## Upgrade trigger
36//!
37//! Insert returns [`AddResult::NoRoom`] when either (a) the new member's
38//! `1 + len` would overflow the 22-byte budget, or (b) the per-member
39//! length exceeds the 21-byte per-entry cap. The caller upgrades to
40//! `Value::Set(Arc<SetData>)` and re-inserts the new member there.
41//!
42//! Linear-scan `contains` over ≤ N members is faster than the
43//! hash-then-SIMD-probe path on a 16-slot Swiss table when N is small
44//! AND the data is one cache line — the same structural reason valkey's
45//! listpack beats `OBJ_ENCODING_HT` for N≤128.
46//!
47//! ## Future extension
48//!
49//! Hash / List / ZSet families want the same encoding switch. The
50//! pattern factored here:
51//! 1. Inline 24-byte packed-entries variant on `Value`.
52//! 2. Per-op `try_*` helper returns `AddResult { Added, AlreadyPresent,
53//! NoRoom }` so the caller knows when to upgrade.
54//! 3. `account_delta` accepts the per-member weight delta uniformly; the
55//! inline variant returns its own `inline_weight()` (zero heap) so the
56//! Store's `used_memory` accounting stays consistent across both
57//! encodings.
58//!
59//! The `Hash` analogue will need `[len_field][field][len_val][val]`
60//! tuples; List can use the same `[len][bytes]` shape; ZSet needs
61//! `[score:8][len][member]`. All three fit the 24-byte budget for the
62//! 1–3 member cases that dominate `redis-benchmark` default shapes.
63
64use kevy_bytes::SmallBytes;
65
66/// Inline packed set storage. 24 bytes total — see module docs for layout.
67///
68/// ```
69/// use kevy_store::{Store, Value};
70/// let mut s = Store::new();
71/// s.sadd(b"s", &[b"x".as_slice()])?;
72/// s.snapshot_each(|_, v, _| {
73/// let Value::SmallSetInline(m) = v else { panic!("a one-member set stays inline") };
74/// assert!(m.contains(b"x"));
75/// assert!(!m.contains(b"y"));
76/// });
77/// # Ok::<(), kevy_store::StoreError>(())
78/// ```
79#[derive(Debug, Clone)]
80pub struct SmallSetData {
81 /// Number of inline members (0..=22 cap, real ceiling is byte-budget).
82 count: u8,
83 /// Bytes used in `buf` so far (sum of `1 + member_len` per entry).
84 used: u8,
85 /// Packed `[len_i: u8][member_i; len_i]` entries, contiguous from
86 /// offset 0 up to `used`.
87 buf: [u8; SMALL_SET_BUF_CAP],
88}
89
90/// Byte budget for the inline packed entries area. Chosen so that
91/// `count(1) + used(1) + buf(22) = 24` bytes total, matching the
92/// `SmallBytes` body size and preserving `size_of::<Value>() <= 32`.
93pub(crate) const SMALL_SET_BUF_CAP: usize = 22;
94
95/// Per-member length cap: one byte is spent on the length prefix, so the
96/// member payload can be at most `SMALL_SET_BUF_CAP - 1` bytes. Members
97/// larger than this trigger an [`AddResult::NoRoom`] regardless of how
98/// empty the inline buffer is — the caller must upgrade to
99/// `Value::Set` to store them.
100pub(crate) const SMALL_SET_MEMBER_MAX: usize = SMALL_SET_BUF_CAP - 1;
101
102/// Per-set member count cap. The byte budget tends to hit first (a single
103/// 20-byte member takes 21 of 22 bytes), but a hard `count` cap keeps the
104/// linear scan deterministic and bounds the `u8` count field.
105pub(crate) const SMALL_SET_COUNT_MAX: usize = 8;
106
107/// Outcome of [`SmallSetData::try_add`].
108pub(crate) enum AddResult {
109 /// Member was new; count + used updated.
110 Added,
111 /// Member already present; no change.
112 AlreadyPresent,
113 /// Member doesn't fit (either too long or buffer full / count cap).
114 /// Caller must upgrade to `Value::Set` and re-insert.
115 NoRoom,
116}
117
118impl SmallSetData {
119 /// Build an empty inline set.
120 pub(crate) fn new() -> Self {
121 Self { count: 0, used: 0, buf: [0; SMALL_SET_BUF_CAP] }
122 }
123
124 /// Build an inline set holding one member, if it fits. Returns `None`
125 /// when the member exceeds [`SMALL_SET_MEMBER_MAX`] — the caller
126 /// should create a `Value::Set(Arc::default())` and insert the
127 /// member there instead.
128 pub(crate) fn with_one(member: &[u8]) -> Option<Self> {
129 if member.len() > SMALL_SET_MEMBER_MAX {
130 return None;
131 }
132 let mut s = Self::new();
133 s.buf[0] = member.len() as u8;
134 s.buf[1..1 + member.len()].copy_from_slice(member);
135 s.count = 1;
136 s.used = 1 + member.len() as u8;
137 Some(s)
138 }
139
140 /// Number of inline members.
141 pub fn len(&self) -> usize {
142 self.count as usize
143 }
144
145 /// Whether the inline set has no members.
146 pub fn is_empty(&self) -> bool {
147 self.count == 0
148 }
149
150 /// Linear scan for `member`. ≤22 bytes of packed entries fit in one
151 /// cache line; loop is unrolled by the optimiser at small counts.
152 pub fn contains(&self, member: &[u8]) -> bool {
153 self.iter().any(|m| m == member)
154 }
155
156 /// Iterator over the packed entries as `&[u8]` slices. Owns nothing.
157 pub fn iter(&self) -> SmallSetIter<'_> {
158 SmallSetIter { buf: &self.buf[..self.used as usize], cursor: 0 }
159 }
160
161 /// Try to append `member`. See [`AddResult`].
162 pub(crate) fn try_add(&mut self, member: &[u8]) -> AddResult {
163 if self.contains(member) {
164 return AddResult::AlreadyPresent;
165 }
166 if member.len() > SMALL_SET_MEMBER_MAX {
167 return AddResult::NoRoom;
168 }
169 if self.count as usize >= SMALL_SET_COUNT_MAX {
170 return AddResult::NoRoom;
171 }
172 let need = 1 + member.len();
173 let new_used = self.used as usize + need;
174 if new_used > SMALL_SET_BUF_CAP {
175 return AddResult::NoRoom;
176 }
177 let off = self.used as usize;
178 self.buf[off] = member.len() as u8;
179 self.buf[off + 1..off + need].copy_from_slice(member);
180 self.used = new_used as u8;
181 self.count += 1;
182 AddResult::Added
183 }
184
185 /// Try to remove `member`. Returns whether it was present. On hit,
186 /// the trailing packed entries are shifted left by `1 + len` to
187 /// close the gap (deterministic O(used) memmove, fits in cache line).
188 pub(crate) fn try_remove(&mut self, member: &[u8]) -> bool {
189 let mut cursor = 0usize;
190 let used = self.used as usize;
191 while cursor < used {
192 let len = self.buf[cursor] as usize;
193 let start = cursor + 1;
194 let end = start + len;
195 if &self.buf[start..end] == member {
196 // Shift [end..used) → [cursor..)
197 self.buf.copy_within(end..used, cursor);
198 let shifted = used - end;
199 let new_used = cursor + shifted;
200 // Zero the freed tail (avoid leaking old member bytes
201 // into snapshots / accidental Debug prints).
202 self.buf[new_used..used].fill(0);
203 self.used = new_used as u8;
204 self.count -= 1;
205 return true;
206 }
207 cursor = end;
208 }
209 false
210 }
211}
212
213/// Iterator over [`SmallSetData`] members as `&[u8]` slices.
214///
215/// ```
216/// use kevy_store::{Store, Value};
217/// let mut s = Store::new();
218/// s.sadd(b"s", &[b"x".as_slice(), b"y"])?;
219/// let mut members = Vec::new();
220/// s.snapshot_each(|_, v, _| {
221/// if let Value::SmallSetInline(m) = v {
222/// members = m.iter().map(<[u8]>::to_vec).collect();
223/// }
224/// });
225/// members.sort();
226/// assert_eq!(members, [b"x".to_vec(), b"y".to_vec()]);
227/// # Ok::<(), kevy_store::StoreError>(())
228/// ```
229#[derive(Debug)]
230pub struct SmallSetIter<'a> {
231 buf: &'a [u8],
232 cursor: usize,
233}
234
235impl<'a> Iterator for SmallSetIter<'a> {
236 type Item = &'a [u8];
237
238 fn next(&mut self) -> Option<&'a [u8]> {
239 if self.cursor >= self.buf.len() {
240 return None;
241 }
242 let len = self.buf[self.cursor] as usize;
243 let start = self.cursor + 1;
244 let end = start + len;
245 self.cursor = end;
246 Some(&self.buf[start..end])
247 }
248}
249
250/// Materialise the inline set as a heap-backed [`crate::value::SetData`].
251/// Used when an upgrade is forced by an oversized member or full buffer.
252pub(crate) fn promote(inline: &SmallSetData) -> crate::value::SetData {
253 let mut s = crate::value::SetData::with_capacity(inline.len().max(1));
254 for m in inline.iter() {
255 s.insert(SmallBytes::from_slice(m));
256 }
257 s
258}
259
260#[cfg(test)]
261mod tests {
262 use super::*;
263
264 #[test]
265 fn size_is_24_bytes() {
266 // Mirrors SmallBytes' 24 B body so size_of::<Value>() <= 32 holds.
267 assert_eq!(core::mem::size_of::<SmallSetData>(), 24);
268 }
269
270 #[test]
271 fn empty_and_with_one() {
272 let s = SmallSetData::new();
273 assert_eq!(s.len(), 0);
274 assert!(!s.contains(b"foo"));
275
276 let s = SmallSetData::with_one(b"hi").unwrap();
277 assert_eq!(s.len(), 1);
278 assert!(s.contains(b"hi"));
279 assert!(!s.contains(b"hj"));
280 }
281
282 #[test]
283 fn member_too_long_for_with_one() {
284 let big = vec![b'x'; SMALL_SET_MEMBER_MAX + 1];
285 assert!(SmallSetData::with_one(&big).is_none());
286 }
287
288 #[test]
289 fn add_dedup_and_iter() {
290 let mut s = SmallSetData::new();
291 assert!(matches!(s.try_add(b"a"), AddResult::Added));
292 assert!(matches!(s.try_add(b"b"), AddResult::Added));
293 assert!(matches!(s.try_add(b"a"), AddResult::AlreadyPresent));
294 assert_eq!(s.len(), 2);
295 let v: Vec<&[u8]> = s.iter().collect();
296 assert_eq!(v, vec![b"a".as_slice(), b"b".as_slice()]);
297 }
298
299 #[test]
300 fn full_buffer_returns_no_room() {
301 let mut s = SmallSetData::new();
302 // single 20-byte member uses 21 of 22 bytes; second won't fit.
303 let m1 = b"element:__rand_int__";
304 assert_eq!(m1.len(), 20);
305 assert!(matches!(s.try_add(m1), AddResult::Added));
306 assert!(matches!(s.try_add(b"x"), AddResult::NoRoom));
307 }
308
309 #[test]
310 fn member_too_long_returns_no_room() {
311 let mut s = SmallSetData::new();
312 let big = vec![b'x'; SMALL_SET_MEMBER_MAX + 1];
313 assert!(matches!(s.try_add(&big), AddResult::NoRoom));
314 assert_eq!(s.len(), 0);
315 }
316
317 #[test]
318 fn remove_middle_shifts_tail() {
319 let mut s = SmallSetData::new();
320 assert!(matches!(s.try_add(b"aa"), AddResult::Added));
321 assert!(matches!(s.try_add(b"bbb"), AddResult::Added));
322 assert!(matches!(s.try_add(b"cc"), AddResult::Added));
323 assert!(s.try_remove(b"bbb"));
324 assert_eq!(s.len(), 2);
325 assert!(s.contains(b"aa"));
326 assert!(!s.contains(b"bbb"));
327 assert!(s.contains(b"cc"));
328 let v: Vec<&[u8]> = s.iter().collect();
329 assert_eq!(v, vec![b"aa".as_slice(), b"cc".as_slice()]);
330 }
331
332 #[test]
333 fn remove_absent_returns_false() {
334 let mut s = SmallSetData::new();
335 s.try_add(b"a");
336 assert!(!s.try_remove(b"zz"));
337 assert_eq!(s.len(), 1);
338 }
339
340 #[test]
341 fn count_cap_returns_no_room() {
342 let mut s = SmallSetData::new();
343 // 8 × 1-byte members fit in 16 bytes; 9th should hit the count cap
344 // before the byte cap.
345 for c in b"abcdefgh" {
346 assert!(matches!(s.try_add(&[*c]), AddResult::Added));
347 }
348 assert_eq!(s.len(), SMALL_SET_COUNT_MAX);
349 assert!(matches!(s.try_add(b"i"), AddResult::NoRoom));
350 }
351
352 #[test]
353 fn promote_preserves_members() {
354 let mut s = SmallSetData::new();
355 s.try_add(b"a");
356 s.try_add(b"bb");
357 s.try_add(b"ccc");
358 let promoted = promote(&s);
359 assert_eq!(promoted.len(), 3);
360 assert!(promoted.contains(b"a".as_slice()));
361 assert!(promoted.contains(b"bb".as_slice()));
362 assert!(promoted.contains(b"ccc".as_slice()));
363 }
364}