1 //===-- UniqueCStringMap.h --------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef liblldb_UniqueCStringMap_h_
11 #define liblldb_UniqueCStringMap_h_
18 // Other libraries and framework includes
20 #include "lldb/Utility/RegularExpression.h"
22 #include "llvm/ADT/StringRef.h"
24 namespace lldb_private {
26 //----------------------------------------------------------------------
27 // Templatized uniqued string map.
29 // This map is useful for mapping unique C string names to values of
30 // type T. Each "const char *" name added must be unique for a given
31 // C string value. ConstString::GetCString() can provide such strings.
32 // Any other string table that has guaranteed unique values can also
34 //----------------------------------------------------------------------
35 template <typename T> class UniqueCStringMap {
40 Entry(llvm::StringRef cstr) : cstring(cstr), value() {}
42 Entry(llvm::StringRef cstr, const T &v) : cstring(cstr), value(v) {}
44 bool operator<(const Entry &rhs) const { return cstring < rhs.cstring; }
46 llvm::StringRef cstring;
50 //------------------------------------------------------------------
51 // Call this function multiple times to add a bunch of entries to
52 // this map, then later call UniqueCStringMap<T>::Sort() before doing
53 // any searches by name.
54 //------------------------------------------------------------------
55 void Append(llvm::StringRef unique_cstr, const T &value) {
56 m_map.push_back(typename UniqueCStringMap<T>::Entry(unique_cstr, value));
59 void Append(const Entry &e) { m_map.push_back(e); }
61 void Clear() { m_map.clear(); }
63 //------------------------------------------------------------------
64 // Call this function to always keep the map sorted when putting
65 // entries into the map.
66 //------------------------------------------------------------------
67 void Insert(llvm::StringRef unique_cstr, const T &value) {
68 typename UniqueCStringMap<T>::Entry e(unique_cstr, value);
69 m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e);
72 void Insert(const Entry &e) {
73 m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e);
76 //------------------------------------------------------------------
77 // Get an entries by index in a variety of forms.
79 // The caller is responsible for ensuring that the collection does
80 // not change during while using the returned values.
81 //------------------------------------------------------------------
82 bool GetValueAtIndex(uint32_t idx, T &value) const {
83 if (idx < m_map.size()) {
84 value = m_map[idx].value;
90 llvm::StringRef GetCStringAtIndexUnchecked(uint32_t idx) const {
91 return m_map[idx].cstring;
94 // Use this function if you have simple types in your map that you
95 // can easily copy when accessing values by index.
96 T GetValueAtIndexUnchecked(uint32_t idx) const { return m_map[idx].value; }
98 // Use this function if you have complex types in your map that you
99 // don't want to copy when accessing values by index.
100 const T &GetValueRefAtIndexUnchecked(uint32_t idx) const {
101 return m_map[idx].value;
104 llvm::StringRef GetCStringAtIndex(uint32_t idx) const {
105 return ((idx < m_map.size()) ? m_map[idx].cstring : llvm::StringRef());
108 //------------------------------------------------------------------
109 // Find the value for the unique string in the map.
111 // Return the value for \a unique_cstr if one is found, return
112 // \a fail_value otherwise. This method works well for simple type
113 // T values and only if there is a sensible failure value that can
114 // be returned and that won't match any existing values.
115 //------------------------------------------------------------------
116 T Find(llvm::StringRef unique_cstr, T fail_value) const {
117 Entry search_entry(unique_cstr);
118 const_iterator end = m_map.end();
119 const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry);
121 if (pos->cstring == unique_cstr)
127 //------------------------------------------------------------------
128 // Get a pointer to the first entry that matches "name". nullptr will
129 // be returned if there is no entry that matches "name".
131 // The caller is responsible for ensuring that the collection does
132 // not change during while using the returned pointer.
133 //------------------------------------------------------------------
134 const Entry *FindFirstValueForName(llvm::StringRef unique_cstr) const {
135 Entry search_entry(unique_cstr);
136 const_iterator end = m_map.end();
137 const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry);
139 llvm::StringRef pos_cstr = pos->cstring;
140 if (pos_cstr == unique_cstr)
146 //------------------------------------------------------------------
147 // Get a pointer to the next entry that matches "name" from a
148 // previously returned Entry pointer. nullptr will be returned if there
149 // is no subsequent entry that matches "name".
151 // The caller is responsible for ensuring that the collection does
152 // not change during while using the returned pointer.
153 //------------------------------------------------------------------
154 const Entry *FindNextValueForName(const Entry *entry_ptr) const {
155 if (!m_map.empty()) {
156 const Entry *first_entry = &m_map[0];
157 const Entry *after_last_entry = first_entry + m_map.size();
158 const Entry *next_entry = entry_ptr + 1;
159 if (first_entry <= next_entry && next_entry < after_last_entry) {
160 if (next_entry->cstring == entry_ptr->cstring)
167 size_t GetValues(llvm::StringRef unique_cstr, std::vector<T> &values) const {
168 const size_t start_size = values.size();
170 Entry search_entry(unique_cstr);
171 const_iterator pos, end = m_map.end();
172 for (pos = std::lower_bound(m_map.begin(), end, search_entry); pos != end;
174 if (pos->cstring == unique_cstr)
175 values.push_back(pos->value);
180 return values.size() - start_size;
183 size_t GetValues(const RegularExpression ®ex,
184 std::vector<T> &values) const {
185 const size_t start_size = values.size();
187 const_iterator pos, end = m_map.end();
188 for (pos = m_map.begin(); pos != end; ++pos) {
189 if (regex.Execute(pos->cstring))
190 values.push_back(pos->value);
193 return values.size() - start_size;
196 //------------------------------------------------------------------
197 // Get the total number of entries in this map.
198 //------------------------------------------------------------------
199 size_t GetSize() const { return m_map.size(); }
201 //------------------------------------------------------------------
202 // Returns true if this map is empty.
203 //------------------------------------------------------------------
204 bool IsEmpty() const { return m_map.empty(); }
206 //------------------------------------------------------------------
207 // Reserve memory for at least "n" entries in the map. This is
208 // useful to call when you know you will be adding a lot of entries
209 // using UniqueCStringMap::Append() (which should be followed by a
210 // call to UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert().
211 //------------------------------------------------------------------
212 void Reserve(size_t n) { m_map.reserve(n); }
214 //------------------------------------------------------------------
215 // Sort the unsorted contents in this map. A typical code flow would
217 // size_t approximate_num_entries = ....
218 // UniqueCStringMap<uint32_t> my_map;
219 // my_map.Reserve (approximate_num_entries);
222 // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...)));
225 //------------------------------------------------------------------
226 void Sort() { std::sort(m_map.begin(), m_map.end()); }
228 //------------------------------------------------------------------
229 // Since we are using a vector to contain our items it will always
230 // double its memory consumption as things are added to the vector,
231 // so if you intend to keep a UniqueCStringMap around and have
232 // a lot of entries in the map, you will want to call this function
233 // to create a new vector and copy _only_ the exact size needed as
234 // part of the finalization of the string map.
235 //------------------------------------------------------------------
237 if (m_map.size() < m_map.capacity()) {
238 collection temp(m_map.begin(), m_map.end());
243 size_t Erase(llvm::StringRef unique_cstr) {
244 size_t num_removed = 0;
245 Entry search_entry(unique_cstr);
246 iterator end = m_map.end();
247 iterator begin = m_map.begin();
248 iterator lower_pos = std::lower_bound(begin, end, search_entry);
249 if (lower_pos != end) {
250 if (lower_pos->cstring == unique_cstr) {
251 iterator upper_pos = std::upper_bound(lower_pos, end, search_entry);
252 if (lower_pos == upper_pos) {
253 m_map.erase(lower_pos);
256 num_removed = std::distance(lower_pos, upper_pos);
257 m_map.erase(lower_pos, upper_pos);
265 typedef std::vector<Entry> collection;
266 typedef typename collection::iterator iterator;
267 typedef typename collection::const_iterator const_iterator;
271 } // namespace lldb_private
273 #endif // liblldb_UniqueCStringMap_h_