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 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.
- if (NumItems*4 > NumBuckets*3 ||
- NumBuckets-(NumItems+NumTombstones) < NumBuckets/8)
+ if (ShouldRehash())
RehashTable();
return true;
}
// filled in by LookupBucketFor.
Bucket.Item = NewItem;
- // 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.
- if (NumItems*4 > NumBuckets*3 ||
- NumBuckets-(NumItems+NumTombstones) < NumBuckets/8)
+ if (ShouldRehash())
RehashTable();
return *NewItem;
}
~StringMap() {
for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) {
- if (MapEntryTy *Id = static_cast<MapEntryTy*>(I->Item))
- Id->Destroy(Allocator);
+ if (I->Item && I->Item != getTombstoneVal())
+ static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator);
}
delete [] TheTable;
}