/// RehashTable - Grow the table, redistributing values into the buckets with
/// the appropriate mod-of-hashtable-size.
-void StringMapImpl::RehashTable() {
+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 (NumItems*4 > NumBuckets*3) {
+ if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {
NewSize = NumBuckets*2;
- } else if (NumBuckets-(NumItems+NumTombstones) <= NumBuckets/8) {
+ } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=
+ NumBuckets / 8)) {
NewSize = NumBuckets;
} else {
- return;
+ return BucketNo;
}
+ unsigned NewBucketNo = BucketNo;
// Allocate one extra bucket which will always be non-empty. This allows the
// iterators to stop at end.
StringMapEntryBase **NewTableArray =
if (!NewTableArray[NewBucket]) {
NewTableArray[FullHash & (NewSize-1)] = Bucket;
NewHashArray[FullHash & (NewSize-1)] = FullHash;
+ if (I == BucketNo)
+ NewBucketNo = NewBucket;
continue;
}
// Finally found a slot. Fill it in.
NewTableArray[NewBucket] = Bucket;
NewHashArray[NewBucket] = FullHash;
+ if (I == BucketNo)
+ NewBucketNo = NewBucket;
}
}
TheTable = NewTableArray;
NumBuckets = NewSize;
NumTombstones = 0;
+ return NewBucketNo;
}