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