1 //===- llvm/ADT/ValueMap.h - Safe map from Values to data -------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the ValueMap class.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_VALUEMAP_H
15 #define LLVM_ADT_VALUEMAP_H
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/Support/ValueHandle.h"
19 #include "llvm/Support/type_traits.h"
20 #include "llvm/System/Mutex.h"
26 template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT>
27 class ValueMapCallbackVH;
29 template<typename DenseMapT, typename KeyT>
30 class ValueMapIterator;
31 template<typename DenseMapT, typename KeyT>
32 class ValueMapConstIterator;
34 template<typename KeyT>
35 struct ValueMapConfig {
36 /// If FollowRAUW is true, the ValueMap will update mappings on RAUW. If it's
37 /// false, the ValueMap will leave the original mapping in place.
38 enum { FollowRAUW = true };
40 // All methods will be called with a first argument of type ExtraData. The
41 // default implementations in this class take a templated first argument so
42 // that users' subclasses can use any type they want without having to
43 // override all the defaults.
46 template<typename ExtraDataT>
47 static void onRAUW(const ExtraDataT &Data, KeyT Old, KeyT New) {}
48 template<typename ExtraDataT>
49 static void onDeleted(const ExtraDataT &Data, KeyT Old) {}
51 /// Returns a mutex that should be acquired around any changes to the map.
52 /// This is only acquired from the CallbackVH (and held around calls to onRAUW
53 /// and onDeleted) and not inside other ValueMap methods. NULL means that no
54 /// mutex is necessary.
55 template<typename ExtraDataT>
56 static sys::Mutex *getMutex(const ExtraDataT &Data) { return NULL; }
59 /// ValueMap maps Value* or any subclass to an arbitrary other
60 /// type. It provides the DenseMap interface. When the key values are
61 /// deleted or RAUWed, ValueMap relies on the Config to decide what to
62 /// do. Config parameters should inherit from ValueMapConfig<KeyT> to
63 /// get default implementations of all the methods ValueMap uses.
65 /// By default, when a key is RAUWed from V1 to V2, the old mapping
66 /// V1->target is removed, and a new mapping V2->target is added. If
67 /// V2 already existed, its old target is overwritten. When a key is
68 /// deleted, its mapping is removed. You can override Config to get
69 /// called back on each event.
70 template<typename KeyT, typename ValueT, typename Config = ValueMapConfig<KeyT>,
71 typename ValueInfoT = DenseMapInfo<ValueT> >
73 friend class ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT>;
74 typedef ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> ValueMapCVH;
75 typedef DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH>,
77 typedef typename Config::ExtraData ExtraData;
81 typedef KeyT key_type;
82 typedef ValueT mapped_type;
83 typedef std::pair<KeyT, ValueT> value_type;
85 ValueMap(const ValueMap& Other) : Map(Other.Map), Data(Other.Data) {}
87 explicit ValueMap(unsigned NumInitBuckets = 64)
88 : Map(NumInitBuckets), Data() {}
89 explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64)
90 : Map(NumInitBuckets), Data(Data) {}
94 typedef ValueMapIterator<MapT, KeyT> iterator;
95 typedef ValueMapConstIterator<MapT, KeyT> const_iterator;
96 inline iterator begin() { return iterator(Map.begin()); }
97 inline iterator end() { return iterator(Map.end()); }
98 inline const_iterator begin() const { return const_iterator(Map.begin()); }
99 inline const_iterator end() const { return const_iterator(Map.end()); }
101 bool empty() const { return Map.empty(); }
102 unsigned size() const { return Map.size(); }
104 /// Grow the map so that it has at least Size buckets. Does not shrink
105 void resize(size_t Size) { Map.resize(Size); }
107 void clear() { Map.clear(); }
109 /// count - Return true if the specified key is in the map.
110 bool count(const KeyT &Val) const {
111 return Map.count(Wrap(Val));
114 iterator find(const KeyT &Val) {
115 return iterator(Map.find(Wrap(Val)));
117 const_iterator find(const KeyT &Val) const {
118 return const_iterator(Map.find(Wrap(Val)));
121 /// lookup - Return the entry for the specified key, or a default
122 /// constructed value if no such entry exists.
123 ValueT lookup(const KeyT &Val) const {
124 return Map.lookup(Wrap(Val));
127 // Inserts key,value pair into the map if the key isn't already in the map.
128 // If the key is already in the map, it returns false and doesn't update the
130 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
131 std::pair<typename MapT::iterator, bool> map_result=
132 Map.insert(std::make_pair(Wrap(KV.first), KV.second));
133 return std::make_pair(iterator(map_result.first), map_result.second);
136 /// insert - Range insertion of pairs.
137 template<typename InputIt>
138 void insert(InputIt I, InputIt E) {
144 bool erase(const KeyT &Val) {
145 return Map.erase(Wrap(Val));
147 bool erase(iterator I) {
148 return Map.erase(I.base());
151 value_type& FindAndConstruct(const KeyT &Key) {
152 return Map.FindAndConstruct(Wrap(Key));
155 ValueT &operator[](const KeyT &Key) {
156 return Map[Wrap(Key)];
159 ValueMap& operator=(const ValueMap& Other) {
165 /// isPointerIntoBucketsArray - Return true if the specified pointer points
166 /// somewhere into the ValueMap's array of buckets (i.e. either to a key or
167 /// value in the ValueMap).
168 bool isPointerIntoBucketsArray(const void *Ptr) const {
169 return Map.isPointerIntoBucketsArray(Ptr);
172 /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
173 /// array. In conjunction with the previous method, this can be used to
174 /// determine whether an insertion caused the ValueMap to reallocate.
175 const void *getPointerIntoBucketsArray() const {
176 return Map.getPointerIntoBucketsArray();
180 ValueMapCVH Wrap(KeyT key) const {
181 // The only way the resulting CallbackVH could try to modify *this (making
182 // the const_cast incorrect) is if it gets inserted into the map. But then
183 // this function must have been called from a non-const method, making the
185 return ValueMapCVH(key, const_cast<ValueMap*>(this));
189 template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT>
190 class ValueMapCallbackVH : public CallbackVH {
191 friend class ValueMap<KeyT, ValueT, Config, ValueInfoT>;
192 friend class DenseMapInfo<ValueMapCallbackVH>;
193 typedef ValueMap<KeyT, ValueT, Config, ValueInfoT> ValueMapT;
194 typedef typename llvm::remove_pointer<KeyT>::type KeySansPointerT;
198 ValueMapCallbackVH(KeyT Key, ValueMapT *Map)
199 : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))),
203 KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); }
205 virtual void deleted() {
206 // Make a copy that won't get changed even when *this is destroyed.
207 ValueMapCallbackVH Copy(*this);
208 sys::Mutex *M = Config::getMutex(Copy.Map->Data);
211 Config::onDeleted(Copy.Map->Data, Copy.Unwrap()); // May destroy *this.
212 Copy.Map->Map.erase(Copy); // Definitely destroys *this.
216 virtual void allUsesReplacedWith(Value *new_key) {
217 assert(isa<KeySansPointerT>(new_key) &&
218 "Invalid RAUW on key of ValueMap<>");
219 // Make a copy that won't get changed even when *this is destroyed.
220 ValueMapCallbackVH Copy(*this);
221 sys::Mutex *M = Config::getMutex(Copy.Map->Data);
225 KeyT typed_new_key = cast<KeySansPointerT>(new_key);
226 // Can destroy *this:
227 Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key);
228 if (Config::FollowRAUW) {
229 typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy);
230 // I could == Copy.Map->Map.end() if the onRAUW callback already
231 // removed the old mapping.
232 if (I != Copy.Map->Map.end()) {
233 ValueT Target(I->second);
234 Copy.Map->Map.erase(I); // Definitely destroys *this.
235 Copy.Map->insert(std::make_pair(typed_new_key, Target));
243 template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT>
244 struct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> > {
245 typedef ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> VH;
246 typedef DenseMapInfo<KeyT> PointerInfo;
248 static inline VH getEmptyKey() {
249 return VH(PointerInfo::getEmptyKey(), NULL);
251 static inline VH getTombstoneKey() {
252 return VH(PointerInfo::getTombstoneKey(), NULL);
254 static unsigned getHashValue(const VH &Val) {
255 return PointerInfo::getHashValue(Val.Unwrap());
257 static bool isEqual(const VH &LHS, const VH &RHS) {
260 static bool isPod() { return false; }
264 template<typename DenseMapT, typename KeyT>
265 class ValueMapIterator :
266 public std::iterator<std::forward_iterator_tag,
267 std::pair<KeyT, typename DenseMapT::mapped_type>,
269 typedef typename DenseMapT::iterator BaseT;
270 typedef typename DenseMapT::mapped_type ValueT;
273 ValueMapIterator() : I() {}
275 ValueMapIterator(BaseT I) : I(I) {}
277 BaseT base() const { return I; }
279 struct ValueTypeProxy {
282 ValueTypeProxy *operator->() { return this; }
283 operator std::pair<KeyT, ValueT>() const {
284 return std::make_pair(first, second);
288 ValueTypeProxy operator*() const {
289 ValueTypeProxy Result = {I->first.Unwrap(), I->second};
293 ValueTypeProxy operator->() const {
297 bool operator==(const ValueMapIterator &RHS) const {
300 bool operator!=(const ValueMapIterator &RHS) const {
304 inline ValueMapIterator& operator++() { // Preincrement
308 ValueMapIterator operator++(int) { // Postincrement
309 ValueMapIterator tmp = *this; ++*this; return tmp;
313 template<typename DenseMapT, typename KeyT>
314 class ValueMapConstIterator :
315 public std::iterator<std::forward_iterator_tag,
316 std::pair<KeyT, typename DenseMapT::mapped_type>,
318 typedef typename DenseMapT::const_iterator BaseT;
319 typedef typename DenseMapT::mapped_type ValueT;
322 ValueMapConstIterator() : I() {}
323 ValueMapConstIterator(BaseT I) : I(I) {}
324 ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other)
327 BaseT base() const { return I; }
329 struct ValueTypeProxy {
331 const ValueT& second;
332 ValueTypeProxy *operator->() { return this; }
333 operator std::pair<KeyT, ValueT>() const {
334 return std::make_pair(first, second);
338 ValueTypeProxy operator*() const {
339 ValueTypeProxy Result = {I->first.Unwrap(), I->second};
343 ValueTypeProxy operator->() const {
347 bool operator==(const ValueMapConstIterator &RHS) const {
350 bool operator!=(const ValueMapConstIterator &RHS) const {
354 inline ValueMapConstIterator& operator++() { // Preincrement
358 ValueMapConstIterator operator++(int) { // Postincrement
359 ValueMapConstIterator tmp = *this; ++*this; return tmp;
363 } // end namespace llvm