Line data Source code
1 : //===- llvm/ADT/PointerUnion.h - Discriminated Union of 2 Ptrs --*- 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 PointerUnion class, which is a discriminated union of
11 : // pointer types.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_ADT_POINTERUNION_H
16 : #define LLVM_ADT_POINTERUNION_H
17 :
18 : #include "llvm/ADT/DenseMapInfo.h"
19 : #include "llvm/ADT/PointerIntPair.h"
20 : #include "llvm/Support/Compiler.h"
21 :
22 : namespace llvm {
23 :
24 : template <typename T>
25 : struct PointerUnionTypeSelectorReturn {
26 : typedef T Return;
27 : };
28 :
29 : /// \brief Get a type based on whether two types are the same or not. For:
30 : /// @code
31 : /// typedef typename PointerUnionTypeSelector<T1, T2, EQ, NE>::Return Ret;
32 : /// @endcode
33 : /// Ret will be EQ type if T1 is same as T2 or NE type otherwise.
34 : template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
35 : struct PointerUnionTypeSelector {
36 : typedef typename PointerUnionTypeSelectorReturn<RET_NE>::Return Return;
37 : };
38 :
39 : template <typename T, typename RET_EQ, typename RET_NE>
40 : struct PointerUnionTypeSelector<T, T, RET_EQ, RET_NE> {
41 : typedef typename PointerUnionTypeSelectorReturn<RET_EQ>::Return Return;
42 : };
43 :
44 : template <typename T1, typename T2, typename RET_EQ, typename RET_NE>
45 : struct PointerUnionTypeSelectorReturn<
46 : PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE> > {
47 : typedef typename PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>::Return
48 : Return;
49 : };
50 :
51 : /// Provide PointerLikeTypeTraits for void* that is used by PointerUnion
52 : /// for the two template arguments.
53 : template <typename PT1, typename PT2>
54 : class PointerUnionUIntTraits {
55 : public:
56 7 : static inline void *getAsVoidPointer(void *P) { return P; }
57 308 : static inline void *getFromVoidPointer(void *P) { return P; }
58 : enum {
59 : PT1BitsAv = (int)(PointerLikeTypeTraits<PT1>::NumLowBitsAvailable),
60 : PT2BitsAv = (int)(PointerLikeTypeTraits<PT2>::NumLowBitsAvailable),
61 : NumLowBitsAvailable = PT1BitsAv < PT2BitsAv ? PT1BitsAv : PT2BitsAv
62 : };
63 : };
64 :
65 : /// PointerUnion - This implements a discriminated union of two pointer types,
66 : /// and keeps the discriminator bit-mangled into the low bits of the pointer.
67 : /// This allows the implementation to be extremely efficient in space, but
68 : /// permits a very natural and type-safe API.
69 : ///
70 : /// Common use patterns would be something like this:
71 : /// PointerUnion<int*, float*> P;
72 : /// P = (int*)0;
73 : /// printf("%d %d", P.is<int*>(), P.is<float*>()); // prints "1 0"
74 : /// X = P.get<int*>(); // ok.
75 : /// Y = P.get<float*>(); // runtime assertion failure.
76 : /// Z = P.get<double*>(); // compile time failure.
77 : /// P = (float*)0;
78 : /// Y = P.get<float*>(); // ok.
79 : /// X = P.get<int*>(); // runtime assertion failure.
80 : template <typename PT1, typename PT2>
81 : class PointerUnion {
82 : public:
83 : typedef PointerIntPair<void*, 1, bool,
84 : PointerUnionUIntTraits<PT1,PT2> > ValTy;
85 : private:
86 : ValTy Val;
87 :
88 : struct IsPT1 {
89 : static const int Num = 0;
90 : };
91 : struct IsPT2 {
92 : static const int Num = 1;
93 : };
94 : template <typename T>
95 : struct UNION_DOESNT_CONTAIN_TYPE { };
96 :
97 : public:
98 328 : PointerUnion() {}
99 :
100 14 : PointerUnion(PT1 V) : Val(
101 7 : const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) {
102 7 : }
103 0 : PointerUnion(PT2 V) : Val(
104 0 : const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)), 1) {
105 0 : }
106 :
107 : /// isNull - Return true if the pointer held in the union is null,
108 : /// regardless of which type it is.
109 : bool isNull() const {
110 : // Convert from the void* to one of the pointer types, to make sure that
111 : // we recursively strip off low bits if we have a nested PointerUnion.
112 186 : return !PointerLikeTypeTraits<PT1>::getFromVoidPointer(Val.getPointer());
113 : }
114 13 : explicit operator bool() const { return !isNull(); }
115 :
116 : /// is<T>() return true if the Union currently holds the type matching T.
117 : template<typename T>
118 : int is() const {
119 : typedef typename
120 : ::llvm::PointerUnionTypeSelector<PT1, T, IsPT1,
121 : ::llvm::PointerUnionTypeSelector<PT2, T, IsPT2,
122 : UNION_DOESNT_CONTAIN_TYPE<T> > >::Return Ty;
123 484 : int TyNo = Ty::Num;
124 484 : return static_cast<int>(Val.getInt()) == TyNo;
125 : }
126 :
127 : /// get<T>() - Return the value of the specified pointer type. If the
128 : /// specified pointer type is incorrect, assert.
129 : template<typename T>
130 : T get() const {
131 244 : assert(is<T>() && "Invalid accessor called");
132 122 : return PointerLikeTypeTraits<T>::getFromVoidPointer(Val.getPointer());
133 : }
134 :
135 : /// dyn_cast<T>() - If the current value is of the specified pointer type,
136 : /// return it, otherwise return null.
137 : template<typename T>
138 : T dyn_cast() const {
139 117 : if (is<T>()) return get<T>();
140 39 : return T();
141 78 : }
142 :
143 : /// \brief If the union is set to the first pointer type get an address
144 : /// pointing to it.
145 : PT1 const *getAddrOfPtr1() const {
146 : return const_cast<PointerUnion *>(this)->getAddrOfPtr1();
147 : }
148 :
149 : /// \brief If the union is set to the first pointer type get an address
150 : /// pointing to it.
151 : PT1 *getAddrOfPtr1() {
152 0 : assert(is<PT1>() && "Val is not the first pointer");
153 0 : assert(get<PT1>() == Val.getPointer() &&
154 : "Can't get the address because PointerLikeTypeTraits changes the ptr");
155 0 : return (PT1 *)Val.getAddrOfPointer();
156 : }
157 :
158 : /// \brief Assignment from nullptr which just clears the union.
159 : const PointerUnion &operator=(std::nullptr_t) {
160 : Val.initWithPointer(nullptr);
161 : return *this;
162 : }
163 :
164 : /// Assignment operators - Allow assigning into this union from either
165 : /// pointer type, setting the discriminator to remember what it came from.
166 : const PointerUnion &operator=(const PT1 &RHS) {
167 : Val.initWithPointer(
168 : const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(RHS)));
169 : return *this;
170 : }
171 : const PointerUnion &operator=(const PT2 &RHS) {
172 0 : Val.setPointerAndInt(
173 0 : const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(RHS)),
174 : 1);
175 0 : return *this;
176 : }
177 :
178 7 : void *getOpaqueValue() const { return Val.getOpaqueValue(); }
179 : static inline PointerUnion getFromOpaqueValue(void *VP) {
180 328 : PointerUnion V;
181 328 : V.Val = ValTy::getFromOpaqueValue(VP);
182 328 : return V;
183 : }
184 : };
185 :
186 : template<typename PT1, typename PT2>
187 : static bool operator==(PointerUnion<PT1, PT2> lhs,
188 : PointerUnion<PT1, PT2> rhs) {
189 : return lhs.getOpaqueValue() == rhs.getOpaqueValue();
190 : }
191 :
192 : template<typename PT1, typename PT2>
193 : static bool operator!=(PointerUnion<PT1, PT2> lhs,
194 : PointerUnion<PT1, PT2> rhs) {
195 : return lhs.getOpaqueValue() != rhs.getOpaqueValue();
196 : }
197 :
198 : template<typename PT1, typename PT2>
199 : static bool operator<(PointerUnion<PT1, PT2> lhs,
200 : PointerUnion<PT1, PT2> rhs) {
201 : return lhs.getOpaqueValue() < rhs.getOpaqueValue();
202 : }
203 :
204 : // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
205 : // # low bits available = min(PT1bits,PT2bits)-1.
206 : template<typename PT1, typename PT2>
207 : class PointerLikeTypeTraits<PointerUnion<PT1, PT2> > {
208 : public:
209 : static inline void *
210 : getAsVoidPointer(const PointerUnion<PT1, PT2> &P) {
211 7 : return P.getOpaqueValue();
212 : }
213 : static inline PointerUnion<PT1, PT2>
214 : getFromVoidPointer(void *P) {
215 328 : return PointerUnion<PT1, PT2>::getFromOpaqueValue(P);
216 : }
217 :
218 : // The number of bits available are the min of the two pointer types.
219 : enum {
220 : NumLowBitsAvailable =
221 : PointerLikeTypeTraits<typename PointerUnion<PT1,PT2>::ValTy>
222 : ::NumLowBitsAvailable
223 : };
224 : };
225 :
226 :
227 : /// PointerUnion3 - This is a pointer union of three pointer types. See
228 : /// documentation for PointerUnion for usage.
229 : template <typename PT1, typename PT2, typename PT3>
230 : class PointerUnion3 {
231 : public:
232 : typedef PointerUnion<PT1, PT2> InnerUnion;
233 : typedef PointerUnion<InnerUnion, PT3> ValTy;
234 : private:
235 : ValTy Val;
236 :
237 : struct IsInnerUnion {
238 : ValTy Val;
239 5 : IsInnerUnion(ValTy val) : Val(val) { }
240 : template<typename T>
241 : int is() const {
242 8 : return Val.template is<InnerUnion>() &&
243 4 : Val.template get<InnerUnion>().template is<T>();
244 : }
245 : template<typename T>
246 : T get() const {
247 1 : return Val.template get<InnerUnion>().template get<T>();
248 : }
249 : };
250 :
251 : struct IsPT3 {
252 : ValTy Val;
253 0 : IsPT3(ValTy val) : Val(val) { }
254 : template<typename T>
255 : int is() const {
256 0 : return Val.template is<T>();
257 : }
258 : template<typename T>
259 : T get() const {
260 0 : return Val.template get<T>();
261 : }
262 : };
263 :
264 : public:
265 : PointerUnion3() {}
266 :
267 : PointerUnion3(PT1 V) {
268 : Val = InnerUnion(V);
269 : }
270 : PointerUnion3(PT2 V) {
271 : Val = InnerUnion(V);
272 : }
273 : PointerUnion3(PT3 V) {
274 : Val = V;
275 : }
276 :
277 : /// isNull - Return true if the pointer held in the union is null,
278 : /// regardless of which type it is.
279 0 : bool isNull() const { return Val.isNull(); }
280 : explicit operator bool() const { return !isNull(); }
281 :
282 : /// is<T>() return true if the Union currently holds the type matching T.
283 : template<typename T>
284 : int is() const {
285 : // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
286 : typedef typename
287 : ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion,
288 : ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 >
289 : >::Return Ty;
290 4 : return Ty(Val).template is<T>();
291 : }
292 :
293 : /// get<T>() - Return the value of the specified pointer type. If the
294 : /// specified pointer type is incorrect, assert.
295 : template<typename T>
296 : T get() const {
297 2 : assert(is<T>() && "Invalid accessor called");
298 : // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
299 : typedef typename
300 : ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion,
301 : ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 >
302 : >::Return Ty;
303 1 : return Ty(Val).template get<T>();
304 : }
305 :
306 : /// dyn_cast<T>() - If the current value is of the specified pointer type,
307 : /// return it, otherwise return null.
308 : template<typename T>
309 : T dyn_cast() const {
310 2 : if (is<T>()) return get<T>();
311 2 : return T();
312 2 : }
313 :
314 : /// \brief Assignment from nullptr which just clears the union.
315 : const PointerUnion3 &operator=(std::nullptr_t) {
316 : Val = nullptr;
317 : return *this;
318 : }
319 :
320 : /// Assignment operators - Allow assigning into this union from either
321 : /// pointer type, setting the discriminator to remember what it came from.
322 : const PointerUnion3 &operator=(const PT1 &RHS) {
323 : Val = InnerUnion(RHS);
324 : return *this;
325 : }
326 : const PointerUnion3 &operator=(const PT2 &RHS) {
327 : Val = InnerUnion(RHS);
328 : return *this;
329 : }
330 : const PointerUnion3 &operator=(const PT3 &RHS) {
331 : Val = RHS;
332 : return *this;
333 : }
334 :
335 : void *getOpaqueValue() const { return Val.getOpaqueValue(); }
336 : static inline PointerUnion3 getFromOpaqueValue(void *VP) {
337 : PointerUnion3 V;
338 : V.Val = ValTy::getFromOpaqueValue(VP);
339 : return V;
340 : }
341 : };
342 :
343 : // Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has
344 : // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
345 : template<typename PT1, typename PT2, typename PT3>
346 : class PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3> > {
347 : public:
348 : static inline void *
349 : getAsVoidPointer(const PointerUnion3<PT1, PT2, PT3> &P) {
350 : return P.getOpaqueValue();
351 : }
352 : static inline PointerUnion3<PT1, PT2, PT3>
353 : getFromVoidPointer(void *P) {
354 : return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P);
355 : }
356 :
357 : // The number of bits available are the min of the two pointer types.
358 : enum {
359 : NumLowBitsAvailable =
360 : PointerLikeTypeTraits<typename PointerUnion3<PT1, PT2, PT3>::ValTy>
361 : ::NumLowBitsAvailable
362 : };
363 : };
364 :
365 : /// PointerUnion4 - This is a pointer union of four pointer types. See
366 : /// documentation for PointerUnion for usage.
367 : template <typename PT1, typename PT2, typename PT3, typename PT4>
368 : class PointerUnion4 {
369 : public:
370 : typedef PointerUnion<PT1, PT2> InnerUnion1;
371 : typedef PointerUnion<PT3, PT4> InnerUnion2;
372 : typedef PointerUnion<InnerUnion1, InnerUnion2> ValTy;
373 : private:
374 : ValTy Val;
375 : public:
376 0 : PointerUnion4() {}
377 :
378 : PointerUnion4(PT1 V) {
379 : Val = InnerUnion1(V);
380 : }
381 : PointerUnion4(PT2 V) {
382 : Val = InnerUnion1(V);
383 : }
384 : PointerUnion4(PT3 V) {
385 : Val = InnerUnion2(V);
386 : }
387 : PointerUnion4(PT4 V) {
388 : Val = InnerUnion2(V);
389 : }
390 :
391 : /// isNull - Return true if the pointer held in the union is null,
392 : /// regardless of which type it is.
393 13 : bool isNull() const { return Val.isNull(); }
394 : explicit operator bool() const { return !isNull(); }
395 :
396 : /// is<T>() return true if the Union currently holds the type matching T.
397 : template<typename T>
398 : int is() const {
399 : // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
400 : typedef typename
401 : ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1,
402 : ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 >
403 : >::Return Ty;
404 72 : return Val.template is<Ty>() &&
405 12 : Val.template get<Ty>().template is<T>();
406 : }
407 :
408 : /// get<T>() - Return the value of the specified pointer type. If the
409 : /// specified pointer type is incorrect, assert.
410 : template<typename T>
411 : T get() const {
412 12 : assert(is<T>() && "Invalid accessor called");
413 : // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
414 : typedef typename
415 : ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1,
416 : ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 >
417 : >::Return Ty;
418 6 : return Val.template get<Ty>().template get<T>();
419 : }
420 :
421 : /// dyn_cast<T>() - If the current value is of the specified pointer type,
422 : /// return it, otherwise return null.
423 : template<typename T>
424 : T dyn_cast() const {
425 28 : if (is<T>()) return get<T>();
426 16 : return T();
427 22 : }
428 :
429 : /// \brief Assignment from nullptr which just clears the union.
430 : const PointerUnion4 &operator=(std::nullptr_t) {
431 : Val = nullptr;
432 : return *this;
433 : }
434 :
435 : /// Assignment operators - Allow assigning into this union from either
436 : /// pointer type, setting the discriminator to remember what it came from.
437 : const PointerUnion4 &operator=(const PT1 &RHS) {
438 : Val = InnerUnion1(RHS);
439 : return *this;
440 : }
441 : const PointerUnion4 &operator=(const PT2 &RHS) {
442 : Val = InnerUnion1(RHS);
443 : return *this;
444 : }
445 : const PointerUnion4 &operator=(const PT3 &RHS) {
446 : Val = InnerUnion2(RHS);
447 : return *this;
448 : }
449 : const PointerUnion4 &operator=(const PT4 &RHS) {
450 : Val = InnerUnion2(RHS);
451 : return *this;
452 : }
453 :
454 : void *getOpaqueValue() const { return Val.getOpaqueValue(); }
455 : static inline PointerUnion4 getFromOpaqueValue(void *VP) {
456 0 : PointerUnion4 V;
457 0 : V.Val = ValTy::getFromOpaqueValue(VP);
458 0 : return V;
459 : }
460 : };
461 :
462 : // Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has
463 : // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
464 : template<typename PT1, typename PT2, typename PT3, typename PT4>
465 : class PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4> > {
466 : public:
467 : static inline void *
468 : getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) {
469 : return P.getOpaqueValue();
470 : }
471 : static inline PointerUnion4<PT1, PT2, PT3, PT4>
472 : getFromVoidPointer(void *P) {
473 : return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P);
474 : }
475 :
476 : // The number of bits available are the min of the two pointer types.
477 : enum {
478 : NumLowBitsAvailable =
479 : PointerLikeTypeTraits<typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy>
480 : ::NumLowBitsAvailable
481 : };
482 : };
483 :
484 : // Teach DenseMap how to use PointerUnions as keys.
485 : template<typename T, typename U>
486 : struct DenseMapInfo<PointerUnion<T, U> > {
487 : typedef PointerUnion<T, U> Pair;
488 : typedef DenseMapInfo<T> FirstInfo;
489 : typedef DenseMapInfo<U> SecondInfo;
490 :
491 : static inline Pair getEmptyKey() {
492 : return Pair(FirstInfo::getEmptyKey());
493 : }
494 : static inline Pair getTombstoneKey() {
495 : return Pair(FirstInfo::getTombstoneKey());
496 : }
497 : static unsigned getHashValue(const Pair &PairVal) {
498 : intptr_t key = (intptr_t)PairVal.getOpaqueValue();
499 : return DenseMapInfo<intptr_t>::getHashValue(key);
500 : }
501 : static bool isEqual(const Pair &LHS, const Pair &RHS) {
502 : return LHS.template is<T>() == RHS.template is<T>() &&
503 : (LHS.template is<T>() ?
504 : FirstInfo::isEqual(LHS.template get<T>(),
505 : RHS.template get<T>()) :
506 : SecondInfo::isEqual(LHS.template get<U>(),
507 : RHS.template get<U>()));
508 : }
509 : };
510 : }
511 :
512 : #endif
|
