ItemBucket *TheTable;
unsigned NumBuckets;
unsigned NumItems;
+ unsigned NumTombstones;
unsigned ItemSize;
protected:
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
/// of the string.
unsigned LookupBucketFor(const char *KeyStart, const char *KeyEnd);
+ /// 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 FindKey(const char *KeyStart, const char *KeyEnd) const;
+
+ /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
+ /// delete it. This aborts if the value isn't in the table.
+ void RemoveKey(StringMapEntryBase *V);
+
+ /// 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);
+
public:
static StringMapEntryBase *getTombstoneVal() {
return (StringMapEntryBase*)-1;
const_iterator begin() const { return const_iterator(TheTable); }
const_iterator end() const { return const_iterator(TheTable+NumBuckets); }
- /// FindValue - Look up the specified key in the map. If it exists, return a
- /// pointer to the element, otherwise return null.
- MapEntryTy *FindValue(const char *KeyStart, const char *KeyEnd) {
- unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
- return static_cast<MapEntryTy*>(TheTable[BucketNo].Item);
+
+ iterator find(const char *KeyStart, const char *KeyEnd) {
+ int Bucket = FindKey(KeyStart, KeyEnd);
+ if (Bucket == -1) return end();
+ return iterator(TheTable+Bucket);
+ }
+
+ const_iterator find(const char *KeyStart, const char *KeyEnd) const {
+ int Bucket = FindKey(KeyStart, KeyEnd);
+ if (Bucket == -1) return end();
+ return const_iterator(TheTable+Bucket);
+ }
+
+ /// insert - Insert the specified key/value pair into the map. If the key
+ /// already exists in the map, return false and ignore the request, otherwise
+ /// insert it and return true.
+ bool insert(MapEntryTy *KeyValue) {
+ unsigned BucketNo =
+ LookupBucketFor(KeyValue->getKeyData(),
+ KeyValue->getKeyData()+KeyValue->getKeyLength());
+ ItemBucket &Bucket = TheTable[BucketNo];
+ if (Bucket.Item && Bucket.Item != getTombstoneVal())
+ return false; // Already exists in map.
+
+ if (Bucket.Item == getTombstoneVal())
+ --NumTombstones;
+ Bucket.Item = KeyValue;
+ ++NumItems;
+
+ if (ShouldRehash())
+ RehashTable();
+ return true;
}
/// GetOrCreateValue - Look up the specified key in the table. If a value
const char *KeyEnd) {
unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
ItemBucket &Bucket = TheTable[BucketNo];
- if (Bucket.Item)
+ if (Bucket.Item && Bucket.Item != getTombstoneVal())
return *static_cast<MapEntryTy*>(Bucket.Item);
MapEntryTy *NewItem = MapEntryTy::Create(KeyStart, KeyEnd, Allocator);
+
+ if (Bucket.Item == getTombstoneVal())
+ --NumTombstones;
++NumItems;
// Fill in the bucket for the hash table. The FullHashValue was already
// filled in by LookupBucketFor.
Bucket.Item = NewItem;
- // If the hash table is now more than 3/4 full, rehash into a larger table.
- if (NumItems > NumBuckets*3/4)
+ if (ShouldRehash())
RehashTable();
return *NewItem;
}
+ /// remove - Remove the specified key/value pair from the map, but do not
+ /// erase it. This aborts if the key is not in the map.
+ void remove(MapEntryTy *KeyValue) {
+ RemoveKey(KeyValue);
+ }
+
~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;
}
template<typename ValueTy>
class StringMapConstIterator {
+protected:
StringMapImpl::ItemBucket *Ptr;
public:
StringMapConstIterator(StringMapImpl::ItemBucket *Bucket) : Ptr(Bucket) {