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/Core/RegularExpression.h"
22 namespace lldb_private {
24 //----------------------------------------------------------------------
25 // Templatized uniqued string map.
27 // This map is useful for mapping unique C string names to values of
28 // type T. Each "const char *" name added must be unique for a given
29 // C string value. ConstString::GetCString() can provide such strings.
30 // Any other string table that has guaranteed unique values can also
32 //----------------------------------------------------------------------
33 template <typename T> class UniqueCStringMap {
38 Entry(llvm::StringRef cstr) : cstring(cstr), value() {}
40 Entry(llvm::StringRef cstr, const T &v) : cstring(cstr), value(v) {}
42 bool operator<(const Entry &rhs) const { return cstring < rhs.cstring; }
44 llvm::StringRef cstring;
48 //------------------------------------------------------------------
49 // Call this function multiple times to add a bunch of entries to
50 // this map, then later call UniqueCStringMap<T>::Sort() before doing
51 // any searches by name.
52 //------------------------------------------------------------------
53 void Append(llvm::StringRef unique_cstr, const T &value) {
54 m_map.push_back(typename UniqueCStringMap<T>::Entry(unique_cstr, value));
57 void Append(const Entry &e) { m_map.push_back(e); }
59 void Clear() { m_map.clear(); }
61 //------------------------------------------------------------------
62 // Call this function to always keep the map sorted when putting
63 // entries into the map.
64 //------------------------------------------------------------------
65 void Insert(llvm::StringRef unique_cstr, const T &value) {
66 typename UniqueCStringMap<T>::Entry e(unique_cstr, value);
67 m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e);
70 void Insert(const Entry &e) {
71 m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e);
74 //------------------------------------------------------------------
75 // Get an entries by index in a variety of forms.
77 // The caller is responsible for ensuring that the collection does
78 // not change during while using the returned values.
79 //------------------------------------------------------------------
80 bool GetValueAtIndex(uint32_t idx, T &value) const {
81 if (idx < m_map.size()) {
82 value = m_map[idx].value;
88 llvm::StringRef GetCStringAtIndexUnchecked(uint32_t idx) const {
89 return m_map[idx].cstring;
92 // Use this function if you have simple types in your map that you
93 // can easily copy when accessing values by index.
94 T GetValueAtIndexUnchecked(uint32_t idx) const { return m_map[idx].value; }
96 // Use this function if you have complex types in your map that you
97 // don't want to copy when accessing values by index.
98 const T &GetValueRefAtIndexUnchecked(uint32_t idx) const {
99 return m_map[idx].value;
102 llvm::StringRef GetCStringAtIndex(uint32_t idx) const {
103 return ((idx < m_map.size()) ? m_map[idx].cstring : llvm::StringRef());
106 //------------------------------------------------------------------
107 // Find the value for the unique string in the map.
109 // Return the value for \a unique_cstr if one is found, return
110 // \a fail_value otherwise. This method works well for simple type
111 // T values and only if there is a sensible failure value that can
112 // be returned and that won't match any existing values.
113 //------------------------------------------------------------------
114 T Find(llvm::StringRef unique_cstr, T fail_value) const {
115 Entry search_entry(unique_cstr);
116 const_iterator end = m_map.end();
117 const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry);
119 if (pos->cstring == unique_cstr)
125 //------------------------------------------------------------------
126 // Get a pointer to the first entry that matches "name". nullptr will
127 // be returned if there is no entry that matches "name".
129 // The caller is responsible for ensuring that the collection does
130 // not change during while using the returned pointer.
131 //------------------------------------------------------------------
132 const Entry *FindFirstValueForName(llvm::StringRef unique_cstr) const {
133 Entry search_entry(unique_cstr);
134 const_iterator end = m_map.end();
135 const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry);
137 llvm::StringRef pos_cstr = pos->cstring;
138 if (pos_cstr == unique_cstr)
144 //------------------------------------------------------------------
145 // Get a pointer to the next entry that matches "name" from a
146 // previously returned Entry pointer. nullptr will be returned if there
147 // is no subsequent entry that matches "name".
149 // The caller is responsible for ensuring that the collection does
150 // not change during while using the returned pointer.
151 //------------------------------------------------------------------
152 const Entry *FindNextValueForName(const Entry *entry_ptr) const {
153 if (!m_map.empty()) {
154 const Entry *first_entry = &m_map[0];
155 const Entry *after_last_entry = first_entry + m_map.size();
156 const Entry *next_entry = entry_ptr + 1;
157 if (first_entry <= next_entry && next_entry < after_last_entry) {
158 if (next_entry->cstring == entry_ptr->cstring)
165 size_t GetValues(llvm::StringRef unique_cstr, std::vector<T> &values) const {
166 const size_t start_size = values.size();
168 Entry search_entry(unique_cstr);
169 const_iterator pos, end = m_map.end();
170 for (pos = std::lower_bound(m_map.begin(), end, search_entry); pos != end;
172 if (pos->cstring == unique_cstr)
173 values.push_back(pos->value);
178 return values.size() - start_size;
181 size_t GetValues(const RegularExpression ®ex,
182 std::vector<T> &values) const {
183 const size_t start_size = values.size();
185 const_iterator pos, end = m_map.end();
186 for (pos = m_map.begin(); pos != end; ++pos) {
187 if (regex.Execute(pos->cstring))
188 values.push_back(pos->value);
191 return values.size() - start_size;
194 //------------------------------------------------------------------
195 // Get the total number of entries in this map.
196 //------------------------------------------------------------------
197 size_t GetSize() const { return m_map.size(); }
199 //------------------------------------------------------------------
200 // Returns true if this map is empty.
201 //------------------------------------------------------------------
202 bool IsEmpty() const { return m_map.empty(); }
204 //------------------------------------------------------------------
205 // Reserve memory for at least "n" entries in the map. This is
206 // useful to call when you know you will be adding a lot of entries
207 // using UniqueCStringMap::Append() (which should be followed by a
208 // call to UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert().
209 //------------------------------------------------------------------
210 void Reserve(size_t n) { m_map.reserve(n); }
212 //------------------------------------------------------------------
213 // Sort the unsorted contents in this map. A typical code flow would
215 // size_t approximate_num_entries = ....
216 // UniqueCStringMap<uint32_t> my_map;
217 // my_map.Reserve (approximate_num_entries);
220 // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...)));
223 //------------------------------------------------------------------
224 void Sort() { std::sort(m_map.begin(), m_map.end()); }
226 //------------------------------------------------------------------
227 // Since we are using a vector to contain our items it will always
228 // double its memory consumption as things are added to the vector,
229 // so if you intend to keep a UniqueCStringMap around and have
230 // a lot of entries in the map, you will want to call this function
231 // to create a new vector and copy _only_ the exact size needed as
232 // part of the finalization of the string map.
233 //------------------------------------------------------------------
235 if (m_map.size() < m_map.capacity()) {
236 collection temp(m_map.begin(), m_map.end());
241 size_t Erase(llvm::StringRef unique_cstr) {
242 size_t num_removed = 0;
243 Entry search_entry(unique_cstr);
244 iterator end = m_map.end();
245 iterator begin = m_map.begin();
246 iterator lower_pos = std::lower_bound(begin, end, search_entry);
247 if (lower_pos != end) {
248 if (lower_pos->cstring == unique_cstr) {
249 iterator upper_pos = std::upper_bound(lower_pos, end, search_entry);
250 if (lower_pos == upper_pos) {
251 m_map.erase(lower_pos);
254 num_removed = std::distance(lower_pos, upper_pos);
255 m_map.erase(lower_pos, upper_pos);
263 typedef std::vector<Entry> collection;
264 typedef typename collection::iterator iterator;
265 typedef typename collection::const_iterator const_iterator;
269 } // namespace lldb_private
271 #endif // liblldb_UniqueCStringMap_h_