//===- StringMap.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 StringMap class. // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_STRINGMAP_H #define LLVM_ADT_STRINGMAP_H #include "llvm/ADT/StringRef.h" #include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/PointerLikeTypeTraits.h" #include "llvm/Support/ErrorHandling.h" #include #include #include #include #include #include #include #include namespace llvm { template class StringMapConstIterator; 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 { protected: // 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 = nullptr; unsigned NumBuckets = 0; unsigned NumItems = 0; unsigned NumTombstones = 0; unsigned ItemSize; protected: explicit StringMapImpl(unsigned itemSize) : 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); unsigned RehashTable(unsigned BucketNo = 0); /// 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(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(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. 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(StringRef Key); /// Allocate the table with the specified number of buckets and otherwise /// setup the map as empty. void init(unsigned Size); public: static StringMapEntryBase *getTombstoneVal() { uintptr_t Val = static_cast(-1); Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; return reinterpret_cast(Val); } 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); } }; /// 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, /// storing the string data *after* the value in the map. template class StringMap : public StringMapImpl { AllocatorTy Allocator; public: using MapEntryTy = StringMapEntry; 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(std::initializer_list> List) : StringMapImpl(List.size(), static_cast(sizeof(MapEntryTy))) { for (const auto &P : List) { insert(P); } } StringMap(StringMap &&RHS) : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {} StringMap(const StringMap &RHS) : StringMapImpl(static_cast(sizeof(MapEntryTy))), Allocator(RHS.Allocator) { if (RHS.empty()) return; // Allocate TheTable of the same size as RHS's TheTable, and set the // sentinel appropriately (and NumBuckets). init(RHS.NumBuckets); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1), *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1); NumItems = RHS.NumItems; NumTombstones = RHS.NumTombstones; for (unsigned I = 0, E = NumBuckets; I != E; ++I) { StringMapEntryBase *Bucket = RHS.TheTable[I]; if (!Bucket || Bucket == getTombstoneVal()) { TheTable[I] = Bucket; continue; } TheTable[I] = MapEntryTy::Create( static_cast(Bucket)->getKey(), Allocator, static_cast(Bucket)->getValue()); HashTable[I] = RHSHashTable[I]; } // Note that here we've copied everything from the RHS into this object, // tombstones included. We could, instead, have re-probed for each key to // instantiate this new object without any tombstone buckets. The // assumption here is that items are rarely deleted from most StringMaps, // and so tombstones are rare, so the cost of re-probing for all inputs is // not worthwhile. } StringMap &operator=(StringMap RHS) { StringMapImpl::swap(RHS); std::swap(Allocator, RHS.Allocator); return *this; } ~StringMap() { // 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); } AllocatorTy &getAllocator() { return Allocator; } const AllocatorTy &getAllocator() const { return Allocator; } using key_type = const char*; using mapped_type = ValueTy; using value_type = StringMapEntry; using size_type = size_t; using const_iterator = StringMapConstIterator; using iterator = StringMapIterator; iterator begin() { return iterator(TheTable, NumBuckets == 0); } iterator end() { return iterator(TheTable+NumBuckets, true); } const_iterator begin() const { return const_iterator(TheTable, NumBuckets == 0); } const_iterator end() const { return const_iterator(TheTable+NumBuckets, true); } iterator_range> keys() const { return make_range(StringMapKeyIterator(begin()), StringMapKeyIterator(end())); } iterator find(StringRef Key) { int Bucket = FindKey(Key); if (Bucket == -1) return end(); return iterator(TheTable+Bucket, true); } const_iterator find(StringRef Key) const { int Bucket = FindKey(Key); if (Bucket == -1) return end(); 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(); } /// Lookup the ValueTy for the \p Key, or create a default constructed value /// if the key is not in the map. ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; } /// count - Return 1 if the element is in the map, 0 otherwise. size_type count(StringRef Key) const { return find(Key) == end() ? 0 : 1; } template size_type count(const StringMapEntry &MapEntry) const { return count(MapEntry.getKey()); } /// 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->getKey()); StringMapEntryBase *&Bucket = TheTable[BucketNo]; if (Bucket && Bucket != getTombstoneVal()) return false; // Already exists in map. if (Bucket == getTombstoneVal()) --NumTombstones; Bucket = KeyValue; ++NumItems; assert(NumItems + NumTombstones <= NumBuckets); RehashTable(); return true; } /// insert - Inserts the specified key/value pair into the map if the key /// isn't already in the map. The bool component of the returned pair is true /// if and only if the insertion takes place, and the iterator component of /// the pair points to the element with key equivalent to the key of the pair. std::pair insert(std::pair KV) { return try_emplace(KV.first, std::move(KV.second)); } /// Inserts an element or assigns to the current element if the key already /// exists. The return type is the same as try_emplace. template std::pair insert_or_assign(StringRef Key, V &&Val) { auto Ret = try_emplace(Key, std::forward(Val)); if (!Ret.second) Ret.first->second = std::forward(Val); return Ret; } /// Emplace a new element for the specified key into the map if the key isn't /// already in the map. The bool component of the returned pair is true /// if and only if the insertion takes place, and the iterator component of /// the pair points to the element with key equivalent to the key of the pair. template std::pair try_emplace(StringRef Key, ArgsTy &&... Args) { unsigned BucketNo = LookupBucketFor(Key); StringMapEntryBase *&Bucket = TheTable[BucketNo]; if (Bucket && Bucket != getTombstoneVal()) return std::make_pair(iterator(TheTable + BucketNo, false), false); // Already exists in map. if (Bucket == getTombstoneVal()) --NumTombstones; Bucket = MapEntryTy::Create(Key, Allocator, std::forward(Args)...); ++NumItems; assert(NumItems + NumTombstones <= NumBuckets); BucketNo = RehashTable(BucketNo); return std::make_pair(iterator(TheTable + BucketNo, false), 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; } /// 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; } }; template class StringMapIterBase : public iterator_facade_base { protected: StringMapEntryBase **Ptr = nullptr; public: StringMapIterBase() = default; explicit StringMapIterBase(StringMapEntryBase **Bucket, bool NoAdvance = false) : Ptr(Bucket) { if (!NoAdvance) AdvancePastEmptyBuckets(); } DerivedTy &operator=(const DerivedTy &Other) { Ptr = Other.Ptr; return static_cast(*this); } bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; } DerivedTy &operator++() { // Preincrement ++Ptr; AdvancePastEmptyBuckets(); return static_cast(*this); } DerivedTy operator++(int) { // Post-increment DerivedTy Tmp(Ptr); ++*this; return Tmp; } private: void AdvancePastEmptyBuckets() { while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) ++Ptr; } }; template class StringMapConstIterator : public StringMapIterBase, const StringMapEntry> { using base = StringMapIterBase, const StringMapEntry>; public: StringMapConstIterator() = default; explicit StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) : base(Bucket, NoAdvance) {} const StringMapEntry &operator*() const { return *static_cast *>(*this->Ptr); } }; template class StringMapIterator : public StringMapIterBase, StringMapEntry> { using base = StringMapIterBase, StringMapEntry>; public: StringMapIterator() = default; explicit StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance = false) : base(Bucket, NoAdvance) {} StringMapEntry &operator*() const { return *static_cast *>(*this->Ptr); } operator StringMapConstIterator() const { return StringMapConstIterator(this->Ptr, true); } }; template class StringMapKeyIterator : public iterator_adaptor_base, StringMapConstIterator, std::forward_iterator_tag, StringRef> { using base = iterator_adaptor_base, StringMapConstIterator, std::forward_iterator_tag, StringRef>; public: StringMapKeyIterator() = default; explicit StringMapKeyIterator(StringMapConstIterator Iter) : base(std::move(Iter)) {} StringRef &operator*() { Key = this->wrapped()->getKey(); return Key; } private: StringRef Key; }; } // end namespace llvm #endif // LLVM_ADT_STRINGMAP_H