diff --git a/llvm/include/llvm/ADT/StringMap.h b/llvm/include/llvm/ADT/StringMap.h --- a/llvm/include/llvm/ADT/StringMap.h +++ b/llvm/include/llvm/ADT/StringMap.h @@ -13,8 +13,7 @@ #ifndef LLVM_ADT_STRINGMAP_H #define LLVM_ADT_STRINGMAP_H -#include "llvm/ADT/StringRef.h" -#include "llvm/Support/AllocatorBase.h" +#include "llvm/ADT/StringMapEntry.h" #include "llvm/Support/PointerLikeTypeTraits.h" #include #include @@ -25,16 +24,6 @@ template class StringMapIterator; template class StringMapKeyIterator; -/// StringMapEntryBase - Shared base class of StringMapEntry instances. -class StringMapEntryBase { - size_t StrLen; - -public: - explicit StringMapEntryBase(size_t Len) : StrLen(Len) {} - - size_t getKeyLength() const { return StrLen; } -}; - /// StringMapImpl - This is the base class of StringMap that is shared among /// all of its instantiations. class StringMapImpl { @@ -108,122 +97,6 @@ } }; -/// StringMapEntryStorage - Holds the value in a StringMapEntry. -/// -/// Factored out into a separate base class to make it easier to specialize. -/// This is primarily intended to support StringSet, which doesn't need a value -/// stored at all. -template -class StringMapEntryStorage : public StringMapEntryBase { -public: - ValueTy second; - - explicit StringMapEntryStorage(size_t strLen) - : StringMapEntryBase(strLen), second() {} - template - StringMapEntryStorage(size_t strLen, InitTy &&... InitVals) - : StringMapEntryBase(strLen), second(std::forward(InitVals)...) {} - StringMapEntryStorage(StringMapEntryStorage &E) = delete; - - const ValueTy &getValue() const { return second; } - ValueTy &getValue() { return second; } - - void setValue(const ValueTy &V) { second = V; } -}; - -template <> class StringMapEntryStorage : public StringMapEntryBase { -public: - explicit StringMapEntryStorage(size_t strLen, NoneType none = None) - : StringMapEntryBase(strLen) {} - StringMapEntryStorage(StringMapEntryStorage &E) = delete; - - NoneType getValue() const { return None; } -}; - -/// StringMapEntry - This is used to represent one value that is inserted into -/// a StringMap. It contains the Value itself and the key: the string length -/// and data. -template -class StringMapEntry final : public StringMapEntryStorage { -public: - using StringMapEntryStorage::StringMapEntryStorage; - - StringRef getKey() const { - return StringRef(getKeyData(), this->getKeyLength()); - } - - /// 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(), this->getKeyLength()); - } - - /// Create a StringMapEntry for the specified key construct the value using - /// \p InitiVals. - template - static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator, - InitTy &&... InitVals) { - size_t KeyLength = Key.size(); - - // Allocate a new item with space for the string at the end and a null - // terminator. - size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1; - size_t Alignment = alignof(StringMapEntry); - - StringMapEntry *NewItem = - static_cast(Allocator.Allocate(AllocSize, Alignment)); - assert(NewItem && "Unhandled out-of-memory"); - - // Construct the value. - new (NewItem) StringMapEntry(KeyLength, std::forward(InitVals)...); - - // Copy the string information. - char *StrBuffer = const_cast(NewItem->getKeyData()); - if (KeyLength > 0) - memcpy(StrBuffer, Key.data(), KeyLength); - StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. - return NewItem; - } - - /// Create - Create a StringMapEntry with normal malloc/free. - template - static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) { - MallocAllocator A; - return Create(Key, A, std::forward(InitVal)...); - } - - static StringMapEntry *Create(StringRef Key) { - return Create(Key, ValueTy()); - } - - /// 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. - size_t AllocSize = sizeof(StringMapEntry) + this->getKeyLength() + 1; - this->~StringMapEntry(); - Allocator.Deallocate(static_cast(this), AllocSize); - } - - /// Destroy this object, releasing memory back to the malloc allocator. - void Destroy() { - MallocAllocator A; - Destroy(A); - } -}; - /// StringMap - This is an unconventional map that is specialized for handling /// keys that are "strings", which are basically ranges of bytes. This does some /// funky memory allocation and hashing things to make it extremely efficient, diff --git a/llvm/include/llvm/ADT/StringMapEntry.h b/llvm/include/llvm/ADT/StringMapEntry.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/StringMapEntry.h @@ -0,0 +1,152 @@ +//===- StringMapEntry.h - String Hash table map interface -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the StringMapEntry class - it is intended to be a low +// dependency implementation detail of StringMap that is more suitable for +// inclusion in public headers than StringMap.h itself is. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_STRINGMAPENTRY_H +#define LLVM_ADT_STRINGMAPENTRY_H + +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/AllocatorBase.h" + +namespace llvm { + +/// StringMapEntryBase - Shared base class of StringMapEntry instances. +class StringMapEntryBase { + size_t keyLength; + +public: + explicit StringMapEntryBase(size_t keyLength) : keyLength(keyLength) {} + + size_t getKeyLength() const { return keyLength; } +}; + +/// StringMapEntryStorage - Holds the value in a StringMapEntry. +/// +/// Factored out into a separate base class to make it easier to specialize. +/// This is primarily intended to support StringSet, which doesn't need a value +/// stored at all. +template +class StringMapEntryStorage : public StringMapEntryBase { +public: + ValueTy second; + + explicit StringMapEntryStorage(size_t keyLength) + : StringMapEntryBase(keyLength), second() {} + template + StringMapEntryStorage(size_t keyLength, InitTy &&... initVals) + : StringMapEntryBase(keyLength), + second(std::forward(initVals)...) {} + StringMapEntryStorage(StringMapEntryStorage &e) = delete; + + const ValueTy &getValue() const { return second; } + ValueTy &getValue() { return second; } + + void setValue(const ValueTy &V) { second = V; } +}; + +template <> class StringMapEntryStorage : public StringMapEntryBase { +public: + explicit StringMapEntryStorage(size_t keyLength, NoneType none = None) + : StringMapEntryBase(keyLength) {} + StringMapEntryStorage(StringMapEntryStorage &entry) = delete; + + NoneType getValue() const { return None; } +}; + +/// StringMapEntry - This is used to represent one value that is inserted into +/// a StringMap. It contains the Value itself and the key: the string length +/// and data. +template +class StringMapEntry final : public StringMapEntryStorage { +public: + using StringMapEntryStorage::StringMapEntryStorage; + + StringRef getKey() const { + return StringRef(getKeyData(), this->getKeyLength()); + } + + /// 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(), this->getKeyLength()); + } + + /// Create a StringMapEntry for the specified key construct the value using + /// \p InitiVals. + template + static StringMapEntry *Create(StringRef key, AllocatorTy &allocator, + InitTy &&... initVals) { + size_t keyLength = key.size(); + + // Allocate a new item with space for the string at the end and a null + // terminator. + size_t allocSize = sizeof(StringMapEntry) + keyLength + 1; + size_t alignment = alignof(StringMapEntry); + + StringMapEntry *newItem = + static_cast(allocator.Allocate(allocSize, alignment)); + assert(newItem && "Unhandled out-of-memory"); + + // Construct the value. + new (newItem) StringMapEntry(keyLength, std::forward(initVals)...); + + // Copy the string information. + char *strBuffer = const_cast(newItem->getKeyData()); + if (keyLength > 0) + memcpy(strBuffer, key.data(), keyLength); + strBuffer[keyLength] = 0; // Null terminate for convenience of clients. + return newItem; + } + + /// Create - Create a StringMapEntry with normal malloc/free. + template + static StringMapEntry *Create(StringRef key, InitType &&... initVal) { + MallocAllocator allocator; + return Create(key, allocator, std::forward(initVal)...); + } + + static StringMapEntry *Create(StringRef key) { + return Create(key, ValueTy()); + } + + /// 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. + size_t AllocSize = sizeof(StringMapEntry) + this->getKeyLength() + 1; + this->~StringMapEntry(); + allocator.Deallocate(static_cast(this), AllocSize); + } + + /// Destroy this object, releasing memory back to the malloc allocator. + void Destroy() { + MallocAllocator allocator; + Destroy(allocator); + } +}; + +} // end namespace llvm + +#endif // LLVM_ADT_STRINGMAPENTRY_H diff --git a/llvm/lib/Support/StringMap.cpp b/llvm/lib/Support/StringMap.cpp --- a/llvm/lib/Support/StringMap.cpp +++ b/llvm/lib/Support/StringMap.cpp @@ -12,10 +12,8 @@ #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringExtras.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/DJB.h" #include "llvm/Support/MathExtras.h" -#include using namespace llvm; @@ -50,23 +48,22 @@ } void StringMapImpl::init(unsigned InitSize) { - assert((InitSize & (InitSize-1)) == 0 && + assert((InitSize & (InitSize - 1)) == 0 && "Init Size must be a power of 2 or zero!"); unsigned NewNumBuckets = InitSize ? InitSize : 16; NumItems = 0; NumTombstones = 0; - TheTable = static_cast( - safe_calloc(NewNumBuckets+1, - sizeof(StringMapEntryBase **) + sizeof(unsigned))); + TheTable = static_cast(safe_calloc( + NewNumBuckets + 1, sizeof(StringMapEntryBase **) + sizeof(unsigned))); // Set the member only if TheTable was successfully allocated NumBuckets = NewNumBuckets; // Allocate one extra bucket, set it to look filled so the iterators stop at // end. - TheTable[NumBuckets] = (StringMapEntryBase*)2; + TheTable[NumBuckets] = (StringMapEntryBase *)2; } /// LookupBucketFor - Look up the bucket that the specified string should end @@ -76,12 +73,12 @@ /// of the string. unsigned StringMapImpl::LookupBucketFor(StringRef Name) { unsigned HTSize = NumBuckets; - if (HTSize == 0) { // Hash table unallocated so far? + if (HTSize == 0) { // Hash table unallocated so far? init(16); HTSize = NumBuckets; } unsigned FullHashValue = djbHash(Name, 0); - unsigned BucketNo = FullHashValue & (HTSize-1); + unsigned BucketNo = FullHashValue & (HTSize - 1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); unsigned ProbeAmt = 1; @@ -103,7 +100,8 @@ if (BucketItem == getTombstoneVal()) { // Skip over tombstones. However, remember the first one we see. - if (FirstTombstone == -1) FirstTombstone = BucketNo; + if (FirstTombstone == -1) + FirstTombstone = BucketNo; } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { // If the full hash value matches, check deeply for a match. The common // case here is that we are only looking at the buckets (for item info @@ -112,7 +110,7 @@ // Do the comparison like this because Name isn't necessarily // null-terminated! - char *ItemStr = (char*)BucketItem+ItemSize; + char *ItemStr = (char *)BucketItem + ItemSize; if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) { // We found a match! return BucketNo; @@ -120,7 +118,7 @@ } // Okay, we didn't find the item. Probe to the next bucket. - BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); + BucketNo = (BucketNo + ProbeAmt) & (HTSize - 1); // Use quadratic probing, it has fewer clumping artifacts than linear // probing and has good cache behavior in the common case. @@ -133,9 +131,10 @@ /// This does not modify the map. int StringMapImpl::FindKey(StringRef Key) const { unsigned HTSize = NumBuckets; - if (HTSize == 0) return -1; // Really empty table? + if (HTSize == 0) + return -1; // Really empty table? unsigned FullHashValue = djbHash(Key, 0); - unsigned BucketNo = FullHashValue & (HTSize-1); + unsigned BucketNo = FullHashValue & (HTSize - 1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); unsigned ProbeAmt = 1; @@ -155,7 +154,7 @@ // Do the comparison like this because NameStart isn't necessarily // null-terminated! - char *ItemStr = (char*)BucketItem+ItemSize; + char *ItemStr = (char *)BucketItem + ItemSize; if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) { // We found a match! return BucketNo; @@ -163,7 +162,7 @@ } // Okay, we didn't find the item. Probe to the next bucket. - BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); + BucketNo = (BucketNo + ProbeAmt) & (HTSize - 1); // Use quadratic probing, it has fewer clumping artifacts than linear // probing and has good cache behavior in the common case. @@ -174,7 +173,7 @@ /// RemoveKey - Remove the specified StringMapEntry from the table, but do not /// delete it. This aborts if the value isn't in the table. void StringMapImpl::RemoveKey(StringMapEntryBase *V) { - const char *VStr = (char*)V + ItemSize; + const char *VStr = (char *)V + ItemSize; StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); (void)V2; assert(V == V2 && "Didn't find key?"); @@ -184,7 +183,8 @@ /// table, returning it. If the key is not in the table, this returns null. StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { int Bucket = FindKey(Key); - if (Bucket == -1) return nullptr; + if (Bucket == -1) + return nullptr; StringMapEntryBase *Result = TheTable[Bucket]; TheTable[Bucket] = getTombstoneVal(); @@ -205,7 +205,7 @@ // the buckets are empty (meaning that many are filled with tombstones), // grow/rehash the table. if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) { - NewSize = NumBuckets*2; + NewSize = NumBuckets * 2; } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <= NumBuckets / 8)) { NewSize = NumBuckets; @@ -216,11 +216,11 @@ unsigned NewBucketNo = BucketNo; // Allocate one extra bucket which will always be non-empty. This allows the // iterators to stop at end. - auto NewTableArray = static_cast( - safe_calloc(NewSize+1, sizeof(StringMapEntryBase *) + sizeof(unsigned))); + auto NewTableArray = static_cast(safe_calloc( + NewSize + 1, sizeof(StringMapEntryBase *) + sizeof(unsigned))); unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1); - NewTableArray[NewSize] = (StringMapEntryBase*)2; + NewTableArray[NewSize] = (StringMapEntryBase *)2; // Rehash all the items into their new buckets. Luckily :) we already have // the hash values available, so we don't have to rehash any strings. @@ -229,10 +229,10 @@ if (Bucket && Bucket != getTombstoneVal()) { // Fast case, bucket available. unsigned FullHash = HashTable[I]; - unsigned NewBucket = FullHash & (NewSize-1); + unsigned NewBucket = FullHash & (NewSize - 1); if (!NewTableArray[NewBucket]) { - NewTableArray[FullHash & (NewSize-1)] = Bucket; - NewHashArray[FullHash & (NewSize-1)] = FullHash; + NewTableArray[FullHash & (NewSize - 1)] = Bucket; + NewHashArray[FullHash & (NewSize - 1)] = FullHash; if (I == BucketNo) NewBucketNo = NewBucket; continue; @@ -241,7 +241,7 @@ // Otherwise probe for a spot. unsigned ProbeSize = 1; do { - NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); + NewBucket = (NewBucket + ProbeSize++) & (NewSize - 1); } while (NewTableArray[NewBucket]); // Finally found a slot. Fill it in.