lib/Support/SmallPtrSet.cpp

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