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 | |
18 | namespace 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. |
26 | template <typename T> class UniqueCStringMap { |
27 | public: |
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 ®ex, |
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 | |
208 | protected: |
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 | |