b3_stable_structures/
base_vec.rs

1//! The common code for all Vec-like data structures.
2//!
3//! # V1 layout
4//!
5//! ```text
6//! ---------------------------------------- <- Address 0
7//! Magic                  ↕ 3 bytes
8//! ----------------------------------------
9//! Layout version         ↕ 1 byte
10//! ----------------------------------------
11//! Number of entries = L  ↕ 8 bytes
12//! ----------------------------------------
13//! Max entry size         ↕ 4 bytes
14//! ----------------------------------------
15//! Fixed size flag        ↕ 1 byte
16//! ----------------------------------------
17//! Reserved space         ↕ 47 bytes
18//! ---------------------------------------- <- Address 64
19//! E_0                    ↕ SLOT_SIZE bytes
20//! ----------------------------------------
21//! E_1                    ↕ SLOT_SIZE bytes
22//! ----------------------------------------
23//! ...
24//! ----------------------------------------
25//! E_(L-1)                ↕ SLOT_SIZE bytes
26//! ----------------------------------------
27//! Unallocated space
28//! ```
29//!
30//! The `SLOT_SIZE` constant depends on the item type. If the item
31//! type sets the `BoundedStorable::IS_FIXED_SIZE` flag, the
32//! `SLOT_SIZE` is equal to `BoundedStorable::MAX_SIZE`.  Otherwise,
33//! the `SLOT_SIZE` is `BoundedStorable::MAX_SIZE` plus the number of
34//! bytes required to represent integers up to
35//! `BoundedStorable::MAX_SIZE`.
36use crate::storable::bytes_to_store_size;
37use crate::{
38    read_u32, read_u64, safe_write, write_u32, write_u64, Address, BoundedStorable, GrowFailed,
39    Memory,
40};
41use std::borrow::{Borrow, Cow};
42use std::fmt;
43use std::marker::PhantomData;
44
45const LAYOUT_VERSION: u8 = 1;
46/// The offset where the user data begins.
47const DATA_OFFSET: u64 = 64;
48/// The offset where the vector length resides.
49const LEN_OFFSET: u64 = 4;
50
51#[derive(Debug)]
52struct HeaderV1 {
53    magic: [u8; 3],
54    version: u8,
55    len: u64,
56    max_size: u32,
57    is_fixed_size: bool,
58}
59
60#[derive(PartialEq, Eq, Debug)]
61pub enum InitError {
62    /// The memory already contains another data structure.
63    /// Use [Vec::new] to overwrite it.
64    BadMagic { actual: [u8; 3], expected: [u8; 3] },
65    /// The current version of [Vec] does not support the of the
66    /// memory layout.
67    IncompatibleVersion(u8),
68    /// The vector type is not compatible with the current vector
69    /// layout: MAX_SIZE and/or IS_FIXED_SIZE differ from the original
70    /// initialization parameters.
71    IncompatibleElementType,
72    /// Failed to allocate memory for the vector.
73    OutOfMemory,
74}
75
76impl fmt::Display for InitError {
77    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
78        match self {
79            Self::BadMagic{ actual, expected } => {
80                write!(fmt, "bad magic number {actual:?}, expected {expected:?}")
81            }
82            Self::IncompatibleVersion(version)
83            => write!(
84                fmt,
85                "unsupported layout version {version}; supported version numbers are 1..={LAYOUT_VERSION}"
86            ),
87            Self::IncompatibleElementType =>
88                write!(fmt, "either MAX_SIZE or IS_FIXED_SIZE of the element type do not match the persisted vector attributes"),
89            Self::OutOfMemory => write!(fmt, "failed to allocate memory for vector metadata"),
90        }
91    }
92}
93
94impl std::error::Error for InitError {}
95
96pub struct BaseVec<T: BoundedStorable, M: Memory> {
97    memory: M,
98    _marker: PhantomData<T>,
99}
100
101impl<T: BoundedStorable, M: Memory> BaseVec<T, M> {
102    /// Creates a new empty vector in the specified memory,
103    /// overwriting any data structures the memory might have
104    /// contained previously.
105    ///
106    /// Complexity: O(1)
107    pub fn new(memory: M, magic: [u8; 3]) -> Result<Self, GrowFailed> {
108        let header = HeaderV1 {
109            magic,
110            version: LAYOUT_VERSION,
111            len: 0,
112            max_size: T::MAX_SIZE,
113            is_fixed_size: T::IS_FIXED_SIZE,
114        };
115        Self::write_header(&header, &memory)?;
116        Ok(Self {
117            memory,
118            _marker: PhantomData,
119        })
120    }
121
122    /// Initializes a vector in the specified memory.
123    ///
124    /// Complexity: O(1)
125    ///
126    /// PRECONDITION: the memory is either empty or contains a valid
127    /// stable vector.
128    pub fn init(memory: M, magic: [u8; 3]) -> Result<Self, InitError> {
129        if memory.size() == 0 {
130            return Self::new(memory, magic).map_err(|_| InitError::OutOfMemory);
131        }
132        let header = Self::read_header(&memory);
133        if header.magic != magic {
134            return Err(InitError::BadMagic {
135                actual: header.magic,
136                expected: magic,
137            });
138        }
139        if header.version != LAYOUT_VERSION {
140            return Err(InitError::IncompatibleVersion(header.version));
141        }
142        if header.max_size != T::MAX_SIZE || header.is_fixed_size != T::IS_FIXED_SIZE {
143            return Err(InitError::IncompatibleElementType);
144        }
145
146        Ok(Self {
147            memory,
148            _marker: PhantomData,
149        })
150    }
151
152    /// Returns the underlying memory instance.
153    pub fn into_memory(self) -> M {
154        self.memory
155    }
156
157    /// Returns true if the vector is empty.
158    ///
159    /// Complexity: O(1)
160    pub fn is_empty(&self) -> bool {
161        self.len() == 0
162    }
163
164    /// Returns the number of items in the vector.
165    ///
166    /// Complexity: O(1)
167    pub fn len(&self) -> u64 {
168        read_u64(&self.memory, Address::from(LEN_OFFSET))
169    }
170
171    /// Sets the item at the specified index to the specified value.
172    ///
173    /// Complexity: O(T::MAX_SIZE)
174    ///
175    /// PRECONDITION: index < self.len()
176    pub fn set(&self, index: u64, item: &T) {
177        assert!(index < self.len());
178
179        let offset = DATA_OFFSET + slot_size::<T>() as u64 * index;
180        let bytes = item.to_bytes();
181        let data_offset = self
182            .write_entry_size(offset, bytes.len() as u32)
183            .expect("unreachable: cannot fail to write to pre-allocated area");
184        self.memory.write(data_offset, bytes.borrow());
185    }
186
187    /// Returns the item at the specified index.
188    ///
189    /// Complexity: O(T::MAX_SIZE)
190    pub fn get(&self, index: u64) -> Option<T> {
191        if index < self.len() {
192            Some(self.read_entry(index))
193        } else {
194            None
195        }
196    }
197
198    /// Adds a new item at the end of the vector.
199    ///
200    /// Complexity: O(T::MAX_SIZE)
201    pub fn push(&self, item: &T) -> Result<(), GrowFailed> {
202        let index = self.len();
203        let offset = DATA_OFFSET + slot_size::<T>() as u64 * index;
204        let bytes = item.to_bytes();
205        let data_offset = self.write_entry_size(offset, bytes.len() as u32)?;
206        safe_write(&self.memory, data_offset, bytes.borrow())?;
207        // NB. We update the size only after we ensure that the data
208        // write succeeded.
209        self.set_len(index + 1);
210        Ok(())
211    }
212
213    /// Removes the item at the end of the vector.
214    ///
215    /// Complexity: O(T::MAX_SIZE)
216    pub fn pop(&self) -> Option<T> {
217        let len = self.len();
218        if len == 0 {
219            return None;
220        }
221        let value = self.read_entry(len - 1);
222        self.set_len(len - 1);
223        Some(value)
224    }
225
226    pub fn iter(&self) -> Iter<'_, T, M> {
227        Iter {
228            vec: self,
229            buf: vec![],
230            pos: 0,
231        }
232    }
233
234    /// Reads the item at the specified index without any bound checks.
235    fn read_entry(&self, index: u64) -> T {
236        let mut data = std::vec::Vec::new();
237        self.read_entry_to(index, &mut data);
238        T::from_bytes(Cow::Owned(data))
239    }
240
241    /// Reads the item at the specified index without any bound checks.
242    fn read_entry_to(&self, index: u64, buf: &mut std::vec::Vec<u8>) {
243        let offset = DATA_OFFSET + slot_size::<T>() as u64 * index;
244        let (data_offset, data_size) = self.read_entry_size(offset);
245        buf.resize(data_size, 0);
246        self.memory.read(data_offset, &mut buf[..]);
247    }
248
249    /// Sets the vector's length.
250    fn set_len(&self, new_len: u64) {
251        write_u64(&self.memory, Address::from(LEN_OFFSET), new_len);
252    }
253
254    /// Writes the size of the item at the specified offset.
255    fn write_entry_size(&self, offset: u64, size: u32) -> Result<u64, GrowFailed> {
256        debug_assert!(size <= T::MAX_SIZE);
257
258        if T::IS_FIXED_SIZE {
259            Ok(offset)
260        } else if T::MAX_SIZE <= u8::MAX as u32 {
261            safe_write(&self.memory, offset, &[size as u8; 1])?;
262            Ok(offset + 1)
263        } else if T::MAX_SIZE <= u16::MAX as u32 {
264            safe_write(&self.memory, offset, &(size as u16).to_le_bytes())?;
265            Ok(offset + 2)
266        } else {
267            safe_write(&self.memory, offset, &size.to_le_bytes())?;
268            Ok(offset + 4)
269        }
270    }
271
272    /// Reads the size of the entry at the specified offset.
273    fn read_entry_size(&self, offset: u64) -> (u64, usize) {
274        if T::IS_FIXED_SIZE {
275            (offset, T::MAX_SIZE as usize)
276        } else if T::MAX_SIZE <= u8::MAX as u32 {
277            let mut size = [0u8; 1];
278            self.memory.read(offset, &mut size);
279            (offset + 1, size[0] as usize)
280        } else if T::MAX_SIZE <= u16::MAX as u32 {
281            let mut size = [0u8; 2];
282            self.memory.read(offset, &mut size);
283            (offset + 2, u16::from_le_bytes(size) as usize)
284        } else {
285            let size = read_u32(&self.memory, Address::from(offset));
286            (offset + 4, size as usize)
287        }
288    }
289
290    /// Write the layout header to the memory.
291    fn write_header(header: &HeaderV1, memory: &M) -> Result<(), GrowFailed> {
292        safe_write(memory, 0, &header.magic)?;
293        memory.write(3, &[header.version; 1]);
294        write_u64(memory, Address::from(4), header.len);
295        write_u32(memory, Address::from(12), header.max_size);
296        memory.write(16, &[if header.is_fixed_size { 1u8 } else { 0u8 }; 1]);
297        Ok(())
298    }
299
300    /// Reads the header from the specified memory.
301    ///
302    /// PRECONDITION: memory.size() > 0
303    fn read_header(memory: &M) -> HeaderV1 {
304        debug_assert!(memory.size() > 0);
305
306        let mut magic = [0u8; 3];
307        let mut version = [0u8; 1];
308        let mut is_fixed_size = [0u8; 1];
309        memory.read(0, &mut magic);
310        memory.read(3, &mut version);
311        let len = read_u64(memory, Address::from(LEN_OFFSET));
312        let max_size = read_u32(memory, Address::from(12));
313        memory.read(16, &mut is_fixed_size);
314
315        HeaderV1 {
316            magic,
317            version: version[0],
318            len,
319            max_size,
320            is_fixed_size: is_fixed_size[0] != 0,
321        }
322    }
323
324    pub fn to_vec(&self) -> Vec<T> {
325        self.iter().collect()
326    }
327}
328
329impl<T: BoundedStorable + fmt::Debug, M: Memory> fmt::Debug for BaseVec<T, M> {
330    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
331        self.to_vec().fmt(fmt)
332    }
333}
334
335fn slot_size<T: BoundedStorable>() -> u32 {
336    T::MAX_SIZE + bytes_to_store_size::<T>()
337}
338
339pub struct Iter<'a, T, M>
340where
341    T: BoundedStorable,
342    M: Memory,
343{
344    vec: &'a BaseVec<T, M>,
345    buf: std::vec::Vec<u8>,
346    pos: u64,
347}
348
349impl<T, M> Iterator for Iter<'_, T, M>
350where
351    T: BoundedStorable,
352    M: Memory,
353{
354    type Item = T;
355
356    fn next(&mut self) -> Option<T> {
357        if self.vec.len() <= self.pos {
358            return None;
359        }
360
361        self.vec.read_entry_to(self.pos, &mut self.buf);
362        self.pos = self.pos.saturating_add(1);
363        Some(T::from_bytes(Cow::Borrowed(&self.buf)))
364    }
365
366    fn size_hint(&self) -> (usize, Option<usize>) {
367        (self.vec.len().saturating_sub(self.pos) as usize, None)
368    }
369
370    fn count(self) -> usize {
371        let n = self.vec.len().saturating_sub(self.pos);
372        if n > usize::MAX as u64 {
373            panic!("The number of items in the vec {n} does not fit into usize");
374        }
375        n as usize
376    }
377
378    fn nth(&mut self, n: usize) -> Option<T> {
379        self.pos = self.pos.saturating_add(n as u64);
380        self.next()
381    }
382}
b3_stable_structures/base_vec.rs

b3_stable_structures/
base_vec.rs
