Struct granite::Chain

pub struct Chain<T, S, I> where
    I: List<Element = S>,
    S: List<Element = T>,  { /* fields omitted */ }

A list data structure wrapping a list of lists used to prevent lag spikes when dealing with huge numbers of elements.

The usual heap array — Vec — has a major weakness if it is used to store large amounts of data: horrible lag spikes will occur during insertions and when capacity is exhausted and more elements need to be inserted (reallocation and relocation of a huge data set). Copying 256 bytes is not a major performance problem, copying 1024 bytes is something that you can afford to do once in a while, and copying 1 GiB is definitely not something you’d want to do, especially in performance-critical code.

Insertion problems can be partially solved by wrapping the Vec in a SparseStorage and its insert_and_shiftfix, but only if remove_and_shiftfix is also used at least exactly as much as insert_and_shiftfix. Insertions without removals and full reallocations, however, are left unsolved.

Chain resolves the issue by limiting the capacity to which a single list storage can be used (technically doesn’t have to be Vec, though that’s what makes the most sense to use), allocating small buffers anew without touching bigger old ones if more space is requested.

Implementations

impl<T, S, I> Chain<T, S, I> where
    S: List<Element = T>,
    I: List<Element = S>, 

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

Creates an iterator over references to the storages of the chain.

This allows for efficient iteration over the elements of a chain, especially if the index collection type (the list which contains the individual sub-lists) is a linked list or any other data structure with O(n) indexing. However, this requires an explicit nested loop, since creating an iterator struct which would flatten iterators into one contiguous iteration sequence is impossible, because that would require modelling a self-referential struct with lifetimes, which isn’t currently possible.

Also, the iterator doesn’t actually iterate over references to storages: it iterates over proxies instead, which are wrappers around references to storages with the sole purpose of making all other trait implementations and methods inaccessible to make sure the chain upholds the ListStorage safety contract in the presence of interior mutability in the used storage type.

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

Creates an iterator over mutable references to the storages of the chain.

This is the same as [iter] — so keep all considerations which apply to it in mind — but the proxies wrap mutable references and not immutable ones.

pub fn set_limit(&mut self, limit: usize)

Sets the limit (in elements, not bytes) to which a buffer will be used before an additional allocation will be performed.

The limit must be even, i.e. a multiple of 2, due to how the limit is stored internally. Check out the source code if you’re curious.

pub fn limit(&self) -> usize

Returns the currently set limit to which a buffer will be used before an additional allocation will be performed.

pub fn allocate_to_limit(&mut self, allocate_to_limit: bool)

Sets whether additional buffers will be allocated to the limit right away or will first allocate as much as needed and only then rellocate to the limit. Enabled by default.

pub fn allocates_to_limit(&self) -> bool

Returns whether allocate_to_limit is enabled.

pub fn num_storages(&self) -> usize

Returns the number of separate storages used.

Trait Implementations

impl<T: Clone, S: Clone, I: Clone> Clone for Chain<T, S, I> where
    I: List<Element = S>,
    S: List<Element = T>, 

fn clone(&self) -> Chain<T, S, I>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Copy, S: Copy, I: Copy> Copy for Chain<T, S, I> where
    I: List<Element = S>,
    S: List<Element = T>, 

impl<T: Debug, S: Debug, I: Debug> Debug for Chain<T, S, I> where
    I: List<Element = S>,
    S: List<Element = T>, 

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

Formats the value using the given formatter.

impl<T, S, I> ListStorage for Chain<T, S, I> where
    S: List<Element = T>,
    I: List<Element = S>, 

type Element = T

The type of values in the container.

const CAPACITY: Option<usize>

The fixed capacity, for statically allocated storages. Storages like SmallVec should set this to None, since going above this limit is generally assumed to panic.

fn with_capacity(capacity: usize) -> Self

Creates an empty collection with the specified capacity.

fn insert(&mut self, index: usize, element: Self::Element)

Inserts an element at position index within the collection, shifting all elements after it to the right.

fn remove(&mut self, index: usize) -> Self::Element

Removes and returns the element at position index within the vector, shifting all elements after it to the left.

fn len(&self) -> usize

Returns the number of elements in the collection, also referred to as its ‘length’.

unsafe fn get_unchecked(&self, index: usize) -> &Self::Element

Returns a reference to the specified element in the collection, without doing bounds checking.

unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut Self::Element

Returns a mutable reference to the specified element in the collection, without doing bounds checking.

fn get(&self, index: usize) -> Option<&Self::Element>

Returns a reference to the specified element in the collection, or None if the index is out of bounds.

fn get_mut(&mut self, index: usize) -> Option<&mut Self::Element>

Returns a mutable reference to the specified element in the collection, or None if the index is out of bounds.

fn new() -> Self

Creates a new empty collection. Dynamically-allocated collections created this way do not allocate memory.

fn push(&mut self, element: Self::Element)

Appends an element to the back of the collection.

fn pop(&mut self) -> Option<Self::Element>

Removes the last element from the collection and returns it, or None if it is empty.

fn capacity(&self) -> usize

Returns the amount of elements the collection can hold without requiring a memory allocation.

fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the given collection. The collection may reserve more space to avoid frequent reallocations. After calling reserve, capacity will be greater than or equal to self.len() + additional. Does nothing if capacity is already sufficient.

fn shrink_to_fit(&mut self)

Shrinks the capacity of the collection as much as possible.

fn truncate(&mut self, len: usize)

Shortens the collection, keeping the first len elements and dropping the rest.

fn insert_and_shiftfix(&mut self, index: usize, element: Self::Element) where
    Self::Element: MoveFix, 

Inserts an element at position index within the collection. The items after the inserted item should be notified using the MoveFix trait or not have their indices changed at all (index changes are not guaranteed and this behavior is implementation-dependent).

fn remove_and_shiftfix(&mut self, index: usize) -> Self::Element where
    Self::Element: MoveFix, 

Removes and returns the element at position index within the collection. The items after the inserted item should be notified using the MoveFix trait or not change indicies at all (index changes are not guaranteed and this behavior is implementation-dependent).

fn add(&mut self, element: Self::Element) -> usize

Uses push under the hood. The Chain should be wrapped in SparseStorage, not vice versa.

fn is_empty(&self) -> bool

Returns true if the collection contains no elements, false otherwise.