X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FStringMap.h;h=b4497a276d0e58331f54b528dd9b0e6353f87336;hb=ac24e251014de60a16558fc0a1f2340c334d2aa8;hp=73fd635ee2bcaa0eaa99c2a40475c04b3fdaa6e0;hpb=6316fbcb04af00fe76b6526fab09f51484014b3e;p=oota-llvm.git diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 73fd635ee2b..b4497a276d0 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -17,7 +17,6 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Support/Allocator.h" #include -#include namespace llvm { template @@ -52,20 +51,11 @@ public: /// StringMapImpl - This is the base class of StringMap that is shared among /// all of its instantiations. class StringMapImpl { -public: - /// ItemBucket - The hash table consists of an array of these. If Item is - /// non-null, this is an extant entry, otherwise, it is a hole. - struct ItemBucket { - /// FullHashValue - This remembers the full hash value of the key for - /// easy scanning. - unsigned FullHashValue; - - /// Item - This is a pointer to the actual item object. - StringMapEntryBase *Item; - }; - protected: - ItemBucket *TheTable; + // Array of NumBuckets pointers to entries, null pointers are holes. + // TheTable[NumBuckets] contains a sentinel value for easy iteration. Follwed + // by an array of the actual hash values as unsigned integers. + StringMapEntryBase **TheTable; unsigned NumBuckets; unsigned NumItems; unsigned NumTombstones; @@ -81,27 +71,17 @@ 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 /// case, the FullHashValue field of the bucket will be set to the hash value /// of the string. - unsigned LookupBucketFor(const StringRef &Key); + unsigned LookupBucketFor(StringRef Key); /// 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 StringRef &Key) const; + int FindKey(StringRef Key) const; /// RemoveKey - Remove the specified StringMapEntry from the table, but do not /// delete it. This aborts if the value isn't in the table. @@ -109,7 +89,7 @@ protected: /// 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 StringRef &Key); + StringMapEntryBase *RemoveKey(StringRef Key); private: void init(unsigned Size); public: @@ -137,8 +117,8 @@ public: StringMapEntry(unsigned strLen, const ValueTy &V) : StringMapEntryBase(strLen), second(V) {} - StringRef getKey() const { - return StringRef(getKeyData(), getKeyLength()); + StringRef getKey() const { + return StringRef(getKeyData(), getKeyLength()); } const ValueTy &getValue() const { return second; } @@ -151,7 +131,7 @@ public: /// StringMapEntry object. const char *getKeyData() const {return reinterpret_cast(this+1);} - const char *first() const { return getKeyData(); } + StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } /// Create - Create a StringMapEntry for the specified key and default /// construct the value. @@ -167,7 +147,7 @@ public: unsigned AllocSize = static_cast(sizeof(StringMapEntry))+ KeyLength+1; - unsigned Alignment = alignof(); + unsigned Alignment = alignOf(); StringMapEntry *NewItem = static_cast(Allocator.Allocate(AllocSize,Alignment)); @@ -217,6 +197,14 @@ public: return GetStringMapEntryFromValue(const_cast(V)); } + /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded + /// into a StringMapEntry, return the StringMapEntry itself. + static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) { + char *Ptr = const_cast(KeyData) - sizeof(StringMapEntry); + return *reinterpret_cast(Ptr); + } + + /// Destroy - Destroy this StringMapEntry, releasing memory back to the /// specified allocator. template @@ -241,25 +229,33 @@ public: template class StringMap : public StringMapImpl { AllocatorTy Allocator; - typedef StringMapEntry MapEntryTy; public: + typedef StringMapEntry MapEntryTy; + StringMap() : StringMapImpl(static_cast(sizeof(MapEntryTy))) {} explicit StringMap(unsigned InitialSize) : StringMapImpl(InitialSize, static_cast(sizeof(MapEntryTy))) {} - explicit StringMap(const StringMap &RHS) + + explicit StringMap(AllocatorTy A) + : StringMapImpl(static_cast(sizeof(MapEntryTy))), Allocator(A) {} + + StringMap(const StringMap &RHS) : StringMapImpl(static_cast(sizeof(MapEntryTy))) { assert(RHS.empty() && "Copy ctor from non-empty stringmap not implemented yet!"); + (void)RHS; } void operator=(const StringMap &RHS) { assert(RHS.empty() && "assignment from non-empty stringmap not implemented yet!"); + (void)RHS; clear(); } - - AllocatorTy &getAllocator() { return Allocator; } - const AllocatorTy &getAllocator() const { return Allocator; } + typedef typename ReferenceAdder::result AllocatorRefTy; + typedef typename ReferenceAdder::result AllocatorCRefTy; + AllocatorRefTy getAllocator() { return Allocator; } + AllocatorCRefTy getAllocator() const { return Allocator; } typedef const char* key_type; typedef ValueTy mapped_type; @@ -282,32 +278,32 @@ public: return const_iterator(TheTable+NumBuckets, true); } - iterator find(const StringRef &Key) { + iterator find(StringRef Key) { int Bucket = FindKey(Key); if (Bucket == -1) return end(); - return iterator(TheTable+Bucket); + return iterator(TheTable+Bucket, true); } - const_iterator find(const StringRef &Key) const { + const_iterator find(StringRef Key) const { int Bucket = FindKey(Key); if (Bucket == -1) return end(); - return const_iterator(TheTable+Bucket); + return const_iterator(TheTable+Bucket, true); } /// lookup - Return the entry for the specified key, or a default /// constructed value if no such entry exists. - ValueTy lookup(const StringRef &Key) const { + ValueTy lookup(StringRef Key) const { const_iterator it = find(Key); if (it != end()) return it->second; return ValueTy(); } - ValueTy& operator[](const StringRef &Key) { + ValueTy &operator[](StringRef Key) { return GetOrCreateValue(Key).getValue(); } - size_type count(const StringRef &Key) const { + size_type count(StringRef Key) const { return find(Key) == end() ? 0 : 1; } @@ -316,17 +312,17 @@ public: /// insert it and return true. bool insert(MapEntryTy *KeyValue) { unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); - ItemBucket &Bucket = TheTable[BucketNo]; - if (Bucket.Item && Bucket.Item != getTombstoneVal()) + StringMapEntryBase *&Bucket = TheTable[BucketNo]; + if (Bucket && Bucket != getTombstoneVal()) return false; // Already exists in map. - if (Bucket.Item == getTombstoneVal()) + if (Bucket == getTombstoneVal()) --NumTombstones; - Bucket.Item = KeyValue; + Bucket = KeyValue; ++NumItems; + assert(NumItems + NumTombstones <= NumBuckets); - if (ShouldRehash()) - RehashTable(); + RehashTable(); return true; } @@ -336,59 +332,48 @@ public: // Zap all values, resetting the keys back to non-present (not tombstone), // which is safe because we're removing all elements. - for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { - if (I->Item && I->Item != getTombstoneVal()) { - static_cast(I->Item)->Destroy(Allocator); - I->Item = 0; + for (unsigned I = 0, E = NumBuckets; I != E; ++I) { + StringMapEntryBase *&Bucket = TheTable[I]; + if (Bucket && Bucket != getTombstoneVal()) { + static_cast(Bucket)->Destroy(Allocator); + Bucket = 0; } } NumItems = 0; + NumTombstones = 0; } /// GetOrCreateValue - Look up the specified key in the table. If a value /// exists, return it. Otherwise, default construct a value, insert it, and /// return. template - StringMapEntry &GetOrCreateValue(const StringRef &Key, - InitTy Val) { + MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { unsigned BucketNo = LookupBucketFor(Key); - ItemBucket &Bucket = TheTable[BucketNo]; - if (Bucket.Item && Bucket.Item != getTombstoneVal()) - return *static_cast(Bucket.Item); + StringMapEntryBase *&Bucket = TheTable[BucketNo]; + if (Bucket && Bucket != getTombstoneVal()) + return *static_cast(Bucket); MapEntryTy *NewItem = MapEntryTy::Create(Key.begin(), Key.end(), Allocator, Val); - if (Bucket.Item == getTombstoneVal()) + if (Bucket == getTombstoneVal()) --NumTombstones; ++NumItems; + assert(NumItems + NumTombstones <= NumBuckets); // Fill in the bucket for the hash table. The FullHashValue was already // filled in by LookupBucketFor. - Bucket.Item = NewItem; + Bucket = NewItem; - if (ShouldRehash()) - RehashTable(); + RehashTable(); return *NewItem; } - StringMapEntry &GetOrCreateValue(const StringRef &Key) { + MapEntryTy &GetOrCreateValue(StringRef Key) { return GetOrCreateValue(Key, ValueTy()); } - template - StringMapEntry &GetOrCreateValue(const char *KeyStart, - const char *KeyEnd, - InitTy Val) { - return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart), Val); - } - - StringMapEntry &GetOrCreateValue(const char *KeyStart, - const char *KeyEnd) { - return GetOrCreateValue(StringRef(KeyStart, KeyEnd - KeyStart)); - } - /// 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) { @@ -401,7 +386,7 @@ public: V.Destroy(Allocator); } - bool erase(const StringRef &Key) { + bool erase(StringRef Key) { iterator I = find(Key); if (I == end()) return false; erase(I); @@ -418,21 +403,21 @@ public: template class StringMapConstIterator { protected: - StringMapImpl::ItemBucket *Ptr; + StringMapEntryBase **Ptr; public: typedef StringMapEntry value_type; - explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, + explicit StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) : Ptr(Bucket) { if (!NoAdvance) AdvancePastEmptyBuckets(); } const value_type &operator*() const { - return *static_cast*>(Ptr->Item); + return *static_cast*>(*Ptr); } const value_type *operator->() const { - return static_cast*>(Ptr->Item); + return static_cast*>(*Ptr); } bool operator==(const StringMapConstIterator &RHS) const { @@ -453,7 +438,7 @@ public: private: void AdvancePastEmptyBuckets() { - while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) + while (*Ptr == 0 || *Ptr == StringMapImpl::getTombstoneVal()) ++Ptr; } }; @@ -461,15 +446,15 @@ private: template class StringMapIterator : public StringMapConstIterator { public: - explicit StringMapIterator(StringMapImpl::ItemBucket *Bucket, + explicit StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) : StringMapConstIterator(Bucket, NoAdvance) { } StringMapEntry &operator*() const { - return *static_cast*>(this->Ptr->Item); + return *static_cast*>(*this->Ptr); } StringMapEntry *operator->() const { - return static_cast*>(this->Ptr->Item); + return static_cast*>(*this->Ptr); } };