LCOV - code coverage report
Current view: top level - include/llvm/ADT - SmallPtrSet.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 102 102 100.0 %
Date: 2017-09-14 15:23:50 Functions: 599 610 98.2 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the SmallPtrSet class.  See the doxygen comment for
      11             : // SmallPtrSetImplBase for more details on the algorithm used.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_ADT_SMALLPTRSET_H
      16             : #define LLVM_ADT_SMALLPTRSET_H
      17             : 
      18             : #include "llvm/Support/Compiler.h"
      19             : #include "llvm/Support/ReverseIteration.h"
      20             : #include "llvm/Support/type_traits.h"
      21             : #include <cassert>
      22             : #include <cstddef>
      23             : #include <cstdlib>
      24             : #include <cstring>
      25             : #include <initializer_list>
      26             : #include <iterator>
      27             : #include <utility>
      28             : 
      29             : namespace llvm {
      30             : 
      31             : /// SmallPtrSetImplBase - This is the common code shared among all the
      32             : /// SmallPtrSet<>'s, which is almost everything.  SmallPtrSet has two modes, one
      33             : /// for small and one for large sets.
      34             : ///
      35             : /// Small sets use an array of pointers allocated in the SmallPtrSet object,
      36             : /// which is treated as a simple array of pointers.  When a pointer is added to
      37             : /// the set, the array is scanned to see if the element already exists, if not
      38             : /// the element is 'pushed back' onto the array.  If we run out of space in the
      39             : /// array, we grow into the 'large set' case.  SmallSet should be used when the
      40             : /// sets are often small.  In this case, no memory allocation is used, and only
      41             : /// light-weight and cache-efficient scanning is used.
      42             : ///
      43             : /// Large sets use a classic exponentially-probed hash table.  Empty buckets are
      44             : /// represented with an illegal pointer value (-1) to allow null pointers to be
      45             : /// inserted.  Tombstones are represented with another illegal pointer value
      46             : /// (-2), to allow deletion.  The hash table is resized when the table is 3/4 or
      47             : /// more.  When this happens, the table is doubled in size.
      48             : ///
      49             : class SmallPtrSetImplBase {
      50             :   friend class SmallPtrSetIteratorImpl;
      51             : 
      52             : protected:
      53             :   /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
      54             :   const void **SmallArray;
      55             :   /// CurArray - This is the current set of buckets.  If equal to SmallArray,
      56             :   /// then the set is in 'small mode'.
      57             :   const void **CurArray;
      58             :   /// CurArraySize - The allocated size of CurArray, always a power of two.
      59             :   unsigned CurArraySize;
      60             : 
      61             :   /// Number of elements in CurArray that contain a value or are a tombstone.
      62             :   /// If small, all these elements are at the beginning of CurArray and the rest
      63             :   /// is uninitialized.
      64             :   unsigned NumNonEmpty;
      65             :   /// Number of tombstones in CurArray.
      66             :   unsigned NumTombstones;
      67             : 
      68             :   // Helpers to copy and move construct a SmallPtrSet.
      69             :   SmallPtrSetImplBase(const void **SmallStorage,
      70             :                       const SmallPtrSetImplBase &that);
      71             :   SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
      72             :                       SmallPtrSetImplBase &&that);
      73             : 
      74             :   explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
      75   274724297 :       : SmallArray(SmallStorage), CurArray(SmallStorage),
      76   280920540 :         CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) {
      77             :     assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
      78             :            "Initial size must be a power of two!");
      79             :   }
      80             : 
      81             :   ~SmallPtrSetImplBase() {
      82   322248720 :     if (!isSmall())
      83     1646863 :       free(CurArray);
      84             :   }
      85             : 
      86             : public:
      87             :   using size_type = unsigned;
      88             : 
      89             :   SmallPtrSetImplBase &operator=(const SmallPtrSetImplBase &) = delete;
      90             : 
      91   145485901 :   LLVM_NODISCARD bool empty() const { return size() == 0; }
      92  1162888517 :   size_type size() const { return NumNonEmpty - NumTombstones; }
      93             : 
      94    48506627 :   void clear() {
      95             :     // If the capacity of the array is huge, and the # elements used is small,
      96             :     // shrink the array.
      97    48506627 :     if (!isSmall()) {
      98     3074550 :       if (size() * 4 < CurArraySize && CurArraySize > 32)
      99       41379 :         return shrink_and_clear();
     100             :       // Fill the array with empty markers.
     101     1495896 :       memset(CurArray, -1, CurArraySize * sizeof(void *));
     102             :     }
     103             : 
     104    48465248 :     NumNonEmpty = 0;
     105    48465248 :     NumTombstones = 0;
     106             :   }
     107             : 
     108             : protected:
     109             :   static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
     110             : 
     111             :   static void *getEmptyMarker() {
     112             :     // Note that -1 is chosen to make clear() efficiently implementable with
     113             :     // memset and because it's not a valid pointer value.
     114             :     return reinterpret_cast<void*>(-1);
     115             :   }
     116             : 
     117             :   const void **EndPointer() const {
     118  2057673227 :     return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize;
     119             :   }
     120             : 
     121             :   /// insert_imp - This returns true if the pointer was new to the set, false if
     122             :   /// it was already in the set.  This is hidden from the client so that the
     123             :   /// derived class can check that the right type of pointer is passed in.
     124  1149471385 :   std::pair<const void *const *, bool> insert_imp(const void *Ptr) {
     125  1149471385 :     if (isSmall()) {
     126             :       // Check to see if it is already in the set.
     127   281011491 :       const void **LastTombstone = nullptr;
     128  1017554900 :       for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty;
     129  1017554900 :            APtr != E; ++APtr) {
     130   756050829 :         const void *Value = *APtr;
     131   756050829 :         if (Value == Ptr)
     132    58522260 :           return std::make_pair(APtr, false);
     133   736543409 :         if (Value == getTombstoneMarker())
     134     5917214 :           LastTombstone = APtr;
     135             :       }
     136             : 
     137             :       // Did we find any tombstone marker?
     138   261504071 :       if (LastTombstone != nullptr) {
     139     2993374 :         *LastTombstone = Ptr;
     140     2993374 :         --NumTombstones;
     141     8980122 :         return std::make_pair(LastTombstone, true);
     142             :       }
     143             : 
     144             :       // Nope, there isn't.  If we stay small, just 'pushback' now.
     145   258510697 :       if (NumNonEmpty < CurArraySize) {
     146   256928630 :         SmallArray[NumNonEmpty++] = Ptr;
     147   770785890 :         return std::make_pair(SmallArray + (NumNonEmpty - 1), true);
     148             :       }
     149             :       // Otherwise, hit the big set case, which will call grow.
     150             :     }
     151   870041961 :     return insert_imp_big(Ptr);
     152             :   }
     153             : 
     154             :   /// erase_imp - If the set contains the specified pointer, remove it and
     155             :   /// return true, otherwise return false.  This is hidden from the client so
     156             :   /// that the derived class can check that the right type of pointer is passed
     157             :   /// in.
     158    14276936 :   bool erase_imp(const void * Ptr) {
     159    14276936 :     const void *const *P = find_imp(Ptr);
     160    14276935 :     if (P == EndPointer())
     161             :       return false;
     162             : 
     163     6641649 :     const void **Loc = const_cast<const void **>(P);
     164             :     assert(*Loc == Ptr && "broken find!");
     165     6641649 :     *Loc = getTombstoneMarker();
     166     6641649 :     NumTombstones++;
     167     6641649 :     return true;
     168             :   }
     169             : 
     170             :   /// Returns the raw pointer needed to construct an iterator.  If element not
     171             :   /// found, this will be EndPointer.  Otherwise, it will be a pointer to the
     172             :   /// slot which stores Ptr;
     173   217831831 :   const void *const * find_imp(const void * Ptr) const {
     174   217831831 :     if (isSmall()) {
     175             :       // Linear search for the item.
     176   719761698 :       for (const void *const *APtr = SmallArray,
     177   139594411 :                       *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr)
     178   613322841 :         if (*APtr == Ptr)
     179             :           return APtr;
     180   106438857 :       return EndPointer();
     181             :     }
     182             : 
     183             :     // Big set case.
     184    78237420 :     auto *Bucket = FindBucketFor(Ptr);
     185    78237420 :     if (*Bucket == Ptr)
     186             :       return Bucket;
     187             :     return EndPointer();
     188             :   }
     189             : 
     190             : private:
     191             :   bool isSmall() const { return CurArray == SmallArray; }
     192             : 
     193             :   std::pair<const void *const *, bool> insert_imp_big(const void *Ptr);
     194             : 
     195             :   const void * const *FindBucketFor(const void *Ptr) const;
     196             :   void shrink_and_clear();
     197             : 
     198             :   /// Grow - Allocate a larger backing store for the buckets and move it over.
     199             :   void Grow(unsigned NewSize);
     200             : 
     201             : protected:
     202             :   /// swap - Swaps the elements of two sets.
     203             :   /// Note: This method assumes that both sets have the same small size.
     204             :   void swap(SmallPtrSetImplBase &RHS);
     205             : 
     206             :   void CopyFrom(const SmallPtrSetImplBase &RHS);
     207             :   void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
     208             : 
     209             : private:
     210             :   /// Code shared by MoveFrom() and move constructor.
     211             :   void MoveHelper(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
     212             :   /// Code shared by CopyFrom() and copy constructor.
     213             :   void CopyHelper(const SmallPtrSetImplBase &RHS);
     214             : };
     215             : 
     216             : /// SmallPtrSetIteratorImpl - This is the common base class shared between all
     217             : /// instances of SmallPtrSetIterator.
     218             : class SmallPtrSetIteratorImpl {
     219             : protected:
     220             :   const void *const *Bucket;
     221             :   const void *const *End;
     222             : 
     223             : public:
     224             :   explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
     225             :     : Bucket(BP), End(E) {
     226             :     if (shouldReverseIterate()) {
     227             :       RetreatIfNotValid();
     228             :       return;
     229             :     }
     230             :     AdvanceIfNotValid();
     231             :   }
     232             : 
     233             :   bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
     234         218 :     return Bucket == RHS.Bucket;
     235             :   }
     236             :   bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
     237       12262 :     return Bucket != RHS.Bucket;
     238             :   }
     239             : 
     240             : protected:
     241             :   /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
     242             :   /// that is.   This is guaranteed to stop because the end() bucket is marked
     243             :   /// valid.
     244             :   void AdvanceIfNotValid() {
     245             :     assert(Bucket <= End);
     246  3028363286 :     while (Bucket != End &&
     247  2558901803 :            (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
     248             :             *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
     249    49452621 :       ++Bucket;
     250             :   }
     251             :   void RetreatIfNotValid() {
     252             :     assert(Bucket >= End);
     253             :     while (Bucket != End &&
     254             :            (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() ||
     255             :             Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) {
     256             :       --Bucket;
     257             :     }
     258             :   }
     259             : };
     260             : 
     261             : /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
     262             : template<typename PtrTy>
     263             : class SmallPtrSetIterator : public SmallPtrSetIteratorImpl {
     264             :   using PtrTraits = PointerLikeTypeTraits<PtrTy>;
     265             : 
     266             : public:
     267             :   using value_type = PtrTy;
     268             :   using reference = PtrTy;
     269             :   using pointer = PtrTy;
     270             :   using difference_type = std::ptrdiff_t;
     271             :   using iterator_category = std::forward_iterator_tag;
     272             : 
     273             :   explicit SmallPtrSetIterator(const void *const *BP, const void *const *E)
     274  3025314528 :     : SmallPtrSetIteratorImpl(BP, E) {}
     275             : 
     276             :   // Most methods provided by baseclass.
     277             : 
     278             :   const PtrTy operator*() const {
     279             :     if (shouldReverseIterate()) {
     280             :       assert(Bucket > End);
     281             :       return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));
     282             :     }
     283             :     assert(Bucket < End);
     284    42556733 :     return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
     285             :   }
     286             : 
     287             :   inline SmallPtrSetIterator& operator++() {          // Preincrement
     288             :     if (shouldReverseIterate()) {
     289             :       --Bucket;
     290             :       RetreatIfNotValid();
     291             :       return *this;
     292             :     }
     293    41764989 :     ++Bucket;
     294    41811195 :     AdvanceIfNotValid();
     295             :     return *this;
     296             :   }
     297             : 
     298             :   SmallPtrSetIterator operator++(int) {        // Postincrement
     299             :     SmallPtrSetIterator tmp = *this;
     300             :     ++*this;
     301             :     return tmp;
     302             :   }
     303             : };
     304             : 
     305             : /// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next
     306             : /// power of two (which means N itself if N is already a power of two).
     307             : template<unsigned N>
     308             : struct RoundUpToPowerOfTwo;
     309             : 
     310             : /// RoundUpToPowerOfTwoH - If N is not a power of two, increase it.  This is a
     311             : /// helper template used to implement RoundUpToPowerOfTwo.
     312             : template<unsigned N, bool isPowerTwo>
     313             : struct RoundUpToPowerOfTwoH {
     314             :   enum { Val = N };
     315             : };
     316             : template<unsigned N>
     317             : struct RoundUpToPowerOfTwoH<N, false> {
     318             :   enum {
     319             :     // We could just use NextVal = N+1, but this converges faster.  N|(N-1) sets
     320             :     // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
     321             :     Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val
     322             :   };
     323             : };
     324             : 
     325             : template<unsigned N>
     326             : struct RoundUpToPowerOfTwo {
     327             :   enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
     328             : };
     329             : 
     330             : /// \brief A templated base class for \c SmallPtrSet which provides the
     331             : /// typesafe interface that is common across all small sizes.
     332             : ///
     333             : /// This is particularly useful for passing around between interface boundaries
     334             : /// to avoid encoding a particular small size in the interface boundary.
     335             : template <typename PtrType>
     336   644497380 : class SmallPtrSetImpl : public SmallPtrSetImplBase {
     337             :   using ConstPtrType = typename add_const_past_pointer<PtrType>::type;
     338             :   using PtrTraits = PointerLikeTypeTraits<PtrType>;
     339             :   using ConstPtrTraits = PointerLikeTypeTraits<ConstPtrType>;
     340             : 
     341             : protected:
     342             :   // Constructors that forward to the base.
     343     7749677 :   SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that)
     344    16757323 :       : SmallPtrSetImplBase(SmallStorage, that) {}
     345    24574265 :   SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize,
     346             :                   SmallPtrSetImpl &&that)
     347    24683524 :       : SmallPtrSetImplBase(SmallStorage, SmallSize, std::move(that)) {}
     348             :   explicit SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize)
     349   561841080 :       : SmallPtrSetImplBase(SmallStorage, SmallSize) {}
     350             : 
     351             : public:
     352             :   using iterator = SmallPtrSetIterator<PtrType>;
     353             :   using const_iterator = SmallPtrSetIterator<PtrType>;
     354             :   using key_type = ConstPtrType;
     355             :   using value_type = PtrType;
     356             : 
     357             :   SmallPtrSetImpl(const SmallPtrSetImpl &) = delete;
     358             : 
     359             :   /// Inserts Ptr if and only if there is no element in the container equal to
     360             :   /// Ptr. The bool component of the returned pair is true if and only if the
     361             :   /// insertion takes place, and the iterator component of the pair points to
     362             :   /// the element equal to Ptr.
     363  1149471386 :   std::pair<iterator, bool> insert(PtrType Ptr) {
     364  2080829550 :     auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));
     365  3448414176 :     return std::make_pair(makeIterator(p.first), p.second);
     366             :   }
     367             : 
     368             :   /// erase - If the set contains the specified pointer, remove it and return
     369             :   /// true, otherwise return false.
     370             :   bool erase(PtrType Ptr) {
     371    18278092 :     return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
     372             :   }
     373             :   /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
     374   203524264 :   size_type count(ConstPtrType Ptr) const { return find(Ptr) != end() ? 1 : 0; }
     375   203554895 :   iterator find(ConstPtrType Ptr) const {
     376   610646764 :     return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));
     377             :   }
     378             : 
     379             :   template <typename IterT>
     380      903691 :   void insert(IterT I, IterT E) {
     381     6911766 :     for (; I != E; ++I)
     382     2404731 :       insert(*I);
     383      903691 :   }
     384             : 
     385           1 :   void insert(std::initializer_list<PtrType> IL) {
     386           2 :     insert(IL.begin(), IL.end());
     387           1 :   }
     388             : 
     389    38672792 :   iterator begin() const {
     390             :     if (shouldReverseIterate())
     391             :       return makeIterator(EndPointer() - 1);
     392    38672792 :     return makeIterator(CurArray);
     393             :   }
     394   725749104 :   iterator end() const { return makeIterator(EndPointer()); }
     395             : 
     396             : private:
     397             :   /// Create an iterator that dereferences to same place as the given pointer.
     398             :   iterator makeIterator(const void *const *P) const {
     399             :     if (shouldReverseIterate())
     400             :       return iterator(P == EndPointer() ? CurArray : P + 1, CurArray);
     401  4658929976 :     return iterator(P, EndPointer());
     402             :   }
     403             : };
     404             : 
     405             : /// SmallPtrSet - This class implements a set which is optimized for holding
     406             : /// SmallSize or less elements.  This internally rounds up SmallSize to the next
     407             : /// power of two if it is not already a power of two.  See the comments above
     408             : /// SmallPtrSetImplBase for details of the algorithm.
     409             : template<class PtrType, unsigned SmallSize>
     410   644494147 : class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
     411             :   // In small mode SmallPtrSet uses linear search for the elements, so it is
     412             :   // not a good idea to choose this value too high. You may consider using a
     413             :   // DenseSet<> instead if you expect many elements in the set.
     414             :   static_assert(SmallSize <= 32, "SmallSize should be small");
     415             : 
     416             :   using BaseT = SmallPtrSetImpl<PtrType>;
     417             : 
     418             :   // Make sure that SmallSize is a power of two, round up if not.
     419             :   enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
     420             :   /// SmallStorage - Fixed size storage used in 'small mode'.
     421             :   const void *SmallStorage[SmallSizePowTwo];
     422             : 
     423             : public:
     424   561011594 :   SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
     425    33514645 :   SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
     426    24574265 :   SmallPtrSet(SmallPtrSet &&that)
     427    49367048 :       : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
     428             : 
     429             :   template<typename It>
     430      829462 :   SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
     431      789962 :     this->insert(I, E);
     432      375231 :   }
     433             : 
     434          12 :   SmallPtrSet(std::initializer_list<PtrType> IL)
     435          24 :       : BaseT(SmallStorage, SmallSizePowTwo) {
     436          36 :     this->insert(IL.begin(), IL.end());
     437          12 :   }
     438             : 
     439             :   SmallPtrSet<PtrType, SmallSize> &
     440             :   operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
     441      169545 :     if (&RHS != this)
     442      212050 :       this->CopyFrom(RHS);
     443             :     return *this;
     444             :   }
     445             : 
     446             :   SmallPtrSet<PtrType, SmallSize> &
     447             :   operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) {
     448        5772 :     if (&RHS != this)
     449        5773 :       this->MoveFrom(SmallSizePowTwo, std::move(RHS));
     450             :     return *this;
     451             :   }
     452             : 
     453             :   SmallPtrSet<PtrType, SmallSize> &
     454           1 :   operator=(std::initializer_list<PtrType> IL) {
     455           1 :     this->clear();
     456           3 :     this->insert(IL.begin(), IL.end());
     457           1 :     return *this;
     458             :   }
     459             : 
     460             :   /// swap - Swaps the elements of two sets.
     461             :   void swap(SmallPtrSet<PtrType, SmallSize> &RHS) {
     462    11677756 :     SmallPtrSetImplBase::swap(RHS);
     463             :   }
     464             : };
     465             : 
     466             : } // end namespace llvm
     467             : 
     468             : namespace std {
     469             : 
     470             :   /// Implement std::swap in terms of SmallPtrSet swap.
     471             :   template<class T, unsigned N>
     472             :   inline void swap(llvm::SmallPtrSet<T, N> &LHS, llvm::SmallPtrSet<T, N> &RHS) {
     473    11674825 :     LHS.swap(RHS);
     474             :   }
     475             : 
     476             : } // end namespace std
     477             : 
     478             : #endif // LLVM_ADT_SMALLPTRSET_H

Generated by: LCOV version 1.13