#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/Support/MathExtras.h"
#include <algorithm>
#include <cstdlib>
using namespace llvm;
void SmallPtrSetImplBase::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);
assert(CurArray && "Failed to allocate memory?");
memset(CurArray, -1, CurArraySize*sizeof(void*));
}
std::pair<const void *const *, bool>
SmallPtrSetImplBase::insert_imp(const void *Ptr) {
if (isSmall()) {
for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
APtr != E; ++APtr)
if (*APtr == Ptr)
return std::make_pair(APtr, false);
if (NumElements < CurArraySize) {
SmallArray[NumElements++] = Ptr;
return std::make_pair(SmallArray + (NumElements - 1), 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 std::make_pair(Bucket, false);
if (*Bucket == getTombstoneMarker())
--NumTombstones;
*Bucket = Ptr;
++NumElements; return std::make_pair(Bucket, true);
}
bool SmallPtrSetImplBase::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 *SmallPtrSetImplBase::FindBucketFor(const void *Ptr) const {
unsigned Bucket = DenseMapInfo<void *>::getHashValue(Ptr) & (CurArraySize-1);
unsigned ArraySize = CurArraySize;
unsigned ProbeAmt = 1;
const void *const *Array = CurArray;
const void *const *Tombstone = nullptr;
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 SmallPtrSetImplBase::Grow(unsigned NewSize) {
unsigned OldSize = CurArraySize;
const void **OldBuckets = CurArray;
bool WasSmall = isSmall();
CurArray = (const void**)malloc(sizeof(void*) * NewSize);
assert(CurArray && "Failed to allocate memory?");
CurArraySize = NewSize;
memset(CurArray, -1, NewSize*sizeof(void*));
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;
}
}
SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
const SmallPtrSetImplBase& that) {
SmallArray = SmallStorage;
if (that.isSmall()) {
CurArray = SmallArray;
} else {
CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize);
assert(CurArray && "Failed to allocate memory?");
}
CurArraySize = that.CurArraySize;
memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize);
NumElements = that.NumElements;
NumTombstones = that.NumTombstones;
}
SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
unsigned SmallSize,
SmallPtrSetImplBase &&that) {
SmallArray = SmallStorage;
CurArraySize = that.CurArraySize;
NumElements = that.NumElements;
NumTombstones = that.NumTombstones;
if (that.isSmall()) {
CurArray = SmallArray;
memcpy(CurArray, that.CurArray, sizeof(void *) * CurArraySize);
} else {
CurArray = that.CurArray;
that.CurArray = that.SmallArray;
}
that.CurArraySize = SmallSize;
assert(that.CurArray == that.SmallArray);
that.NumElements = 0;
that.NumTombstones = 0;
}
void SmallPtrSetImplBase::CopyFrom(const SmallPtrSetImplBase &RHS) {
assert(&RHS != this && "Self-copy should be handled by the caller.");
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);
else {
const void **T = (const void**)realloc(CurArray,
sizeof(void*) * RHS.CurArraySize);
if (!T)
free(CurArray);
CurArray = T;
}
assert(CurArray && "Failed to allocate memory?");
}
CurArraySize = RHS.CurArraySize;
memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize);
NumElements = RHS.NumElements;
NumTombstones = RHS.NumTombstones;
}
void SmallPtrSetImplBase::MoveFrom(unsigned SmallSize,
SmallPtrSetImplBase &&RHS) {
assert(&RHS != this && "Self-move should be handled by the caller.");
if (!isSmall())
free(CurArray);
if (RHS.isSmall()) {
CurArray = SmallArray;
memcpy(CurArray, RHS.CurArray, sizeof(void*)*RHS.CurArraySize);
} else {
CurArray = RHS.CurArray;
RHS.CurArray = RHS.SmallArray;
}
CurArraySize = RHS.CurArraySize;
NumElements = RHS.NumElements;
NumTombstones = RHS.NumTombstones;
RHS.CurArraySize = SmallSize;
assert(RHS.CurArray == RHS.SmallArray);
RHS.NumElements = 0;
RHS.NumTombstones = 0;
}
void SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) {
if (this == &RHS) return;
if (!this->isSmall() && !RHS.isSmall()) {
std::swap(this->CurArray, RHS.CurArray);
std::swap(this->CurArraySize, RHS.CurArraySize);
std::swap(this->NumElements, RHS.NumElements);
std::swap(this->NumTombstones, RHS.NumTombstones);
return;
}
if (!this->isSmall() && RHS.isSmall()) {
std::copy(RHS.SmallArray, RHS.SmallArray+RHS.CurArraySize,
this->SmallArray);
std::swap(this->NumElements, RHS.NumElements);
std::swap(this->CurArraySize, RHS.CurArraySize);
RHS.CurArray = this->CurArray;
RHS.NumTombstones = this->NumTombstones;
this->CurArray = this->SmallArray;
this->NumTombstones = 0;
return;
}
if (this->isSmall() && !RHS.isSmall()) {
std::copy(this->SmallArray, this->SmallArray+this->CurArraySize,
RHS.SmallArray);
std::swap(RHS.NumElements, this->NumElements);
std::swap(RHS.CurArraySize, this->CurArraySize);
this->CurArray = RHS.CurArray;
this->NumTombstones = RHS.NumTombstones;
RHS.CurArray = RHS.SmallArray;
RHS.NumTombstones = 0;
return;
}
assert(this->isSmall() && RHS.isSmall());
assert(this->CurArraySize == RHS.CurArraySize);
std::swap_ranges(this->SmallArray, this->SmallArray+this->CurArraySize,
RHS.SmallArray);
std::swap(this->NumElements, RHS.NumElements);
}
SmallPtrSetImplBase::~SmallPtrSetImplBase() {
if (!isSmall())
free(CurArray);
}