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