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 = new void*[NewSize+1];
 118   CurArraySize = NewSize;
 119   memset(CurArray, -1, NewSize*sizeof(void*));
 120
 121   // The end pointer, always valid, is set to a valid element to help the
 122   // iterator.
 123   CurArray[NewSize] = 0;
 124
 125   // Copy over all the elements.
 126   if (WasSmall) {
 127     // Small sets store their elements in order.
 128     for (void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements;
 129          BucketPtr != E; ++BucketPtr) {
 130       void *Elt = *BucketPtr;
 131       *const_cast<void**>(FindBucketFor(Elt)) = Elt;
 132     }
 133   } else {
 134     // Copy over all valid entries.
 135     for (void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize;
 136          BucketPtr != E; ++BucketPtr) {
 137       // Copy over the element if it is valid.
 138       void *Elt = *BucketPtr;
 139       if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
 140         *const_cast<void**>(FindBucketFor(Elt)) = Elt;
 141     }
 142
 143     delete [] OldBuckets;
 144     NumTombstones = 0;
 145   }
 146 }
 147
 148 SmallPtrSetImpl::SmallPtrSetImpl(const SmallPtrSetImpl& that) {
 149   NumElements = that.NumElements;
 150   NumTombstones = 0;
 151   if (that.isSmall()) {
 152     CurArraySize = that.CurArraySize;
 153     CurArray = &SmallArray[0];
 154     // Copy the entire contents of the array, including the -1's and the null
 155     // terminator.
 156     memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1));
 157   } else {
 158     CurArraySize = that.NumElements < 64 ? 128 : that.CurArraySize*2;
 159     CurArray = new void*[CurArraySize+1];
 160     memset(CurArray, -1, CurArraySize*sizeof(void*));
 161
 162     // The end pointer, always valid, is set to a valid element to help the
 163     // iterator.
 164     CurArray[CurArraySize] = 0;
 165
 166     // Copy over all valid entries.
 167     for (void **BucketPtr = that.CurArray, **E = that.CurArray+that.CurArraySize;
 168          BucketPtr != E; ++BucketPtr) {
 169       // Copy over the element if it is valid.
 170       void *Elt = *BucketPtr;
 171       if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
 172         *const_cast<void**>(FindBucketFor(Elt)) = Elt;
 173     }
 174   }
 175 }
 176
 177 /// CopyFrom - implement operator= from a smallptrset that has the same pointer
 178 /// type, but may have a different small size.
 179 void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) {
 180   // Allocate space if needed or clear the current elements out of the array.
 181   if (CurArraySize < RHS.size()*2) {
 182     if (!isSmall())
 183       delete [] CurArray;
 184
 185     NumElements = NumTombstones = 0;
 186
 187     // Get a power of two larger than twice the RHS size.
 188     CurArraySize = 1 << Log2_32(RHS.size()*4);
 189
 190     // Install the new array.  Clear all the buckets to empty.
 191     CurArray = new void*[CurArraySize+1];
 192     memset(CurArray, -1, CurArraySize*sizeof(void*));
 193
 194     // The end pointer, always valid, is set to a valid element to help the
 195     // iterator.
 196     CurArray[CurArraySize] = 0;
 197
 198   } else if (!empty()) {
 199     clear();
 200   }
 201
 202   // Now that we know we have enough space, and that the current array is empty,
 203   // copy over all the elements from the RHS.
 204   for (void **BucketPtr = RHS.CurArray, **E = RHS.CurArray+RHS.CurArraySize;
 205        BucketPtr != E; ++BucketPtr) {
 206     // Copy over the element if it is valid.
 207     void *Elt = *BucketPtr;
 208     if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) {
 209       if (isSmall())
 210         SmallArray[NumElements++] = Elt;
 211       else
 212         *const_cast<void**>(FindBucketFor(Elt)) = Elt;
 213     }
 214   }
 215
 216   if (!isSmall())
 217     NumElements = RHS.NumElements;
 218 }