rate_common/memory/
vector.rs

1//! `Vector` is a thin wrapper around
2//! [std::vec::Vec](https://doc.rust-lang.org/std/vec/struct.Vec.html)
3
4use crate::{config, features::RangeContainsExt, memory::HeapSpace};
5use serde::{Deserialize, Deserializer, Serialize, Serializer};
6use static_assertions::const_assert;
7use std::{
8    iter::FromIterator,
9    mem::size_of,
10    ops::{Deref, DerefMut, Index, IndexMut, Range},
11    ptr, slice,
12};
13
14/// A contiguous growable array type like [`std::vec::Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html)
15///
16/// This should expose a subset of the `std::vec::Vec` API to facilitate
17/// switching between implementations.
18///
19/// The difference to `std::vec::Vec` is mostly that `Vector` uses a different
20/// growth factor (1.5 instead of 2) and disable bounds checking by default.
21#[derive(Debug, Clone, Default, Eq)]
22pub struct Vector<T>(Vec<T>);
23
24impl<T> Vector<T> {
25    /// Wrap a `std::vec::Vec`.
26    pub fn from_vec(vec: Vec<T>) -> Vector<T> {
27        Vector(vec)
28    }
29    /// Convert to a `std::vec::Vec`.
30    pub fn into_vec(self) -> Vec<T> {
31        self.0
32    }
33    /// See [`Vec::new()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.new).
34    // Currently it's not possible to make the `new` const (even though it does not allocate).
35    pub fn new() -> Vector<T> {
36        Vector(Vec::new())
37    }
38    /// See [`Vec::with_capacity()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.with_capacity).
39    pub fn with_capacity(capacity: usize) -> Vector<T> {
40        Vector(Vec::with_capacity(capacity))
41    }
42    /// See [`Vec::len()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.len).
43    pub fn len(&self) -> usize {
44        self.0.len()
45    }
46    /// See [`Vec::is_empty()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.is_empty).
47    pub fn is_empty(&self) -> bool {
48        self.0.is_empty()
49    }
50    /// See [`Vec::capacity()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.capacity).
51    pub fn capacity(&self) -> usize {
52        self.0.capacity()
53    }
54    /// See [`Vec::pop()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.pop).
55    pub fn pop(&mut self) -> Option<T> {
56        self.0.pop()
57    }
58    /// See [`Vec::first()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.first).
59    pub fn first(&self) -> &T {
60        requires!(!self.is_empty());
61        &self[0]
62    }
63    /// See [`Vec::last()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.last).
64    pub fn last(&self) -> &T {
65        requires!(!self.is_empty());
66        &self[self.len() - 1]
67    }
68    /// See [`Vec::iter()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.iter).
69    pub fn iter(&self) -> slice::Iter<T> {
70        self.0.iter()
71    }
72    /// See [`Vec::as_ptr()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.as_ptr).
73    pub fn as_ptr(&self) -> *const T {
74        self.0.as_ptr()
75    }
76    /// See [`Vec::mut_ptr()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.mut_ptr).
77    pub fn mut_ptr(&mut self) -> *mut T {
78        self.0.as_mut_ptr()
79    }
80    /// See [`Vec::truncate()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.truncate).
81    pub fn truncate(&mut self, new_length: usize) {
82        self.0.truncate(new_length)
83    }
84    /// See [`Vec::clear()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.clear).
85    pub fn clear(&mut self) {
86        self.0.clear()
87    }
88    /// See [`Vec::shrink_to_fit()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.shrink_to_fit).
89    pub fn shrink_to_fit(&mut self) {
90        self.0.shrink_to_fit()
91    }
92    /// Like [push](#method.push) but do not grow the vector.
93    ///
94    /// This must only be called when there is enough space left for the
95    /// new element.
96    pub fn push_no_grow(&mut self, value: T) {
97        requires!(self.len() < self.capacity());
98        unsafe {
99            ptr::write(self.mut_ptr().add(self.len()), value);
100            self.0.set_len(self.len() + 1)
101        }
102    }
103}
104
105impl<T: Clone + Default> Vector<T> {
106    pub fn push(&mut self, value: T) {
107        if self.len() == self.capacity() {
108            let new_capacity = next_capacity(self);
109            self.0.reserve_exact(new_capacity - self.capacity())
110        }
111        self.push_no_grow(value)
112    }
113    pub fn fill(size: usize, default_value: T) -> Vector<T> {
114        let mut result = Vector::new();
115        for _ in 0..size {
116            result.push(default_value.clone());
117        }
118        result
119    }
120}
121
122/// Returns the capacity to use when growing the vector.
123///
124/// This uses a growth factor of 1.5 instead of the default 2.
125/// Related: https://github.com/rust-lang/rust/issues/29931
126fn next_capacity<T>(vector: &Vector<T>) -> usize {
127    if vector.is_empty() {
128        4
129    } else {
130        // Assuming we are running on a 64 bit system, this will not overflow
131        // for our expected input sizes.
132        const_assert!(size_of::<usize>() >= 8);
133        vector.capacity() * 3 / 2
134    }
135}
136
137/// Similar to [`vec!`](https://doc.rust-lang.org/std/macro.vec.html) ---
138/// construct a new vector with the given elements.
139#[allow(unused_macros)]
140macro_rules! vector {
141    ($($x:expr),*) => (
142        {
143            #[allow(unused_mut)]
144            let mut result = Vector::new();
145            $(
146                result.push($x);
147            )*
148            result
149        }
150    );
151    ($($x:expr,)*) => (vector!($($x),*))
152}
153
154impl<T: Copy> Vector<T> {
155    /// See [`Vec::swap_remove()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.swap_remove).
156    pub fn swap_remove(&mut self, index: usize) -> T {
157        // copied from Vec::swap_remove to use our own bounds checking
158        unsafe {
159            // We replace self[index] with the last element. Note that if the
160            // bounds check on hole succeeds there must be a last element (which
161            // can be self[index] itself).
162            let hole: *mut T = &mut self[index];
163            let last = ptr::read(self.get_unchecked(self.len() - 1));
164            self.0.set_len(self.len() - 1);
165            ptr::replace(hole, last)
166        }
167    }
168}
169
170impl<T: Ord> Vector<T> {
171    /// See [`Vec::sort_unstable()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_unstable).
172    pub fn sort_unstable(&mut self) {
173        self.0.sort_unstable()
174    }
175}
176
177impl<T> Vector<T> {
178    /// See [`Vec::sort_unstable_by_key()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_unstable_by_key).
179    pub fn sort_unstable_by_key<F, K>(&mut self, f: F)
180    where
181        F: FnMut(&T) -> K,
182        K: Ord,
183    {
184        self.0.sort_unstable_by_key(f)
185    }
186}
187
188impl<T: Clone + Default> Vector<T> {
189    /// See [`Vec::resize()`](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.resize).
190    pub fn resize(&mut self, new_length: usize) {
191        self.0.resize(new_length, T::default())
192    }
193}
194
195impl<T> Deref for Vector<T> {
196    type Target = [T];
197    fn deref(&self) -> &[T] {
198        &self.0
199    }
200}
201
202impl<T> DerefMut for Vector<T> {
203    fn deref_mut(&mut self) -> &mut [T] {
204        &mut self.0
205    }
206}
207
208impl<T> AsRef<Vector<T>> for Vector<T> {
209    fn as_ref(&self) -> &Vector<T> {
210        self
211    }
212}
213
214impl<T> AsMut<Vector<T>> for Vector<T> {
215    fn as_mut(&mut self) -> &mut Vector<T> {
216        self
217    }
218}
219
220impl<T> AsRef<[T]> for Vector<T> {
221    fn as_ref(&self) -> &[T] {
222        self
223    }
224}
225
226impl<T> AsMut<[T]> for Vector<T> {
227    fn as_mut(&mut self) -> &mut [T] {
228        self
229    }
230}
231
232/// Check if an offset is contained in a half-open range.
233/// # Panics
234/// Panic if bounds checking is enabled and the index is out of the given bounds.
235pub fn assert_in_bounds(bounds: Range<usize>, offset: usize) {
236    if config::ENABLE_BOUNDS_CHECKING {
237        assert!(
238            bounds.contains_item(&offset),
239            format!(
240                "array index out of bounds: {} (range is {:?})",
241                offset, bounds
242            )
243        );
244    }
245}
246
247impl<T> Index<usize> for Vector<T> {
248    type Output = T;
249    fn index(&self, index: usize) -> &Self::Output {
250        assert_in_bounds(0..self.len(), index);
251        unsafe { self.0.get_unchecked(index) }
252    }
253}
254
255impl<T> Index<Range<usize>> for Vector<T> {
256    type Output = [T];
257    #[allow(clippy::range_plus_one)]
258    fn index(&self, index: Range<usize>) -> &Self::Output {
259        assert_in_bounds(0..self.len() + 1, index.start);
260        assert_in_bounds(0..self.len() + 1, index.end);
261        unsafe { slice::from_raw_parts(self.as_ptr().add(index.start), index.end - index.start) }
262    }
263}
264
265impl<T> IndexMut<usize> for Vector<T> {
266    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
267        assert_in_bounds(0..self.len(), index);
268        unsafe { self.0.get_unchecked_mut(index) }
269    }
270}
271
272impl<T> IndexMut<Range<usize>> for Vector<T> {
273    #[allow(clippy::range_plus_one)]
274    fn index_mut(&mut self, index: Range<usize>) -> &mut Self::Output {
275        assert_in_bounds(0..self.len() + 1, index.start);
276        assert_in_bounds(0..self.len() + 1, index.end);
277        unsafe {
278            slice::from_raw_parts_mut(self.mut_ptr().add(index.start), index.end - index.start)
279        }
280    }
281}
282
283impl<T: PartialEq> PartialEq for Vector<T> {
284    fn eq(&self, other: &Self) -> bool {
285        self.len() == other.len() && (0..self.len()).all(|i| self[i] == other[i])
286    }
287}
288
289impl<'a, T> IntoIterator for &'a Vector<T> {
290    type Item = &'a T;
291    type IntoIter = slice::Iter<'a, T>;
292    fn into_iter(self) -> Self::IntoIter {
293        self.iter()
294    }
295}
296
297impl<T> FromIterator<T> for Vector<T> {
298    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Vector<T> {
299        Vector(Vec::from_iter(iter))
300    }
301}
302
303impl<T: HeapSpace> HeapSpace for Vector<T> {
304    fn heap_space(&self) -> usize {
305        self.capacity() * size_of::<T>()
306            + (0..self.len()).fold(0, |sum, i| sum + self[i].heap_space())
307    }
308}
309
310impl<T> IntoIterator for Vector<T> {
311    type Item = T;
312    type IntoIter = <Vec<T> as IntoIterator>::IntoIter;
313    fn into_iter(self) -> Self::IntoIter {
314        self.0.into_iter()
315    }
316}
317
318impl<T: Clone + Serialize> Serialize for Vector<T> {
319    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
320    where
321        S: Serializer,
322    {
323        self.clone().into_vec().serialize(serializer)
324    }
325}
326
327impl<'de, T: Clone + Deserialize<'de>> Deserialize<'de> for Vector<T> {
328    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
329    where
330        D: Deserializer<'de>,
331    {
332        Vec::deserialize(deserializer).map(Vector::from_vec)
333    }
334}
rate_common/memory/vector.rs

rate_common/memory/
vector.rs
