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>
  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     static inline void *getAsVoidPointer(void *P) { return P; }
  57     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     PointerUnion() {}
  99
 100     PointerUnion(PT1 V) : Val(
 101       const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) {
 102     }
 103     PointerUnion(PT2 V) : Val(
 104       const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)), 1) {
 105     }
 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       return !PointerLikeTypeTraits<PT1>::getFromVoidPointer(Val.getPointer());
 113     }
 114     LLVM_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       int TyNo = Ty::Num;
 124       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       assert(is<T>() && "Invalid accessor called");
 132       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       if (is<T>()) return get<T>();
 140       return T();
 141     }
 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       assert(is<PT1>() && "Val is not the first pointer");
 153       assert(get<PT1>() == Val.getPointer() &&
 154          "Can't get the address because PointerLikeTypeTraits changes the ptr");
 155       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       Val.setPointerAndInt(
 173         const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(RHS)),
 174         1);
 175       return *this;
 176     }
 177
 178     void *getOpaqueValue() const { return Val.getOpaqueValue(); }
 179     static inline PointerUnion getFromOpaqueValue(void *VP) {
 180       PointerUnion V;
 181       V.Val = ValTy::getFromOpaqueValue(VP);
 182       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   // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
 199   // # low bits available = min(PT1bits,PT2bits)-1.
 200   template<typename PT1, typename PT2>
 201   class PointerLikeTypeTraits<PointerUnion<PT1, PT2> > {
 202   public:
 203     static inline void *
 204     getAsVoidPointer(const PointerUnion<PT1, PT2> &P) {
 205       return P.getOpaqueValue();
 206     }
 207     static inline PointerUnion<PT1, PT2>
 208     getFromVoidPointer(void *P) {
 209       return PointerUnion<PT1, PT2>::getFromOpaqueValue(P);
 210     }
 211
 212     // The number of bits available are the min of the two pointer types.
 213     enum {
 214       NumLowBitsAvailable =
 215         PointerLikeTypeTraits<typename PointerUnion<PT1,PT2>::ValTy>
 216           ::NumLowBitsAvailable
 217     };
 218   };
 219
 220
 221   /// PointerUnion3 - This is a pointer union of three pointer types.  See
 222   /// documentation for PointerUnion for usage.
 223   template <typename PT1, typename PT2, typename PT3>
 224   class PointerUnion3 {
 225   public:
 226     typedef PointerUnion<PT1, PT2> InnerUnion;
 227     typedef PointerUnion<InnerUnion, PT3> ValTy;
 228   private:
 229     ValTy Val;
 230
 231     struct IsInnerUnion {
 232       ValTy Val;
 233       IsInnerUnion(ValTy val) : Val(val) { }
 234       template<typename T>
 235       int is() const {
 236         return Val.template is<InnerUnion>() &&
 237                Val.template get<InnerUnion>().template is<T>();
 238       }
 239       template<typename T>
 240       T get() const {
 241         return Val.template get<InnerUnion>().template get<T>();
 242       }
 243     };
 244
 245     struct IsPT3 {
 246       ValTy Val;
 247       IsPT3(ValTy val) : Val(val) { }
 248       template<typename T>
 249       int is() const {
 250         return Val.template is<T>();
 251       }
 252       template<typename T>
 253       T get() const {
 254         return Val.template get<T>();
 255       }
 256     };
 257
 258   public:
 259     PointerUnion3() {}
 260
 261     PointerUnion3(PT1 V) {
 262       Val = InnerUnion(V);
 263     }
 264     PointerUnion3(PT2 V) {
 265       Val = InnerUnion(V);
 266     }
 267     PointerUnion3(PT3 V) {
 268       Val = V;
 269     }
 270
 271     /// isNull - Return true if the pointer held in the union is null,
 272     /// regardless of which type it is.
 273     bool isNull() const { return Val.isNull(); }
 274     LLVM_EXPLICIT operator bool() const { return !isNull(); }
 275
 276     /// is<T>() return true if the Union currently holds the type matching T.
 277     template<typename T>
 278     int is() const {
 279       // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
 280       typedef typename
 281         ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion,
 282           ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 >
 283                                                                    >::Return Ty;
 284       return Ty(Val).template is<T>();
 285     }
 286
 287     /// get<T>() - Return the value of the specified pointer type. If the
 288     /// specified pointer type is incorrect, assert.
 289     template<typename T>
 290     T get() const {
 291       assert(is<T>() && "Invalid accessor called");
 292       // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
 293       typedef typename
 294         ::llvm::PointerUnionTypeSelector<PT1, T, IsInnerUnion,
 295           ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3 >
 296                                                                    >::Return Ty;
 297       return Ty(Val).template get<T>();
 298     }
 299
 300     /// dyn_cast<T>() - If the current value is of the specified pointer type,
 301     /// return it, otherwise return null.
 302     template<typename T>
 303     T dyn_cast() const {
 304       if (is<T>()) return get<T>();
 305       return T();
 306     }
 307
 308     /// \brief Assignment from nullptr which just clears the union.
 309     const PointerUnion3 &operator=(std::nullptr_t) {
 310       Val = nullptr;
 311       return *this;
 312     }
 313
 314     /// Assignment operators - Allow assigning into this union from either
 315     /// pointer type, setting the discriminator to remember what it came from.
 316     const PointerUnion3 &operator=(const PT1 &RHS) {
 317       Val = InnerUnion(RHS);
 318       return *this;
 319     }
 320     const PointerUnion3 &operator=(const PT2 &RHS) {
 321       Val = InnerUnion(RHS);
 322       return *this;
 323     }
 324     const PointerUnion3 &operator=(const PT3 &RHS) {
 325       Val = RHS;
 326       return *this;
 327     }
 328
 329     void *getOpaqueValue() const { return Val.getOpaqueValue(); }
 330     static inline PointerUnion3 getFromOpaqueValue(void *VP) {
 331       PointerUnion3 V;
 332       V.Val = ValTy::getFromOpaqueValue(VP);
 333       return V;
 334     }
 335   };
 336
 337   // Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has
 338   // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
 339   template<typename PT1, typename PT2, typename PT3>
 340   class PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3> > {
 341   public:
 342     static inline void *
 343     getAsVoidPointer(const PointerUnion3<PT1, PT2, PT3> &P) {
 344       return P.getOpaqueValue();
 345     }
 346     static inline PointerUnion3<PT1, PT2, PT3>
 347     getFromVoidPointer(void *P) {
 348       return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P);
 349     }
 350
 351     // The number of bits available are the min of the two pointer types.
 352     enum {
 353       NumLowBitsAvailable =
 354         PointerLikeTypeTraits<typename PointerUnion3<PT1, PT2, PT3>::ValTy>
 355           ::NumLowBitsAvailable
 356     };
 357   };
 358
 359   /// PointerUnion4 - This is a pointer union of four pointer types.  See
 360   /// documentation for PointerUnion for usage.
 361   template <typename PT1, typename PT2, typename PT3, typename PT4>
 362   class PointerUnion4 {
 363   public:
 364     typedef PointerUnion<PT1, PT2> InnerUnion1;
 365     typedef PointerUnion<PT3, PT4> InnerUnion2;
 366     typedef PointerUnion<InnerUnion1, InnerUnion2> ValTy;
 367   private:
 368     ValTy Val;
 369   public:
 370     PointerUnion4() {}
 371
 372     PointerUnion4(PT1 V) {
 373       Val = InnerUnion1(V);
 374     }
 375     PointerUnion4(PT2 V) {
 376       Val = InnerUnion1(V);
 377     }
 378     PointerUnion4(PT3 V) {
 379       Val = InnerUnion2(V);
 380     }
 381     PointerUnion4(PT4 V) {
 382       Val = InnerUnion2(V);
 383     }
 384
 385     /// isNull - Return true if the pointer held in the union is null,
 386     /// regardless of which type it is.
 387     bool isNull() const { return Val.isNull(); }
 388     LLVM_EXPLICIT operator bool() const { return !isNull(); }
 389
 390     /// is<T>() return true if the Union currently holds the type matching T.
 391     template<typename T>
 392     int is() const {
 393       // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
 394       typedef typename
 395         ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1,
 396           ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 >
 397                                                                    >::Return Ty;
 398       return Val.template is<Ty>() &&
 399              Val.template get<Ty>().template is<T>();
 400     }
 401
 402     /// get<T>() - Return the value of the specified pointer type. If the
 403     /// specified pointer type is incorrect, assert.
 404     template<typename T>
 405     T get() const {
 406       assert(is<T>() && "Invalid accessor called");
 407       // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
 408       typedef typename
 409         ::llvm::PointerUnionTypeSelector<PT1, T, InnerUnion1,
 410           ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1, InnerUnion2 >
 411                                                                    >::Return Ty;
 412       return Val.template get<Ty>().template get<T>();
 413     }
 414
 415     /// dyn_cast<T>() - If the current value is of the specified pointer type,
 416     /// return it, otherwise return null.
 417     template<typename T>
 418     T dyn_cast() const {
 419       if (is<T>()) return get<T>();
 420       return T();
 421     }
 422
 423     /// \brief Assignment from nullptr which just clears the union.
 424     const PointerUnion4 &operator=(std::nullptr_t) {
 425       Val = nullptr;
 426       return *this;
 427     }
 428
 429     /// Assignment operators - Allow assigning into this union from either
 430     /// pointer type, setting the discriminator to remember what it came from.
 431     const PointerUnion4 &operator=(const PT1 &RHS) {
 432       Val = InnerUnion1(RHS);
 433       return *this;
 434     }
 435     const PointerUnion4 &operator=(const PT2 &RHS) {
 436       Val = InnerUnion1(RHS);
 437       return *this;
 438     }
 439     const PointerUnion4 &operator=(const PT3 &RHS) {
 440       Val = InnerUnion2(RHS);
 441       return *this;
 442     }
 443     const PointerUnion4 &operator=(const PT4 &RHS) {
 444       Val = InnerUnion2(RHS);
 445       return *this;
 446     }
 447
 448     void *getOpaqueValue() const { return Val.getOpaqueValue(); }
 449     static inline PointerUnion4 getFromOpaqueValue(void *VP) {
 450       PointerUnion4 V;
 451       V.Val = ValTy::getFromOpaqueValue(VP);
 452       return V;
 453     }
 454   };
 455
 456   // Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has
 457   // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
 458   template<typename PT1, typename PT2, typename PT3, typename PT4>
 459   class PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4> > {
 460   public:
 461     static inline void *
 462     getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) {
 463       return P.getOpaqueValue();
 464     }
 465     static inline PointerUnion4<PT1, PT2, PT3, PT4>
 466     getFromVoidPointer(void *P) {
 467       return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P);
 468     }
 469
 470     // The number of bits available are the min of the two pointer types.
 471     enum {
 472       NumLowBitsAvailable =
 473         PointerLikeTypeTraits<typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy>
 474           ::NumLowBitsAvailable
 475     };
 476   };
 477
 478   // Teach DenseMap how to use PointerUnions as keys.
 479   template<typename T, typename U>
 480   struct DenseMapInfo<PointerUnion<T, U> > {
 481     typedef PointerUnion<T, U> Pair;
 482     typedef DenseMapInfo<T> FirstInfo;
 483     typedef DenseMapInfo<U> SecondInfo;
 484
 485     static inline Pair getEmptyKey() {
 486       return Pair(FirstInfo::getEmptyKey());
 487     }
 488     static inline Pair getTombstoneKey() {
 489       return Pair(FirstInfo::getTombstoneKey());
 490     }
 491     static unsigned getHashValue(const Pair &PairVal) {
 492       intptr_t key = (intptr_t)PairVal.getOpaqueValue();
 493       return DenseMapInfo<intptr_t>::getHashValue(key);
 494     }
 495     static bool isEqual(const Pair &LHS, const Pair &RHS) {
 496       return LHS.template is<T>() == RHS.template is<T>() &&
 497              (LHS.template is<T>() ?
 498               FirstInfo::isEqual(LHS.template get<T>(),
 499                                  RHS.template get<T>()) :
 500               SecondInfo::isEqual(LHS.template get<U>(),
 501                                   RHS.template get<U>()));
 502     }
 503   };
 504 }
 505
 506 #endif