diff options
Diffstat (limited to 'include/llvm/ADT/SmallPtrSet.h')
| -rw-r--r-- | include/llvm/ADT/SmallPtrSet.h | 125 |
1 files changed, 106 insertions, 19 deletions
diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index eaed6aa05dcb..49feb9da897a 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -15,19 +15,25 @@ #ifndef LLVM_ADT_SMALLPTRSET_H #define LLVM_ADT_SMALLPTRSET_H +#include "llvm/Config/abi-breaking.h" #include "llvm/Support/Compiler.h" -#include "llvm/Support/DataTypes.h" #include "llvm/Support/PointerLikeTypeTraits.h" #include <cassert> #include <cstddef> #include <cstring> #include <cstdlib> +#include <initializer_list> #include <iterator> #include <utility> +#if LLVM_ENABLE_ABI_BREAKING_CHECKS namespace llvm { +template <class T = void> struct ReverseIterate { static bool value; }; +template <class T> bool ReverseIterate<T>::value = false; +} +#endif -class SmallPtrSetIteratorImpl; +namespace llvm { /// SmallPtrSetImplBase - This is the common code shared among all the /// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one @@ -71,12 +77,14 @@ protected: const SmallPtrSetImplBase &that); SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize, SmallPtrSetImplBase &&that); + explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) : SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && "Initial size must be a power of two!"); } + ~SmallPtrSetImplBase() { if (!isSmall()) free(CurArray); @@ -84,7 +92,10 @@ protected: public: typedef unsigned size_type; - bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return size() == 0; } + + SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete; + + LLVM_NODISCARD bool empty() const { return size() == 0; } size_type size() const { return NumNonEmpty - NumTombstones; } void clear() { @@ -103,6 +114,7 @@ public: protected: static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); } + static void *getEmptyMarker() { // Note that -1 is chosen to make clear() efficiently implementable with // memset and because it's not a valid pointer value. @@ -150,22 +162,38 @@ protected: /// return true, otherwise return false. This is hidden from the client so /// that the derived class can check that the right type of pointer is passed /// in. - bool erase_imp(const void * Ptr); + bool erase_imp(const void * Ptr) { + const void *const *P = find_imp(Ptr); + if (P == EndPointer()) + return false; + + const void ** Loc = const_cast<const void **>(P); + assert(*Loc == Ptr && "broken find!"); + *Loc = getTombstoneMarker(); + NumTombstones++; + return true; + } - bool count_imp(const void * Ptr) const { + /// Returns the raw pointer needed to construct an iterator. If element not + /// found, this will be EndPointer. Otherwise, it will be a pointer to the + /// slot which stores Ptr; + const void *const * find_imp(const void * Ptr) const { if (isSmall()) { // Linear search for the item. for (const void *const *APtr = SmallArray, *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr) if (*APtr == Ptr) - return true; - return false; + return APtr; + return EndPointer(); } // Big set case. - return *FindBucketFor(Ptr) == Ptr; + auto *Bucket = FindBucketFor(Ptr); + if (*Bucket == Ptr) + return Bucket; + return EndPointer(); } - + private: bool isSmall() const { return CurArray == SmallArray; } @@ -177,8 +205,6 @@ private: /// Grow - Allocate a larger backing store for the buckets and move it over. void Grow(unsigned NewSize); - void operator=(const SmallPtrSetImplBase &RHS) = delete; - protected: /// swap - Swaps the elements of two sets. /// Note: This method assumes that both sets have the same small size. @@ -204,6 +230,12 @@ protected: public: explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) : Bucket(BP), End(E) { +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIterate<bool>::value) { + RetreatIfNotValid(); + return; + } +#endif AdvanceIfNotValid(); } @@ -225,6 +257,17 @@ protected: *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) ++Bucket; } +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + void RetreatIfNotValid() { + --Bucket; + assert(Bucket <= End); + while (Bucket != End && + (*Bucket == SmallPtrSetImplBase::getEmptyMarker() || + *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) { + --Bucket; + } + } +#endif }; /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. @@ -250,13 +293,21 @@ public: } inline SmallPtrSetIterator& operator++() { // Preincrement +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIterate<bool>::value) { + RetreatIfNotValid(); + return *this; + } +#endif ++Bucket; AdvanceIfNotValid(); return *this; } SmallPtrSetIterator operator++(int) { // Postincrement - SmallPtrSetIterator tmp = *this; ++*this; return tmp; + SmallPtrSetIterator tmp = *this; + ++*this; + return tmp; } }; @@ -294,8 +345,6 @@ template <typename PtrType> class SmallPtrSetImpl : public SmallPtrSetImplBase { typedef PointerLikeTypeTraits<PtrType> PtrTraits; - SmallPtrSetImpl(const SmallPtrSetImpl &) = delete; - protected: // Constructors that forward to the base. SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that) @@ -310,6 +359,8 @@ public: typedef SmallPtrSetIterator<PtrType> iterator; typedef SmallPtrSetIterator<PtrType> const_iterator; + SmallPtrSetImpl(const SmallPtrSetImpl &) = delete; + /// Inserts Ptr if and only if there is no element in the container equal to /// Ptr. The bool component of the returned pair is true if and only if the /// insertion takes place, and the iterator component of the pair points to @@ -327,7 +378,11 @@ public: /// count - Return 1 if the specified pointer is in the set, 0 otherwise. size_type count(PtrType Ptr) const { - return count_imp(PtrTraits::getAsVoidPointer(Ptr)) ? 1 : 0; + return find(Ptr) != endPtr() ? 1 : 0; + } + iterator find(PtrType Ptr) const { + auto *P = find_imp(PtrTraits::getAsVoidPointer(Ptr)); + return iterator(P, EndPointer()); } template <typename IterT> @@ -336,10 +391,27 @@ public: insert(*I); } + void insert(std::initializer_list<PtrType> IL) { + insert(IL.begin(), IL.end()); + } + inline iterator begin() const { +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIterate<bool>::value) + return endPtr(); +#endif return iterator(CurArray, EndPointer()); } inline iterator end() const { +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIterate<bool>::value) + return iterator(CurArray, CurArray); +#endif + return endPtr(); + } + +private: + inline iterator endPtr() const { const void *const *End = EndPointer(); return iterator(End, End); } @@ -374,6 +446,11 @@ public: this->insert(I, E); } + SmallPtrSet(std::initializer_list<PtrType> IL) + : BaseT(SmallStorage, SmallSizePowTwo) { + this->insert(IL.begin(), IL.end()); + } + SmallPtrSet<PtrType, SmallSize> & operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) { if (&RHS != this) @@ -381,26 +458,36 @@ public: return *this; } - SmallPtrSet<PtrType, SmallSize>& + SmallPtrSet<PtrType, SmallSize> & operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) { if (&RHS != this) this->MoveFrom(SmallSizePowTwo, std::move(RHS)); return *this; } + SmallPtrSet<PtrType, SmallSize> & + operator=(std::initializer_list<PtrType> IL) { + this->clear(); + this->insert(IL.begin(), IL.end()); + return *this; + } + /// swap - Swaps the elements of two sets. void swap(SmallPtrSet<PtrType, SmallSize> &RHS) { SmallPtrSetImplBase::swap(RHS); } }; -} + +} // end namespace llvm namespace std { + /// Implement std::swap in terms of SmallPtrSet swap. template<class T, unsigned N> inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) { LHS.swap(RHS); } -} -#endif +} // end namespace std + +#endif // LLVM_ADT_SMALLPTRSET_H |