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     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   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       return P.getOpaqueValue();
 212     }
 213     static inline PointerUnion<PT1, PT2>
 214     getFromVoidPointer(void *P) {
 215       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       IsInnerUnion(ValTy val) : Val(val) { }
 240       template<typename T>
 241       int is() const {
 242         return Val.template is<InnerUnion>() &&
 243                Val.template get<InnerUnion>().template is<T>();
 244       }
 245       template<typename T>
 246       T get() const {
 247         return Val.template get<InnerUnion>().template get<T>();
 248       }
 249     };
 250
 251     struct IsPT3 {
 252       ValTy Val;
 253       IsPT3(ValTy val) : Val(val) { }
 254       template<typename T>
 255       int is() const {
 256         return Val.template is<T>();
 257       }
 258       template<typename T>
 259       T get() const {
 260         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     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       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       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       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       if (is<T>()) return get<T>();
 311       return T();
 312     }
 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     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     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       return Val.template is<Ty>() &&
 405              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       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       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       if (is<T>()) return get<T>();
 426       return T();
 427     }
 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       PointerUnion4 V;
 457       V.Val = ValTy::getFromOpaqueValue(VP);
 458       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