subetha_cxc/
tagged_offset_ptr.rs

1//! `TaggedOffsetPtr<T, const TAG_BITS: u32>` - high-bit-stealing
2//! variant of [`OffsetPtr`](crate::OffsetPtr).
3//!
4//! Steals the TOP `TAG_BITS` bits of the u32 index for a small type
5//! tag, leaving `(32 - TAG_BITS)` bits of index space.
6//!
7//! # Why high-bit stealing
8//!
9//! Classical tagged pointers steal the LOW bits because aligned
10//! pointers have low bits guaranteed zero. We work with INDICES,
11//! not addresses, so alignment is irrelevant. The natural free
12//! bits in an index are the HIGH bits, because most regions don't
13//! fill all 4 billion u32 slots. With `TAG_BITS = 4` you still
14//! get 268M slots and 16 type IDs - plenty for most data
15//! structures.
16//!
17//! # Typical sizes
18//!
19//! | TAG_BITS | Max tag | Max index | Typical use |
20//! |---|---|---|---|
21//! | 1 | 1 | 2.1B | Generation parity / dirty bit |
22//! | 2 | 3 | 1.07B | 4-state machine |
23//! | 3 | 7 | 537M | 8-color / 8-type discriminator |
24//! | 4 | 15 | 268M | 16 node types in a tree |
25//! | 8 | 255 | 16.7M | 256 distinct kinds; still huge index space |
26//!
27//! # Bit layout
28//!
29//! ```text
30//!   bit 31                            bit 0
31//!   [TAG_BITS][         32 - TAG_BITS         ]
32//!     tag              index
33//! ```
34//!
35//! NIL is `u32::MAX` (all-ones, both tag and index saturated).
36//! Distinguishable from any meaningful `(tag, index)` pair as long
37//! as the caller doesn't create one with tag == max_tag AND index ==
38//! max_index. For safety, use `NIL` constant rather than constructing
39//! all-ones manually.
40//!
41//! # Integration with SharedRegion
42//!
43//! Pass `ptr.index()` to `SharedRegion::get` / `set`. The tag bits
44//! are caller-managed: type discriminator, state flag, color,
45//! generation parity, whatever the data structure encodes.
46
47use std::marker::PhantomData;
48
49#[derive(Debug, Clone, Copy, PartialEq, Eq)]
50pub enum TaggedPtrError {
51    TagOutOfRange,
52    IndexOutOfRange,
53}
54
55/// A 32-bit position-independent pointer with `TAG_BITS` high bits
56/// reserved for a caller-defined tag. Packs `(tag, index)` into one
57/// `u32`. Cross-process safe: same raw bits resolve to the same
58/// `(tag, index)` in every process.
59#[derive(Debug)]
60#[repr(C)]
61pub struct TaggedOffsetPtr<T, const TAG_BITS: u32> {
62    packed: u32,
63    _phantom: PhantomData<T>,
64}
65
66impl<T, const TAG_BITS: u32> Clone for TaggedOffsetPtr<T, TAG_BITS> {
67    fn clone(&self) -> Self { *self }
68}
69impl<T, const TAG_BITS: u32> Copy for TaggedOffsetPtr<T, TAG_BITS> {}
70impl<T, const TAG_BITS: u32> PartialEq for TaggedOffsetPtr<T, TAG_BITS> {
71    fn eq(&self, other: &Self) -> bool { self.packed == other.packed }
72}
73impl<T, const TAG_BITS: u32> Eq for TaggedOffsetPtr<T, TAG_BITS> {}
74impl<T, const TAG_BITS: u32> std::hash::Hash for TaggedOffsetPtr<T, TAG_BITS> {
75    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
76        self.packed.hash(state);
77    }
78}
79
80impl<T, const TAG_BITS: u32> TaggedOffsetPtr<T, TAG_BITS> {
81    // Compile-time bounds check: TAG_BITS must be 0..=31. At 32 we'd
82    // need a 33-bit shift which is UB; at >=32 the index space is
83    // zero which has no useful meaning. This const item is evaluated
84    // when the type is instantiated, blocking invalid TAG_BITS at
85    // monomorphisation time.
86    const _ASSERT_TAG_BITS: () = assert!(
87        TAG_BITS <= 31,
88        "TAG_BITS must be in 0..=31 (32 would leave no index bits)",
89    );
90
91    /// All-ones bit pattern serving as a NIL sentinel.
92    pub const NIL: Self = Self { packed: u32::MAX, _phantom: PhantomData };
93
94    /// Maximum tag value: `(1 << TAG_BITS) - 1`. Returns 0 when
95    /// TAG_BITS == 0.
96    pub const fn max_tag() -> u32 {
97        if TAG_BITS == 0 { 0 } else { (1u32 << TAG_BITS) - 1 }
98    }
99
100    /// Maximum index value: `(1 << (32 - TAG_BITS)) - 1`. Returns
101    /// `u32::MAX` when TAG_BITS == 0.
102    pub const fn max_index() -> u32 {
103        let idx_bits = 32 - TAG_BITS;
104        if idx_bits == 32 { u32::MAX } else { (1u32 << idx_bits) - 1 }
105    }
106
107    /// Bit mask covering the index portion of the packed word.
108    #[inline]
109    pub const fn index_mask() -> u32 { Self::max_index() }
110
111    /// Bit shift for the tag (== 32 - TAG_BITS).
112    #[inline]
113    pub const fn tag_shift() -> u32 { 32 - TAG_BITS }
114
115    /// Construct from `(index, tag)`. Panics if either component
116    /// exceeds its range. Use [`try_new`](Self::try_new) for
117    /// fallible construction.
118    pub fn new(index: u32, tag: u32) -> Self {
119        // Force the const-eval ASSERT to fire if TAG_BITS is invalid.
120        let _: () = Self::_ASSERT_TAG_BITS;
121        assert!(
122            tag <= Self::max_tag(),
123            "tag {tag} exceeds MAX_TAG {} (TAG_BITS={TAG_BITS})",
124            Self::max_tag(),
125        );
126        assert!(
127            index <= Self::max_index(),
128            "index {index} exceeds MAX_INDEX {} (TAG_BITS={TAG_BITS})",
129            Self::max_index(),
130        );
131        let packed = if TAG_BITS == 0 {
132            // Edge case: TAG_BITS=0 means no tag bits; the whole
133            // word is the index.
134            index
135        } else {
136            (tag << Self::tag_shift()) | index
137        };
138        Self { packed, _phantom: PhantomData }
139    }
140
141    /// Fallible construction. Returns `Err(TagOutOfRange)` or
142    /// `Err(IndexOutOfRange)` instead of panicking.
143    pub fn try_new(index: u32, tag: u32) -> Result<Self, TaggedPtrError> {
144        if tag > Self::max_tag() { return Err(TaggedPtrError::TagOutOfRange); }
145        if index > Self::max_index() { return Err(TaggedPtrError::IndexOutOfRange); }
146        let packed = if TAG_BITS == 0 {
147            index
148        } else {
149            (tag << Self::tag_shift()) | index
150        };
151        Ok(Self { packed, _phantom: PhantomData })
152    }
153
154    /// Construct from the raw packed `u32` representation. Useful
155    /// for deserialisation. Caller is responsible for ensuring the
156    /// raw value is meaningful for the chosen `TAG_BITS`.
157    #[inline]
158    pub const fn from_raw(packed: u32) -> Self {
159        Self { packed, _phantom: PhantomData }
160    }
161
162    /// Extract the raw packed `u32`. Useful for serialisation.
163    #[inline]
164    pub const fn raw(self) -> u32 { self.packed }
165
166    /// Extract the index portion.
167    #[inline]
168    pub fn index(self) -> u32 { self.packed & Self::index_mask() }
169
170    /// Extract the tag portion.
171    #[inline]
172    pub fn tag(self) -> u32 {
173        if TAG_BITS == 0 { 0 } else { self.packed >> Self::tag_shift() }
174    }
175
176    /// Return a new pointer with the same index but a different tag.
177    pub fn with_tag(self, new_tag: u32) -> Self {
178        Self::new(self.index(), new_tag)
179    }
180
181    /// Return a new pointer with the same tag but a different index.
182    pub fn with_index(self, new_index: u32) -> Self {
183        Self::new(new_index, self.tag())
184    }
185
186    /// True when the pointer is the NIL sentinel.
187    #[inline]
188    pub fn is_nil(self) -> bool { self.packed == u32::MAX }
189}
190
191#[cfg(test)]
192mod tests {
193    use super::*;
194
195    #[test]
196    fn tag_bits_4_max_tag_and_index() {
197        type P = TaggedOffsetPtr<u64, 4>;
198        assert_eq!(P::max_tag(), 15);  // 2^4 - 1
199        assert_eq!(P::max_index(), (1u32 << 28) - 1);  // 268_435_455
200        assert_eq!(P::tag_shift(), 28);
201    }
202
203    #[test]
204    fn tag_bits_0_degenerates_to_offset_ptr() {
205        type P = TaggedOffsetPtr<u64, 0>;
206        assert_eq!(P::max_tag(), 0);
207        assert_eq!(P::max_index(), u32::MAX);
208        // Only valid tag is 0.
209        let p = P::new(123, 0);
210        assert_eq!(p.index(), 123);
211        assert_eq!(p.tag(), 0);
212    }
213
214    #[test]
215    fn pack_unpack_round_trip_tag_bits_4() {
216        type P = TaggedOffsetPtr<u64, 4>;
217        let p = P::new(42, 7);
218        assert_eq!(p.index(), 42);
219        assert_eq!(p.tag(), 7);
220    }
221
222    #[test]
223    fn pack_unpack_round_trip_tag_bits_8() {
224        type P = TaggedOffsetPtr<u64, 8>;
225        assert_eq!(P::max_tag(), 255);
226        assert_eq!(P::max_index(), (1u32 << 24) - 1);
227        let p = P::new(99_999, 200);
228        assert_eq!(p.index(), 99_999);
229        assert_eq!(p.tag(), 200);
230    }
231
232    #[test]
233    fn raw_round_trip() {
234        type P = TaggedOffsetPtr<u64, 4>;
235        let p = P::new(42, 7);
236        let raw = p.raw();
237        let q = P::from_raw(raw);
238        assert_eq!(p, q);
239        assert_eq!(q.index(), 42);
240        assert_eq!(q.tag(), 7);
241    }
242
243    #[test]
244    fn with_tag_keeps_index() {
245        type P = TaggedOffsetPtr<u64, 4>;
246        let p = P::new(42, 7);
247        let q = p.with_tag(3);
248        assert_eq!(q.index(), 42);
249        assert_eq!(q.tag(), 3);
250    }
251
252    #[test]
253    fn with_index_keeps_tag() {
254        type P = TaggedOffsetPtr<u64, 4>;
255        let p = P::new(42, 7);
256        let q = p.with_index(100);
257        assert_eq!(q.index(), 100);
258        assert_eq!(q.tag(), 7);
259    }
260
261    #[test]
262    fn try_new_rejects_oversized_tag() {
263        type P = TaggedOffsetPtr<u64, 4>;
264        assert_eq!(P::try_new(0, 16).err(), Some(TaggedPtrError::TagOutOfRange));
265        assert_eq!(P::try_new(0, 999).err(), Some(TaggedPtrError::TagOutOfRange));
266    }
267
268    #[test]
269    fn try_new_rejects_oversized_index() {
270        type P = TaggedOffsetPtr<u64, 4>;
271        let max = P::max_index();
272        assert!(P::try_new(max, 0).is_ok());
273        assert_eq!(P::try_new(max + 1, 0).err(), Some(TaggedPtrError::IndexOutOfRange));
274    }
275
276    #[test]
277    #[should_panic(expected = "tag")]
278    fn new_panics_on_oversized_tag() {
279        type P = TaggedOffsetPtr<u64, 4>;
280        let _p = P::new(0, 999);
281    }
282
283    #[test]
284    #[should_panic(expected = "index")]
285    fn new_panics_on_oversized_index() {
286        type P = TaggedOffsetPtr<u64, 4>;
287        let _p = P::new(u32::MAX, 0);
288    }
289
290    #[test]
291    fn nil_is_all_ones_and_detectable() {
292        type P = TaggedOffsetPtr<u64, 4>;
293        let n = P::NIL;
294        assert!(n.is_nil());
295        assert_eq!(n.raw(), u32::MAX);
296        let p = P::new(0, 0);
297        assert!(!p.is_nil());
298    }
299
300    #[test]
301    fn equality_and_hash() {
302        use std::collections::HashSet;
303        type P = TaggedOffsetPtr<u64, 4>;
304        let a = P::new(5, 1);
305        let b = P::new(5, 1);
306        let c = P::new(5, 2);
307        let d = P::new(6, 1);
308        assert_eq!(a, b);
309        assert_ne!(a, c);
310        assert_ne!(a, d);
311        let mut s = HashSet::new();
312        s.insert(a);
313        assert!(s.contains(&b));
314        assert!(!s.contains(&c));
315        assert!(!s.contains(&d));
316    }
317
318    #[test]
319    fn boundary_index_at_max_for_tag_bits_4() {
320        type P = TaggedOffsetPtr<u64, 4>;
321        let max_idx = P::max_index();
322        let p = P::new(max_idx, 0);
323        assert_eq!(p.index(), max_idx);
324        assert_eq!(p.tag(), 0);
325        // Max tag with max index.
326        let max_tag = P::max_tag();
327        let p2 = P::new(max_idx, max_tag);
328        assert_eq!(p2.index(), max_idx);
329        assert_eq!(p2.tag(), max_tag);
330    }
331
332    #[test]
333    fn integration_with_shared_region_via_index_extraction() {
334        use crate::SharedRegion;
335        use std::path::PathBuf;
336
337        let mut p: PathBuf = std::env::temp_dir();
338        let pid = std::process::id();
339        p.push(format!("subetha-tagged-region-{pid}.bin"));
340
341        // SharedRegion holding heterogeneous nodes; tag discriminates
342        // 4 node kinds (Leaf=0, Internal=1, Tombstone=2, Sentinel=3).
343        #[derive(Clone, Copy, Debug, PartialEq)]
344        #[repr(C)]
345        struct Node { key: u64, value: u64 }
346
347        let r: SharedRegion<Node> = SharedRegion::create(&p, 16).unwrap();
348        // Allocate a slot; wrap the returned OffsetPtr's index in
349        // a TaggedOffsetPtr<Node, 2> with tag=1 (Internal).
350        let inner = r.allocate(Node { key: 42, value: 100 }).unwrap();
351        type P = TaggedOffsetPtr<Node, 2>;
352        let tagged = P::new(inner.index, 1);
353        assert_eq!(tagged.tag(), 1);
354        // Resolve back: use the index to query SharedRegion.
355        let n = r.get(crate::OffsetPtr::new(tagged.index())).unwrap();
356        assert_eq!(n, Node { key: 42, value: 100 });
357        std::fs::remove_file(&p).ok();
358    }
359
360    #[test]
361    fn cross_process_position_independence_via_raw_bits() {
362        // The same packed u32 resolves to the same (index, tag) in
363        // any process. Demonstrated by raw round-trip; in real use
364        // the u32 is the cross-process-stable representation.
365        type P = TaggedOffsetPtr<u64, 4>;
366        let producer = P::new(1234, 9);
367        let raw = producer.raw();
368        // (any other process would do: P::from_raw(raw))
369        let consumer = P::from_raw(raw);
370        assert_eq!(consumer.index(), 1234);
371        assert_eq!(consumer.tag(), 9);
372    }
373
374    #[test]
375    fn tag_bits_1_dirty_bit_pattern() {
376        // A common use: 1 bit for a dirty/clean state flag.
377        type P = TaggedOffsetPtr<u64, 1>;
378        assert_eq!(P::max_tag(), 1);
379        assert_eq!(P::max_index(), i32::MAX as u32);  // 2^31 - 1
380        let clean = P::new(42, 0);
381        let dirty = clean.with_tag(1);
382        assert_eq!(dirty.index(), clean.index());
383        assert_ne!(dirty, clean);
384        assert_eq!(dirty.tag(), 1);
385    }
386}
subetha_cxc/tagged_offset_ptr.rs

subetha_cxc/
tagged_offset_ptr.rs
