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 LLDB_CORE_UNIQUECSTRINGMAP_H
10 #define LLDB_CORE_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(ConstString cstr, const T &v) : cstring(cstr), value(v) {}
30 
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 
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 
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(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() { llvm::sort(m_map.begin(), m_map.end(), Compare()); }
169 
170  // Since we are using a vector to contain our items it will always double its
171  // memory consumption as things are added to the vector, so if you intend to
172  // keep a UniqueCStringMap around and have a lot of entries in the map, you
173  // will want to call this function to create a new vector and copy _only_ the
174  // exact size needed as part of the finalization of the string map.
175  void SizeToFit() {
176  if (m_map.size() < m_map.capacity()) {
177  collection temp(m_map.begin(), m_map.end());
178  m_map.swap(temp);
179  }
180  }
181 
182  iterator begin() { return m_map.begin(); }
183  iterator end() { return m_map.end(); }
184  const_iterator begin() const { return m_map.begin(); }
185  const_iterator end() const { return m_map.end(); }
186 
187  // Range-based for loop for all entries of the specified ConstString name.
188  llvm::iterator_range<const_iterator>
189  equal_range(ConstString unique_cstr) const {
190  return llvm::make_range(
191  std::equal_range(m_map.begin(), m_map.end(), unique_cstr, Compare()));
192  };
193 
194 protected:
195  struct Compare {
196  bool operator()(const Entry &lhs, const Entry &rhs) {
197  return operator()(lhs.cstring, rhs.cstring);
198  }
199 
200  bool operator()(const Entry &lhs, ConstString rhs) {
201  return operator()(lhs.cstring, rhs);
202  }
203 
204  bool operator()(ConstString lhs, const Entry &rhs) {
205  return operator()(lhs, rhs.cstring);
206  }
207 
208  // This is only for uniqueness, not lexicographical ordering, so we can
209  // just compare pointers. *However*, comparing pointers from different
210  // allocations is UB, so we need compare their integral values instead.
212  return uintptr_t(lhs.GetCString()) < uintptr_t(rhs.GetCString());
213  }
214  };
216 };
217 
218 } // namespace lldb_private
219 
220 #endif // LLDB_CORE_UNIQUECSTRINGMAP_H
RegularExpression.h
lldb_private::UniqueCStringMap::Entry::cstring
ConstString cstring
Definition: UniqueCStringMap.h:31
lldb_private::UniqueCStringMap::m_map
collection m_map
Definition: UniqueCStringMap.h:215
lldb_private::UniqueCStringMap::Sort
void Sort()
Definition: UniqueCStringMap.h:168
lldb_private::RegularExpression
Definition: RegularExpression.h:18
lldb_private::UniqueCStringMap::Compare::operator()
bool operator()(const Entry &lhs, const Entry &rhs)
Definition: UniqueCStringMap.h:196
lldb_private::UniqueCStringMap::Compare::operator()
bool operator()(const Entry &lhs, ConstString rhs)
Definition: UniqueCStringMap.h:200
lldb_private::UniqueCStringMap::Compare::operator()
bool operator()(ConstString lhs, const Entry &rhs)
Definition: UniqueCStringMap.h:204
lldb_private::UniqueCStringMap::Append
void Append(const Entry &e)
Definition: UniqueCStringMap.h:46
lldb_private::UniqueCStringMap::Entry::Entry
Entry(ConstString cstr, const T &v)
Definition: UniqueCStringMap.h:29
lldb_private::UniqueCStringMap::equal_range
llvm::iterator_range< const_iterator > equal_range(ConstString unique_cstr) const
Definition: UniqueCStringMap.h:189
lldb_private::UniqueCStringMap::Compare
Definition: UniqueCStringMap.h:195
lldb_private::UniqueCStringMap::Find
T Find(ConstString unique_cstr, T fail_value) const
Definition: UniqueCStringMap.h:86
lldb_private::UniqueCStringMap::SizeToFit
void SizeToFit()
Definition: UniqueCStringMap.h:175
lldb_private::UniqueCStringMap::end
iterator end()
Definition: UniqueCStringMap.h:183
lldb_private::UniqueCStringMap::IsEmpty
bool IsEmpty() const
Definition: UniqueCStringMap.h:151
lldb_private::UniqueCStringMap::GetValueAtIndexUnchecked
T GetValueAtIndexUnchecked(uint32_t idx) const
Definition: UniqueCStringMap.h:68
lldb_private::UniqueCStringMap::GetSize
size_t GetSize() const
Definition: UniqueCStringMap.h:148
lldb_private::UniqueCStringMap::Entry
Definition: UniqueCStringMap.h:28
Compare
static bool Compare(BreakpointLocationSP lhs, lldb::break_id_t val)
Definition: BreakpointLocationList.cpp:64
lldb_private::UniqueCStringMap::FindFirstValueForName
const Entry * FindFirstValueForName(ConstString unique_cstr) const
Definition: UniqueCStringMap.h:98
lldb_private::UniqueCStringMap::const_iterator
collection::const_iterator const_iterator
Definition: UniqueCStringMap.h:37
lldb_private::UniqueCStringMap::end
const_iterator end() const
Definition: UniqueCStringMap.h:185
lldb_private::ConstString
Definition: ConstString.h:40
lldb_private::UniqueCStringMap::Compare::operator()
bool operator()(ConstString lhs, ConstString rhs)
Definition: UniqueCStringMap.h:211
lldb_private::UniqueCStringMap::iterator
collection::iterator iterator
Definition: UniqueCStringMap.h:36
lldb_private::UniqueCStringMap::begin
const_iterator begin() const
Definition: UniqueCStringMap.h:184
lldb_private::UniqueCStringMap
Definition: UniqueCStringMap.h:26
lldb_private::UniqueCStringMap::Reserve
void Reserve(size_t n)
Definition: UniqueCStringMap.h:157
lldb_private::UniqueCStringMap::GetValues
size_t GetValues(const RegularExpression &regex, std::vector< T > &values) const
Definition: UniqueCStringMap.h:134
lldb_private::UniqueCStringMap::GetCStringAtIndex
ConstString GetCStringAtIndex(uint32_t idx) const
Definition: UniqueCStringMap.h:76
lldb_private::UniqueCStringMap::Append
void Append(ConstString unique_cstr, const T &value)
Definition: UniqueCStringMap.h:42
uint32_t
lldb_private::FormatEntity::Entry
Definition: FormatEntity.h:40
lldb_private::UniqueCStringMap::GetValueRefAtIndexUnchecked
const T & GetValueRefAtIndexUnchecked(uint32_t idx) const
Definition: UniqueCStringMap.h:72
lldb_private::ConstString::GetCString
const char * GetCString() const
Get the string value as a C string.
Definition: ConstString.h:216
lldb_private::UniqueCStringMap::Entry::value
T value
Definition: UniqueCStringMap.h:32
lldb_private::UniqueCStringMap::GetValues
size_t GetValues(ConstString unique_cstr, std::vector< T > &values) const
Definition: UniqueCStringMap.h:124
lldb_private::UniqueCStringMap::GetValueAtIndex
bool GetValueAtIndex(uint32_t idx, T &value) const
Definition: UniqueCStringMap.h:54
lldb_private
A class that represents a running process on the host machine.
Definition: SBCommandInterpreterRunOptions.h:16
lldb_private::UniqueCStringMap::collection
std::vector< Entry > collection
Definition: UniqueCStringMap.h:35
lldb_private::RegularExpression::Execute
bool Execute(llvm::StringRef string, llvm::SmallVectorImpl< llvm::StringRef > *matches=nullptr) const
Execute a regular expression match using the compiled regular expression that is already in this obje...
Definition: RegularExpression.cpp:23
ConstString.h
lldb_private::UniqueCStringMap::begin
iterator begin()
Definition: UniqueCStringMap.h:182
lldb_private::UniqueCStringMap::FindNextValueForName
const Entry * FindNextValueForName(const Entry *entry_ptr) const
Definition: UniqueCStringMap.h:111
lldb_private::UniqueCStringMap::Clear
void Clear()
Definition: UniqueCStringMap.h:48
lldb_private::UniqueCStringMap::GetCStringAtIndexUnchecked
ConstString GetCStringAtIndexUnchecked(uint32_t idx) const
Definition: UniqueCStringMap.h:62