UniqueCStringMap.h revision 53d68e749f0715691a95f23e9490d97e484b15da
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 18namespace lldb_private { 19 20 21 22//---------------------------------------------------------------------- 23// Templatized uniqued string map. 24// 25// This map is useful for mapping unique C string names to values of 26// type T. Each "const char *" name added must be unique for a given 27// C string value. ConstString::GetCString() can provide such strings. 28// Any other string table that has guaranteed unique values can also 29// be used. 30//---------------------------------------------------------------------- 31template <typename T> 32class UniqueCStringMap 33{ 34public: 35 struct Entry 36 { 37 Entry () : 38 cstring(NULL), 39 value() 40 { 41 } 42 43 Entry (const char *cstr) : 44 cstring(cstr), 45 value() 46 { 47 } 48 49 Entry (const char *cstr, const T&v) : 50 cstring(cstr), 51 value(v) 52 { 53 } 54 55 bool 56 operator < (const Entry& rhs) const 57 { 58 return cstring < rhs.cstring; 59 } 60 61 const char* cstring; 62 T value; 63 }; 64 65 //------------------------------------------------------------------ 66 // Call this function multiple times to add a bunch of entries to 67 // this map, then later call UniqueCStringMap<T>::Sort() before doing 68 // any searches by name. 69 //------------------------------------------------------------------ 70 void 71 Append (const char *unique_cstr, const T& value) 72 { 73 m_map.push_back (typename UniqueCStringMap<T>::Entry(unique_cstr, value)); 74 } 75 76 void 77 Append (const Entry &e) 78 { 79 m_map.push_back (e); 80 } 81 82 void 83 Clear () 84 { 85 m_map.clear(); 86 } 87 88 //------------------------------------------------------------------ 89 // Call this function to always keep the map sorted when putting 90 // entries into the map. 91 //------------------------------------------------------------------ 92 void 93 Insert (const char *unique_cstr, const T& value) 94 { 95 typename UniqueCStringMap<T>::Entry e(unique_cstr, value); 96 m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e); 97 } 98 99 void 100 Insert (const Entry &e) 101 { 102 m_map.insert (std::upper_bound (m_map.begin(), m_map.end(), e), e); 103 } 104 105 //------------------------------------------------------------------ 106 // Get an entry by index. 107 // 108 // The caller is responsible for ensuring that the collection does 109 // not change during while using the returned pointer. 110 //------------------------------------------------------------------ 111 const T * 112 GetValueAtIndex (uint32_t idx) const 113 { 114 if (idx < m_map.size()) 115 return &m_map[idx].value; 116 return NULL; 117 } 118 119 const char * 120 GetCStringAtIndex (uint32_t idx) const 121 { 122 if (idx < m_map.size()) 123 return m_map[idx].cstring; 124 return NULL; 125 } 126 127 //------------------------------------------------------------------ 128 // Get a pointer to the first entry that matches "name". NULL will 129 // be returned if there is no entry that matches "name". 130 // 131 // The caller is responsible for ensuring that the collection does 132 // not change during while using the returned pointer. 133 //------------------------------------------------------------------ 134 const Entry * 135 FindFirstValueForName (const char *unique_cstr) const 136 { 137 Entry search_entry (unique_cstr); 138 const_iterator end = m_map.end(); 139 const_iterator pos = std::lower_bound (m_map.begin(), end, search_entry); 140 if (pos != end) 141 { 142 const char *pos_cstr = pos->cstring; 143 if (pos_cstr == unique_cstr) 144 return &(*pos); 145 } 146 return NULL; 147 } 148 149 //------------------------------------------------------------------ 150 // Get a pointer to the next entry that matches "name" from a 151 // previously returned Entry pointer. NULL will be returned if there 152 // is no subsequent entry that matches "name". 153 // 154 // The caller is responsible for ensuring that the collection does 155 // not change during while using the returned pointer. 156 //------------------------------------------------------------------ 157 const Entry * 158 FindNextValueForName (const char *unique_cstr, const Entry *entry_ptr) const 159 { 160 if (!m_map.empty()) 161 { 162 const Entry *first_entry = &m_map[0]; 163 const Entry *after_last_entry = first_entry + m_map.size(); 164 const Entry *next_entry = entry_ptr + 1; 165 if (first_entry <= next_entry && next_entry < after_last_entry) 166 { 167 if (next_entry->cstring == unique_cstr) 168 return next_entry; 169 } 170 } 171 return NULL; 172 } 173 174 //------------------------------------------------------------------ 175 // Get the total number of entries in this map. 176 //------------------------------------------------------------------ 177 size_t 178 GetSize () 179 { 180 return m_map.size(); 181 } 182 183 184 //------------------------------------------------------------------ 185 // Returns true if this map is empty. 186 //------------------------------------------------------------------ 187 bool 188 IsEmpty() const 189 { 190 return m_map.empty(); 191 } 192 193 //------------------------------------------------------------------ 194 // Reserve memory for at least "n" entries in the map. This is 195 // useful to call when you know you will be adding a lot of entries 196 // using UniqueCStringMap::Append() (which should be followed by a 197 // call to UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert(). 198 //------------------------------------------------------------------ 199 void 200 Reserve (size_t n) 201 { 202 m_map.reserve (n); 203 } 204 205 //------------------------------------------------------------------ 206 // Sort the unsorted contents in this map. A typical code flow would 207 // be: 208 // size_t approximate_num_entries = .... 209 // UniqueCStringMap<uint32_t> my_map; 210 // my_map.Reserve (approximate_num_entries); 211 // for (...) 212 // { 213 // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...))); 214 // } 215 // my_map.Sort(); 216 //------------------------------------------------------------------ 217 void 218 Sort () 219 { 220 std::sort (m_map.begin(), m_map.end()); 221 } 222 223protected: 224 typedef std::vector<Entry> collection; 225 typedef typename collection::iterator iterator; 226 typedef typename collection::const_iterator const_iterator; 227 collection m_map; 228}; 229 230 231 232} // namespace lldb_private 233 234#endif // #if defined(__cplusplus) 235#endif // liblldb_UniqueCStringMap_h_ 236