Struct varlen::seq::Seq

pub struct Seq<T: VarLen, Idx: Indexing = UncheckedIndexing> { /* private fields */ }

A sequence of variable-length objects in a flat buffer.

For example, the Seq<Str<u8>> representation of ["hello", "good", "world!"] is:

Examples

Like Vec<T>, this type is a sequence of objects supporting amortized-O(1) push(), and you can iterate through elements of the sequence:

use varlen::prelude::*;
let mut seq: Seq<Str> = Seq::new();
seq.push(Str::copy("hello"));
seq.push(Str::copy("good"));
seq.push(Str::copy("world!"));
let v: Vec<&str> = seq.iter().map(|s| &s[..]).collect();
assert_eq!(vec!["hello", "good", "world!"], v);

Unlike Vec<T>, there is no random access to the nth element of the sequence, Unlike Vec<T>, once an element has been pushed onto the sequence, its size cannot change.

Indexing

Since the T elements are variable-sized, the address of the nth element in the storage cannot directly be calculated from n. This means that random access to the nth element is not available in the Seq<T> type. However, some alternatives exist, either in variations of the Seq<T> type or in different kinds of indexing.

Indexing by offset

Instead of indexing by element index, you may index by offset. The offset of an element is defined to be its position in the storage buffer, in units of T::ALIGN. Offsets start at 0 and increase as you push elements onto a sequence, but they may skip values:

use varlen::prelude::*;
let mut seq: Seq<Str<u16>> = Seq::new();
assert_eq!(0, seq.offset());
seq.push(Str::try_copy("hello").unwrap());
// "hello" takes u16 length, plus 5 bytes storage. Total: 7 bytes, which is 
// `div_round_up(7, Str::<u16>::ALIGN)=4` offsets.
assert_eq!(4, seq.offset());
seq.push(Str::try_copy("fantastic").unwrap());
assert_eq!(10, seq.offset());
seq.push(Str::try_copy("world").unwrap());
assert_eq!(14, seq.offset());

In Seq<T> indexing by offset is available, but unsafe, because the data structure doesn’t contain enough information to validate an offset:

// ... continued
let s = unsafe { seq.from_offset_unchecked(4) };
assert_eq!("fantastic", &s[..]);

In Seq<T, CheckedIndexing> indexing by offset is available and safe:

use varlen::prelude::*;
let mut seq: IndexableSeq<Str<u16>> = Seq::new();
seq.push(Str::try_copy("hello").unwrap());
assert_eq!(4, seq.offset());
seq.push(Str::try_copy("fantastic").unwrap());
seq.push(Str::try_copy("world").unwrap());
assert_eq!("fantastic", &seq.from_offset(4)[..]);
// Would panic: seq.from_offset(5)

To make this possible, Seq<T, CheckedIndexing> stores a bitmap indicating where the start of every element in the storage is:

Maintaining this bitmap adds a memory overhead of 1 bit per T::ALIGN bytes (at most 12.5% overhead in the case T::ALIGN=1), and slightly increases the cost of Seq::push.

Implementations

impl<T: VarLen> Seq<T>

pub fn new_minimal() -> Self

Constructs a sequence without checked indexing.

Examples

use varlen::prelude::*;

let mut seq = Seq::new_minimal();
seq.push(Str::copy("hello"));
seq.push(Str::copy("world"));
let v: Vec<&str> = seq.iter().map(|s| &s[..]).collect();
assert_eq!(vec!["hello", "world"], v);

impl<T: VarLen> Seq<T, CheckedIndexing>

pub fn new_indexable() -> Self

Constructs a seq with checked indexing.

Examples

use varlen::prelude::*;

let mut seq = Seq::new_indexable();
seq.push(Str::copy("hello"));
let pos = seq.offset();
seq.push(Str::copy("world"));
assert_eq!("hello", &seq.from_offset(0)[..]);
assert_eq!("world", &seq.from_offset(pos)[..]);

impl<T: VarLen, Idx: Indexing> Seq<T, Idx>

pub fn new() -> Self

Creates an empty sequence.

Examples

use varlen::prelude::*;
let mut seq: Seq<Str> = Seq::new();
seq.push(Str::copy("hello"));
seq.push(Str::copy("world"));
let v: Vec<&str> = seq.iter().map(|s| &s[..]).collect();
assert_eq!(vec!["hello", "world"], v);

pub fn len(&self) -> usize

Number of elements in the sequence.

Examples

use varlen::prelude::*;
let mut seq: Seq<Str> = Seq::new_minimal();
assert_eq!(seq.len(), 0);
seq.push(Str::copy("hello"));
assert_eq!(seq.len(), 1);
seq.push(Str::copy("world"));
assert_eq!(seq.len(), 2);

pub fn capacity_in_offsets(&self) -> usize

Number of offsets (units of T::ALIGN) in the storage.

Examples

