diff options
Diffstat (limited to 'include/llvm/ADT')
35 files changed, 751 insertions, 581 deletions
diff --git a/include/llvm/ADT/APFloat.h b/include/llvm/ADT/APFloat.h index acfefe9d89..50f1463d7e 100644 --- a/include/llvm/ADT/APFloat.h +++ b/include/llvm/ADT/APFloat.h @@ -236,19 +236,19 @@ public: APInt fill(64, type); return getQNaN(Sem, Negative, &fill); } else { - return getQNaN(Sem, Negative, 0); + return getQNaN(Sem, Negative, nullptr); } } /// Factory for QNaN values. static APFloat getQNaN(const fltSemantics &Sem, bool Negative = false, - const APInt *payload = 0) { + const APInt *payload = nullptr) { return makeNaN(Sem, false, Negative, payload); } /// Factory for SNaN values. static APFloat getSNaN(const fltSemantics &Sem, bool Negative = false, - const APInt *payload = 0) { + const APInt *payload = nullptr) { return makeNaN(Sem, true, Negative, payload); } @@ -500,7 +500,8 @@ private: void makeLargest(bool Neg = false); void makeSmallest(bool Neg = false); - void makeNaN(bool SNaN = false, bool Neg = false, const APInt *fill = 0); + void makeNaN(bool SNaN = false, bool Neg = false, + const APInt *fill = nullptr); static APFloat makeNaN(const fltSemantics &Sem, bool SNaN, bool Negative, const APInt *fill); void makeInf(bool Neg = false); diff --git a/include/llvm/ADT/ArrayRef.h b/include/llvm/ADT/ArrayRef.h index fcf280d445..1b64fee9a5 100644 --- a/include/llvm/ADT/ArrayRef.h +++ b/include/llvm/ADT/ArrayRef.h @@ -12,7 +12,6 @@ #include "llvm/ADT/None.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/Support/Allocator.h" #include <vector> namespace llvm { @@ -49,10 +48,10 @@ namespace llvm { /// @{ /// Construct an empty ArrayRef. - /*implicit*/ ArrayRef() : Data(0), Length(0) {} + /*implicit*/ ArrayRef() : Data(nullptr), Length(0) {} /// Construct an empty ArrayRef from None. - /*implicit*/ ArrayRef(NoneType) : Data(0), Length(0) {} + /*implicit*/ ArrayRef(NoneType) : Data(nullptr), Length(0) {} /// Construct an ArrayRef from a single element. /*implicit*/ ArrayRef(const T &OneElt) @@ -121,9 +120,9 @@ namespace llvm { return Data[Length-1]; } - // copy - Allocate copy in BumpPtrAllocator and return ArrayRef<T> to it. - ArrayRef<T> copy(BumpPtrAllocator &Allocator) { - T *Buff = Allocator.Allocate<T>(Length); + // copy - Allocate copy in Allocator and return ArrayRef<T> to it. + template <typename Allocator> ArrayRef<T> copy(Allocator &A) { + T *Buff = A.template Allocate<T>(Length); std::copy(begin(), end(), Buff); return ArrayRef<T>(Buff, Length); } @@ -132,10 +131,7 @@ namespace llvm { bool equals(ArrayRef RHS) const { if (Length != RHS.Length) return false; - for (size_type i = 0; i != Length; i++) - if (Data[i] != RHS.Data[i]) - return false; - return true; + return std::equal(begin(), end(), RHS.begin()); } /// slice(n) - Chop off the first N elements of the array. @@ -221,7 +217,7 @@ namespace llvm { /// Construct an MutableArrayRef from a C array. template <size_t N> - /*implicit*/ MutableArrayRef(T (&Arr)[N]) + /*implicit*/ LLVM_CONSTEXPR MutableArrayRef(T (&Arr)[N]) : ArrayRef<T>(Arr) {} T *data() const { return const_cast<T*>(ArrayRef<T>::data()); } diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index b53182021e..da2b3ad7e7 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -72,7 +72,7 @@ public: /// BitVector default ctor - Creates an empty bitvector. BitVector() : Size(0), Capacity(0) { - Bits = 0; + Bits = nullptr; } /// BitVector ctor - Creates a bitvector of specified number of bits. All @@ -88,7 +88,7 @@ public: /// BitVector copy ctor. BitVector(const BitVector &RHS) : Size(RHS.size()) { if (Size == 0) { - Bits = 0; + Bits = nullptr; Capacity = 0; return; } @@ -100,7 +100,7 @@ public: BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity) { - RHS.Bits = 0; + RHS.Bits = nullptr; } ~BitVector() { @@ -467,7 +467,7 @@ public: Size = RHS.Size; Capacity = RHS.Capacity; - RHS.Bits = 0; + RHS.Bits = nullptr; return *this; } diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 037989f49d..826913289e 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -461,12 +461,12 @@ private: const unsigned NumBuckets = getNumBuckets(); if (NumBuckets == 0) { - FoundBucket = 0; + FoundBucket = nullptr; return false; } // FoundTombstone - Keep track of whether we find a tombstone while probing. - const BucketT *FoundTombstone = 0; + const BucketT *FoundTombstone = nullptr; const KeyT EmptyKey = getEmptyKey(); const KeyT TombstoneKey = getTombstoneKey(); assert(!KeyInfoT::isEqual(Val, EmptyKey) && @@ -665,7 +665,7 @@ private: bool allocateBuckets(unsigned Num) { NumBuckets = Num; if (NumBuckets == 0) { - Buckets = 0; + Buckets = nullptr; return false; } @@ -985,7 +985,7 @@ public: private: pointer Ptr, End; public: - DenseMapIterator() : Ptr(0), End(0) {} + DenseMapIterator() : Ptr(nullptr), End(nullptr) {} DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) : Ptr(Pos), End(E) { diff --git a/include/llvm/ADT/DepthFirstIterator.h b/include/llvm/ADT/DepthFirstIterator.h index 644544253a..dfba43f3ac 100644 --- a/include/llvm/ADT/DepthFirstIterator.h +++ b/include/llvm/ADT/DepthFirstIterator.h @@ -33,6 +33,7 @@ #ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H #define LLVM_ADT_DEPTHFIRSTITERATOR_H +#include "llvm/ADT/iterator_range.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallPtrSet.h" @@ -207,6 +208,12 @@ df_iterator<T> df_end(const T& G) { return df_iterator<T>::end(G); } +// Provide an accessor method to use them in range-based patterns. +template <class T> +iterator_range<df_iterator<T>> depth_first(const T& G) { + return iterator_range<df_iterator<T>>(df_begin(G), df_end(G)); +} + // Provide global definitions of external depth first iterators... template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> > struct df_ext_iterator : public df_iterator<T, SetTy, true> { @@ -244,6 +251,12 @@ idf_iterator<T> idf_end(const T& G){ return idf_iterator<T>::end(Inverse<T>(G)); } +// Provide an accessor method to use them in range-based patterns. +template <class T> +iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) { + return iterator_range<idf_iterator<T>>(idf_begin(G), idf_end(G)); +} + // Provide global definitions of external inverse depth first iterators... template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> > struct idf_ext_iterator : public idf_iterator<T, SetTy, true> { diff --git a/include/llvm/ADT/EquivalenceClasses.h b/include/llvm/ADT/EquivalenceClasses.h index 2256ee7ae4..e0396c7e79 100644 --- a/include/llvm/ADT/EquivalenceClasses.h +++ b/include/llvm/ADT/EquivalenceClasses.h @@ -86,14 +86,14 @@ class EquivalenceClasses { } void setNext(const ECValue *NewNext) const { - assert(getNext() == 0 && "Already has a next pointer!"); + assert(getNext() == nullptr && "Already has a next pointer!"); Next = (const ECValue*)((intptr_t)NewNext | (intptr_t)isLeader()); } public: ECValue(const ECValue &RHS) : Leader(this), Next((ECValue*)(intptr_t)1), Data(RHS.Data) { // Only support copying of singleton nodes. - assert(RHS.isLeader() && RHS.getNext() == 0 && "Not a singleton!"); + assert(RHS.isLeader() && RHS.getNext() == nullptr && "Not a singleton!"); } bool operator<(const ECValue &UFN) const { return Data < UFN.Data; } @@ -147,10 +147,10 @@ public: class member_iterator; member_iterator member_begin(iterator I) const { // Only leaders provide anything to iterate over. - return member_iterator(I->isLeader() ? &*I : 0); + return member_iterator(I->isLeader() ? &*I : nullptr); } member_iterator member_end() const { - return member_iterator(0); + return member_iterator(nullptr); } /// findValue - Return an iterator to the specified value. If it does not @@ -251,13 +251,13 @@ public: explicit member_iterator(const ECValue *N) : Node(N) {} reference operator*() const { - assert(Node != 0 && "Dereferencing end()!"); + assert(Node != nullptr && "Dereferencing end()!"); return Node->getData(); } reference operator->() const { return operator*(); } member_iterator &operator++() { - assert(Node != 0 && "++'d off the end of the list!"); + assert(Node != nullptr && "++'d off the end of the list!"); Node = Node->getNext(); return *this; } diff --git a/include/llvm/ADT/FoldingSet.h b/include/llvm/ADT/FoldingSet.h index 188010d8ba..9b7ee8520d 100644 --- a/include/llvm/ADT/FoldingSet.h +++ b/include/llvm/ADT/FoldingSet.h @@ -137,7 +137,7 @@ public: public: - Node() : NextInFoldingSetBucket(0) {} + Node() : NextInFoldingSetBucket(nullptr) {} // Accessors void *getNextInBucket() const { return NextInFoldingSetBucket; } @@ -269,7 +269,7 @@ class FoldingSetNodeIDRef { const unsigned *Data; size_t Size; public: - FoldingSetNodeIDRef() : Data(0), Size(0) {} + FoldingSetNodeIDRef() : Data(nullptr), Size(0) {} FoldingSetNodeIDRef(const unsigned *D, size_t S) : Data(D), Size(S) {} /// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef, diff --git a/include/llvm/ADT/Hashing.h b/include/llvm/ADT/Hashing.h index 4bffd8e6e2..b11e3c1c50 100644 --- a/include/llvm/ADT/Hashing.h +++ b/include/llvm/ADT/Hashing.h @@ -45,7 +45,6 @@ #ifndef LLVM_ADT_HASHING_H #define LLVM_ADT_HASHING_H -#include "llvm/ADT/STLExtras.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/Host.h" #include "llvm/Support/SwapByteOrder.h" @@ -266,7 +265,6 @@ inline uint64_t hash_short(const char *s, size_t length, uint64_t seed) { /// keeps 56 bytes of arbitrary state. struct hash_state { uint64_t h0, h1, h2, h3, h4, h5, h6; - uint64_t seed; /// \brief Create a new hash_state structure and initialize it based on the /// seed and the first 64-byte chunk. @@ -274,7 +272,7 @@ struct hash_state { static hash_state create(const char *s, uint64_t seed) { hash_state state = { 0, seed, hash_16_bytes(seed, k1), rotate(seed ^ k1, 49), - seed * k1, shift_mix(seed), 0, seed }; + seed * k1, shift_mix(seed), 0 }; state.h6 = hash_16_bytes(state.h4, state.h5); state.mix(s); return state; @@ -412,7 +410,7 @@ template <typename InputIteratorT> hash_code hash_combine_range_impl(InputIteratorT first, InputIteratorT last) { const size_t seed = get_execution_seed(); char buffer[64], *buffer_ptr = buffer; - char *const buffer_end = buffer_ptr + array_lengthof(buffer); + char *const buffer_end = std::end(buffer); while (first != last && store_and_advance(buffer_ptr, buffer_end, get_hashable_data(*first))) ++first; diff --git a/include/llvm/ADT/ImmutableIntervalMap.h b/include/llvm/ADT/ImmutableIntervalMap.h deleted file mode 100644 index 6793c6b9c2..0000000000 --- a/include/llvm/ADT/ImmutableIntervalMap.h +++ /dev/null @@ -1,248 +0,0 @@ -//===--- ImmutableIntervalMap.h - Immutable (functional) map ---*- 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 ImmutableIntervalMap class. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ADT_IMMUTABLEINTERVALMAP_H -#define LLVM_ADT_IMMUTABLEINTERVALMAP_H - -#include "llvm/ADT/ImmutableMap.h" - -namespace llvm { - -class Interval { -private: - int64_t Start; - int64_t End; - -public: - Interval(int64_t S, int64_t E) : Start(S), End(E) {} - - int64_t getStart() const { return Start; } - int64_t getEnd() const { return End; } -}; - -template <typename T> -struct ImutIntervalInfo { - typedef const std::pair<Interval, T> value_type; - typedef const value_type &value_type_ref; - typedef const Interval key_type; - typedef const Interval &key_type_ref; - typedef const T data_type; - typedef const T &data_type_ref; - - static key_type_ref KeyOfValue(value_type_ref V) { - return V.first; - } - - static data_type_ref DataOfValue(value_type_ref V) { - return V.second; - } - - static bool isEqual(key_type_ref L, key_type_ref R) { - return L.getStart() == R.getStart() && L.getEnd() == R.getEnd(); - } - - static bool isDataEqual(data_type_ref L, data_type_ref R) { - return ImutContainerInfo<T>::isEqual(L,R); - } - - static bool isLess(key_type_ref L, key_type_ref R) { - // Assume L and R does not overlap. - if (L.getStart() < R.getStart()) { - assert(L.getEnd() < R.getStart()); - return true; - } else if (L.getStart() == R.getStart()) { - assert(L.getEnd() == R.getEnd()); - return false; - } else { - assert(L.getStart() > R.getEnd()); - return false; - } - } - - static bool isContainedIn(key_type_ref K, key_type_ref L) { - if (K.getStart() >= L.getStart() && K.getEnd() <= L.getEnd()) - return true; - else - return false; - } - - static void Profile(FoldingSetNodeID &ID, value_type_ref V) { - ID.AddInteger(V.first.getStart()); - ID.AddInteger(V.first.getEnd()); - ImutProfileInfo<T>::Profile(ID, V.second); - } -}; - -template <typename ImutInfo> -class ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> { - typedef ImutAVLTree<ImutInfo> TreeTy; - typedef typename ImutInfo::value_type value_type; - typedef typename ImutInfo::value_type_ref value_type_ref; - typedef typename ImutInfo::key_type key_type; - typedef typename ImutInfo::key_type_ref key_type_ref; - typedef typename ImutInfo::data_type data_type; - typedef typename ImutInfo::data_type_ref data_type_ref; - -public: - ImutIntervalAVLFactory(BumpPtrAllocator &Alloc) - : ImutAVLFactory<ImutInfo>(Alloc) {} - - TreeTy *Add(TreeTy *T, value_type_ref V) { - T = add_internal(V,T); - this->MarkImmutable(T); - return T; - } - - TreeTy *Find(TreeTy *T, key_type_ref K) { - if (!T) - return NULL; - - key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->getValue(T)); - - if (ImutInfo::isContainedIn(K, CurrentKey)) - return T; - else if (ImutInfo::isLess(K, CurrentKey)) - return Find(this->getLeft(T), K); - else - return Find(this->getRight(T), K); - } - -private: - TreeTy *add_internal(value_type_ref V, TreeTy *T) { - key_type_ref K = ImutInfo::KeyOfValue(V); - T = removeAllOverlaps(T, K); - if (this->isEmpty(T)) - return this->CreateNode(NULL, V, NULL); - - assert(!T->isMutable()); - - key_type_ref KCurrent = ImutInfo::KeyOfValue(this->Value(T)); - - if (ImutInfo::isLess(K, KCurrent)) - return this->Balance(add_internal(V, this->Left(T)), this->Value(T), - this->Right(T)); - else - return this->Balance(this->Left(T), this->Value(T), - add_internal(V, this->Right(T))); - } - - // Remove all overlaps from T. - TreeTy *removeAllOverlaps(TreeTy *T, key_type_ref K) { - bool Changed; - do { - Changed = false; - T = removeOverlap(T, K, Changed); - this->markImmutable(T); - } while (Changed); - - return T; - } - - // Remove one overlap from T. - TreeTy *removeOverlap(TreeTy *T, key_type_ref K, bool &Changed) { - if (!T) - return NULL; - Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T)); - - // If current key does not overlap the inserted key. - if (CurrentK.getStart() > K.getEnd()) - return this->Balance(removeOverlap(this->Left(T), K, Changed), - this->Value(T), this->Right(T)); - else if (CurrentK.getEnd() < K.getStart()) - return this->Balance(this->Left(T), this->Value(T), - removeOverlap(this->Right(T), K, Changed)); - - // Current key overlaps with the inserted key. - // Remove the current key. - Changed = true; - data_type_ref OldData = ImutInfo::DataOfValue(this->Value(T)); - T = this->Remove_internal(CurrentK, T); - // Add back the unoverlapped part of the current key. - if (CurrentK.getStart() < K.getStart()) { - if (CurrentK.getEnd() <= K.getEnd()) { - Interval NewK(CurrentK.getStart(), K.getStart()-1); - return add_internal(std::make_pair(NewK, OldData), T); - } else { - Interval NewK1(CurrentK.getStart(), K.getStart()-1); - T = add_internal(std::make_pair(NewK1, OldData), T); - - Interval NewK2(K.getEnd()+1, CurrentK.getEnd()); - return add_internal(std::make_pair(NewK2, OldData), T); - } - } else { - if (CurrentK.getEnd() > K.getEnd()) { - Interval NewK(K.getEnd()+1, CurrentK.getEnd()); - return add_internal(std::make_pair(NewK, OldData), T); - } else - return T; - } - } -}; - -/// ImmutableIntervalMap maps an interval [start, end] to a value. The intervals -/// in the map are guaranteed to be disjoint. -template <typename ValT> -class ImmutableIntervalMap - : public ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> > { - - typedef typename ImutIntervalInfo<ValT>::value_type value_type; - typedef typename ImutIntervalInfo<ValT>::value_type_ref value_type_ref; - typedef typename ImutIntervalInfo<ValT>::key_type key_type; - typedef typename ImutIntervalInfo<ValT>::key_type_ref key_type_ref; - typedef typename ImutIntervalInfo<ValT>::data_type data_type; - typedef typename ImutIntervalInfo<ValT>::data_type_ref data_type_ref; - typedef ImutAVLTree<ImutIntervalInfo<ValT> > TreeTy; - -public: - explicit ImmutableIntervalMap(TreeTy *R) - : ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> >(R) {} - - class Factory { - ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F; - - public: - Factory(BumpPtrAllocator& Alloc) : F(Alloc) {} - - ImmutableIntervalMap getEmptyMap() { - return ImmutableIntervalMap(F.getEmptyTree()); - } - - ImmutableIntervalMap add(ImmutableIntervalMap Old, - key_type_ref K, data_type_ref D) { - TreeTy *T = F.add(Old.Root, std::pair<key_type, data_type>(K, D)); - return ImmutableIntervalMap(F.getCanonicalTree(T)); - } - - ImmutableIntervalMap remove(ImmutableIntervalMap Old, key_type_ref K) { - TreeTy *T = F.remove(Old.Root, K); - return ImmutableIntervalMap(F.getCanonicalTree(T)); - } - - data_type *lookup(ImmutableIntervalMap M, key_type_ref K) { - TreeTy *T = F.Find(M.getRoot(), K); - if (T) - return &T->getValue().second; - else - return 0; - } - }; - -private: - // For ImmutableIntervalMap, the lookup operation has to be done by the - // factory. - data_type* lookup(key_type_ref K) const; -}; - -} // end namespace llvm - -#endif diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h index 8f8fb98770..11f281be3d 100644 --- a/include/llvm/ADT/ImmutableMap.h +++ b/include/llvm/ADT/ImmutableMap.h @@ -241,14 +241,14 @@ public: if (T) return &T->getValue().second; } - return 0; + return nullptr; } /// getMaxElement - Returns the <key,value> pair in the ImmutableMap for /// which key is the highest in the ordering of keys in the map. This /// method returns NULL if the map is empty. value_type* getMaxElement() const { - return Root ? &(Root->getMaxElement()->getValue()) : 0; + return Root ? &(Root->getMaxElement()->getValue()) : nullptr; } //===--------------------------------------------------===// diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h index ad349699e2..5a3d8ad21f 100644 --- a/include/llvm/ADT/ImmutableSet.h +++ b/include/llvm/ADT/ImmutableSet.h @@ -81,7 +81,7 @@ public: else T = T->getRight(); } - return NULL; + return nullptr; } /// getMaxElement - Find the subtree associated with the highest ranged @@ -242,9 +242,9 @@ private: /// ImutAVLFactory. ImutAVLTree(Factory *f, ImutAVLTree* l, ImutAVLTree* r, value_type_ref v, unsigned height) - : factory(f), left(l), right(r), prev(0), next(0), height(height), - IsMutable(true), IsDigestCached(false), IsCanonicalized(0), - value(v), digest(0), refCount(0) + : factory(f), left(l), right(r), prev(nullptr), next(nullptr), + height(height), IsMutable(true), IsDigestCached(false), + IsCanonicalized(0), value(v), digest(0), refCount(0) { if (left) left->retain(); if (right) right->retain(); @@ -411,7 +411,7 @@ public: return T; } - TreeTy* getEmptyTree() const { return NULL; } + TreeTy* getEmptyTree() const { return nullptr; } protected: @@ -607,7 +607,7 @@ protected: public: TreeTy *getCanonicalTree(TreeTy *TNew) { if (!TNew) - return 0; + return nullptr; if (TNew->IsCanonicalized) return TNew; @@ -619,7 +619,7 @@ public: do { if (!entry) break; - for (TreeTy *T = entry ; T != 0; T = T->next) { + for (TreeTy *T = entry ; T != nullptr; T = T->next) { // Compare the Contents('T') with Contents('TNew') typename TreeTy::iterator TI = T->begin(), TE = T->end(); if (!compareTreeWithSection(TNew, TI, TE)) @@ -696,12 +696,7 @@ public: } inline bool operator==(const _Self& x) const { - if (stack.size() != x.stack.size()) - return false; - for (unsigned i = 0 ; i < stack.size(); i++) - if (stack[i] != x.stack[i]) - return false; - return true; + return stack == x.stack; } inline bool operator!=(const _Self& x) const { return !operator==(x); } diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h index 1ca3288a35..46549eed99 100644 --- a/include/llvm/ADT/IntervalMap.h +++ b/include/llvm/ADT/IntervalMap.h @@ -1177,7 +1177,7 @@ branchRoot(unsigned Position) { if (Nodes == 1) size[0] = rootSize; else - NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, size, + NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, size, Position, true); // Allocate new nodes. @@ -1218,7 +1218,7 @@ splitRoot(unsigned Position) { if (Nodes == 1) Size[0] = rootSize; else - NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, NULL, Size, + NewOffset = distribute(Nodes, rootSize, Leaf::Capacity, nullptr, Size, Position, true); // Allocate new nodes. @@ -1346,7 +1346,7 @@ protected: public: /// const_iterator - Create an iterator that isn't pointing anywhere. - const_iterator() : map(0) {} + const_iterator() : map(nullptr) {} /// setMap - Change the map iterated over. This call must be followed by a /// call to goToBegin(), goToEnd(), or find() diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h index 729e37f06a..cd1946c54d 100644 --- a/include/llvm/ADT/IntrusiveRefCntPtr.h +++ b/include/llvm/ADT/IntrusiveRefCntPtr.h @@ -139,7 +139,7 @@ public: public: typedef T element_type; - explicit IntrusiveRefCntPtr() : Obj(0) {} + explicit IntrusiveRefCntPtr() : Obj(nullptr) {} IntrusiveRefCntPtr(T* obj) : Obj(obj) { retain(); @@ -150,7 +150,7 @@ public: } IntrusiveRefCntPtr(IntrusiveRefCntPtr&& S) : Obj(S.Obj) { - S.Obj = 0; + S.Obj = nullptr; } template <class X> @@ -179,7 +179,7 @@ public: typedef T* (IntrusiveRefCntPtr::*unspecified_bool_type) () const; operator unspecified_bool_type() const { - return Obj == 0 ? 0 : &IntrusiveRefCntPtr::getPtr; + return Obj ? &IntrusiveRefCntPtr::getPtr : nullptr; } void swap(IntrusiveRefCntPtr& other) { @@ -190,7 +190,7 @@ public: void reset() { release(); - Obj = 0; + Obj = nullptr; } void resetWithoutRelease() { diff --git a/include/llvm/ADT/OwningPtr.h b/include/llvm/ADT/OwningPtr.h index 034bcfd6ed..5e83358fc0 100644 --- a/include/llvm/ADT/OwningPtr.h +++ b/include/llvm/ADT/OwningPtr.h @@ -69,7 +69,7 @@ public: /// not delete the pointer before returning it. T *take() { T *Tmp = Ptr; - Ptr = 0; + Ptr = nullptr; return Tmp; } @@ -84,9 +84,9 @@ public: T *operator->() const { return Ptr; } T *get() const { return Ptr; } - LLVM_EXPLICIT operator bool() const { return Ptr != 0; } - bool operator!() const { return Ptr == 0; } - bool isValid() const { return Ptr != 0; } + LLVM_EXPLICIT operator bool() const { return Ptr != nullptr; } + bool operator!() const { return Ptr == nullptr; } + bool isValid() const { return Ptr != nullptr; } void swap(OwningPtr &RHS) { T *Tmp = RHS.Ptr; @@ -146,7 +146,7 @@ public: T *get() const { return Ptr; } LLVM_EXPLICIT operator bool() const { return Ptr != 0; } - bool operator!() const { return Ptr == 0; } + bool operator!() const { return Ptr == nullptr; } void swap(OwningArrayPtr &RHS) { T *Tmp = RHS.Ptr; diff --git a/include/llvm/ADT/PointerUnion.h b/include/llvm/ADT/PointerUnion.h index 8cbe8d1df7..a6dddd2776 100644 --- a/include/llvm/ADT/PointerUnion.h +++ b/include/llvm/ADT/PointerUnion.h @@ -15,6 +15,7 @@ #ifndef LLVM_ADT_POINTERUNION_H #define LLVM_ADT_POINTERUNION_H +#include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/Support/Compiler.h" @@ -153,6 +154,12 @@ namespace llvm { "Can't get the address because PointerLikeTypeTraits changes the ptr"); return (PT1 *)Val.getAddrOfPointer(); } + + /// \brief Assignment from nullptr which just clears the union. + const PointerUnion &operator=(std::nullptr_t) { + Val.initWithPointer(nullptr); + return *this; + } /// Assignment operators - Allow assigning into this union from either /// pointer type, setting the discriminator to remember what it came from. @@ -297,6 +304,12 @@ namespace llvm { if (is<T>()) return get<T>(); return T(); } + + /// \brief Assignment from nullptr which just clears the union. + const PointerUnion3 &operator=(std::nullptr_t) { + Val = nullptr; + return *this; + } /// Assignment operators - Allow assigning into this union from either /// pointer type, setting the discriminator to remember what it came from. @@ -406,6 +419,12 @@ namespace llvm { if (is<T>()) return get<T>(); return T(); } + + /// \brief Assignment from nullptr which just clears the union. + const PointerUnion4 &operator=(std::nullptr_t) { + Val = nullptr; + return *this; + } /// Assignment operators - Allow assigning into this union from either /// pointer type, setting the discriminator to remember what it came from. @@ -455,6 +474,33 @@ namespace llvm { ::NumLowBitsAvailable }; }; + + // Teach DenseMap how to use PointerUnions as keys. + template<typename T, typename U> + struct DenseMapInfo<PointerUnion<T, U> > { + typedef PointerUnion<T, U> Pair; + typedef DenseMapInfo<T> FirstInfo; + typedef DenseMapInfo<U> SecondInfo; + + static inline Pair getEmptyKey() { + return Pair(FirstInfo::getEmptyKey()); + } + static inline Pair getTombstoneKey() { + return Pair(FirstInfo::getTombstoneKey()); + } + static unsigned getHashValue(const Pair &PairVal) { + intptr_t key = (intptr_t)PairVal.getOpaqueValue(); + return DenseMapInfo<intptr_t>::getHashValue(key); + } + static bool isEqual(const Pair &LHS, const Pair &RHS) { + return LHS.template is<T>() == RHS.template is<T>() && + (LHS.template is<T>() ? + FirstInfo::isEqual(LHS.template get<T>(), + RHS.template get<T>()) : + SecondInfo::isEqual(LHS.template get<U>(), + RHS.template get<U>())); + } + }; } #endif diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h index 59fa3f39c9..dd8cc74b71 100644 --- a/include/llvm/ADT/PostOrderIterator.h +++ b/include/llvm/ADT/PostOrderIterator.h @@ -111,7 +111,7 @@ class po_iterator : public std::iterator<std::forward_iterator_tag, } inline po_iterator(NodeType *BB) { - this->insertEdge((NodeType*)0, BB); + this->insertEdge((NodeType*)nullptr, BB); VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); traverseChild(); } @@ -119,7 +119,7 @@ class po_iterator : public std::iterator<std::forward_iterator_tag, inline po_iterator(NodeType *BB, SetType &S) : po_iterator_storage<SetType, ExtStorage>(S) { - if (this->insertEdge((NodeType*)0, BB)) { + if (this->insertEdge((NodeType*)nullptr, BB)) { VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); traverseChild(); } diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h index 58ac149e32..bc74416ac8 100644 --- a/include/llvm/ADT/SCCIterator.h +++ b/include/llvm/ADT/SCCIterator.h @@ -25,6 +25,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/iterator.h" #include <vector> namespace llvm { @@ -35,19 +36,17 @@ namespace llvm { /// This is implemented using Tarjan's DFS algorithm using an internal stack to /// build up a vector of nodes in a particular SCC. Note that it is a forward /// iterator and thus you cannot backtrack or re-visit nodes. -template <class GraphT, class GT = GraphTraits<GraphT> > +template <class GraphT, class GT = GraphTraits<GraphT>> class scc_iterator - : public std::iterator<std::forward_iterator_tag, - std::vector<typename GT::NodeType>, ptrdiff_t> { + : public iterator_facade_base< + scc_iterator<GraphT, GT>, std::forward_iterator_tag, + const std::vector<typename GT::NodeType *>, ptrdiff_t> { typedef typename GT::NodeType NodeType; typedef typename GT::ChildIteratorType ChildItTy; typedef std::vector<NodeType *> SccTy; - typedef std::iterator<std::forward_iterator_tag, - std::vector<typename GT::NodeType>, ptrdiff_t> super; - typedef typename super::reference reference; - typedef typename super::pointer pointer; + typedef typename scc_iterator::reference reference; - // Element of VisitStack during DFS. + /// Element of VisitStack during DFS. struct StackElement { NodeType *Node; ///< The current node pointer. ChildItTy NextChild; ///< The next child, modified inplace during DFS. @@ -63,135 +62,63 @@ class scc_iterator } }; - // The visit counters used to detect when a complete SCC is on the stack. - // visitNum is the global counter. - // nodeVisitNumbers are per-node visit numbers, also used as DFS flags. + /// The visit counters used to detect when a complete SCC is on the stack. + /// visitNum is the global counter. + /// + /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags. unsigned visitNum; DenseMap<NodeType *, unsigned> nodeVisitNumbers; - // Stack holding nodes of the SCC. + /// Stack holding nodes of the SCC. std::vector<NodeType *> SCCNodeStack; - // The current SCC, retrieved using operator*(). + /// The current SCC, retrieved using operator*(). SccTy CurrentSCC; - - // DFS stack, Used to maintain the ordering. The top contains the current - // node, the next child to visit, and the minimum uplink value of all child + /// DFS stack, Used to maintain the ordering. The top contains the current + /// node, the next child to visit, and the minimum uplink value of all child std::vector<StackElement> VisitStack; - // A single "visit" within the non-recursive DFS traversal. - void DFSVisitOne(NodeType *N) { - ++visitNum; - nodeVisitNumbers[N] = visitNum; - SCCNodeStack.push_back(N); - VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum)); -#if 0 // Enable if needed when debugging. - dbgs() << "TarjanSCC: Node " << N << - " : visitNum = " << visitNum << "\n"; -#endif - } + /// A single "visit" within the non-recursive DFS traversal. + void DFSVisitOne(NodeType *N); - // The stack-based DFS traversal; defined below. - void DFSVisitChildren() { - assert(!VisitStack.empty()); - while (VisitStack.back().NextChild != - GT::child_end(VisitStack.back().Node)) { - // TOS has at least one more child so continue DFS - NodeType *childN = *VisitStack.back().NextChild++; - typename DenseMap<NodeType *, unsigned>::iterator Visited = - nodeVisitNumbers.find(childN); - if (Visited == nodeVisitNumbers.end()) { - // this node has never been seen. - DFSVisitOne(childN); - continue; - } - - unsigned childNum = Visited->second; - if (VisitStack.back().MinVisited > childNum) - VisitStack.back().MinVisited = childNum; - } - } + /// The stack-based DFS traversal; defined below. + void DFSVisitChildren(); - // Compute the next SCC using the DFS traversal. - void GetNextSCC() { - CurrentSCC.clear(); // Prepare to compute the next SCC - while (!VisitStack.empty()) { - DFSVisitChildren(); + /// Compute the next SCC using the DFS traversal. + void GetNextSCC(); - // Pop the leaf on top of the VisitStack. - NodeType *visitingN = VisitStack.back().Node; - unsigned minVisitNum = VisitStack.back().MinVisited; - assert(VisitStack.back().NextChild == GT::child_end(visitingN)); - VisitStack.pop_back(); - - // Propagate MinVisitNum to parent so we can detect the SCC starting node. - if (!VisitStack.empty() && VisitStack.back().MinVisited > minVisitNum) - VisitStack.back().MinVisited = minVisitNum; - -#if 0 // Enable if needed when debugging. - dbgs() << "TarjanSCC: Popped node " << visitingN << - " : minVisitNum = " << minVisitNum << "; Node visit num = " << - nodeVisitNumbers[visitingN] << "\n"; -#endif - - if (minVisitNum != nodeVisitNumbers[visitingN]) - continue; - - // A full SCC is on the SCCNodeStack! It includes all nodes below - // visitingN on the stack. Copy those nodes to CurrentSCC, - // reset their minVisit values, and return (this suspends - // the DFS traversal till the next ++). - do { - CurrentSCC.push_back(SCCNodeStack.back()); - SCCNodeStack.pop_back(); - nodeVisitNumbers[CurrentSCC.back()] = ~0U; - } while (CurrentSCC.back() != visitingN); - return; - } - } - - inline scc_iterator(NodeType *entryN) : visitNum(0) { + scc_iterator(NodeType *entryN) : visitNum(0) { DFSVisitOne(entryN); GetNextSCC(); } - // End is when the DFS stack is empty. - inline scc_iterator() {} + /// End is when the DFS stack is empty. + scc_iterator() {} public: - static inline scc_iterator begin(const GraphT &G) { + static scc_iterator begin(const GraphT &G) { return scc_iterator(GT::getEntryNode(G)); } - static inline scc_iterator end(const GraphT &) { return scc_iterator(); } + static scc_iterator end(const GraphT &) { return scc_iterator(); } /// \brief Direct loop termination test which is more efficient than /// comparison with \c end(). - inline bool isAtEnd() const { + bool isAtEnd() const { assert(!CurrentSCC.empty() || VisitStack.empty()); return CurrentSCC.empty(); } - inline bool operator==(const scc_iterator &x) const { + bool operator==(const scc_iterator &x) const { return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC; } - inline bool operator!=(const scc_iterator &x) const { return !operator==(x); } - inline scc_iterator &operator++() { + scc_iterator &operator++() { GetNextSCC(); return *this; } - inline scc_iterator operator++(int) { - scc_iterator tmp = *this; - ++*this; - return tmp; - } - inline const SccTy &operator*() const { - assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); - return CurrentSCC; - } - inline SccTy &operator*() { + reference operator*() const { assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); return CurrentSCC; } @@ -200,7 +127,88 @@ public: /// /// If the SCC has more than one node, this is trivially true. If not, it may /// still contain a loop if the node has an edge back to itself. - bool hasLoop() const { + bool hasLoop() const; + + /// This informs the \c scc_iterator that the specified \c Old node + /// has been deleted, and \c New is to be used in its place. + void ReplaceNode(NodeType *Old, NodeType *New) { + assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?"); + nodeVisitNumbers[New] = nodeVisitNumbers[Old]; + nodeVisitNumbers.erase(Old); + } +}; + +template <class GraphT, class GT> +void scc_iterator<GraphT, GT>::DFSVisitOne(NodeType *N) { + ++visitNum; + nodeVisitNumbers[N] = visitNum; + SCCNodeStack.push_back(N); + VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum)); +#if 0 // Enable if needed when debugging. + dbgs() << "TarjanSCC: Node " << N << + " : visitNum = " << visitNum << "\n"; +#endif +} + +template <class GraphT, class GT> +void scc_iterator<GraphT, GT>::DFSVisitChildren() { + assert(!VisitStack.empty()); + while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) { + // TOS has at least one more child so continue DFS + NodeType *childN = *VisitStack.back().NextChild++; + typename DenseMap<NodeType *, unsigned>::iterator Visited = + nodeVisitNumbers.find(childN); + if (Visited == nodeVisitNumbers.end()) { + // this node has never been seen. + DFSVisitOne(childN); + continue; + } + + unsigned childNum = Visited->second; + if (VisitStack.back().MinVisited > childNum) + VisitStack.back().MinVisited = childNum; + } +} + +template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() { + CurrentSCC.clear(); // Prepare to compute the next SCC + while (!VisitStack.empty()) { + DFSVisitChildren(); + + // Pop the leaf on top of the VisitStack. + NodeType *visitingN = VisitStack.back().Node; + unsigned minVisitNum = VisitStack.back().MinVisited; + assert(VisitStack.back().NextChild == GT::child_end(visitingN)); + VisitStack.pop_back(); + + // Propagate MinVisitNum to parent so we can detect the SCC starting node. + if (!VisitStack.empty() && VisitStack.back().MinVisited > minVisitNum) + VisitStack.back().MinVisited = minVisitNum; + +#if 0 // Enable if needed when debugging. + dbgs() << "TarjanSCC: Popped node " << visitingN << + " : minVisitNum = " << minVisitNum << "; Node visit num = " << + nodeVisitNumbers[visitingN] << "\n"; +#endif + + if (minVisitNum != nodeVisitNumbers[visitingN]) + continue; + + // A full SCC is on the SCCNodeStack! It includes all nodes below + // visitingN on the stack. Copy those nodes to CurrentSCC, + // reset their minVisit values, and return (this suspends + // the DFS traversal till the next ++). + do { + CurrentSCC.push_back(SCCNodeStack.back()); + SCCNodeStack.pop_back(); + nodeVisitNumbers[CurrentSCC.back()] = ~0U; + } while (CurrentSCC.back() != visitingN); + return; + } +} + +template <class GraphT, class GT> +bool scc_iterator<GraphT, GT>::hasLoop() const { assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); if (CurrentSCC.size() > 1) return true; @@ -212,15 +220,6 @@ public: return false; } - /// This informs the \c scc_iterator that the specified \c Old node - /// has been deleted, and \c New is to be used in its place. - void ReplaceNode(NodeType *Old, NodeType *New) { - assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?"); - nodeVisitNumbers[New] = nodeVisitNumbers[Old]; - nodeVisitNumbers.erase(Old); - } -}; - /// \brief Construct the begin iterator for a deduced graph type T. template <class T> scc_iterator<T> scc_begin(const T &G) { return scc_iterator<T>::begin(G); diff --git a/include/llvm/ADT/STLExtras.h b/include/llvm/ADT/STLExtras.h index ab6884ffb5..1cef3933b5 100644 --- a/include/llvm/ADT/STLExtras.h +++ b/include/llvm/ADT/STLExtras.h @@ -55,6 +55,131 @@ struct greater_ptr : public std::binary_function<Ty, Ty, bool> { } }; +/// An efficient, type-erasing, non-owning reference to a callable. This is +/// intended for use as the type of a function parameter that is not used +/// after the function in question returns. +/// +/// This class does not own the callable, so it is not in general safe to store +/// a function_ref. +template<typename Fn> class function_ref; + +#if LLVM_HAS_VARIADIC_TEMPLATES + +template<typename Ret, typename ...Params> +class function_ref<Ret(Params...)> { + Ret (*callback)(intptr_t callable, Params ...params); + intptr_t callable; + + template<typename Callable> + static Ret callback_fn(intptr_t callable, Params ...params) { + return (*reinterpret_cast<Callable*>(callable))( + std::forward<Params>(params)...); + } + +public: + template<typename Callable> + function_ref(Callable &&callable) + : callback(callback_fn<typename std::remove_reference<Callable>::type>), + callable(reinterpret_cast<intptr_t>(&callable)) {} + Ret operator()(Params ...params) const { + return callback(callable, std::forward<Params>(params)...); + } +}; + +#else + +template<typename Ret> +class function_ref<Ret()> { + Ret (*callback)(intptr_t callable); + intptr_t callable; + + template<typename Callable> + static Ret callback_fn(intptr_t callable) { + return (*reinterpret_cast<Callable*>(callable))(); + } + +public: + template<typename Callable> + function_ref(Callable &&callable) + : callback(callback_fn<typename std::remove_reference<Callable>::type>), + callable(reinterpret_cast<intptr_t>(&callable)) {} + Ret operator()() const { return callback(callable); } +}; + +template<typename Ret, typename Param1> +class function_ref<Ret(Param1)> { + Ret (*callback)(intptr_t callable, Param1 param1); + intptr_t callable; + + template<typename Callable> + static Ret callback_fn(intptr_t callable, Param1 param1) { + return (*reinterpret_cast<Callable*>(callable))( + std::forward<Param1>(param1)); + } + +public: + template<typename Callable> + function_ref(Callable &&callable) + : callback(callback_fn<typename std::remove_reference<Callable>::type>), + callable(reinterpret_cast<intptr_t>(&callable)) {} + Ret operator()(Param1 param1) { + return callback(callable, std::forward<Param1>(param1)); + } +}; + +template<typename Ret, typename Param1, typename Param2> +class function_ref<Ret(Param1, Param2)> { + Ret (*callback)(intptr_t callable, Param1 param1, Param2 param2); + intptr_t callable; + + template<typename Callable> + static Ret callback_fn(intptr_t callable, Param1 param1, Param2 param2) { + return (*reinterpret_cast<Callable*>(callable))( + std::forward<Param1>(param1), + std::forward<Param2>(param2)); + } + +public: + template<typename Callable> + function_ref(Callable &&callable) + : callback(callback_fn<typename std::remove_reference<Callable>::type>), + callable(reinterpret_cast<intptr_t>(&callable)) {} + Ret operator()(Param1 param1, Param2 param2) { + return callback(callable, + std::forward<Param1>(param1), + std::forward<Param2>(param2)); + } +}; + +template<typename Ret, typename Param1, typename Param2, typename Param3> +class function_ref<Ret(Param1, Param2, Param3)> { + Ret (*callback)(intptr_t callable, Param1 param1, Param2 param2, Param3 param3); + intptr_t callable; + + template<typename Callable> + static Ret callback_fn(intptr_t callable, Param1 param1, Param2 param2, + Param3 param3) { + return (*reinterpret_cast<Callable*>(callable))( + std::forward<Param1>(param1), + std::forward<Param2>(param2), + std::forward<Param3>(param3)); + } + +public: + template<typename Callable> + function_ref(Callable &&callable) + : callback(callback_fn<typename std::remove_reference<Callable>::type>), + callable(reinterpret_cast<intptr_t>(&callable)) {} + Ret operator()(Param1 param1, Param2 param2, Param3 param3) { + return callback(callable, + std::forward<Param1>(param1), + std::forward<Param2>(param2), + std::forward<Param3>(param3)); + } +}; + +#endif + // deleter - Very very very simple method that is used to invoke operator // delete on something. It is used like this: // @@ -165,27 +290,20 @@ struct less_second { // Extra additions for arrays //===----------------------------------------------------------------------===// -/// Find where an array ends (for ending iterators) -/// This returns a pointer to the byte immediately -/// after the end of an array. -template<class T, std::size_t N> -inline T *array_endof(T (&x)[N]) { - return x+N; -} - /// Find the length of an array. -template<class T, std::size_t N> -inline size_t array_lengthof(T (&)[N]) { +template <class T, std::size_t N> +LLVM_CONSTEXPR inline size_t array_lengthof(T (&)[N]) { return N; } -/// array_pod_sort_comparator - This is helper function for array_pod_sort, -/// which just uses operator< on T. +/// Adapt std::less<T> for array_pod_sort. template<typename T> inline int array_pod_sort_comparator(const void *P1, const void *P2) { - if (*reinterpret_cast<const T*>(P1) < *reinterpret_cast<const T*>(P2)) + if (std::less<T>()(*reinterpret_cast<const T*>(P1), + *reinterpret_cast<const T*>(P2))) return -1; - if (*reinterpret_cast<const T*>(P2) < *reinterpret_cast<const T*>(P1)) + if (std::less<T>()(*reinterpret_cast<const T*>(P2), + *reinterpret_cast<const T*>(P1))) return 1; return 0; } @@ -208,7 +326,7 @@ inline int (*get_array_pod_sort_comparator(const T &)) /// possible. /// /// This function assumes that you have simple POD-like types that can be -/// compared with operator< and can be moved with memcpy. If this isn't true, +/// compared with std::less and can be moved with memcpy. If this isn't true, /// you should use std::sort. /// /// NOTE: If qsort_r were portable, we could allow a custom comparator and @@ -412,6 +530,13 @@ make_unique(size_t n) { #endif +template<typename First, typename Second> +struct pair_hash { + size_t operator()(const std::pair<First, Second> &P) const { + return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); + } +}; + } // End llvm namespace #endif diff --git a/include/llvm/ADT/ScopedHashTable.h b/include/llvm/ADT/ScopedHashTable.h index efddd9f9b8..3cc7738df8 100644 --- a/include/llvm/ADT/ScopedHashTable.h +++ b/include/llvm/ADT/ScopedHashTable.h @@ -159,18 +159,16 @@ private: void operator=(const ScopedHashTable&); // NOT YET IMPLEMENTED friend class ScopedHashTableScope<K, V, KInfo, AllocatorTy>; public: - ScopedHashTable() : CurScope(0) {} + ScopedHashTable() : CurScope(nullptr) {} ScopedHashTable(AllocatorTy A) : CurScope(0), Allocator(A) {} ~ScopedHashTable() { - assert(CurScope == 0 && TopLevelMap.empty() && "Scope imbalance!"); + assert(!CurScope && TopLevelMap.empty() && "Scope imbalance!"); } /// Access to the allocator. - typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; - typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; - AllocatorRefTy getAllocator() { return Allocator; } - AllocatorCRefTy getAllocator() const { return Allocator; } + AllocatorTy &getAllocator() { return Allocator; } + const AllocatorTy &getAllocator() const { return Allocator; } bool count(const K &Key) const { return TopLevelMap.count(Key); @@ -222,7 +220,7 @@ ScopedHashTableScope<K, V, KInfo, Allocator>:: ScopedHashTableScope(ScopedHashTable<K, V, KInfo, Allocator> &ht) : HT(ht) { PrevScope = HT.CurScope; HT.CurScope = this; - LastValInScope = 0; + LastValInScope = nullptr; } template <typename K, typename V, typename KInfo, typename Allocator> @@ -233,7 +231,7 @@ ScopedHashTableScope<K, V, KInfo, Allocator>::~ScopedHashTableScope() { // Pop and delete all values corresponding to this scope. while (ScopedHashTableVal<K, V> *ThisEntry = LastValInScope) { // Pop this value out of the TopLevelMap. - if (ThisEntry->getNextForKey() == 0) { + if (!ThisEntry->getNextForKey()) { assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry && "Scope imbalance!"); HT.TopLevelMap.erase(ThisEntry->getKey()); diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 0a4140e8f8..dcf0354860 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -220,28 +220,20 @@ protected: /// Guarantees space for at least one more element, or MinSize more /// elements if specified. void grow(size_t MinSize = 0); - + public: void push_back(const T &Elt) { - if (this->EndX < this->CapacityX) { - Retry: - ::new ((void*) this->end()) T(Elt); - this->setEnd(this->end()+1); - return; - } - this->grow(); - goto Retry; + if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) + this->grow(); + ::new ((void*) this->end()) T(Elt); + this->setEnd(this->end()+1); } void push_back(T &&Elt) { - if (this->EndX < this->CapacityX) { - Retry: - ::new ((void*) this->end()) T(::std::move(Elt)); - this->setEnd(this->end()+1); - return; - } - this->grow(); - goto Retry; + if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) + this->grow(); + ::new ((void*) this->end()) T(::std::move(Elt)); + this->setEnd(this->end()+1); } void pop_back() { @@ -255,7 +247,7 @@ template <typename T, bool isPodLike> void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) { size_t CurCapacity = this->capacity(); size_t CurSize = this->size(); - // Always grow, even from zero. + // Always grow, even from zero. size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2)); if (NewCapacity < MinSize) NewCapacity = MinSize; @@ -335,16 +327,12 @@ protected: } public: void push_back(const T &Elt) { - if (this->EndX < this->CapacityX) { - Retry: - memcpy(this->end(), &Elt, sizeof(T)); - this->setEnd(this->end()+1); - return; - } - this->grow(); - goto Retry; + if (LLVM_UNLIKELY(this->EndX >= this->CapacityX)) + this->grow(); + memcpy(this->end(), &Elt, sizeof(T)); + this->setEnd(this->end()+1); } - + void pop_back() { this->setEnd(this->end()-1); } @@ -493,26 +481,25 @@ public: assert(I >= this->begin() && "Insertion iterator is out of bounds."); assert(I <= this->end() && "Inserting past the end of the vector."); - if (this->EndX < this->CapacityX) { - Retry: - ::new ((void*) this->end()) T(::std::move(this->back())); - this->setEnd(this->end()+1); - // Push everything else over. - this->move_backward(I, this->end()-1, this->end()); + if (this->EndX >= this->CapacityX) { + size_t EltNo = I-this->begin(); + this->grow(); + I = this->begin()+EltNo; + } - // If we just moved the element we're inserting, be sure to update - // the reference. - T *EltPtr = &Elt; - if (I <= EltPtr && EltPtr < this->EndX) - ++EltPtr; + ::new ((void*) this->end()) T(::std::move(this->back())); + this->setEnd(this->end()+1); + // Push everything else over. + this->move_backward(I, this->end()-1, this->end()); - *I = ::std::move(*EltPtr); - return I; - } - size_t EltNo = I-this->begin(); - this->grow(); - I = this->begin()+EltNo; - goto Retry; + // If we just moved the element we're inserting, be sure to update + // the reference. + T *EltPtr = &Elt; + if (I <= EltPtr && EltPtr < this->EndX) + ++EltPtr; + + *I = ::std::move(*EltPtr); + return I; } iterator insert(iterator I, const T &Elt) { @@ -524,26 +511,24 @@ public: assert(I >= this->begin() && "Insertion iterator is out of bounds."); assert(I <= this->end() && "Inserting past the end of the vector."); - if (this->EndX < this->CapacityX) { - Retry: - ::new ((void*) this->end()) T(this->back()); - this->setEnd(this->end()+1); - // Push everything else over. - this->move_backward(I, this->end()-1, this->end()); - - // If we just moved the element we're inserting, be sure to update - // the reference. - const T *EltPtr = &Elt; - if (I <= EltPtr && EltPtr < this->EndX) - ++EltPtr; - - *I = *EltPtr; - return I; + if (this->EndX >= this->CapacityX) { + size_t EltNo = I-this->begin(); + this->grow(); + I = this->begin()+EltNo; } - size_t EltNo = I-this->begin(); - this->grow(); - I = this->begin()+EltNo; - goto Retry; + ::new ((void*) this->end()) T(this->back()); + this->setEnd(this->end()+1); + // Push everything else over. + this->move_backward(I, this->end()-1, this->end()); + + // If we just moved the element we're inserting, be sure to update + // the reference. + const T *EltPtr = &Elt; + if (I <= EltPtr && EltPtr < this->EndX) + ++EltPtr; + + *I = *EltPtr; + return I; } iterator insert(iterator I, size_type NumToInsert, const T &Elt) { @@ -820,7 +805,7 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) { this->grow(RHSSize); } else if (CurSize) { // Otherwise, use assignment for the already-constructed elements. - this->move(RHS.begin(), RHS.end(), this->begin()); + this->move(RHS.begin(), RHS.begin()+CurSize, this->begin()); } // Move-construct the new elements in place. diff --git a/include/llvm/ADT/SparseMultiSet.h b/include/llvm/ADT/SparseMultiSet.h index 797a898dcc..d2b2f8d9b6 100644 --- a/include/llvm/ADT/SparseMultiSet.h +++ b/include/llvm/ADT/SparseMultiSet.h @@ -187,7 +187,7 @@ public: typedef const ValueT *const_pointer; SparseMultiSet() - : Sparse(0), Universe(0), FreelistIdx(SMSNode::INVALID), NumFree(0) { } + : Sparse(nullptr), Universe(0), FreelistIdx(SMSNode::INVALID), NumFree(0) {} ~SparseMultiSet() { free(Sparse); } diff --git a/include/llvm/ADT/SparseSet.h b/include/llvm/ADT/SparseSet.h index b46ccc9375..899f2e4da0 100644 --- a/include/llvm/ADT/SparseSet.h +++ b/include/llvm/ADT/SparseSet.h @@ -142,7 +142,7 @@ public: typedef ValueT *pointer; typedef const ValueT *const_pointer; - SparseSet() : Sparse(0), Universe(0) {} + SparseSet() : Sparse(nullptr), Universe(0) {} ~SparseSet() { free(Sparse); } /// setUniverse - Set the universe size which determines the largest key the diff --git a/include/llvm/ADT/Statistic.h b/include/llvm/ADT/Statistic.h index 26aac7bea6..d98abc375e 100644 --- a/include/llvm/ADT/Statistic.h +++ b/include/llvm/ADT/Statistic.h @@ -46,7 +46,7 @@ public: /// construct - This should only be called for non-global statistics. void construct(const char *name, const char *desc) { Name = name; Desc = desc; - Value = 0; Initialized = 0; + Value = 0; Initialized = false; } // Allow use of this class as the value itself. diff --git a/include/llvm/ADT/StringExtras.h b/include/llvm/ADT/StringExtras.h index a0b3fe7a06..a152f4d3c2 100644 --- a/include/llvm/ADT/StringExtras.h +++ b/include/llvm/ADT/StringExtras.h @@ -141,7 +141,7 @@ void SplitString(StringRef Source, // 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) + for (StringRef::size_type i = 0, e = Str.size(); i != e; ++i) Result = Result * 33 + (unsigned char)Str[i]; return Result; } diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 4e74cf6529..ecac5dd5f6 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -17,6 +17,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Support/Allocator.h" #include <cstring> +#include <utility> namespace llvm { template<typename ValueT> @@ -48,13 +49,20 @@ protected: unsigned NumTombstones; unsigned ItemSize; protected: - explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) { - // Initialize the map with zero buckets to allocation. - TheTable = 0; - NumBuckets = 0; - NumItems = 0; - NumTombstones = 0; + explicit StringMapImpl(unsigned itemSize) + : TheTable(nullptr), + // Initialize the map with zero buckets to allocation. + NumBuckets(0), NumItems(0), NumTombstones(0), ItemSize(itemSize) {} + StringMapImpl(StringMapImpl &&RHS) + : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets), + NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones), + ItemSize(RHS.ItemSize) { + RHS.TheTable = nullptr; + RHS.NumBuckets = 0; + RHS.NumItems = 0; + RHS.NumTombstones = 0; } + StringMapImpl(unsigned InitSize, unsigned ItemSize); void RehashTable(); @@ -109,8 +117,8 @@ public: explicit StringMapEntry(unsigned strLen) : StringMapEntryBase(strLen), second() {} - StringMapEntry(unsigned strLen, const ValueTy &V) - : StringMapEntryBase(strLen), second(V) {} + StringMapEntry(unsigned strLen, ValueTy V) + : StringMapEntryBase(strLen), second(std::move(V)) {} StringRef getKey() const { return StringRef(getKeyData(), getKeyLength()); @@ -146,7 +154,7 @@ public: static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment)); // Default construct the value. - new (NewItem) StringMapEntry(KeyLength, InitVal); + new (NewItem) StringMapEntry(KeyLength, std::move(InitVal)); // Copy the string information. char *StrBuffer = const_cast<char*>(NewItem->getKeyData()); @@ -166,7 +174,7 @@ public: static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, InitType InitVal) { MallocAllocator A; - return Create(KeyStart, KeyEnd, A, InitVal); + return Create(KeyStart, KeyEnd, A, std::move(InitVal)); } static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { @@ -198,8 +206,10 @@ public: template<typename AllocatorTy> void Destroy(AllocatorTy &Allocator) { // Free memory referenced by the item. + unsigned AllocSize = + static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1; this->~StringMapEntry(); - Allocator.Deallocate(this); + Allocator.Deallocate(static_cast<void *>(this), AllocSize); } /// Destroy this object, releasing memory back to the malloc allocator. @@ -231,23 +241,19 @@ public: : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {} - StringMap(const StringMap &RHS) - : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) { - assert(RHS.empty() && - "Copy ctor from non-empty stringmap not implemented yet!"); - (void)RHS; - } - void operator=(const StringMap &RHS) { - assert(RHS.empty() && - "assignment from non-empty stringmap not implemented yet!"); - (void)RHS; - clear(); + StringMap(StringMap &&RHS) + : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {} + + StringMap &operator=(StringMap RHS) { + StringMapImpl::swap(RHS); + std::swap(Allocator, RHS.Allocator); + return *this; } - typedef typename ReferenceAdder<AllocatorTy>::result AllocatorRefTy; - typedef typename ReferenceAdder<const AllocatorTy>::result AllocatorCRefTy; - AllocatorRefTy getAllocator() { return Allocator; } - AllocatorCRefTy getAllocator() const { return Allocator; } + // FIXME: Implement copy operations if/when they're needed. + + AllocatorTy &getAllocator() { return Allocator; } + const AllocatorTy &getAllocator() const { return Allocator; } typedef const char* key_type; typedef ValueTy mapped_type; @@ -330,7 +336,7 @@ public: if (Bucket && Bucket != getTombstoneVal()) { static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator); } - Bucket = 0; + Bucket = nullptr; } NumItems = 0; @@ -348,7 +354,7 @@ public: return *static_cast<MapEntryTy*>(Bucket); MapEntryTy *NewItem = - MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); + MapEntryTy::Create(Key.begin(), Key.end(), Allocator, std::move(Val)); if (Bucket == getTombstoneVal()) --NumTombstones; @@ -410,7 +416,7 @@ protected: public: typedef StringMapEntry<ValueTy> value_type; - StringMapConstIterator() : Ptr(0) { } + StringMapConstIterator() : Ptr(nullptr) { } explicit StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) @@ -443,7 +449,7 @@ public: private: void AdvancePastEmptyBuckets() { - while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal()) + while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) ++Ptr; } }; diff --git a/include/llvm/ADT/StringRef.h b/include/llvm/ADT/StringRef.h index 0514d7b196..1f413e8055 100644 --- a/include/llvm/ADT/StringRef.h +++ b/include/llvm/ADT/StringRef.h @@ -10,7 +10,6 @@ #ifndef LLVM_ADT_STRINGREF_H #define LLVM_ADT_STRINGREF_H -#include "llvm/Support/Allocator.h" #include <algorithm> #include <cassert> #include <cstring> @@ -70,7 +69,7 @@ namespace llvm { /// @{ /// Construct an empty string ref. - /*implicit*/ StringRef() : Data(0), Length(0) {} + /*implicit*/ StringRef() : Data(nullptr), Length(0) {} /// Construct a string ref from a cstring. /*implicit*/ StringRef(const char *Str) @@ -124,9 +123,9 @@ namespace llvm { return Data[Length-1]; } - // copy - Allocate copy in BumpPtrAllocator and return StringRef to it. - StringRef copy(BumpPtrAllocator &Allocator) { - char *S = Allocator.Allocate<char>(Length); + // copy - Allocate copy in Allocator and return StringRef to it. + template <typename Allocator> StringRef copy(Allocator &A) { + char *S = A.template Allocate<char>(Length); std::copy(begin(), end(), S); return StringRef(S, Length); } @@ -186,7 +185,7 @@ namespace llvm { /// str - Get the contents as an std::string. std::string str() const { - if (Data == 0) return std::string(); + if (!Data) return std::string(); return std::string(Data, Length); } diff --git a/include/llvm/ADT/StringSwitch.h b/include/llvm/ADT/StringSwitch.h index 7fd6e27960..0393a0c373 100644 --- a/include/llvm/ADT/StringSwitch.h +++ b/include/llvm/ADT/StringSwitch.h @@ -49,7 +49,7 @@ class StringSwitch { public: explicit StringSwitch(StringRef S) - : Str(S), Result(0) { } + : Str(S), Result(nullptr) { } template<unsigned N> StringSwitch& Case(const char (&S)[N], const T& Value) { diff --git a/include/llvm/ADT/TinyPtrVector.h b/include/llvm/ADT/TinyPtrVector.h index 1df8d661b4..5669b2a81a 100644 --- a/include/llvm/ADT/TinyPtrVector.h +++ b/include/llvm/ADT/TinyPtrVector.h @@ -69,7 +69,7 @@ public: } TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { - RHS.Val = (EltTy)0; + RHS.Val = (EltTy)nullptr; } TinyPtrVector &operator=(TinyPtrVector &&RHS) { if (this == &RHS) @@ -92,7 +92,7 @@ public: } Val = RHS.Val; - RHS.Val = (EltTy)0; + RHS.Val = (EltTy)nullptr; return *this; } @@ -174,7 +174,7 @@ public: } void push_back(EltTy NewVal) { - assert(NewVal != 0 && "Can't add a null value"); + assert(NewVal && "Can't add a null value"); // If we have nothing, add something. if (Val.isNull()) { @@ -195,7 +195,7 @@ public: void pop_back() { // If we have a single value, convert to empty. if (Val.template is<EltTy>()) - Val = (EltTy)0; + Val = (EltTy)nullptr; else if (VecTy *Vec = Val.template get<VecTy*>()) Vec->pop_back(); } @@ -203,7 +203,7 @@ public: void clear() { // If we have a single value, convert to empty. if (Val.template is<EltTy>()) { - Val = (EltTy)0; + Val = (EltTy)nullptr; } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { // If we have a vector form, just clear it. Vec->clear(); @@ -218,7 +218,7 @@ public: // If we have a single value, convert to empty. if (Val.template is<EltTy>()) { if (I == begin()) - Val = (EltTy)0; + Val = (EltTy)nullptr; } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { // multiple items in a vector; just do the erase, there is no // benefit to collapsing back to a pointer @@ -234,7 +234,7 @@ public: if (Val.template is<EltTy>()) { if (S == begin() && S != E) - Val = (EltTy)0; + Val = (EltTy)nullptr; } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { return Vec->erase(S, E); } diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h index 185003dc65..95f3380b36 100644 --- a/include/llvm/ADT/Triple.h +++ b/include/llvm/ADT/Triple.h @@ -48,7 +48,8 @@ public: arm, // ARM (little endian): arm, armv.*, xscale armeb, // ARM (big endian): armeb - arm64, // ARM: arm64 + arm64, // ARM64 (little endian): arm64 + arm64_be, // ARM64 (big endian): arm64_be aarch64, // AArch64 (little endian): aarch64 aarch64_be, // AArch64 (big endian): aarch64_be hexagon, // Hexagon: hexagon @@ -335,6 +336,10 @@ public: return isMacOSX() || isiOS(); } + bool isOSFreeBSD() const { + return getOS() == Triple::FreeBSD; + } + bool isWindowsMSVCEnvironment() const { return getOS() == Triple::Win32 && (getEnvironment() == Triple::UnknownEnvironment || @@ -362,7 +367,7 @@ public: /// \brief Is this a "Windows" OS targeting a "MSVCRT.dll" environment. bool isOSMSVCRT() const { - return getOS() == Triple::Win32 || getOS() == Triple::MinGW32; + return isWindowsMSVCEnvironment() || isWindowsGNUEnvironment(); } /// \brief Tests whether the OS is Windows. diff --git a/include/llvm/ADT/Twine.h b/include/llvm/ADT/Twine.h index e16c6b4913..a54fd743ad 100644 --- a/include/llvm/ADT/Twine.h +++ b/include/llvm/ADT/Twine.h @@ -374,7 +374,7 @@ namespace llvm { static Twine utohexstr(const uint64_t &Val) { Child LHS, RHS; LHS.uHex = &Val; - RHS.twine = 0; + RHS.twine = nullptr; return Twine(LHS, UHexKind, RHS, EmptyKind); } diff --git a/include/llvm/ADT/edit_distance.h b/include/llvm/ADT/edit_distance.h index f77ef13fef..9ee1edc54e 100644 --- a/include/llvm/ADT/edit_distance.h +++ b/include/llvm/ADT/edit_distance.h @@ -17,8 +17,8 @@ #define LLVM_ADT_EDIT_DISTANCE_H #include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/OwningPtr.h" #include <algorithm> +#include <memory> namespace llvm { @@ -57,7 +57,7 @@ unsigned ComputeEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray, const unsigned SmallBufferSize = 64; unsigned SmallBuffer[SmallBufferSize]; - llvm::OwningArrayPtr<unsigned> Allocated; + std::unique_ptr<unsigned[]> Allocated; unsigned *Previous = SmallBuffer; if (2*(n + 1) > SmallBufferSize) { Previous = new unsigned [2*(n+1)]; diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h index 6aeaa91f1b..bc148452f2 100644 --- a/include/llvm/ADT/ilist.h +++ b/include/llvm/ADT/ilist.h @@ -83,7 +83,7 @@ struct ilist_sentinel_traits { /// provideInitialHead - when constructing an ilist, provide a starting /// value for its Head /// @return null node to indicate that it needs to be allocated later - static NodeTy *provideInitialHead() { return 0; } + static NodeTy *provideInitialHead() { return nullptr; } /// ensureHead - make sure that Head is either already /// initialized or assigned a fresh sentinel @@ -92,7 +92,7 @@ struct ilist_sentinel_traits { if (!Head) { Head = ilist_traits<NodeTy>::createSentinel(); ilist_traits<NodeTy>::noteHead(Head, Head); - ilist_traits<NodeTy>::setNext(Head, 0); + ilist_traits<NodeTy>::setNext(Head, nullptr); return Head; } return ilist_traits<NodeTy>::getPrev(Head); @@ -175,7 +175,7 @@ public: ilist_iterator(pointer NP) : NodePtr(NP) {} ilist_iterator(reference NR) : NodePtr(&NR) {} - ilist_iterator() : NodePtr(0) {} + ilist_iterator() : NodePtr(nullptr) {} // This is templated so that we can allow constructing a const iterator from // a nonconst iterator... @@ -383,7 +383,7 @@ public: // Miscellaneous inspection routines. size_type max_size() const { return size_type(-1); } bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { - return Head == 0 || Head == getTail(); + return !Head || Head == getTail(); } // Front and back accessor functions... @@ -451,8 +451,8 @@ public: // an ilist (and potentially deleted) with iterators still pointing at it. // When those iterators are incremented or decremented, they will assert on // the null next/prev pointer instead of "usually working". - this->setNext(Node, 0); - this->setPrev(Node, 0); + this->setNext(Node, nullptr); + this->setPrev(Node, nullptr); return Node; } @@ -494,9 +494,9 @@ private: // Note: we have to be careful about the case when we move the first node // in the list. This node is the list sentinel node and we can't move it. NodeTy *ThisSentinel = getTail(); - setTail(0); + setTail(nullptr); NodeTy *L2Sentinel = L2.getTail(); - L2.setTail(0); + L2.setTail(nullptr); // Remove [first, last) from its old position. NodeTy *First = &*first, *Prev = this->getPrev(First); @@ -537,7 +537,7 @@ public: // size_type LLVM_ATTRIBUTE_UNUSED_RESULT size() const { - if (Head == 0) return 0; // Don't require construction of sentinel if empty. + if (!Head) return 0; // Don't require construction of sentinel if empty. return std::distance(begin(), end()); } diff --git a/include/llvm/ADT/ilist_node.h b/include/llvm/ADT/ilist_node.h index 03612440e7..85aa7a4b1f 100644 --- a/include/llvm/ADT/ilist_node.h +++ b/include/llvm/ADT/ilist_node.h @@ -30,7 +30,7 @@ protected: NodeTy *getPrev() { return Prev; } const NodeTy *getPrev() const { return Prev; } void setPrev(NodeTy *P) { Prev = P; } - ilist_half_node() : Prev(0) {} + ilist_half_node() : Prev(nullptr) {} }; template<typename NodeTy> @@ -48,7 +48,7 @@ class ilist_node : private ilist_half_node<NodeTy> { const NodeTy *getNext() const { return Next; } void setNext(NodeTy *N) { Next = N; } protected: - ilist_node() : Next(0) {} + ilist_node() : Next(nullptr) {} public: /// @name Adjacent Node Accessors @@ -60,7 +60,7 @@ public: // Check for sentinel. if (!Prev->getNext()) - return 0; + return nullptr; return Prev; } @@ -71,7 +71,7 @@ public: // Check for sentinel. if (!Prev->getNext()) - return 0; + return nullptr; return Prev; } @@ -82,7 +82,7 @@ public: // Check for sentinel. if (!Next->getNext()) - return 0; + return nullptr; return Next; } @@ -93,7 +93,7 @@ public: // Check for sentinel. if (!Next->getNext()) - return 0; + return nullptr; return Next; } diff --git a/include/llvm/ADT/iterator.h b/include/llvm/ADT/iterator.h new file mode 100644 index 0000000000..56041dbb10 --- /dev/null +++ b/include/llvm/ADT/iterator.h @@ -0,0 +1,244 @@ +//===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ITERATOR_H +#define LLVM_ADT_ITERATOR_H + +#include <iterator> +#include <cstddef> + +namespace llvm { + +/// \brief CRTP base class which implements the entire standard iterator facade +/// in terms of a minimal subset of the interface. +/// +/// Use this when it is reasonable to implement most of the iterator +/// functionality in terms of a core subset. If you need special behavior or +/// there are performance implications for this, you may want to override the +/// relevant members instead. +/// +/// Note, one abstraction that this does *not* provide is implementing +/// subtraction in terms of addition by negating the difference. Negation isn't +/// always information preserving, and I can see very reasonable iterator +/// designs where this doesn't work well. It doesn't really force much added +/// boilerplate anyways. +/// +/// Another abstraction that this doesn't provide is implementing increment in +/// terms of addition of one. These aren't equivalent for all iterator +/// categories, and respecting that adds a lot of complexity for little gain. +template <typename DerivedT, typename IteratorCategoryT, typename T, + typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *, + typename ReferenceT = T &> +class iterator_facade_base + : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT, + ReferenceT> { +protected: + enum { + IsRandomAccess = + std::is_base_of<std::random_access_iterator_tag, IteratorCategoryT>::value, + IsBidirectional = + std::is_base_of<std::bidirectional_iterator_tag, IteratorCategoryT>::value, + }; + +public: + DerivedT operator+(DifferenceTypeT n) const { + static_assert( + IsRandomAccess, + "The '+' operator is only defined for random access iterators."); + DerivedT tmp = *static_cast<const DerivedT *>(this); + tmp += n; + return tmp; + } + friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { + static_assert( + IsRandomAccess, + "The '+' operator is only defined for random access iterators."); + return i + n; + } + DerivedT operator-(DifferenceTypeT n) const { + static_assert( + IsRandomAccess, + "The '-' operator is only defined for random access iterators."); + DerivedT tmp = *static_cast<const DerivedT *>(this); + tmp -= n; + return tmp; + } + + DerivedT &operator++() { + return static_cast<DerivedT *>(this)->operator+=(1); + } + DerivedT operator++(int) { + DerivedT tmp = *static_cast<DerivedT *>(this); + ++*static_cast<DerivedT *>(this); + return tmp; + } + DerivedT &operator--() { + static_assert( + IsBidirectional, + "The decrement operator is only defined for bidirectional iterators."); + return static_cast<DerivedT *>(this)->operator-=(1); + } + DerivedT operator--(int) { + static_assert( + IsBidirectional, + "The decrement operator is only defined for bidirectional iterators."); + DerivedT tmp = *static_cast<DerivedT *>(this); + --*static_cast<DerivedT *>(this); + return tmp; + } + + bool operator!=(const DerivedT &RHS) const { + return !static_cast<const DerivedT *>(this)->operator==(RHS); + } + + bool operator>(const DerivedT &RHS) const { + static_assert( + IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return !static_cast<const DerivedT *>(this)->operator<(RHS) && + !static_cast<const DerivedT *>(this)->operator==(RHS); + } + bool operator<=(const DerivedT &RHS) const { + static_assert( + IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return !static_cast<const DerivedT *>(this)->operator>(RHS); + } + bool operator>=(const DerivedT &RHS) const { + static_assert( + IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return !static_cast<const DerivedT *>(this)->operator<(RHS); + } + + PointerT operator->() const { + return &static_cast<const DerivedT *>(this)->operator*(); + } + ReferenceT operator[](DifferenceTypeT n) const { + static_assert(IsRandomAccess, + "Subscripting is only defined for random access iterators."); + return *static_cast<const DerivedT *>(this)->operator+(n); + } +}; + +/// \brief CRTP base class for adapting an iterator to a different type. +/// +/// This class can be used through CRTP to adapt one iterator into another. +/// Typically this is done through providing in the derived class a custom \c +/// operator* implementation. Other methods can be overridden as well. +template < + typename DerivedT, typename WrappedIteratorT, + typename IteratorCategoryT = + typename std::iterator_traits<WrappedIteratorT>::iterator_category, + typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, + typename DifferenceTypeT = + typename std::iterator_traits<WrappedIteratorT>::difference_type, + typename PointerT = T *, typename ReferenceT = T &, + // Don't provide these, they are mostly to act as aliases below. + typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>> +class iterator_adaptor_base + : public iterator_facade_base<DerivedT, IteratorCategoryT, T, + DifferenceTypeT, PointerT, ReferenceT> { + typedef typename iterator_adaptor_base::iterator_facade_base BaseT; + +protected: + WrappedIteratorT I; + + iterator_adaptor_base() {} + + template <typename U> + explicit iterator_adaptor_base( + U &&u, + typename std::enable_if< + !std::is_base_of<typename std::remove_cv< + typename std::remove_reference<U>::type>::type, + DerivedT>::value, + int>::type = 0) + : I(std::forward<U &&>(u)) {} + +public: + typedef DifferenceTypeT difference_type; + + DerivedT &operator+=(difference_type n) { + static_assert( + BaseT::IsRandomAccess, + "The '+=' operator is only defined for random access iterators."); + I += n; + return *static_cast<DerivedT *>(this); + } + DerivedT &operator-=(difference_type n) { + static_assert( + BaseT::IsRandomAccess, + "The '-=' operator is only defined for random access iterators."); + I -= n; + return *static_cast<DerivedT *>(this); + } + using BaseT::operator-; + difference_type operator-(const DerivedT &RHS) const { + static_assert( + BaseT::IsRandomAccess, + "The '-' operator is only defined for random access iterators."); + return I - RHS.I; + } + + // We have to explicitly provide ++ and -- rather than letting the facade + // forward to += because WrappedIteratorT might not support +=. + using BaseT::operator++; + DerivedT &operator++() { + ++I; + return *static_cast<DerivedT *>(this); + } + using BaseT::operator--; + DerivedT &operator--() { + static_assert( + BaseT::IsBidirectional, + "The decrement operator is only defined for bidirectional iterators."); + --I; + return *static_cast<DerivedT *>(this); + } + + bool operator==(const DerivedT &RHS) const { return I == RHS.I; } + bool operator<(const DerivedT &RHS) const { + static_assert( + BaseT::IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return I < RHS.I; + } + + ReferenceT operator*() const { return *I; } +}; + +/// \brief An iterator type that allows iterating over the pointees via some +/// other iterator. +/// +/// The typical usage of this is to expose a type that iterates over Ts, but +/// which is implemented with some iterator over T*s: +/// +/// \code +/// typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator; +/// \endcode +template <typename WrappedIteratorT, + typename T = typename std::remove_reference< + decltype(**std::declval<WrappedIteratorT>())>::type> +struct pointee_iterator + : iterator_adaptor_base< + pointee_iterator<WrappedIteratorT>, WrappedIteratorT, + typename std::iterator_traits<WrappedIteratorT>::iterator_category, + T> { + pointee_iterator() {} + template <typename U> + pointee_iterator(U &&u) + : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} + + T &operator*() const { return **this->I; } +}; + +} + +#endif diff --git a/include/llvm/ADT/iterator_range.h b/include/llvm/ADT/iterator_range.h index 4f2f3218f3..dd17d6c8f7 100644 --- a/include/llvm/ADT/iterator_range.h +++ b/include/llvm/ADT/iterator_range.h @@ -40,6 +40,14 @@ public: IteratorT begin() const { return begin_iterator; } IteratorT end() const { return end_iterator; } }; + +/// \brief Convenience function for iterating over sub-ranges. +/// +/// This provides a bit of syntactic sugar to make using sub-ranges +/// in for loops a bit easier. Analogous to std::make_pair(). +template <class T> iterator_range<T> make_range(T x, T y) { + return iterator_range<T>(std::move(x), std::move(y)); +} } #endif |