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