context_engine/
list.rs

1use core::{
2    primitive::{
3        usize,
4        bool
5    },
6    result::Result
7};
8use alloc::vec::Vec;
9use alloc::vec;
10use crate::required::SetOutcome;
11
12#[derive(Debug)]
13pub enum ListError {
14    OutOfBounds,
15    NotExist,
16}
17#[derive(Debug)]
18pub enum VariableListError {
19    List(ListError),
20    Compact,
21}
22
23fn is_null<T: Default + PartialEq>(unit: &[T]) -> bool {
24    unit.iter().all(|x| *x == T::default())
25}
26
27/// A list provides fixed-width unit store.
28///
29/// identity:  usize - 1-based integer (0 is the null sentinel)
30/// schema: usize - unit size in T
31/// error:  ListError
32/// value:  [T]
33///
34/// ```
35/// use context_engine::list::List;
36/// use context_engine::required::SetOutcome;
37///
38/// let mut list: List<u32> = List::new(2);
39///
40/// // append: first real entry is id=1
41/// let r = list.set(&0, &mut 2, &[10u32, 20], false).unwrap();
42/// assert!(matches!(r, SetOutcome::Created(1)));
43/// assert_eq!(list.get(&1, &2).unwrap(), &[10u32, 20]);
44///
45/// // update
46/// let r = list.set(&1, &mut 2, &[30u32, 40], false).unwrap();
47/// assert!(matches!(r, SetOutcome::Updated));
48/// assert_eq!(list.get(&1, &2).unwrap(), &[30u32, 40]);
49///
50/// // delete then reuse_vacant
51/// list.delete(&1, &mut 2).unwrap();
52/// assert!(list.get(&1, &2).is_err());
53/// let r = list.set(&0, &mut 2, &[50u32, 60], true).unwrap();
54/// assert!(matches!(r, SetOutcome::Created(1)));
55/// ```
56pub struct List<T> {
57    pub data: Vec<T>,
58}
59
60impl<T: Copy + Default + PartialEq> List<T> {
61    pub fn new(width: usize) -> Self {
62        Self {
63            data: vec![T::default(); width],
64        }
65    }
66}
67
68impl<T: Copy + Default + PartialEq> List<T> {
69
70    pub fn get<'a>(
71        &'a self,
72        identity: &usize,
73        schema: &usize,
74    ) -> Result<&'a [T], ListError> {
75        let start = identity * schema;
76        let end = start + schema;
77        let unit = self.data.get(start..end).ok_or(ListError::OutOfBounds)?;
78        if is_null(unit) {
79            return Err(ListError::NotExist);
80        }
81        Ok(unit)
82    }
83
84    /// intern: if true and identity=0, return first match value identity(i)
85    pub fn set(
86        &mut self,
87        identity: &usize,
88        schema: &mut usize,
89        value: &[T],
90        reuse_vacant: bool,
91    ) -> Result<SetOutcome, ListError> {
92        if value.len() != *schema {
93            return Err(ListError::OutOfBounds);
94        }
95        let unit = *schema;
96        if *identity != 0 {
97            let start = identity * unit;
98            let end = start + unit;
99            if end > self.data.len() {
100                return Err(ListError::OutOfBounds);
101            }
102            if is_null(&self.data[start..end]) {
103                return Err(ListError::NotExist);
104            }
105            self.data[start..end].copy_from_slice(value);
106            Ok(SetOutcome::Updated)
107        } else {
108            // Ensure id=0 sentinel exists
109            if self.data.is_empty() {
110                self.data.extend(core::iter::repeat(T::default()).take(unit));
111            }
112            let vacant = if reuse_vacant {
113                (1..self.data.len() / unit)
114                    .find(|&i| is_null(&self.data[i * unit..(i + 1) * unit]))
115            } else {
116                None
117            };
118            match vacant {
119                Some(i) => {
120                    self.data[i * unit..(i + 1) * unit].copy_from_slice(value);
121                    Ok(SetOutcome::Created(i))
122                }
123                None => {
124                    let i = self.data.len() / unit;
125                    self.data.extend_from_slice(value);
126                    Ok(SetOutcome::Created(i))
127                }
128            }
129        }
130    }
131
132    pub fn delete(
133        &mut self,
134        identity: &usize,
135        schema: &mut usize,
136    ) -> Result<(), ListError> {
137        let unit = *schema;
138        let start = identity * unit;
139        let end = start + unit;
140        if end > self.data.len() {
141            return Err(ListError::OutOfBounds);
142        }
143        self.data[start..end].fill(T::default());
144        Ok(())
145    }
146}
147
148/// A variable list provides variable-length unit store.
149///
150/// identity:  usize - 1-based integer (0 is the null sentinel). 0 on set appends
151/// error:  ListError
152/// value:  [T]
153///
154/// ```
155/// use context_engine::list::VariableList;
156/// use context_engine::required::SetOutcome;
157///
158/// let mut vl: VariableList<u32> = VariableList::new();
159///
160/// // append: first real entry is id=1
161/// let r = vl.set(&0, &[1u32, 2, 3], false).unwrap();
162/// assert!(matches!(r, SetOutcome::Created(1)));
163/// assert_eq!(vl.get(&1).unwrap(), &[1u32, 2, 3]);
164///
165/// // intern: same value returns existing id
166/// let r = vl.set(&0, &[1u32, 2, 3], true).unwrap();
167/// assert!(matches!(r, SetOutcome::Created(1)));
168///
169/// // update in-place (value fits)
170/// let r = vl.set(&1, &[9u32, 8], false).unwrap();
171/// assert!(matches!(r, SetOutcome::Updated));
172/// assert_eq!(vl.get(&1).unwrap(), &[9u32, 8]);
173///
174/// // delete
175/// vl.delete(&1).unwrap();
176/// assert!(vl.get(&1).is_err());
177/// ```
178pub struct VariableList<T> {
179    pub identity: Vec<usize>,
180    pub data: Vec<T>,
181}
182
183impl<T: Copy + Default + PartialEq> VariableList<T> {
184    pub fn new() -> Self {
185        Self {
186            identity: vec![0, 0], // id=0 sentinel
187            data: Vec::new(),
188        }
189    }
190}
191
192impl<T: Copy + Default + PartialEq> VariableList<T> {
193
194    pub fn get<'a>(
195        &'a self,
196        identity: &usize,
197    ) -> Result<&'a [T], ListError> {
198        let identity_start = identity * 2;
199        let identity_end = identity_start + 2;
200        let identity_range = self.identity.get(identity_start..identity_end).ok_or(ListError::OutOfBounds)?;
201        if is_null(identity_range) {
202            return Err(ListError::NotExist);
203        }
204        let start = identity_range[0];
205        let end = identity_range[1];
206        self.data.get(start..end).ok_or(ListError::OutOfBounds)
207    }
208
209    /// intern: if true and identity=0, return first match value identity(i)
210    ///
211    /// note: update tries in-place if value fits the existing range; otherwise
212    ///       appends to data and rewrites the identity range (old bytes become unreachable
213    ///       until compact is called).
214    pub fn set(
215        &mut self,
216        identity: &usize,
217        value: &[T],
218        intern: bool,
219    ) -> Result<SetOutcome, ListError> {
220        if *identity != 0 {
221            let identity_start = identity * 2;
222            let identity_end = identity_start + 2;
223            if identity_end > self.identity.len() {
224                return Err(ListError::OutOfBounds);
225            }
226            if is_null(&self.identity[identity_start..identity_end]) {
227                return Err(ListError::NotExist);
228            }
229            let old_start = self.identity[identity_start];
230            let old_end   = self.identity[identity_start + 1];
231            let old_len   = old_end - old_start;
232            if value.len() <= old_len {
233                // in-place: value fits within the existing range
234                self.data[old_start..old_start + value.len()].copy_from_slice(value);
235                self.identity[identity_start + 1] = old_start + value.len();
236            } else {
237                // append: value does not fit; old bytes are unreachable until compact
238                let start = self.data.len();
239                let end = start + value.len();
240                self.data.extend_from_slice(value);
241                self.identity[identity_start..identity_end].copy_from_slice(&[start, end]);
242            }
243            Ok(SetOutcome::Updated)
244        } else {
245            if intern {
246                let count = self.identity.len() / 2;
247                for i in 1..count {
248                    let identity_start = i * 2;
249                    let start = self.identity[identity_start];
250                    let end = self.identity[identity_start + 1];
251                    if !is_null(&self.identity[identity_start..identity_start + 2]) && &self.data[start..end] == value {
252                        return Ok(SetOutcome::Created(i));
253                    }
254                }
255            }
256            let start = self.data.len();
257            let end = start + value.len();
258            self.data.extend_from_slice(value);
259            // append [start, end] entry to identity line via List<usize>
260            let entry = [start, end];
261            let mut ls: List<usize> = List {
262                data: core::mem::take(&mut self.identity),
263            };
264            let outcome = ls.set(&0, &mut 2usize, &entry, false)
265                .map_err(|_| ListError::OutOfBounds)?;
266            self.identity = ls.data;
267            Ok(outcome)
268        }
269    }
270
271    pub fn delete(
272        &mut self,
273        identity: &usize,
274    ) -> Result<(), ListError> {
275        if *identity == 0 {
276            return Err(ListError::NotExist);
277        }
278        let identity_start = identity * 2;
279        let identity_end = identity_start + 2;
280        if identity_end > self.identity.len() {
281            return Err(ListError::OutOfBounds);
282        }
283        self.identity[identity_start..identity_end].fill(0);
284        Ok(())
285    }
286
287
288    /// Rebuilds both identity and data from scratch:
289    /// - vacant entries are removed from identity (identity shrinks)
290    /// - update-leaked bytes in data are reclaimed
291    /// - surviving entries are re-assigned sequential id values starting at 1
292    /// Returns a mapping of old id -> new id for callers that hold external references.
293    ///
294    /// ```
295    /// use context_engine::list::VariableList;
296    /// use context_engine::required::SetOutcome;
297    ///
298    /// let mut vl: VariableList<u32> = VariableList::new();
299    /// vl.set(&0, &[1u32, 2, 3], false).unwrap(); // id=1
300    /// vl.set(&0, &[4u32, 5, 6], false).unwrap(); // id=2
301    /// vl.delete(&1).unwrap();                     // id=1 vacant
302    ///
303    /// let remap = vl.compact().unwrap();
304    /// assert_eq!(remap[&2], 1); // old id=2 -> new id=1
305    /// assert_eq!(vl.get(&1).unwrap(), &[4u32, 5, 6]);
306    /// ```
307    pub fn compact(&mut self) -> Result<alloc::collections::BTreeMap<usize, usize>, VariableListError> {
308        let mut new_identity    = vec![0, 0]; // id=0 sentinel
309        let mut new_data: Vec<T> = Vec::new();
310        let mut remap        = alloc::collections::BTreeMap::new();
311        let count = self.identity.len() / 2;
312        // skip i=0 (sentinel)
313        for i in 1..count {
314            let identity_start = i * 2;
315            if is_null(&self.identity[identity_start..identity_start + 2]) {
316                continue;
317            }
318            let start = self.identity[identity_start];
319            let end   = self.identity[identity_start + 1];
320            let slice = self.data.get(start..end).ok_or(VariableListError::Compact)?;
321            let new_start = new_data.len();
322            new_data.extend_from_slice(slice);
323            let new_end = new_data.len();
324            let new_id = new_identity.len() / 2;
325            new_identity.push(new_start);
326            new_identity.push(new_end);
327            remap.insert(i, new_id);
328        }
329        self.identity = new_identity;
330        self.data  = new_data;
331        Ok(remap)
332    }
333}
334
335#[cfg(test)]
336mod tests {
337    use super::*;
338    use crate::required::SetOutcome;
339
340    // ── List ─────────────────────────────────────────────────────────────────
341
342    #[test]
343    fn list_set_update_append_when_value_too_large() {
344        // VariableList::set update path: value exceeds existing range → append
345        let mut vl: VariableList<u32> = VariableList::new();
346        vl.set(&0, &[1u32, 2], false).unwrap(); // id=1, len=2
347        // update with larger value: must append instead of in-place
348        let r = vl.set(&1, &[10u32, 20, 30], false).unwrap();
349        assert!(matches!(r, SetOutcome::Updated));
350        assert_eq!(vl.get(&1).unwrap(), &[10u32, 20, 30]);
351    }
352
353    #[test]
354    fn list_set_wrong_width_returns_out_of_bounds() {
355        let mut list: List<u32> = List::new(2);
356        let err = list.set(&0, &mut 2, &[1u32], false).unwrap_err();
357        assert!(matches!(err, ListError::OutOfBounds));
358    }
359
360    #[test]
361    fn list_set_update_not_exist() {
362        let mut list: List<u32> = List::new(2);
363        // append id=1 then delete it, leaving a null unit
364        list.set(&0, &mut 2, &[1u32, 2], false).unwrap();
365        list.delete(&1, &mut 2).unwrap();
366        let err = list.set(&1, &mut 2, &[3u32, 4], false).unwrap_err();
367        assert!(matches!(err, ListError::NotExist));
368    }
369
370    #[test]
371    fn list_set_update_out_of_bounds() {
372        let mut list: List<u32> = List::new(2);
373        let err = list.set(&99, &mut 2, &[1u32, 2], false).unwrap_err();
374        assert!(matches!(err, ListError::OutOfBounds));
375    }
376
377    #[test]
378    fn list_get_sentinel_returns_not_exist() {
379        let list: List<u32> = List::new(2);
380        let err = list.get(&0, &2).unwrap_err();
381        assert!(matches!(err, ListError::NotExist));
382    }
383
384    // ── VariableList ─────────────────────────────────────────────────────────
385
386    #[test]
387    fn variable_list_delete_sentinel_returns_not_exist() {
388        let mut vl: VariableList<u32> = VariableList::new();
389        let err = vl.delete(&0).unwrap_err();
390        assert!(matches!(err, ListError::NotExist));
391    }
392
393    #[test]
394    fn variable_list_compact_invalidates_old_identity() {
395        let mut vl: VariableList<u32> = VariableList::new();
396        vl.set(&0, &[1u32, 2, 3], false).unwrap(); // id=1
397        vl.set(&0, &[4u32, 5, 6], false).unwrap(); // id=2
398        vl.delete(&1).unwrap();
399        vl.compact().unwrap();
400        // old id=2 is now id=1; old id=1 no longer exists
401        assert!(vl.get(&2).is_err());
402        assert_eq!(vl.get(&1).unwrap(), &[4u32, 5, 6]);
403    }
404}
context_engine/list.rs

context_engine/
list.rs