use varlen::prelude::*;
let mut seq: Seq<Str<u32>> = Seq::new_minimal();
assert_eq!(seq.capacity_in_offsets(), 0);
seq.push(Str::try_copy("hello").unwrap());
assert_eq!(seq.capacity_in_offsets(), 8);
seq.push(Str::try_copy("world").unwrap());
assert_eq!(seq.capacity_in_offsets(), 8);

pub fn offset(&self) -> usize

Offset of the next element to be added to the sequence.

The offset is counted in units of T::ALIGN.

Also see crate::seq::Seq::from_offset.

Examples

use varlen::prelude::*;
let mut seq: Seq<Str<u32>> = Seq::new_minimal();
assert_eq!(seq.offset(), 0);
seq.push(Str::try_copy("hello").unwrap());
assert_eq!(seq.offset(), 3);
seq.push(Str::try_copy("world").unwrap());
assert_eq!(seq.offset(), 6);

pub fn push(&mut self, init: impl Initializer<T>)

Adds an element to the sequence.

Examples

use varlen::prelude::*;
let mut seq: Seq<Str> = Seq::new();
seq.push(Str::copy("hello"));
seq.push(Str::copy("good"));
seq.push(Str::copy("world!"));
let v: Vec<&str> = seq.iter().map(|s| &s[..]).collect();
assert_eq!(vec!["hello", "good", "world!"], v);

pub fn iter(&self) -> Iter<'_, T>

Iterate over references.

Examples

use varlen::prelude::*;
let s: Seq<Str>  = seq![Str::copy("hello"), Str::copy("world")];
let total_len: usize = s.iter().map(|s| s.len()).sum();
assert_eq!(10, total_len);

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Iterate over mutable (pinned) references.

Examples

use varlen::prelude::*;
let mut s: Seq<Str> = seq![Str::copy("hello"), Str::copy("world")];
for str in s.iter_mut() {
    str.mut_slice().make_ascii_uppercase();
}
let v: Vec<&str> = s.iter().map(|s| &s[..]).collect();
assert_eq!(&v[..], &["HELLO", "WORLD"]);

pub fn offset_of(&self, element: &T) -> usize

Gets the offset of this element from the start of the contiguous storage, counted in multiples of <T as VarLen>::ALIGN.

Examples

use varlen::prelude::*;
let s: Seq<Str<u16>> = seq![
    Str::try_copy("hello").unwrap(),
    Str::try_copy("world").unwrap(),
];
let element = s.iter().nth(1).unwrap();
assert_eq!(4, s.offset_of(element));

Panics

Panics if this element isn’t from this sequence’s storage.

use varlen::prelude::*;
let s: Seq<Str> = seq![
    Str::copy("hello"),
    Str::copy("world"),
];
let b = VBox::new(Str::copy("hello"));
s.offset_of(&*b);  // Panics

pub unsafe fn from_offset_unchecked(&self, offset: usize) -> &T

Given an offset of an element from the start of the continuous storage (counted in multiples of <T as VarLen>::ALIGN), returns a reference to the element.

Example

use varlen::prelude::*;

let mut seq = Seq::new_minimal();
seq.push(Str::copy("hello"));
let pos = seq.offset();
seq.push(Str::copy("world"));
// Safe because: first element is always at offset 0.
assert_eq!("hello", unsafe { &seq.from_offset_unchecked(0)[..] });
// Safe because: offset() returned offset of the next element to be pushed.
assert_eq!("world", unsafe { &seq.from_offset_unchecked(pos)[..] });

Safety

The offset must be a valid offset to an element in this sequence. The canonical way to find this is by Self::offset() or by Self::offset_of() on an element from this sequence. Such offsets remain valid for all immutable operations on the sequence, and also for Self::push() on the sequence. The offset is invalidated by any mutable operation that removes the specified element, or any earlier element, from the sequence.

For a safe variant, see Self::from_offset().

pub unsafe fn from_offset_unchecked_mut(&mut self, offset: usize) -> Pin<&mut T>

Given an offset of an element from the start of the continuous storage (counted in multiples of <T as VarLen>::ALIGN), returns a reference to the element.

Example

use varlen::prelude::*;

let mut seq = Seq::new_minimal();
seq.push(Str::copy("hello"));
let pos = seq.offset();
seq.push(Str::copy("world"));
// Safe because: first element is always at offset 0.
assert_eq!("hello", unsafe { &seq.from_offset_unchecked(0)[..] });
// Safe because: offset() returned offset of the next element to be pushed.
unsafe { seq.from_offset_unchecked_mut(pos) }
    .mut_slice().make_ascii_uppercase();
assert_eq!("WORLD", unsafe { &seq.from_offset_unchecked(pos)[..] });

Safety

