1 //===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file defines the PointerIntPair class.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_ADT_POINTERINTPAIR_H
14 #define LLVM_ADT_POINTERINTPAIR_H
16 #include "llvm/Support/Compiler.h"
17 #include "llvm/Support/PointerLikeTypeTraits.h"
18 #include "llvm/Support/type_traits.h"
25 template <typename T
> struct DenseMapInfo
;
26 template <typename PointerT
, unsigned IntBits
, typename PtrTraits
>
27 struct PointerIntPairInfo
;
29 /// PointerIntPair - This class implements a pair of a pointer and small
30 /// integer. It is designed to represent this in the space required by one
31 /// pointer by bitmangling the integer into the low part of the pointer. This
32 /// can only be done for small integers: typically up to 3 bits, but it depends
33 /// on the number of bits available according to PointerLikeTypeTraits for the
36 /// Note that PointerIntPair always puts the IntVal part in the highest bits
37 /// possible. For example, PointerIntPair<void*, 1, bool> will put the bit for
38 /// the bool into bit #2, not bit #0, which allows the low two bits to be used
39 /// for something else. For example, this allows:
40 /// PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool>
41 /// ... and the two bools will land in different bits.
42 template <typename PointerTy
, unsigned IntBits
, typename IntType
= unsigned,
43 typename PtrTraits
= PointerLikeTypeTraits
<PointerTy
>,
44 typename Info
= PointerIntPairInfo
<PointerTy
, IntBits
, PtrTraits
>>
45 class PointerIntPair
{
46 // Used by MSVC visualizer and generally helpful for debugging/visualizing.
51 constexpr PointerIntPair() = default;
53 PointerIntPair(PointerTy PtrVal
, IntType IntVal
) {
54 setPointerAndInt(PtrVal
, IntVal
);
57 explicit PointerIntPair(PointerTy PtrVal
) { initWithPointer(PtrVal
); }
59 PointerTy
getPointer() const { return Info::getPointer(Value
); }
61 IntType
getInt() const { return (IntType
)Info::getInt(Value
); }
63 void setPointer(PointerTy PtrVal
) LLVM_LVALUE_FUNCTION
{
64 Value
= Info::updatePointer(Value
, PtrVal
);
67 void setInt(IntType IntVal
) LLVM_LVALUE_FUNCTION
{
68 Value
= Info::updateInt(Value
, static_cast<intptr_t>(IntVal
));
71 void initWithPointer(PointerTy PtrVal
) LLVM_LVALUE_FUNCTION
{
72 Value
= Info::updatePointer(0, PtrVal
);
75 void setPointerAndInt(PointerTy PtrVal
, IntType IntVal
) LLVM_LVALUE_FUNCTION
{
76 Value
= Info::updateInt(Info::updatePointer(0, PtrVal
),
77 static_cast<intptr_t>(IntVal
));
80 PointerTy
const *getAddrOfPointer() const {
81 return const_cast<PointerIntPair
*>(this)->getAddrOfPointer();
84 PointerTy
*getAddrOfPointer() {
85 assert(Value
== reinterpret_cast<intptr_t>(getPointer()) &&
86 "Can only return the address if IntBits is cleared and "
87 "PtrTraits doesn't change the pointer");
88 return reinterpret_cast<PointerTy
*>(&Value
);
91 void *getOpaqueValue() const { return reinterpret_cast<void *>(Value
); }
93 void setFromOpaqueValue(void *Val
) LLVM_LVALUE_FUNCTION
{
94 Value
= reinterpret_cast<intptr_t>(Val
);
97 static PointerIntPair
getFromOpaqueValue(void *V
) {
99 P
.setFromOpaqueValue(V
);
103 // Allow PointerIntPairs to be created from const void * if and only if the
104 // pointer type could be created from a const void *.
105 static PointerIntPair
getFromOpaqueValue(const void *V
) {
106 (void)PtrTraits::getFromVoidPointer(V
);
107 return getFromOpaqueValue(const_cast<void *>(V
));
110 bool operator==(const PointerIntPair
&RHS
) const {
111 return Value
== RHS
.Value
;
114 bool operator!=(const PointerIntPair
&RHS
) const {
115 return Value
!= RHS
.Value
;
118 bool operator<(const PointerIntPair
&RHS
) const { return Value
< RHS
.Value
; }
119 bool operator>(const PointerIntPair
&RHS
) const { return Value
> RHS
.Value
; }
121 bool operator<=(const PointerIntPair
&RHS
) const {
122 return Value
<= RHS
.Value
;
125 bool operator>=(const PointerIntPair
&RHS
) const {
126 return Value
>= RHS
.Value
;
130 // Specialize is_trivially_copyable to avoid limitation of llvm::is_trivially_copyable
131 // when compiled with gcc 4.9.
132 template <typename PointerTy
, unsigned IntBits
, typename IntType
,
135 struct is_trivially_copyable
<PointerIntPair
<PointerTy
, IntBits
, IntType
, PtrTraits
, Info
>> : std::true_type
{
136 #ifdef HAVE_STD_IS_TRIVIALLY_COPYABLE
137 static_assert(std::is_trivially_copyable
<PointerIntPair
<PointerTy
, IntBits
, IntType
, PtrTraits
, Info
>>::value
,
138 "inconsistent behavior between llvm:: and std:: implementation of is_trivially_copyable");
143 template <typename PointerT
, unsigned IntBits
, typename PtrTraits
>
144 struct PointerIntPairInfo
{
145 static_assert(PtrTraits::NumLowBitsAvailable
<
146 std::numeric_limits
<uintptr_t>::digits
,
147 "cannot use a pointer type that has all bits free");
148 static_assert(IntBits
<= PtrTraits::NumLowBitsAvailable
,
149 "PointerIntPair with integer size too large for pointer");
151 /// PointerBitMask - The bits that come from the pointer.
153 ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable
) - 1),
155 /// IntShift - The number of low bits that we reserve for other uses, and
157 IntShift
= (uintptr_t)PtrTraits::NumLowBitsAvailable
- IntBits
,
159 /// IntMask - This is the unshifted mask for valid bits of the int type.
160 IntMask
= (uintptr_t)(((intptr_t)1 << IntBits
) - 1),
162 // ShiftedIntMask - This is the bits for the integer shifted in place.
163 ShiftedIntMask
= (uintptr_t)(IntMask
<< IntShift
)
166 static PointerT
getPointer(intptr_t Value
) {
167 return PtrTraits::getFromVoidPointer(
168 reinterpret_cast<void *>(Value
& PointerBitMask
));
171 static intptr_t getInt(intptr_t Value
) {
172 return (Value
>> IntShift
) & IntMask
;
175 static intptr_t updatePointer(intptr_t OrigValue
, PointerT Ptr
) {
177 reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr
));
178 assert((PtrWord
& ~PointerBitMask
) == 0 &&
179 "Pointer is not sufficiently aligned");
180 // Preserve all low bits, just update the pointer.
181 return PtrWord
| (OrigValue
& ~PointerBitMask
);
184 static intptr_t updateInt(intptr_t OrigValue
, intptr_t Int
) {
185 intptr_t IntWord
= static_cast<intptr_t>(Int
);
186 assert((IntWord
& ~IntMask
) == 0 && "Integer too large for field");
188 // Preserve all bits other than the ones we are updating.
189 return (OrigValue
& ~ShiftedIntMask
) | IntWord
<< IntShift
;
193 // Provide specialization of DenseMapInfo for PointerIntPair.
194 template <typename PointerTy
, unsigned IntBits
, typename IntType
>
195 struct DenseMapInfo
<PointerIntPair
<PointerTy
, IntBits
, IntType
>> {
196 using Ty
= PointerIntPair
<PointerTy
, IntBits
, IntType
>;
198 static Ty
getEmptyKey() {
199 uintptr_t Val
= static_cast<uintptr_t>(-1);
200 Val
<<= PointerLikeTypeTraits
<Ty
>::NumLowBitsAvailable
;
201 return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val
));
204 static Ty
getTombstoneKey() {
205 uintptr_t Val
= static_cast<uintptr_t>(-2);
206 Val
<<= PointerLikeTypeTraits
<PointerTy
>::NumLowBitsAvailable
;
207 return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val
));
210 static unsigned getHashValue(Ty V
) {
211 uintptr_t IV
= reinterpret_cast<uintptr_t>(V
.getOpaqueValue());
212 return unsigned(IV
) ^ unsigned(IV
>> 9);
215 static bool isEqual(const Ty
&LHS
, const Ty
&RHS
) { return LHS
== RHS
; }
218 // Teach SmallPtrSet that PointerIntPair is "basically a pointer".
219 template <typename PointerTy
, unsigned IntBits
, typename IntType
,
221 struct PointerLikeTypeTraits
<
222 PointerIntPair
<PointerTy
, IntBits
, IntType
, PtrTraits
>> {
224 getAsVoidPointer(const PointerIntPair
<PointerTy
, IntBits
, IntType
> &P
) {
225 return P
.getOpaqueValue();
228 static inline PointerIntPair
<PointerTy
, IntBits
, IntType
>
229 getFromVoidPointer(void *P
) {
230 return PointerIntPair
<PointerTy
, IntBits
, IntType
>::getFromOpaqueValue(P
);
233 static inline PointerIntPair
<PointerTy
, IntBits
, IntType
>
234 getFromVoidPointer(const void *P
) {
235 return PointerIntPair
<PointerTy
, IntBits
, IntType
>::getFromOpaqueValue(P
);
238 enum { NumLowBitsAvailable
= PtrTraits::NumLowBitsAvailable
- IntBits
};
241 } // end namespace llvm
243 #endif // LLVM_ADT_POINTERINTPAIR_H