qualia_core_db/specialized_libs/shared/
zero_heap.rs

1//! Zero-Heap Utilities
2//!
3//! This module provides stack-allocated, fixed-size data structures that
4//! respect the zero-heap mandate for hot paths in the QualiaDB engine.
5//!
6//! ## Core Principles
7//! - No heap allocation (no Vec, String, Box)
8//! - Fixed-size arrays only
9//! - Caller-supplied output buffers
10//! - Deterministic memory usage
11//! - Compatible with 48-byte NQuin structure
12
13/// Maximum size for fixed arrays (configurable per use case)
14pub const MAX_FIXED_ARRAY_SIZE: usize = 64;
15
16/// Maximum size for ring buffers (must be power of 2 for efficiency)
17pub const MAX_RING_BUFFER_SIZE: usize = 256;
18
19/// Fixed-size array wrapper
20///
21/// Provides array-like interface with bounds checking.
22/// Zero-heap alternative to Vec.
23#[repr(C)]
24#[derive(Debug, Clone, Copy)]
25pub struct FixedArray<T, const N: usize> {
26    data: [T; N],
27    len: usize,
28}
29
30impl<T: Default + Copy, const N: usize> FixedArray<T, N> {
31    /// Creates a new empty fixed array
32    pub fn new() -> Self {
33        Self {
34            data: [T::default(); N],
35            len: 0,
36        }
37    }
38
39    /// Creates a fixed array from an array
40    pub fn from_array(data: [T; N]) -> Self {
41        Self { data, len: N }
42    }
43
44    /// Pushes a value if space is available
45    pub fn push(&mut self, value: T) -> Result<(), &'static str> {
46        if self.len >= N {
47            return Err("FixedArray overflow");
48        }
49        self.data[self.len] = value;
50        self.len += 1;
51        Ok(())
52    }
53
54    /// Returns the current length
55    pub fn len(&self) -> usize {
56        self.len
57    }
58
59    /// Returns true if empty
60    pub fn is_empty(&self) -> bool {
61        self.len == 0
62    }
63
64    /// Returns true if full
65    pub fn is_full(&self) -> bool {
66        self.len >= N
67    }
68
69    /// Gets a value by index
70    pub fn get(&self, index: usize) -> Option<T> {
71        if index < self.len {
72            Some(self.data[index])
73        } else {
74            None
75        }
76    }
77
78    /// Clears the array
79    pub fn clear(&mut self) {
80        self.len = 0;
81    }
82
83    /// Returns the underlying array slice
84    pub fn as_slice(&self) -> &[T] {
85        &self.data[..self.len]
86    }
87
88    /// Returns the underlying mutable array slice
89    pub fn as_mut_slice(&mut self) -> &mut [T] {
90        &mut self.data[..self.len]
91    }
92}
93
94impl<T: Default + Copy, const N: usize> Default for FixedArray<T, N> {
95    fn default() -> Self {
96        Self::new()
97    }
98}
99
100/// Fixed-size stack
101///
102/// LIFO data structure with fixed capacity.
103/// Zero-heap alternative to Vec used as a stack.
104#[repr(C)]
105#[derive(Debug, Clone, Copy)]
106pub struct FixedStack<T, const N: usize> {
107    data: [T; N],
108    top: usize,
109}
110
111impl<T: Default + Copy, const N: usize> FixedStack<T, N> {
112    /// Creates a new empty stack
113    pub fn new() -> Self {
114        Self {
115            data: [T::default(); N],
116            top: 0,
117        }
118    }
119
120    /// Pushes a value onto the stack
121    pub fn push(&mut self, value: T) -> Result<(), &'static str> {
122        if self.top >= N {
123            return Err("Stack overflow");
124        }
125        self.data[self.top] = value;
126        self.top += 1;
127        Ok(())
128    }
129
130    /// Pops a value from the stack
131    pub fn pop(&mut self) -> Option<T> {
132        if self.top == 0 {
133            None
134        } else {
135            self.top -= 1;
136            Some(self.data[self.top])
137        }
138    }
139
140    /// Peeks at the top value without removing it
141    pub fn peek(&self) -> Option<T> {
142        if self.top == 0 {
143            None
144        } else {
145            Some(self.data[self.top - 1])
146        }
147    }
148
149    /// Returns the current depth
150    pub fn depth(&self) -> usize {
151        self.top
152    }
153
154    /// Returns true if empty
155    pub fn is_empty(&self) -> bool {
156        self.top == 0
157    }
158
159    /// Returns true if full
160    pub fn is_full(&self) -> bool {
161        self.top >= N
162    }
163
164    /// Clears the stack
165    pub fn clear(&mut self) {
166        self.top = 0;
167    }
168}
169
170impl<T: Default + Copy, const N: usize> Default for FixedStack<T, N> {
171    fn default() -> Self {
172        Self::new()
173    }
174}
175
176/// Ring buffer (circular buffer)
177///
178/// Fixed-size FIFO queue with power-of-2 capacity for efficient indexing.
179/// Zero-heap alternative to VecDeque.
180#[repr(C)]
181#[derive(Debug, Clone, Copy)]
182pub struct RingBuffer<T, const N: usize> {
183    data: [T; N],
184    head: usize,
185    tail: usize,
186    count: usize,
187}
188
189impl<T: Default + Copy, const N: usize> RingBuffer<T, N> {
190    /// Creates a new empty ring buffer
191    pub fn new() -> Self {
192        assert!(N.is_power_of_two(), "Ring buffer size must be power of 2");
193        Self {
194            data: [T::default(); N],
195            head: 0,
196            tail: 0,
197            count: 0,
198        }
199    }
200
201    /// Enqueues a value
202    pub fn enqueue(&mut self, value: T) -> Result<(), &'static str> {
203        if self.count >= N {
204            return Err("Ring buffer full");
205        }
206        self.data[self.tail] = value;
207        self.tail = (self.tail + 1) & (N - 1);
208        self.count += 1;
209        Ok(())
210    }
211
212    /// Dequeues a value
213    pub fn dequeue(&mut self) -> Option<T> {
214        if self.count == 0 {
215            None
216        } else {
217            let value = self.data[self.head];
218            self.head = (self.head + 1) & (N - 1);
219            self.count -= 1;
220            Some(value)
221        }
222    }
223
224    /// Peeks at the front value without removing it
225    pub fn peek(&self) -> Option<T> {
226        if self.count == 0 {
227            None
228        } else {
229            Some(self.data[self.head])
230        }
231    }
232
233    /// Returns the current count
234    pub fn count(&self) -> usize {
235        self.count
236    }
237
238    /// Returns true if empty
239    pub fn is_empty(&self) -> bool {
240        self.count == 0
241    }
242
243    /// Returns true if full
244    pub fn is_full(&self) -> bool {
245        self.count >= N
246    }
247
248    /// Clears the buffer
249    pub fn clear(&mut self) {
250        self.head = 0;
251        self.tail = 0;
252        self.count = 0;
253    }
254}
255
256impl<T: Default + Copy, const N: usize> Default for RingBuffer<T, N> {
257    fn default() -> Self {
258        Self::new()
259    }
260}
261
262/// Fixed-size queue (simple FIFO)
263///
264/// Non-circular fixed-size queue for simpler use cases.
265#[repr(C)]
266#[derive(Debug, Clone, Copy)]
267pub struct FixedQueue<T, const N: usize> {
268    data: [T; N],
269    front: usize,
270    rear: usize,
271    count: usize,
272}
273
274impl<T: Default + Copy, const N: usize> FixedQueue<T, N> {
275    /// Creates a new empty queue
276    pub fn new() -> Self {
277        Self {
278            data: [T::default(); N],
279            front: 0,
280            rear: 0,
281            count: 0,
282        }
283    }
284
285    /// Enqueues a value
286    pub fn enqueue(&mut self, value: T) -> Result<(), &'static str> {
287        if self.count >= N {
288            return Err("Queue full");
289        }
290        self.data[self.rear] = value;
291        self.rear = (self.rear + 1) % N;
292        self.count += 1;
293        Ok(())
294    }
295
296    /// Dequeues a value
297    pub fn dequeue(&mut self) -> Option<T> {
298        if self.count == 0 {
299            None
300        } else {
301            let value = self.data[self.front];
302            self.front = (self.front + 1) % N;
303            self.count -= 1;
304            Some(value)
305        }
306    }
307
308    /// Peeks at the front value
309    pub fn peek(&self) -> Option<T> {
310        if self.count == 0 {
311            None
312        } else {
313            Some(self.data[self.front])
314        }
315    }
316
317    /// Returns the current count
318    pub fn count(&self) -> usize {
319        self.count
320    }
321
322    /// Returns true if empty
323    pub fn is_empty(&self) -> bool {
324        self.count == 0
325    }
326
327    /// Returns true if full
328    pub fn is_full(&self) -> bool {
329        self.count >= N
330    }
331
332    /// Clears the queue
333    pub fn clear(&mut self) {
334        self.front = 0;
335        self.rear = 0;
336        self.count = 0;
337    }
338}
339
340impl<T: Default + Copy, const N: usize> Default for FixedQueue<T, N> {
341    fn default() -> Self {
342        Self::new()
343    }
344}
345
346#[cfg(test)]
347mod tests {
348    use super::*;
349
350    #[test]
351    fn test_fixed_array() {
352        let mut arr: FixedArray<u32, 4> = FixedArray::new();
353        assert!(arr.is_empty());
354        assert!(!arr.is_full());
355
356        arr.push(1).unwrap();
357        arr.push(2).unwrap();
358        arr.push(3).unwrap();
359        arr.push(4).unwrap();
360
361        assert!(arr.is_full());
362        assert_eq!(arr.len(), 4);
363        assert_eq!(arr.get(0), Some(1));
364        assert_eq!(arr.get(3), Some(4));
365
366        assert!(arr.push(5).is_err());
367    }
368
369    #[test]
370    fn test_fixed_stack() {
371        let mut stack: FixedStack<u32, 4> = FixedStack::new();
372        assert!(stack.is_empty());
373
374        stack.push(1).unwrap();
375        stack.push(2).unwrap();
376        stack.push(3).unwrap();
377
378        assert_eq!(stack.depth(), 3);
379        assert_eq!(stack.peek(), Some(3));
380
381        assert_eq!(stack.pop(), Some(3));
382        assert_eq!(stack.pop(), Some(2));
383        assert_eq!(stack.depth(), 1);
384    }
385
386    #[test]
387    fn test_ring_buffer() {
388        let mut buf: RingBuffer<u32, 8> = RingBuffer::new();
389        assert!(buf.is_empty());
390
391        buf.enqueue(1).unwrap();
392        buf.enqueue(2).unwrap();
393        buf.enqueue(3).unwrap();
394
395        assert_eq!(buf.count(), 3);
396        assert_eq!(buf.peek(), Some(1));
397
398        assert_eq!(buf.dequeue(), Some(1));
399        assert_eq!(buf.dequeue(), Some(2));
400        assert_eq!(buf.count(), 1);
401    }
402
403    #[test]
404    fn test_fixed_queue() {
405        let mut queue: FixedQueue<u32, 4> = FixedQueue::new();
406        assert!(queue.is_empty());
407
408        queue.enqueue(1).unwrap();
409        queue.enqueue(2).unwrap();
410        queue.enqueue(3).unwrap();
411
412        assert_eq!(queue.count(), 3);
413        assert_eq!(queue.peek(), Some(1));
414
415        assert_eq!(queue.dequeue(), Some(1));
416        assert_eq!(queue.dequeue(), Some(2));
417        assert_eq!(queue.count(), 1);
418    }
419}
qualia_core_db/specialized_libs/shared/zero_heap.rs

qualia_core_db/specialized_libs/shared/
zero_heap.rs
