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