diff options
author | Chris Lattner <sabre@nondot.org> | 2007-02-11 20:58:00 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2007-02-11 20:58:00 +0000 |
commit | 44dcd01cb3424420d79d5811fa8c1c052411f975 (patch) | |
tree | 924d277f075907d5eda297880467fcbec73fab4d /include | |
parent | ec68fd4391dd401f995b8e9eec3393698dbdf2d7 (diff) | |
download | external_llvm-44dcd01cb3424420d79d5811fa8c1c052411f975.tar.gz external_llvm-44dcd01cb3424420d79d5811fa8c1c052411f975.tar.bz2 external_llvm-44dcd01cb3424420d79d5811fa8c1c052411f975.zip |
Add support for removing elements out of StringMap.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34185 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include')
-rw-r--r-- | include/llvm/ADT/StringMap.h | 43 |
1 files changed, 42 insertions, 1 deletions
diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 7cc9ce7b6c..243f9cd13f 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -52,6 +52,7 @@ protected: ItemBucket *TheTable; unsigned NumBuckets; unsigned NumItems; + unsigned NumTombstones; unsigned ItemSize; protected: StringMapImpl(unsigned InitSize, unsigned ItemSize); @@ -68,6 +69,14 @@ protected: /// 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() { @@ -193,6 +202,28 @@ public: 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 the hash table is now more than 3/4 full, rehash into a larger table. + if (NumItems > NumBuckets*3/4) + RehashTable(); + return true; + } + /// GetOrCreateValue - Look up the specified key in the table. If a value /// exists, return it. Otherwise, default construct a value, insert it, and /// return. @@ -200,10 +231,13 @@ public: 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 @@ -216,6 +250,12 @@ public: 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)) @@ -228,6 +268,7 @@ public: template<typename ValueTy> class StringMapConstIterator { +protected: StringMapImpl::ItemBucket *Ptr; public: StringMapConstIterator(StringMapImpl::ItemBucket *Bucket) : Ptr(Bucket) { |