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, move everything over, replacing this element.
  58         memmove(APtr, APtr+1, sizeof(void*)*(E-APtr-1));
  59         // Clear the end element.
  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   }
 145 }