rvf_runtime/
cow_map.rs

1//! COW cluster map for vector-addressed cluster resolution.
2//!
3//! Supports three formats: flat array (default), ART tree, and extent list.
4//! Currently only flat_array is implemented; ART tree and extent list are
5//! reserved for future optimization of sparse mappings.
6
7use rvf_types::cow_map::{CowMapEntry, MapFormat};
8use rvf_types::{ErrorCode, RvfError};
9
10/// Adaptive cluster map for cluster_id -> location resolution.
11///
12/// Each cluster is either local (written to this file), inherited from the
13/// parent (ParentRef), or unallocated.
14pub struct CowMap {
15    format: MapFormat,
16    entries: Vec<CowMapEntry>,
17}
18
19impl CowMap {
20    /// Create a new flat-array map with `cluster_count` entries, all Unallocated.
21    pub fn new_flat(cluster_count: u32) -> Self {
22        Self {
23            format: MapFormat::FlatArray,
24            entries: vec![CowMapEntry::Unallocated; cluster_count as usize],
25        }
26    }
27
28    /// Create a new flat-array map with all entries set to ParentRef.
29    pub fn new_parent_ref(cluster_count: u32) -> Self {
30        Self {
31            format: MapFormat::FlatArray,
32            entries: vec![CowMapEntry::ParentRef; cluster_count as usize],
33        }
34    }
35
36    /// Look up a cluster by ID.
37    pub fn lookup(&self, cluster_id: u32) -> CowMapEntry {
38        self.entries
39            .get(cluster_id as usize)
40            .copied()
41            .unwrap_or(CowMapEntry::Unallocated)
42    }
43
44    /// Update a cluster entry.
45    pub fn update(&mut self, cluster_id: u32, entry: CowMapEntry) {
46        let idx = cluster_id as usize;
47        if idx >= self.entries.len() {
48            self.entries.resize(idx + 1, CowMapEntry::Unallocated);
49        }
50        self.entries[idx] = entry;
51    }
52
53    /// Serialize the map to bytes.
54    ///
55    /// Wire format (flat_array):
56    ///   format(u8) | cluster_count(u32) | entries[cluster_count]
57    /// Each entry: tag(u8) | offset(u64)
58    ///   tag 0x00 = Unallocated, tag 0x01 = ParentRef, tag 0x02 = LocalOffset
59    pub fn serialize(&self) -> Vec<u8> {
60        let count = self.entries.len() as u32;
61        // 1 (format) + 4 (count) + count * 9 (tag + offset)
62        let mut buf = Vec::with_capacity(5 + self.entries.len() * 9);
63        buf.push(self.format as u8);
64        buf.extend_from_slice(&count.to_le_bytes());
65        for entry in &self.entries {
66            match entry {
67                CowMapEntry::Unallocated => {
68                    buf.push(0x00);
69                    buf.extend_from_slice(&0u64.to_le_bytes());
70                }
71                CowMapEntry::ParentRef => {
72                    buf.push(0x01);
73                    buf.extend_from_slice(&0u64.to_le_bytes());
74                }
75                CowMapEntry::LocalOffset(off) => {
76                    buf.push(0x02);
77                    buf.extend_from_slice(&off.to_le_bytes());
78                }
79            }
80        }
81        buf
82    }
83
84    /// Deserialize a CowMap from bytes.
85    pub fn deserialize(data: &[u8], format: MapFormat) -> Result<Self, RvfError> {
86        if data.len() < 5 {
87            return Err(RvfError::Code(ErrorCode::CowMapCorrupt));
88        }
89        let stored_format = data[0];
90        if stored_format != format as u8 {
91            return Err(RvfError::Code(ErrorCode::CowMapCorrupt));
92        }
93        let count = u32::from_le_bytes([data[1], data[2], data[3], data[4]]) as usize;
94        let expected_len = count.checked_mul(9)
95            .and_then(|v| v.checked_add(5))
96            .ok_or(RvfError::Code(ErrorCode::CowMapCorrupt))?;
97        if data.len() < expected_len {
98            return Err(RvfError::Code(ErrorCode::CowMapCorrupt));
99        }
100        let mut entries = Vec::with_capacity(count);
101        let mut offset = 5;
102        for _ in 0..count {
103            let tag = data[offset];
104            let val = u64::from_le_bytes([
105                data[offset + 1],
106                data[offset + 2],
107                data[offset + 3],
108                data[offset + 4],
109                data[offset + 5],
110                data[offset + 6],
111                data[offset + 7],
112                data[offset + 8],
113            ]);
114            let entry = match tag {
115                0x00 => CowMapEntry::Unallocated,
116                0x01 => CowMapEntry::ParentRef,
117                0x02 => CowMapEntry::LocalOffset(val),
118                _ => return Err(RvfError::Code(ErrorCode::CowMapCorrupt)),
119            };
120            entries.push(entry);
121            offset += 9;
122        }
123        Ok(Self { format, entries })
124    }
125
126    /// Count of clusters that have local data.
127    pub fn local_cluster_count(&self) -> u32 {
128        self.entries
129            .iter()
130            .filter(|e| matches!(e, CowMapEntry::LocalOffset(_)))
131            .count() as u32
132    }
133
134    /// Total number of clusters in the map.
135    pub fn cluster_count(&self) -> u32 {
136        self.entries.len() as u32
137    }
138
139    /// Get the map format.
140    pub fn format(&self) -> MapFormat {
141        self.format
142    }
143}
144
145#[cfg(test)]
146mod tests {
147    use super::*;
148
149    #[test]
150    fn new_flat_all_unallocated() {
151        let map = CowMap::new_flat(10);
152        assert_eq!(map.cluster_count(), 10);
153        assert_eq!(map.local_cluster_count(), 0);
154        for i in 0..10 {
155            assert_eq!(map.lookup(i), CowMapEntry::Unallocated);
156        }
157    }
158
159    #[test]
160    fn new_parent_ref_all_parent() {
161        let map = CowMap::new_parent_ref(5);
162        assert_eq!(map.cluster_count(), 5);
163        for i in 0..5 {
164            assert_eq!(map.lookup(i), CowMapEntry::ParentRef);
165        }
166    }
167
168    #[test]
169    fn update_and_lookup() {
170        let mut map = CowMap::new_flat(4);
171        map.update(1, CowMapEntry::LocalOffset(0x1000));
172        map.update(3, CowMapEntry::ParentRef);
173        assert_eq!(map.lookup(0), CowMapEntry::Unallocated);
174        assert_eq!(map.lookup(1), CowMapEntry::LocalOffset(0x1000));
175        assert_eq!(map.lookup(2), CowMapEntry::Unallocated);
176        assert_eq!(map.lookup(3), CowMapEntry::ParentRef);
177        assert_eq!(map.local_cluster_count(), 1);
178    }
179
180    #[test]
181    fn update_grows_map() {
182        let mut map = CowMap::new_flat(2);
183        map.update(5, CowMapEntry::LocalOffset(0x2000));
184        assert_eq!(map.cluster_count(), 6);
185        assert_eq!(map.lookup(5), CowMapEntry::LocalOffset(0x2000));
186    }
187
188    #[test]
189    fn out_of_bounds_lookup_returns_unallocated() {
190        let map = CowMap::new_flat(2);
191        assert_eq!(map.lookup(100), CowMapEntry::Unallocated);
192    }
193
194    #[test]
195    fn serialize_deserialize_round_trip() {
196        let mut map = CowMap::new_flat(4);
197        map.update(0, CowMapEntry::LocalOffset(0x100));
198        map.update(1, CowMapEntry::ParentRef);
199        // 2 stays Unallocated
200        map.update(3, CowMapEntry::LocalOffset(0x200));
201
202        let bytes = map.serialize();
203        let map2 = CowMap::deserialize(&bytes, MapFormat::FlatArray).unwrap();
204
205        assert_eq!(map2.cluster_count(), 4);
206        assert_eq!(map2.lookup(0), CowMapEntry::LocalOffset(0x100));
207        assert_eq!(map2.lookup(1), CowMapEntry::ParentRef);
208        assert_eq!(map2.lookup(2), CowMapEntry::Unallocated);
209        assert_eq!(map2.lookup(3), CowMapEntry::LocalOffset(0x200));
210    }
211
212    #[test]
213    fn deserialize_corrupt_data() {
214        let result = CowMap::deserialize(&[0x00, 0x01], MapFormat::FlatArray);
215        assert!(result.is_err());
216    }
217
218    #[test]
219    fn deserialize_wrong_format() {
220        let map = CowMap::new_flat(1);
221        let bytes = map.serialize();
222        let result = CowMap::deserialize(&bytes, MapFormat::ArtTree);
223        assert!(result.is_err());
224    }
225}
rvf_runtime/cow_map.rs

rvf_runtime/
cow_map.rs
