Vec of fixed capacity ( StackVec )

I just made a Vec of fixed capacity, which can be allocated on the stack ( due to smallvec::SmallVec having some covariance issue ).

The one part I am a bit unsure about is in push, is it ok to make a mut ref to the element before it is written? If not, how should I proceed?

/// Vec of fixed capacity N, typically allocated on the stack.
pub struct StackVec<T, const N: usize> {
    len: usize,
    v: MaybeUninit<[T; N]>,
}

impl<T, const N: usize> StackVec<T, N> {
    /// Construct new empty Vec.
    pub fn new() -> Self {
        Self {
            len: 0,
            v: MaybeUninit::uninit(),
        }
    }

    /// Get Vec length.
    pub fn len(&self) -> usize {
        self.len
    }

    /// Check if Vec is empty.
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    /// Push value.
    ///
    /// # Panics
    ///
    /// Panics if Vec is full to capacity.
    pub fn push(&mut self, value: T) {
        assert!(self.len < N);
        let p = self.v.as_mut_ptr();
        unsafe {
            let p: *mut T = &mut (*p)[self.len];
            p.write(value);
        }
        self.len += 1;
    }

    /// Pop value, returns None if Vec is empty.
    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            None
        } else {
            self.len -= 1;
            let p = self.v.as_ptr();
            unsafe {
                let p: *const T = &(*p)[self.len];
                Some(p.read())
            }
        }
    }

    /// Insert value at specified position.
    ///
    /// # Panics
    ///
    /// Panics if at > len or vec is full.
    pub fn insert(&mut self, at: usize, value: T) {
        assert!(at <= self.len && self.len < N);
        let p = self.v.as_mut_ptr();
        unsafe {
            let p: *mut T = &mut (*p)[at];
            let n = self.len - at;
            let to = p.add(1);
            ptr::copy(p, to, n);
            p.write(value);
        }
        self.len += 1;
    }
}

impl<T, const N: usize> Drop for StackVec<T, N> {
    fn drop(&mut self) {
        let mut len = self.len;
        while len > 0 {
            len -= 1;
            self.pop();
        }
    }
}

impl<T, const N: usize> Deref for StackVec<T, N> {
    type Target = [T];
    #[inline]
    fn deref(&self) -> &[T] {
        let len = self.len;
        let p = self.v.as_ptr();
        unsafe { &(*p)[0..len] }
    }
}

impl<T, const N: usize> DerefMut for StackVec<T, N> {
    #[inline]
    fn deref_mut(&mut self) -> &mut [T] {
        let len = self.len;
        let p = self.v.as_mut_ptr();
        unsafe { &mut (*p)[0..len] }
    }
}

impl<T, const N: usize> Default for StackVec<T, N> {
    fn default() -> Self {
        Self::new()
    }
}

#[test]
fn test_stackvec() {
    let mut sv = StackVec::<i32, 10>::new();
    sv.push(98);
    sv.push(100);
    sv.insert(1, 99);
    println!("sv[0..3]={:?}", &sv[0..3]);
}

From StackVec in btree_experiment - Rust

Probably not; you can use offset() to get a raw pointer to the element slot without needing to make an &mut and then index. Alternatively, you could perhaps store [MaybeUninit<T>; N] instead.

1 Like

But what can I offset from? I am a bit confused here...

It’ll be something like

assert!(self.len < N);
unsafe {
    self.v.as_mut_ptr()
        .cast::<T>() // Pointer to array is also pointer to first element
        .offset(self.len) // Advance pointer to `len`th element
        .write(value);
}
self.len += 1;
1 Like

Ok, that looks good, but I used add rather than offset as it takes usize rather than isize, I think that is appropriate.

I think you could just use ArrayVec, no?

3 Likes

Looks like it, yes!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.