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_
12 #if defined(__cplusplus)
18 #include "lldb/Core/RegularExpression.h"
20 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 //----------------------------------------------------------------------
34 class UniqueCStringMap
45 Entry (const char *cstr) :
51 Entry (const char *cstr, const T&v) :
58 operator < (const Entry& rhs) const
60 return cstring < rhs.cstring;
67 //------------------------------------------------------------------
68 // Call this function multiple times to add a bunch of entries to
69 // this map, then later call UniqueCStringMap<T>::Sort() before doing
70 // any searches by name.
71 //------------------------------------------------------------------
73 Append (const char *unique_cstr, const T& value)
75 m_map.push_back (typename UniqueCStringMap<T>::Entry(unique_cstr, value));
79 Append (const Entry &e)
90 //------------------------------------------------------------------
91 // Call this function to always keep the map sorted when putting
92 // entries into the map.
93 //------------------------------------------------------------------
95 Insert (const char *unique_cstr, const T& value)
97 typename UniqueCStringMap<T>::Entry e(unique_cstr, value);
98 m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e);
102 Insert (const Entry &e)
104 m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e);
107 //------------------------------------------------------------------
108 // Get an entries by index in a variety of forms.
110 // The caller is responsible for ensuring that the collection does
111 // not change during while using the returned values.
112 //------------------------------------------------------------------
114 GetValueAtIndex (uint32_t idx, T &value) const
116 if (idx < m_map.size())
118 value = m_map[idx].value;
125 GetCStringAtIndexUnchecked (uint32_t idx) const
127 return m_map[idx].cstring;
130 // Use this function if you have simple types in your map that you
131 // can easily copy when accessing values by index.
133 GetValueAtIndexUnchecked (uint32_t idx) const
135 return m_map[idx].value;
138 // Use this function if you have complex types in your map that you
139 // don't want to copy when accessing values by index.
141 GetValueRefAtIndexUnchecked (uint32_t idx) const
143 return m_map[idx].value;
147 GetCStringAtIndex (uint32_t idx) const
149 if (idx < m_map.size())
150 return m_map[idx].cstring;
154 //------------------------------------------------------------------
155 // Find the value for the unique string in the map.
157 // Return the value for \a unique_cstr if one is found, return
158 // \a fail_value otherwise. This method works well for simple type
159 // T values and only if there is a sensible failure value that can
160 // be returned and that won't match any existing values.
161 //------------------------------------------------------------------
163 Find (const char *unique_cstr, T fail_value) const
165 Entry search_entry (unique_cstr);
166 const_iterator end = m_map.end();
167 const_iterator pos = std::lower_bound (m_map.begin(), end, search_entry);
170 if (pos->cstring == unique_cstr)
175 //------------------------------------------------------------------
176 // Get a pointer to the first entry that matches "name". NULL will
177 // be returned if there is no entry that matches "name".
179 // The caller is responsible for ensuring that the collection does
180 // not change during while using the returned pointer.
181 //------------------------------------------------------------------
183 FindFirstValueForName (const char *unique_cstr) const
185 Entry search_entry (unique_cstr);
186 const_iterator end = m_map.end();
187 const_iterator pos = std::lower_bound (m_map.begin(), end, search_entry);
190 const char *pos_cstr = pos->cstring;
191 if (pos_cstr == unique_cstr)
197 //------------------------------------------------------------------
198 // Get a pointer to the next entry that matches "name" from a
199 // previously returned Entry pointer. NULL will be returned if there
200 // is no subsequent entry that matches "name".
202 // The caller is responsible for ensuring that the collection does
203 // not change during while using the returned pointer.
204 //------------------------------------------------------------------
206 FindNextValueForName (const Entry *entry_ptr) const
210 const Entry *first_entry = &m_map[0];
211 const Entry *after_last_entry = first_entry + m_map.size();
212 const Entry *next_entry = entry_ptr + 1;
213 if (first_entry <= next_entry && next_entry < after_last_entry)
215 if (next_entry->cstring == entry_ptr->cstring)
223 GetValues (const char *unique_cstr, std::vector<T> &values) const
225 const size_t start_size = values.size();
227 Entry search_entry (unique_cstr);
228 const_iterator pos, end = m_map.end();
229 for (pos = std::lower_bound (m_map.begin(), end, search_entry); pos != end; ++pos)
231 if (pos->cstring == unique_cstr)
232 values.push_back (pos->value);
237 return values.size() - start_size;
241 GetValues (const RegularExpression& regex, std::vector<T> &values) const
243 const size_t start_size = values.size();
245 const_iterator pos, end = m_map.end();
246 for (pos = m_map.begin(); pos != end; ++pos)
248 if (regex.Execute(pos->cstring))
249 values.push_back (pos->value);
252 return values.size() - start_size;
255 //------------------------------------------------------------------
256 // Get the total number of entries in this map.
257 //------------------------------------------------------------------
265 //------------------------------------------------------------------
266 // Returns true if this map is empty.
267 //------------------------------------------------------------------
271 return m_map.empty();
274 //------------------------------------------------------------------
275 // Reserve memory for at least "n" entries in the map. This is
276 // useful to call when you know you will be adding a lot of entries
277 // using UniqueCStringMap::Append() (which should be followed by a
278 // call to UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert().
279 //------------------------------------------------------------------
286 //------------------------------------------------------------------
287 // Sort the unsorted contents in this map. A typical code flow would
289 // size_t approximate_num_entries = ....
290 // UniqueCStringMap<uint32_t> my_map;
291 // my_map.Reserve (approximate_num_entries);
294 // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...)));
297 //------------------------------------------------------------------
301 std::sort (m_map.begin(), m_map.end());
304 //------------------------------------------------------------------
305 // Since we are using a vector to contain our items it will always
306 // double its memory consumption as things are added to the vector,
307 // so if you intend to keep a UniqueCStringMap around and have
308 // a lot of entries in the map, you will want to call this function
309 // to create a new vector and copy _only_ the exact size needed as
310 // part of the finalization of the string map.
311 //------------------------------------------------------------------
315 if (m_map.size() < m_map.capacity())
317 collection temp (m_map.begin(), m_map.end());
323 Erase (const char *unique_cstr)
325 size_t num_removed = 0;
326 Entry search_entry (unique_cstr);
327 iterator end = m_map.end();
328 iterator begin = m_map.begin();
329 iterator lower_pos = std::lower_bound (begin, end, search_entry);
330 if (lower_pos != end)
332 if (lower_pos->cstring == unique_cstr)
334 iterator upper_pos = std::upper_bound (lower_pos, end, search_entry);
335 if (lower_pos == upper_pos)
337 m_map.erase (lower_pos);
342 num_removed = std::distance (lower_pos, upper_pos);
343 m_map.erase (lower_pos, upper_pos);
350 typedef std::vector<Entry> collection;
351 typedef typename collection::iterator iterator;
352 typedef typename collection::const_iterator const_iterator;
358 } // namespace lldb_private
360 #endif // #if defined(__cplusplus)
361 #endif // liblldb_UniqueCStringMap_h_