Struct regex_automata::util::sparse_set::SparseSet

pub(crate) struct SparseSet {
    len: usize,
    dense: Vec<StateID>,
    sparse: Vec<StateID>,
}

A sparse set used for representing ordered NFA states.

This supports constant time addition and membership testing. Clearing an entire set can also be done in constant time. Iteration yields elements in the order in which they were inserted.

The data structure is based on: https://research.swtch.com/sparse Note though that we don’t actually use uninitialized memory. We generally reuse sparse sets, so the initial allocation cost is bareable. However, its other properties listed above are extremely useful.

Fields

len: usize

The number of elements currently in this set.

dense: Vec<StateID>

Dense contains the ids in the order in which they were inserted.

sparse: Vec<StateID>

Sparse maps ids to their location in dense.

A state ID is in the set if and only if sparse[id] < len && id == dense[sparse[id]].

Note that these are indices into ‘dense’. It’s a little weird to use StateID here, but we know our length can never exceed the bounds of StateID (enforced by ‘resize’) and StateID will be at most 4 bytes where as a usize is likely double that in most cases.

Implementations

impl SparseSet

pub(crate) fn new(capacity: usize) -> SparseSet

Create a new sparse set with the given capacity.

Sparse sets have a fixed size and they cannot grow. Attempting to insert more distinct elements than the total capacity of the set will result in a panic.

This panics if the capacity given is bigger than StateID::LIMIT.

pub(crate) fn resize(&mut self, new_capacity: usize)

Resizes this sparse set to have the new capacity given.

This set is automatically cleared.

This panics if the capacity given is bigger than StateID::LIMIT.

pub(crate) fn capacity(&self) -> usize

Returns the capacity of this set.

The capacity represents a fixed limit on the number of distinct elements that are allowed in this set. The capacity cannot be changed.

pub(crate) fn len(&self) -> usize

Returns the number of elements in this set.

pub(crate) fn is_empty(&self) -> bool

Returns true if and only if this set is empty.

pub(crate) fn insert(&mut self, id: StateID) -> bool

Insert the state ID value into this set and return true if the given state ID was not previously in this set.

This operation is idempotent. If the given value is already in this set, then this is a no-op.

If more than capacity ids are inserted, then this panics.

This is marked as inline(always) since the compiler won’t inline it otherwise, and it’s a fairly hot piece of code in DFA determinization.

pub(crate) fn contains(&self, id: StateID) -> bool

Returns true if and only if this set contains the given value.

pub(crate) fn clear(&mut self)

Clear this set such that it has no members.

pub(crate) fn iter(&self) -> SparseSetIter<'_>

pub(crate) fn memory_usage(&self) -> usize

Returns the heap memory usage, in bytes, used by this sparse set.

Trait Implementations

impl Clone for SparseSet

fn clone(&self) -> SparseSet

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for SparseSet

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

Formats the value using the given formatter.