rostl_datastructures/
vector.rs

1//! Implements variable length vectors.
2//! The vector is oblivious to the access pattern.
3
4use std::fmt::Debug;
5
6use crate::array::DynamicArray;
7use bytemuck::Pod;
8use rostl_primitives::{indexable::Length, traits::Cmov};
9
10/// Implements a variable length vector.
11/// Leaks the length rounded to the next power of two.
12/// The vector is oblivious to the access pattern.
13pub type Vector<T> = EagerVector<T>;
14
15/// Implements a variable length vector.
16/// Leaks the length rounded to the next power of two.
17/// The vector is oblivious to the access pattern.
18#[derive(Debug)]
19pub struct EagerVector<T>
20where
21  T: Cmov + Pod,
22{
23  /// The length of the vector (number of elements in the vector)
24  n: usize,
25  /// The underlying data storage
26  data: DynamicArray<T>,
27}
28
29impl<T> EagerVector<T>
30where
31  T: Cmov + Pod + Default + Debug,
32{
33  /// Creates a new `EagerVector` with the given size `n`.
34  pub fn new() -> Self {
35    Self { n: 0, data: DynamicArray::new(2) }
36  }
37
38  /// Reads from the index
39  pub fn read(&mut self, index: usize, out: &mut T) {
40    assert!(index < self.n);
41    self.data.read(index, out);
42  }
43
44  /// Writes to the index
45  pub fn write(&mut self, index: usize, value: T) {
46    assert!(index < self.n);
47    self.data.write(index, value);
48  }
49
50  /// Pushes a new element to the end of the vector
51  pub fn push_back(&mut self, value: T) {
52    if self.n == self.data.len() {
53      self.data.resize(2 * self.n);
54    }
55    self.data.write(self.n, value);
56    self.n += 1;
57  }
58
59  /// Pops the last element from the vector, returning it
60  pub fn pop_back(&mut self) -> T {
61    assert!(self.n > 0);
62    self.n -= 1;
63    let mut value = Default::default();
64    self.data.read(self.n, &mut value);
65    value
66  }
67
68  /// Returns the current capacity of the vector: `len() <= capacity()`
69  pub fn capacity(&self) -> usize {
70    self.data.len()
71  }
72}
73
74impl<T: Cmov + Pod> Length for EagerVector<T> {
75  fn len(&self) -> usize {
76    self.n
77  }
78}
79
80impl<T: Cmov + Pod + Default + Debug> Default for EagerVector<T> {
81  fn default() -> Self {
82    Self::new()
83  }
84}
85
86// UNDONE(git-40): Should we implement LazyVector? (i.e. it grows lazily when needed, without leaking the length increase at powers of 2 directly)
87// UNDONE(git-42): Benchmark EagerVector
88
89#[cfg(test)]
90mod tests {
91  use super::*;
92
93  #[test]
94  fn test_vector() {
95    let mut v: Vector<u64> = Vector::new();
96    assert_eq!(v.len(), 0);
97    assert_eq!(v.capacity(), 2);
98
99    v.push_back(1);
100    assert_eq!(v.len(), 1);
101    assert_eq!(v.capacity(), 2);
102    assert_eq!(v.pop_back(), 1);
103    assert_eq!(v.len(), 0);
104    assert_eq!(v.capacity(), 2);
105
106    v.push_back(1);
107    v.push_back(2);
108    v.push_back(3);
109    assert_eq!(v.len(), 3);
110    assert_eq!(v.capacity(), 4);
111    assert_eq!(v.pop_back(), 3);
112    assert_eq!(v.pop_back(), 2);
113    assert_eq!(v.pop_back(), 1);
114    assert_eq!(v.len(), 0);
115    assert_eq!(v.capacity(), 4);
116  }
117}
rostl_datastructures/vector.rs

rostl_datastructures/
vector.rs
