#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/MathExtras.h"
#include <cstdlib>
using namespace llvm;
void SmallPtrSetImpl::shrink_and_clear() {
assert(!isSmall() && "Can't shrink a small set!");
free(CurArray);
CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32;
NumElements = NumTombstones = 0;
CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1));
assert(CurArray && "Failed to allocate memory?");
memset(CurArray, -1, CurArraySize*sizeof(void*));
CurArray[CurArraySize] = 0;
}
bool SmallPtrSetImpl::insert_imp(const void * Ptr) {
if (isSmall()) {
for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
APtr != E; ++APtr)
if (*APtr == Ptr)
return false;
if (NumElements < CurArraySize-1) {
SmallArray[NumElements++] = Ptr;
return true;
}
}
if (NumElements*4 >= CurArraySize*3) {
Grow(CurArraySize < 64 ? 128 : CurArraySize*2);
} else if (CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) {
Grow(CurArraySize);
}
const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr));
if (*Bucket == Ptr) return false;
if (*Bucket == getTombstoneMarker())
--NumTombstones;
*Bucket = Ptr;
++NumElements; return true;
}
bool SmallPtrSetImpl::erase_imp(const void * Ptr) {
if (isSmall()) {
for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
APtr != E; ++APtr)
if (*APtr == Ptr) {
*APtr = E[-1];
E[-1] = getEmptyMarker();
--NumElements;
return true;
}
return false;
}
void **Bucket = const_cast<void**>(FindBucketFor(Ptr));
if (*Bucket != Ptr) return false;
*Bucket = getTombstoneMarker();
--NumElements;
++NumTombstones;
return true;
}
const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const {
unsigned Bucket = Hash(Ptr);
unsigned ArraySize = CurArraySize;
unsigned ProbeAmt = 1;
const void *const *Array = CurArray;
const void *const *Tombstone = 0;
while (1) {
if (Array[Bucket] == Ptr)
return Array+Bucket;
if (Array[Bucket] == getEmptyMarker())
return Tombstone ? Tombstone : Array+Bucket;
if (Array[Bucket] == getTombstoneMarker() && !Tombstone)
Tombstone = Array+Bucket;
Bucket = (Bucket + ProbeAmt++) & (ArraySize-1);
}
}
void SmallPtrSetImpl::Grow(unsigned NewSize) {
unsigned OldSize = CurArraySize;
const void **OldBuckets = CurArray;
bool WasSmall = isSmall();
CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1));
assert(CurArray && "Failed to allocate memory?");
CurArraySize = NewSize;
memset(CurArray, -1, NewSize*sizeof(void*));
CurArray[NewSize] = 0;
if (WasSmall) {
for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements;
BucketPtr != E; ++BucketPtr) {
const void *Elt = *BucketPtr;
*const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
}
} else {
for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize;
BucketPtr != E; ++BucketPtr) {
const void *Elt = *BucketPtr;
if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
*const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
}
free(OldBuckets);
NumTombstones = 0;
}
}
SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage,
const SmallPtrSetImpl& that) {
SmallArray = SmallStorage;
if (that.isSmall()) {
CurArray = SmallArray;
} else {
CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1));
assert(CurArray && "Failed to allocate memory?");
}
CurArraySize = that.CurArraySize;
memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1));
NumElements = that.NumElements;
NumTombstones = that.NumTombstones;
}
void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) {
if (isSmall() && RHS.isSmall())
assert(CurArraySize == RHS.CurArraySize &&
"Cannot assign sets with different small sizes");
if (RHS.isSmall()) {
if (!isSmall())
free(CurArray);
CurArray = SmallArray;
} 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?");
}
CurArraySize = RHS.CurArraySize;
memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1));
NumElements = RHS.NumElements;
NumTombstones = RHS.NumTombstones;
}
SmallPtrSetImpl::~SmallPtrSetImpl() {
if (!isSmall())
free(CurArray);
}