1//===-- UniqueCStringMap.h --------------------------------------*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8 9#ifndef liblldb_UniqueCStringMap_h_ 10#define liblldb_UniqueCStringMap_h_ 11 12#include <algorithm> 13#include <vector> 14 15#include "lldb/Utility/ConstString.h" 16#include "lldb/Utility/RegularExpression.h" 17 18namespace lldb_private { 19 20// Templatized uniqued string map. 21// 22// This map is useful for mapping unique C string names to values of type T. 23// Each "const char *" name added must be unique for a given 24// C string value. ConstString::GetCString() can provide such strings. 25// Any other string table that has guaranteed unique values can also be used. 26template <typename T> class UniqueCStringMap { 27public: 28 struct Entry { 29 Entry(ConstString cstr, const T &v) : cstring(cstr), value(v) {} 30 31 ConstString cstring; 32 T value; 33 }; 34 35 // Call this function multiple times to add a bunch of entries to this map, 36 // then later call UniqueCStringMap<T>::Sort() before doing any searches by 37 // name. 38 void Append(ConstString unique_cstr, const T &value) { 39 m_map.push_back(typename UniqueCStringMap<T>::Entry(unique_cstr, value)); 40 } 41 42 void Append(const Entry &e) { m_map.push_back(e); } 43 44 void Clear() { m_map.clear(); } 45 46 // Get an entries by index in a variety of forms. 47 // 48 // The caller is responsible for ensuring that the collection does not change 49 // during while using the returned values. 50 bool GetValueAtIndex(uint32_t idx, T &value) const { 51 if (idx < m_map.size()) { 52 value = m_map[idx].value; 53 return true; 54 } 55 return false; 56 } 57 58 ConstString GetCStringAtIndexUnchecked(uint32_t idx) const { 59 return m_map[idx].cstring; 60 } 61 62 // Use this function if you have simple types in your map that you can easily 63 // copy when accessing values by index. 64 T GetValueAtIndexUnchecked(uint32_t idx) const { return m_map[idx].value; } 65 66 // Use this function if you have complex types in your map that you don't 67 // want to copy when accessing values by index. 68 const T &GetValueRefAtIndexUnchecked(uint32_t idx) const { 69 return m_map[idx].value; 70 } 71 72 ConstString GetCStringAtIndex(uint32_t idx) const { 73 return ((idx < m_map.size()) ? m_map[idx].cstring : ConstString()); 74 } 75 76 // Find the value for the unique string in the map. 77 // 78 // Return the value for \a unique_cstr if one is found, return \a fail_value 79 // otherwise. This method works well for simple type 80 // T values and only if there is a sensible failure value that can 81 // be returned and that won't match any existing values. 82 T Find(ConstString unique_cstr, T fail_value) const { 83 auto pos = llvm::lower_bound(m_map, unique_cstr, Compare()); 84 if (pos != m_map.end() && pos->cstring == unique_cstr) 85 return pos->value; 86 return fail_value; 87 } 88 89 // Get a pointer to the first entry that matches "name". nullptr will be 90 // returned if there is no entry that matches "name". 91 // 92 // The caller is responsible for ensuring that the collection does not change 93 // during while using the returned pointer. 94 const Entry *FindFirstValueForName(ConstString unique_cstr) const { 95 auto pos = llvm::lower_bound(m_map, unique_cstr, Compare()); 96 if (pos != m_map.end() && pos->cstring == unique_cstr) 97 return &(*pos); 98 return nullptr; 99 } 100 101 // Get a pointer to the next entry that matches "name" from a previously 102 // returned Entry pointer. nullptr will be returned if there is no subsequent 103 // entry that matches "name". 104 // 105 // The caller is responsible for ensuring that the collection does not change 106 // during while using the returned pointer. 107 const Entry *FindNextValueForName(const Entry *entry_ptr) const { 108 if (!m_map.empty()) { 109 const Entry *first_entry = &m_map[0]; 110 const Entry *after_last_entry = first_entry + m_map.size(); 111 const Entry *next_entry = entry_ptr + 1; 112 if (first_entry <= next_entry && next_entry < after_last_entry) { 113 if (next_entry->cstring == entry_ptr->cstring) 114 return next_entry; 115 } 116 } 117 return nullptr; 118 } 119 120 size_t GetValues(ConstString unique_cstr, std::vector<T> &values) const { 121 const size_t start_size = values.size(); 122 123 for (const Entry &entry : llvm::make_range(std::equal_range( 124 m_map.begin(), m_map.end(), unique_cstr, Compare()))) 125 values.push_back(entry.value); 126 127 return values.size() - start_size; 128 } 129 130 size_t GetValues(const RegularExpression ®ex, 131 std::vector<T> &values) const { 132 const size_t start_size = values.size(); 133 134 const_iterator pos, end = m_map.end(); 135 for (pos = m_map.begin(); pos != end; ++pos) { 136 if (regex.Execute(pos->cstring.GetCString())) 137 values.push_back(pos->value); 138 } 139 140 return values.size() - start_size; 141 } 142 143 // Get the total number of entries in this map. 144 size_t GetSize() const { return m_map.size(); } 145 146 // Returns true if this map is empty. 147 bool IsEmpty() const { return m_map.empty(); } 148 149 // Reserve memory for at least "n" entries in the map. This is useful to call 150 // when you know you will be adding a lot of entries using 151 // UniqueCStringMap::Append() (which should be followed by a call to 152 // UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert(). 153 void Reserve(size_t n) { m_map.reserve(n); } 154 155 // Sort the unsorted contents in this map. A typical code flow would be: 156 // size_t approximate_num_entries = .... 157 // UniqueCStringMap<uint32_t> my_map; 158 // my_map.Reserve (approximate_num_entries); 159 // for (...) 160 // { 161 // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...))); 162 // } 163 // my_map.Sort(); 164 void Sort() { llvm::sort(m_map.begin(), m_map.end(), Compare()); } 165 166 // Since we are using a vector to contain our items it will always double its 167 // memory consumption as things are added to the vector, so if you intend to 168 // keep a UniqueCStringMap around and have a lot of entries in the map, you 169 // will want to call this function to create a new vector and copy _only_ the 170 // exact size needed as part of the finalization of the string map. 171 void SizeToFit() { 172 if (m_map.size() < m_map.capacity()) { 173 collection temp(m_map.begin(), m_map.end()); 174 m_map.swap(temp); 175 } 176 } 177 178protected: 179 struct Compare { 180 bool operator()(const Entry &lhs, const Entry &rhs) { 181 return operator()(lhs.cstring, rhs.cstring); 182 } 183 184 bool operator()(const Entry &lhs, ConstString rhs) { 185 return operator()(lhs.cstring, rhs); 186 } 187 188 bool operator()(ConstString lhs, const Entry &rhs) { 189 return operator()(lhs, rhs.cstring); 190 } 191 192 // This is only for uniqueness, not lexicographical ordering, so we can 193 // just compare pointers. *However*, comparing pointers from different 194 // allocations is UB, so we need compare their integral values instead. 195 bool operator()(ConstString lhs, ConstString rhs) { 196 return uintptr_t(lhs.GetCString()) < uintptr_t(rhs.GetCString()); 197 } 198 }; 199 typedef std::vector<Entry> collection; 200 typedef typename collection::iterator iterator; 201 typedef typename collection::const_iterator const_iterator; 202 collection m_map; 203}; 204 205} // namespace lldb_private 206 207#endif // liblldb_UniqueCStringMap_h_ 208