]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This file defines the PointerIntPair class. | |
11 | // | |
12 | //===----------------------------------------------------------------------===// | |
13 | ||
14 | #ifndef LLVM_ADT_POINTERINTPAIR_H | |
15 | #define LLVM_ADT_POINTERINTPAIR_H | |
16 | ||
1a4d82fc | 17 | #include "llvm/Support/Compiler.h" |
223e47cc LB |
18 | #include "llvm/Support/PointerLikeTypeTraits.h" |
19 | #include <cassert> | |
1a4d82fc | 20 | #include <limits> |
223e47cc LB |
21 | |
22 | namespace llvm { | |
23 | ||
24 | template<typename T> | |
25 | struct DenseMapInfo; | |
26 | ||
27 | /// PointerIntPair - This class implements a pair of a pointer and small | |
28 | /// integer. It is designed to represent this in the space required by one | |
29 | /// pointer by bitmangling the integer into the low part of the pointer. This | |
30 | /// can only be done for small integers: typically up to 3 bits, but it depends | |
31 | /// on the number of bits available according to PointerLikeTypeTraits for the | |
32 | /// type. | |
33 | /// | |
1a4d82fc | 34 | /// Note that PointerIntPair always puts the IntVal part in the highest bits |
223e47cc LB |
35 | /// possible. For example, PointerIntPair<void*, 1, bool> will put the bit for |
36 | /// the bool into bit #2, not bit #0, which allows the low two bits to be used | |
37 | /// for something else. For example, this allows: | |
38 | /// PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool> | |
39 | /// ... and the two bools will land in different bits. | |
40 | /// | |
41 | template <typename PointerTy, unsigned IntBits, typename IntType=unsigned, | |
42 | typename PtrTraits = PointerLikeTypeTraits<PointerTy> > | |
43 | class PointerIntPair { | |
44 | intptr_t Value; | |
1a4d82fc JJ |
45 | static_assert(PtrTraits::NumLowBitsAvailable < |
46 | std::numeric_limits<uintptr_t>::digits, | |
47 | "cannot use a pointer type that has all bits free"); | |
48 | static_assert(IntBits <= PtrTraits::NumLowBitsAvailable, | |
49 | "PointerIntPair with integer size too large for pointer"); | |
50 | enum : uintptr_t { | |
223e47cc LB |
51 | /// PointerBitMask - The bits that come from the pointer. |
52 | PointerBitMask = | |
53 | ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable)-1), | |
54 | ||
55 | /// IntShift - The number of low bits that we reserve for other uses, and | |
56 | /// keep zero. | |
57 | IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable-IntBits, | |
58 | ||
59 | /// IntMask - This is the unshifted mask for valid bits of the int type. | |
60 | IntMask = (uintptr_t)(((intptr_t)1 << IntBits)-1), | |
61 | ||
62 | // ShiftedIntMask - This is the bits for the integer shifted in place. | |
63 | ShiftedIntMask = (uintptr_t)(IntMask << IntShift) | |
64 | }; | |
65 | public: | |
66 | PointerIntPair() : Value(0) {} | |
1a4d82fc JJ |
67 | PointerIntPair(PointerTy PtrVal, IntType IntVal) { |
68 | setPointerAndInt(PtrVal, IntVal); | |
970d7e83 | 69 | } |
1a4d82fc JJ |
70 | explicit PointerIntPair(PointerTy PtrVal) { |
71 | initWithPointer(PtrVal); | |
223e47cc LB |
72 | } |
73 | ||
74 | PointerTy getPointer() const { | |
75 | return PtrTraits::getFromVoidPointer( | |
76 | reinterpret_cast<void*>(Value & PointerBitMask)); | |
77 | } | |
78 | ||
79 | IntType getInt() const { | |
80 | return (IntType)((Value >> IntShift) & IntMask); | |
81 | } | |
82 | ||
1a4d82fc JJ |
83 | void setPointer(PointerTy PtrVal) { |
84 | intptr_t PtrWord | |
85 | = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal)); | |
86 | assert((PtrWord & ~PointerBitMask) == 0 && | |
223e47cc LB |
87 | "Pointer is not sufficiently aligned"); |
88 | // Preserve all low bits, just update the pointer. | |
1a4d82fc | 89 | Value = PtrWord | (Value & ~PointerBitMask); |
223e47cc LB |
90 | } |
91 | ||
1a4d82fc JJ |
92 | void setInt(IntType IntVal) { |
93 | intptr_t IntWord = static_cast<intptr_t>(IntVal); | |
94 | assert((IntWord & ~IntMask) == 0 && "Integer too large for field"); | |
223e47cc LB |
95 | |
96 | // Preserve all bits other than the ones we are updating. | |
97 | Value &= ~ShiftedIntMask; // Remove integer field. | |
1a4d82fc | 98 | Value |= IntWord << IntShift; // Set new integer. |
223e47cc LB |
99 | } |
100 | ||
1a4d82fc JJ |
101 | void initWithPointer(PointerTy PtrVal) { |
102 | intptr_t PtrWord | |
103 | = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal)); | |
104 | assert((PtrWord & ~PointerBitMask) == 0 && | |
970d7e83 | 105 | "Pointer is not sufficiently aligned"); |
1a4d82fc | 106 | Value = PtrWord; |
970d7e83 LB |
107 | } |
108 | ||
1a4d82fc JJ |
109 | void setPointerAndInt(PointerTy PtrVal, IntType IntVal) { |
110 | intptr_t PtrWord | |
111 | = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal)); | |
112 | assert((PtrWord & ~PointerBitMask) == 0 && | |
970d7e83 | 113 | "Pointer is not sufficiently aligned"); |
1a4d82fc JJ |
114 | intptr_t IntWord = static_cast<intptr_t>(IntVal); |
115 | assert((IntWord & ~IntMask) == 0 && "Integer too large for field"); | |
970d7e83 | 116 | |
1a4d82fc | 117 | Value = PtrWord | (IntWord << IntShift); |
970d7e83 LB |
118 | } |
119 | ||
223e47cc LB |
120 | PointerTy const *getAddrOfPointer() const { |
121 | return const_cast<PointerIntPair *>(this)->getAddrOfPointer(); | |
122 | } | |
123 | ||
124 | PointerTy *getAddrOfPointer() { | |
125 | assert(Value == reinterpret_cast<intptr_t>(getPointer()) && | |
126 | "Can only return the address if IntBits is cleared and " | |
127 | "PtrTraits doesn't change the pointer"); | |
128 | return reinterpret_cast<PointerTy *>(&Value); | |
129 | } | |
130 | ||
131 | void *getOpaqueValue() const { return reinterpret_cast<void*>(Value); } | |
132 | void setFromOpaqueValue(void *Val) { Value = reinterpret_cast<intptr_t>(Val);} | |
133 | ||
134 | static PointerIntPair getFromOpaqueValue(void *V) { | |
135 | PointerIntPair P; P.setFromOpaqueValue(V); return P; | |
136 | } | |
137 | ||
138 | // Allow PointerIntPairs to be created from const void * if and only if the | |
139 | // pointer type could be created from a const void *. | |
140 | static PointerIntPair getFromOpaqueValue(const void *V) { | |
141 | (void)PtrTraits::getFromVoidPointer(V); | |
142 | return getFromOpaqueValue(const_cast<void *>(V)); | |
143 | } | |
144 | ||
145 | bool operator==(const PointerIntPair &RHS) const {return Value == RHS.Value;} | |
146 | bool operator!=(const PointerIntPair &RHS) const {return Value != RHS.Value;} | |
147 | bool operator<(const PointerIntPair &RHS) const {return Value < RHS.Value;} | |
148 | bool operator>(const PointerIntPair &RHS) const {return Value > RHS.Value;} | |
149 | bool operator<=(const PointerIntPair &RHS) const {return Value <= RHS.Value;} | |
150 | bool operator>=(const PointerIntPair &RHS) const {return Value >= RHS.Value;} | |
151 | }; | |
152 | ||
153 | template <typename T> struct isPodLike; | |
154 | template<typename PointerTy, unsigned IntBits, typename IntType> | |
155 | struct isPodLike<PointerIntPair<PointerTy, IntBits, IntType> > { | |
156 | static const bool value = true; | |
157 | }; | |
158 | ||
159 | // Provide specialization of DenseMapInfo for PointerIntPair. | |
160 | template<typename PointerTy, unsigned IntBits, typename IntType> | |
161 | struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType> > { | |
162 | typedef PointerIntPair<PointerTy, IntBits, IntType> Ty; | |
163 | static Ty getEmptyKey() { | |
164 | uintptr_t Val = static_cast<uintptr_t>(-1); | |
1a4d82fc JJ |
165 | Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable; |
166 | return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val)); | |
223e47cc LB |
167 | } |
168 | static Ty getTombstoneKey() { | |
169 | uintptr_t Val = static_cast<uintptr_t>(-2); | |
170 | Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable; | |
1a4d82fc | 171 | return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val)); |
223e47cc LB |
172 | } |
173 | static unsigned getHashValue(Ty V) { | |
174 | uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue()); | |
175 | return unsigned(IV) ^ unsigned(IV >> 9); | |
176 | } | |
177 | static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; } | |
178 | }; | |
179 | ||
180 | // Teach SmallPtrSet that PointerIntPair is "basically a pointer". | |
181 | template<typename PointerTy, unsigned IntBits, typename IntType, | |
182 | typename PtrTraits> | |
183 | class PointerLikeTypeTraits<PointerIntPair<PointerTy, IntBits, IntType, | |
184 | PtrTraits> > { | |
185 | public: | |
186 | static inline void * | |
187 | getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) { | |
188 | return P.getOpaqueValue(); | |
189 | } | |
190 | static inline PointerIntPair<PointerTy, IntBits, IntType> | |
191 | getFromVoidPointer(void *P) { | |
192 | return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); | |
193 | } | |
194 | static inline PointerIntPair<PointerTy, IntBits, IntType> | |
195 | getFromVoidPointer(const void *P) { | |
196 | return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); | |
197 | } | |
198 | enum { | |
199 | NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits | |
200 | }; | |
201 | }; | |
202 | ||
203 | } // end namespace llvm | |
204 | #endif |