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