TaggedPointer.h

#pragma once
 
#include <xrpl/basics/SHAMapHash.h>
#include <xrpl/shamap/SHAMapTreeNode.h>
 
#include <bit>
#include <cstdint>
#include <optional>
#include <tuple>
#include <utility>
#include <version>  // IWYU pragma: keep
 
namespace xrpl {

class TaggedPointer
{
private:
    static_assert(
        alignof(SHAMapHash) >= 4,
        "Bad alignment: Tag pointer requires low two bits to be zero.");
    std::uintptr_t tp_ = 0;
    static constexpr std::uintptr_t kTagMask = 3;
    static constexpr std::uintptr_t kPtrMask = ~kTagMask;

    void
    destroyHashesAndChildren();
 
    struct RawAllocateTag
    {
    };

    explicit TaggedPointer(RawAllocateTag, std::uint8_t numChildren);
 
public:
    TaggedPointer() = delete;
    explicit TaggedPointer(std::uint8_t numChildren);

    explicit TaggedPointer(TaggedPointer&& other, std::uint16_t isBranch, std::uint8_t toAllocate);

    explicit TaggedPointer(
        TaggedPointer&& other,
        std::uint16_t srcBranches,
        std::uint16_t dstBranches,
        std::uint8_t toAllocate);
 
    TaggedPointer(TaggedPointer const&) = delete;
 
    TaggedPointer(TaggedPointer&&);
 
    TaggedPointer&
    operator=(TaggedPointer&&);
 
    ~TaggedPointer();

    [[nodiscard]] std::pair<std::uint8_t, void*>
    decode() const;

    [[nodiscard]] std::uint8_t
    capacity() const;

    [[nodiscard]] bool
    isDense() const;

    [[nodiscard]] std::tuple<std::uint8_t, SHAMapHash*, SHAMapTreeNodePtr*>
    getHashesAndChildren() const;

    [[nodiscard]] SHAMapHash*
    getHashes() const;

    [[nodiscard]] SHAMapTreeNodePtr*
    getChildren() const;

    template <class F>
    void
    iterChildren(std::uint16_t isBranch, F&& f) const;

    template <class F>
    void
    iterNonEmptyChildIndexes(std::uint16_t isBranch, F&& f) const;

    [[nodiscard]] std::optional<int>
    getChildIndex(std::uint16_t isBranch, int i) const;
};
 
[[nodiscard]] inline int
popcnt16(std::uint16_t a)
{
#if __cpp_lib_bitops
    return std::popcount(a);
#elif defined(__clang__) || defined(__GNUC__)
    return __builtin_popcount(a);
#else
    // fallback to table lookup
    static constexpr auto tbl = []() {
        std::array<std::uint8_t, 256> ret{};
        for (int i = 0; i != 256; ++i)
        {
            for (int j = 0; j != 8; ++j)
            {
                if (i & (1 << j))
                    ret[i]++;
            }
        }
        return ret;
    }();
    return tbl[a & 0xff] + tbl[a >> 8];
#endif
}
 
}  // namespace xrpl