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 384e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename Config> 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. 754e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename Config =ValueMapConfig<KeyT> > 7671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMap { 774e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class ValueMapCallbackVH<KeyT, ValueT, Config>; 784e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typedef ValueMapCallbackVH<KeyT, ValueT, Config> ValueMapCVH; 794e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typedef DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH> > MapT; 8071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename Config::ExtraData ExtraData; 8171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin MapT Map; 8271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ExtraData Data; 833850f5cedad95e6062671d66b08e1a29e7d5e20fDuncan Sands ValueMap(const ValueMap&); // DO NOT IMPLEMENT 84fffe6cf084d91a8c99b710e30f2b9fb23d62b58dDuncan Sands ValueMap& operator=(const ValueMap&); // DO NOT IMPLEMENT 8571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 8671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef KeyT key_type; 8771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef ValueT mapped_type; 8871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef std::pair<KeyT, ValueT> value_type; 8971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 9071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin explicit ValueMap(unsigned NumInitBuckets = 64) 9171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : Map(NumInitBuckets), Data() {} 9271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64) 9371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : Map(NumInitBuckets), Data(Data) {} 9471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 9571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ~ValueMap() {} 9671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 9771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef ValueMapIterator<MapT, KeyT> iterator; 9871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef ValueMapConstIterator<MapT, KeyT> const_iterator; 9971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin inline iterator begin() { return iterator(Map.begin()); } 10071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin inline iterator end() { return iterator(Map.end()); } 10171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin inline const_iterator begin() const { return const_iterator(Map.begin()); } 10271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin inline const_iterator end() const { return const_iterator(Map.end()); } 10371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 10471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool empty() const { return Map.empty(); } 10571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin unsigned size() const { return Map.size(); } 10671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 10771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// Grow the map so that it has at least Size buckets. Does not shrink 10871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin void resize(size_t Size) { Map.resize(Size); } 10971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 11071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin void clear() { Map.clear(); } 11171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 11271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// count - Return true if the specified key is in the map. 11371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool count(const KeyT &Val) const { 11496edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return Map.find_as(Val) != Map.end(); 11571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 11671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 11771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin iterator find(const KeyT &Val) { 11896edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return iterator(Map.find_as(Val)); 11971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 12071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const_iterator find(const KeyT &Val) const { 12196edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return const_iterator(Map.find_as(Val)); 12271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 12371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 12471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// lookup - Return the entry for the specified key, or a default 12571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// constructed value if no such entry exists. 12671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT lookup(const KeyT &Val) const { 12796edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer typename MapT::const_iterator I = Map.find_as(Val); 12896edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return I != Map.end() ? I->second : ValueT(); 12971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 13071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 13171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Inserts key,value pair into the map if the key isn't already in the map. 13271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // If the key is already in the map, it returns false and doesn't update the 13371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // value. 13471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 13571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<typename MapT::iterator, bool> map_result= 13671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Map.insert(std::make_pair(Wrap(KV.first), KV.second)); 13771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(iterator(map_result.first), map_result.second); 13871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 13971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 14071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// insert - Range insertion of pairs. 14171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin template<typename InputIt> 14271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin void insert(InputIt I, InputIt E) { 14371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin for (; I != E; ++I) 14471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin insert(*I); 14571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 14671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 14771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 14871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool erase(const KeyT &Val) { 14996edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer typename MapT::iterator I = Map.find_as(Val); 15096edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer if (I == Map.end()) 15196edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return false; 15296edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer 15396edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer Map.erase(I); 15496edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return true; 15571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 156e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(iterator I) { 15771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.erase(I.base()); 15871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 15971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 16071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin value_type& FindAndConstruct(const KeyT &Key) { 16171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.FindAndConstruct(Wrap(Key)); 16271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 16371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 16471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT &operator[](const KeyT &Key) { 16571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map[Wrap(Key)]; 16671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 16771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 16871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// isPointerIntoBucketsArray - Return true if the specified pointer points 16971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// somewhere into the ValueMap's array of buckets (i.e. either to a key or 17071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// value in the ValueMap). 17171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool isPointerIntoBucketsArray(const void *Ptr) const { 17271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.isPointerIntoBucketsArray(Ptr); 17371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 17471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 17571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 17671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// array. In conjunction with the previous method, this can be used to 17771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// determine whether an insertion caused the ValueMap to reallocate. 17871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const void *getPointerIntoBucketsArray() const { 17971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.getPointerIntoBucketsArray(); 18071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 18171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 18271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinprivate: 1834ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // Takes a key being looked up in the map and wraps it into a 1844ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // ValueMapCallbackVH, the actual key type of the map. We use a helper 1854ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // function because ValueMapCVH is constructed with a second parameter. 18671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCVH Wrap(KeyT key) const { 18771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // The only way the resulting CallbackVH could try to modify *this (making 18871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // the const_cast incorrect) is if it gets inserted into the map. But then 18971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // this function must have been called from a non-const method, making the 19071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // const_cast ok. 19171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return ValueMapCVH(key, const_cast<ValueMap*>(this)); 19271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 19371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 19471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 1954ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// This CallbackVH updates its ValueMap when the contained Value changes, 1964ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// according to the user's preferences expressed through the Config object. 1974e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename Config> 19871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapCallbackVH : public CallbackVH { 1994e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class ValueMap<KeyT, ValueT, Config>; 200fe134fe9e5673d63b4b80392adcc5a3df928475fMike Stump friend struct DenseMapInfo<ValueMapCallbackVH>; 2014e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typedef ValueMap<KeyT, ValueT, Config> ValueMapT; 20271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename llvm::remove_pointer<KeyT>::type KeySansPointerT; 20371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapT *Map; 20571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH(KeyT Key, ValueMapT *Map) 20771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))), 20871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Map(Map) {} 20971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 21071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 21171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); } 21271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 21371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin virtual void deleted() { 21471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Make a copy that won't get changed even when *this is destroyed. 21571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH Copy(*this); 21671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin sys::Mutex *M = Config::getMutex(Copy.Map->Data); 21771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 21871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->acquire(); 2194ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin Config::onDelete(Copy.Map->Data, Copy.Unwrap()); // May destroy *this. 22071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->Map.erase(Copy); // Definitely destroys *this. 22171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 22271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->release(); 22371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 22471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin virtual void allUsesReplacedWith(Value *new_key) { 22571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin assert(isa<KeySansPointerT>(new_key) && 22671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin "Invalid RAUW on key of ValueMap<>"); 22771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Make a copy that won't get changed even when *this is destroyed. 22871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH Copy(*this); 22971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin sys::Mutex *M = Config::getMutex(Copy.Map->Data); 23071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 23171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->acquire(); 23271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 23371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin KeyT typed_new_key = cast<KeySansPointerT>(new_key); 23471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Can destroy *this: 23571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key); 23671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (Config::FollowRAUW) { 23771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy); 23871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // I could == Copy.Map->Map.end() if the onRAUW callback already 23971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // removed the old mapping. 24071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (I != Copy.Map->Map.end()) { 24171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT Target(I->second); 24271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->Map.erase(I); // Definitely destroys *this. 24371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->insert(std::make_pair(typed_new_key, Target)); 24471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 24571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 24671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 24771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->release(); 24871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 24971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 25071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 2514e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename Config> 2524e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramerstruct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config> > { 2534e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typedef ValueMapCallbackVH<KeyT, ValueT, Config> VH; 25471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef DenseMapInfo<KeyT> PointerInfo; 25571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 25671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static inline VH getEmptyKey() { 25771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return VH(PointerInfo::getEmptyKey(), NULL); 25871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 25971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static inline VH getTombstoneKey() { 26071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return VH(PointerInfo::getTombstoneKey(), NULL); 26171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 26271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static unsigned getHashValue(const VH &Val) { 26371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return PointerInfo::getHashValue(Val.Unwrap()); 26471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 26596edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer static unsigned getHashValue(const KeyT &Val) { 26696edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return PointerInfo::getHashValue(Val); 26796edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer } 26871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static bool isEqual(const VH &LHS, const VH &RHS) { 26971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return LHS == RHS; 27071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 27196edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer static bool isEqual(const KeyT &LHS, const VH &RHS) { 2729e7e04823cb472ae8c36ce354365ba76ba1bcb36Benjamin Kramer return LHS == RHS.getValPtr(); 27396edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer } 27471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 27571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 27671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 27771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 27871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapIterator : 27971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin public std::iterator<std::forward_iterator_tag, 28071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<KeyT, typename DenseMapT::mapped_type>, 28171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ptrdiff_t> { 28271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::iterator BaseT; 28371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::mapped_type ValueT; 28471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT I; 28571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 28671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator() : I() {} 28771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 28871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator(BaseT I) : I(I) {} 28971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 29071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT base() const { return I; } 29171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 29271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin struct ValueTypeProxy { 29371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const KeyT first; 29471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT& second; 2954ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueTypeProxy *operator->() { return this; } 29671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin operator std::pair<KeyT, ValueT>() const { 29771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(first, second); 29871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 29971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin }; 30071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 30171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator*() const { 30271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 30371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Result; 30471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 30571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 30671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator->() const { 30771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return operator*(); 30871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 30971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 31071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator==(const ValueMapIterator &RHS) const { 31171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I == RHS.I; 31271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 31371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator!=(const ValueMapIterator &RHS) const { 31471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I != RHS.I; 31571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 31671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3174ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline ValueMapIterator& operator++() { // Preincrement 31871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ++I; 31971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return *this; 32071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 3214ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueMapIterator operator++(int) { // Postincrement 32271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator tmp = *this; ++*this; return tmp; 32371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 32471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 32571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 32671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 32771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapConstIterator : 32871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin public std::iterator<std::forward_iterator_tag, 32971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<KeyT, typename DenseMapT::mapped_type>, 33071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ptrdiff_t> { 33171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::const_iterator BaseT; 33271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::mapped_type ValueT; 33371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT I; 33471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 33571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator() : I() {} 33671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator(BaseT I) : I(I) {} 33771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other) 33871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : I(Other.base()) {} 33971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 34071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT base() const { return I; } 34171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 34271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin struct ValueTypeProxy { 34371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const KeyT first; 34471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const ValueT& second; 3454ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueTypeProxy *operator->() { return this; } 34671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin operator std::pair<KeyT, ValueT>() const { 34771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(first, second); 34871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 34971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin }; 35071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 35171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator*() const { 35271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 35371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Result; 35471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 35571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 35671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator->() const { 35771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return operator*(); 35871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 35971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 36071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator==(const ValueMapConstIterator &RHS) const { 36171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I == RHS.I; 36271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 36371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator!=(const ValueMapConstIterator &RHS) const { 36471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I != RHS.I; 36571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 36671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3674ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline ValueMapConstIterator& operator++() { // Preincrement 36871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ++I; 36971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return *this; 37071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 3714ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueMapConstIterator operator++(int) { // Postincrement 37271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator tmp = *this; ++*this; return tmp; 37371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 37471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 37571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 37671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin} // end namespace llvm 37771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 37871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#endif 379