include/llvm/ADT/PointerIntPair.h

   1 //===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- 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 PointerIntPair class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_POINTERINTPAIR_H
  15 #define LLVM_ADT_POINTERINTPAIR_H
  16
  17 #include "llvm/Support/Compiler.h"
  18 #include "llvm/Support/PointerLikeTypeTraits.h"
  19 #include <cassert>
  20 #include <limits>
  21
  22 namespace llvm {
  23
  24 template<typename T>
  25 struct DenseMapInfo;
  26
  27 /// PointerIntPair - This class implements a pair of a pointer and small
  28 /// integer.  It is designed to represent this in the space required by one
  29 /// pointer by bitmangling the integer into the low part of the pointer.  This
  30 /// can only be done for small integers: typically up to 3 bits, but it depends
  31 /// on the number of bits available according to PointerLikeTypeTraits for the
  32 /// type.
  33 ///
  34 /// Note that PointerIntPair always puts the IntVal part in the highest bits
  35 /// possible.  For example, PointerIntPair<void*, 1, bool> will put the bit for
  36 /// the bool into bit #2, not bit #0, which allows the low two bits to be used
  37 /// for something else.  For example, this allows:
  38 ///   PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool>
  39 /// ... and the two bools will land in different bits.
  40 ///
  41 template <typename PointerTy, unsigned IntBits, typename IntType=unsigned,
  42           typename PtrTraits = PointerLikeTypeTraits<PointerTy> >
  43 class PointerIntPair {
  44   intptr_t Value;
  45   static_assert(PtrTraits::NumLowBitsAvailable <
  46                 std::numeric_limits<uintptr_t>::digits,
  47                 "cannot use a pointer type that has all bits free");
  48   static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
  49                 "PointerIntPair with integer size too large for pointer");
  50   enum : uintptr_t {
  51     /// PointerBitMask - The bits that come from the pointer.
  52     PointerBitMask =
  53       ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable)-1),
  54
  55     /// IntShift - The number of low bits that we reserve for other uses, and
  56     /// keep zero.
  57     IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits,
  58
  59     /// IntMask - This is the unshifted mask for valid bits of the int type.
  60     IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1),
  61
  62     // ShiftedIntMask - This is the bits for the integer shifted in place.
  63     ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
  64   };
  65
  66 public:
  67   PointerIntPair() : Value(0) {}
  68   PointerIntPair(PointerTy PtrVal, IntType IntVal) {
  69     setPointerAndInt(PtrVal, IntVal);
  70   }
  71   explicit PointerIntPair(PointerTy PtrVal) {
  72     initWithPointer(PtrVal);
  73   }
  74
  75   PointerTy getPointer() const {
  76     return PtrTraits::getFromVoidPointer(
  77                          reinterpret_cast<void*>(Value & PointerBitMask));
  78   }
  79
  80   IntType getInt() const {
  81     return (IntType)((Value >> IntShift) & IntMask);
  82   }
  83
  84   void setPointer(PointerTy PtrVal) {
  85     intptr_t PtrWord
  86       = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal));
  87     assert((PtrWord & ~PointerBitMask) == 0 &&
  88            "Pointer is not sufficiently aligned");
  89     // Preserve all low bits, just update the pointer.
  90     Value = PtrWord | (Value & ~PointerBitMask);
  91   }
  92
  93   void setInt(IntType IntVal) {
  94     intptr_t IntWord = static_cast<intptr_t>(IntVal);
  95     assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
  96
  97     // Preserve all bits other than the ones we are updating.
  98     Value &= ~ShiftedIntMask;     // Remove integer field.
  99     Value |= IntWord << IntShift;  // Set new integer.
 100   }
 101
 102   void initWithPointer(PointerTy PtrVal) {
 103     intptr_t PtrWord
 104       = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal));
 105     assert((PtrWord & ~PointerBitMask) == 0 &&
 106            "Pointer is not sufficiently aligned");
 107     Value = PtrWord;
 108   }
 109
 110   void setPointerAndInt(PointerTy PtrVal, IntType IntVal) {
 111     intptr_t PtrWord
 112       = reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(PtrVal));
 113     assert((PtrWord & ~PointerBitMask) == 0 &&
 114            "Pointer is not sufficiently aligned");
 115     intptr_t IntWord = static_cast<intptr_t>(IntVal);
 116     assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
 117
 118     Value = PtrWord | (IntWord << IntShift);
 119   }
 120
 121   PointerTy const *getAddrOfPointer() const {
 122     return const_cast<PointerIntPair *>(this)->getAddrOfPointer();
 123   }
 124
 125   PointerTy *getAddrOfPointer() {
 126     assert(Value == reinterpret_cast<intptr_t>(getPointer()) &&
 127            "Can only return the address if IntBits is cleared and "
 128            "PtrTraits doesn't change the pointer");
 129     return reinterpret_cast<PointerTy *>(&Value);
 130   }
 131
 132   void *getOpaqueValue() const { return reinterpret_cast<void*>(Value); }
 133   void setFromOpaqueValue(void *Val) { Value = reinterpret_cast<intptr_t>(Val);}
 134
 135   static PointerIntPair getFromOpaqueValue(void *V) {
 136     PointerIntPair P;
 137     P.setFromOpaqueValue(V);
 138     return P;
 139   }
 140
 141   // Allow PointerIntPairs to be created from const void * if and only if the
 142   // pointer type could be created from a const void *.
 143   static PointerIntPair getFromOpaqueValue(const void *V) {
 144     (void)PtrTraits::getFromVoidPointer(V);
 145     return getFromOpaqueValue(const_cast<void *>(V));
 146   }
 147
 148   bool operator==(const PointerIntPair &RHS) const {return Value == RHS.Value;}
 149   bool operator!=(const PointerIntPair &RHS) const {return Value != RHS.Value;}
 150   bool operator<(const PointerIntPair &RHS) const {return Value < RHS.Value;}
 151   bool operator>(const PointerIntPair &RHS) const {return Value > RHS.Value;}
 152   bool operator<=(const PointerIntPair &RHS) const {return Value <= RHS.Value;}
 153   bool operator>=(const PointerIntPair &RHS) const {return Value >= RHS.Value;}
 154 };
 155
 156 template <typename T> struct isPodLike;
 157 template<typename PointerTy, unsigned IntBits, typename IntType>
 158 struct isPodLike<PointerIntPair<PointerTy, IntBits, IntType> > {
 159    static const bool value = true;
 160 };
 161
 162 // Provide specialization of DenseMapInfo for PointerIntPair.
 163 template<typename PointerTy, unsigned IntBits, typename IntType>
 164 struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType> > {
 165   typedef PointerIntPair<PointerTy, IntBits, IntType> Ty;
 166   static Ty getEmptyKey() {
 167     uintptr_t Val = static_cast<uintptr_t>(-1);
 168     Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable;
 169     return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
 170   }
 171   static Ty getTombstoneKey() {
 172     uintptr_t Val = static_cast<uintptr_t>(-2);
 173     Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
 174     return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
 175   }
 176   static unsigned getHashValue(Ty V) {
 177     uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue());
 178     return unsigned(IV) ^ unsigned(IV >> 9);
 179   }
 180   static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; }
 181 };
 182
 183 // Teach SmallPtrSet that PointerIntPair is "basically a pointer".
 184 template<typename PointerTy, unsigned IntBits, typename IntType,
 185          typename PtrTraits>
 186 class PointerLikeTypeTraits<PointerIntPair<PointerTy, IntBits, IntType,
 187                                            PtrTraits> > {
 188 public:
 189   static inline void *
 190   getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) {
 191     return P.getOpaqueValue();
 192   }
 193   static inline PointerIntPair<PointerTy, IntBits, IntType>
 194   getFromVoidPointer(void *P) {
 195     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
 196   }
 197   static inline PointerIntPair<PointerTy, IntBits, IntType>
 198   getFromVoidPointer(const void *P) {
 199     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
 200   }
 201   enum {
 202     NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits
 203   };
 204 };
 205
 206 } // end namespace llvm
 207 #endif