rlox_core/buffer/
varlen.rs

1/// Packed variable-length sequence storage.
2///
3/// Uses the Arrow ListArray pattern: a flat contiguous data array
4/// plus an offsets array that marks sequence boundaries.
5pub struct VarLenStore {
6    data: Vec<u32>,
7    offsets: Vec<u64>,
8}
9
10impl Default for VarLenStore {
11    fn default() -> Self {
12        Self::new()
13    }
14}
15
16impl VarLenStore {
17    /// Create an empty store.
18    pub fn new() -> Self {
19        Self {
20            data: Vec::new(),
21            offsets: vec![0],
22        }
23    }
24
25    /// Append a variable-length sequence.
26    pub fn push(&mut self, sequence: &[u32]) {
27        self.data.extend_from_slice(sequence);
28        self.offsets.push(self.data.len() as u64);
29    }
30
31    /// Number of sequences stored.
32    pub fn num_sequences(&self) -> usize {
33        self.offsets.len() - 1
34    }
35
36    /// Total number of elements across all sequences.
37    pub fn total_elements(&self) -> usize {
38        self.data.len()
39    }
40
41    /// Get the i-th sequence as a slice.
42    ///
43    /// # Panics
44    /// Panics if `index >= num_sequences()`.
45    pub fn get(&self, index: usize) -> &[u32] {
46        let start = self.offsets[index] as usize;
47        let end = self.offsets[index + 1] as usize;
48        &self.data[start..end]
49    }
50
51    /// Length of the i-th sequence.
52    pub fn sequence_len(&self, index: usize) -> usize {
53        let start = self.offsets[index] as usize;
54        let end = self.offsets[index + 1] as usize;
55        end - start
56    }
57
58    /// Raw flat data array.
59    pub fn flat_data(&self) -> &[u32] {
60        &self.data
61    }
62
63    /// Raw offsets array.
64    pub fn offsets(&self) -> &[u64] {
65        &self.offsets
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn empty_store() {
75        let store = VarLenStore::new();
76        assert_eq!(store.num_sequences(), 0);
77        assert_eq!(store.total_elements(), 0);
78    }
79
80    #[test]
81    fn push_and_retrieve() {
82        let mut store = VarLenStore::new();
83        store.push(&[10, 20, 30]);
84        store.push(&[40, 50]);
85        assert_eq!(store.num_sequences(), 2);
86        assert_eq!(store.get(0), &[10, 20, 30]);
87        assert_eq!(store.get(1), &[40, 50]);
88    }
89
90    #[test]
91    fn total_elements_correct() {
92        let mut store = VarLenStore::new();
93        store.push(&[1, 2, 3]);
94        store.push(&[4, 5]);
95        assert_eq!(store.total_elements(), 5);
96    }
97
98    #[test]
99    fn no_padding_waste() {
100        let mut store = VarLenStore::new();
101        store.push(&[1, 2, 3]);
102        store.push(&[4, 5]);
103        assert_eq!(store.flat_data(), &[1, 2, 3, 4, 5]);
104        assert_eq!(store.offsets(), &[0, 3, 5]);
105    }
106
107    #[test]
108    fn sequence_len() {
109        let mut store = VarLenStore::new();
110        store.push(&[1, 2, 3]);
111        store.push(&[4]);
112        assert_eq!(store.sequence_len(0), 3);
113        assert_eq!(store.sequence_len(1), 1);
114    }
115
116    #[test]
117    fn default_is_empty() {
118        let store = VarLenStore::default();
119        assert_eq!(store.num_sequences(), 0);
120    }
121
122    mod proptests {
123        use super::*;
124        use proptest::collection::vec;
125        use proptest::prelude::*;
126
127        proptest! {
128            #[test]
129            fn varlen_total_equals_sum_of_lengths(sequences in vec(vec(0u32..1000, 1..100), 1..50)) {
130                let mut store = VarLenStore::new();
131                let expected: usize = sequences.iter().map(|s| s.len()).sum();
132                for seq in &sequences {
133                    store.push(seq);
134                }
135                prop_assert_eq!(store.total_elements(), expected);
136            }
137
138            #[test]
139            fn varlen_roundtrip(sequences in vec(vec(0u32..1000, 1..100), 1..50)) {
140                let mut store = VarLenStore::new();
141                for seq in &sequences {
142                    store.push(seq);
143                }
144                for (i, seq) in sequences.iter().enumerate() {
145                    prop_assert_eq!(store.get(i), seq.as_slice());
146                }
147            }
148
149            #[test]
150            fn varlen_num_sequences_matches(sequences in vec(vec(0u32..1000, 1..50), 1..100)) {
151                let mut store = VarLenStore::new();
152                for seq in &sequences {
153                    store.push(seq);
154                }
155                prop_assert_eq!(store.num_sequences(), sequences.len());
156            }
157        }
158    }
159}
rlox_core/buffer/varlen.rs

rlox_core/buffer/
varlen.rs
