1//===-- UniqueCStringMap.h --------------------------------------*- 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#ifndef LLDB_CORE_UNIQUECSTRINGMAP_H
10#define LLDB_CORE_UNIQUECSTRINGMAP_H
11
12#include <algorithm>
13#include <vector>
14
15#include "lldb/Utility/ConstString.h"
16#include "lldb/Utility/RegularExpression.h"
17
18namespace lldb_private {
19
20// Templatized uniqued string map.
21//
22// This map is useful for mapping unique C string names to values of type T.
23// Each "const char *" name added must be unique for a given
24// C string value. ConstString::GetCString() can provide such strings.
25// Any other string table that has guaranteed unique values can also be used.
26template <typename T> class UniqueCStringMap {
27public:
28 struct Entry {
29 Entry(ConstString cstr, const T &v) : cstring(cstr), value(v) {}
30
31 ConstString cstring;
32 T value;
33 };
34
35 typedef std::vector<Entry> collection;
36 typedef typename collection::iterator iterator;
37 typedef typename collection::const_iterator const_iterator;
38
39 // Call this function multiple times to add a bunch of entries to this map,
40 // then later call UniqueCStringMap<T>::Sort() before doing any searches by
41 // name.
42 void Append(ConstString unique_cstr, const T &value) {
43 m_map.push_back(typename UniqueCStringMap<T>::Entry(unique_cstr, value));
44 }
45
46 void Append(const Entry &e) { m_map.push_back(e); }
47
48 void Clear() { m_map.clear(); }
49
50 // Get an entries by index in a variety of forms.
51 //
52 // The caller is responsible for ensuring that the collection does not change
53 // during while using the returned values.
54 bool GetValueAtIndex(uint32_t idx, T &value) const {
55 if (idx < m_map.size()) {
56 value = m_map[idx].value;
57 return true;
58 }
59 return false;
60 }
61
62 ConstString GetCStringAtIndexUnchecked(uint32_t idx) const {
63 return m_map[idx].cstring;
64 }
65
66 // Use this function if you have simple types in your map that you can easily
67 // copy when accessing values by index.
68 T GetValueAtIndexUnchecked(uint32_t idx) const { return m_map[idx].value; }
69
70 // Use this function if you have complex types in your map that you don't
71 // want to copy when accessing values by index.
72 const T &GetValueRefAtIndexUnchecked(uint32_t idx) const {
73 return m_map[idx].value;
74 }
75
76 ConstString GetCStringAtIndex(uint32_t idx) const {
77 return ((idx < m_map.size()) ? m_map[idx].cstring : ConstString());
78 }
79
80 // Find the value for the unique string in the map.
81 //
82 // Return the value for \a unique_cstr if one is found, return \a fail_value
83 // otherwise. This method works well for simple type
84 // T values and only if there is a sensible failure value that can
85 // be returned and that won't match any existing values.
86 T Find(ConstString unique_cstr, T fail_value) const {
87 auto pos = llvm::lower_bound(m_map, unique_cstr, Compare());
88 if (pos != m_map.end() && pos->cstring == unique_cstr)
89 return pos->value;
90 return fail_value;
91 }
92
93 // Get a pointer to the first entry that matches "name". nullptr will be
94 // returned if there is no entry that matches "name".
95 //
96 // The caller is responsible for ensuring that the collection does not change
97 // during while using the returned pointer.
98 const Entry *FindFirstValueForName(ConstString unique_cstr) const {
99 auto pos = llvm::lower_bound(m_map, unique_cstr, Compare());
100 if (pos != m_map.end() && pos->cstring == unique_cstr)
101 return &(*pos);
102 return nullptr;
103 }
104
105 // Get a pointer to the next entry that matches "name" from a previously
106 // returned Entry pointer. nullptr will be returned if there is no subsequent
107 // entry that matches "name".
108 //
109 // The caller is responsible for ensuring that the collection does not change
110 // during while using the returned pointer.
111 const Entry *FindNextValueForName(const Entry *entry_ptr) const {
112 if (!m_map.empty()) {
113 const Entry *first_entry = &m_map[0];
114 const Entry *after_last_entry = first_entry + m_map.size();
115 const Entry *next_entry = entry_ptr + 1;
116 if (first_entry <= next_entry && next_entry < after_last_entry) {
117 if (next_entry->cstring == entry_ptr->cstring)
118 return next_entry;
119 }
120 }
121 return nullptr;
122 }
123
124 size_t GetValues(ConstString unique_cstr, std::vector<T> &values) const {
125 const size_t start_size = values.size();
126
127 for (const Entry &entry : llvm::make_range(std::equal_range(
128 m_map.begin(), m_map.end(), unique_cstr, Compare())))
129 values.push_back(entry.value);
130
131 return values.size() - start_size;
132 }
133
134 size_t GetValues(const RegularExpression &regex,
135 std::vector<T> &values) const {
136 const size_t start_size = values.size();
137
138 const_iterator pos, end = m_map.end();
139 for (pos = m_map.begin(); pos != end; ++pos) {
140 if (regex.Execute(string: pos->cstring.GetCString()))
141 values.push_back(pos->value);
142 }
143
144 return values.size() - start_size;
145 }
146
147 // Get the total number of entries in this map.
148 size_t GetSize() const { return m_map.size(); }
149
150 // Returns true if this map is empty.
151 bool IsEmpty() const { return m_map.empty(); }
152
153 // Reserve memory for at least "n" entries in the map. This is useful to call
154 // when you know you will be adding a lot of entries using
155 // UniqueCStringMap::Append() (which should be followed by a call to
156 // UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert().
157 void Reserve(size_t n) { m_map.reserve(n); }
158
159 // Sort the unsorted contents in this map. A typical code flow would be:
160 // size_t approximate_num_entries = ....
161 // UniqueCStringMap<uint32_t> my_map;
162 // my_map.Reserve (approximate_num_entries);
163 // for (...)
164 // {
165 // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...)));
166 // }
167 // my_map.Sort();
168 void Sort() {
169 Sort([](const T &, const T &) { return false; });
170 }
171
172 /// Sort contents of this map using the provided comparator to break ties for
173 /// entries with the same string value.
174 template <typename TCompare> void Sort(TCompare tc) {
175 Compare c;
176 llvm::sort(m_map, [&](const Entry &lhs, const Entry &rhs) -> bool {
177 int result = c.ThreeWay(lhs.cstring, rhs.cstring);
178 if (result == 0)
179 return tc(lhs.value, rhs.value);
180 return result < 0;
181 });
182 }
183
184 // Since we are using a vector to contain our items it will always double its
185 // memory consumption as things are added to the vector, so if you intend to
186 // keep a UniqueCStringMap around and have a lot of entries in the map, you
187 // will want to call this function to create a new vector and copy _only_ the
188 // exact size needed as part of the finalization of the string map.
189 void SizeToFit() {
190 if (m_map.size() < m_map.capacity()) {
191 collection temp(m_map.begin(), m_map.end());
192 m_map.swap(temp);
193 }
194 }
195
196 iterator begin() { return m_map.begin(); }
197 iterator end() { return m_map.end(); }
198 const_iterator begin() const { return m_map.begin(); }
199 const_iterator end() const { return m_map.end(); }
200
201 // Range-based for loop for all entries of the specified ConstString name.
202 llvm::iterator_range<const_iterator>
203 equal_range(ConstString unique_cstr) const {
204 return llvm::make_range(
205 std::equal_range(m_map.begin(), m_map.end(), unique_cstr, Compare()));
206 };
207
208protected:
209 struct Compare {
210 bool operator()(const Entry &lhs, const Entry &rhs) {
211 return operator()(lhs.cstring, rhs.cstring);
212 }
213
214 bool operator()(const Entry &lhs, ConstString rhs) {
215 return operator()(lhs.cstring, rhs);
216 }
217
218 bool operator()(ConstString lhs, const Entry &rhs) {
219 return operator()(lhs, rhs.cstring);
220 }
221
222 bool operator()(ConstString lhs, ConstString rhs) {
223 return ThreeWay(lhs, rhs) < 0;
224 }
225
226 // This is only for uniqueness, not lexicographical ordering, so we can
227 // just compare pointers. *However*, comparing pointers from different
228 // allocations is UB, so we need compare their integral values instead.
229 int ThreeWay(ConstString lhs, ConstString rhs) {
230 auto lhsint = uintptr_t(lhs.GetCString());
231 auto rhsint = uintptr_t(rhs.GetCString());
232 if (lhsint < rhsint)
233 return -1;
234 if (lhsint > rhsint)
235 return 1;
236 return 0;
237 }
238 };
239
240 collection m_map;
241};
242
243} // namespace lldb_private
244
245#endif // LLDB_CORE_UNIQUECSTRINGMAP_H
246

source code of lldb/include/lldb/Core/UniqueCStringMap.h