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:
StringMapEntryBase(size_t keyLength)29 explicit StringMapEntryBase(size_t keyLength) : keyLength(keyLength) {}
30
getKeyLength()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>
allocateWithKey(size_t EntrySize,size_t EntryAlign,StringRef Key,AllocatorTy & Allocator)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
StringMapEntryStorage(size_t keyLength)73 explicit StringMapEntryStorage(size_t keyLength)
74 : StringMapEntryBase(keyLength), second() {}
75 template <typename... InitTy>
StringMapEntryStorage(size_t keyLength,InitTy &&...initVals)76 StringMapEntryStorage(size_t keyLength, InitTy &&...initVals)
77 : StringMapEntryBase(keyLength),
78 second(std::forward<InitTy>(initVals)...) {}
79 StringMapEntryStorage(StringMapEntryStorage &e) = delete;
80
getValue()81 const ValueTy &getValue() const { return second; }
getValue()82 ValueTy &getValue() { return second; }
83
setValue(const ValueTy & V)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)
StringMapEntryBase(keyLength)92 : StringMapEntryBase(keyLength) {}
93 StringMapEntryStorage(StringMapEntryStorage &entry) = delete;
94
getValue()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
getKey()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.
getKeyData()115 const char *getKeyData() const {
116 return reinterpret_cast<const char *>(this + 1);
117 }
118
first()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>
create(StringRef key,AllocatorTy & allocator,InitTy &&...initVals)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.
GetStringMapEntryFromKeyData(const char * keyData)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.
Destroy(AllocatorTy & 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>
decltype(auto)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>
decltype(auto)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