UniqueCStringMap.h revision 272461
1254225Speter//===-- UniqueCStringMap.h --------------------------------------*- C++ -*-===// 2254225Speter// 3254225Speter// The LLVM Compiler Infrastructure 4254225Speter// 5254225Speter// This file is distributed under the University of Illinois Open Source 6254225Speter// License. See LICENSE.TXT for details. 7254225Speter// 8254225Speter//===----------------------------------------------------------------------===// 9254225Speter 10254225Speter#ifndef liblldb_UniqueCStringMap_h_ 11254225Speter#define liblldb_UniqueCStringMap_h_ 12254225Speter#if defined(__cplusplus) 13254225Speter 14254225Speter#include <assert.h> 15254225Speter#include <algorithm> 16254225Speter#include <vector> 17254225Speter 18254225Speter#include "lldb/Core/RegularExpression.h" 19254225Speter 20254225Speternamespace lldb_private { 21254225Speter 22254225Speter 23254225Speter 24254225Speter//---------------------------------------------------------------------- 25254225Speter// Templatized uniqued string map. 26254225Speter// 27254225Speter// This map is useful for mapping unique C string names to values of 28254225Speter// type T. Each "const char *" name added must be unique for a given 29254225Speter// C string value. ConstString::GetCString() can provide such strings. 30254225Speter// Any other string table that has guaranteed unique values can also 31254225Speter// be used. 32254225Speter//---------------------------------------------------------------------- 33254225Spetertemplate <typename T> 34254225Speterclass UniqueCStringMap 35254225Speter{ 36254225Speterpublic: 37254225Speter struct Entry 38254225Speter { 39254225Speter Entry () : 40254225Speter cstring(NULL), 41254225Speter value() 42254225Speter { 43254225Speter } 44254225Speter 45254225Speter Entry (const char *cstr) : 46254225Speter cstring(cstr), 47254225Speter value() 48254225Speter { 49254225Speter } 50254225Speter 51254225Speter Entry (const char *cstr, const T&v) : 52254225Speter cstring(cstr), 53254225Speter value(v) 54254225Speter { 55254225Speter } 56254225Speter 57254225Speter bool 58254225Speter operator < (const Entry& rhs) const 59254225Speter { 60254225Speter return cstring < rhs.cstring; 61254225Speter } 62254225Speter 63254225Speter const char* cstring; 64254225Speter T value; 65254225Speter }; 66254225Speter 67254225Speter //------------------------------------------------------------------ 68254225Speter // Call this function multiple times to add a bunch of entries to 69254225Speter // this map, then later call UniqueCStringMap<T>::Sort() before doing 70254225Speter // any searches by name. 71254225Speter //------------------------------------------------------------------ 72254225Speter void 73254225Speter Append (const char *unique_cstr, const T& value) 74254225Speter { 75254225Speter m_map.push_back (typename UniqueCStringMap<T>::Entry(unique_cstr, value)); 76254225Speter } 77254225Speter 78254225Speter void 79254225Speter Append (const Entry &e) 80254225Speter { 81254225Speter m_map.push_back (e); 82254225Speter } 83254225Speter 84254225Speter void 85254225Speter Clear () 86254225Speter { 87254225Speter m_map.clear(); 88254225Speter } 89254225Speter 90254225Speter //------------------------------------------------------------------ 91254225Speter // Call this function to always keep the map sorted when putting 92254225Speter // entries into the map. 93254225Speter //------------------------------------------------------------------ 94254225Speter void 95254225Speter Insert (const char *unique_cstr, const T& value) 96254225Speter { 97254225Speter typename UniqueCStringMap<T>::Entry e(unique_cstr, value); 98254225Speter m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e); 99254225Speter } 100254225Speter 101254225Speter void 102254225Speter Insert (const Entry &e) 103254225Speter { 104254225Speter m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e); 105254225Speter } 106254225Speter 107254225Speter //------------------------------------------------------------------ 108254225Speter // Get an entries by index in a variety of forms. 109254225Speter // 110 // The caller is responsible for ensuring that the collection does 111 // not change during while using the returned values. 112 //------------------------------------------------------------------ 113 bool 114 GetValueAtIndex (uint32_t idx, T &value) const 115 { 116 if (idx < m_map.size()) 117 { 118 value = m_map[idx].value; 119 return true; 120 } 121 return false; 122 } 123 124 const char * 125 GetCStringAtIndexUnchecked (uint32_t idx) const 126 { 127 return m_map[idx].cstring; 128 } 129 130 // Use this function if you have simple types in your map that you 131 // can easily copy when accessing values by index. 132 T 133 GetValueAtIndexUnchecked (uint32_t idx) const 134 { 135 return m_map[idx].value; 136 } 137 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. 140 const T & 141 GetValueRefAtIndexUnchecked (uint32_t idx) const 142 { 143 return m_map[idx].value; 144 } 145 146 const char * 147 GetCStringAtIndex (uint32_t idx) const 148 { 149 if (idx < m_map.size()) 150 return m_map[idx].cstring; 151 return NULL; 152 } 153 154 //------------------------------------------------------------------ 155 // Find the value for the unique string in the map. 156 // 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 //------------------------------------------------------------------ 162 T 163 Find (const char *unique_cstr, T fail_value) const 164 { 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); 168 if (pos != end) 169 { 170 if (pos->cstring == unique_cstr) 171 return pos->value; 172 } 173 return fail_value; 174 } 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". 178 // 179 // The caller is responsible for ensuring that the collection does 180 // not change during while using the returned pointer. 181 //------------------------------------------------------------------ 182 const Entry * 183 FindFirstValueForName (const char *unique_cstr) const 184 { 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); 188 if (pos != end) 189 { 190 const char *pos_cstr = pos->cstring; 191 if (pos_cstr == unique_cstr) 192 return &(*pos); 193 } 194 return NULL; 195 } 196 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". 201 // 202 // The caller is responsible for ensuring that the collection does 203 // not change during while using the returned pointer. 204 //------------------------------------------------------------------ 205 const Entry * 206 FindNextValueForName (const Entry *entry_ptr) const 207 { 208 if (!m_map.empty()) 209 { 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) 214 { 215 if (next_entry->cstring == entry_ptr->cstring) 216 return next_entry; 217 } 218 } 219 return NULL; 220 } 221 222 size_t 223 GetValues (const char *unique_cstr, std::vector<T> &values) const 224 { 225 const size_t start_size = values.size(); 226 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) 230 { 231 if (pos->cstring == unique_cstr) 232 values.push_back (pos->value); 233 else 234 break; 235 } 236 237 return values.size() - start_size; 238 } 239 240 size_t 241 GetValues (const RegularExpression& regex, std::vector<T> &values) const 242 { 243 const size_t start_size = values.size(); 244 245 const_iterator pos, end = m_map.end(); 246 for (pos = m_map.begin(); pos != end; ++pos) 247 { 248 if (regex.Execute(pos->cstring)) 249 values.push_back (pos->value); 250 } 251 252 return values.size() - start_size; 253 } 254 255 //------------------------------------------------------------------ 256 // Get the total number of entries in this map. 257 //------------------------------------------------------------------ 258 size_t 259 GetSize () const 260 { 261 return m_map.size(); 262 } 263 264 265 //------------------------------------------------------------------ 266 // Returns true if this map is empty. 267 //------------------------------------------------------------------ 268 bool 269 IsEmpty() const 270 { 271 return m_map.empty(); 272 } 273 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 //------------------------------------------------------------------ 280 void 281 Reserve (size_t n) 282 { 283 m_map.reserve (n); 284 } 285 286 //------------------------------------------------------------------ 287 // Sort the unsorted contents in this map. A typical code flow would 288 // be: 289 // size_t approximate_num_entries = .... 290 // UniqueCStringMap<uint32_t> my_map; 291 // my_map.Reserve (approximate_num_entries); 292 // for (...) 293 // { 294 // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...))); 295 // } 296 // my_map.Sort(); 297 //------------------------------------------------------------------ 298 void 299 Sort () 300 { 301 std::sort (m_map.begin(), m_map.end()); 302 } 303 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 //------------------------------------------------------------------ 312 void 313 SizeToFit () 314 { 315 if (m_map.size() < m_map.capacity()) 316 { 317 collection temp (m_map.begin(), m_map.end()); 318 m_map.swap(temp); 319 } 320 } 321 322 size_t 323 Erase (const char *unique_cstr) 324 { 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) 331 { 332 if (lower_pos->cstring == unique_cstr) 333 { 334 iterator upper_pos = std::upper_bound (lower_pos, end, search_entry); 335 if (lower_pos == upper_pos) 336 { 337 m_map.erase (lower_pos); 338 num_removed = 1; 339 } 340 else 341 { 342 num_removed = std::distance (lower_pos, upper_pos); 343 m_map.erase (lower_pos, upper_pos); 344 } 345 } 346 } 347 return num_removed; 348 } 349protected: 350 typedef std::vector<Entry> collection; 351 typedef typename collection::iterator iterator; 352 typedef typename collection::const_iterator const_iterator; 353 collection m_map; 354}; 355 356 357 358} // namespace lldb_private 359 360#endif // #if defined(__cplusplus) 361#endif // liblldb_UniqueCStringMap_h_ 362