Struct VecCell 

pub struct VecCell<T> { /* private fields */ }

A contiguous, growable array type with interior mutability.

This type allows to get a mutable reference (VecRefMut) to an index i, while letting you access immutably (VecRef) elements at indices j != i. New mutable references may only be created if there are no active mutable or immutable references. New immutable references may only be created for indices that aren’t mutably borrowed.

• To borrow an item immutably, use borrow().
• To borrow an item mutably, use borrow_mut().
• If you have a mutable reference to the VecCell, then you may also use get_mut().
• You may access the internal Vec<UnsafeCell<T>> using inner() and inner_mut().
• To read the number of borrows, use borrows() and mut_borrow()

This type is essentially a more restricted version of Vec<RefCell<T>>, with the benefit of having a lower memory footprint since we only need sizeof!(usize) + sizeof!(Option<usize>) bytes instead of N*sizeof!(usize) bytes of memory to prevent aliasing.

Examples

use veccell::VecCell;

fn update(current: &mut usize, prev: &usize) {
    *current += *prev;
}

// Create an empty vec
let mut vec: VecCell<usize> = VecCell::new();

// Add the numbers from 0 to 9 in vec
for n in 0..10 {
    vec.push(n);
}

for index in 1..10 {
    // Get a mutable reference *then* an immutable reference
    // (would fail if the order was reversed)
    let mut current = vec.borrow_mut(index).unwrap();
    let prev = vec.borrow(index - 1).unwrap();

    // Give both references to update
    update(&mut *current, &*prev);
}

assert_eq!(vec, vec![0, 1, 3, 6, 10, 15, 21, 28, 36, 45]);

Safety

The following invariants are enforced by the code:

• (I) mutable guards (RefMut) may only be created if vec.mut_borrow.is_none() and vec.borrows == 0
• (II) when a mutable guard is created, vec.mut_borrow is set to Some(index)
• (III) when a mutable guard is dropped, vec.mut_borrow may be set back to None
• (IV) a mutable reference may only be created if:
  • (IV-a) exclusive access to the VecCell is guaranteed (&mut VecCell)
  • (IV-b) it is created from a mutable guard, and the mutable guard’s lifetime does not exceed that of the mutable guard

Implementations

impl<T> VecCell<T>

pub fn new() -> Self

Creates a new, empty VecCell.

pub fn with_capacity(capacity: usize) -> Self

Creates a new, empty VecCell with capacity as capacity.

pub fn len(&self) -> usize

Returns the length of the VecCell, ie. the number of elements in the array.

See Vec::len() for more information.

Example

let mut vec: VecCell<usize> = VecCell::new();
assert_eq!(vec.len(), 0); // There are no elements

vec.push(32);
assert_eq!(vec.len(), 1); // There is one element: [32]

vec.push(64);
assert_eq!(vec.len(), 2); // There are two elements: [32, 64]

vec.push(64);
assert_eq!(vec.len(), 3); // There are three elements: [32, 64, 64]

pub fn capacity(&self) -> usize

Returns the capacity of the VecCell, ie. the number of elements that can be added before we need to realloc. The following holds true at any time: vec.len() <= vec.capacity().

See Vec::capacity() for more information.

pub fn reserve(&mut self, additional: usize)

Reserves space in the buffer for at least additional more elements.

See Vec::reserve() for more information.

pub fn remove(&mut self, index: usize) -> T

Removes the element at index index, shifting the elements after it and returning that index.

See Vec::remove() for more information.

Panics

Panics if index >= self.len().

Example

let mut vec: VecCell<usize> = VecCell::new();

vec.push(4);
vec.push(6);
vec.push(8);
vec.push(10);
vec.push(12);

vec.remove(0);

assert_eq!(vec, vec![6, 8, 10, 12]);

pub fn swap_remove(&mut self, index: usize) -> T

Removes the element at index index, replacing it with the last element.

See Vec::swap_remove() for more information.

Panics

Panics if index >= self.len().

Example

let mut vec: VecCell<usize> = VecCell::new();

vec.push(4);
vec.push(6);
vec.push(8);
vec.push(10);
vec.push(12);

vec.swap_remove(0);

assert_eq!(vec, vec![12, 6, 8, 10]);

pub fn borrows(&self) -> usize

Returns the number of immutable borrows to elements of the VecCell.

Example

let mut vec: VecCell<usize> = VecCell::new();

vec.push(2);
vec.push(5);
vec.push(9);

// There are no borrows at this point
assert_eq!(vec.borrows(), 0);

let x = vec.borrow(1);

// There is exactly one borrow at this point
assert_eq!(vec.borrows(), 1);

std::mem::drop(x); // x lives up to here

pub fn mut_borrow(&self) -> Option<usize>

Returns the index of the mutable borrows of the VecCell, if any.

Example

