TaggedOffsetPtr<T, const TAG_BITS: u32>

A 32-bit position-independent pointer that packs a small caller- defined tag into the high bits of an OffsetPtr index. Still 4 bytes total, same as OffsetPtr<T>, but now also carries a TAG_BITS-wide discriminator that travels with the pointer through arrays, hash maps, and cross-process MMF storage.

Use it when you want both a slot reference and a small classifier in the same word. Tree-node kind, color (for tri- color GC or red-black trees), generation parity, dirty bit, tombstone flag, version tag are all common candidates. With TAG_BITS = 4 you keep 268 million slots and gain 16 tag values at zero size cost.

Constraints (read first):

• Pointer encoding only, not an allocator. Pair with a SharedRegion or any slot-indexed structure. The crate inherits every SharedRegion constraint (cross- process MMF, T: Copy + 'static, fixed capacity, non-thread- safe clear).
• TAG_BITS must be in 0..=31. A compile-time const assertion blocks invalid choices; TAG_BITS = 32 leaves zero index bits.
• Index range shrinks as TAG_BITS grows. TAG_BITS = 4 leaves 268 M slots; TAG_BITS = 16 collapses both halves to 65 K. Pick the smallest tag width that covers your discriminator.
• Reader and writer must agree on TAG_BITS out of band. TAG_BITS is a const generic; it is not stored in the MMF. A reader decoding with a different TAG_BITS than the writer splits the packed u32 differently and silently reads the wrong index.
• new() panics on out-of-range arguments. Use try_new() for fallible construction at the API boundary.
• NIL = u32::MAX collides with (tag = max_tag, index = max_index). Reserve the top tag value OR the top index slot to keep the sentinel unambiguous.

Table of contents

• What it is
• Why high-bit stealing instead of low-bit stealing
• Typical TAG_BITS choices
• Bit layout
• API at a glance
• Worked example
• Benchmark results
• Integration with SharedRegion
• Known limitations (verified)
• Common pitfalls
• Use case patterns

What it is

TaggedOffsetPtr<T, const TAG_BITS: u32> is a #[repr(C)] struct with one field plus a phantom marker:

pub struct TaggedOffsetPtr<T, const TAG_BITS: u32> {
    packed: u32,
    _phantom: PhantomData<T>,
}

TAG_BITS is a const generic. Each instantiation of the type produces a distinct memory layout with the chosen split between tag bits and index bits. A compile-time assertion blocks invalid choices (TAG_BITS > 31).

The four-byte width and #[repr(C)] make this type interchangeable with OffsetPtr<T> at the byte level for any data structure that needs to embed pointers in an MMF. Two processes that map the same file see the same packed u32 and decode the same (tag, index) pair.

Why high-bit stealing instead of low-bit stealing

Classical tagged pointers steal the low bits because aligned machine pointers have low bits guaranteed zero. A *const Node whose Node has 8-byte alignment is guaranteed to have its bottom 3 bits as 000, free for the taking.

This crate works with indices, not addresses. An index is just a u32 counter, with no alignment guarantees. The natural free bits in an index are the high bits, because most regions do not fill all 4 billion u32 slots:

For most workloads TAG_BITS = 4 is the sweet spot: 16 tag values covers most node-kind / state-flag use cases, and 268M slots remains a large region.

Typical TAG_BITS choices

Bit layout

    flowchart LR
    subgraph PACKED["TaggedOffsetPtr packed u32 (32 bits)"]
      direction LR
      TAG["[TAG_BITS]<br/>tag<br/>bits 31..32-TAG_BITS"]
      IDX["[32-TAG_BITS]<br/>index<br/>bits 31-TAG_BITS..0"]
    end

    classDef tag fill:#b91c1c,stroke:#7f1d1d,color:#ffffff
    classDef idx fill:#059669,stroke:#065f46,color:#ffffff
    class TAG tag
    class IDX idx
  

Pack and unpack are pure bit operations:

packed = (tag << (32 - TAG_BITS)) | index
index  = packed & ((1 << (32 - TAG_BITS)) - 1)
tag    = packed >> (32 - TAG_BITS)

The NIL sentinel is u32::MAX (all bits set). It is distinguishable from any meaningful (tag, index) pair so long as the caller does not construct one with tag == max_tag AND index == max_index simultaneously. Use the NIL constant to avoid collision.

API at a glance

Worked example

use subetha_cxc::{OffsetPtr, SharedRegion, TaggedOffsetPtr};

// Type alias: 4 tag bits => 16 node kinds, 268M slot indices.
type NodePtr = TaggedOffsetPtr<Node, 4>;

#[derive(Clone, Copy)]
#[repr(C)]
struct Node {
    key: u64,
    left: u32,   // packed NodePtr.raw()
    right: u32,
}

// Tag values: caller-defined.
const KIND_LEAF: u32 = 0;
const KIND_INTERNAL: u32 = 1;
const KIND_TOMBSTONE: u32 = 2;

let region: SharedRegion<Node> = SharedRegion::create("/tmp/tree.bin", 1024)?;

// Allocate a leaf node.
let raw = region.allocate(Node { key: 42, left: 0, right: 0 })?;
let leaf_ptr = NodePtr::new(raw.index, KIND_LEAF);

// Allocate an internal node pointing at the leaf.
let internal_node = Node {
    key: 100,
    left: leaf_ptr.raw(),
    right: leaf_ptr.raw(),
};
let internal_raw = region.allocate(internal_node)?;
let internal_ptr = NodePtr::new(internal_raw.index, KIND_INTERNAL);

// Dispatch on tag without touching the slot.
match leaf_ptr.tag() {
    KIND_LEAF => { /* handle leaf */ }
    KIND_INTERNAL => { /* handle internal */ }
    KIND_TOMBSTONE => { /* skip */ }
    _ => unreachable!(),
}

// Resolve via SharedRegion using the index portion.
let node = region.get(OffsetPtr::new(leaf_ptr.index()))?;

Benchmark results

Baseline: (OffsetPtr<T>, u8), a Rust tuple of an OffsetPtr plus a u8 tag. The natural alternative when a developer wants to keep a tag alongside a pointer.

Numbers are median of 10 samples, 2-second measurement window, on Windows x86-64. Each iteration is one operation. Lower is faster.

Why each result lands where it does

Integration with SharedRegion

TaggedOffsetPtr does not own storage. It is a pointer encoding, not a container. Use it alongside SharedRegion or any other slot-indexed structure:

let r: SharedRegion<Node> = SharedRegion::create(path, 1024)?;

// Allocate via SharedRegion (returns an OffsetPtr).
let raw = r.allocate(node)?;
// Wrap with a tag.
let tagged: TaggedOffsetPtr<Node, 4> = TaggedOffsetPtr::new(raw.index, tag);

// Later, resolve back through SharedRegion.
let resolved = r.get(OffsetPtr::new(tagged.index()))?;

The pattern is: SharedRegion is the allocator, TaggedOffsetPtr is the address book entry, and the tag is metadata the caller attaches at the allocation site.

Known limitations (verified)

Each limitation below is observable in the source.

1. TAG_BITS must be in 0..=31. A compile-time const assertion (_ASSERT_TAG_BITS) blocks invalid choices when the type is instantiated. TAG_BITS = 32 leaves zero index bits and triggers UB on the shift; the assertion prevents it.

2. No type-level distinction between different TAG_BITS. TaggedOffsetPtr<T, 4> and TaggedOffsetPtr<T, 8> are different types and cannot be assigned to each other. Switching tag width requires changing every type annotation.

3. No automatic association with a SharedRegion. The type carries PhantomData<T> for type safety, but the relationship to a specific region instance is the caller’s responsibility. A TaggedOffsetPtr<Node, 4> from region A is the same Rust type as one from region B; passing the wrong region to get silently reads the wrong bytes (or returns Err(InvalidPtr) if the index exceeds the wrong region’s capacity).

4. NIL collision risk. NIL = u32::MAX overlaps with the pair (tag = max_tag, index = max_index). Most callers will never construct that exact pair, but if a workload uses every tag value AND every index, the NIL sentinel becomes ambiguous. For safety, treat the bottom slot or top slot as reserved.

5. new() panics on out-of-range arguments. Use try_new() for fallible construction. The panic message names the offending value and the limit, which helps diagnosis but does not help recovery.

6. The tag is not validated against any type-level enum. tag() returns a u32 regardless of whether the caller defined exactly N distinct tag values. A newly-introduced tag value added by one process can be misinterpreted by an older process that does not know about it.

7. Equality and hashing operate on the packed word. Two pointers are equal only when both index and tag match. Two pointers to the same index with different tags hash to different buckets. This is usually desired; callers wanting “same slot regardless of tag” semantics must extract index() first.

Common pitfalls

// CORRECT:
let value = region.get(OffsetPtr::new(tagged.index()))?;

// WRONG when TAG_BITS > 0:
let value = region.get(OffsetPtr::new(tagged.raw()))?;

Use case patterns

back to subetha docs