ValueMap.h revision 1f6efa3996dd1929fbc129203ce5009b620e6969
171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin//===- llvm/ADT/ValueMap.h - Safe map from Values to data -------*- C++ -*-===// 271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin// 371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin// The LLVM Compiler Infrastructure 471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin// 571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin// This file is distributed under the University of Illinois Open Source 671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin// License. See LICENSE.TXT for details. 771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin// 871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin//===----------------------------------------------------------------------===// 971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin// 104ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// This file defines the ValueMap class. ValueMap maps Value* or any subclass 114ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// to an arbitrary other type. It provides the DenseMap interface but updates 124ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// itself to remain safe when keys are RAUWed or deleted. By default, when a 134ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// key is RAUWed from V1 to V2, the old mapping V1->target is removed, and a new 144ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// mapping V2->target is added. If V2 already existed, its old target is 154ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// overwritten. When a key is deleted, its mapping is removed. 164ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// 174ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// You can override a ValueMap's Config parameter to control exactly what 184ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// happens on RAUW and destruction and to get called back on each event. It's 194ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// legal to call back into the ValueMap from a Config's callbacks. Config 204ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// parameters should inherit from ValueMapConfig<KeyT> to get default 214ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// implementations of all the methods ValueMap uses. See ValueMapConfig for 224ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// documentation of the functions you can override. 2371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin// 2471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin//===----------------------------------------------------------------------===// 2571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 2671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#ifndef LLVM_ADT_VALUEMAP_H 2771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#define LLVM_ADT_VALUEMAP_H 2871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 2971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#include "llvm/ADT/DenseMap.h" 3071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#include "llvm/Support/ValueHandle.h" 3171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#include "llvm/Support/type_traits.h" 321f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/Mutex.h" 3371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#include <iterator> 3571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinnamespace llvm { 3771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename KeyT, typename ValueT, typename Config, typename ValueInfoT> 3971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapCallbackVH; 4071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 4171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 4271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapIterator; 4371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 4471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapConstIterator; 4571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 464ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin/// This class defines the default behavior for configurable aspects of 474ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin/// ValueMap<>. User Configs should inherit from this class to be as compatible 484ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin/// as possible with future versions of ValueMap. 4971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename KeyT> 5071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinstruct ValueMapConfig { 5171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// If FollowRAUW is true, the ValueMap will update mappings on RAUW. If it's 5271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// false, the ValueMap will leave the original mapping in place. 5371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin enum { FollowRAUW = true }; 5471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 5571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // All methods will be called with a first argument of type ExtraData. The 5671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // default implementations in this class take a templated first argument so 5771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // that users' subclasses can use any type they want without having to 5871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // override all the defaults. 5971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin struct ExtraData {}; 6071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 6171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin template<typename ExtraDataT> 62dd6f86a28f1ae77ec2a35598f6a7a934dd5d802fEric Christopher static void onRAUW(const ExtraDataT & /*Data*/, KeyT /*Old*/, KeyT /*New*/) {} 6371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin template<typename ExtraDataT> 64dd6f86a28f1ae77ec2a35598f6a7a934dd5d802fEric Christopher static void onDelete(const ExtraDataT &/*Data*/, KeyT /*Old*/) {} 6571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 6671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// Returns a mutex that should be acquired around any changes to the map. 6771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// This is only acquired from the CallbackVH (and held around calls to onRAUW 684ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin /// and onDelete) and not inside other ValueMap methods. NULL means that no 6971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// mutex is necessary. 7071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin template<typename ExtraDataT> 71dd6f86a28f1ae77ec2a35598f6a7a934dd5d802fEric Christopher static sys::Mutex *getMutex(const ExtraDataT &/*Data*/) { return NULL; } 7271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 7371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 744ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin/// See the file comment. 7571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename KeyT, typename ValueT, typename Config = ValueMapConfig<KeyT>, 7671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typename ValueInfoT = DenseMapInfo<ValueT> > 7771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMap { 7871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin friend class ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT>; 7971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> ValueMapCVH; 8071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH>, 8171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueInfoT> MapT; 8271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename Config::ExtraData ExtraData; 8371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin MapT Map; 8471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ExtraData Data; 853850f5cedad95e6062671d66b08e1a29e7d5e20fDuncan Sands ValueMap(const ValueMap&); // DO NOT IMPLEMENT 86fffe6cf084d91a8c99b710e30f2b9fb23d62b58dDuncan Sands ValueMap& operator=(const ValueMap&); // DO NOT IMPLEMENT 8771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 8871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef KeyT key_type; 8971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef ValueT mapped_type; 9071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef std::pair<KeyT, ValueT> value_type; 9171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 9271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin explicit ValueMap(unsigned NumInitBuckets = 64) 9371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : Map(NumInitBuckets), Data() {} 9471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64) 9571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : Map(NumInitBuckets), Data(Data) {} 9671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 9771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ~ValueMap() {} 9871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 9971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef ValueMapIterator<MapT, KeyT> iterator; 10071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef ValueMapConstIterator<MapT, KeyT> const_iterator; 10171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin inline iterator begin() { return iterator(Map.begin()); } 10271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin inline iterator end() { return iterator(Map.end()); } 10371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin inline const_iterator begin() const { return const_iterator(Map.begin()); } 10471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin inline const_iterator end() const { return const_iterator(Map.end()); } 10571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 10671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool empty() const { return Map.empty(); } 10771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin unsigned size() const { return Map.size(); } 10871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 10971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// Grow the map so that it has at least Size buckets. Does not shrink 11071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin void resize(size_t Size) { Map.resize(Size); } 11171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 11271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin void clear() { Map.clear(); } 11371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 11471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// count - Return true if the specified key is in the map. 11571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool count(const KeyT &Val) const { 11671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.count(Wrap(Val)); 11771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 11871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 11971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin iterator find(const KeyT &Val) { 12071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return iterator(Map.find(Wrap(Val))); 12171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 12271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const_iterator find(const KeyT &Val) const { 12371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return const_iterator(Map.find(Wrap(Val))); 12471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 12571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 12671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// lookup - Return the entry for the specified key, or a default 12771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// constructed value if no such entry exists. 12871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT lookup(const KeyT &Val) const { 12971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.lookup(Wrap(Val)); 13071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 13171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 13271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Inserts key,value pair into the map if the key isn't already in the map. 13371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // If the key is already in the map, it returns false and doesn't update the 13471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // value. 13571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 13671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<typename MapT::iterator, bool> map_result= 13771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Map.insert(std::make_pair(Wrap(KV.first), KV.second)); 13871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(iterator(map_result.first), map_result.second); 13971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 14071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 14171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// insert - Range insertion of pairs. 14271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin template<typename InputIt> 14371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin void insert(InputIt I, InputIt E) { 14471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin for (; I != E; ++I) 14571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin insert(*I); 14671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 14771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 14871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 14971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool erase(const KeyT &Val) { 15071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.erase(Wrap(Val)); 15171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 152e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(iterator I) { 15371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.erase(I.base()); 15471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 15571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 15671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin value_type& FindAndConstruct(const KeyT &Key) { 15771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.FindAndConstruct(Wrap(Key)); 15871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 15971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 16071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT &operator[](const KeyT &Key) { 16171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map[Wrap(Key)]; 16271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 16371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 16471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// isPointerIntoBucketsArray - Return true if the specified pointer points 16571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// somewhere into the ValueMap's array of buckets (i.e. either to a key or 16671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// value in the ValueMap). 16771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool isPointerIntoBucketsArray(const void *Ptr) const { 16871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.isPointerIntoBucketsArray(Ptr); 16971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 17071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 17171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 17271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// array. In conjunction with the previous method, this can be used to 17371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// determine whether an insertion caused the ValueMap to reallocate. 17471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const void *getPointerIntoBucketsArray() const { 17571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.getPointerIntoBucketsArray(); 17671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 17771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 17871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinprivate: 1794ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // Takes a key being looked up in the map and wraps it into a 1804ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // ValueMapCallbackVH, the actual key type of the map. We use a helper 1814ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // function because ValueMapCVH is constructed with a second parameter. 18271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCVH Wrap(KeyT key) const { 18371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // The only way the resulting CallbackVH could try to modify *this (making 18471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // the const_cast incorrect) is if it gets inserted into the map. But then 18571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // this function must have been called from a non-const method, making the 18671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // const_cast ok. 18771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return ValueMapCVH(key, const_cast<ValueMap*>(this)); 18871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 18971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 19071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 1914ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// This CallbackVH updates its ValueMap when the contained Value changes, 1924ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// according to the user's preferences expressed through the Config object. 19371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename KeyT, typename ValueT, typename Config, typename ValueInfoT> 19471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapCallbackVH : public CallbackVH { 19571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin friend class ValueMap<KeyT, ValueT, Config, ValueInfoT>; 196fe134fe9e5673d63b4b80392adcc5a3df928475fMike Stump friend struct DenseMapInfo<ValueMapCallbackVH>; 19771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef ValueMap<KeyT, ValueT, Config, ValueInfoT> ValueMapT; 19871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename llvm::remove_pointer<KeyT>::type KeySansPointerT; 19971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapT *Map; 20171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH(KeyT Key, ValueMapT *Map) 20371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))), 20471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Map(Map) {} 20571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 20771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); } 20871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin virtual void deleted() { 21071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Make a copy that won't get changed even when *this is destroyed. 21171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH Copy(*this); 21271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin sys::Mutex *M = Config::getMutex(Copy.Map->Data); 21371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 21471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->acquire(); 2154ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin Config::onDelete(Copy.Map->Data, Copy.Unwrap()); // May destroy *this. 21671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->Map.erase(Copy); // Definitely destroys *this. 21771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 21871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->release(); 21971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 22071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin virtual void allUsesReplacedWith(Value *new_key) { 22171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin assert(isa<KeySansPointerT>(new_key) && 22271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin "Invalid RAUW on key of ValueMap<>"); 22371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Make a copy that won't get changed even when *this is destroyed. 22471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH Copy(*this); 22571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin sys::Mutex *M = Config::getMutex(Copy.Map->Data); 22671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 22771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->acquire(); 22871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 22971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin KeyT typed_new_key = cast<KeySansPointerT>(new_key); 23071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Can destroy *this: 23171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key); 23271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (Config::FollowRAUW) { 23371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy); 23471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // I could == Copy.Map->Map.end() if the onRAUW callback already 23571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // removed the old mapping. 23671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (I != Copy.Map->Map.end()) { 23771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT Target(I->second); 23871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->Map.erase(I); // Definitely destroys *this. 23971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->insert(std::make_pair(typed_new_key, Target)); 24071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 24171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 24271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 24371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->release(); 24471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 24571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 24671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 24771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename KeyT, typename ValueT, typename Config, typename ValueInfoT> 24871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinstruct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> > { 24971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> VH; 25071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef DenseMapInfo<KeyT> PointerInfo; 25171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 25271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static inline VH getEmptyKey() { 25371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return VH(PointerInfo::getEmptyKey(), NULL); 25471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 25571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static inline VH getTombstoneKey() { 25671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return VH(PointerInfo::getTombstoneKey(), NULL); 25771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 25871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static unsigned getHashValue(const VH &Val) { 25971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return PointerInfo::getHashValue(Val.Unwrap()); 26071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 26171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static bool isEqual(const VH &LHS, const VH &RHS) { 26271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return LHS == RHS; 26371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 26471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 26571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 26671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 26771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 26871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapIterator : 26971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin public std::iterator<std::forward_iterator_tag, 27071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<KeyT, typename DenseMapT::mapped_type>, 27171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ptrdiff_t> { 27271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::iterator BaseT; 27371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::mapped_type ValueT; 27471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT I; 27571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 27671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator() : I() {} 27771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 27871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator(BaseT I) : I(I) {} 27971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 28071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT base() const { return I; } 28171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 28271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin struct ValueTypeProxy { 28371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const KeyT first; 28471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT& second; 2854ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueTypeProxy *operator->() { return this; } 28671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin operator std::pair<KeyT, ValueT>() const { 28771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(first, second); 28871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 28971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin }; 29071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 29171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator*() const { 29271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 29371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Result; 29471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 29571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 29671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator->() const { 29771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return operator*(); 29871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 29971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 30071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator==(const ValueMapIterator &RHS) const { 30171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I == RHS.I; 30271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 30371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator!=(const ValueMapIterator &RHS) const { 30471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I != RHS.I; 30571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 30671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3074ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline ValueMapIterator& operator++() { // Preincrement 30871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ++I; 30971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return *this; 31071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 3114ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueMapIterator operator++(int) { // Postincrement 31271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator tmp = *this; ++*this; return tmp; 31371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 31471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 31571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 31671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 31771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapConstIterator : 31871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin public std::iterator<std::forward_iterator_tag, 31971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<KeyT, typename DenseMapT::mapped_type>, 32071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ptrdiff_t> { 32171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::const_iterator BaseT; 32271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::mapped_type ValueT; 32371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT I; 32471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 32571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator() : I() {} 32671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator(BaseT I) : I(I) {} 32771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other) 32871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : I(Other.base()) {} 32971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 33071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT base() const { return I; } 33171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 33271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin struct ValueTypeProxy { 33371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const KeyT first; 33471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const ValueT& second; 3354ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueTypeProxy *operator->() { return this; } 33671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin operator std::pair<KeyT, ValueT>() const { 33771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(first, second); 33871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 33971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin }; 34071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 34171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator*() const { 34271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 34371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Result; 34471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 34571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 34671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator->() const { 34771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return operator*(); 34871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 34971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 35071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator==(const ValueMapConstIterator &RHS) const { 35171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I == RHS.I; 35271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 35371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator!=(const ValueMapConstIterator &RHS) const { 35471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I != RHS.I; 35571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 35671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3574ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline ValueMapConstIterator& operator++() { // Preincrement 35871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ++I; 35971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return *this; 36071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 3614ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueMapConstIterator operator++(int) { // Postincrement 36271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator tmp = *this; ++*this; return tmp; 36371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 36471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 36571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 36671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin} // end namespace llvm 36771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 36871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#endif 369