From 8a95f504dfaef24e84b14398b4416bf9f1b552cd Mon Sep 17 00:00:00 2001 From: Richard Qin Date: Thu, 5 Nov 2026 08:44:49 +0800 Subject: [libbase][adt] Add pointer utility types --- libbase/include/core/adt/PointerIntPair.h | 301 +++++++++++++++++++++++ libbase/include/core/adt/PointerLikeTypeTraits.h | 165 +++++++++++++ 2 files changed, 466 insertions(+) create mode 100644 libbase/include/core/adt/PointerIntPair.h create mode 100644 libbase/include/core/adt/PointerLikeTypeTraits.h (limited to 'libbase/include/core/adt') diff --git a/libbase/include/core/adt/PointerIntPair.h b/libbase/include/core/adt/PointerIntPair.h new file mode 100644 index 0000000..6a7f5db --- /dev/null +++ b/libbase/include/core/adt/PointerIntPair.h @@ -0,0 +1,301 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + . +*/ + +//===- core/adt/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// This file defines the PointerIntPair class. +/// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_ADT_POINTERINTPAIR_H +#define LIBBASE_ADT_POINTERINTPAIR_H + +#include "core/compiler/Compiler.h" +#include "core/adt/PointerLikeTypeTraits.h" +#include +#include +#include +#include +#include + +namespace libbase { + +namespace detail { +template struct PunnedPointer { + static_assert(sizeof(Ptr) == sizeof(intptr_t), ""); + + // Asserts that allow us to let the compiler implement the destructor and + // copy/move constructors + static_assert(std::is_trivially_destructible::value, ""); + static_assert(std::is_trivially_copy_constructible::value, ""); + static_assert(std::is_trivially_move_constructible::value, ""); + + explicit constexpr PunnedPointer(intptr_t i = 0) { *this = i; } + + constexpr intptr_t asInt() const { + intptr_t R = 0; + std::memcpy(&R, Data, sizeof(R)); + return R; + } + + constexpr operator intptr_t() const { return asInt(); } + + constexpr PunnedPointer &operator=(intptr_t V) { + std::memcpy(Data, &V, sizeof(Data)); + return *this; + } + + Ptr *getPointerAddress() { return reinterpret_cast(Data); } + const Ptr *getPointerAddress() const { return reinterpret_cast(Data); } + +private: + alignas(Ptr) unsigned char Data[sizeof(Ptr)]; +}; +} // namespace detail + +template struct DenseMapInfo; +template +struct PointerIntPairInfo; + +/// PointerIntPair - This class implements a pair of a pointer and small +/// integer. It is designed to represent this in the space required by one +/// pointer by bitmangling the integer into the low part of the pointer. This +/// can only be done for small integers: typically up to 3 bits, but it depends +/// on the number of bits available according to PointerLikeTypeTraits for the +/// type. +/// +/// Note that PointerIntPair always puts the IntVal part in the highest bits +/// possible. For example, PointerIntPair will put the bit for +/// the bool into bit #2, not bit #0, which allows the low two bits to be used +/// for something else. For example, this allows: +/// PointerIntPair, 1, bool> +/// ... and the two bools will land in different bits. +template , + typename Info = PointerIntPairInfo> +class PointerIntPair { + // Used by MSVC visualizer and generally helpful for debugging/visualizing. + using InfoTy = Info; + detail::PunnedPointer Value; + +public: + constexpr PointerIntPair() = default; + + PointerIntPair(PointerTy PtrVal, IntType IntVal) { + setPointerAndInt(PtrVal, IntVal); + } + + explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); } + + PointerTy getPointer() const { return Info::getPointer(Value); } + + IntType getInt() const { return (IntType)Info::getInt(Value); } + + void setPointer(PointerTy PtrVal) & { + Value = Info::updatePointer(Value, PtrVal); + } + + void setInt(IntType IntVal) & { + Value = Info::updateInt(Value, static_cast(IntVal)); + } + + void initWithPointer(PointerTy PtrVal) & { + Value = Info::updatePointer(0, PtrVal); + } + + void setPointerAndInt(PointerTy PtrVal, IntType IntVal) & { + Value = Info::updateInt(Info::updatePointer(0, PtrVal), + static_cast(IntVal)); + } + + PointerTy const *getAddrOfPointer() const { + return const_cast(this)->getAddrOfPointer(); + } + + PointerTy *getAddrOfPointer() { + assert(Value == reinterpret_cast(getPointer()) && + "Can only return the address if IntBits is cleared and " + "PtrTraits doesn't change the pointer"); + return Value.getPointerAddress(); + } + + void *getOpaqueValue() const { + return reinterpret_cast(Value.asInt()); + } + + void setFromOpaqueValue(void *Val) & { + Value = reinterpret_cast(Val); + } + + static PointerIntPair getFromOpaqueValue(void *V) { + PointerIntPair P; + P.setFromOpaqueValue(V); + return P; + } + + // Allow PointerIntPairs to be created from const void * if and only if the + // pointer type could be created from a const void *. + static PointerIntPair getFromOpaqueValue(const void *V) { + (void)PtrTraits::getFromVoidPointer(V); + return getFromOpaqueValue(const_cast(V)); + } + + bool operator==(const PointerIntPair &RHS) const { + return Value == RHS.Value; + } + + bool operator!=(const PointerIntPair &RHS) const { + return Value != RHS.Value; + } + + bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; } + bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; } + + bool operator<=(const PointerIntPair &RHS) const { + return Value <= RHS.Value; + } + + bool operator>=(const PointerIntPair &RHS) const { + return Value >= RHS.Value; + } +}; + +template +struct PointerIntPairInfo { + static_assert(PtrTraits::NumLowBitsAvailable < + std::numeric_limits::digits, + "cannot use a pointer type that has all bits free"); + static_assert(IntBits <= PtrTraits::NumLowBitsAvailable, + "PointerIntPair with integer size too large for pointer"); + enum MaskAndShiftConstants : uintptr_t { + /// PointerBitMask - The bits that come from the pointer. + PointerBitMask = (~(uintptr_t)0) << PtrTraits::NumLowBitsAvailable, + + /// IntShift - The number of low bits that we reserve for other uses, and + /// keep zero. + IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits, + + /// IntMask - This is the unshifted mask for valid bits of the int type. + IntMask = ((uintptr_t)1 << IntBits) - 1, + + // ShiftedIntMask - This is the bits for the integer shifted in place. + ShiftedIntMask = (uintptr_t)(IntMask << IntShift) + }; + + static PointerT getPointer(intptr_t Value) { + return PtrTraits::getFromVoidPointer( + reinterpret_cast(Value & PointerBitMask)); + } + + static intptr_t getInt(intptr_t Value) { + return (Value >> IntShift) & IntMask; + } + + static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) { + intptr_t PtrWord = + reinterpret_cast(PtrTraits::getAsVoidPointer(Ptr)); + assert((PtrWord & ~PointerBitMask) == 0 && + "Pointer is not sufficiently aligned"); + // Preserve all low bits, just update the pointer. + return PtrWord | (OrigValue & ~PointerBitMask); + } + + static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) { + assert((Int & ~IntMask) == 0 && "Integer too large for field"); + + // Preserve all bits other than the ones we are updating. + return (OrigValue & ~ShiftedIntMask) | Int << IntShift; + } +}; + +// Provide specialization of DenseMapInfo for PointerIntPair. +template +struct DenseMapInfo, void> { + using Ty = PointerIntPair; + + static unsigned getHashValue(Ty V) { + uintptr_t IV = reinterpret_cast(V.getOpaqueValue()); + return unsigned(IV) ^ unsigned(IV >> 9); + } + + static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; } +}; + +// Teach SmallPtrSet that PointerIntPair is "basically a pointer". +template +struct PointerLikeTypeTraits< + PointerIntPair> { + static inline void * + getAsVoidPointer(const PointerIntPair &P) { + return P.getOpaqueValue(); + } + + static inline PointerIntPair + getFromVoidPointer(void *P) { + return PointerIntPair::getFromOpaqueValue(P); + } + + static inline PointerIntPair + getFromVoidPointer(const void *P) { + return PointerIntPair::getFromOpaqueValue(P); + } + + static constexpr int NumLowBitsAvailable = + PtrTraits::NumLowBitsAvailable - IntBits; +}; + +// Allow structured bindings on PointerIntPair. +template +decltype(auto) +get(const PointerIntPair &Pair) { + static_assert(I < 2); + if constexpr (I == 0) + return Pair.getPointer(); + else + return Pair.getInt(); +} + +} // end namespace libbase + +namespace std { +template +struct tuple_size< + libbase::PointerIntPair> + : std::integral_constant {}; + +template +struct tuple_element< + I, libbase::PointerIntPair> + : std::conditional {}; +} // namespace std + +#endif // LIBBASE_ADT_POINTERINTPAIR_H diff --git a/libbase/include/core/adt/PointerLikeTypeTraits.h b/libbase/include/core/adt/PointerLikeTypeTraits.h new file mode 100644 index 0000000..9c1a36f --- /dev/null +++ b/libbase/include/core/adt/PointerLikeTypeTraits.h @@ -0,0 +1,165 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + . +*/ + +//===- core/adt/PointerLikeTypeTraits.h - Pointer Traits ----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the PointerLikeTypeTraits class. This allows data +// structures to reason about pointers and other things that are pointer sized. +// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_ADT_POINTERLIKETYPETRAITS_H +#define LIBBASE_ADT_POINTERLIKETYPETRAITS_H + +#include "core/compiler/DataTypes.h" +#include "core/math/MathExtras.h" +#include + +namespace libbase { + +/// A traits type that is used to handle pointer types and things that are just +/// wrappers for pointers as a uniform entity. +template struct PointerLikeTypeTraits; + +namespace detail { +// Provide a trait to check if T is pointer-like. +template struct HasPointerLikeTypeTraits { + static const bool value = false; +}; + +// sizeof(T) is valid only for a complete T. +template +struct HasPointerLikeTypeTraits< + T, decltype((sizeof(PointerLikeTypeTraits) + sizeof(T)), void())> { + static const bool value = true; +}; + +template struct IsPointerLike { + static const bool value = HasPointerLikeTypeTraits::value; +}; + +template struct IsPointerLike { + static const bool value = true; +}; +} // namespace detail + +// Provide PointerLikeTypeTraits for non-cvr pointers. +template struct PointerLikeTypeTraits { + static inline void *getAsVoidPointer(T *P) { return P; } + static inline T *getFromVoidPointer(void *P) { return static_cast(P); } + + static constexpr int NumLowBitsAvailable = ConstantLog2(); +}; + +template <> struct PointerLikeTypeTraits { + static inline void *getAsVoidPointer(void *P) { return P; } + static inline void *getFromVoidPointer(void *P) { return P; } + + /// Note, we assume here that void* is related to raw malloc'ed memory and + /// that malloc returns objects at least 4-byte aligned. However, this may be + /// wrong, or pointers may be from something other than malloc. In this case, + /// you should specify a real typed pointer or avoid this template. + /// + /// All clients should use assertions to do a run-time check to ensure that + /// this is actually true. + static constexpr int NumLowBitsAvailable = 2; +}; + +// Provide PointerLikeTypeTraits for const things. +template struct PointerLikeTypeTraits { + using NonConst = PointerLikeTypeTraits; + + static inline const void *getAsVoidPointer(const T P) { + return NonConst::getAsVoidPointer(P); + } + static inline const T getFromVoidPointer(const void *P) { + return NonConst::getFromVoidPointer(const_cast(P)); + } + static constexpr int NumLowBitsAvailable = NonConst::NumLowBitsAvailable; +}; + +// Provide PointerLikeTypeTraits for const pointers. +template struct PointerLikeTypeTraits { + using NonConst = PointerLikeTypeTraits; + + static inline const void *getAsVoidPointer(const T *P) { + return NonConst::getAsVoidPointer(const_cast(P)); + } + static inline const T *getFromVoidPointer(const void *P) { + return NonConst::getFromVoidPointer(const_cast(P)); + } + static constexpr int NumLowBitsAvailable = NonConst::NumLowBitsAvailable; +}; + +// Provide PointerLikeTypeTraits for uintptr_t. +template <> struct PointerLikeTypeTraits { + static inline void *getAsVoidPointer(uintptr_t P) { + return reinterpret_cast(P); + } + static inline uintptr_t getFromVoidPointer(void *P) { + return reinterpret_cast(P); + } + // No bits are available! + static constexpr int NumLowBitsAvailable = 0; +}; + +/// Provide suitable custom traits struct for function pointers. +/// +/// Function pointers can't be directly given these traits as functions can't +/// have their alignment computed with `alignof` and we need different casting. +/// +/// To rely on higher alignment for a specialized use, you can provide a +/// customized form of this template explicitly with higher alignment, and +/// potentially use alignment attributes on functions to satisfy that. +template +struct FunctionPointerLikeTypeTraits { + static constexpr int NumLowBitsAvailable = ConstantLog2(); + static inline void *getAsVoidPointer(FunctionPointerT P) { + assert((reinterpret_cast(P) & + ~((uintptr_t)-1 << NumLowBitsAvailable)) == 0 && + "Alignment not satisfied for an actual function pointer!"); + return reinterpret_cast(P); + } + static inline FunctionPointerT getFromVoidPointer(void *P) { + return reinterpret_cast(P); + } +}; + +/// Provide a default specialization for function pointers that assumes 4-byte +/// alignment. +/// +/// We assume here that functions used with this are always at least 4-byte +/// aligned. This means that, for example, thumb functions won't work or systems +/// with weird unaligned function pointers won't work. But all practical systems +/// we support satisfy this requirement. +template +struct PointerLikeTypeTraits + : FunctionPointerLikeTypeTraits<4, ReturnT (*)(ParamTs...)> {}; + +} // end namespace libbase + +#endif -- cgit v1.2.3