Documentation
¶
Overview ¶
Package sparse provides a compact and efficient sparse array implementation for addressable key ranges from [0..255].
It is optimized for use in radix tries and lookup structures where only a small subset of possible keys contain actual data.
Internally, an Array256 combines a fixed-size BitSet256 with a compact packed Items slice. The bitset tracks which key slots are occupied and enables fast index mapping via popcount (Rank), while the Items slice stores the associated payloads.
Lookup, insertion, and deletion operate in O(1) time (worst-case O(n) only for shifting/copying in extremely full arrays).
This module avoids memory allocations where possible and provides predictable performance even under heavy insert/delete workloads.
Index ¶
- type Array256
- func (a *Array256[T]) Clear(uint)
- func (a *Array256[T]) Copy() *Array256[T]
- func (a *Array256[T]) DeleteAt(i uint8) (value T, exists bool)
- func (a *Array256[T]) Get(i uint8) (value T, ok bool)
- func (a *Array256[T]) InsertAt(i uint8, value T) (rank0 int, exists bool)
- func (a *Array256[T]) Len() int
- func (a *Array256[T]) MustGet(i uint8) T
- func (a *Array256[T]) Set(uint)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Array256 ¶ added in v0.19.0
Array256 is a popcount-compressed sparse array for up to 256 item slots.
Internally, it consists of:
- a BitSet256, where each set bit marks a present slot (i.e., key i used)
- a compact Items slice, which stores the payloads only for the set bits
Each occupied index i ∈ [0..255] can be tested using .Test(i). The actual index within the Items slice is computed via .Rank(i)-1.
All insert/delete operations update both the bitset and item slice to preserve this mapping invariant. Direct mutation of the underlying bitset (via Set or Clear) is forbidden and will panic.
This structure allows extremely fast and compact prefix-based routing, highly efficient child-node containers in prefix tries, or memory-safe alternatives to map[uint8]T with deterministic iteration.
Example layout:
BitSet256: [0 1 0 0 0 1 ...] // bits 1 and 5 set Items: [T1, T2] // a.Items[0] ↔ key 1, a.Items[1] ↔ key 5
func (*Array256[T]) Clear ¶ added in v0.20.3
Clear panics. The bitset is internally coupled with Items[].
func (*Array256[T]) Copy ¶ added in v0.19.0
Copy returns a shallow copy of the Array. The elements are copied using assignment, this is no deep clone.
func (*Array256[T]) DeleteAt ¶ added in v0.19.0
DeleteAt removes the value at index i from the sparse array, shifting remaining items down in the slice and clearing the bit.
If the entry exists, it is returned together with true. If i is not present, the zero value and false are returned.
func (*Array256[T]) Get ¶ added in v0.19.0
Get returns the value at index i and whether it exists.
If the bit for i is not set, ok is false and value is the zero-value of T.
example: a.Get(5) -> a.Items[1]
⬇
BitSet256: [0|0|1|0|0|1|0|...|1] <- 3 bits set
Items: [*|*|*] <- len(Items) = 3
⬆
BitSet256.Test(5): true
BitSet256.Rank(5): 2,
func (*Array256[T]) InsertAt ¶ added in v0.19.0
InsertAt inserts or overwrites the value at sparse index i.
If the slot at i already exists, its value is overwritten in-place and (rank0, true) is returned, where rank0 = Rank(i)-1 is the 0-based index into Items[].
If the slot is new, the bit for i is set, the value is inserted into Items[] at the correct packed position, and (rank0, false) is returned.
rank0 can be cached by the caller to directly access Items[rank0] without a second Rank() call.
Source Files