let mut vec: VecCell<usize> = VecCell::new();

vec.push(2);
vec.push(5);
vec.push(9);

// There is no mutable borrow at this point
assert_eq!(vec.mut_borrow(), None);

let x = vec.borrow_mut(2);

// There is a mutable borrow of element 2 at this point
assert_eq!(vec.mut_borrow(), Some(2));

std::mem::drop(x); // x lives up to here

pub fn push(&mut self, value: T)

Pushes a value at the end of the array.

Example

use veccell::VecCell;

let mut vec: VecCell<usize> = VecCell::new();
assert_eq!(vec.len(), 0);

vec.push(32);
assert_eq!(vec.len(), 1);
assert_eq!(vec.borrow(0).unwrap(), 32);

vec.push(127);
assert_eq!(vec.len(), 2);
assert_eq!(vec.borrow(1).unwrap(), 127);

pub fn pop(&mut self) -> Option<T>

Pops the last value of the array, if any.

Example

let mut vec: VecCell<usize> = VecCell::new();

vec.push(7);
vec.push(15);
vec.push(31);

assert_eq!(vec.pop(), Some(31));
assert_eq!(vec.len(), 2);

assert_eq!(vec.pop(), Some(15));
assert_eq!(vec.len(), 1);

pub fn borrow<'b>(&'b self, index: usize) -> Option<VecRef<'b, T>>

Borrows the index-th element immutably, if it exists and isn’t already mutably borrowed. Returns None otherwise.

To prevent aliasing, this function returns None if self.mut_borrow() == Some(index). Otherwise, it returns Some(VecRef(reference)) to make sure that the immutable borrow is well-tracked.

Example

let mut vec: VecCell<usize> = VecCell::new();

vec.push(1);
vec.push(2);
vec.push(3);

let x = vec.borrow(1).unwrap();

assert_eq!(*x, 2);

let y = vec.borrow(1).unwrap();

assert_eq!(x, y);

// Manual drops for demonstration purposes
std::mem::drop(x);
std::mem::drop(y);

pub fn borrow_range<'b, R: RangeBounds<usize>>( &'b self, range: R, ) -> Option<VecRef<'b, [T]>>

Borrows a range of elements, making sure that none of these elements are borrowed mutably already. Returns Some(VecRef(slice)) on success. Returns None otherwise.

To prevent aliasing, this function returns None if self.mut_borrow().is_some() and self.mut_borrow().unwrap() ∈ range.

Example

let mut vec: VecCell<usize> = VecCell::new();

vec.push(1);
vec.push(2);
vec.push(3);

let s = vec.borrow_range(0..2).unwrap(); // Gets elements 0 and 1
assert_eq!(s[0], 1);
assert_eq!(s[1], 2);
assert!(s.get(2).is_none());

pub fn borrow_mut<'b>(&'b self, index: usize) -> Option<VecRefMut<'b, T>>

Borrows the index-th element mutably, if it exists and no mutable or immutable borrow are active. Returns None otherwise.

To prevent aliasing, this function only returns Some(VecRefMut(reference)) if self.mut_borrow() == None and self.borrows() == 0. The VecRefMut object sets self.mut_borrow to Some(index) and clears this field once it is dropped.

If you need to borrow an element mutably and borrow another element immutably, then you must first borrow it mutably, then borrow it immutably. Otherwise, borrow_mut will not have the guarantee that its element isn’t already being borrowed.

let mut vec: VecCell<usize> = VecCell::new();

vec.push(1);
vec.push(2);
vec.push(3);

let mut x = vec.borrow_mut(1).unwrap();
let y = vec.borrow(2).unwrap();

*x = *y;

// Manual drops for demonstration purposes
std::mem::drop(x);
std::mem::drop(y);

assert_eq!(vec.borrow(1).unwrap(), 3);

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

Returns a mutable reference to the index-th element, if it exists. Requires exclusive access to self (guaranteed by &mut self).

let mut vec: VecCell<usize> = VecCell::new();

vec.push(1);
vec.push(2);
vec.push(3);

let x = vec.get_mut(1).unwrap();
*x = 5;

assert_eq!(vec.borrow(1).unwrap(), 5);

pub fn iter<'b>(&'b self) -> impl Iterator<Item = VecRef<'b, T>>

Returns an iterator of immutable borrows (VecRef).

Panics

Panics if an element was mutably borrowed when the iterator yields it.

Examples

let mut vec: VecCell<usize> = VecCell::new();

vec.push(0);
vec.push(1);
vec.push(2);
vec.push(3);

for (index, guard) in vec.iter().enumerate() {
    assert_eq!(index, *guard);
}

pub fn iter_mut<'b>(&'b mut self) -> impl Iterator<Item = &'b mut T>

Returns an iterator of mutable references. Requires exclusive access to self (guaranteed by &mut self).

