diff options
Diffstat (limited to 'include/llvm/ADT')
| -rw-r--r-- | include/llvm/ADT/APFloat.h | 3 | ||||
| -rw-r--r-- | include/llvm/ADT/DenseMapInfo.h | 4 | ||||
| -rw-r--r-- | include/llvm/ADT/FoldingSet.h | 1 | ||||
| -rw-r--r-- | include/llvm/ADT/StringExtras.h | 21 | ||||
| -rw-r--r-- | include/llvm/ADT/StringRef.h | 52 | ||||
| -rw-r--r-- | include/llvm/ADT/Triple.h | 3 | ||||
| -rw-r--r-- | include/llvm/ADT/ValueMap.h | 365 |
7 files changed, 411 insertions, 38 deletions
diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index 4d7e7ae..30d998f 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -125,6 +125,7 @@ namespace llvm { public: /* We support the following floating point semantics. */ + static const fltSemantics IEEEhalf; static const fltSemantics IEEEsingle; static const fltSemantics IEEEdouble; static const fltSemantics IEEEquad; @@ -321,12 +322,14 @@ namespace llvm { opStatus roundSignificandWithExponent(const integerPart *, unsigned int, int, roundingMode); + APInt convertHalfAPFloatToAPInt() const; APInt convertFloatAPFloatToAPInt() const; APInt convertDoubleAPFloatToAPInt() const; APInt convertQuadrupleAPFloatToAPInt() const; APInt convertF80LongDoubleAPFloatToAPInt() const; APInt convertPPCDoubleDoubleAPFloatToAPInt() const; void initFromAPInt(const APInt& api, bool isIEEE = false); + void initFromHalfAPInt(const APInt& api); void initFromFloatAPInt(const APInt& api); void initFromDoubleAPInt(const APInt& api); void initFromQuadrupleAPInt(const APInt &api); diff --git a/include/llvm/ADT/DenseMapInfo.h b/include/llvm/ADT/DenseMapInfo.h index 52ac5f9..2f241c5 100644 --- a/include/llvm/ADT/DenseMapInfo.h +++ b/include/llvm/ADT/DenseMapInfo.h @@ -76,7 +76,7 @@ template<> struct DenseMapInfo<unsigned long> { static inline unsigned long getEmptyKey() { return ~0UL; } static inline unsigned long getTombstoneKey() { return ~0UL - 1L; } static unsigned getHashValue(const unsigned long& Val) { - return Val * 37UL; + return (unsigned)(Val * 37UL); } static bool isPod() { return true; } static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { @@ -89,7 +89,7 @@ template<> struct DenseMapInfo<unsigned long long> { static inline unsigned long long getEmptyKey() { return ~0ULL; } static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; } static unsigned getHashValue(const unsigned long long& Val) { - return (unsigned)Val * 37ULL; + return (unsigned)(Val * 37ULL); } static bool isPod() { return true; } static bool isEqual(const unsigned long long& LHS, diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h index c62c47d..26090ce 100644 --- a/include/llvm/ADT/FoldingSet.h +++ b/include/llvm/ADT/FoldingSet.h @@ -19,7 +19,6 @@ #include "llvm/Support/DataTypes.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" -#include <iterator> namespace llvm { class APFloat; diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h index 3d1993c..899823d 100644 --- a/include/llvm/ADT/StringExtras.h +++ b/include/llvm/ADT/StringExtras.h @@ -16,6 +16,7 @@ #include "llvm/Support/DataTypes.h" #include "llvm/ADT/APFloat.h" +#include "llvm/ADT/StringRef.h" #include <cctype> #include <cstdio> #include <string> @@ -216,14 +217,18 @@ void SplitString(const std::string &Source, std::vector<std::string> &OutFragments, const char *Delimiters = " \t\n\v\f\r"); -/// UnescapeString - Modify the argument string, turning two character sequences -/// like '\\' 'n' into '\n'. This handles: \e \a \b \f \n \r \t \v \' \\ and -/// \num (where num is a 1-3 byte octal value). -void UnescapeString(std::string &Str); - -/// EscapeString - Modify the argument string, turning '\\' and anything that -/// doesn't satisfy std::isprint into an escape sequence. -void EscapeString(std::string &Str); +/// HashString - Hash funtion for strings. +/// +/// This is the Bernstein hash function. +// +// FIXME: Investigate whether a modified bernstein hash function performs +// better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx +// X*33+c -> X*33^c +static inline unsigned HashString(StringRef Str, unsigned Result = 0) { + for (unsigned i = 0, e = Str.size(); i != e; ++i) + Result = Result * 33 + Str[i]; + return Result; +} } // End llvm namespace diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h index aa7d577..2fa5c66 100644 --- a/include/llvm/ADT/StringRef.h +++ b/include/llvm/ADT/StringRef.h @@ -29,7 +29,7 @@ namespace llvm { typedef const char *iterator; static const size_t npos = ~size_t(0); typedef size_t size_type; - + private: /// The start of the string, in an external buffer. const char *Data; @@ -45,15 +45,15 @@ namespace llvm { /*implicit*/ StringRef() : Data(0), Length(0) {} /// Construct a string ref from a cstring. - /*implicit*/ StringRef(const char *Str) + /*implicit*/ StringRef(const char *Str) : Data(Str) { if (Str) Length = ::strlen(Str); else Length = 0; } - + /// Construct a string ref from a pointer and length. - /*implicit*/ StringRef(const char *data, unsigned length) + /*implicit*/ StringRef(const char *data, size_t length) : Data(data), Length(length) {} /// Construct a string ref from an std::string. - /*implicit*/ StringRef(const std::string &Str) + /*implicit*/ StringRef(const std::string &Str) : Data(Str.c_str()), Length(Str.length()) {} /// @} @@ -83,7 +83,7 @@ namespace llvm { assert(!empty()); return Data[0]; } - + /// back - Get the last character in the string. char back() const { assert(!empty()); @@ -93,7 +93,7 @@ namespace llvm { /// equals - Check for string equality, this is more efficient than /// compare() when the relative ordering of inequal strings isn't needed. bool equals(const StringRef &RHS) const { - return (Length == RHS.Length && + return (Length == RHS.Length && memcmp(Data, RHS.Data, RHS.Length) == 0); } @@ -117,9 +117,9 @@ namespace llvm { /// @name Operator Overloads /// @{ - char operator[](size_t Index) const { + char operator[](size_t Index) const { assert(Index < Length && "Invalid index!"); - return Data[Index]; + return Data[Index]; } /// @} @@ -135,7 +135,7 @@ namespace llvm { /// @{ /// startswith - Check if this string starts with the given \arg Prefix. - bool startswith(const StringRef &Prefix) const { + bool startswith(const StringRef &Prefix) const { return substr(0, Prefix.Length).equals(Prefix); } @@ -164,7 +164,7 @@ namespace llvm { /// \return - The index of the first occurence of \arg Str, or npos if not /// found. size_t find(const StringRef &Str) const; - + /// rfind - Search for the last character \arg C in the string. /// /// \return - The index of the last occurence of \arg C, or npos if not @@ -179,29 +179,29 @@ namespace llvm { } return npos; } - + /// rfind - Search for the last string \arg Str in the string. /// /// \return - The index of the last occurence of \arg Str, or npos if not /// found. size_t rfind(const StringRef &Str) const; - + /// find_first_of - Find the first instance of the specified character or /// return npos if not in string. Same as find. size_type find_first_of(char C) const { return find(C); } - + /// find_first_of - Find the first character from the string 'Chars' in the /// current string or return npos if not in string. size_type find_first_of(StringRef Chars) const; - + /// find_first_not_of - Find the first character in the string that is not /// in the string 'Chars' or return npos if all are in string. Same as find. size_type find_first_not_of(StringRef Chars) const; - + /// @} /// @name Helpful Algorithms /// @{ - + /// count - Return the number of occurrences of \arg C in the string. size_t count(char C) const { size_t Count = 0; @@ -210,11 +210,11 @@ namespace llvm { ++Count; return Count; } - + /// count - Return the number of non-overlapped occurrences of \arg Str in /// the string. size_t count(const StringRef &Str) const; - + /// getAsInteger - Parse the current string as an integer of the specified /// radix. If Radix is specified as zero, this does radix autosensing using /// extended C rules: 0 is octal, 0x is hex, 0b is binary. @@ -229,7 +229,7 @@ namespace llvm { bool getAsInteger(unsigned Radix, unsigned &Result) const; // TODO: Provide overloads for int/unsigned that check for overflow. - + /// @} /// @name Substring Operations /// @{ @@ -308,24 +308,24 @@ namespace llvm { return LHS.equals(RHS); } - inline bool operator!=(const StringRef &LHS, const StringRef &RHS) { + inline bool operator!=(const StringRef &LHS, const StringRef &RHS) { return !(LHS == RHS); } - + inline bool operator<(const StringRef &LHS, const StringRef &RHS) { - return LHS.compare(RHS) == -1; + return LHS.compare(RHS) == -1; } inline bool operator<=(const StringRef &LHS, const StringRef &RHS) { - return LHS.compare(RHS) != 1; + return LHS.compare(RHS) != 1; } inline bool operator>(const StringRef &LHS, const StringRef &RHS) { - return LHS.compare(RHS) == 1; + return LHS.compare(RHS) == 1; } inline bool operator>=(const StringRef &LHS, const StringRef &RHS) { - return LHS.compare(RHS) != -1; + return LHS.compare(RHS) != -1; } /// @} diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h index 89736bc..7fb0014 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -95,7 +95,8 @@ public: NetBSD, OpenBSD, Solaris, - Win32 + Win32, + Haiku }; private: diff --git a/include/llvm/ADT/ValueMap.h b/include/llvm/ADT/ValueMap.h new file mode 100644 index 0000000..14f2100 --- /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 |
