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     Grow();
  37
  38   // Okay, we know we have space.  Find a hash bucket.
  39   void **Bucket = const_cast<void**>(FindBucketFor(Ptr));
  40   if (*Bucket == Ptr) return false; // Already inserted, good.
  41
  42   // Otherwise, insert it!
  43   *Bucket = Ptr;
  44   ++NumElements;  // Track density.
  45   return true;
  46 }
  47
  48 bool SmallPtrSetImpl::erase(void *Ptr) {
  49   if (isSmall()) {
  50     // Check to see if it is in the set.
  51     for (void **APtr = SmallArray, **E = SmallArray+NumElements;
  52          APtr != E; ++APtr)
  53       if (*APtr == Ptr) {
  54         // If it is in the set, move everything over, replacing this element.
  55         memmove(APtr, APtr+1, sizeof(void*)*(E-APtr-1));
  56         // Clear the end element.
  57         E[-1] = getEmptyMarker();
  58         --NumElements;
  59         return false;
  60       }
  61
  62     return false;
  63   }
  64
  65   // Okay, we know we have space.  Find a hash bucket.
  66   void **Bucket = const_cast<void**>(FindBucketFor(Ptr));
  67   if (*Bucket != Ptr) return false;  // Not in the set?
  68
  69   // Set this as a tombstone.
  70   *Bucket = getTombstoneMarker();
  71   --NumElements;
  72   return true;
  73 }
  74
  75 void * const *SmallPtrSetImpl::FindBucketFor(void *Ptr) const {
  76   unsigned Bucket = Hash(Ptr);
  77   unsigned ArraySize = CurArraySize;
  78   unsigned ProbeAmt = 1;
  79   void *const *Array = CurArray;
  80   void *const *Tombstone = 0;
  81   while (1) {
  82     // Found Ptr's bucket?
  83     if (Array[Bucket] == Ptr)
  84       return Array+Bucket;
  85
  86     // If we found an empty bucket, the pointer doesn't exist in the set.
  87     // Return a tombstone if we've seen one so far, or the empty bucket if
  88     // not.
  89     if (Array[Bucket] == getEmptyMarker())
  90       return Tombstone ? Tombstone : Array+Bucket;
  91
  92     // If this is a tombstone, remember it.  If Ptr ends up not in the set, we
  93     // prefer to return it than something that would require more probing.
  94     if (Array[Bucket] == getTombstoneMarker() && !Tombstone)
  95       Tombstone = Array+Bucket;  // Remember the first tombstone found.
  96
  97     // It's a hash collision or a tombstone. Reprobe.
  98     Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);
  99   }
 100 }
 101
 102 /// Grow - Allocate a larger backing store for the buckets and move it over.
 103 ///
 104 void SmallPtrSetImpl::Grow() {
 105   // Allocate at twice as many buckets, but at least 128.
 106   unsigned OldSize = CurArraySize;
 107   unsigned NewSize = OldSize < 64 ? 128 : OldSize*2;
 108
 109   void **OldBuckets = CurArray;
 110   bool WasSmall = isSmall();
 111
 112   // Install the new array.  Clear all the buckets to empty.
 113   CurArray = new void*[NewSize+1];
 114   CurArraySize = NewSize;
 115   memset(CurArray, -1, NewSize*sizeof(void*));
 116
 117   // The end pointer, always valid, is set to a valid element to help the
 118   // iterator.
 119   CurArray[NewSize] = 0;
 120
 121   // Copy over all the elements.
 122   if (WasSmall) {
 123     // Small sets store their elements in order.
 124     for (void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements;
 125          BucketPtr != E; ++BucketPtr) {
 126       void *Elt = *BucketPtr;
 127       *const_cast<void**>(FindBucketFor(Elt)) = Elt;
 128     }
 129   } else {
 130     // Copy over all valid entries.
 131     for (void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize;
 132          BucketPtr != E; ++BucketPtr) {
 133       // Copy over the element if it is valid.
 134       void *Elt = *BucketPtr;
 135       if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
 136         *const_cast<void**>(FindBucketFor(Elt)) = Elt;
 137     }
 138
 139     delete [] OldBuckets;
 140   }
 141 }