diff options
author | Jeffrey Yasskin <jyasskin@google.com> | 2009-10-22 22:11:22 +0000 |
---|---|---|
committer | Jeffrey Yasskin <jyasskin@google.com> | 2009-10-22 22:11:22 +0000 |
commit | 71a5c22c2b635ea903c3ae7d2695ca649b38726f (patch) | |
tree | 96bc787234b3b3b2b86cf0540889780ae06709a4 /include | |
parent | abc5ac728961cb23b1041a3466fe2eb4521603c3 (diff) | |
download | llvm-71a5c22c2b635ea903c3ae7d2695ca649b38726f.tar.gz llvm-71a5c22c2b635ea903c3ae7d2695ca649b38726f.tar.bz2 llvm-71a5c22c2b635ea903c3ae7d2695ca649b38726f.tar.xz |
Try r84890 again (adding ValueMap<>), now that I've tested the compile on
gcc-4.4.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84902 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include')
-rw-r--r-- | include/llvm/ADT/ValueMap.h | 365 | ||||
-rw-r--r-- | include/llvm/Support/type_traits.h | 9 |
2 files changed, 374 insertions, 0 deletions
diff --git a/include/llvm/ADT/ValueMap.h b/include/llvm/ADT/ValueMap.h new file mode 100644 index 0000000000..14f21001df --- /dev/null +++ b/include/llvm/ADT/ValueMap.h @@ -0,0 +1,365 @@ +//===- llvm/ADT/ValueMap.h - Safe map from Values to data -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the ValueMap class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_VALUEMAP_H +#define LLVM_ADT_VALUEMAP_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/ValueHandle.h" +#include "llvm/Support/type_traits.h" +#include "llvm/System/Mutex.h" + +#include <iterator> + +namespace llvm { + +template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT> +class ValueMapCallbackVH; + +template<typename DenseMapT, typename KeyT> +class ValueMapIterator; +template<typename DenseMapT, typename KeyT> +class ValueMapConstIterator; + +template<typename KeyT> +struct ValueMapConfig { + /// If FollowRAUW is true, the ValueMap will update mappings on RAUW. If it's + /// false, the ValueMap will leave the original mapping in place. + enum { FollowRAUW = true }; + + // All methods will be called with a first argument of type ExtraData. The + // default implementations in this class take a templated first argument so + // that users' subclasses can use any type they want without having to + // override all the defaults. + struct ExtraData {}; + + template<typename ExtraDataT> + static void onRAUW(const ExtraDataT &Data, KeyT Old, KeyT New) {} + template<typename ExtraDataT> + static void onDeleted(const ExtraDataT &Data, KeyT Old) {} + + /// Returns a mutex that should be acquired around any changes to the map. + /// This is only acquired from the CallbackVH (and held around calls to onRAUW + /// and onDeleted) and not inside other ValueMap methods. NULL means that no + /// mutex is necessary. + template<typename ExtraDataT> + static sys::Mutex *getMutex(const ExtraDataT &Data) { return NULL; } +}; + +/// ValueMap maps Value* or any subclass to an arbitrary other +/// type. It provides the DenseMap interface. When the key values are +/// deleted or RAUWed, ValueMap relies on the Config to decide what to +/// do. Config parameters should inherit from ValueMapConfig<KeyT> to +/// get default implementations of all the methods ValueMap uses. +/// +/// By default, when a key is RAUWed from V1 to V2, the old mapping +/// V1->target is removed, and a new mapping V2->target is added. If +/// V2 already existed, its old target is overwritten. When a key is +/// deleted, its mapping is removed. You can override Config to get +/// called back on each event. +template<typename KeyT, typename ValueT, typename Config = ValueMapConfig<KeyT>, + typename ValueInfoT = DenseMapInfo<ValueT> > +class ValueMap { + friend class ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT>; + typedef ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> ValueMapCVH; + typedef DenseMap<ValueMapCVH, ValueT, DenseMapInfo<ValueMapCVH>, + ValueInfoT> MapT; + typedef typename Config::ExtraData ExtraData; + MapT Map; + ExtraData Data; +public: + typedef KeyT key_type; + typedef ValueT mapped_type; + typedef std::pair<KeyT, ValueT> value_type; + + ValueMap(const ValueMap& Other) : Map(Other.Map), Data(Other.Data) {} + + explicit ValueMap(unsigned NumInitBuckets = 64) + : Map(NumInitBuckets), Data() {} + explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64) + : Map(NumInitBuckets), Data(Data) {} + + ~ValueMap() {} + + typedef ValueMapIterator<MapT, KeyT> iterator; + typedef ValueMapConstIterator<MapT, KeyT> const_iterator; + inline iterator begin() { return iterator(Map.begin()); } + inline iterator end() { return iterator(Map.end()); } + inline const_iterator begin() const { return const_iterator(Map.begin()); } + inline const_iterator end() const { return const_iterator(Map.end()); } + + bool empty() const { return Map.empty(); } + unsigned size() const { return Map.size(); } + + /// Grow the map so that it has at least Size buckets. Does not shrink + void resize(size_t Size) { Map.resize(Size); } + + void clear() { Map.clear(); } + + /// count - Return true if the specified key is in the map. + bool count(const KeyT &Val) const { + return Map.count(Wrap(Val)); + } + + iterator find(const KeyT &Val) { + return iterator(Map.find(Wrap(Val))); + } + const_iterator find(const KeyT &Val) const { + return const_iterator(Map.find(Wrap(Val))); + } + + /// lookup - Return the entry for the specified key, or a default + /// constructed value if no such entry exists. + ValueT lookup(const KeyT &Val) const { + return Map.lookup(Wrap(Val)); + } + + // Inserts key,value pair into the map if the key isn't already in the map. + // If the key is already in the map, it returns false and doesn't update the + // value. + std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { + std::pair<typename MapT::iterator, bool> map_result= + Map.insert(std::make_pair(Wrap(KV.first), KV.second)); + return std::make_pair(iterator(map_result.first), map_result.second); + } + + /// insert - Range insertion of pairs. + template<typename InputIt> + void insert(InputIt I, InputIt E) { + for (; I != E; ++I) + insert(*I); + } + + + bool erase(const KeyT &Val) { + return Map.erase(Wrap(Val)); + } + bool erase(iterator I) { + return Map.erase(I.base()); + } + + value_type& FindAndConstruct(const KeyT &Key) { + return Map.FindAndConstruct(Wrap(Key)); + } + + ValueT &operator[](const KeyT &Key) { + return Map[Wrap(Key)]; + } + + ValueMap& operator=(const ValueMap& Other) { + Map = Other.Map; + Data = Other.Data; + return *this; + } + + /// isPointerIntoBucketsArray - Return true if the specified pointer points + /// somewhere into the ValueMap's array of buckets (i.e. either to a key or + /// value in the ValueMap). + bool isPointerIntoBucketsArray(const void *Ptr) const { + return Map.isPointerIntoBucketsArray(Ptr); + } + + /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets + /// array. In conjunction with the previous method, this can be used to + /// determine whether an insertion caused the ValueMap to reallocate. + const void *getPointerIntoBucketsArray() const { + return Map.getPointerIntoBucketsArray(); + } + +private: + ValueMapCVH Wrap(KeyT key) const { + // The only way the resulting CallbackVH could try to modify *this (making + // the const_cast incorrect) is if it gets inserted into the map. But then + // this function must have been called from a non-const method, making the + // const_cast ok. + return ValueMapCVH(key, const_cast<ValueMap*>(this)); + } +}; + +template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT> +class ValueMapCallbackVH : public CallbackVH { + friend class ValueMap<KeyT, ValueT, Config, ValueInfoT>; + friend class DenseMapInfo<ValueMapCallbackVH>; + typedef ValueMap<KeyT, ValueT, Config, ValueInfoT> ValueMapT; + typedef typename llvm::remove_pointer<KeyT>::type KeySansPointerT; + + ValueMapT *Map; + + ValueMapCallbackVH(KeyT Key, ValueMapT *Map) + : CallbackVH(const_cast<Value*>(static_cast<const Value*>(Key))), + Map(Map) {} + +public: + KeyT Unwrap() const { return cast_or_null<KeySansPointerT>(getValPtr()); } + + virtual void deleted() { + // Make a copy that won't get changed even when *this is destroyed. + ValueMapCallbackVH Copy(*this); + sys::Mutex *M = Config::getMutex(Copy.Map->Data); + if (M) + M->acquire(); + Config::onDeleted(Copy.Map->Data, Copy.Unwrap()); // May destroy *this. + Copy.Map->Map.erase(Copy); // Definitely destroys *this. + if (M) + M->release(); + } + virtual void allUsesReplacedWith(Value *new_key) { + assert(isa<KeySansPointerT>(new_key) && + "Invalid RAUW on key of ValueMap<>"); + // Make a copy that won't get changed even when *this is destroyed. + ValueMapCallbackVH Copy(*this); + sys::Mutex *M = Config::getMutex(Copy.Map->Data); + if (M) + M->acquire(); + + KeyT typed_new_key = cast<KeySansPointerT>(new_key); + // Can destroy *this: + Config::onRAUW(Copy.Map->Data, Copy.Unwrap(), typed_new_key); + if (Config::FollowRAUW) { + typename ValueMapT::MapT::iterator I = Copy.Map->Map.find(Copy); + // I could == Copy.Map->Map.end() if the onRAUW callback already + // removed the old mapping. + if (I != Copy.Map->Map.end()) { + ValueT Target(I->second); + Copy.Map->Map.erase(I); // Definitely destroys *this. + Copy.Map->insert(std::make_pair(typed_new_key, Target)); + } + } + if (M) + M->release(); + } +}; + +template<typename KeyT, typename ValueT, typename Config, typename ValueInfoT> +struct DenseMapInfo<ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> > { + typedef ValueMapCallbackVH<KeyT, ValueT, Config, ValueInfoT> VH; + typedef DenseMapInfo<KeyT> PointerInfo; + + static inline VH getEmptyKey() { + return VH(PointerInfo::getEmptyKey(), NULL); + } + static inline VH getTombstoneKey() { + return VH(PointerInfo::getTombstoneKey(), NULL); + } + static unsigned getHashValue(const VH &Val) { + return PointerInfo::getHashValue(Val.Unwrap()); + } + static bool isEqual(const VH &LHS, const VH &RHS) { + return LHS == RHS; + } + static bool isPod() { return false; } +}; + + +template<typename DenseMapT, typename KeyT> +class ValueMapIterator : + public std::iterator<std::forward_iterator_tag, + std::pair<KeyT, typename DenseMapT::mapped_type>, + ptrdiff_t> { + typedef typename DenseMapT::iterator BaseT; + typedef typename DenseMapT::mapped_type ValueT; + BaseT I; +public: + ValueMapIterator() : I() {} + + ValueMapIterator(BaseT I) : I(I) {} + + BaseT base() const { return I; } + + struct ValueTypeProxy { + const KeyT first; + ValueT& second; + ValueTypeProxy *operator->() { return this; } + operator std::pair<KeyT, ValueT>() const { + return std::make_pair(first, second); + } + }; + + ValueTypeProxy operator*() const { + ValueTypeProxy Result = {I->first.Unwrap(), I->second}; + return Result; + } + + ValueTypeProxy operator->() const { + return operator*(); + } + + bool operator==(const ValueMapIterator &RHS) const { + return I == RHS.I; + } + bool operator!=(const ValueMapIterator &RHS) const { + return I != RHS.I; + } + + inline ValueMapIterator& operator++() { // Preincrement + ++I; + return *this; + } + ValueMapIterator operator++(int) { // Postincrement + ValueMapIterator tmp = *this; ++*this; return tmp; + } +}; + +template<typename DenseMapT, typename KeyT> +class ValueMapConstIterator : + public std::iterator<std::forward_iterator_tag, + std::pair<KeyT, typename DenseMapT::mapped_type>, + ptrdiff_t> { + typedef typename DenseMapT::const_iterator BaseT; + typedef typename DenseMapT::mapped_type ValueT; + BaseT I; +public: + ValueMapConstIterator() : I() {} + ValueMapConstIterator(BaseT I) : I(I) {} + ValueMapConstIterator(ValueMapIterator<DenseMapT, KeyT> Other) + : I(Other.base()) {} + + BaseT base() const { return I; } + + struct ValueTypeProxy { + const KeyT first; + const ValueT& second; + ValueTypeProxy *operator->() { return this; } + operator std::pair<KeyT, ValueT>() const { + return std::make_pair(first, second); + } + }; + + ValueTypeProxy operator*() const { + ValueTypeProxy Result = {I->first.Unwrap(), I->second}; + return Result; + } + + ValueTypeProxy operator->() const { + return operator*(); + } + + bool operator==(const ValueMapConstIterator &RHS) const { + return I == RHS.I; + } + bool operator!=(const ValueMapConstIterator &RHS) const { + return I != RHS.I; + } + + inline ValueMapConstIterator& operator++() { // Preincrement + ++I; + return *this; + } + ValueMapConstIterator operator++(int) { // Postincrement + ValueMapConstIterator tmp = *this; ++*this; return tmp; + } +}; + +} // end namespace llvm + +#endif diff --git a/include/llvm/Support/type_traits.h b/include/llvm/Support/type_traits.h index 5f799b850d..cfaae4b841 100644 --- a/include/llvm/Support/type_traits.h +++ b/include/llvm/Support/type_traits.h @@ -87,6 +87,15 @@ struct is_base_of { sizeof(char) == sizeof(dont_use::base_of_helper<Base>((Derived*)0)); }; +// remove_pointer - Metafunction to turn Foo* into Foo. Defined in +// C++0x [meta.trans.ptr]. +template <typename T> struct remove_pointer { typedef T type; }; +template <typename T> struct remove_pointer<T*> { typedef T type; }; +template <typename T> struct remove_pointer<T*const> { typedef T type; }; +template <typename T> struct remove_pointer<T*volatile> { typedef T type; }; +template <typename T> struct remove_pointer<T*const volatile> { + typedef T type; }; + } #endif |