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