LLVM  mainline
PointerIntPair.h
Go to the documentation of this file.
00001 //===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the PointerIntPair class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_ADT_POINTERINTPAIR_H
00015 #define LLVM_ADT_POINTERINTPAIR_H
00016 
00017 #include "llvm/Support/Compiler.h"
00018 #include "llvm/Support/PointerLikeTypeTraits.h"
00019 #include <cassert>
00020 #include <limits>
00021 
00022 namespace llvm {
00023 
00024 template <typename T> struct DenseMapInfo;
00025 
00026 template <typename PointerT, unsigned IntBits, typename PtrTraits>
00027 struct PointerIntPairInfo;
00028 
00029 /// PointerIntPair - This class implements a pair of a pointer and small
00030 /// integer.  It is designed to represent this in the space required by one
00031 /// pointer by bitmangling the integer into the low part of the pointer.  This
00032 /// can only be done for small integers: typically up to 3 bits, but it depends
00033 /// on the number of bits available according to PointerLikeTypeTraits for the
00034 /// type.
00035 ///
00036 /// Note that PointerIntPair always puts the IntVal part in the highest bits
00037 /// possible.  For example, PointerIntPair<void*, 1, bool> will put the bit for
00038 /// the bool into bit #2, not bit #0, which allows the low two bits to be used
00039 /// for something else.  For example, this allows:
00040 ///   PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool>
00041 /// ... and the two bools will land in different bits.
00042 ///
00043 template <typename PointerTy, unsigned IntBits, typename IntType = unsigned,
00044           typename PtrTraits = PointerLikeTypeTraits<PointerTy>,
00045           typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>>
00046 class PointerIntPair {
00047   intptr_t Value;
00048 
00049 public:
00050   PointerIntPair() : Value(0) {}
00051   PointerIntPair(PointerTy PtrVal, IntType IntVal) {
00052     setPointerAndInt(PtrVal, IntVal);
00053   }
00054   explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); }
00055 
00056   PointerTy getPointer() const { return Info::getPointer(Value); }
00057 
00058   IntType getInt() const {
00059     return (IntType)Info::getInt(Value);
00060   }
00061 
00062   void setPointer(PointerTy PtrVal) {
00063     Value = Info::updatePointer(Value, PtrVal);
00064   }
00065 
00066   void setInt(IntType IntVal) {
00067     Value = Info::updateInt(Value, static_cast<intptr_t>(IntVal));
00068   }
00069 
00070   void initWithPointer(PointerTy PtrVal) {
00071     Value = Info::updatePointer(0, PtrVal);
00072   }
00073 
00074   void setPointerAndInt(PointerTy PtrVal, IntType IntVal) {
00075     Value = Info::updateInt(Info::updatePointer(0, PtrVal),
00076                             static_cast<intptr_t>(IntVal));
00077   }
00078 
00079   PointerTy const *getAddrOfPointer() const {
00080     return const_cast<PointerIntPair *>(this)->getAddrOfPointer();
00081   }
00082 
00083   PointerTy *getAddrOfPointer() {
00084     assert(Value == reinterpret_cast<intptr_t>(getPointer()) &&
00085            "Can only return the address if IntBits is cleared and "
00086            "PtrTraits doesn't change the pointer");
00087     return reinterpret_cast<PointerTy *>(&Value);
00088   }
00089 
00090   void *getOpaqueValue() const { return reinterpret_cast<void *>(Value); }
00091   void setFromOpaqueValue(void *Val) {
00092     Value = reinterpret_cast<intptr_t>(Val);
00093   }
00094 
00095   static PointerIntPair getFromOpaqueValue(void *V) {
00096     PointerIntPair P;
00097     P.setFromOpaqueValue(V);
00098     return P;
00099   }
00100 
00101   // Allow PointerIntPairs to be created from const void * if and only if the
00102   // pointer type could be created from a const void *.
00103   static PointerIntPair getFromOpaqueValue(const void *V) {
00104     (void)PtrTraits::getFromVoidPointer(V);
00105     return getFromOpaqueValue(const_cast<void *>(V));
00106   }
00107 
00108   bool operator==(const PointerIntPair &RHS) const {
00109     return Value == RHS.Value;
00110   }
00111   bool operator!=(const PointerIntPair &RHS) const {
00112     return Value != RHS.Value;
00113   }
00114   bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; }
00115   bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; }
00116   bool operator<=(const PointerIntPair &RHS) const {
00117     return Value <= RHS.Value;
00118   }
00119   bool operator>=(const PointerIntPair &RHS) const {
00120     return Value >= RHS.Value;
00121   }
00122 };
00123 
00124 template <typename PointerT, unsigned IntBits, typename PtrTraits>
00125 struct PointerIntPairInfo {
00126   static_assert(PtrTraits::NumLowBitsAvailable <
00127                     std::numeric_limits<uintptr_t>::digits,
00128                 "cannot use a pointer type that has all bits free");
00129   static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
00130                 "PointerIntPair with integer size too large for pointer");
00131   enum : uintptr_t {
00132     /// PointerBitMask - The bits that come from the pointer.
00133     PointerBitMask =
00134         ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1),
00135 
00136     /// IntShift - The number of low bits that we reserve for other uses, and
00137     /// keep zero.
00138     IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits,
00139 
00140     /// IntMask - This is the unshifted mask for valid bits of the int type.
00141     IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1),
00142 
00143     // ShiftedIntMask - This is the bits for the integer shifted in place.
00144     ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
00145   };
00146 
00147   static PointerT getPointer(intptr_t Value) {
00148     return PtrTraits::getFromVoidPointer(
00149         reinterpret_cast<void *>(Value & PointerBitMask));
00150   }
00151 
00152   static intptr_t getInt(intptr_t Value) {
00153     return (Value >> IntShift) & IntMask;
00154   }
00155 
00156   static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) {
00157     intptr_t PtrWord =
00158         reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr));
00159     assert((PtrWord & ~PointerBitMask) == 0 &&
00160            "Pointer is not sufficiently aligned");
00161     // Preserve all low bits, just update the pointer.
00162     return PtrWord | (OrigValue & ~PointerBitMask);
00163   }
00164 
00165   static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) {
00166     intptr_t IntWord = static_cast<intptr_t>(Int);
00167     assert((IntWord & ~IntMask) == 0 && "Integer too large for field");
00168 
00169     // Preserve all bits other than the ones we are updating.
00170     return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift;
00171   }
00172 };
00173 
00174 template <typename T> struct isPodLike;
00175 template <typename PointerTy, unsigned IntBits, typename IntType>
00176 struct isPodLike<PointerIntPair<PointerTy, IntBits, IntType>> {
00177   static const bool value = true;
00178 };
00179 
00180 // Provide specialization of DenseMapInfo for PointerIntPair.
00181 template <typename PointerTy, unsigned IntBits, typename IntType>
00182 struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>> {
00183   typedef PointerIntPair<PointerTy, IntBits, IntType> Ty;
00184   static Ty getEmptyKey() {
00185     uintptr_t Val = static_cast<uintptr_t>(-1);
00186     Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable;
00187     return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
00188   }
00189   static Ty getTombstoneKey() {
00190     uintptr_t Val = static_cast<uintptr_t>(-2);
00191     Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
00192     return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
00193   }
00194   static unsigned getHashValue(Ty V) {
00195     uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue());
00196     return unsigned(IV) ^ unsigned(IV >> 9);
00197   }
00198   static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; }
00199 };
00200 
00201 // Teach SmallPtrSet that PointerIntPair is "basically a pointer".
00202 template <typename PointerTy, unsigned IntBits, typename IntType,
00203           typename PtrTraits>
00204 class PointerLikeTypeTraits<
00205     PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> {
00206 public:
00207   static inline void *
00208   getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) {
00209     return P.getOpaqueValue();
00210   }
00211   static inline PointerIntPair<PointerTy, IntBits, IntType>
00212   getFromVoidPointer(void *P) {
00213     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
00214   }
00215   static inline PointerIntPair<PointerTy, IntBits, IntType>
00216   getFromVoidPointer(const void *P) {
00217     return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
00218   }
00219   enum { NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits };
00220 };
00221 
00222 } // end namespace llvm
00223 #endif