UniqueCStringMap.h revision 24943d2ee8bfaa7cf5893e4709143924157a5c1e
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 const Entry *first_entry = m_map.data(); 161 const Entry *after_last_entry = first_entry + m_map.size(); 162 const Entry *next_entry = entry_ptr + 1; 163 if (first_entry <= next_entry && next_entry < after_last_entry) 164 { 165 if (next_entry->cstring == unique_cstr) 166 return next_entry; 167 } 168 return NULL; 169 } 170 171 //------------------------------------------------------------------ 172 // Get the total number of entries in this map. 173 //------------------------------------------------------------------ 174 size_t 175 GetSize () 176 { 177 return m_map.size(); 178 } 179 180 181 //------------------------------------------------------------------ 182 // Returns true if this map is empty. 183 //------------------------------------------------------------------ 184 bool 185 IsEmpty() const 186 { 187 return m_map.empty(); 188 } 189 190 //------------------------------------------------------------------ 191 // Reserve memory for at least "n" entries in the map. This is 192 // useful to call when you know you will be adding a lot of entries 193 // using UniqueCStringMap::Append() (which should be followed by a 194 // call to UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert(). 195 //------------------------------------------------------------------ 196 void 197 Reserve (size_t n) 198 { 199 m_map.reserve (n); 200 } 201 202 //------------------------------------------------------------------ 203 // Sort the unsorted contents in this map. A typical code flow would 204 // be: 205 // size_t approximate_num_entries = .... 206 // UniqueCStringMap<uint32_t> my_map; 207 // my_map.Reserve (approximate_num_entries); 208 // for (...) 209 // { 210 // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...))); 211 // } 212 // my_map.Sort(); 213 //------------------------------------------------------------------ 214 void 215 Sort () 216 { 217 std::sort (m_map.begin(), m_map.end()); 218 } 219 220protected: 221 typedef std::vector<Entry> collection; 222 typedef typename collection::iterator iterator; 223 typedef typename collection::const_iterator const_iterator; 224 collection m_map; 225}; 226 227 228 229} // namespace lldb_private 230 231#endif // #if defined(__cplusplus) 232#endif // liblldb_UniqueCStringMap_h_ 233