lib/Support/SmallPtrSet.cpp

   1 //===- llvm/ADT/SmallPtrSet.cpp - 'Normally small' pointer set ------------===//
   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 implements the SmallPtrSet class.  See SmallPtrSet.h for an
  11 // overview of the algorithm.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/ADT/SmallPtrSet.h"
  16 #include "llvm/Support/MathExtras.h"
  17 #include <cstdlib>
  18
  19 using namespace llvm;
  20
  21 void SmallPtrSetImpl::shrink_and_clear() {
  22   assert(!isSmall() && "Can't shrink a small set!");
  23   free(CurArray);
  24
  25   // Reduce the number of buckets.
  26   CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32;
  27   NumElements = NumTombstones = 0;
  28
  29   // Install the new array.  Clear all the buckets to empty.
  30   CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1));
  31   assert(CurArray && "Failed to allocate memory?");
  32   memset(CurArray, -1, CurArraySize*sizeof(void*));
  33
  34   // The end pointer, always valid, is set to a valid element to help the
  35   // iterator.
  36   CurArray[CurArraySize] = 0;
  37 }
  38
  39 bool SmallPtrSetImpl::insert_imp(const void * Ptr) {
  40   if (isSmall()) {
  41     // Check to see if it is already in the set.
  42     for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
  43          APtr != E; ++APtr)
  44       if (*APtr == Ptr)
  45         return false;
  46
  47     // Nope, there isn't.  If we stay small, just 'pushback' now.
  48     if (NumElements < CurArraySize-1) {
  49       SmallArray[NumElements++] = Ptr;
  50       return true;
  51     }
  52     // Otherwise, hit the big set case, which will call grow.
  53   }
  54
  55   if (NumElements*4 >= CurArraySize*3) {
  56     // If more than 3/4 of the array is full, grow.
  57     Grow(CurArraySize < 64 ? 128 : CurArraySize*2);
  58   } else if (CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) {
  59     // If fewer of 1/8 of the array is empty (meaning that many are filled with
  60     // tombstones), rehash.
  61     Grow(CurArraySize);
  62   }
  63
  64   // Okay, we know we have space.  Find a hash bucket.
  65   const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr));
  66   if (*Bucket == Ptr) return false; // Already inserted, good.
  67
  68   // Otherwise, insert it!
  69   if (*Bucket == getTombstoneMarker())
  70     --NumTombstones;
  71   *Bucket = Ptr;
  72   ++NumElements;  // Track density.
  73   return true;
  74 }
  75
  76 bool SmallPtrSetImpl::erase_imp(const void * Ptr) {
  77   if (isSmall()) {
  78     // Check to see if it is in the set.
  79     for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
  80          APtr != E; ++APtr)
  81       if (*APtr == Ptr) {
  82         // If it is in the set, replace this element.
  83         *APtr = E[-1];
  84         E[-1] = getEmptyMarker();
  85         --NumElements;
  86         return true;
  87       }
  88
  89     return false;
  90   }
  91
  92   // Okay, we know we have space.  Find a hash bucket.
  93   void **Bucket = const_cast<void**>(FindBucketFor(Ptr));
  94   if (*Bucket != Ptr) return false;  // Not in the set?
  95
  96   // Set this as a tombstone.
  97   *Bucket = getTombstoneMarker();
  98   --NumElements;
  99   ++NumTombstones;
 100   return true;
 101 }
 102
 103 const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const {
 104   unsigned Bucket = Hash(Ptr);
 105   unsigned ArraySize = CurArraySize;
 106   unsigned ProbeAmt = 1;
 107   const void *const *Array = CurArray;
 108   const void *const *Tombstone = 0;
 109   while (1) {
 110     // Found Ptr's bucket?
 111     if (Array[Bucket] == Ptr)
 112       return Array+Bucket;
 113
 114     // If we found an empty bucket, the pointer doesn't exist in the set.
 115     // Return a tombstone if we've seen one so far, or the empty bucket if
 116     // not.
 117     if (Array[Bucket] == getEmptyMarker())
 118       return Tombstone ? Tombstone : Array+Bucket;
 119
 120     // If this is a tombstone, remember it.  If Ptr ends up not in the set, we
 121     // prefer to return it than something that would require more probing.
 122     if (Array[Bucket] == getTombstoneMarker() && !Tombstone)
 123       Tombstone = Array+Bucket;  // Remember the first tombstone found.
 124
 125     // It's a hash collision or a tombstone. Reprobe.
 126     Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);
 127   }
 128 }
 129
 130 /// Grow - Allocate a larger backing store for the buckets and move it over.
 131 ///
 132 void SmallPtrSetImpl::Grow(unsigned NewSize) {
 133   // Allocate at twice as many buckets, but at least 128.
 134   unsigned OldSize = CurArraySize;
 135
 136   const void **OldBuckets = CurArray;
 137   bool WasSmall = isSmall();
 138
 139   // Install the new array.  Clear all the buckets to empty.
 140   CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1));
 141   assert(CurArray && "Failed to allocate memory?");
 142   CurArraySize = NewSize;
 143   memset(CurArray, -1, NewSize*sizeof(void*));
 144
 145   // The end pointer, always valid, is set to a valid element to help the
 146   // iterator.
 147   CurArray[NewSize] = 0;
 148
 149   // Copy over all the elements.
 150   if (WasSmall) {
 151     // Small sets store their elements in order.
 152     for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements;
 153          BucketPtr != E; ++BucketPtr) {
 154       const void *Elt = *BucketPtr;
 155       *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
 156     }
 157   } else {
 158     // Copy over all valid entries.
 159     for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize;
 160          BucketPtr != E; ++BucketPtr) {
 161       // Copy over the element if it is valid.
 162       const void *Elt = *BucketPtr;
 163       if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
 164         *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
 165     }
 166
 167     free(OldBuckets);
 168     NumTombstones = 0;
 169   }
 170 }
 171
 172 SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage,
 173                                  const SmallPtrSetImpl& that) {
 174   SmallArray = SmallStorage;
 175
 176   // If we're becoming small, prepare to insert into our stack space
 177   if (that.isSmall()) {
 178     CurArray = SmallArray;
 179   // Otherwise, allocate new heap space (unless we were the same size)
 180   } else {
 181     CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1));
 182     assert(CurArray && "Failed to allocate memory?");
 183   }
 184
 185   // Copy over the new array size
 186   CurArraySize = that.CurArraySize;
 187
 188   // Copy over the contents from the other set
 189   memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1));
 190
 191   NumElements = that.NumElements;
 192   NumTombstones = that.NumTombstones;
 193 }
 194
 195 /// CopyFrom - implement operator= from a smallptrset that has the same pointer
 196 /// type, but may have a different small size.
 197 void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) {
 198   if (isSmall() && RHS.isSmall())
 199     assert(CurArraySize == RHS.CurArraySize &&
 200            "Cannot assign sets with different small sizes");
 201
 202   // If we're becoming small, prepare to insert into our stack space
 203   if (RHS.isSmall()) {
 204     if (!isSmall())
 205       free(CurArray);
 206     CurArray = SmallArray;
 207   // Otherwise, allocate new heap space (unless we were the same size)
 208   } else if (CurArraySize != RHS.CurArraySize) {
 209     if (isSmall())
 210       CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1));
 211     else
 212       CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1));
 213     assert(CurArray && "Failed to allocate memory?");
 214   }
 215
 216   // Copy over the new array size
 217   CurArraySize = RHS.CurArraySize;
 218
 219   // Copy over the contents from the other set
 220   memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1));
 221
 222   NumElements = RHS.NumElements;
 223   NumTombstones = RHS.NumTombstones;
 224 }
 225
 226 SmallPtrSetImpl::~SmallPtrSetImpl() {
 227   if (!isSmall())
 228     free(CurArray);
 229 }