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