1254721Semaste//===-- UniqueCStringMap.h --------------------------------------*- C++ -*-===// 2254721Semaste// 3254721Semaste// The LLVM Compiler Infrastructure 4254721Semaste// 5254721Semaste// This file is distributed under the University of Illinois Open Source 6254721Semaste// License. See LICENSE.TXT for details. 7254721Semaste// 8254721Semaste//===----------------------------------------------------------------------===// 9254721Semaste 10254721Semaste#ifndef liblldb_UniqueCStringMap_h_ 11254721Semaste#define liblldb_UniqueCStringMap_h_ 12254721Semaste#if defined(__cplusplus) 13254721Semaste 14254721Semaste#include <assert.h> 15254721Semaste#include <algorithm> 16254721Semaste#include <vector> 17254721Semaste 18254721Semaste#include "lldb/Core/RegularExpression.h" 19254721Semaste 20254721Semastenamespace lldb_private { 21254721Semaste 22254721Semaste 23254721Semaste 24254721Semaste//---------------------------------------------------------------------- 25254721Semaste// Templatized uniqued string map. 26254721Semaste// 27254721Semaste// This map is useful for mapping unique C string names to values of 28254721Semaste// type T. Each "const char *" name added must be unique for a given 29254721Semaste// C string value. ConstString::GetCString() can provide such strings. 30254721Semaste// Any other string table that has guaranteed unique values can also 31254721Semaste// be used. 32254721Semaste//---------------------------------------------------------------------- 33254721Semastetemplate <typename T> 34254721Semasteclass UniqueCStringMap 35254721Semaste{ 36254721Semastepublic: 37254721Semaste struct Entry 38254721Semaste { 39254721Semaste Entry () : 40254721Semaste cstring(NULL), 41254721Semaste value() 42254721Semaste { 43254721Semaste } 44254721Semaste 45254721Semaste Entry (const char *cstr) : 46254721Semaste cstring(cstr), 47254721Semaste value() 48254721Semaste { 49254721Semaste } 50254721Semaste 51254721Semaste Entry (const char *cstr, const T&v) : 52254721Semaste cstring(cstr), 53254721Semaste value(v) 54254721Semaste { 55254721Semaste } 56254721Semaste 57254721Semaste bool 58254721Semaste operator < (const Entry& rhs) const 59254721Semaste { 60254721Semaste return cstring < rhs.cstring; 61254721Semaste } 62254721Semaste 63254721Semaste const char* cstring; 64254721Semaste T value; 65254721Semaste }; 66254721Semaste 67254721Semaste //------------------------------------------------------------------ 68254721Semaste // Call this function multiple times to add a bunch of entries to 69254721Semaste // this map, then later call UniqueCStringMap<T>::Sort() before doing 70254721Semaste // any searches by name. 71254721Semaste //------------------------------------------------------------------ 72254721Semaste void 73254721Semaste Append (const char *unique_cstr, const T& value) 74254721Semaste { 75254721Semaste m_map.push_back (typename UniqueCStringMap<T>::Entry(unique_cstr, value)); 76254721Semaste } 77254721Semaste 78254721Semaste void 79254721Semaste Append (const Entry &e) 80254721Semaste { 81254721Semaste m_map.push_back (e); 82254721Semaste } 83254721Semaste 84254721Semaste void 85254721Semaste Clear () 86254721Semaste { 87254721Semaste m_map.clear(); 88254721Semaste } 89254721Semaste 90254721Semaste //------------------------------------------------------------------ 91254721Semaste // Call this function to always keep the map sorted when putting 92254721Semaste // entries into the map. 93254721Semaste //------------------------------------------------------------------ 94254721Semaste void 95254721Semaste Insert (const char *unique_cstr, const T& value) 96254721Semaste { 97254721Semaste typename UniqueCStringMap<T>::Entry e(unique_cstr, value); 98254721Semaste m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e); 99254721Semaste } 100254721Semaste 101254721Semaste void 102254721Semaste Insert (const Entry &e) 103254721Semaste { 104254721Semaste m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e); 105254721Semaste } 106254721Semaste 107254721Semaste //------------------------------------------------------------------ 108254721Semaste // Get an entries by index in a variety of forms. 109254721Semaste // 110254721Semaste // The caller is responsible for ensuring that the collection does 111254721Semaste // not change during while using the returned values. 112254721Semaste //------------------------------------------------------------------ 113254721Semaste bool 114254721Semaste GetValueAtIndex (uint32_t idx, T &value) const 115254721Semaste { 116254721Semaste if (idx < m_map.size()) 117254721Semaste { 118254721Semaste value = m_map[idx].value; 119254721Semaste return true; 120254721Semaste } 121254721Semaste return false; 122254721Semaste } 123254721Semaste 124254721Semaste const char * 125254721Semaste GetCStringAtIndexUnchecked (uint32_t idx) const 126254721Semaste { 127254721Semaste return m_map[idx].cstring; 128254721Semaste } 129254721Semaste 130254721Semaste // Use this function if you have simple types in your map that you 131254721Semaste // can easily copy when accessing values by index. 132254721Semaste T 133254721Semaste GetValueAtIndexUnchecked (uint32_t idx) const 134254721Semaste { 135254721Semaste return m_map[idx].value; 136254721Semaste } 137254721Semaste 138254721Semaste // Use this function if you have complex types in your map that you 139254721Semaste // don't want to copy when accessing values by index. 140254721Semaste const T & 141254721Semaste GetValueRefAtIndexUnchecked (uint32_t idx) const 142254721Semaste { 143254721Semaste return m_map[idx].value; 144254721Semaste } 145254721Semaste 146254721Semaste const char * 147254721Semaste GetCStringAtIndex (uint32_t idx) const 148254721Semaste { 149254721Semaste if (idx < m_map.size()) 150254721Semaste return m_map[idx].cstring; 151254721Semaste return NULL; 152254721Semaste } 153254721Semaste 154254721Semaste //------------------------------------------------------------------ 155254721Semaste // Find the value for the unique string in the map. 156254721Semaste // 157254721Semaste // Return the value for \a unique_cstr if one is found, return 158254721Semaste // \a fail_value otherwise. This method works well for simple type 159254721Semaste // T values and only if there is a sensible failure value that can 160254721Semaste // be returned and that won't match any existing values. 161254721Semaste //------------------------------------------------------------------ 162254721Semaste T 163254721Semaste Find (const char *unique_cstr, T fail_value) const 164254721Semaste { 165254721Semaste Entry search_entry (unique_cstr); 166254721Semaste const_iterator end = m_map.end(); 167254721Semaste const_iterator pos = std::lower_bound (m_map.begin(), end, search_entry); 168254721Semaste if (pos != end) 169254721Semaste { 170254721Semaste if (pos->cstring == unique_cstr) 171254721Semaste return pos->value; 172254721Semaste } 173254721Semaste return fail_value; 174254721Semaste } 175254721Semaste //------------------------------------------------------------------ 176254721Semaste // Get a pointer to the first entry that matches "name". NULL will 177254721Semaste // be returned if there is no entry that matches "name". 178254721Semaste // 179254721Semaste // The caller is responsible for ensuring that the collection does 180254721Semaste // not change during while using the returned pointer. 181254721Semaste //------------------------------------------------------------------ 182254721Semaste const Entry * 183254721Semaste FindFirstValueForName (const char *unique_cstr) const 184254721Semaste { 185254721Semaste Entry search_entry (unique_cstr); 186254721Semaste const_iterator end = m_map.end(); 187254721Semaste const_iterator pos = std::lower_bound (m_map.begin(), end, search_entry); 188254721Semaste if (pos != end) 189254721Semaste { 190254721Semaste const char *pos_cstr = pos->cstring; 191254721Semaste if (pos_cstr == unique_cstr) 192254721Semaste return &(*pos); 193254721Semaste } 194254721Semaste return NULL; 195254721Semaste } 196254721Semaste 197254721Semaste //------------------------------------------------------------------ 198254721Semaste // Get a pointer to the next entry that matches "name" from a 199254721Semaste // previously returned Entry pointer. NULL will be returned if there 200254721Semaste // is no subsequent entry that matches "name". 201254721Semaste // 202254721Semaste // The caller is responsible for ensuring that the collection does 203254721Semaste // not change during while using the returned pointer. 204254721Semaste //------------------------------------------------------------------ 205254721Semaste const Entry * 206254721Semaste FindNextValueForName (const Entry *entry_ptr) const 207254721Semaste { 208254721Semaste if (!m_map.empty()) 209254721Semaste { 210254721Semaste const Entry *first_entry = &m_map[0]; 211254721Semaste const Entry *after_last_entry = first_entry + m_map.size(); 212254721Semaste const Entry *next_entry = entry_ptr + 1; 213254721Semaste if (first_entry <= next_entry && next_entry < after_last_entry) 214254721Semaste { 215254721Semaste if (next_entry->cstring == entry_ptr->cstring) 216254721Semaste return next_entry; 217254721Semaste } 218254721Semaste } 219254721Semaste return NULL; 220254721Semaste } 221254721Semaste 222254721Semaste size_t 223254721Semaste GetValues (const char *unique_cstr, std::vector<T> &values) const 224254721Semaste { 225254721Semaste const size_t start_size = values.size(); 226254721Semaste 227254721Semaste Entry search_entry (unique_cstr); 228254721Semaste const_iterator pos, end = m_map.end(); 229254721Semaste for (pos = std::lower_bound (m_map.begin(), end, search_entry); pos != end; ++pos) 230254721Semaste { 231254721Semaste if (pos->cstring == unique_cstr) 232254721Semaste values.push_back (pos->value); 233254721Semaste else 234254721Semaste break; 235254721Semaste } 236254721Semaste 237254721Semaste return values.size() - start_size; 238254721Semaste } 239254721Semaste 240254721Semaste size_t 241254721Semaste GetValues (const RegularExpression& regex, std::vector<T> &values) const 242254721Semaste { 243254721Semaste const size_t start_size = values.size(); 244254721Semaste 245254721Semaste const_iterator pos, end = m_map.end(); 246254721Semaste for (pos = m_map.begin(); pos != end; ++pos) 247254721Semaste { 248254721Semaste if (regex.Execute(pos->cstring)) 249254721Semaste values.push_back (pos->value); 250254721Semaste } 251254721Semaste 252254721Semaste return values.size() - start_size; 253254721Semaste } 254254721Semaste 255254721Semaste //------------------------------------------------------------------ 256254721Semaste // Get the total number of entries in this map. 257254721Semaste //------------------------------------------------------------------ 258254721Semaste size_t 259254721Semaste GetSize () const 260254721Semaste { 261254721Semaste return m_map.size(); 262254721Semaste } 263254721Semaste 264254721Semaste 265254721Semaste //------------------------------------------------------------------ 266254721Semaste // Returns true if this map is empty. 267254721Semaste //------------------------------------------------------------------ 268254721Semaste bool 269254721Semaste IsEmpty() const 270254721Semaste { 271254721Semaste return m_map.empty(); 272254721Semaste } 273254721Semaste 274254721Semaste //------------------------------------------------------------------ 275254721Semaste // Reserve memory for at least "n" entries in the map. This is 276254721Semaste // useful to call when you know you will be adding a lot of entries 277254721Semaste // using UniqueCStringMap::Append() (which should be followed by a 278254721Semaste // call to UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert(). 279254721Semaste //------------------------------------------------------------------ 280254721Semaste void 281254721Semaste Reserve (size_t n) 282254721Semaste { 283254721Semaste m_map.reserve (n); 284254721Semaste } 285254721Semaste 286254721Semaste //------------------------------------------------------------------ 287254721Semaste // Sort the unsorted contents in this map. A typical code flow would 288254721Semaste // be: 289254721Semaste // size_t approximate_num_entries = .... 290254721Semaste // UniqueCStringMap<uint32_t> my_map; 291254721Semaste // my_map.Reserve (approximate_num_entries); 292254721Semaste // for (...) 293254721Semaste // { 294254721Semaste // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...))); 295254721Semaste // } 296254721Semaste // my_map.Sort(); 297254721Semaste //------------------------------------------------------------------ 298254721Semaste void 299254721Semaste Sort () 300254721Semaste { 301254721Semaste std::sort (m_map.begin(), m_map.end()); 302254721Semaste } 303254721Semaste 304254721Semaste //------------------------------------------------------------------ 305254721Semaste // Since we are using a vector to contain our items it will always 306254721Semaste // double its memory consumption as things are added to the vector, 307254721Semaste // so if you intend to keep a UniqueCStringMap around and have 308254721Semaste // a lot of entries in the map, you will want to call this function 309254721Semaste // to create a new vector and copy _only_ the exact size needed as 310254721Semaste // part of the finalization of the string map. 311254721Semaste //------------------------------------------------------------------ 312254721Semaste void 313254721Semaste SizeToFit () 314254721Semaste { 315254721Semaste if (m_map.size() < m_map.capacity()) 316254721Semaste { 317254721Semaste collection temp (m_map.begin(), m_map.end()); 318254721Semaste m_map.swap(temp); 319254721Semaste } 320254721Semaste } 321254721Semaste 322254721Semaste size_t 323254721Semaste Erase (const char *unique_cstr) 324254721Semaste { 325254721Semaste size_t num_removed = 0; 326254721Semaste Entry search_entry (unique_cstr); 327254721Semaste iterator end = m_map.end(); 328254721Semaste iterator begin = m_map.begin(); 329254721Semaste iterator lower_pos = std::lower_bound (begin, end, search_entry); 330254721Semaste if (lower_pos != end) 331254721Semaste { 332254721Semaste if (lower_pos->cstring == unique_cstr) 333254721Semaste { 334254721Semaste iterator upper_pos = std::upper_bound (lower_pos, end, search_entry); 335254721Semaste if (lower_pos == upper_pos) 336254721Semaste { 337254721Semaste m_map.erase (lower_pos); 338254721Semaste num_removed = 1; 339254721Semaste } 340254721Semaste else 341254721Semaste { 342254721Semaste num_removed = std::distance (lower_pos, upper_pos); 343254721Semaste m_map.erase (lower_pos, upper_pos); 344254721Semaste } 345254721Semaste } 346254721Semaste } 347254721Semaste return num_removed; 348254721Semaste } 349254721Semasteprotected: 350254721Semaste typedef std::vector<Entry> collection; 351254721Semaste typedef typename collection::iterator iterator; 352254721Semaste typedef typename collection::const_iterator const_iterator; 353254721Semaste collection m_map; 354254721Semaste}; 355254721Semaste 356254721Semaste 357254721Semaste 358254721Semaste} // namespace lldb_private 359254721Semaste 360254721Semaste#endif // #if defined(__cplusplus) 361254721Semaste#endif // liblldb_UniqueCStringMap_h_ 362