PointerIntPair.h revision 54e01d06db7c04208a684e34cb82b0847a077261 
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
20namespace llvm {
21
22template<typename T>
23struct 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///
39template <typename PointerTy, unsigned IntBits, typename IntType=unsigned,
40          typename PtrTraits = PointerLikeTypeTraits<PointerTy> >
41class PointerIntPair {
42  intptr_t Value;
43  enum {
44    /// PointerBitMask - The bits that come from the pointer.
45    PointerBitMask = ~(((intptr_t)1 << PtrTraits::NumLowBitsAvailable)-1),
46    /// IntShift - The number of low bits that we reserve for other uses, and
47    /// keep zero.
48    IntShift = PtrTraits::NumLowBitsAvailable-IntBits,
49
50    /// IntMask - This is the unshifted mask for valid bits of the int type.
51    IntMask = ((intptr_t)1 << IntBits)-1,
52
53    // ShiftedIntMask - This is the bits for the integer shifted in place.
54    ShiftedIntMask = IntMask << IntShift
55  };
56public:
57  PointerIntPair() : Value(0) {}
58  PointerIntPair(PointerTy Ptr, IntType Int) : Value(0) {
59    assert(IntBits <= PtrTraits::NumLowBitsAvailable &&
60           "PointerIntPair formed with integer size too large for pointer");
61    setPointer(Ptr);
62    setInt(Int);
63  }
64
65  PointerTy getPointer() const {
66    return reinterpret_cast<PointerTy>(Value & PointerBitMask);
67  }
68
69  IntType getInt() const {
70    return (IntType)((Value >> IntShift) & IntMask);
71  }
72
73  void setPointer(PointerTy Ptr) {
74    intptr_t PtrVal = reinterpret_cast<intptr_t>(Ptr);
75    assert((PtrVal & ((1 << PtrTraits::NumLowBitsAvailable)-1)) == 0 &&
76           "Pointer is not sufficiently aligned");
77    // Preserve all low bits, just update the pointer.
78    Value = PtrVal | (Value & ~PointerBitMask);
79  }
80
81  void setInt(IntType Int) {
82    intptr_t IntVal = Int;
83    assert(IntVal < (1 << IntBits) && "Integer too large for field");
84
85    // Preserve all bits other than the ones we are updating.
86    Value &= ~ShiftedIntMask;     // Remove integer field.
87    Value |= IntVal << IntShift;  // Set new integer.
88  }
89
90  void *getOpaqueValue() const { return reinterpret_cast<void*>(Value); }
91  void setFromOpaqueValue(void *Val) { Value = reinterpret_cast<intptr_t>(Val);}
92
93  static PointerIntPair getFromOpaqueValue(void *V) {
94    PointerIntPair P; P.setFromOpaqueValue(V); return P;
95  }
96
97  bool operator==(const PointerIntPair &RHS) const {return Value == RHS.Value;}
98  bool operator!=(const PointerIntPair &RHS) const {return Value != RHS.Value;}
99  bool operator<(const PointerIntPair &RHS) const {return Value < RHS.Value;}
100  bool operator>(const PointerIntPair &RHS) const {return Value > RHS.Value;}
101  bool operator<=(const PointerIntPair &RHS) const {return Value <= RHS.Value;}
102  bool operator>=(const PointerIntPair &RHS) const {return Value >= RHS.Value;}
103};
104
105// Provide specialization of DenseMapInfo for PointerIntPair.
106template<typename PointerTy, unsigned IntBits, typename IntType>
107struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType> > {
108  typedef PointerIntPair<PointerTy, IntBits, IntType> Ty;
109  static Ty getEmptyKey() {
110    intptr_t Val = -1;
111    Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
112    return Ty(reinterpret_cast<PointerTy>(Val), IntType((1 << IntBits)-1));
113  }
114  static Ty getTombstoneKey() {
115    intptr_t Val = -2;
116    Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
117    return Ty(reinterpret_cast<PointerTy>(Val), IntType(0));
118  }
119  static unsigned getHashValue(Ty V) {
120    uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue());
121    return unsigned(IV) ^ unsigned(IV >> 9);
122  }
123  static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; }
124  static bool isPod() { return true; }
125};
126
127// Teach SmallPtrSet that PointerIntPair is "basically a pointer".
128template<typename PointerTy, unsigned IntBits, typename IntType>
129class PointerLikeTypeTraits<PointerIntPair<PointerTy, IntBits, IntType> > {
130public:
131  static inline void *
132  getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) {
133    return P.getOpaqueValue();
134  }
135  static inline PointerIntPair<PointerTy, IntBits, IntType>
136  getFromVoidPointer(void *P) {
137    return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
138  }
139  enum {
140    NumLowBitsAvailable =
141           PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable - IntBits
142  };
143};
144
145} // end namespace llvm
146#endif
147