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