A header only library that provides a few bitpacked data structures
UInt_pair
stores a pair in the bits of a single integer type.tagged_ptr
stores a pointer plus some data in the bottom few bits.variant_ptr
stores a pointer plus a tag that indicates which type it points to
These are useful building blocks for creating cache-friendly data structures.
These are intended to be somewhat interchangeable with std::pair
and std::variant
, with some limitations. Also, tagged_ptr
’s interface is loosely modeled off of std::unique
and std::shared
.
I haven’t written them here yet, but you will find some basic usage in tests/test.cpp
Everything will try its best to be noexcept
(if asserts are disabled) and constexpr
.
/**
* A pair packed into a specified UInt type.
* X = the type on the "left"
* Y = the type on the "right"
* UInt = the unsigned int type to stuff the pair into
* low_bit_count_ = how many bits of the Y value do we store?
*/
template<class X,
class Y,
std::unsigned_integral UInt,
int low_bit_count_ = bits::bit_sizeof<Y>>
class UInt_pair;
- default constructor
UInt_pair(X,Y)
/** * x = the "left" value * y = the "right" value */ explicit constexpr UInt_pair(X const x, Y const y)
get
is analogous tostd::get
.template<class T> bitpack::get
returns the value of typeT
contained in the pair if it exists.template<auto i> bitpack::get
returns the value of the ith element (i must be 0 or 1)
operator==
performs elementwise equality comparison (same asstd::pair
’s==
)operator<=>
performs lexicographic comparison (same asstd::pair
’s==
)explicit operator std::pair<X,Y>
returns thestd::pair
holding the same elements.
template<class X, class Y, int low_bit_count = bits::bit_sizeof<Y>>
using uintptr_pair = UInt_pair<X, Y, uintptr_t, low_bit_count>;
Is a specialization of UInt_pair
that always uses a uintptr_t
. There’s also a make_uintptr_pair
helper until we have alias deduction guides.
/**
* Holds a pointer(`T*`) and puts a tag(`Tag`) in the low bits(the number
* `tag_size` of lowest bits). Optionally, use `ptr_replacement_bits` to fill
* the low bits of the pointer back in. Provide a smart pointer-- like
* interface to get at the underlying pointer.
*
* Ptr = the pointer type to hold
* Tag = the tag type to hold (probably an enum or small number)
* tag_bits_ = the number of bits needed to store the tag
* ptr_replacement_bits = if the low bits of the pointer aren't 0, what should
* they be filled in with?
*/
template<class Ptr,
class Tag,
uintptr_t tag_bits_ = std::bit_width(alignof(traits::unptr_t<Ptr>) - 1),
uintptr_t ptr_replacement_bits = 0u>
class tagged_ptr;
- default constructor
tagged_ptr(Ptr ptr, Tag tag)
/** * ptr = the pointer to store * tag = the tag to store */ explicit constexpr tagged_ptr(Ptr const ptr, Tag const tag)
this->get()
returns the pointerthis->tag()
returns the tag
operator*
dereferences the stored pointeroperator->
calls members of the pointed-to objectoperator==
compares element-wise (pointer and tag). But if you compare againstnullptr_t
, we just check for null-ness (regardless of tag).operator bool
does this point to null?
- default constructor
- constructor from a pointer:
template<class T> explicit(alignof(traits::unptr_t<T>) <= tag_bits) // If alignment<= number. of tag bits, then inserting it into the variant // risks clobbering meaningful low bits of the address. So we require it // be done explicitly. constexpr variant_ptr(T ptr)
As long as the type
T
has large enough alignment to store the tag, this can be implicitly constructed. Otherwise, it is up to the user to ensure there are enough free low bits, so this must be explicitly bought-into.
this->index()
gives a number corresponding to the type of the currently stored value
These work like their analogues for std::variant
.
get<class>
andget<number>
maybe_get<class>
andmaybe_get<number>
(in<bitpack/maybe_get.hpp>
). Because we squish the tag and the pointer into a single object, we cannot return pointers to them. So we can’t implementget_if
. Instead,maybe_get
returns anstd::optional
. If the type is in the variant, returnstd::optional{the_value}
. Otherwise, we returnstd::nullopt
.holds_alternative<class>
visit
(only takes one variant, unlike thestd::
version)
operator==
Liketagged_ptr
, this is equality-comparable tostd::nullptr_t
.operator bool()
: does it hold a null pointer of any type?
BITPACK_UNROLL_VISIT_N
. You can ignore it safely. It shouldn’t affect correctness at all. This is solely for optimization. BecauseC++20
does not have a way to expand parameter packs into cases for aswitch
statement, we have to use tail recursion to implementvisit
. To help optimizers, there are a few macros that will unroll this tail recursion into one bigswitch
on the index. This variable macro determines up to what sizevariant_ptr
to unroll for. Seemacros.hpp
for more info.