UniqueCStringMap.h revision 172295062971d190d74a0118e0244e3a6e6e6ef7
1//===-- UniqueCStringMap.h --------------------------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef liblldb_UniqueCStringMap_h_ 11#define liblldb_UniqueCStringMap_h_ 12#if defined(__cplusplus) 13 14#include <assert.h> 15#include <algorithm> 16#include <vector> 17 18#include "lldb/Core/RegularExpression.h" 19 20namespace lldb_private { 21 22 23 24//---------------------------------------------------------------------- 25// Templatized uniqued string map. 26// 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 31// be used. 32//---------------------------------------------------------------------- 33template <typename T> 34class UniqueCStringMap 35{ 36public: 37 struct Entry 38 { 39 Entry () : 40 cstring(NULL), 41 value() 42 { 43 } 44 45 Entry (const char *cstr) : 46 cstring(cstr), 47 value() 48 { 49 } 50 51 Entry (const char *cstr, const T&v) : 52 cstring(cstr), 53 value(v) 54 { 55 } 56 57 bool 58 operator < (const Entry& rhs) const 59 { 60 return cstring < rhs.cstring; 61 } 62 63 const char* cstring; 64 T value; 65 }; 66 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 //------------------------------------------------------------------ 72 void 73 Append (const char *unique_cstr, const T& value) 74 { 75 m_map.push_back (typename UniqueCStringMap<T>::Entry(unique_cstr, value)); 76 } 77 78 void 79 Append (const Entry &e) 80 { 81 m_map.push_back (e); 82 } 83 84 void 85 Clear () 86 { 87 m_map.clear(); 88 } 89 90 //------------------------------------------------------------------ 91 // Call this function to always keep the map sorted when putting 92 // entries into the map. 93 //------------------------------------------------------------------ 94 void 95 Insert (const char *unique_cstr, const T& value) 96 { 97 typename UniqueCStringMap<T>::Entry e(unique_cstr, value); 98 m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e); 99 } 100 101 void 102 Insert (const Entry &e) 103 { 104 m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e); 105 } 106 107 //------------------------------------------------------------------ 108 // Get an entries by index in a variety of forms. 109 // 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 // Use this function if you have simple types in your map that you 125 // can easily copy when accessing values by index. 126 T 127 GetValueAtIndexUnchecked (uint32_t idx) const 128 { 129 return m_map[idx].value; 130 } 131 132 // Use this function if you have complex types in your map that you 133 // don't want to copy when accessing values by index. 134 const T & 135 GetValueRefAtIndexUnchecked (uint32_t idx) const 136 { 137 return m_map[idx].value; 138 } 139 140 const char * 141 GetCStringAtIndex (uint32_t idx) const 142 { 143 if (idx < m_map.size()) 144 return m_map[idx].cstring; 145 return NULL; 146 } 147 148 //------------------------------------------------------------------ 149 // Find the value for the unique string in the map. 150 // 151 // Return the value for \a unique_cstr if one is found, return 152 // \a fail_value otherwise. This method works well for simple type 153 // T values and only if there is a sensible failure value that can 154 // be returned and that won't match any existing values. 155 //------------------------------------------------------------------ 156 T 157 Find (const char *unique_cstr, T fail_value) const 158 { 159 Entry search_entry (unique_cstr); 160 const_iterator end = m_map.end(); 161 const_iterator pos = std::lower_bound (m_map.begin(), end, search_entry); 162 if (pos != end) 163 { 164 if (pos->cstring == unique_cstr) 165 return pos->value; 166 } 167 return fail_value; 168 } 169 //------------------------------------------------------------------ 170 // Get a pointer to the first entry that matches "name". NULL will 171 // be returned if there is no entry that matches "name". 172 // 173 // The caller is responsible for ensuring that the collection does 174 // not change during while using the returned pointer. 175 //------------------------------------------------------------------ 176 const Entry * 177 FindFirstValueForName (const char *unique_cstr) const 178 { 179 Entry search_entry (unique_cstr); 180 const_iterator end = m_map.end(); 181 const_iterator pos = std::lower_bound (m_map.begin(), end, search_entry); 182 if (pos != end) 183 { 184 const char *pos_cstr = pos->cstring; 185 if (pos_cstr == unique_cstr) 186 return &(*pos); 187 } 188 return NULL; 189 } 190 191 //------------------------------------------------------------------ 192 // Get a pointer to the next entry that matches "name" from a 193 // previously returned Entry pointer. NULL will be returned if there 194 // is no subsequent entry that matches "name". 195 // 196 // The caller is responsible for ensuring that the collection does 197 // not change during while using the returned pointer. 198 //------------------------------------------------------------------ 199 const Entry * 200 FindNextValueForName (const Entry *entry_ptr) const 201 { 202 if (!m_map.empty()) 203 { 204 const Entry *first_entry = &m_map[0]; 205 const Entry *after_last_entry = first_entry + m_map.size(); 206 const Entry *next_entry = entry_ptr + 1; 207 if (first_entry <= next_entry && next_entry < after_last_entry) 208 { 209 if (next_entry->cstring == entry_ptr->cstring) 210 return next_entry; 211 } 212 } 213 return NULL; 214 } 215 216 size_t 217 GetValues (const char *unique_cstr, std::vector<T> &values) const 218 { 219 const size_t start_size = values.size(); 220 221 Entry search_entry (unique_cstr); 222 const_iterator pos, end = m_map.end(); 223 for (pos = std::lower_bound (m_map.begin(), end, search_entry); pos != end; ++pos) 224 { 225 if (pos->cstring == unique_cstr) 226 values.push_back (pos->value); 227 else 228 break; 229 } 230 231 return values.size() - start_size; 232 } 233 234 size_t 235 GetValues (const RegularExpression& regex, std::vector<T> &values) const 236 { 237 const size_t start_size = values.size(); 238 239 const_iterator pos, end = m_map.end(); 240 for (pos = m_map.begin(); pos != end; ++pos) 241 { 242 if (regex.Execute(pos->cstring)) 243 values.push_back (pos->value); 244 } 245 246 return values.size() - start_size; 247 } 248 249 //------------------------------------------------------------------ 250 // Get the total number of entries in this map. 251 //------------------------------------------------------------------ 252 size_t 253 GetSize () const 254 { 255 return m_map.size(); 256 } 257 258 259 //------------------------------------------------------------------ 260 // Returns true if this map is empty. 261 //------------------------------------------------------------------ 262 bool 263 IsEmpty() const 264 { 265 return m_map.empty(); 266 } 267 268 //------------------------------------------------------------------ 269 // Reserve memory for at least "n" entries in the map. This is 270 // useful to call when you know you will be adding a lot of entries 271 // using UniqueCStringMap::Append() (which should be followed by a 272 // call to UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert(). 273 //------------------------------------------------------------------ 274 void 275 Reserve (size_t n) 276 { 277 m_map.reserve (n); 278 } 279 280 //------------------------------------------------------------------ 281 // Sort the unsorted contents in this map. A typical code flow would 282 // be: 283 // size_t approximate_num_entries = .... 284 // UniqueCStringMap<uint32_t> my_map; 285 // my_map.Reserve (approximate_num_entries); 286 // for (...) 287 // { 288 // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...))); 289 // } 290 // my_map.Sort(); 291 //------------------------------------------------------------------ 292 void 293 Sort () 294 { 295 std::sort (m_map.begin(), m_map.end()); 296 } 297 298 //------------------------------------------------------------------ 299 // Since we are using a vector to contain our items it will always 300 // double its memory consumption as things are added to the vector, 301 // so if you intend to keep a UniqueCStringMap around and have 302 // a lot of entries in the map, you will want to call this function 303 // to create a new vector and copy _only_ the exact size needed as 304 // part of the finalization of the string map. 305 //------------------------------------------------------------------ 306 void 307 SizeToFit () 308 { 309 if (m_map.size() < m_map.capacity()) 310 { 311 collection temp (m_map.begin(), m_map.end()); 312 m_map.swap(temp); 313 } 314 } 315 316 size_t 317 Erase (const char *unique_cstr) 318 { 319 size_t num_removed = 0; 320 Entry search_entry (unique_cstr); 321 iterator end = m_map.end(); 322 iterator begin = m_map.begin(); 323 iterator lower_pos = std::lower_bound (begin, end, search_entry); 324 if (lower_pos != end) 325 { 326 if (lower_pos->cstring == unique_cstr) 327 { 328 iterator upper_pos = std::upper_bound (lower_pos, end, search_entry); 329 if (lower_pos == upper_pos) 330 { 331 m_map.erase (lower_pos); 332 num_removed = 1; 333 } 334 else 335 { 336 num_removed = std::distance (lower_pos, upper_pos); 337 m_map.erase (lower_pos, upper_pos); 338 } 339 } 340 } 341 return num_removed; 342 } 343protected: 344 typedef std::vector<Entry> collection; 345 typedef typename collection::iterator iterator; 346 typedef typename collection::const_iterator const_iterator; 347 collection m_map; 348}; 349 350 351 352} // namespace lldb_private 353 354#endif // #if defined(__cplusplus) 355#endif // liblldb_UniqueCStringMap_h_ 356