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 <utility> 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 { return getKey(); } 120 121 /// Create a StringMapEntry for the specified key construct the value using 122 /// \p InitiVals. 123 template <typename AllocatorTy, typename... InitTy> 124 static StringMapEntry *create(StringRef key, AllocatorTy &allocator, 125 InitTy &&...initVals) { 126 return new (StringMapEntryBase::allocateWithKey( 127 sizeof(StringMapEntry), alignof(StringMapEntry), key, allocator)) 128 StringMapEntry(key.size(), std::forward<InitTy>(initVals)...); 129 } 130 131 /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded 132 /// into a StringMapEntry, return the StringMapEntry itself. 133 static StringMapEntry &GetStringMapEntryFromKeyData(const char *keyData) { 134 char *ptr = const_cast<char *>(keyData) - sizeof(StringMapEntry<ValueTy>); 135 return *reinterpret_cast<StringMapEntry *>(ptr); 136 } 137 138 /// Destroy - Destroy this StringMapEntry, releasing memory back to the 139 /// specified allocator. 140 template <typename AllocatorTy> void Destroy(AllocatorTy &allocator) { 141 // Free memory referenced by the item. 142 size_t AllocSize = sizeof(StringMapEntry) + this->getKeyLength() + 1; 143 this->~StringMapEntry(); 144 allocator.Deallocate(static_cast<void *>(this), AllocSize, 145 alignof(StringMapEntry)); 146 } 147 }; 148 149 // Allow structured bindings on StringMapEntry. 150 151 template <std::size_t Index, typename ValueTy> 152 decltype(auto) get(StringMapEntry<ValueTy> &E) { 153 static_assert(Index < 2); 154 if constexpr (Index == 0) 155 return E.getKey(); 156 else 157 return E.getValue(); 158 } 159 160 template <std::size_t Index, typename ValueTy> 161 decltype(auto) get(const StringMapEntry<ValueTy> &E) { 162 static_assert(Index < 2); 163 if constexpr (Index == 0) 164 return E.getKey(); 165 else 166 return E.getValue(); 167 } 168 169 } // end namespace llvm 170 171 template <typename ValueTy> 172 struct std::tuple_size<llvm::StringMapEntry<ValueTy>> 173 : std::integral_constant<std::size_t, 2> {}; 174 175 template <std::size_t Index, typename ValueTy> 176 struct std::tuple_element<Index, llvm::StringMapEntry<ValueTy>> 177 : std::tuple_element<Index, std::pair<llvm::StringRef, ValueTy>> {}; 178 179 #endif // LLVM_ADT_STRINGMAPENTRY_H 180