kevy_store/
small_list.rs

1//! `SmallListData` — inline-listpack encoding for tiny lists.
2//!
3//! Companion to [`crate::small_set::SmallSetData`]. Mirrors valkey's
4//! `OBJ_ENCODING_LISTPACK` for lists (`t_list.c::listTypeTryConversion`).
5//! For the `redis-benchmark -t lpush/-t rpush` default shape (single
6//! literal value `__rand_int__`), a one-element list fits in one cache
7//! line. The encoding-switch promotes to `Value::List(Arc<VecDeque>)`
8//! on overflow.
9//!
10//! ## Layout — 24 bytes packed
11//!
12//! Same shape as [`crate::small_set::SmallSetData`]:
13//!
14//! ```text
15//! offset: 0    1                                 23
16//!         +----+----+----+----+----+ ...     +-----+
17//!         | n  | u  |       buf[22]              |
18//!         +----+----+----+----+----+ ...     +-----+
19//! ```
20//!
21//! - `n` (u8): element count (`0..=COUNT_MAX`).
22//! - `u` (u8): bytes used (sum of `1 + len_i`).
23//! - `buf` ([u8; 22]): packed `[len_i: u8][elem_i: u8; len_i]` entries.
24//!
25//! Unlike sets, lists allow duplicates and preserve order. LPUSH
26//! prepends (entries are shifted right to make room); RPUSH appends.
27
28use std::collections::VecDeque;
29
30/// Inline packed list storage. 24 bytes total.
31#[derive(Clone)]
32pub struct SmallListData {
33    count: u8,
34    used: u8,
35    buf: [u8; SMALL_LIST_BUF_CAP],
36}
37
38pub(crate) const SMALL_LIST_BUF_CAP: usize = 22;
39pub(crate) const SMALL_LIST_ELEM_MAX: usize = SMALL_LIST_BUF_CAP - 1;
40pub(crate) const SMALL_LIST_COUNT_MAX: usize = 8;
41
42/// Outcome of `try_push_*`.
43pub(crate) enum PushResult {
44    Pushed,
45    NoRoom,
46}
47
48impl SmallListData {
49    pub(crate) fn new() -> Self {
50        Self { count: 0, used: 0, buf: [0; SMALL_LIST_BUF_CAP] }
51    }
52
53    pub(crate) fn with_one(elem: &[u8]) -> Option<Self> {
54        if elem.len() > SMALL_LIST_ELEM_MAX {
55            return None;
56        }
57        let mut s = Self::new();
58        s.buf[0] = elem.len() as u8;
59        s.buf[1..1 + elem.len()].copy_from_slice(elem);
60        s.count = 1;
61        s.used = 1 + elem.len() as u8;
62        Some(s)
63    }
64
65    pub fn len(&self) -> usize {
66        self.count as usize
67    }
68
69    pub fn is_empty(&self) -> bool {
70        self.count == 0
71    }
72
73    /// Iterator yielding elements as `&[u8]` (front → back).
74    pub fn iter(&self) -> SmallListIter<'_> {
75        SmallListIter { buf: &self.buf[..self.used as usize], cursor: 0 }
76    }
77
78    /// Append at the back (RPUSH).
79    pub(crate) fn try_push_back(&mut self, elem: &[u8]) -> PushResult {
80        if !self.room_for(elem) {
81            return PushResult::NoRoom;
82        }
83        let need = 1 + elem.len();
84        let off = self.used as usize;
85        self.buf[off] = elem.len() as u8;
86        self.buf[off + 1..off + need].copy_from_slice(elem);
87        self.used += need as u8;
88        self.count += 1;
89        PushResult::Pushed
90    }
91
92    /// Prepend at the front (LPUSH).
93    pub(crate) fn try_push_front(&mut self, elem: &[u8]) -> PushResult {
94        if !self.room_for(elem) {
95            return PushResult::NoRoom;
96        }
97        let need = 1 + elem.len();
98        let used = self.used as usize;
99        // Shift everything right by `need` bytes.
100        self.buf.copy_within(0..used, need);
101        self.buf[0] = elem.len() as u8;
102        self.buf[1..need].copy_from_slice(elem);
103        self.used += need as u8;
104        self.count += 1;
105        PushResult::Pushed
106    }
107
108    fn room_for(&self, elem: &[u8]) -> bool {
109        elem.len() <= SMALL_LIST_ELEM_MAX
110            && (self.count as usize) < SMALL_LIST_COUNT_MAX
111            && (self.used as usize + 1 + elem.len()) <= SMALL_LIST_BUF_CAP
112    }
113}
114
115/// Iterator over [`SmallListData`].
116pub struct SmallListIter<'a> {
117    buf: &'a [u8],
118    cursor: usize,
119}
120
121impl<'a> Iterator for SmallListIter<'a> {
122    type Item = &'a [u8];
123    fn next(&mut self) -> Option<&'a [u8]> {
124        if self.cursor >= self.buf.len() {
125            return None;
126        }
127        let len = self.buf[self.cursor] as usize;
128        let start = self.cursor + 1;
129        let end = start + len;
130        self.cursor = end;
131        Some(&self.buf[start..end])
132    }
133}
134
135/// Materialise the inline list as a heap-backed [`crate::value::ListData`].
136pub(crate) fn promote(inline: &SmallListData) -> crate::value::ListData {
137    let mut d: VecDeque<Vec<u8>> = VecDeque::with_capacity(inline.len().max(1));
138    for e in inline.iter() {
139        d.push_back(e.to_vec());
140    }
141    d
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147
148    #[test]
149    fn size_is_24_bytes() {
150        assert_eq!(std::mem::size_of::<SmallListData>(), 24);
151    }
152
153    #[test]
154    fn push_back_basic() {
155        let mut l = SmallListData::new();
156        assert!(matches!(l.try_push_back(b"a"), PushResult::Pushed));
157        assert!(matches!(l.try_push_back(b"bb"), PushResult::Pushed));
158        let v: Vec<&[u8]> = l.iter().collect();
159        assert_eq!(v, vec![b"a".as_slice(), b"bb".as_slice()]);
160        assert_eq!(l.len(), 2);
161    }
162
163    #[test]
164    fn push_front_basic() {
165        let mut l = SmallListData::new();
166        assert!(matches!(l.try_push_front(b"a"), PushResult::Pushed));
167        assert!(matches!(l.try_push_front(b"bb"), PushResult::Pushed));
168        let v: Vec<&[u8]> = l.iter().collect();
169        assert_eq!(v, vec![b"bb".as_slice(), b"a".as_slice()]);
170    }
171
172    #[test]
173    fn duplicate_allowed() {
174        let mut l = SmallListData::new();
175        l.try_push_back(b"a");
176        l.try_push_back(b"a");
177        assert_eq!(l.len(), 2);
178        let v: Vec<&[u8]> = l.iter().collect();
179        assert_eq!(v, vec![b"a".as_slice(), b"a".as_slice()]);
180    }
181
182    #[test]
183    fn no_room_when_full() {
184        let mut l = SmallListData::new();
185        let big = b"element:__rand_int__"; // 20 bytes
186        assert_eq!(big.len(), 20);
187        assert!(matches!(l.try_push_back(big), PushResult::Pushed));
188        // Used = 21 of 22, second 20-byte element won't fit.
189        assert!(matches!(l.try_push_back(big), PushResult::NoRoom));
190    }
191
192    #[test]
193    fn elem_too_long() {
194        let mut l = SmallListData::new();
195        let big = vec![b'x'; SMALL_LIST_ELEM_MAX + 1];
196        assert!(matches!(l.try_push_back(&big), PushResult::NoRoom));
197    }
198
199    #[test]
200    fn promote_preserves_order() {
201        let mut l = SmallListData::new();
202        l.try_push_back(b"a");
203        l.try_push_back(b"bb");
204        l.try_push_back(b"ccc");
205        let d = promote(&l);
206        let v: Vec<&Vec<u8>> = d.iter().collect();
207        assert_eq!(v[0], b"a");
208        assert_eq!(v[1], b"bb");
209        assert_eq!(v[2], b"ccc");
210    }
211}
kevy_store/small_list.rs

kevy_store/
small_list.rs
