//
// 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.
//
//===----------------------------------------------------------------------===//
//
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;
Grow();
// 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;