13 releases
new 0.2.8 | Oct 28, 2024 |
---|---|
0.2.7 | Apr 28, 2023 |
0.2.6 | Dec 20, 2022 |
0.2.3 | Sep 4, 2022 |
0.1.3 | Mar 19, 2021 |
#229 in Data structures
153 downloads per month
Used in 2 crates
(via btree-vec)
73KB
977 lines
tagged-pointer
This crate provides an implementation of tagged pointers: a
space-efficient representation of a pointer and integer tag. In particular,
both TaggedPtr
and Option<TaggedPtr>
are the size of a pointer
despite containing both a pointer and tag.
This crate depends only on core
, so it can be used in no_std
environments.
Example
use core::mem::size_of;
use core::ptr::NonNull;
use tagged_pointer::TaggedPtr;
#[repr(align(4))]
struct Item(u32, u32);
// `TaggedPtr` and `Option<TaggedPtr>` are both the size of a pointer:
assert_eq!(size_of::<TaggedPtr<Item, 2>>(), size_of::<*mut ()>());
assert_eq!(size_of::<Option<TaggedPtr<Item, 2>>>(), size_of::<*mut ()>());
let item1 = Item(1, 2);
let item2 = Item(3, 4);
// We can store two bits of the tag, since `Item` has an alignment of 4.
let tp1 = TaggedPtr::<_, 2>::new(NonNull::from(&item1), 1);
let tp2 = TaggedPtr::<_, 2>::new(NonNull::from(&item2), 3);
let (ptr1, tag1) = tp1.get();
let (ptr2, tag2) = tp2.get();
assert_eq!((ptr1, tag1), (NonNull::from(&item1), 1));
assert_eq!((ptr2, tag2), (NonNull::from(&item2), 3));
Platform considerations
The number of tag bits that can be stored in a pointer of a given type
depends on the type’s alignment. However, the alignment of many types is
platform-specific: u64
, for example, could have an
alignment of 8 on one platform and 4 on another.
Therefore, it is highly recommended to use #[repr(align)]
to guarantee a minimum alignment, defining a wrapper type if necessary:
// This won't work on systems where `u64` has an alignment of 4!
let x: u64 = 123;
let tp = TaggedPtr::<u64, 3>::new(NonNull::from(&x), 0b11);
// Instead, do this:
#[repr(align(8))]
struct MyU64(pub u64);
let x = MyU64(123);
let tp = TaggedPtr::<MyU64, 3>::new(NonNull::from(&x), 0b11);
Assumptions
This crate avoids making assumptions about the representations of pointers.
In particular, it does not cast pointers to usize
and assume that the
lower bits of that number can be used for tagging. There exist
architectures that do not allow reusing the lower bits of aligned pointers
in this manner, and even if none are currently supported by Rust, that
could change in the future. This crate’s approach also works better with
strict provenance.
Previously, this crate relied on assumptions about the behavior of
pointer::align_offset
in certain circumstances. These
assumptions were effectively always true, but were not strictly guaranteed,
so a fallback implementation was provided with the crate feature
fallback
, which would avoid relying on this assumption at the cost of
space efficiency.
However, as of Rust 1.78, this assumption is no longer necessary:
align_offset
is guaranteed to behave as required.