X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FStringMap.h;h=a15d24eeae2511fa491b6c7badaea91d19dc48e7;hb=7eaf057e54e9b5f0469057c71d81dcfee90d9e12;hp=745428880bea5c6d30bb44e48d3dce76ae18fd63;hpb=ded2b0d0fb0d4fa09198e3d05da529d2c97214c3;p=oota-llvm.git diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 745428880be..a15d24eeae2 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Chris Lattner and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -16,6 +16,7 @@ #include "llvm/Support/Allocator.h" #include +#include namespace llvm { template @@ -26,26 +27,27 @@ namespace llvm { class StringMapEntry; /// StringMapEntryInitializer - This datatype can be partially specialized for -/// various datatypes in a stringmap to allow them to be initialized when an +/// various datatypes in a stringmap to allow them to be initialized when an /// entry is default constructed for the map. template class StringMapEntryInitializer { public: template static void Initialize(StringMapEntry &T, InitTy InitVal) { + T.second = InitVal; } }; - - + + /// StringMapEntryBase - Shared base class of StringMapEntry instances. class StringMapEntryBase { unsigned StrLen; public: explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {} - + unsigned getKeyLength() const { return StrLen; } }; - + /// StringMapImpl - This is the base class of StringMap that is shared among /// all of its instantiations. class StringMapImpl { @@ -56,11 +58,11 @@ public: /// 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; unsigned NumBuckets; @@ -77,7 +79,7 @@ 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 { @@ -87,14 +89,14 @@ protected: 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 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. @@ -113,7 +115,7 @@ public: static StringMapEntryBase *getTombstoneVal() { return (StringMapEntryBase*)-1; } - + unsigned getNumBuckets() const { return NumBuckets; } unsigned getNumItems() const { return NumItems; } @@ -126,61 +128,65 @@ public: /// and data. template class StringMapEntry : public StringMapEntryBase { - ValueTy Val; public: - explicit StringMapEntry(unsigned StrLen) - : StringMapEntryBase(StrLen), Val() {} - StringMapEntry(unsigned StrLen, const ValueTy &V) - : StringMapEntryBase(StrLen), Val(V) {} - - const ValueTy &getValue() const { return Val; } - ValueTy &getValue() { return Val; } - - void setValue(const ValueTy &V) { Val = V; } - + ValueTy second; + + explicit StringMapEntry(unsigned strLen) + : StringMapEntryBase(strLen), second() {} + StringMapEntry(unsigned strLen, const ValueTy &V) + : StringMapEntryBase(strLen), second(V) {} + + const ValueTy &getValue() const { return second; } + ValueTy &getValue() { return second; } + + void setValue(const ValueTy &V) { second = V; } + /// getKeyData - Return the start of the string data that is the key for this /// value. The string data is always stored immediately after the /// StringMapEntry object. const char *getKeyData() const {return reinterpret_cast(this+1);} - + + const char *first() const { return getKeyData(); } + /// Create - Create a StringMapEntry for the specified key and default /// construct the value. template static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, AllocatorTy &Allocator, InitType InitVal) { - unsigned KeyLength = KeyEnd-KeyStart; - + unsigned KeyLength = static_cast(KeyEnd-KeyStart); + // Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill // in. Allocate a new item with space for the string at the end and a null // terminator. - - unsigned AllocSize = sizeof(StringMapEntry)+KeyLength+1; + + unsigned AllocSize = static_cast(sizeof(StringMapEntry))+ + KeyLength+1; unsigned Alignment = alignof(); - + StringMapEntry *NewItem = static_cast(Allocator.Allocate(AllocSize,Alignment)); - + // Default construct the value. new (NewItem) StringMapEntry(KeyLength); - + // Copy the string information. char *StrBuffer = const_cast(NewItem->getKeyData()); memcpy(StrBuffer, KeyStart, KeyLength); StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. - + // Initialize the value if the client wants to. StringMapEntryInitializer::Initialize(*NewItem, InitVal); return NewItem; } - + template static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, AllocatorTy &Allocator) { - return Create(KeyStart, KeyEnd, Allocator, (void*)0); + return Create(KeyStart, KeyEnd, Allocator, 0); } - - + + /// Create - Create a StringMapEntry with normal malloc/free. template static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, @@ -190,22 +196,22 @@ public: } static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { - return Create(KeyStart, KeyEnd, (void*)0); + return Create(KeyStart, KeyEnd, ValueTy()); } - + /// GetStringMapEntryFromValue - Given a value that is known to be embedded /// into a StringMapEntry, return the StringMapEntry itself. static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) { StringMapEntry *EPtr = 0; - char *Ptr = reinterpret_cast(&V) - - (reinterpret_cast(&EPtr->Val) - + char *Ptr = reinterpret_cast(&V) - + (reinterpret_cast(&EPtr->second) - reinterpret_cast(EPtr)); return *reinterpret_cast(Ptr); } static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) { return GetStringMapEntryFromValue(const_cast(V)); } - + /// Destroy - Destroy this StringMapEntry, releasing memory back to the /// specified allocator. template @@ -214,7 +220,7 @@ public: this->~StringMapEntry(); Allocator.Deallocate(this); } - + /// Destroy this object, releasing memory back to the malloc allocator. void Destroy() { MallocAllocator A; @@ -232,16 +238,32 @@ class StringMap : public StringMapImpl { AllocatorTy Allocator; typedef StringMapEntry MapEntryTy; public: - StringMap() : StringMapImpl(sizeof(MapEntryTy)) {} + StringMap() : StringMapImpl(static_cast(sizeof(MapEntryTy))) {} explicit StringMap(unsigned InitialSize) - : StringMapImpl(InitialSize, sizeof(MapEntryTy)) {} - + : StringMapImpl(InitialSize, static_cast(sizeof(MapEntryTy))) {} + explicit StringMap(const StringMap &RHS) + : StringMapImpl(static_cast(sizeof(MapEntryTy))) { + assert(RHS.empty() && + "Copy ctor from non-empty stringmap not implemented yet!"); + } + void operator=(const StringMap &RHS) { + assert(RHS.empty() && + "assignment from non-empty stringmap not implemented yet!"); + clear(); + } + + AllocatorTy &getAllocator() { return Allocator; } const AllocatorTy &getAllocator() const { return Allocator; } + typedef const char* key_type; + typedef ValueTy mapped_type; + typedef StringMapEntry value_type; + typedef size_t size_type; + typedef StringMapConstIterator const_iterator; typedef StringMapIterator iterator; - + iterator begin() { return iterator(TheTable, NumBuckets == 0); } @@ -254,19 +276,69 @@ public: const_iterator end() const { return const_iterator(TheTable+NumBuckets, true); } - + iterator find(const char *KeyStart, const char *KeyEnd) { int Bucket = FindKey(KeyStart, KeyEnd); if (Bucket == -1) return end(); return iterator(TheTable+Bucket); } + iterator find(const char *Key) { + return find(Key, Key + strlen(Key)); + } + iterator find(const std::string &Key) { + return find(Key.data(), Key.data() + Key.size()); + } 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); } - + const_iterator find(const char *Key) const { + return find(Key, Key + strlen(Key)); + } + const_iterator find(const std::string &Key) const { + return find(Key.data(), Key.data() + Key.size()); + } + + /// lookup - Return the entry for the specified key, or a default + /// constructed value if no such entry exists. + ValueTy lookup(const char *KeyStart, const char *KeyEnd) const { + const_iterator it = find(KeyStart, KeyEnd); + if (it != end()) + return it->second; + return ValueTy(); + } + ValueTy lookup(const char *Key) const { + const_iterator it = find(Key); + if (it != end()) + return it->second; + return ValueTy(); + } + ValueTy lookup(const std::string &Key) const { + const_iterator it = find(Key); + if (it != end()) + return it->second; + return ValueTy(); + } + + ValueTy& operator[](const char *Key) { + return GetOrCreateValue(Key, Key + strlen(Key)).getValue(); + } + ValueTy& operator[](const std::string &Key) { + return GetOrCreateValue(Key.data(), Key.data() + Key.size()).getValue(); + } + + size_type count(const char *KeyStart, const char *KeyEnd) const { + return find(KeyStart, KeyEnd) == end() ? 0 : 1; + } + size_type count(const char *Key) const { + return count(Key, Key + strlen(Key)); + } + size_type count(const std::string &Key) const { + return count(Key.data(), Key.data() + Key.size()); + } + /// 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. @@ -275,101 +347,127 @@ public: LookupBucketFor(KeyValue->getKeyData(), KeyValue->getKeyData()+KeyValue->getKeyLength()); ItemBucket &Bucket = TheTable[BucketNo]; - if (Bucket.Item && Bucket.Item != getTombstoneVal()) + 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; } - + + // clear - Empties out the StringMap + void clear() { + if (empty()) return; + + // 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; + } + } + + NumItems = 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 char *KeyStart, + StringMapEntry &GetOrCreateValue(const char *KeyStart, const char *KeyEnd, InitTy Val) { unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd); ItemBucket &Bucket = TheTable[BucketNo]; if (Bucket.Item && Bucket.Item != getTombstoneVal()) return *static_cast(Bucket.Item); - + MapEntryTy *NewItem = MapEntryTy::Create(KeyStart, KeyEnd, Allocator, Val); - + 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 (ShouldRehash()) RehashTable(); return *NewItem; } - - StringMapEntry &GetOrCreateValue(const char *KeyStart, + + StringMapEntry &GetOrCreateValue(const char *KeyStart, const char *KeyEnd) { - return GetOrCreateValue(KeyStart, KeyEnd, (void*)0); + return GetOrCreateValue(KeyStart, KeyEnd, ValueTy()); } - + /// 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); } - + void erase(iterator I) { MapEntryTy &V = *I; remove(&V); V.Destroy(Allocator); } - + + bool erase(const char *Key) { + iterator I = find(Key); + if (I == end()) return false; + erase(I); + return true; + } + + bool erase(const std::string &Key) { + iterator I = find(Key); + if (I == end()) return false; + erase(I); + return true; + } + ~StringMap() { - for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { - if (I->Item && I->Item != getTombstoneVal()) - static_cast(I->Item)->Destroy(Allocator); - } + clear(); free(TheTable); } -private: - StringMap(const StringMap &); // FIXME: Implement. - void operator=(const StringMap &); // FIXME: Implement. }; - + template class StringMapConstIterator { protected: StringMapImpl::ItemBucket *Ptr; public: + typedef StringMapEntry value_type; + explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, bool NoAdvance = false) : Ptr(Bucket) { if (!NoAdvance) AdvancePastEmptyBuckets(); } - - const StringMapEntry &operator*() const { + + const value_type &operator*() const { return *static_cast*>(Ptr->Item); } - const StringMapEntry *operator->() const { + const value_type *operator->() const { return static_cast*>(Ptr->Item); } - + bool operator==(const StringMapConstIterator &RHS) const { return Ptr == RHS.Ptr; } bool operator!=(const StringMapConstIterator &RHS) const { return Ptr != RHS.Ptr; } - + inline StringMapConstIterator& operator++() { // Preincrement ++Ptr; AdvancePastEmptyBuckets(); @@ -378,7 +476,7 @@ public: StringMapConstIterator operator++(int) { // Postincrement StringMapConstIterator tmp = *this; ++*this; return tmp; } - + private: void AdvancePastEmptyBuckets() { while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) @@ -388,7 +486,7 @@ private: template class StringMapIterator : public StringMapConstIterator { -public: +public: explicit StringMapIterator(StringMapImpl::ItemBucket *Bucket, bool NoAdvance = false) : StringMapConstIterator(Bucket, NoAdvance) { @@ -404,4 +502,3 @@ public: } #endif -