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 { 11471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.count(Wrap(Val)); 11571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 11671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 11771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin iterator find(const KeyT &Val) { 11871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return iterator(Map.find(Wrap(Val))); 11971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 12071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const_iterator find(const KeyT &Val) const { 12171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return const_iterator(Map.find(Wrap(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 { 12771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.lookup(Wrap(Val)); 12871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 12971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 13071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Inserts key,value pair into the map if the key isn't already in the map. 13171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // If the key is already in the map, it returns false and doesn't update the 13271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // value. 13371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 13471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<typename MapT::iterator, bool> map_result= 13571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Map.insert(std::make_pair(Wrap(KV.first), KV.second)); 13671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(iterator(map_result.first), map_result.second); 13771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 13871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 13971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// insert - Range insertion of pairs. 14071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin template<typename InputIt> 14171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin void insert(InputIt I, InputIt E) { 14271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin for (; I != E; ++I) 14371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin insert(*I); 14471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 14571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 14671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 14771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool erase(const KeyT &Val) { 14871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.erase(Wrap(Val)); 14971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 150e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(iterator I) { 15171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.erase(I.base()); 15271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 15371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 15471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin value_type& FindAndConstruct(const KeyT &Key) { 15571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.FindAndConstruct(Wrap(Key)); 15671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 15771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 15871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT &operator[](const KeyT &Key) { 15971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map[Wrap(Key)]; 16071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 16171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 16271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// isPointerIntoBucketsArray - Return true if the specified pointer points 16371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// somewhere into the ValueMap's array of buckets (i.e. either to a key or 16471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// value in the ValueMap). 16571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool isPointerIntoBucketsArray(const void *Ptr) const { 16671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.isPointerIntoBucketsArray(Ptr); 16771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 16871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 16971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 17071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// array. In conjunction with the previous method, this can be used to 17171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin /// determine whether an insertion caused the ValueMap to reallocate. 17271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const void *getPointerIntoBucketsArray() const { 17371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Map.getPointerIntoBucketsArray(); 17471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 17571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 17671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinprivate: 1774ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // Takes a key being looked up in the map and wraps it into a 1784ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // ValueMapCallbackVH, the actual key type of the map. We use a helper 1794ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin // function because ValueMapCVH is constructed with a second parameter. 18071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCVH Wrap(KeyT key) const { 18171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // The only way the resulting CallbackVH could try to modify *this (making 18271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // the const_cast incorrect) is if it gets inserted into the map. But then 18371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // this function must have been called from a non-const method, making the 18471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // const_cast ok. 18571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return ValueMapCVH(key, const_cast<ValueMap*>(this)); 18671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 18771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 18871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 1894ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// This CallbackVH updates its ValueMap when the contained Value changes, 1904ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin// according to the user's preferences expressed through the Config object. 1914e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename Config> 19271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapCallbackVH : public CallbackVH { 1934e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class ValueMap<KeyT, ValueT, Config>; 194fe134fe9e5673d63b4b80392adcc5a3df928475fMike Stump friend struct DenseMapInfo<ValueMapCallbackVH>; 1954e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typedef ValueMap<KeyT, ValueT, Config> ValueMapT; 19671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename llvm::remove_pointer<KeyT>::type KeySansPointerT; 19771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 19871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapT *Map; 19971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH(KeyT Key, ValueMapT *Map) 20171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))), 20271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Map(Map) {} 20371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 20571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); } 20671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 20771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin virtual void deleted() { 20871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Make a copy that won't get changed even when *this is destroyed. 20971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH Copy(*this); 21071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin sys::Mutex *M = Config::getMutex(Copy.Map->Data); 21171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 21271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->acquire(); 2134ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin Config::onDelete(Copy.Map->Data, Copy.Unwrap()); // May destroy *this. 21471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->Map.erase(Copy); // Definitely destroys *this. 21571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 21671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->release(); 21771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 21871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin virtual void allUsesReplacedWith(Value *new_key) { 21971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin assert(isa<KeySansPointerT>(new_key) && 22071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin "Invalid RAUW on key of ValueMap<>"); 22171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Make a copy that won't get changed even when *this is destroyed. 22271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapCallbackVH Copy(*this); 22371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin sys::Mutex *M = Config::getMutex(Copy.Map->Data); 22471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 22571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->acquire(); 22671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 22771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin KeyT typed_new_key = cast<KeySansPointerT>(new_key); 22871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // Can destroy *this: 22971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key); 23071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (Config::FollowRAUW) { 23171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy); 23271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // I could == Copy.Map->Map.end() if the onRAUW callback already 23371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin // removed the old mapping. 23471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (I != Copy.Map->Map.end()) { 23571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT Target(I->second); 23671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->Map.erase(I); // Definitely destroys *this. 23771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin Copy.Map->insert(std::make_pair(typed_new_key, Target)); 23871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 23971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 24071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin if (M) 24171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin M->release(); 24271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 24371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 24471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 2454e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename Config> 2464e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramerstruct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config> > { 2474e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typedef ValueMapCallbackVH<KeyT, ValueT, Config> VH; 24871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef DenseMapInfo<KeyT> PointerInfo; 24971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 25071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static inline VH getEmptyKey() { 25171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return VH(PointerInfo::getEmptyKey(), NULL); 25271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 25371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static inline VH getTombstoneKey() { 25471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return VH(PointerInfo::getTombstoneKey(), NULL); 25571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 25671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static unsigned getHashValue(const VH &Val) { 25771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return PointerInfo::getHashValue(Val.Unwrap()); 25871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 25971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin static bool isEqual(const VH &LHS, const VH &RHS) { 26071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return LHS == RHS; 26171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 26271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 26371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 26471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 26571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 26671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapIterator : 26771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin public std::iterator<std::forward_iterator_tag, 26871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<KeyT, typename DenseMapT::mapped_type>, 26971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ptrdiff_t> { 27071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::iterator BaseT; 27171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::mapped_type ValueT; 27271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT I; 27371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 27471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator() : I() {} 27571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 27671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator(BaseT I) : I(I) {} 27771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 27871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT base() const { return I; } 27971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 28071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin struct ValueTypeProxy { 28171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const KeyT first; 28271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueT& second; 2834ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueTypeProxy *operator->() { return this; } 28471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin operator std::pair<KeyT, ValueT>() const { 28571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(first, second); 28671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 28771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin }; 28871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 28971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator*() const { 29071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 29171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Result; 29271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 29371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 29471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator->() const { 29571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return operator*(); 29671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 29771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 29871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator==(const ValueMapIterator &RHS) const { 29971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I == RHS.I; 30071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 30171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator!=(const ValueMapIterator &RHS) const { 30271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I != RHS.I; 30371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 30471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3054ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline ValueMapIterator& operator++() { // Preincrement 30671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ++I; 30771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return *this; 30871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 3094ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueMapIterator operator++(int) { // Postincrement 31071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapIterator tmp = *this; ++*this; return tmp; 31171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 31271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 31371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 31471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskintemplate<typename DenseMapT, typename KeyT> 31571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinclass ValueMapConstIterator : 31671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin public std::iterator<std::forward_iterator_tag, 31771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin std::pair<KeyT, typename DenseMapT::mapped_type>, 31871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ptrdiff_t> { 31971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::const_iterator BaseT; 32071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin typedef typename DenseMapT::mapped_type ValueT; 32171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT I; 32271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskinpublic: 32371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator() : I() {} 32471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator(BaseT I) : I(I) {} 32571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other) 32671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin : I(Other.base()) {} 32771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 32871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin BaseT base() const { return I; } 32971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 33071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin struct ValueTypeProxy { 33171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const KeyT first; 33271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin const ValueT& second; 3334ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueTypeProxy *operator->() { return this; } 33471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin operator std::pair<KeyT, ValueT>() const { 33571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return std::make_pair(first, second); 33671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 33771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin }; 33871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 33971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator*() const { 34071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy Result = {I->first.Unwrap(), I->second}; 34171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return Result; 34271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 34371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 34471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueTypeProxy operator->() const { 34571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return operator*(); 34671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 34771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 34871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator==(const ValueMapConstIterator &RHS) const { 34971a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I == RHS.I; 35071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 35171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin bool operator!=(const ValueMapConstIterator &RHS) const { 35271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return I != RHS.I; 35371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 35471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 3554ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline ValueMapConstIterator& operator++() { // Preincrement 35671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ++I; 35771a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin return *this; 35871a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 3594ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin ValueMapConstIterator operator++(int) { // Postincrement 36071a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin ValueMapConstIterator tmp = *this; ++*this; return tmp; 36171a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin } 36271a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin}; 36371a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 36471a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin} // end namespace llvm 36571a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin 36671a5c22c2b635ea903c3ae7d2695ca649b38726fJeffrey Yasskin#endif 367