136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===- 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 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef LLVM_IR_VALUEMAP_H 2736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#define LLVM_IR_VALUEMAP_H 2871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 2971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#include "llvm/ADT/DenseMap.h" 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/ValueHandle.h" 31255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Support/Mutex.h" 3271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#include "llvm/Support/type_traits.h" 3371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#include <iterator> 3471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinnamespace llvm { 3671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 374e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename Config> 3871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapCallbackVH; 3971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 4071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 4171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapIterator; 4271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 4371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapConstIterator; 4471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 454ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin/// This class defines the default behavior for configurable aspects of 464ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin/// ValueMap<>. User Configs should inherit from this class to be as compatible 474ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin/// as possible with future versions of ValueMap. 48cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinestemplate<typename KeyT, typename MutexT = sys::Mutex> 4971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinstruct ValueMapConfig { 50cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef MutexT mutex_type; 51cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 5271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// If FollowRAUW is true, the ValueMap will update mappings on RAUW. If it's 5371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// false, the ValueMap will leave the original mapping in place. 5471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin enum { FollowRAUW = true }; 5571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 5671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // All methods will be called with a first argument of type ExtraData. The 5771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // default implementations in this class take a templated first argument so 5871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // that users' subclasses can use any type they want without having to 5971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // override all the defaults. 6071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin struct ExtraData {}; 6171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 6271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin template<typename ExtraDataT> 63dd6f86a28f1ae77ec2a35598f6a7a934dd5d802fEric Christopher static void onRAUW(const ExtraDataT & /*Data*/, KeyT /*Old*/, KeyT /*New*/) {} 6471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin template<typename ExtraDataT> 65dd6f86a28f1ae77ec2a35598f6a7a934dd5d802fEric Christopher static void onDelete(const ExtraDataT &/*Data*/, KeyT /*Old*/) {} 6671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 6771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// Returns a mutex that should be acquired around any changes to the map. 6871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// This is only acquired from the CallbackVH (and held around calls to onRAUW 694ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin /// and onDelete) and not inside other ValueMap methods. NULL means that no 7071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// mutex is necessary. 7171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin template<typename ExtraDataT> 72cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines static mutex_type *getMutex(const ExtraDataT &/*Data*/) { return nullptr; } 7371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 7471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 754ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin/// See the file comment. 764e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename Config =ValueMapConfig<KeyT> > 7771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMap { 784e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class ValueMapCallbackVH<KeyT, ValueT, Config>; 794e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typedef ValueMapCallbackVH<KeyT, ValueT, Config> ValueMapCVH; 804e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typedef DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH> > MapT; 8171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename Config::ExtraData ExtraData; 8271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin MapT Map; 8371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ExtraData Data; 84fc601db2ed899d800ea0a50f7ecf7de2a820cbc1Craig Topper ValueMap(const ValueMap&) LLVM_DELETED_FUNCTION; 85fc601db2ed899d800ea0a50f7ecf7de2a820cbc1Craig Topper ValueMap& operator=(const ValueMap&) LLVM_DELETED_FUNCTION; 8671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 8771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef KeyT key_type; 8871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef ValueT mapped_type; 8971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef std::pair<KeyT, ValueT> value_type; 90cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef unsigned size_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(); } 107cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines size_type 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 114cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// Return 1 if the specified key is in the map, 0 otherwise. 115cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines size_type count(const KeyT &Val) const { 116cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Map.find_as(Val) == Map.end() ? 0 : 1; 11771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 11871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 11971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin iterator find(const KeyT &Val) { 12096edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return iterator(Map.find_as(Val)); 12171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 12271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const_iterator find(const KeyT &Val) const { 12396edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return const_iterator(Map.find_as(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 { 12996edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer typename MapT::const_iterator I = Map.find_as(Val); 13096edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return I != Map.end() ? I->second : ValueT(); 13171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 13271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 13371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Inserts key,value pair into the map if the key isn't already in the map. 13471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // If the key is already in the map, it returns false and doesn't update the 13571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // value. 13671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 13771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<typename MapT::iterator, bool> map_result= 13871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Map.insert(std::make_pair(Wrap(KV.first), KV.second)); 13971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(iterator(map_result.first), map_result.second); 14071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 14171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 14271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// insert - Range insertion of pairs. 14371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin template<typename InputIt> 14471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin void insert(InputIt I, InputIt E) { 14571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin for (; I != E; ++I) 14671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin insert(*I); 14771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 14871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 14971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 15071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool erase(const KeyT &Val) { 15196edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer typename MapT::iterator I = Map.find_as(Val); 15296edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer if (I == Map.end()) 15396edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return false; 15496edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer 15596edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer Map.erase(I); 15696edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return true; 15771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 158e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(iterator I) { 15971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.erase(I.base()); 16071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 16171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 16271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin value_type& FindAndConstruct(const KeyT &Key) { 16371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.FindAndConstruct(Wrap(Key)); 16471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 16571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 16671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT &operator[](const KeyT &Key) { 16771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map[Wrap(Key)]; 16871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 16971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 17071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// isPointerIntoBucketsArray - Return true if the specified pointer points 17171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// somewhere into the ValueMap's array of buckets (i.e. either to a key or 17271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// value in the ValueMap). 17371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool isPointerIntoBucketsArray(const void *Ptr) const { 17471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.isPointerIntoBucketsArray(Ptr); 17571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 17671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 17771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 17871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// array. In conjunction with the previous method, this can be used to 17971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// determine whether an insertion caused the ValueMap to reallocate. 18071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const void *getPointerIntoBucketsArray() const { 18171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.getPointerIntoBucketsArray(); 18271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 18371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 18471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinprivate: 1854ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // Takes a key being looked up in the map and wraps it into a 1864ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // ValueMapCallbackVH, the actual key type of the map. We use a helper 1874ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // function because ValueMapCVH is constructed with a second parameter. 18871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCVH Wrap(KeyT key) const { 18971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // The only way the resulting CallbackVH could try to modify *this (making 19071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // the const_cast incorrect) is if it gets inserted into the map. But then 19171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // this function must have been called from a non-const method, making the 19271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // const_cast ok. 19371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return ValueMapCVH(key, const_cast<ValueMap*>(this)); 19471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 19571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 19671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 1974ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// This CallbackVH updates its ValueMap when the contained Value changes, 1984ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// according to the user's preferences expressed through the Config object. 1994e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename Config> 20071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapCallbackVH : public CallbackVH { 2014e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class ValueMap<KeyT, ValueT, Config>; 202fe134fe9e5673d63b4b80392adcc5a3df928475fMike Stump friend struct DenseMapInfo<ValueMapCallbackVH>; 2034e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typedef ValueMap<KeyT, ValueT, Config> ValueMapT; 20436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef typename std::remove_pointer<KeyT>::type KeySansPointerT; 20571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapT *Map; 20771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH(KeyT Key, ValueMapT *Map) 20971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))), 21071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Map(Map) {} 21171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 21271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 21371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); } 21471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 21536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void deleted() override { 21671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Make a copy that won't get changed even when *this is destroyed. 21771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH Copy(*this); 218cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typename Config::mutex_type *M = Config::getMutex(Copy.Map->Data); 21971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 22071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->acquire(); 2214ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin Config::onDelete(Copy.Map->Data, Copy.Unwrap()); // May destroy *this. 22271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->Map.erase(Copy); // Definitely destroys *this. 22371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 22471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->release(); 22571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 22636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void allUsesReplacedWith(Value *new_key) override { 22771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin assert(isa<KeySansPointerT>(new_key) && 22871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin "Invalid RAUW on key of ValueMap<>"); 22971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Make a copy that won't get changed even when *this is destroyed. 23071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH Copy(*this); 231cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typename Config::mutex_type *M = Config::getMutex(Copy.Map->Data); 23271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 23371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->acquire(); 23471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 23571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin KeyT typed_new_key = cast<KeySansPointerT>(new_key); 23671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Can destroy *this: 23771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key); 23871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (Config::FollowRAUW) { 23971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy); 24071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // I could == Copy.Map->Map.end() if the onRAUW callback already 24171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // removed the old mapping. 24271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (I != Copy.Map->Map.end()) { 24371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT Target(I->second); 24471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->Map.erase(I); // Definitely destroys *this. 24571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->insert(std::make_pair(typed_new_key, Target)); 24671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 24771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 24871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 24971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->release(); 25071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 25171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 25271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 2534e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename Config> 2544e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramerstruct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config> > { 2554e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typedef ValueMapCallbackVH<KeyT, ValueT, Config> VH; 25671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef DenseMapInfo<KeyT> PointerInfo; 25771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 25871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static inline VH getEmptyKey() { 259dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return VH(PointerInfo::getEmptyKey(), nullptr); 26071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 26171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static inline VH getTombstoneKey() { 262dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return VH(PointerInfo::getTombstoneKey(), nullptr); 26371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 26471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static unsigned getHashValue(const VH &Val) { 26571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return PointerInfo::getHashValue(Val.Unwrap()); 26671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 26796edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer static unsigned getHashValue(const KeyT &Val) { 26896edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer return PointerInfo::getHashValue(Val); 26996edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer } 27071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static bool isEqual(const VH &LHS, const VH &RHS) { 27171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return LHS == RHS; 27271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 27396edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer static bool isEqual(const KeyT &LHS, const VH &RHS) { 2749e7e04823cb472ae8c36ce354365ba76ba1bcb36Benjamin Kramer return LHS == RHS.getValPtr(); 27596edb648e2ea10e1662758b791fc7b494fe74f49Benjamin Kramer } 27671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 27771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 27871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 27971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 28071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapIterator : 28171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin public std::iterator<std::forward_iterator_tag, 28271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<KeyT, typename DenseMapT::mapped_type>, 28371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ptrdiff_t> { 28471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::iterator BaseT; 28571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::mapped_type ValueT; 28671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT I; 28771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 28871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator() : I() {} 28971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 29071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator(BaseT I) : I(I) {} 29171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 29271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT base() const { return I; } 29371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 29471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin struct ValueTypeProxy { 29571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const KeyT first; 29671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT& second; 2974ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueTypeProxy *operator->() { return this; } 29871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin operator std::pair<KeyT, ValueT>() const { 29971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(first, second); 30071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 30171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin }; 30271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 30371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator*() const { 30471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 30571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Result; 30671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 30771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 30871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator->() const { 30971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return operator*(); 31071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 31171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 31271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator==(const ValueMapIterator &RHS) const { 31371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I == RHS.I; 31471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 31571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator!=(const ValueMapIterator &RHS) const { 31671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I != RHS.I; 31771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 31871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3194ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline ValueMapIterator& operator++() { // Preincrement 32071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ++I; 32171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return *this; 32271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 3234ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueMapIterator operator++(int) { // Postincrement 32471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator tmp = *this; ++*this; return tmp; 32571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 32671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 32771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 32871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 32971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapConstIterator : 33071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin public std::iterator<std::forward_iterator_tag, 33171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<KeyT, typename DenseMapT::mapped_type>, 33271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ptrdiff_t> { 33371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::const_iterator BaseT; 33471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::mapped_type ValueT; 33571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT I; 33671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 33771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator() : I() {} 33871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator(BaseT I) : I(I) {} 33971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other) 34071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : I(Other.base()) {} 34171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 34271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT base() const { return I; } 34371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 34471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin struct ValueTypeProxy { 34571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const KeyT first; 34671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const ValueT& second; 3474ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueTypeProxy *operator->() { return this; } 34871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin operator std::pair<KeyT, ValueT>() const { 34971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(first, second); 35071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 35171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin }; 35271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 35371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator*() const { 35471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 35571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Result; 35671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 35771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 35871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator->() const { 35971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return operator*(); 36071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 36171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 36271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator==(const ValueMapConstIterator &RHS) const { 36371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I == RHS.I; 36471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 36571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator!=(const ValueMapConstIterator &RHS) const { 36671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I != RHS.I; 36771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 36871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3694ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline ValueMapConstIterator& operator++() { // Preincrement 37071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ++I; 37171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return *this; 37271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 3734ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueMapConstIterator operator++(int) { // Postincrement 37471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator tmp = *this; ++*this; return tmp; 37571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 37671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 37771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 37871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin} // end namespace llvm 37971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 38071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#endif 381