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   using Return = T;
  29 };
  30
  31 /// Get a type based on whether two types are the same or not.
  32 ///
  33 /// For:
  34 ///
  35 /// \code
  36 ///   using Ret = typename PointerUnionTypeSelector<T1, T2, EQ, NE>::Return;
  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   using Return = typename PointerUnionTypeSelectorReturn<RET_NE>::Return;
  43 };
  44
  45 template <typename T, typename RET_EQ, typename RET_NE>
  46 struct PointerUnionTypeSelector<T, T, RET_EQ, RET_NE> {
  47   using Return = typename PointerUnionTypeSelectorReturn<RET_EQ>::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   using Return =
  54       typename PointerUnionTypeSelector<T1, T2, RET_EQ, RET_NE>::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   using ValTy =
  90       PointerIntPair<void *, 1, bool, PointerUnionUIntTraits<PT1, PT2>>;
  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   PointerUnion(PT1 V)
 106       : Val(const_cast<void *>(
 107             PointerLikeTypeTraits<PT1>::getAsVoidPointer(V))) {}
 108   PointerUnion(PT2 V)
 109       : Val(const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(V)),
 110             1) {}
 111
 112   /// Test if the pointer held in the union is null, regardless of
 113   /// which type it is.
 114   bool isNull() const {
 115     // Convert from the void* to one of the pointer types, to make sure that
 116     // we recursively strip off low bits if we have a nested PointerUnion.
 117     return !PointerLikeTypeTraits<PT1>::getFromVoidPointer(Val.getPointer());
 118   }
 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     using Ty = typename ::llvm::PointerUnionTypeSelector<
 125         PT1, T, IsPT1,
 126         ::llvm::PointerUnionTypeSelector<PT2, T, IsPT2,
 127                                          UNION_DOESNT_CONTAIN_TYPE<T>>>::Return;
 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 *>(
 162         reinterpret_cast<const PT1 *>(Val.getAddrOfPointer()));
 163   }
 164
 165   /// Assignment from nullptr which just clears the union.
 166   const PointerUnion &operator=(std::nullptr_t) {
 167     Val.initWithPointer(nullptr);
 168     return *this;
 169   }
 170
 171   /// Assignment operators - Allow assigning into this union from either
 172   /// pointer type, setting the discriminator to remember what it came from.
 173   const PointerUnion &operator=(const PT1 &RHS) {
 174     Val.initWithPointer(
 175         const_cast<void *>(PointerLikeTypeTraits<PT1>::getAsVoidPointer(RHS)));
 176     return *this;
 177   }
 178   const PointerUnion &operator=(const PT2 &RHS) {
 179     Val.setPointerAndInt(
 180         const_cast<void *>(PointerLikeTypeTraits<PT2>::getAsVoidPointer(RHS)),
 181         1);
 182     return *this;
 183   }
 184
 185   void *getOpaqueValue() const { return Val.getOpaqueValue(); }
 186   static inline PointerUnion getFromOpaqueValue(void *VP) {
 187     PointerUnion V;
 188     V.Val = ValTy::getFromOpaqueValue(VP);
 189     return V;
 190   }
 191 };
 192
 193 template <typename PT1, typename PT2>
 194 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 bool operator!=(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
 200   return lhs.getOpaqueValue() != rhs.getOpaqueValue();
 201 }
 202
 203 template <typename PT1, typename PT2>
 204 bool operator<(PointerUnion<PT1, PT2> lhs, PointerUnion<PT1, PT2> rhs) {
 205   return lhs.getOpaqueValue() < rhs.getOpaqueValue();
 206 }
 207
 208 // Teach SmallPtrSet that PointerUnion is "basically a pointer", that has
 209 // # low bits available = min(PT1bits,PT2bits)-1.
 210 template <typename PT1, typename PT2>
 211 struct PointerLikeTypeTraits<PointerUnion<PT1, PT2>> {
 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   using InnerUnion = PointerUnion<PT1, PT2>;
 232   using ValTy = PointerUnion<InnerUnion, PT3>;
 233
 234 private:
 235   ValTy Val;
 236
 237   struct IsInnerUnion {
 238     ValTy Val;
 239
 240     IsInnerUnion(ValTy val) : Val(val) {}
 241
 242     template <typename T> int is() const {
 243       return Val.template is<InnerUnion>() &&
 244              Val.template get<InnerUnion>().template is<T>();
 245     }
 246
 247     template <typename T> T get() const {
 248       return Val.template get<InnerUnion>().template get<T>();
 249     }
 250   };
 251
 252   struct IsPT3 {
 253     ValTy Val;
 254
 255     IsPT3(ValTy val) : Val(val) {}
 256
 257     template <typename T> int is() const { return Val.template is<T>(); }
 258     template <typename T> T get() const { return Val.template get<T>(); }
 259   };
 260
 261 public:
 262   PointerUnion3() = default;
 263   PointerUnion3(PT1 V) { Val = InnerUnion(V); }
 264   PointerUnion3(PT2 V) { Val = InnerUnion(V); }
 265   PointerUnion3(PT3 V) { Val = V; }
 266
 267   /// Test if the pointer held in the union is null, regardless of
 268   /// which type it is.
 269   bool isNull() const { return Val.isNull(); }
 270   explicit operator bool() const { return !isNull(); }
 271
 272   /// Test if the Union currently holds the type matching T.
 273   template <typename T> int is() const {
 274     // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
 275     using Ty = typename ::llvm::PointerUnionTypeSelector<
 276         PT1, T, IsInnerUnion,
 277         ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return;
 278     return Ty(Val).template is<T>();
 279   }
 280
 281   /// Returns the value of the specified pointer type.
 282   ///
 283   /// If the specified pointer type is incorrect, assert.
 284   template <typename T> T get() const {
 285     assert(is<T>() && "Invalid accessor called");
 286     // If T is PT1/PT2 choose IsInnerUnion otherwise choose IsPT3.
 287     using Ty = typename ::llvm::PointerUnionTypeSelector<
 288         PT1, T, IsInnerUnion,
 289         ::llvm::PointerUnionTypeSelector<PT2, T, IsInnerUnion, IsPT3>>::Return;
 290     return Ty(Val).template get<T>();
 291   }
 292
 293   /// Returns the current pointer if it is of the specified pointer type,
 294   /// otherwises returns null.
 295   template <typename T> T dyn_cast() const {
 296     if (is<T>())
 297       return get<T>();
 298     return T();
 299   }
 300
 301   /// Assignment from nullptr which just clears the union.
 302   const PointerUnion3 &operator=(std::nullptr_t) {
 303     Val = nullptr;
 304     return *this;
 305   }
 306
 307   /// Assignment operators - Allow assigning into this union from either
 308   /// pointer type, setting the discriminator to remember what it came from.
 309   const PointerUnion3 &operator=(const PT1 &RHS) {
 310     Val = InnerUnion(RHS);
 311     return *this;
 312   }
 313   const PointerUnion3 &operator=(const PT2 &RHS) {
 314     Val = InnerUnion(RHS);
 315     return *this;
 316   }
 317   const PointerUnion3 &operator=(const PT3 &RHS) {
 318     Val = RHS;
 319     return *this;
 320   }
 321
 322   void *getOpaqueValue() const { return Val.getOpaqueValue(); }
 323   static inline PointerUnion3 getFromOpaqueValue(void *VP) {
 324     PointerUnion3 V;
 325     V.Val = ValTy::getFromOpaqueValue(VP);
 326     return V;
 327   }
 328 };
 329
 330 // Teach SmallPtrSet that PointerUnion3 is "basically a pointer", that has
 331 // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
 332 template <typename PT1, typename PT2, typename PT3>
 333 struct PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3>> {
 334   static inline void *getAsVoidPointer(const PointerUnion3<PT1, PT2, PT3> &P) {
 335     return P.getOpaqueValue();
 336   }
 337
 338   static inline PointerUnion3<PT1, PT2, PT3> getFromVoidPointer(void *P) {
 339     return PointerUnion3<PT1, PT2, PT3>::getFromOpaqueValue(P);
 340   }
 341
 342   // The number of bits available are the min of the two pointer types.
 343   enum {
 344     NumLowBitsAvailable = PointerLikeTypeTraits<
 345         typename PointerUnion3<PT1, PT2, PT3>::ValTy>::NumLowBitsAvailable
 346   };
 347 };
 348
 349 template <typename PT1, typename PT2, typename PT3>
 350 bool operator<(PointerUnion3<PT1, PT2, PT3> lhs,
 351                PointerUnion3<PT1, PT2, PT3> rhs) {
 352   return lhs.getOpaqueValue() < rhs.getOpaqueValue();
 353 }
 354
 355 /// A pointer union of four pointer types. See documentation for PointerUnion
 356 /// for usage.
 357 template <typename PT1, typename PT2, typename PT3, typename PT4>
 358 class PointerUnion4 {
 359 public:
 360   using InnerUnion1 = PointerUnion<PT1, PT2>;
 361   using InnerUnion2 = PointerUnion<PT3, PT4>;
 362   using ValTy = PointerUnion<InnerUnion1, InnerUnion2>;
 363
 364 private:
 365   ValTy Val;
 366
 367 public:
 368   PointerUnion4() = default;
 369   PointerUnion4(PT1 V) { Val = InnerUnion1(V); }
 370   PointerUnion4(PT2 V) { Val = InnerUnion1(V); }
 371   PointerUnion4(PT3 V) { Val = InnerUnion2(V); }
 372   PointerUnion4(PT4 V) { Val = InnerUnion2(V); }
 373
 374   /// Test if the pointer held in the union is null, regardless of
 375   /// which type it is.
 376   bool isNull() const { return Val.isNull(); }
 377   explicit operator bool() const { return !isNull(); }
 378
 379   /// Test if the Union currently holds the type matching T.
 380   template <typename T> int is() const {
 381     // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
 382     using Ty = typename ::llvm::PointerUnionTypeSelector<
 383         PT1, T, InnerUnion1,
 384         ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1,
 385                                          InnerUnion2>>::Return;
 386     return Val.template is<Ty>() && Val.template get<Ty>().template is<T>();
 387   }
 388
 389   /// Returns the value of the specified pointer type.
 390   ///
 391   /// If the specified pointer type is incorrect, assert.
 392   template <typename T> T get() const {
 393     assert(is<T>() && "Invalid accessor called");
 394     // If T is PT1/PT2 choose InnerUnion1 otherwise choose InnerUnion2.
 395     using Ty = typename ::llvm::PointerUnionTypeSelector<
 396         PT1, T, InnerUnion1,
 397         ::llvm::PointerUnionTypeSelector<PT2, T, InnerUnion1,
 398                                          InnerUnion2>>::Return;
 399     return Val.template get<Ty>().template get<T>();
 400   }
 401
 402   /// Returns the current pointer if it is of the specified pointer type,
 403   /// otherwises returns null.
 404   template <typename T> T dyn_cast() const {
 405     if (is<T>())
 406       return get<T>();
 407     return T();
 408   }
 409
 410   /// Assignment from nullptr which just clears the union.
 411   const PointerUnion4 &operator=(std::nullptr_t) {
 412     Val = nullptr;
 413     return *this;
 414   }
 415
 416   /// Assignment operators - Allow assigning into this union from either
 417   /// pointer type, setting the discriminator to remember what it came from.
 418   const PointerUnion4 &operator=(const PT1 &RHS) {
 419     Val = InnerUnion1(RHS);
 420     return *this;
 421   }
 422   const PointerUnion4 &operator=(const PT2 &RHS) {
 423     Val = InnerUnion1(RHS);
 424     return *this;
 425   }
 426   const PointerUnion4 &operator=(const PT3 &RHS) {
 427     Val = InnerUnion2(RHS);
 428     return *this;
 429   }
 430   const PointerUnion4 &operator=(const PT4 &RHS) {
 431     Val = InnerUnion2(RHS);
 432     return *this;
 433   }
 434
 435   void *getOpaqueValue() const { return Val.getOpaqueValue(); }
 436   static inline PointerUnion4 getFromOpaqueValue(void *VP) {
 437     PointerUnion4 V;
 438     V.Val = ValTy::getFromOpaqueValue(VP);
 439     return V;
 440   }
 441 };
 442
 443 // Teach SmallPtrSet that PointerUnion4 is "basically a pointer", that has
 444 // # low bits available = min(PT1bits,PT2bits,PT2bits)-2.
 445 template <typename PT1, typename PT2, typename PT3, typename PT4>
 446 struct PointerLikeTypeTraits<PointerUnion4<PT1, PT2, PT3, PT4>> {
 447   static inline void *
 448   getAsVoidPointer(const PointerUnion4<PT1, PT2, PT3, PT4> &P) {
 449     return P.getOpaqueValue();
 450   }
 451
 452   static inline PointerUnion4<PT1, PT2, PT3, PT4> getFromVoidPointer(void *P) {
 453     return PointerUnion4<PT1, PT2, PT3, PT4>::getFromOpaqueValue(P);
 454   }
 455
 456   // The number of bits available are the min of the two pointer types.
 457   enum {
 458     NumLowBitsAvailable = PointerLikeTypeTraits<
 459         typename PointerUnion4<PT1, PT2, PT3, PT4>::ValTy>::NumLowBitsAvailable
 460   };
 461 };
 462
 463 // Teach DenseMap how to use PointerUnions as keys.
 464 template <typename T, typename U> struct DenseMapInfo<PointerUnion<T, U>> {
 465   using Pair = PointerUnion<T, U>;
 466   using FirstInfo = DenseMapInfo<T>;
 467   using SecondInfo = DenseMapInfo<U>;
 468
 469   static inline Pair getEmptyKey() { return Pair(FirstInfo::getEmptyKey()); }
 470
 471   static inline Pair getTombstoneKey() {
 472     return Pair(FirstInfo::getTombstoneKey());
 473   }
 474
 475   static unsigned getHashValue(const Pair &PairVal) {
 476     intptr_t key = (intptr_t)PairVal.getOpaqueValue();
 477     return DenseMapInfo<intptr_t>::getHashValue(key);
 478   }
 479
 480   static bool isEqual(const Pair &LHS, const Pair &RHS) {
 481     return LHS.template is<T>() == RHS.template is<T>() &&
 482            (LHS.template is<T>() ? FirstInfo::isEqual(LHS.template get<T>(),
 483                                                       RHS.template get<T>())
 484                                  : SecondInfo::isEqual(LHS.template get<U>(),
 485                                                        RHS.template get<U>()));
 486   }
 487 };
 488
 489 } // end namespace llvm
 490
 491 #endif // LLVM_ADT_POINTERUNION_H