Documentation
¶
Overview ¶
Package sparse provides a sparse set data structure for efficient state tracking.
A sparse set achieves O(1) insertion, membership testing, and clearing by exploiting the "uninitialized memory trick" described by Briggs & Torczon (1993) and popularized by Russ Cox for regex engines (https://research.swtch.com/sparse).
This is the preferred data structure for NFA state tracking because:
- O(1) clear: just reset the size counter, no memory zeroing needed
- O(1) membership test: cross-validation between sparse and dense arrays
- Insertion order preserved: enables deterministic NFA simulation
- Cache-friendly iteration: sequential access to dense array
Trade-off: Uses 8 bytes per potential element (4 bytes sparse + 4 bytes dense) vs 1 bit for bitsets. But the O(1) clear makes this worthwhile for regex engines where clear is called per-position during NFA simulation.
Reference implementations:
- Rust regex-automata: regex-automata/src/util/sparse_set.rs
- RE2: re2/sparse_set.h
- Go regexp: uses bitsets (different trade-off for small patterns)
Index ¶
- type SparseSet
- func (s *SparseSet) Capacity() uint32
- func (s *SparseSet) Clear()
- func (s *SparseSet) Clone() *SparseSet
- func (s *SparseSet) Contains(value uint32) bool
- func (s *SparseSet) Insert(value uint32) bool
- func (s *SparseSet) IsEmpty() bool
- func (s *SparseSet) Iter(f func(uint32))
- func (s *SparseSet) Len() int
- func (s *SparseSet) MemoryUsage() int
- func (s *SparseSet) Remove(value uint32)
- func (s *SparseSet) Resize(newCapacity uint32)
- func (s *SparseSet) Size() int
- func (s *SparseSet) Values() []uint32
- type SparseSets
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type SparseSet ¶
type SparseSet struct {
// contains filtered or unexported fields
}
SparseSet is a set of uint32 values with O(1) membership, insertion, and clear.
The data structure maintains two arrays:
- sparse[value] = index in dense where value is stored
- dense[index] = the actual value
Membership test: sparse[v] < size AND dense[sparse[v]] == v The cross-validation handles garbage values in uninitialized sparse slots.
Example layout for set {2, 5, 1}:
sparse[] dense[]
+---+---+---+---+---+---+ +---+---+---+---+
| ? | 2 | 0 | ? | ? | 1 | | 2 | 5 | 1 | ? |
+---+---+---+---+---+---+ +---+---+---+---+
0 1 2 3 4 5 0 1 2
^ size=3
Clear() simply sets size=0, making all elements "unreachable" in O(1).
func NewSparseSet ¶
NewSparseSet creates a new sparse set with the given capacity. Capacity must be at least max(values)+1 that will be stored. For NFA state tracking, use nfa.States() as capacity.
func (*SparseSet) Clear ¶
func (s *SparseSet) Clear()
Clear removes all elements in O(1) time. This is the magic of sparse sets - no memory zeroing needed. All previous elements become "unreachable" because idx >= size.
func (*SparseSet) Contains ¶
Contains returns true if the value is in the set. This is the key operation - O(1) with cross-validation to handle garbage.
func (*SparseSet) Insert ¶
Insert adds a value to the set. Returns true if the value was newly added. If the value is already present, returns false (no-op). Panics if value >= capacity.
func (*SparseSet) Iter ¶
Iter calls the given function for each value in the set. Values are iterated in insertion order.
func (*SparseSet) MemoryUsage ¶
MemoryUsage returns the approximate memory usage in bytes. Formula: 2 * capacity * 4 bytes (for sparse and dense arrays)
func (*SparseSet) Remove ¶
Remove removes a value from the set. If the value is not present, this is a no-op.
func (*SparseSet) Resize ¶
Resize changes the capacity of the set. If newCapacity < current capacity, the set is cleared. If newCapacity > current capacity, arrays are reallocated.
type SparseSets ¶
SparseSets holds a pair of sparse sets for double-buffering. This is the Rust regex-automata pattern for NFA simulation:
- Set1 holds current generation states
- Set2 accumulates next generation states
- After each byte: Swap() and Clear(Set2)
func NewSparseSets ¶
func NewSparseSets(capacity uint32) *SparseSets
NewSparseSets creates a pair of sparse sets with given capacity.
func (*SparseSets) MemoryUsage ¶
func (ss *SparseSets) MemoryUsage() int
MemoryUsage returns total memory usage of both sets.
func (*SparseSets) Resize ¶
func (ss *SparseSets) Resize(newCapacity uint32)
Resize resizes both sets to the new capacity.
func (*SparseSets) Swap ¶
func (ss *SparseSets) Swap()
Swap exchanges Set1 and Set2 in O(1) time (pointer swap).
Source Files