[−][src]Trait pui_arena::version::Version

pub unsafe trait Version: Copy {
    type Save: Copy;

    pub const EMPTY: Self;

    pub unsafe fn mark_empty(self) -> Result<Self, Self>;

    pub unsafe fn mark_full(self) -> Self;

    pub fn is_exhausted(&self) -> bool;

    pub fn is_full(self) -> bool;

    pub unsafe fn save(self) -> Self::Save;

    pub fn equals_saved(self, saved: Self::Save) -> bool;

    pub fn is_empty(self) -> bool { ... }
}

The versioning strategy

Slot Exhaustion

Arenas store a version alongside each slot they have. If a slot's version is exhausted, then that slot will never be reused. For DefaultVersion this will only happen after about 2 billion insertion/deletion pairs per slot, so it shouldn't be an issue. However, for smaller version types like TinyVersion each slot will exhaust after only 127 insertion/deletion pairs per slot.

You can avoid version exahustion by using Unversioned, but this suffers from the ABA problem.

ABA problem

Wikipedia

Consider this sequence of operations:

ⓘ
use pui_arena::version::UnversionedFull;
// insert 0 at index 0, arena = [(version: Unversioned::Full, Some(0))]
let a: Key<usize, UnversionedFull> = arena.insert(0);
// remove at index 0, arena = [(version: Unversioned::Empty, None)]
arena.remove(a);
// insert 10 at index 0, arena = [(version: Unversioned::Full, Some(10))]
let b: Key<usize, UnversionedFull> = arena.insert(10);
// get the value at index 0
assert_eq!(arena.get(a), None);

because arena is using Unversioned slots, even though key a was removed from the arena, we can still access it! This is fundementally what the ABA problem is. Even though a key was removed, the arena can't distinguish stale keys so it allows access to the new values when it shouldn't.

Depending on your problem space, this may or may not be a problem you need to sove. If it is a problem you need to solve, then you will need to deal with version exhaustion in some way, because there are never going to be an infinite number of versions. pui-arena handles this for you by "leaking" slots with exhausted versions. These slots will not be reused, but will be deallocated once the Arena drops.

Associated Types

type Save: Copy[src]

Represents a full version

Loading content...

Associated Constants

pub const EMPTY: Self[src]

The initial empty version

Loading content...

Required methods

pub unsafe fn mark_empty(self) -> Result<Self, Self>[src]

Convert an full version to a empty version

returns Err if there are no more versions

Safety

mark_empty can only be called on a full version

pub unsafe fn mark_full(self) -> Self[src]

Convert an empty version to a full version

Safety

mark_full can only be called on a empty version

pub fn is_exhausted(&self) -> bool[src]

Check if the version is exhausted

pub fn is_full(self) -> bool[src]

Check if the version is full

pub unsafe fn save(self) -> Self::Save[src]

Save the current version

Safety

save can only be called on a full version

pub fn equals_saved(self, saved: Self::Save) -> bool[src]

Check if the saved version matches the current version

In particular, this can only be true if the current version is full and may not be true if there was a call to mark_empty in since the save was created.

Loading content...

Provided methods

pub fn is_empty(self) -> bool[src]

Check if the version is empty

Loading content...

Implementors

impl Version for Unversioned[src]

type Save = UnversionedFull

impl Version for DefaultVersion[src]

type Save = SavedDefaultVersion

impl Version for TinyVersion[src]

type Save = SavedTinyVersion

Loading content...