unsigned NumTombstones;
unsigned ItemSize;
protected:
+ StringMapImpl(unsigned itemSize) : ItemSize(itemSize) { init(16); }
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
/// 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 *RemoveKey(const char *KeyStart, const char *KeyEnd);
-
+private:
+ void init(unsigned Size);
public:
static StringMapEntryBase *getTombstoneVal() {
return (StringMapEntryBase*)-1;
AllocatorTy Allocator;
typedef StringMapEntry<ValueTy> MapEntryTy;
public:
- StringMap(unsigned InitialSize = 0)
+ StringMap() : StringMapImpl(sizeof(MapEntryTy)) {}
+ StringMap(unsigned InitialSize)
: StringMapImpl(InitialSize, sizeof(MapEntryTy)) {}
AllocatorTy &getAllocator() { return Allocator; }
typedef StringMapConstIterator<ValueTy> const_iterator;
typedef StringMapIterator<ValueTy> iterator;
- iterator begin() { return iterator(TheTable); }
- iterator end() { return iterator(TheTable+NumBuckets); }
- const_iterator begin() const { return const_iterator(TheTable); }
- const_iterator end() const { return const_iterator(TheTable+NumBuckets); }
-
+ iterator begin() {
+ return iterator(TheTable, NumBuckets == 0);
+ }
+ iterator end() {
+ return iterator(TheTable+NumBuckets, true);
+ }
+ const_iterator begin() const {
+ return const_iterator(TheTable, NumBuckets == 0);
+ }
+ const_iterator end() const {
+ return const_iterator(TheTable+NumBuckets, true);
+ }
iterator find(const char *KeyStart, const char *KeyEnd) {
int Bucket = FindKey(KeyStart, KeyEnd);
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;
+ free(TheTable);
}
};
protected:
StringMapImpl::ItemBucket *Ptr;
public:
- StringMapConstIterator(StringMapImpl::ItemBucket *Bucket) : Ptr(Bucket) {
- AdvancePastEmptyBuckets();
+ StringMapConstIterator(StringMapImpl::ItemBucket *Bucket,
+ bool NoAdvance = false)
+ : Ptr(Bucket) {
+ if (!NoAdvance) AdvancePastEmptyBuckets();
}
const StringMapEntry<ValueTy> &operator*() const {
template<typename ValueTy>
class StringMapIterator : public StringMapConstIterator<ValueTy> {
public:
- StringMapIterator(StringMapImpl::ItemBucket *Bucket)
- : StringMapConstIterator<ValueTy>(Bucket) {
+ StringMapIterator(StringMapImpl::ItemBucket *Bucket,
+ bool NoAdvance = false)
+ : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
}
StringMapEntry<ValueTy> &operator*() const {
return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item);