X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FSmallPtrSet.cpp;h=997ce0b74cd24c559c6a6a05c7e5a6f44dc6d752;hb=adf01b3f18442ae8db6b8948e70d82d9df415119;hp=1507059f386b764178f46c764a2628fce8726e39;hpb=e992a56ae93140171f5044079e8d317f784c8cc1;p=oota-llvm.git

diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp
index 1507059f386..997ce0b74cd 100644
--- a/lib/Support/SmallPtrSet.cpp
+++ b/lib/Support/SmallPtrSet.cpp
@@ -2,8 +2,8 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by Chris Lattner and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -18,7 +18,25 @@
 
 using namespace llvm;
 
-bool SmallPtrSetImpl::insert(const void * Ptr) {
+void SmallPtrSetImpl::shrink_and_clear() {
+  assert(!isSmall() && "Can't shrink a small set!");
+  free(CurArray);
+
+  // Reduce the number of buckets.
+  CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32;
+  NumElements = NumTombstones = 0;
+
+  // Install the new array.  Clear all the buckets to empty.
+  CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1));
+  assert(CurArray && "Failed to allocate memory?");
+  memset(CurArray, -1, CurArraySize*sizeof(void*));
+  
+  // The end pointer, always valid, is set to a valid element to help the
+  // iterator.
+  CurArray[CurArraySize] = 0;
+}
+
+bool SmallPtrSetImpl::insert_imp(const void * Ptr) {
   if (isSmall()) {
     // Check to see if it is already in the set.
     for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
@@ -34,24 +52,28 @@ bool SmallPtrSetImpl::insert(const void * Ptr) {
     // Otherwise, hit the big set case, which will call grow.
   }
   
-  // If more than 3/4 of the array is full, grow.
-  if (NumElements*4 >= CurArraySize*3 ||
-      CurArraySize-(NumElements+NumTombstones) < CurArraySize/8)
-    Grow();
+  if (NumElements*4 >= CurArraySize*3) {
+    // If more than 3/4 of the array is full, grow.
+    Grow(CurArraySize < 64 ? 128 : CurArraySize*2);
+  } else if (CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) {
+    // If fewer of 1/8 of the array is empty (meaning that many are filled with
+    // tombstones), rehash.
+    Grow(CurArraySize);
+  }
   
   // Okay, we know we have space.  Find a hash bucket.
-  void **Bucket = const_cast<void**>(FindBucketFor((void*)Ptr));
+  const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr));
   if (*Bucket == Ptr) return false; // Already inserted, good.
   
   // Otherwise, insert it!
   if (*Bucket == getTombstoneMarker())
     --NumTombstones;
-  *Bucket = (void*)Ptr;
+  *Bucket = Ptr;
   ++NumElements;  // Track density.
   return true;
 }
 
-bool SmallPtrSetImpl::erase(void * const Ptr) {
+bool SmallPtrSetImpl::erase_imp(const void * Ptr) {
   if (isSmall()) {
     // Check to see if it is in the set.
     for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
@@ -107,10 +129,9 @@ const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const {
 
 /// Grow - Allocate a larger backing store for the buckets and move it over.
 ///
-void SmallPtrSetImpl::Grow() {
+void SmallPtrSetImpl::Grow(unsigned NewSize) {
   // Allocate at twice as many buckets, but at least 128.
   unsigned OldSize = CurArraySize;
-  unsigned NewSize = OldSize < 64 ? 128 : OldSize*2;
   
   const void **OldBuckets = CurArray;
   bool WasSmall = isSmall();
@@ -148,10 +169,13 @@ void SmallPtrSetImpl::Grow() {
   }
 }
 
-SmallPtrSetImpl::SmallPtrSetImpl(const SmallPtrSetImpl& that) {
+SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage,
+                                 const SmallPtrSetImpl& that) {
+  SmallArray = SmallStorage;
+
   // If we're becoming small, prepare to insert into our stack space
   if (that.isSmall()) {
-    CurArray = &SmallArray[0];
+    CurArray = SmallArray;
   // Otherwise, allocate new heap space (unless we were the same size)
   } else {
     CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1));
@@ -179,7 +203,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) {
   if (RHS.isSmall()) {
     if (!isSmall())
       free(CurArray);
-    CurArray = &SmallArray[0];
+    CurArray = SmallArray;
   // Otherwise, allocate new heap space (unless we were the same size)
   } else if (CurArraySize != RHS.CurArraySize) {
     if (isSmall())