UniqueCStringMap.h revision 321369
1204792Srdivacky//===-- UniqueCStringMap.h --------------------------------------*- C++ -*-===// 2204792Srdivacky// 3204792Srdivacky// The LLVM Compiler Infrastructure 4204792Srdivacky// 5204792Srdivacky// This file is distributed under the University of Illinois Open Source 6204792Srdivacky// License. See LICENSE.TXT for details. 7204792Srdivacky// 8204792Srdivacky//===----------------------------------------------------------------------===// 9204792Srdivacky 10204792Srdivacky#ifndef liblldb_UniqueCStringMap_h_ 11204792Srdivacky#define liblldb_UniqueCStringMap_h_ 12204792Srdivacky 13204792Srdivacky// C Includes 14204792Srdivacky// C++ Includes 15239462Sdim#include <algorithm> 16249423Sdim#include <vector> 17249423Sdim 18249423Sdim// Other libraries and framework includes 19249423Sdim// Project includes 20249423Sdim#include "lldb/Utility/ConstString.h" 21249423Sdim#include "lldb/Utility/RegularExpression.h" 22249423Sdim 23249423Sdimnamespace lldb_private { 24234353Sdim 25204792Srdivacky//---------------------------------------------------------------------- 26204792Srdivacky// Templatized uniqued string map. 27204792Srdivacky// 28204792Srdivacky// This map is useful for mapping unique C string names to values of 29204792Srdivacky// type T. Each "const char *" name added must be unique for a given 30204792Srdivacky// C string value. ConstString::GetCString() can provide such strings. 31204792Srdivacky// Any other string table that has guaranteed unique values can also 32204792Srdivacky// be used. 33204792Srdivacky//---------------------------------------------------------------------- 34204792Srdivackytemplate <typename T> class UniqueCStringMap { 35243830Sdimpublic: 36239462Sdim struct Entry { 37239462Sdim Entry() {} 38239462Sdim 39239462Sdim Entry(ConstString cstr) : cstring(cstr), value() {} 40204792Srdivacky 41249423Sdim Entry(ConstString cstr, const T &v) : cstring(cstr), value(v) {} 42249423Sdim 43249423Sdim // This is only for uniqueness, not lexicographical ordering, so we can 44249423Sdim // just compare pointers. 45249423Sdim bool operator<(const Entry &rhs) const { 46204792Srdivacky return cstring.GetCString() < rhs.cstring.GetCString(); 47204792Srdivacky } 48243830Sdim 49249423Sdim ConstString cstring; 50249423Sdim T value; 51204792Srdivacky }; 52204792Srdivacky 53204792Srdivacky //------------------------------------------------------------------ 54204792Srdivacky // Call this function multiple times to add a bunch of entries to 55204792Srdivacky // this map, then later call UniqueCStringMap<T>::Sort() before doing 56204792Srdivacky // any searches by name. 57204792Srdivacky //------------------------------------------------------------------ 58204792Srdivacky void Append(ConstString unique_cstr, const T &value) { 59204792Srdivacky m_map.push_back(typename UniqueCStringMap<T>::Entry(unique_cstr, value)); 60204792Srdivacky } 61239462Sdim 62239462Sdim void Append(const Entry &e) { m_map.push_back(e); } 63239462Sdim 64239462Sdim void Clear() { m_map.clear(); } 65243830Sdim 66239462Sdim //------------------------------------------------------------------ 67239462Sdim // Call this function to always keep the map sorted when putting 68239462Sdim // entries into the map. 69239462Sdim //------------------------------------------------------------------ 70249423Sdim void Insert(ConstString unique_cstr, const T &value) { 71249423Sdim typename UniqueCStringMap<T>::Entry e(unique_cstr, value); 72249423Sdim m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e); 73249423Sdim } 74249423Sdim 75239462Sdim void Insert(const Entry &e) { 76239462Sdim m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e); 77243830Sdim } 78249423Sdim 79249423Sdim //------------------------------------------------------------------ 80239462Sdim // Get an entries by index in a variety of forms. 81239462Sdim // 82239462Sdim // The caller is responsible for ensuring that the collection does 83239462Sdim // not change during while using the returned values. 84239462Sdim //------------------------------------------------------------------ 85239462Sdim bool GetValueAtIndex(uint32_t idx, T &value) const { 86239462Sdim if (idx < m_map.size()) { 87239462Sdim value = m_map[idx].value; 88239462Sdim return true; 89239462Sdim } 90239462Sdim return false; 91204792Srdivacky } 92204792Srdivacky 93204792Srdivacky ConstString GetCStringAtIndexUnchecked(uint32_t idx) const { 94204792Srdivacky return m_map[idx].cstring; 95243830Sdim } 96239462Sdim 97239462Sdim // Use this function if you have simple types in your map that you 98239462Sdim // can easily copy when accessing values by index. 99204792Srdivacky T GetValueAtIndexUnchecked(uint32_t idx) const { return m_map[idx].value; } 100249423Sdim 101249423Sdim // Use this function if you have complex types in your map that you 102249423Sdim // don't want to copy when accessing values by index. 103249423Sdim const T &GetValueRefAtIndexUnchecked(uint32_t idx) const { 104204792Srdivacky return m_map[idx].value; 105226633Sdim } 106226633Sdim 107243830Sdim ConstString GetCStringAtIndex(uint32_t idx) const { 108249423Sdim return ((idx < m_map.size()) ? m_map[idx].cstring : ConstString()); 109249423Sdim } 110204792Srdivacky 111204792Srdivacky //------------------------------------------------------------------ 112204792Srdivacky // Find the value for the unique string in the map. 113204792Srdivacky // 114204792Srdivacky // Return the value for \a unique_cstr if one is found, return 115204792Srdivacky // \a fail_value otherwise. This method works well for simple type 116204792Srdivacky // T values and only if there is a sensible failure value that can 117204792Srdivacky // be returned and that won't match any existing values. 118210299Sed //------------------------------------------------------------------ 119210299Sed T Find(ConstString unique_cstr, T fail_value) const { 120243830Sdim Entry search_entry(unique_cstr); 121239462Sdim const_iterator end = m_map.end(); 122239462Sdim const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry); 123239462Sdim if (pos != end) { 124239462Sdim if (pos->cstring == unique_cstr) 125210299Sed return pos->value; 126249423Sdim } 127249423Sdim return fail_value; 128249423Sdim } 129249423Sdim 130249423Sdim //------------------------------------------------------------------ 131249423Sdim // Get a pointer to the first entry that matches "name". nullptr will 132210299Sed // be returned if there is no entry that matches "name". 133210299Sed // 134243830Sdim // The caller is responsible for ensuring that the collection does 135249423Sdim // not change during while using the returned pointer. 136249423Sdim //------------------------------------------------------------------ 137210299Sed const Entry *FindFirstValueForName(ConstString unique_cstr) const { 138210299Sed Entry search_entry(unique_cstr); 139210299Sed const_iterator end = m_map.end(); 140210299Sed const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry); 141210299Sed if (pos != end && pos->cstring == unique_cstr) 142210299Sed return &(*pos); 143210299Sed return nullptr; 144210299Sed } 145210299Sed 146210299Sed //------------------------------------------------------------------ 147210299Sed // Get a pointer to the next entry that matches "name" from a 148210299Sed // previously returned Entry pointer. nullptr will be returned if there 149210299Sed // is no subsequent entry that matches "name". 150204792Srdivacky // 151204792Srdivacky // The caller is responsible for ensuring that the collection does 152204792Srdivacky // not change during while using the returned pointer. 153243830Sdim //------------------------------------------------------------------ 154239462Sdim const Entry *FindNextValueForName(const Entry *entry_ptr) const { 155239462Sdim if (!m_map.empty()) { 156239462Sdim const Entry *first_entry = &m_map[0]; 157239462Sdim const Entry *after_last_entry = first_entry + m_map.size(); 158204792Srdivacky const Entry *next_entry = entry_ptr + 1; 159249423Sdim if (first_entry <= next_entry && next_entry < after_last_entry) { 160249423Sdim if (next_entry->cstring == entry_ptr->cstring) 161249423Sdim return next_entry; 162249423Sdim } 163226633Sdim } 164243830Sdim return nullptr; 165249423Sdim } 166204792Srdivacky 167204792Srdivacky size_t GetValues(ConstString unique_cstr, std::vector<T> &values) const { 168205218Srdivacky const size_t start_size = values.size(); 169204792Srdivacky 170204792Srdivacky Entry search_entry(unique_cstr); 171204792Srdivacky const_iterator pos, end = m_map.end(); 172204792Srdivacky for (pos = std::lower_bound(m_map.begin(), end, search_entry); pos != end; 173204792Srdivacky ++pos) { 174205218Srdivacky if (pos->cstring == unique_cstr) 175205218Srdivacky values.push_back(pos->value); 176205218Srdivacky else 177243830Sdim break; 178239462Sdim } 179239462Sdim 180239462Sdim return values.size() - start_size; 181239462Sdim } 182205218Srdivacky 183249423Sdim size_t GetValues(const RegularExpression ®ex, 184249423Sdim std::vector<T> &values) const { 185249423Sdim const size_t start_size = values.size(); 186249423Sdim 187226633Sdim const_iterator pos, end = m_map.end(); 188243830Sdim for (pos = m_map.begin(); pos != end; ++pos) { 189249423Sdim if (regex.Execute(pos->cstring.GetCString())) 190249423Sdim values.push_back(pos->value); 191207618Srdivacky } 192207618Srdivacky 193205218Srdivacky return values.size() - start_size; 194205218Srdivacky } 195205218Srdivacky 196205218Srdivacky //------------------------------------------------------------------ 197205218Srdivacky // Get the total number of entries in this map. 198205218Srdivacky //------------------------------------------------------------------ 199205218Srdivacky size_t GetSize() const { return m_map.size(); } 200206083Srdivacky 201206083Srdivacky //------------------------------------------------------------------ 202206083Srdivacky // Returns true if this map is empty. 203206083Srdivacky //------------------------------------------------------------------ 204243830Sdim bool IsEmpty() const { return m_map.empty(); } 205239462Sdim 206239462Sdim //------------------------------------------------------------------ 207239462Sdim // Reserve memory for at least "n" entries in the map. This is 208239462Sdim // useful to call when you know you will be adding a lot of entries 209206083Srdivacky // using UniqueCStringMap::Append() (which should be followed by a 210249423Sdim // call to UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert(). 211249423Sdim //------------------------------------------------------------------ 212249423Sdim void Reserve(size_t n) { m_map.reserve(n); } 213206083Srdivacky 214206083Srdivacky //------------------------------------------------------------------ 215249423Sdim // Sort the unsorted contents in this map. A typical code flow would 216206083Srdivacky // be: 217206083Srdivacky // size_t approximate_num_entries = .... 218206083Srdivacky // UniqueCStringMap<uint32_t> my_map; 219206083Srdivacky // my_map.Reserve (approximate_num_entries); 220206083Srdivacky // for (...) 221206083Srdivacky // { 222206083Srdivacky // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...))); 223206083Srdivacky // } 224206083Srdivacky // my_map.Sort(); 225206083Srdivacky //------------------------------------------------------------------ 226206083Srdivacky void Sort() { std::sort(m_map.begin(), m_map.end()); } 227206083Srdivacky 228206083Srdivacky //------------------------------------------------------------------ 229204792Srdivacky // Since we are using a vector to contain our items it will always 230204792Srdivacky // double its memory consumption as things are added to the vector, 231204792Srdivacky // so if you intend to keep a UniqueCStringMap around and have 232243830Sdim // a lot of entries in the map, you will want to call this function 233239462Sdim // to create a new vector and copy _only_ the exact size needed as 234239462Sdim // part of the finalization of the string map. 235239462Sdim //------------------------------------------------------------------ 236239462Sdim void SizeToFit() { 237204792Srdivacky if (m_map.size() < m_map.capacity()) { 238249423Sdim collection temp(m_map.begin(), m_map.end()); 239249423Sdim m_map.swap(temp); 240249423Sdim } 241249423Sdim } 242204792Srdivacky 243243830Sdim size_t Erase(ConstString unique_cstr) { 244249423Sdim size_t num_removed = 0; 245204792Srdivacky Entry search_entry(unique_cstr); 246204792Srdivacky iterator end = m_map.end(); 247204792Srdivacky iterator begin = m_map.begin(); 248204792Srdivacky iterator lower_pos = std::lower_bound(begin, end, search_entry); 249204792Srdivacky if (lower_pos != end) { 250204792Srdivacky if (lower_pos->cstring == unique_cstr) { 251204792Srdivacky iterator upper_pos = std::upper_bound(lower_pos, end, search_entry); 252204792Srdivacky if (lower_pos == upper_pos) { 253204792Srdivacky m_map.erase(lower_pos); 254204792Srdivacky num_removed = 1; 255204792Srdivacky } else { 256204792Srdivacky num_removed = std::distance(lower_pos, upper_pos); 257204792Srdivacky m_map.erase(lower_pos, upper_pos); 258204792Srdivacky } 259204792Srdivacky } 260243830Sdim } 261239462Sdim return num_removed; 262239462Sdim } 263239462Sdim 264239462Sdimprotected: 265204792Srdivacky typedef std::vector<Entry> collection; 266249423Sdim typedef typename collection::iterator iterator; 267249423Sdim typedef typename collection::const_iterator const_iterator; 268249423Sdim collection m_map; 269249423Sdim}; 270249423Sdim 271249423Sdim} // namespace lldb_private 272204792Srdivacky 273204792Srdivacky#endif // liblldb_UniqueCStringMap_h_ 274243830Sdim