//===----------------------------------------------------------------------===//
#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/Compiler.h"
#include <cassert>
using namespace llvm;
}
// Otherwise, initialize it with zero buckets to avoid the allocation.
- TheTable = 0;
+ TheTable = nullptr;
NumBuckets = 0;
NumItems = 0;
NumTombstones = 0;
NumItems = 0;
NumTombstones = 0;
- TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket));
-
+ TheTable = (StringMapEntryBase **)calloc(NumBuckets+1,
+ sizeof(StringMapEntryBase **) +
+ sizeof(unsigned));
+
// Allocate one extra bucket, set it to look filled so the iterators stop at
// end.
- TheTable[NumBuckets].Item = (StringMapEntryBase*)2;
+ TheTable[NumBuckets] = (StringMapEntryBase*)2;
}
-/// HashString - Compute a hash code for the specified string.
-///
-static unsigned HashString(const char *Start, const char *End) {
- // Bernstein hash function.
- unsigned int Result = 0;
- // TODO: investigate whether a modified bernstein hash function performs
- // better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
- // X*33+c -> X*33^c
- while (Start != End)
- Result = Result * 33 + *Start++;
- Result = Result + (Result >> 5);
- return Result;
-}
-
/// LookupBucketFor - Look up the bucket that the specified string should end
/// up in. If it already exists as a key in the map, the Item pointer for the
/// specified bucket will be non-null. Otherwise, it will be null. In either
/// case, the FullHashValue field of the bucket will be set to the hash value
/// of the string.
-unsigned StringMapImpl::LookupBucketFor(const StringRef &Name) {
+unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
unsigned HTSize = NumBuckets;
if (HTSize == 0) { // Hash table unallocated so far?
init(16);
HTSize = NumBuckets;
}
- unsigned FullHashValue = HashString(Name.begin(), Name.end());
+ unsigned FullHashValue = HashString(Name);
unsigned BucketNo = FullHashValue & (HTSize-1);
-
+ unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
+
unsigned ProbeAmt = 1;
int FirstTombstone = -1;
while (1) {
- ItemBucket &Bucket = TheTable[BucketNo];
- StringMapEntryBase *BucketItem = Bucket.Item;
+ StringMapEntryBase *BucketItem = TheTable[BucketNo];
// If we found an empty bucket, this key isn't in the table yet, return it.
- if (BucketItem == 0) {
+ if (LLVM_LIKELY(!BucketItem)) {
// If we found a tombstone, we want to reuse the tombstone instead of an
// empty bucket. This reduces probing.
if (FirstTombstone != -1) {
- TheTable[FirstTombstone].FullHashValue = FullHashValue;
+ HashTable[FirstTombstone] = FullHashValue;
return FirstTombstone;
}
- Bucket.FullHashValue = FullHashValue;
+ HashTable[BucketNo] = FullHashValue;
return BucketNo;
}
if (BucketItem == getTombstoneVal()) {
// Skip over tombstones. However, remember the first one we see.
if (FirstTombstone == -1) FirstTombstone = BucketNo;
- } else if (Bucket.FullHashValue == FullHashValue) {
+ } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
// If the full hash value matches, check deeply for a match. The common
// case here is that we are only looking at the buckets (for item info
// being non-null and for the full hash value) not at the items. This
/// FindKey - Look up the bucket that contains the specified key. If it exists
/// in the map, return the bucket number of the key. Otherwise return -1.
/// This does not modify the map.
-int StringMapImpl::FindKey(const StringRef &Key) const {
+int StringMapImpl::FindKey(StringRef Key) const {
unsigned HTSize = NumBuckets;
if (HTSize == 0) return -1; // Really empty table?
- unsigned FullHashValue = HashString(Key.begin(), Key.end());
+ unsigned FullHashValue = HashString(Key);
unsigned BucketNo = FullHashValue & (HTSize-1);
-
+ unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
+
unsigned ProbeAmt = 1;
while (1) {
- ItemBucket &Bucket = TheTable[BucketNo];
- StringMapEntryBase *BucketItem = Bucket.Item;
+ StringMapEntryBase *BucketItem = TheTable[BucketNo];
// If we found an empty bucket, this key isn't in the table yet, return.
- if (BucketItem == 0)
+ if (LLVM_LIKELY(!BucketItem))
return -1;
if (BucketItem == getTombstoneVal()) {
// Ignore tombstones.
- } else if (Bucket.FullHashValue == FullHashValue) {
+ } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
// If the full hash value matches, check deeply for a match. The common
// case here is that we are only looking at the buckets (for item info
// being non-null and for the full hash value) not at the items. This
void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
const char *VStr = (char*)V + ItemSize;
StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
- V2 = V2;
+ (void)V2;
assert(V == V2 && "Didn't find key?");
}
/// RemoveKey - Remove the StringMapEntry for the specified key from the
/// table, returning it. If the key is not in the table, this returns null.
-StringMapEntryBase *StringMapImpl::RemoveKey(const StringRef &Key) {
+StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
int Bucket = FindKey(Key);
- if (Bucket == -1) return 0;
+ if (Bucket == -1) return nullptr;
- StringMapEntryBase *Result = TheTable[Bucket].Item;
- TheTable[Bucket].Item = getTombstoneVal();
+ StringMapEntryBase *Result = TheTable[Bucket];
+ TheTable[Bucket] = getTombstoneVal();
--NumItems;
++NumTombstones;
+ assert(NumItems + NumTombstones <= NumBuckets);
+
return Result;
}
/// RehashTable - Grow the table, redistributing values into the buckets with
/// the appropriate mod-of-hashtable-size.
-void StringMapImpl::RehashTable() {
- unsigned NewSize = NumBuckets*2;
+unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
+ unsigned NewSize;
+ unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
+
+ // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
+ // the buckets are empty (meaning that many are filled with tombstones),
+ // grow/rehash the table.
+ if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {
+ NewSize = NumBuckets*2;
+ } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=
+ NumBuckets / 8)) {
+ NewSize = NumBuckets;
+ } else {
+ return BucketNo;
+ }
+
+ unsigned NewBucketNo = BucketNo;
// Allocate one extra bucket which will always be non-empty. This allows the
// iterators to stop at end.
- ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket));
- NewTableArray[NewSize].Item = (StringMapEntryBase*)2;
-
+ StringMapEntryBase **NewTableArray =
+ (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) +
+ sizeof(unsigned));
+ unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
+ NewTableArray[NewSize] = (StringMapEntryBase*)2;
+
// Rehash all the items into their new buckets. Luckily :) we already have
// the hash values available, so we don't have to rehash any strings.
- for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) {
- if (IB->Item && IB->Item != getTombstoneVal()) {
+ for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
+ StringMapEntryBase *Bucket = TheTable[I];
+ if (Bucket && Bucket != getTombstoneVal()) {
// Fast case, bucket available.
- unsigned FullHash = IB->FullHashValue;
+ unsigned FullHash = HashTable[I];
unsigned NewBucket = FullHash & (NewSize-1);
- if (NewTableArray[NewBucket].Item == 0) {
- NewTableArray[FullHash & (NewSize-1)].Item = IB->Item;
- NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash;
+ if (!NewTableArray[NewBucket]) {
+ NewTableArray[FullHash & (NewSize-1)] = Bucket;
+ NewHashArray[FullHash & (NewSize-1)] = FullHash;
+ if (I == BucketNo)
+ NewBucketNo = NewBucket;
continue;
}
unsigned ProbeSize = 1;
do {
NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
- } while (NewTableArray[NewBucket].Item);
+ } while (NewTableArray[NewBucket]);
// Finally found a slot. Fill it in.
- NewTableArray[NewBucket].Item = IB->Item;
- NewTableArray[NewBucket].FullHashValue = FullHash;
+ NewTableArray[NewBucket] = Bucket;
+ NewHashArray[NewBucket] = FullHash;
+ if (I == BucketNo)
+ NewBucketNo = NewBucket;
}
}
TheTable = NewTableArray;
NumBuckets = NewSize;
+ NumTombstones = 0;
+ return NewBucketNo;
}