Crate tagged_pointer[−][src]
This crate provides an implementation of tagged pointers: pointers that also contain an integer tag in a space-efficient manner.
Unless the fallback implementation is used (see the
Assumptions section below), both TaggedPtr
and
Option<TaggedPtr>
are guaranteed to be the size of a pointer.
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; use typenum::U2; #[repr(align(4))] struct Item(u32, u32); // `TaggedPtr` and `Option<TaggedPtr>` are both the size of a pointer: assert_eq!(size_of::<TaggedPtr<Item, U2>>(), size_of::<usize>()); assert_eq!(size_of::<Option<TaggedPtr<Item, U2>>>(), size_of::<usize>()); 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::<_, U2>::new(NonNull::from(&item1), 1); let tp2 = TaggedPtr::<_, U2>::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));
Assumptions
This crate relies on pointer::align_offset
not failing
under certain circumstances. Specifically, align_offset
must succeed
when the desired alignment is less than or equal to the alignment of the
allocation pointed to by the provided pointer. In practice, this is true,
even in Miri with the -Zmiri-symbolic-alignment-check
flag, but the
specifications of align_offset
technically allow an implementation not
to follow this behavior. If you experience issues due to this, please file
an issue in the Git repository. As a workaround, you can enable the
"fallback"
feature, which avoids relying on align_offset
at the cost
of making TaggedPtr
twice as large.
Note that this crate is always sound: an implementation of align_offset
that doesn’t follow the required behavior may cause panics, but not
undefined behavior.
Unfortunately, there’s currently no way to implement space-efficient tagged
pointers in Rust without making some assumptions. However, this approach
has some advantages over the usual method of casting the pointer to a
usize
and reusing the lower bits: the usual approach makes
platform-specific assumptions about the representation of pointers (which
currently apply to all platforms supported by rustc but could be
invalidated if support for new architectures is added, and there are
real architectures which do not allow reusing the lower bits of aligned
pointers), whereas this crate’s assumptions are platform-independent (aside
from the requirements already imposed by Rust, like having 8-bit bytes) and
are satisfied by all known implementations of Rust, including Miri with
-Zmiri-symbolic-alignment-check
.
Structs
TaggedPtr | A tagged pointer: a space-efficient representation of a pointer and integer tag. |