StringMapImpl(unsigned InitSize, unsigned ItemSize);
void RehashTable();
- /// ShouldRehash - Return true if the table should be rehashed after a new
- /// element was recently inserted.
- bool ShouldRehash() const {
- // 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 the table.
- return NumItems*4 > NumBuckets*3 ||
- NumBuckets-(NumItems+NumTombstones) < NumBuckets/8;
- }
-
/// 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
Bucket.Item = KeyValue;
++NumItems;
- if (ShouldRehash())
- RehashTable();
+ RehashTable();
return true;
}
// filled in by LookupBucketFor.
Bucket.Item = NewItem;
- if (ShouldRehash())
- RehashTable();
+ RehashTable();
return *NewItem;
}
/// RehashTable - Grow the table, redistributing values into the buckets with
/// the appropriate mod-of-hashtable-size.
void StringMapImpl::RehashTable() {
- unsigned NewSize = NumBuckets*2;
+ unsigned NewSize;
+
+ // 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) {
+ NewSize = NumBuckets*2;
+ } else if (NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) {
+ NewSize = NumBuckets;
+ } else {
+ return;
+ }
+
// 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));