1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
|
//===- llvm/ADT/ValueMap.h - Safe map from Values to data -------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the ValueMap class.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_VALUEMAP_H
#define LLVM_ADT_VALUEMAP_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/type_traits.h"
#include "llvm/System/Mutex.h"
#include <iterator>
namespace llvm {
template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT>
class ValueMapCallbackVH;
template<typename DenseMapT, typename KeyT>
class ValueMapIterator;
template<typename DenseMapT, typename KeyT>
class ValueMapConstIterator;
template<typename KeyT>
struct ValueMapConfig {
/// If FollowRAUW is true, the ValueMap will update mappings on RAUW. If it's
/// false, the ValueMap will leave the original mapping in place.
enum { FollowRAUW = true };
// All methods will be called with a first argument of type ExtraData. The
// default implementations in this class take a templated first argument so
// that users' subclasses can use any type they want without having to
// override all the defaults.
struct ExtraData {};
template<typename ExtraDataT>
static void onRAUW(const ExtraDataT &Data, KeyT Old, KeyT New) {}
template<typename ExtraDataT>
static void onDeleted(const ExtraDataT &Data, KeyT Old) {}
/// Returns a mutex that should be acquired around any changes to the map.
/// This is only acquired from the CallbackVH (and held around calls to onRAUW
/// and onDeleted) and not inside other ValueMap methods. NULL means that no
/// mutex is necessary.
template<typename ExtraDataT>
static sys::Mutex *getMutex(const ExtraDataT &Data) { return NULL; }
};
/// ValueMap maps Value* or any subclass to an arbitrary other
/// type. It provides the DenseMap interface. When the key values are
/// deleted or RAUWed, ValueMap relies on the Config to decide what to
/// do. Config parameters should inherit from ValueMapConfig<KeyT> to
/// get default implementations of all the methods ValueMap uses.
///
/// By default, when a key is RAUWed from V1 to V2, the old mapping
/// V1->target is removed, and a new mapping V2->target is added. If
/// V2 already existed, its old target is overwritten. When a key is
/// deleted, its mapping is removed. You can override Config to get
/// called back on each event.
template<typename KeyT, typename ValueT, typename Config = ValueMapConfig<KeyT>,
typename ValueInfoT = DenseMapInfo<ValueT> >
class ValueMap {
friend class ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT>;
typedef ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> ValueMapCVH;
typedef DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH>,
ValueInfoT> MapT;
typedef typename Config::ExtraData ExtraData;
MapT Map;
ExtraData Data;
public:
typedef KeyT key_type;
typedef ValueT mapped_type;
typedef std::pair<KeyT, ValueT> value_type;
ValueMap(const ValueMap& Other) : Map(Other.Map), Data(Other.Data) {}
explicit ValueMap(unsigned NumInitBuckets = 64)
: Map(NumInitBuckets), Data() {}
explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64)
: Map(NumInitBuckets), Data(Data) {}
~ValueMap() {}
typedef ValueMapIterator<MapT, KeyT> iterator;
typedef ValueMapConstIterator<MapT, KeyT> const_iterator;
inline iterator begin() { return iterator(Map.begin()); }
inline iterator end() { return iterator(Map.end()); }
inline const_iterator begin() const { return const_iterator(Map.begin()); }
inline const_iterator end() const { return const_iterator(Map.end()); }
bool empty() const { return Map.empty(); }
unsigned size() const { return Map.size(); }
/// Grow the map so that it has at least Size buckets. Does not shrink
void resize(size_t Size) { Map.resize(Size); }
void clear() { Map.clear(); }
/// count - Return true if the specified key is in the map.
bool count(const KeyT &Val) const {
return Map.count(Wrap(Val));
}
iterator find(const KeyT &Val) {
return iterator(Map.find(Wrap(Val)));
}
const_iterator find(const KeyT &Val) const {
return const_iterator(Map.find(Wrap(Val)));
}
/// lookup - Return the entry for the specified key, or a default
/// constructed value if no such entry exists.
ValueT lookup(const KeyT &Val) const {
return Map.lookup(Wrap(Val));
}
// Inserts key,value pair into the map if the key isn't already in the map.
// If the key is already in the map, it returns false and doesn't update the
// value.
std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
std::pair<typename MapT::iterator, bool> map_result=
Map.insert(std::make_pair(Wrap(KV.first), KV.second));
return std::make_pair(iterator(map_result.first), map_result.second);
}
/// insert - Range insertion of pairs.
template<typename InputIt>
void insert(InputIt I, InputIt E) {
for (; I != E; ++I)
insert(*I);
}
bool erase(const KeyT &Val) {
return Map.erase(Wrap(Val));
}
bool erase(iterator I) {
return Map.erase(I.base());
}
value_type& FindAndConstruct(const KeyT &Key) {
return Map.FindAndConstruct(Wrap(Key));
}
ValueT &operator[](const KeyT &Key) {
return Map[Wrap(Key)];
}
ValueMap& operator=(const ValueMap& Other) {
Map = Other.Map;
Data = Other.Data;
return *this;
}
/// isPointerIntoBucketsArray - Return true if the specified pointer points
/// somewhere into the ValueMap's array of buckets (i.e. either to a key or
/// value in the ValueMap).
bool isPointerIntoBucketsArray(const void *Ptr) const {
return Map.isPointerIntoBucketsArray(Ptr);
}
/// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
/// array. In conjunction with the previous method, this can be used to
/// determine whether an insertion caused the ValueMap to reallocate.
const void *getPointerIntoBucketsArray() const {
return Map.getPointerIntoBucketsArray();
}
private:
ValueMapCVH Wrap(KeyT key) const {
// The only way the resulting CallbackVH could try to modify *this (making
// the const_cast incorrect) is if it gets inserted into the map. But then
// this function must have been called from a non-const method, making the
// const_cast ok.
return ValueMapCVH(key, const_cast<ValueMap*>(this));
}
};
template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT>
class ValueMapCallbackVH : public CallbackVH {
friend class ValueMap<KeyT, ValueT, Config, ValueInfoT>;
friend class DenseMapInfo<ValueMapCallbackVH>;
typedef ValueMap<KeyT, ValueT, Config, ValueInfoT> ValueMapT;
typedef typename llvm::remove_pointer<KeyT>::type KeySansPointerT;
ValueMapT *Map;
ValueMapCallbackVH(KeyT Key, ValueMapT *Map)
: CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))),
Map(Map) {}
public:
KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); }
virtual void deleted() {
// Make a copy that won't get changed even when *this is destroyed.
ValueMapCallbackVH Copy(*this);
sys::Mutex *M = Config::getMutex(Copy.Map->Data);
if (M)
M->acquire();
Config::onDeleted(Copy.Map->Data, Copy.Unwrap()); // May destroy *this.
Copy.Map->Map.erase(Copy); // Definitely destroys *this.
if (M)
M->release();
}
virtual void allUsesReplacedWith(Value *new_key) {
assert(isa<KeySansPointerT>(new_key) &&
"Invalid RAUW on key of ValueMap<>");
// Make a copy that won't get changed even when *this is destroyed.
ValueMapCallbackVH Copy(*this);
sys::Mutex *M = Config::getMutex(Copy.Map->Data);
if (M)
M->acquire();
KeyT typed_new_key = cast<KeySansPointerT>(new_key);
// Can destroy *this:
Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key);
if (Config::FollowRAUW) {
typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy);
// I could == Copy.Map->Map.end() if the onRAUW callback already
// removed the old mapping.
if (I != Copy.Map->Map.end()) {
ValueT Target(I->second);
Copy.Map->Map.erase(I); // Definitely destroys *this.
Copy.Map->insert(std::make_pair(typed_new_key, Target));
}
}
if (M)
M->release();
}
};
template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT>
struct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> > {
typedef ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> VH;
typedef DenseMapInfo<KeyT> PointerInfo;
static inline VH getEmptyKey() {
return VH(PointerInfo::getEmptyKey(), NULL);
}
static inline VH getTombstoneKey() {
return VH(PointerInfo::getTombstoneKey(), NULL);
}
static unsigned getHashValue(const VH &Val) {
return PointerInfo::getHashValue(Val.Unwrap());
}
static bool isEqual(const VH &LHS, const VH &RHS) {
return LHS == RHS;
}
static bool isPod() { return false; }
};
template<typename DenseMapT, typename KeyT>
class ValueMapIterator :
public std::iterator<std::forward_iterator_tag,
std::pair<KeyT, typename DenseMapT::mapped_type>,
ptrdiff_t> {
typedef typename DenseMapT::iterator BaseT;
typedef typename DenseMapT::mapped_type ValueT;
BaseT I;
public:
ValueMapIterator() : I() {}
ValueMapIterator(BaseT I) : I(I) {}
BaseT base() const { return I; }
struct ValueTypeProxy {
const KeyT first;
ValueT& second;
ValueTypeProxy *operator->() { return this; }
operator std::pair<KeyT, ValueT>() const {
return std::make_pair(first, second);
}
};
ValueTypeProxy operator*() const {
ValueTypeProxy Result = {I->first.Unwrap(), I->second};
return Result;
}
ValueTypeProxy operator->() const {
return operator*();
}
bool operator==(const ValueMapIterator &RHS) const {
return I == RHS.I;
}
bool operator!=(const ValueMapIterator &RHS) const {
return I != RHS.I;
}
inline ValueMapIterator& operator++() { // Preincrement
++I;
return *this;
}
ValueMapIterator operator++(int) { // Postincrement
ValueMapIterator tmp = *this; ++*this; return tmp;
}
};
template<typename DenseMapT, typename KeyT>
class ValueMapConstIterator :
public std::iterator<std::forward_iterator_tag,
std::pair<KeyT, typename DenseMapT::mapped_type>,
ptrdiff_t> {
typedef typename DenseMapT::const_iterator BaseT;
typedef typename DenseMapT::mapped_type ValueT;
BaseT I;
public:
ValueMapConstIterator() : I() {}
ValueMapConstIterator(BaseT I) : I(I) {}
ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other)
: I(Other.base()) {}
BaseT base() const { return I; }
struct ValueTypeProxy {
const KeyT first;
const ValueT& second;
ValueTypeProxy *operator->() { return this; }
operator std::pair<KeyT, ValueT>() const {
return std::make_pair(first, second);
}
};
ValueTypeProxy operator*() const {
ValueTypeProxy Result = {I->first.Unwrap(), I->second};
return Result;
}
ValueTypeProxy operator->() const {
return operator*();
}
bool operator==(const ValueMapConstIterator &RHS) const {
return I == RHS.I;
}
bool operator!=(const ValueMapConstIterator &RHS) const {
return I != RHS.I;
}
inline ValueMapConstIterator& operator++() { // Preincrement
++I;
return *this;
}
ValueMapConstIterator operator++(int) { // Postincrement
ValueMapConstIterator tmp = *this; ++*this; return tmp;
}
};
} // end namespace llvm
#endif
|