The offset must be a valid offset to an element in this sequence. The canonical way to find this is by Self::offset() or by Self::offset_of() on an element from this sequence. Such offsets remain valid for all immutable operations on the sequence, and also for Self::push() on the sequence. The offset is invalidated by any mutable operation that removes the specified element, or any earlier element, from the sequence.

For a safe variant, see Self::from_offset_mut().

pub fn take_elems(&mut self) -> OwnedElems<'_, T>

Iterate over Owned<T> values.

Examples

use varlen::prelude::*;
use std::sync::atomic::{AtomicUsize, Ordering};

struct CountsDropCalls(usize);
static DROP_COUNT: AtomicUsize = AtomicUsize::new(0);
impl Drop for CountsDropCalls {
    fn drop(&mut self) {
        DROP_COUNT.fetch_add(1, Ordering::SeqCst);
    }
}

let mut seq: Seq<FixedLen<CountsDropCalls>> = seq![
    FixedLen(CountsDropCalls(123)),
    FixedLen(CountsDropCalls(456)),
];
assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 0);
let mut iter = seq.take_elems();

// Take and drop first element:
assert_eq!(iter.next().unwrap().0.0, 123);
assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 1);

// Take and drop second element:
assert_eq!(iter.next().unwrap().0.0, 456);
assert_eq!(DROP_COUNT.load(Ordering::SeqCst), 2);

assert!(iter.next().is_none());

Ownership

Ownership semantics is a little unusual:

• ownership (responsibility to drop) of the T values is transferred to OwnedElems
• ownership (responsibility to drop) the storage remains with the sequence
• any access to the sequence after calling take_elems will see a logically empty sequence, with large capacity.

impl<T: VarLen> Seq<T, CheckedIndexing>

pub fn from_offset(&self, offset: usize) -> &T

Gets a reference to the element at the specified offset (measured in units of T::ALIGN).

Examples

use varlen::prelude::*;

let mut seq = Seq::new_indexable();
seq.push(Str::copy("hello"));
let pos = seq.offset();
seq.push(Str::copy("world"));
assert_eq!("hello", &seq.from_offset(0)[..]);
assert_eq!("world", &seq.from_offset(pos)[..]);

Panics

Panics if the offset doesn’t point to the beginning of an element of this sequence.

pub fn from_offset_mut(&mut self, offset: usize) -> Pin<&mut T>

Gets a mutable reference to the element at the specified offset (measured in units of T::ALIGN).

Examples

use varlen::prelude::*;

let mut seq = Seq::new_indexable();
seq.push(Str::copy("hello"));
let pos = seq.offset();
seq.push(Str::copy("world"));
let mut w = seq.from_offset_mut(pos);
w.as_mut().mut_slice().make_ascii_uppercase();
assert_eq!("WORLD", &w[..]);

Panics

Panics if the offset doesn’t point to the beginning of an element of this sequence.

pub fn is_offset_valid(&self, offset: usize) -> bool

Checks whether the specified offset is valid for this sequence.

Examples

use varlen::prelude::*;

let mut seq = Seq::new_indexable();
seq.push(Str::copy("hello"));
let pos = seq.offset();
assert!(!seq.is_offset_valid(pos));
seq.push(Str::copy("world"));
assert!(seq.is_offset_valid(pos));
assert!(!seq.is_offset_valid(1));

Trait Implementations

impl<T: VarLen, Idx: Indexing> Drop for Seq<T, Idx>

fn drop(&mut self)

Executes the destructor for this type.

impl<T: VarLen, Init: Initializer<T>, Idx: Indexing> Extend<Init> for Seq<T, Idx>

Extends a Seq<T> from a slice.

Examples

use varlen::prelude::*;
let mut seq = Seq::new_minimal();
seq.push(Str::copy("hello"));
seq.extend(["brave", "new", "world"]
    .iter()
    .map(|s| Str::copy(s)));
let mut iter = seq.iter();
assert_eq!(&iter.next().unwrap()[..], "hello");
assert_eq!(&iter.next().unwrap()[..], "brave");
assert_eq!(&iter.next().unwrap()[..], "new");
assert_eq!(&iter.next().unwrap()[..], "world");
assert!(iter.next().is_none());

fn extend<I>(&mut self, iter: I) where
    I: IntoIterator<Item = Init>, 

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: VarLen, Init: Initializer<T>, Idx: Indexing> FromIterator<Init> for Seq<T, Idx>

Collects a Seq<T> from an iterator.

Examples

use varlen::prelude::*;
let seq: Seq<Str> = ["hello", "world"]
    .iter()
    .map(|s| Str::copy(s))
    .collect();
let mut iter = seq.iter();
assert_eq!(&iter.next().unwrap()[..], "hello");
assert_eq!(&iter.next().unwrap()[..], "world");
assert!(iter.next().is_none());

fn from_iter<I>(iter: I) -> Self where
    I: IntoIterator<Item = Init>, 

Creates a value from an iterator.