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