//===----------------------------------------------------------------------===//
#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Support/MathExtras.h"
+#include <cstdlib>
+
using namespace llvm;
-bool SmallPtrSetImpl::insert(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(const void * Ptr) {
if (isSmall()) {
// Check to see if it is already in the set.
- for (void **APtr = SmallArray, **E = SmallArray+NumElements;
+ for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
APtr != E; ++APtr)
if (*APtr == Ptr)
return false;
Grow();
// Okay, we know we have space. Find a hash bucket.
- void **Bucket = const_cast<void**>(FindBucketFor(Ptr));
+ void **Bucket = const_cast<void**>(FindBucketFor((void*)Ptr));
if (*Bucket == Ptr) return false; // Already inserted, good.
// Otherwise, insert it!
if (*Bucket == getTombstoneMarker())
--NumTombstones;
- *Bucket = Ptr;
+ *Bucket = (void*)Ptr;
++NumElements; // Track density.
return true;
}
-bool SmallPtrSetImpl::erase(void *Ptr) {
+bool SmallPtrSetImpl::erase(void * const Ptr) {
if (isSmall()) {
// Check to see if it is in the set.
- for (void **APtr = SmallArray, **E = SmallArray+NumElements;
+ for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
APtr != E; ++APtr)
if (*APtr == Ptr) {
// If it is in the set, replace this element.
return true;
}
-void * const *SmallPtrSetImpl::FindBucketFor(void *Ptr) const {
+const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const {
unsigned Bucket = Hash(Ptr);
unsigned ArraySize = CurArraySize;
unsigned ProbeAmt = 1;
- void *const *Array = CurArray;
- void *const *Tombstone = 0;
+ const void *const *Array = CurArray;
+ const void *const *Tombstone = 0;
while (1) {
// Found Ptr's bucket?
if (Array[Bucket] == Ptr)
unsigned OldSize = CurArraySize;
unsigned NewSize = OldSize < 64 ? 128 : OldSize*2;
- void **OldBuckets = CurArray;
+ const void **OldBuckets = CurArray;
bool WasSmall = isSmall();
// Install the new array. Clear all the buckets to empty.
- CurArray = new void*[NewSize+1];
+ CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1));
+ assert(CurArray && "Failed to allocate memory?");
CurArraySize = NewSize;
memset(CurArray, -1, NewSize*sizeof(void*));
// Copy over all the elements.
if (WasSmall) {
// Small sets store their elements in order.
- for (void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements;
+ for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements;
BucketPtr != E; ++BucketPtr) {
- void *Elt = *BucketPtr;
- *const_cast<void**>(FindBucketFor(Elt)) = Elt;
+ const void *Elt = *BucketPtr;
+ *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
}
} else {
// Copy over all valid entries.
- for (void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize;
+ for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize;
BucketPtr != E; ++BucketPtr) {
// Copy over the element if it is valid.
- void *Elt = *BucketPtr;
+ const void *Elt = *BucketPtr;
if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
- *const_cast<void**>(FindBucketFor(Elt)) = Elt;
+ *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
}
- delete [] OldBuckets;
+ free(OldBuckets);
NumTombstones = 0;
}
}
SmallPtrSetImpl::SmallPtrSetImpl(const SmallPtrSetImpl& that) {
- NumElements = that.NumElements;
- NumTombstones = 0;
+ // If we're becoming small, prepare to insert into our stack space
if (that.isSmall()) {
- CurArraySize = that.CurArraySize;
CurArray = &SmallArray[0];
- // Copy the entire contents of the array, including the -1's and the null
- // terminator.
- memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1));
+ // Otherwise, allocate new heap space (unless we were the same size)
} else {
- CurArraySize = that.NumElements < 64 ? 128 : that.NumElements*2;
- CurArray = new void*[CurArraySize+1];
- memset(CurArray, -1, CurArraySize*sizeof(void*));
-
- // The end pointer, always valid, is set to a valid element to help the
- // iterator.
- CurArray[CurArraySize] = 0;
+ CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1));
+ assert(CurArray && "Failed to allocate memory?");
+ }
+
+ // Copy over the new array size
+ CurArraySize = that.CurArraySize;
- // Copy over all valid entries.
- for (void **BucketPtr = that.CurArray, **E = that.CurArray+CurArraySize;
- BucketPtr != E; ++BucketPtr) {
- // Copy over the element if it is valid.
- void *Elt = *BucketPtr;
- if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
- *const_cast<void**>(FindBucketFor(Elt)) = Elt;
- }
+ // Copy over the contents from the other set
+ memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1));
+
+ NumElements = that.NumElements;
+ NumTombstones = that.NumTombstones;
+}
+
+/// CopyFrom - implement operator= from a smallptrset that has the same pointer
+/// type, but may have a different small size.
+void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) {
+ if (isSmall() && RHS.isSmall())
+ assert(CurArraySize == RHS.CurArraySize &&
+ "Cannot assign sets with different small sizes");
+
+ // If we're becoming small, prepare to insert into our stack space
+ if (RHS.isSmall()) {
+ if (!isSmall())
+ free(CurArray);
+ CurArray = &SmallArray[0];
+ // Otherwise, allocate new heap space (unless we were the same size)
+ } else if (CurArraySize != RHS.CurArraySize) {
+ if (isSmall())
+ CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1));
+ else
+ CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1));
+ assert(CurArray && "Failed to allocate memory?");
}
+
+ // Copy over the new array size
+ CurArraySize = RHS.CurArraySize;
+
+ // Copy over the contents from the other set
+ memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1));
+
+ NumElements = RHS.NumElements;
+ NumTombstones = RHS.NumTombstones;
+}
+
+SmallPtrSetImpl::~SmallPtrSetImpl() {
+ if (!isSmall())
+ free(CurArray);
}
projects / oota-llvm.git / blobdiff