A pointer class storing flags in unused address bits.

tagged_ptr.cpp

#include <cassert>
#include <cstdint>
#include <iostream>
#include <type_traits>

template <unsigned arg, unsigned result = 0>
constexpr unsigned log2 = log2<(arg >> 1), result + 1>;

template <unsigned result>
constexpr unsigned log2<1, result> = result;

template <unsigned arg, unsigned result = 1>
constexpr unsigned exp2 = exp2<arg - 1, result << 1>;

template <unsigned result>
constexpr unsigned exp2<0, result> = result;


template <typename tag_type, typename T, unsigned num_tags = log2<std::alignment_of<T>::value>>
class tagged_ptr final {
public:
    tagged_ptr() noexcept
        : tagged_ptr(nullptr)
    {
    }
    
    explicit tagged_ptr(T* p) noexcept
        : ptr{reinterpret_cast<uintptr_t>(p)}
    {
        static_assert(num_tags >= tag_type::num_tags, "enum defines too many flags");
        assert((ptr & bitmask()) == 0);
    }
    
    tagged_ptr(tagged_ptr const&) noexcept = default;
    tagged_ptr(tagged_ptr&&) noexcept = default;
    
    tagged_ptr& operator=(tagged_ptr const&) = default;
    tagged_ptr& operator=(tagged_ptr&&) = default;
    
    ~tagged_ptr() noexcept = default;    
    
    T& operator*() noexcept {
        return *reinterpret_cast<T*>(ptr & ~bitmask());
    }
    
    T const& operator*() const noexcept {
        return *reinterpret_cast<T const*>(ptr & ~bitmask());
    }
    
    T* operator->() noexcept {
        return reinterpret_cast<T*>(ptr & ~bitmask());
    }
    
    T const* operator->() const noexcept {
        return reinterpret_cast<T const*>(ptr & ~bitmask());
    }
    
    static constexpr uintptr_t bitmask() noexcept {
        return (1 << num_tags) - 1;
    }
    
    template <tag_type t>
    bool check() const noexcept {
        return ptr & exp2<static_cast<unsigned>(t)>;
    }
    
    template <tag_type t>
    void set(bool v) noexcept {
        constexpr auto i = static_cast<unsigned>(t);
        
        if (v) {
            ptr |= (1 << i);
        }
        else {
            ptr &= ~(1 << i);
        }
    }
    
private:
    uintptr_t ptr;
};

template <typename tag_type, typename T>
tagged_ptr<tag_type, T> make_tagged(T* ptr) noexcept {
    return tagged_ptr<tag_type, T>{ptr};
}

template <typename tag_type, typename T>
tagged_ptr<tag_type, T const> const make_tagged(T const* ptr) noexcept {
    return tagged_ptr<tag_type, T const>{ptr};
}

enum tree_tags {
    is_inner_node,
    is_leaf_node = 5,

    num_tags
};

template <unsigned num_tags>
struct alignas(exp2<num_tags>) tagged_struct {};

// a node with 6 tag bits
struct tree_node : tagged_struct<6> {
    using pointer = tagged_ptr<tree_tags, tree_node, 6>;
    
    tree_node(std::string v) : value{v} {}
    std::string value;
};


int main() {
    tree_node n1 { "hi" };
    tree_node* n2 = new tree_node { "there" };
           
    auto p1 = tree_node::pointer(&n1);
    auto p2 = tree_node::pointer(n2);
    
    std::cout << p1->value << " - inner: " << p1.check<is_inner_node>() << "; leaf: " << p1.check<is_leaf_node>() << std::endl;
    std::cout << p2->value << " - inner: " << p2.check<is_inner_node>() << "; leaf: " << p2.check<is_leaf_node>() << std::endl;
    
    p1.set<is_inner_node>(true);
    p2.set<is_leaf_node>(true);
    
    std::cout << p1->value << " - inner: " << p1.check<is_inner_node>() << "; leaf: " << p1.check<is_leaf_node>() << std::endl;
    std::cout << p2->value << " - inner: " << p2.check<is_inner_node>() << "; leaf: " << p2.check<is_leaf_node>() << std::endl;
}