README
¶
kjkrol/uid
A bit-packed 64-bit Generational Unique Identifier package for Go.
Designed for memory pools and contiguous data structures. It provides index recycling with ABA problem prevention and an isolated 8-bit space for module-specific metadata.
Overview
- Zero-Allocation: Identifier and bitmask manipulations are value-based.
- Recycling: Uses a generational counter to invalidate recycled pool indices.
- Metadata Segments: Provides a
MetaSegmentAPI to divide the 8-bit metadata space for safe bitwise operations across different modules.
Installation
go get github.com/kjkrol/uid
64-bit Layout
The UID64 type is a uint64 partitioned into three segments:
63 56 55 32 31 0
+------------+------------------------+--------------------------------+
| Metadata | Generation | Index |
| (8 bits) | (24 bits) | (32 bits) |
+------------+------------------------+--------------------------------+
- Index (32 bits): The main sequence number for array or pool offsets (Max: ~4.29 billion).
- Generation (24 bits): Incremented upon index release. Validates active references.
- Metadata (8 bits): User-defined space for boolean flags, enums, or module state.
Usage
Pool Management (UID64Pool)
The pool handles allocation, generation increments, and index validation.
package main
import (
"fmt"
"github.com/kjkrol/uid"
)
func main() {
var pool uid.UID64Pool
pool.Init(1000, 100)
// Allocate
id := pool.Next()
// Unpack returns both index and generation
index, gen := id.Unpack()
fmt.Printf("Allocated: Index %d, Gen %d\n", index, gen)
// Release invalidates the current generation of this index
pool.Release(id)
if !pool.IsValid(id) {
fmt.Println("Old reference is invalid.")
}
// Next allocation reuses the index but increments the generation
recycled := pool.Next()
fmt.Printf("Recycled: Index %d, Gen %d\n", recycled.Index(), recycled.Generation())
}
Custom Metadata (MetaSegment)
Divide the 8-bit Metadata space into strict, pre-shifted segments to prevent bit collisions between modules.
For example, defining a 1-bit segment at offset 7 (virtualFlag) and a 2-bit segment at offset 0 (spatialFrag):
7 6 5 4 3 2 1 0 (Metadata Bit Index)
+---+---+---+---+---+---+---+---+
| V | | | | | | S | S |
+---+---+---+---+---+---+---+---+
^ ^^^^^
virtualFlag spatialFrag
package main
import (
"fmt"
"github.com/kjkrol/uid"
)
// Define segments globally per module
// Length: 1 bit, Offset: 7 (highest bit)
var virtualFlag = uid.NewMetaSegment(1, 7)
// Length: 2 bits, Offset: 0 (lowest bits)
var spatialFrag = uid.NewMetaSegment(2, 0)
func main() {
id := uid.UID64(42) // Cast raw integer to UID64
// Mutate segments
id = id.WithMetaSegment(virtualFlag, 1)
id = id.WithMetaSegment(spatialFrag, 3)
// Read segments
isVirtual := id.MetaSegment(virtualFlag) == 1
fragValue := id.MetaSegment(spatialFrag)
fmt.Printf("Virtual: %v, Frag: %d\n", isVirtual, fragValue)
}
Documentation
¶
Overview ¶
Package uid implements UID64, a bit-packed 64-bit generational identifier for memory pools and contiguous, index-addressed data structures such as entity systems, slab allocators and slot maps.
Layout ¶
A UID64 packs three fields into a single uint64:
63 56 55 32 31 0
+------------+------------------------+--------------------------------+
| Metadata | Generation | Index |
| (8 bits) | (24 bits) | (32 bits) |
+------------+------------------------+--------------------------------+
- Index (32 bits): slot offset into a backing array (up to ~4.29 billion).
- Generation (24 bits): bumped each time a slot is released, so a stale
reference to a recycled slot fails validation — this prevents the ABA
problem.
- Metadata (8 bits): user-defined space, partitioned with [MetaSegment].
All extraction and mutation is value-based and allocation-free.
Pools ¶
UID64Pool hands out identifiers, recycles released indices and validates references. Initialise it in place with UID64Pool.Init:
var pool uid.UID64Pool pool.Init(1000, 100) id := pool.Next() // allocate one pool.Release(id) // recycle the index; id no longer validates next := pool.Next() // reuses the index under a bumped generation
UID64Pool.NextN reserves many identifiers at once into a caller-owned buffer, amortising the per-id branch, capacity check and growth — preferable for bulk creation.
Metadata segments ¶
MetaSegment divides the 8-bit metadata space into fixed, pre-shifted bit-ranges so independent modules can store flags without colliding. See NewMetaSegment, UID64.WithMetaSegment and UID64.MetaSegment.
Index ¶
Examples ¶
Constants ¶
const ( // IndexMask isolates the lower 32 bits used for the entity index. IndexMask = 0xFFFFFFFF // GenerationShift is the bit offset for the generation counter. GenerationShift = 32 // GenerationMask isolates the 24 bits allocated for the generation counter. GenerationMask = 0xFFFFFF // MetadataShift is the bit offset for the custom metadata byte. MetadataShift = 56 // MetadataMask isolates the upper 8 bits allocated for user-defined metadata. MetadataMask = 0xFF )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type MetaSegment ¶
type MetaSegment struct {
// contains filtered or unexported fields
}
MetaSegment defines a strictly bounded bit-range within the 8-bit Metadata space. It stores a pre-shifted mask for zero-cost bit clears during updates.
func NewMetaSegment ¶
func NewMetaSegment(length, offset uint8) MetaSegment
NewMetaSegment creates a definition for a metadata field.
- length: the number of bits allocated to this segment (1 to 8).
- offset: the starting bit position from the right (0 to 7).
Example of a segment with length=3 and offset=2:
7 6 5 4 3 2 1 0 (Metadata Bit Index)
+---+---+---+---+---+---+---+---+
| | | | ■ | ■ | ■ | | |
+---+---+---+---+---+---+---+---+
^^^^^^^^^
Segment Space
type UID64 ¶
type UID64 uint64
UID64 is a bit-packed 64-bit Generational Unique Identifier.
Bit layout configuration:
63 56 55 32 31 0 +------------+------------------------+--------------------------------+ | Metadata | Generation | Index | | (8 bits) | (24 bits) | (32 bits) | +------------+------------------------+--------------------------------+
Component breakdown:
- Bits 00-31: Index (32 bits) - Main sequence for array/pool offsets.
- Bits 32-55: Generation (24 bits) - Recycling counter preventing ABA problems.
- Bits 56-63: Metadata (8 bits) - User-defined space for module flags.
func (UID64) Generation ¶
Generation extracts the 24-bit generation counter from the UID64.
func (UID64) MetaSegment ¶
func (u UID64) MetaSegment(s MetaSegment) uint8
MetaSegment reads the value of a specific metadata segment directly from the UID64.
func (UID64) WithMetaSegment ¶
func (u UID64) WithMetaSegment(s MetaSegment, value uint8) UID64
WithMetaSegment returns a copy of the UID64 with only the specified segment updated. Excess bits in the provided value are silently truncated to prevent corruption.
type UID64Pool ¶
type UID64Pool struct {
// contains filtered or unexported fields
}
UID64Pool manages the allocation, recycling, and validation of UID64 identifiers.
Example ¶
ExampleUID64Pool shows the allocate / release / recycle lifecycle: releasing an id bumps its index's generation, so the old reference stops validating and the next allocation reuses the index under a fresh generation.
package main
import (
"fmt"
"github.com/kjkrol/uid"
)
func main() {
var pool uid.UID64Pool
pool.Init(1000, 100)
// Allocate
id := pool.Next()
// Unpack returns both index and generation
index, gen := id.Unpack()
fmt.Printf("Allocated: Index %d, Gen %d\n", index, gen)
// Release invalidates the current generation of this index
pool.Release(id)
if !pool.IsValid(id) {
fmt.Println("Old reference is invalid.")
}
// Next allocation reuses the index but increments the generation
recycled := pool.Next()
fmt.Printf("Recycled: Index %d, Gen %d\n", recycled.Index(), recycled.Generation())
}
Output: Allocated: Index 0, Gen 0 Old reference is invalid. Recycled: Index 0, Gen 1
Example (Batch) ¶
ExampleUID64Pool_batch shows NextN reserving several ids at once into a caller-owned buffer (zero allocation).
package main
import (
"fmt"
"github.com/kjkrol/uid"
)
func main() {
var pool uid.UID64Pool
pool.Init(1000, 100)
ids := make([]uid.UID64, 4)
pool.NextN(ids)
for _, id := range ids {
fmt.Printf("Index %d, Gen %d\n", id.Index(), id.Generation())
}
}
Output: Index 0, Gen 0 Index 1, Gen 0 Index 2, Gen 0 Index 3, Gen 0
func (*UID64Pool) Init ¶ added in v0.2.0
Init prepares the pool with pre-allocated capacities: indexCap sizes the index generation table (the index space the pool can address before growing) and recycleCap sizes the released-index recycling list. It resets any prior state, so it may also be used to re-initialise a reused pool.
func (*UID64Pool) Next ¶
Next returns a new, valid UID64. It reuses an old index if available, otherwise it allocates a new one.
func (*UID64Pool) NextN ¶ added in v0.2.0
NextN reserves len(dst) fresh UID64s and writes them into dst. The caller owns the buffer, so it is zero-alloc and reusable across calls. Recycled indices are drained first (LIFO, with their current generation), then the remainder is allocated as one contiguous run from the high-water mark, growing the generation table at most once — amortising the per-id branch, capacity check and growth that Next() pays on every call.
Source Files