contrib/llvm/include/llvm/ADT/PointerUnion.h

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