Examples

let mut vec: VecCell<usize> = VecCell::new();

vec.push(0);
vec.push(1);
vec.push(2);
vec.push(3);

for x in vec.iter_mut() {
    *x += 1;
}

assert_eq!(vec, vec![1, 2, 3, 4]);

pub fn try_iter<'b>(&'b self) -> impl Iterator<Item = Option<VecRef<'b, T>>>

Returns an iterator of immutable borrows (VecRef). Yields None for any element that was mutably borrowed when the iterator tried to yield it.

Equivalent to calling (0..self.len()).map(VecCell::get). Can be used in conjunction with Iterator::flatten() and <Option as IntoIterator>

Examples

let mut vec: VecCell<usize> = VecCell::new();

vec.push(0);
vec.push(1);
vec.push(2);
vec.push(3);

let x = vec.borrow_mut(1);

let vec2: Vec<_> = vec.try_iter().flatten().map(|x| *x).collect();
assert_eq!(vec2, vec![0, 2, 3]); // Element 1 was skipped, as it was mutably borrowed

// Manual drop for demonstration purposes
std::mem::drop(x);

pub fn undo_leak(&mut self)

Resets the borrows and mut_borrow counters. Useful if a VecRef or VecRefMut was forgotten without Dropping it.

Requires exclusive access to self (guaranteed by &mut self).

Example

let mut vec: VecCell<usize> = VecCell::new();

vec.push(0);
vec.push(1);
vec.push(2);

let x = vec.borrow_mut(1);
let y = vec.borrow(2);

std::mem::forget(x);
std::mem::forget(y);

assert_eq!(vec.mut_borrow(), Some(1));
assert_eq!(vec.borrows(), 1);

vec.undo_leak();

assert_eq!(vec.mut_borrow(), None);
assert_eq!(vec.borrows(), 0);

pub fn inner(&self) -> &Vec<UnsafeCell<T>>

Returns a reference to the inner buffer, on which you may safely perform immutable operations.

pub fn inner_mut(&mut self) -> &mut Vec<UnsafeCell<T>>

Returns a mutable reference to the inner buffer, on which you may safely perform mutable operations. Requires exclusive access to self (guaranteed by &mut self).

pub fn into_raw_parts(self) -> (Vec<UnsafeCell<T>>, Option<usize>, usize)

Returns the raw parts of a VecCell in the format (inner_vec, mut_borrow, borrows). If no reference was forgotten, then mut_borrow == None and borrows == 0.

pub unsafe fn get_unchecked(&self, index: usize) -> &T

Alternative to get, which skips all checks and returns a mutable reference. Neither the mut_borrow, nor the borrows buffer will be updated or read, so make sure that no exclusive reference to the element at index is made.

If index >= len, then calling this function is undefined behavior.

pub unsafe fn get_mut_unchecked(&self, index: usize) -> &mut T

Alternative to borrow_mut, which skips all checks and returns a mutable reference. Neither the mut_borrow, nor the borrows buffer will be updated or read, so make sure that this is the only reference to the element at index.

If index >= len, then calling this function is undefined behavior.

pub unsafe fn from_raw_parts( inner: Vec<UnsafeCell<T>>, mut_borrow: Option<usize>, borrows: usize, ) -> Self

Constructs a VecCell from its raw parts.

Trait Implementations

impl<T: Clone> Clone for VecCell<T>

fn clone(&self) -> Self

Panics

Panics if a value is currently mutably borrowed

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for VecCell<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> From<Vec<T>> for VecCell<T>

fn from(vec: Vec<T>) -> Self

Converts to this type from the input type.

impl<T> From<VecCell<T>> for Vec<T>

fn from(veccell: VecCell<T>) -> Vec<T>

Converts to this type from the input type.

impl<'a, T: 'a> IntoIterator for &'a VecCell<T>

fn into_iter(self) -> Self::IntoIter

Panics

Panics if a value is currently mutably borrowed

type Item = VecRef<'a, T>

The type of the elements being iterated over.

type IntoIter = VecCellRefIter<'a, T>

Which kind of iterator are we turning this into?

impl<T> IntoIterator for VecCell<T>

fn into_iter(self) -> Self::IntoIter

Panics

Panics if a value is currently mutably borrowed

type Item = T

The type of the elements being iterated over.

type IntoIter = VecCellIntoIter<T>

Which kind of iterator are we turning this into?

impl<T: PartialEq> PartialEq<Vec<T>> for VecCell<T>

fn eq(&self, other: &Vec<T>) -> bool

Panics

Panics if a value in self is currently mutably borrowed when it is encountered in the comparison.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: PartialEq> PartialEq for VecCell<T>

fn eq(&self, other: &Self) -> bool

Panics

Panics if a value in self or other is currently mutably borrowed when it is encountered in the comparison.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.