Home | History | Annotate | Download | only in ADT 
      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 // SmallPtrSetImpl 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 <cassert>
     19 #include <cstddef>
     20 #include <cstring>
     21 #include <iterator>
     22 #include "llvm/Support/DataTypes.h"
     23 #include "llvm/Support/PointerLikeTypeTraits.h"
     24 
     25 namespace llvm {
     26 
     27 class SmallPtrSetIteratorImpl;
     28 
     29 /// SmallPtrSetImpl - This is the common code shared among all the
     30 /// SmallPtrSet<>'s, which is almost everything.  SmallPtrSet has two modes, one
     31 /// for small and one for large sets.
     32 ///
     33 /// Small sets use an array of pointers allocated in the SmallPtrSet object,
     34 /// which is treated as a simple array of pointers.  When a pointer is added to
     35 /// the set, the array is scanned to see if the element already exists, if not
     36 /// the element is 'pushed back' onto the array.  If we run out of space in the
     37 /// array, we grow into the 'large set' case.  SmallSet should be used when the
     38 /// sets are often small.  In this case, no memory allocation is used, and only
     39 /// light-weight and cache-efficient scanning is used.
     40 ///
     41 /// Large sets use a classic exponentially-probed hash table.  Empty buckets are
     42 /// represented with an illegal pointer value (-1) to allow null pointers to be
     43 /// inserted.  Tombstones are represented with another illegal pointer value
     44 /// (-2), to allow deletion.  The hash table is resized when the table is 3/4 or
     45 /// more.  When this happens, the table is doubled in size.
     46 ///
     47 class SmallPtrSetImpl {
     48   friend class SmallPtrSetIteratorImpl;
     49 protected:
     50   /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
     51   const void **SmallArray;
     52   /// CurArray - This is the current set of buckets.  If equal to SmallArray,
     53   /// then the set is in 'small mode'.
     54   const void **CurArray;
     55   /// CurArraySize - The allocated size of CurArray, always a power of two.
     56   /// Note that CurArray points to an array that has CurArraySize+1 elements in
     57   /// it, so that the end iterator actually points to valid memory.
     58   unsigned CurArraySize;
     59 
     60   // If small, this is # elts allocated consecutively
     61   unsigned NumElements;
     62   unsigned NumTombstones;
     63 
     64   // Helper to copy construct a SmallPtrSet.
     65   SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl& that);
     66   explicit SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize) :
     67     SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) {
     68     assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
     69            "Initial size must be a power of two!");
     70     // The end pointer, always valid, is set to a valid element to help the
     71     // iterator.
     72     CurArray[SmallSize] = 0;
     73     clear();
     74   }
     75   ~SmallPtrSetImpl();
     76 
     77 public:
     78   bool empty() const { return size() == 0; }
     79   unsigned size() const { return NumElements; }
     80 
     81   void clear() {
     82     // If the capacity of the array is huge, and the # elements used is small,
     83     // shrink the array.
     84     if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32)
     85       return shrink_and_clear();
     86 
     87     // Fill the array with empty markers.
     88     memset(CurArray, -1, CurArraySize*sizeof(void*));
     89     NumElements = 0;
     90     NumTombstones = 0;
     91   }
     92 
     93 protected:
     94   static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
     95   static void *getEmptyMarker() {
     96     // Note that -1 is chosen to make clear() efficiently implementable with
     97     // memset and because it's not a valid pointer value.
     98     return reinterpret_cast<void*>(-1);
     99   }
    100 
    101   /// insert_imp - This returns true if the pointer was new to the set, false if
    102   /// it was already in the set.  This is hidden from the client so that the
    103   /// derived class can check that the right type of pointer is passed in.
    104   bool insert_imp(const void * Ptr);
    105 
    106   /// erase_imp - If the set contains the specified pointer, remove it and
    107   /// return true, otherwise return false.  This is hidden from the client so
    108   /// that the derived class can check that the right type of pointer is passed
    109   /// in.
    110   bool erase_imp(const void * Ptr);
    111 
    112   bool count_imp(const void * Ptr) const {
    113     if (isSmall()) {
    114       // Linear search for the item.
    115       for (const void *const *APtr = SmallArray,
    116                       *const *E = SmallArray+NumElements; APtr != E; ++APtr)
    117         if (*APtr == Ptr)
    118           return true;
    119       return false;
    120     }
    121 
    122     // Big set case.
    123     return *FindBucketFor(Ptr) == Ptr;
    124   }
    125 
    126 private:
    127   bool isSmall() const { return CurArray == SmallArray; }
    128 
    129   unsigned Hash(const void *Ptr) const {
    130     return static_cast<unsigned>(((uintptr_t)Ptr >> 4) & (CurArraySize-1));
    131   }
    132   const void * const *FindBucketFor(const void *Ptr) const;
    133   void shrink_and_clear();
    134 
    135   /// Grow - Allocate a larger backing store for the buckets and move it over.
    136   void Grow(unsigned NewSize);
    137 
    138   void operator=(const SmallPtrSetImpl &RHS);  // DO NOT IMPLEMENT.
    139 protected:
    140   void CopyFrom(const SmallPtrSetImpl &RHS);
    141 };
    142 
    143 /// SmallPtrSetIteratorImpl - This is the common base class shared between all
    144 /// instances of SmallPtrSetIterator.
    145 class SmallPtrSetIteratorImpl {
    146 protected:
    147   const void *const *Bucket;
    148 public:
    149   explicit SmallPtrSetIteratorImpl(const void *const *BP) : Bucket(BP) {
    150     AdvanceIfNotValid();
    151   }
    152 
    153   bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
    154     return Bucket == RHS.Bucket;
    155   }
    156   bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
    157     return Bucket != RHS.Bucket;
    158   }
    159 
    160 protected:
    161   /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
    162   /// that is.   This is guaranteed to stop because the end() bucket is marked
    163   /// valid.
    164   void AdvanceIfNotValid() {
    165     while (*Bucket == SmallPtrSetImpl::getEmptyMarker() ||
    166            *Bucket == SmallPtrSetImpl::getTombstoneMarker())
    167       ++Bucket;
    168   }
    169 };
    170 
    171 /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
    172 template<typename PtrTy>
    173 class SmallPtrSetIterator : public SmallPtrSetIteratorImpl {
    174   typedef PointerLikeTypeTraits<PtrTy> PtrTraits;
    175 
    176 public:
    177   typedef PtrTy                     value_type;
    178   typedef PtrTy                     reference;
    179   typedef PtrTy                     pointer;
    180   typedef std::ptrdiff_t            difference_type;
    181   typedef std::forward_iterator_tag iterator_category;
    182 
    183   explicit SmallPtrSetIterator(const void *const *BP)
    184     : SmallPtrSetIteratorImpl(BP) {}
    185 
    186   // Most methods provided by baseclass.
    187 
    188   const PtrTy operator*() const {
    189     return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
    190   }
    191 
    192   inline SmallPtrSetIterator& operator++() {          // Preincrement
    193     ++Bucket;
    194     AdvanceIfNotValid();
    195     return *this;
    196   }
    197 
    198   SmallPtrSetIterator operator++(int) {        // Postincrement
    199     SmallPtrSetIterator tmp = *this; ++*this; return tmp;
    200   }
    201 };
    202 
    203 /// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next
    204 /// power of two (which means N itself if N is already a power of two).
    205 template<unsigned N>
    206 struct RoundUpToPowerOfTwo;
    207 
    208 /// RoundUpToPowerOfTwoH - If N is not a power of two, increase it.  This is a
    209 /// helper template used to implement RoundUpToPowerOfTwo.
    210 template<unsigned N, bool isPowerTwo>
    211 struct RoundUpToPowerOfTwoH {
    212   enum { Val = N };
    213 };
    214 template<unsigned N>
    215 struct RoundUpToPowerOfTwoH<N, false> {
    216   enum {
    217     // We could just use NextVal = N+1, but this converges faster.  N|(N-1) sets
    218     // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111.
    219     Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val
    220   };
    221 };
    222 
    223 template<unsigned N>
    224 struct RoundUpToPowerOfTwo {
    225   enum { Val = RoundUpToPowerOfTwoH<N, (N&(N-1)) == 0>::Val };
    226 };
    227 
    228 
    229 /// SmallPtrSet - This class implements a set which is optimized for holding
    230 /// SmallSize or less elements.  This internally rounds up SmallSize to the next
    231 /// power of two if it is not already a power of two.  See the comments above
    232 /// SmallPtrSetImpl for details of the algorithm.
    233 template<class PtrType, unsigned SmallSize>
    234 class SmallPtrSet : public SmallPtrSetImpl {
    235   // Make sure that SmallSize is a power of two, round up if not.
    236   enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
    237   /// SmallStorage - Fixed size storage used in 'small mode'.  The extra element
    238   /// ensures that the end iterator actually points to valid memory.
    239   const void *SmallStorage[SmallSizePowTwo+1];
    240   typedef PointerLikeTypeTraits<PtrType> PtrTraits;
    241 public:
    242   SmallPtrSet() : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) {}
    243   SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(SmallStorage, that) {}
    244 
    245   template<typename It>
    246   SmallPtrSet(It I, It E) : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) {
    247     insert(I, E);
    248   }
    249 
    250   /// insert - This returns true if the pointer was new to the set, false if it
    251   /// was already in the set.
    252   bool insert(PtrType Ptr) {
    253     return insert_imp(PtrTraits::getAsVoidPointer(Ptr));
    254   }
    255 
    256   /// erase - If the set contains the specified pointer, remove it and return
    257   /// true, otherwise return false.
    258   bool erase(PtrType Ptr) {
    259     return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
    260   }
    261 
    262   /// count - Return true if the specified pointer is in the set.
    263   bool count(PtrType Ptr) const {
    264     return count_imp(PtrTraits::getAsVoidPointer(Ptr));
    265   }
    266 
    267   template <typename IterT>
    268   void insert(IterT I, IterT E) {
    269     for (; I != E; ++I)
    270       insert(*I);
    271   }
    272 
    273   typedef SmallPtrSetIterator<PtrType> iterator;
    274   typedef SmallPtrSetIterator<PtrType> const_iterator;
    275   inline iterator begin() const {
    276     return iterator(CurArray);
    277   }
    278   inline iterator end() const {
    279     return iterator(CurArray+CurArraySize);
    280   }
    281 
    282   // Allow assignment from any smallptrset with the same element type even if it
    283   // doesn't have the same smallsize.
    284   const SmallPtrSet<PtrType, SmallSize>&
    285   operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
    286     CopyFrom(RHS);
    287     return *this;
    288   }
    289 
    290 };
    291 
    292 }
    293 
    294 #endif
    295