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