1 //===- StringMapEntry.h - String Hash table map interface -------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file defines the StringMapEntry class - it is intended to be a low 11 /// dependency implementation detail of StringMap that is more suitable for 12 /// inclusion in public headers than StringMap.h itself is. 13 /// 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_ADT_STRINGMAPENTRY_H 17 #define LLVM_ADT_STRINGMAPENTRY_H 18 19 #include "llvm/ADT/StringRef.h" 20 #include <optional> 21 22 namespace llvm { 23 24 /// StringMapEntryBase - Shared base class of StringMapEntry instances. 25 class StringMapEntryBase { 26 size_t keyLength; 27 28 public: 29 explicit StringMapEntryBase(size_t keyLength) : keyLength(keyLength) {} 30 31 size_t getKeyLength() const { return keyLength; } 32 33 protected: 34 /// Helper to tail-allocate \p Key. It'd be nice to generalize this so it 35 /// could be reused elsewhere, maybe even taking an llvm::function_ref to 36 /// type-erase the allocator and put it in a source file. 37 template <typename AllocatorTy> 38 static void *allocateWithKey(size_t EntrySize, size_t EntryAlign, 39 StringRef Key, AllocatorTy &Allocator); 40 }; 41 42 // Define out-of-line to dissuade inlining. 43 template <typename AllocatorTy> 44 void *StringMapEntryBase::allocateWithKey(size_t EntrySize, size_t EntryAlign, 45 StringRef Key, 46 AllocatorTy &Allocator) { 47 size_t KeyLength = Key.size(); 48 49 // Allocate a new item with space for the string at the end and a null 50 // terminator. 51 size_t AllocSize = EntrySize + KeyLength + 1; 52 void *Allocation = Allocator.Allocate(AllocSize, EntryAlign); 53 assert(Allocation && "Unhandled out-of-memory"); 54 55 // Copy the string information. 56 char *Buffer = reinterpret_cast<char *>(Allocation) + EntrySize; 57 if (KeyLength > 0) 58 ::memcpy(Buffer, Key.data(), KeyLength); 59 Buffer[KeyLength] = 0; // Null terminate for convenience of clients. 60 return Allocation; 61 } 62 63 /// StringMapEntryStorage - Holds the value in a StringMapEntry. 64 /// 65 /// Factored out into a separate base class to make it easier to specialize. 66 /// This is primarily intended to support StringSet, which doesn't need a value 67 /// stored at all. 68 template <typename ValueTy> 69 class StringMapEntryStorage : public StringMapEntryBase { 70 public: 71 ValueTy second; 72 73 explicit StringMapEntryStorage(size_t keyLength) 74 : StringMapEntryBase(keyLength), second() {} 75 template <typename... InitTy> 76 StringMapEntryStorage(size_t keyLength, InitTy &&...initVals) 77 : StringMapEntryBase(keyLength), 78 second(std::forward<InitTy>(initVals)...) {} 79 StringMapEntryStorage(StringMapEntryStorage &e) = delete; 80 81 const ValueTy &getValue() const { return second; } 82 ValueTy &getValue() { return second; } 83 84 void setValue(const ValueTy &V) { second = V; } 85 }; 86 87 template <> 88 class StringMapEntryStorage<std::nullopt_t> : public StringMapEntryBase { 89 public: 90 explicit StringMapEntryStorage(size_t keyLength, 91 std::nullopt_t = std::nullopt) 92 : StringMapEntryBase(keyLength) {} 93 StringMapEntryStorage(StringMapEntryStorage &entry) = delete; 94 95 std::nullopt_t getValue() const { return std::nullopt; } 96 }; 97 98 /// StringMapEntry - This is used to represent one value that is inserted into 99 /// a StringMap. It contains the Value itself and the key: the string length 100 /// and data. 101 template <typename ValueTy> 102 class StringMapEntry final : public StringMapEntryStorage<ValueTy> { 103 public: 104 using StringMapEntryStorage<ValueTy>::StringMapEntryStorage; 105 106 using ValueType = ValueTy; 107 108 StringRef getKey() const { 109 return StringRef(getKeyData(), this->getKeyLength()); 110 } 111 112 /// getKeyData - Return the start of the string data that is the key for this 113 /// value. The string data is always stored immediately after the 114 /// StringMapEntry object. 115 const char *getKeyData() const { 116 return reinterpret_cast<const char *>(this + 1); 117 } 118 119 StringRef first() const { 120 return StringRef(getKeyData(), this->getKeyLength()); 121 } 122 123 /// Create a StringMapEntry for the specified key construct the value using 124 /// \p InitiVals. 125 template <typename AllocatorTy, typename... InitTy> 126 static StringMapEntry *create(StringRef key, AllocatorTy &allocator, 127 InitTy &&...initVals) { 128 return new (StringMapEntryBase::allocateWithKey( 129 sizeof(StringMapEntry), alignof(StringMapEntry), key, allocator)) 130 StringMapEntry(key.size(), std::forward<InitTy>(initVals)...); 131 } 132 133 /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 134 /// into a StringMapEntry, return the StringMapEntry itself. 135 static StringMapEntry &GetStringMapEntryFromKeyData(const char *keyData) { 136 char *ptr = const_cast<char *>(keyData) - sizeof(StringMapEntry<ValueTy>); 137 return *reinterpret_cast<StringMapEntry *>(ptr); 138 } 139 140 /// Destroy - Destroy this StringMapEntry, releasing memory back to the 141 /// specified allocator. 142 template <typename AllocatorTy> void Destroy(AllocatorTy &allocator) { 143 // Free memory referenced by the item. 144 size_t AllocSize = sizeof(StringMapEntry) + this->getKeyLength() + 1; 145 this->~StringMapEntry(); 146 allocator.Deallocate(static_cast<void *>(this), AllocSize, 147 alignof(StringMapEntry)); 148 } 149 }; 150 151 // Allow structured bindings on StringMapEntry. 152 template <std::size_t Index, typename ValueTy> 153 decltype(auto) get(const StringMapEntry<ValueTy> &E) { 154 static_assert(Index < 2); 155 if constexpr (Index == 0) 156 return E.first(); 157 else 158 return E.second; 159 } 160 161 } // end namespace llvm 162 163 namespace std { 164 template <typename ValueTy> 165 struct tuple_size<llvm::StringMapEntry<ValueTy>> 166 : std::integral_constant<std::size_t, 2> {}; 167 168 template <std::size_t I, typename ValueTy> 169 struct tuple_element<I, llvm::StringMapEntry<ValueTy>> 170 : std::conditional<I == 0, llvm::StringRef, ValueTy> {}; 171 } // namespace std 172 173 #endif // LLVM_ADT_STRINGMAPENTRY_H 174