X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FStringMap.h;h=ecac5dd5f66abf117a3a574ac0adc5bbf506d470;hb=50f8a53856ccfd07b70f1722863957f22db187f3;hp=5c47604db450477fd683ea6ad8f882c698f3e9fe;hpb=adf3eab7735741926c67e6fc12b952500c45a9ba;p=oota-llvm.git diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 5c47604db45..ecac5dd5f66 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. // //===----------------------------------------------------------------------===// // @@ -14,78 +14,69 @@ #ifndef LLVM_ADT_STRINGMAP_H #define LLVM_ADT_STRINGMAP_H +#include "llvm/ADT/StringRef.h" #include "llvm/Support/Allocator.h" #include +#include namespace llvm { template class StringMapConstIterator; template class StringMapIterator; + template + class StringMapEntry; - /// 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 { -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. Followed + // by an array of the actual hash values as unsigned integers. + StringMapEntryBase **TheTable; unsigned NumBuckets; unsigned NumItems; unsigned NumTombstones; unsigned ItemSize; protected: - explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) { - // Initialize the map with zero buckets to allocation. - TheTable = 0; - NumBuckets = 0; - NumItems = 0; - NumTombstones = 0; + explicit StringMapImpl(unsigned itemSize) + : TheTable(nullptr), + // Initialize the map with zero buckets to allocation. + NumBuckets(0), NumItems(0), NumTombstones(0), ItemSize(itemSize) {} + StringMapImpl(StringMapImpl &&RHS) + : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets), + NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones), + ItemSize(RHS.ItemSize) { + RHS.TheTable = nullptr; + RHS.NumBuckets = 0; + RHS.NumItems = 0; + RHS.NumTombstones = 0; } + 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 char *KeyStart, const char *KeyEnd); - + 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 char *KeyStart, const char *KeyEnd) 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. @@ -93,19 +84,26 @@ 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 char *KeyStart, const char *KeyEnd); + StringMapEntryBase *RemoveKey(StringRef Key); private: void init(unsigned Size); public: static StringMapEntryBase *getTombstoneVal() { return (StringMapEntryBase*)-1; } - + unsigned getNumBuckets() const { return NumBuckets; } unsigned getNumItems() const { return NumItems; } bool empty() const { return NumItems == 0; } unsigned size() const { return NumItems; } + + void swap(StringMapImpl &Other) { + std::swap(TheTable, Other.TheTable); + std::swap(NumBuckets, Other.NumBuckets); + std::swap(NumItems, Other.NumItems); + std::swap(NumTombstones, Other.NumTombstones); + } }; /// StringMapEntry - This is used to represent one value that is inserted into @@ -113,79 +111,107 @@ public: /// and data. template class StringMapEntry : public StringMapEntryBase { - ValueTy Val; + StringMapEntry(StringMapEntry &E) LLVM_DELETED_FUNCTION; public: - explicit StringMapEntry(unsigned StrLen) - : StringMapEntryBase(StrLen), Val() {} - StringMapEntry(unsigned StrLen, const ValueTy &V) - : StringMapEntryBase(StrLen), Val(V) {} + ValueTy second; + + explicit StringMapEntry(unsigned strLen) + : StringMapEntryBase(strLen), second() {} + StringMapEntry(unsigned strLen, ValueTy V) + : StringMapEntryBase(strLen), second(std::move(V)) {} + + StringRef getKey() const { + return StringRef(getKeyData(), getKeyLength()); + } + + const ValueTy &getValue() const { return second; } + ValueTy &getValue() { return second; } + + void setValue(const ValueTy &V) { second = V; } - const ValueTy &getValue() const { return Val; } - ValueTy &getValue() { return Val; } - - void setValue(const ValueTy &V) { Val = 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);} - + + StringRef first() const { return StringRef(getKeyData(), getKeyLength()); } + /// Create - Create a StringMapEntry for the specified key and default /// construct the value. - template + template static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, - AllocatorTy &Allocator) { - unsigned KeyLength = 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 + AllocatorTy &Allocator, + InitType InitVal) { + unsigned KeyLength = static_cast(KeyEnd-KeyStart); + + // Allocate a new item with space for the string at the end and a null // terminator. - - unsigned AllocSize = sizeof(StringMapEntry)+KeyLength+1; - unsigned Alignment = alignof(); - + 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); - + new (NewItem) StringMapEntry(KeyLength, std::move(InitVal)); + // Copy the string information. char *StrBuffer = const_cast(NewItem->getKeyData()); memcpy(StrBuffer, KeyStart, KeyLength); StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. return NewItem; } - + + template + static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, + AllocatorTy &Allocator) { + return Create(KeyStart, KeyEnd, Allocator, 0); + } + /// Create - Create a StringMapEntry with normal malloc/free. - static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { + template + static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd, + InitType InitVal) { MallocAllocator A; - return Create(KeyStart, KeyEnd, A); + return Create(KeyStart, KeyEnd, A, std::move(InitVal)); } - - + + static StringMapEntry *Create(const char *KeyStart, const char *KeyEnd) { + 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)); } - + + /// 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 void Destroy(AllocatorTy &Allocator) { // Free memory referenced by the item. + unsigned AllocSize = + static_cast(sizeof(StringMapEntry)) + getKeyLength() + 1; this->~StringMapEntry(); - Allocator.Deallocate(this); + Allocator.Deallocate(static_cast(this), AllocSize); } - + /// Destroy this object, releasing memory back to the malloc allocator. void Destroy() { MallocAllocator A; @@ -201,18 +227,42 @@ public: template class StringMap : public StringMapImpl { AllocatorTy Allocator; - typedef StringMapEntry MapEntryTy; public: - StringMap() : StringMapImpl(sizeof(MapEntryTy)) {} - explicit StringMap(unsigned InitialSize) - : StringMapImpl(InitialSize, sizeof(MapEntryTy)) {} + typedef StringMapEntry MapEntryTy; + StringMap() : StringMapImpl(static_cast(sizeof(MapEntryTy))) {} + explicit StringMap(unsigned InitialSize) + : StringMapImpl(InitialSize, static_cast(sizeof(MapEntryTy))) {} + + explicit StringMap(AllocatorTy A) + : StringMapImpl(static_cast(sizeof(MapEntryTy))), Allocator(A) {} + + StringMap(unsigned InitialSize, AllocatorTy A) + : StringMapImpl(InitialSize, static_cast(sizeof(MapEntryTy))), + Allocator(A) {} + + StringMap(StringMap &&RHS) + : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {} + + StringMap &operator=(StringMap RHS) { + StringMapImpl::swap(RHS); + std::swap(Allocator, RHS.Allocator); + return *this; + } + + // FIXME: Implement copy operations if/when they're needed. + 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); } @@ -225,116 +275,170 @@ public: const_iterator end() const { return const_iterator(TheTable+NumBuckets, true); } - - iterator find(const char *KeyStart, const char *KeyEnd) { - int Bucket = FindKey(KeyStart, KeyEnd); + + 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 char *KeyStart, const char *KeyEnd) const { - int Bucket = FindKey(KeyStart, KeyEnd); + 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(StringRef Key) const { + const_iterator it = find(Key); + if (it != end()) + return it->second; + return ValueTy(); + } + + ValueTy &operator[](StringRef Key) { + return GetOrCreateValue(Key).getValue(); + } + + /// count - Return 1 if the element is in the map, 0 otherwise. + size_type count(StringRef Key) const { + return find(Key) == end() ? 0 : 1; + } + /// 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()) + unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); + 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; - - if (ShouldRehash()) - RehashTable(); + assert(NumItems + NumTombstones <= NumBuckets); + + 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 (unsigned I = 0, E = NumBuckets; I != E; ++I) { + StringMapEntryBase *&Bucket = TheTable[I]; + if (Bucket && Bucket != getTombstoneVal()) { + static_cast(Bucket)->Destroy(Allocator); + } + Bucket = nullptr; + } + + 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. - StringMapEntry &GetOrCreateValue(const char *KeyStart, - const char *KeyEnd) { - 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); - - if (Bucket.Item == getTombstoneVal()) + template + MapEntryTy &GetOrCreateValue(StringRef Key, InitTy Val) { + unsigned BucketNo = LookupBucketFor(Key); + StringMapEntryBase *&Bucket = TheTable[BucketNo]; + if (Bucket && Bucket != getTombstoneVal()) + return *static_cast(Bucket); + + MapEntryTy *NewItem = + MapEntryTy::Create(Key.begin(), Key.end(), Allocator, std::move(Val)); + + 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; - - if (ShouldRehash()) - RehashTable(); + Bucket = NewItem; + + RehashTable(); return *NewItem; } - + + MapEntryTy &GetOrCreateValue(StringRef Key) { + return GetOrCreateValue(Key, 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(StringRef 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); + // Delete all the elements in the map, but don't reset the elements + // to default values. This is a copy of clear(), but avoids unnecessary + // work not required in the destructor. + if (!empty()) { + for (unsigned I = 0, E = NumBuckets; I != E; ++I) { + StringMapEntryBase *Bucket = TheTable[I]; + if (Bucket && Bucket != getTombstoneVal()) { + static_cast(Bucket)->Destroy(Allocator); + } + } } free(TheTable); } -private: - StringMap(const StringMap &); // FIXME: Implement. - void operator=(const StringMap &); // FIXME: Implement. }; - + template class StringMapConstIterator { protected: - StringMapImpl::ItemBucket *Ptr; + StringMapEntryBase **Ptr; public: - explicit StringMapConstIterator(StringMapImpl::ItemBucket *Bucket, + typedef StringMapEntry value_type; + + StringMapConstIterator() : Ptr(nullptr) { } + + explicit StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) : Ptr(Bucket) { if (!NoAdvance) AdvancePastEmptyBuckets(); } - - const StringMapEntry &operator*() const { - return *static_cast*>(Ptr->Item); + + const value_type &operator*() const { + return *static_cast*>(*Ptr); } - const StringMapEntry *operator->() const { - return static_cast*>(Ptr->Item); + const value_type *operator->() const { + return static_cast*>(*Ptr); } - + bool operator==(const StringMapConstIterator &RHS) const { return Ptr == RHS.Ptr; } bool operator!=(const StringMapConstIterator &RHS) const { return Ptr != RHS.Ptr; } - - inline StringMapConstIterator& operator++() { // Preincrement + + inline StringMapConstIterator& operator++() { // Preincrement ++Ptr; AdvancePastEmptyBuckets(); return *this; @@ -342,30 +446,30 @@ public: StringMapConstIterator operator++(int) { // Postincrement StringMapConstIterator tmp = *this; ++*this; return tmp; } - + private: void AdvancePastEmptyBuckets() { - while (Ptr->Item == 0 || Ptr->Item == StringMapImpl::getTombstoneVal()) + while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) ++Ptr; } }; template class StringMapIterator : public StringMapConstIterator { -public: - StringMapIterator(StringMapImpl::ItemBucket *Bucket, - bool NoAdvance = false) +public: + StringMapIterator() {} + 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); } }; } #endif -