#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringExtras.h"
#include <cassert>
using namespace llvm;
StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
ItemSize = itemSize;
if (InitSize) {
init(InitSize);
return;
}
TheTable = 0;
NumBuckets = 0;
NumItems = 0;
NumTombstones = 0;
}
void StringMapImpl::init(unsigned InitSize) {
assert((InitSize & (InitSize-1)) == 0 &&
"Init Size must be a power of 2 or zero!");
NumBuckets = InitSize ? InitSize : 16;
NumItems = 0;
NumTombstones = 0;
TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket));
TheTable[NumBuckets].Item = (StringMapEntryBase*)2;
}
unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
unsigned HTSize = NumBuckets;
if (HTSize == 0) { init(16);
HTSize = NumBuckets;
}
unsigned FullHashValue = HashString(Name);
unsigned BucketNo = FullHashValue & (HTSize-1);
unsigned ProbeAmt = 1;
int FirstTombstone = -1;
while (1) {
ItemBucket &Bucket = TheTable[BucketNo];
StringMapEntryBase *BucketItem = Bucket.Item;
if (BucketItem == 0) {
if (FirstTombstone != -1) {
TheTable[FirstTombstone].FullHashValue = FullHashValue;
return FirstTombstone;
}
Bucket.FullHashValue = FullHashValue;
return BucketNo;
}
if (BucketItem == getTombstoneVal()) {
if (FirstTombstone == -1) FirstTombstone = BucketNo;
} else if (Bucket.FullHashValue == FullHashValue) {
char *ItemStr = (char*)BucketItem+ItemSize;
if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
return BucketNo;
}
}
BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
++ProbeAmt;
}
}
int StringMapImpl::FindKey(StringRef Key) const {
unsigned HTSize = NumBuckets;
if (HTSize == 0) return -1; unsigned FullHashValue = HashString(Key);
unsigned BucketNo = FullHashValue & (HTSize-1);
unsigned ProbeAmt = 1;
while (1) {
ItemBucket &Bucket = TheTable[BucketNo];
StringMapEntryBase *BucketItem = Bucket.Item;
if (BucketItem == 0)
return -1;
if (BucketItem == getTombstoneVal()) {
} else if (Bucket.FullHashValue == FullHashValue) {
char *ItemStr = (char*)BucketItem+ItemSize;
if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
return BucketNo;
}
}
BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
++ProbeAmt;
}
}
void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
const char *VStr = (char*)V + ItemSize;
StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
(void)V2;
assert(V == V2 && "Didn't find key?");
}
StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
int Bucket = FindKey(Key);
if (Bucket == -1) return 0;
StringMapEntryBase *Result = TheTable[Bucket].Item;
TheTable[Bucket].Item = getTombstoneVal();
--NumItems;
++NumTombstones;
assert(NumItems + NumTombstones <= NumBuckets);
return Result;
}
void StringMapImpl::RehashTable() {
unsigned NewSize;
if (NumItems*4 > NumBuckets*3) {
NewSize = NumBuckets*2;
} else if (NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) {
NewSize = NumBuckets;
} else {
return;
}
ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket));
NewTableArray[NewSize].Item = (StringMapEntryBase*)2;
for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) {
if (IB->Item && IB->Item != getTombstoneVal()) {
unsigned FullHash = IB->FullHashValue;
unsigned NewBucket = FullHash & (NewSize-1);
if (NewTableArray[NewBucket].Item == 0) {
NewTableArray[FullHash & (NewSize-1)].Item = IB->Item;
NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash;
continue;
}
unsigned ProbeSize = 1;
do {
NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
} while (NewTableArray[NewBucket].Item);
NewTableArray[NewBucket].Item = IB->Item;
NewTableArray[NewBucket].FullHashValue = FullHash;
}
}
free(TheTable);
TheTable = NewTableArray;
NumBuckets = NewSize;
NumTombstones = 0;
}