include/llvm/ADT/SmallPtrSet.h

   1 //===- llvm/ADT/SmallPtrSet.h - 'Normally small' pointer set ----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the SmallPtrSet class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_SMALLPTRSET_H
  15 #define LLVM_ADT_SMALLPTRSET_H
  16
  17 #include <cassert>
  18 #include <cstring>
  19
  20 namespace llvm {
  21
  22 class SmallPtrSetImpl {
  23 protected:
  24   /// CurArray - This is the current set of buckets.  If it points to
  25   /// SmallArray, then the set is in 'small mode'.
  26   void **CurArray;
  27   /// CurArraySize - The allocated size of CurArray, always a power of two.
  28   /// Note that CurArray points to an array that has CurArraySize+1 elements in
  29   /// it, so that the end iterator actually points to valid memory.
  30   unsigned CurArraySize;
  31
  32   // If small, this is # elts allocated consequtively
  33   unsigned NumElements;
  34   void *SmallArray[1];  // Must be last ivar.
  35 public:
  36   SmallPtrSetImpl(unsigned SmallSize) {
  37     assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
  38            "Initial size must be a power of two!");
  39     CurArray = &SmallArray[0];
  40     CurArraySize = SmallSize;
  41     // The end pointer, always valid, is set to a valid element to help the
  42     // iterator.
  43     CurArray[SmallSize] = 0;
  44     clear();
  45   }
  46   ~SmallPtrSetImpl() {
  47     if (!isSmall())
  48       delete[] CurArray;
  49   }
  50
  51   bool isSmall() const { return CurArray == &SmallArray[0]; }
  52
  53   static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
  54   static void *getEmptyMarker() {
  55     // Note that -1 is chosen to make clear() efficiently implementable with
  56     // memset and because it's not a valid pointer value.
  57     return reinterpret_cast<void*>(-1);
  58   }
  59
  60   void clear() {
  61     // Fill the array with empty markers.
  62     memset(CurArray, -1, CurArraySize*sizeof(void*));
  63     NumElements = 0;
  64   }
  65
  66   /// insert - This returns true if the pointer was new to the set, false if it
  67   /// was already in the set.
  68   bool insert(void *Ptr);
  69
  70   bool count(void *Ptr) const {
  71     if (isSmall()) {
  72       // Linear search for the item.
  73       for (void *const *APtr = SmallArray, *const *E = SmallArray+NumElements;
  74            APtr != E; ++APtr)
  75         if (*APtr == Ptr)
  76           return true;
  77       return false;
  78     }
  79
  80     // Big set case.
  81     return *FindBucketFor(Ptr) == Ptr;
  82   }
  83
  84 private:
  85   unsigned Hash(void *Ptr) const {
  86     return ((uintptr_t)Ptr >> 4) & (CurArraySize-1);
  87   }
  88   void * const *FindBucketFor(void *Ptr) const;
  89
  90   /// Grow - Allocate a larger backing store for the buckets and move it over.
  91   void Grow();
  92 };
  93
  94 /// SmallPtrSetIteratorImpl - This is the common base class shared between all
  95 /// instances of SmallPtrSetIterator.
  96 class SmallPtrSetIteratorImpl {
  97 protected:
  98   void *const *Bucket;
  99 public:
 100   SmallPtrSetIteratorImpl(void *const *BP) : Bucket(BP) {
 101     AdvanceIfNotValid();
 102   }
 103
 104   bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
 105     return Bucket == RHS.Bucket;
 106   }
 107   bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
 108     return Bucket != RHS.Bucket;
 109   }
 110
 111 protected:
 112   /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
 113   /// that is.   This is guaranteed to stop because the end() bucket is marked
 114   /// valid.
 115   void AdvanceIfNotValid() {
 116     while (*Bucket == SmallPtrSetImpl::getEmptyMarker() ||
 117            *Bucket == SmallPtrSetImpl::getTombstoneMarker())
 118       ++Bucket;
 119   }
 120 };
 121
 122 /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
 123 template<typename PtrTy>
 124 class SmallPtrSetIterator : public SmallPtrSetIteratorImpl {
 125 public:
 126   SmallPtrSetIterator(void *const *BP) : SmallPtrSetIteratorImpl(BP) {}
 127
 128   // Most methods provided by baseclass.
 129
 130   PtrTy operator*() const {
 131     return static_cast<PtrTy>(*Bucket);
 132   }
 133
 134   inline SmallPtrSetIterator& operator++() {          // Preincrement
 135     ++Bucket;
 136     AdvanceIfNotValid();
 137     return *this;
 138   }
 139
 140   SmallPtrSetIterator operator++(int) {        // Postincrement
 141     SmallPtrSetIterator tmp = *this; ++*this; return tmp;
 142   }
 143 };
 144
 145
 146 /// SmallPtrSet - This class implements
 147 template<class PtrType, unsigned SmallSize>
 148 class SmallPtrSet : public SmallPtrSetImpl {
 149   void *SmallArray[SmallSize];
 150 public:
 151   SmallPtrSet() : SmallPtrSetImpl(SmallSize) {}
 152
 153   typedef SmallPtrSetIterator<PtrType> iterator;
 154   typedef SmallPtrSetIterator<PtrType> const_iterator;
 155   inline iterator begin() const {
 156     return iterator(CurArray);
 157   }
 158   inline iterator end() const {
 159     return iterator(CurArray+CurArraySize);
 160   }
 161 };
 162
 163 }
 164
 165 #endif