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