1254721Semaste//===-- UniqueCStringMap.h --------------------------------------*- C++ -*-===// 2254721Semaste// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6254721Semaste// 7254721Semaste//===----------------------------------------------------------------------===// 8254721Semaste 9254721Semaste#ifndef liblldb_UniqueCStringMap_h_ 10254721Semaste#define liblldb_UniqueCStringMap_h_ 11254721Semaste 12254721Semaste#include <algorithm> 13254721Semaste#include <vector> 14254721Semaste 15321369Sdim#include "lldb/Utility/ConstString.h" 16321369Sdim#include "lldb/Utility/RegularExpression.h" 17254721Semaste 18254721Semastenamespace lldb_private { 19254721Semaste 20254721Semaste// Templatized uniqued string map. 21254721Semaste// 22341825Sdim// This map is useful for mapping unique C string names to values of type T. 23341825Sdim// Each "const char *" name added must be unique for a given 24254721Semaste// C string value. ConstString::GetCString() can provide such strings. 25341825Sdim// Any other string table that has guaranteed unique values can also be used. 26314564Sdimtemplate <typename T> class UniqueCStringMap { 27254721Semastepublic: 28314564Sdim struct Entry { 29321369Sdim Entry(ConstString cstr, const T &v) : cstring(cstr), value(v) {} 30254721Semaste 31321369Sdim ConstString cstring; 32314564Sdim T value; 33314564Sdim }; 34254721Semaste 35341825Sdim // Call this function multiple times to add a bunch of entries to this map, 36341825Sdim // then later call UniqueCStringMap<T>::Sort() before doing any searches by 37341825Sdim // name. 38321369Sdim void Append(ConstString unique_cstr, const T &value) { 39314564Sdim m_map.push_back(typename UniqueCStringMap<T>::Entry(unique_cstr, value)); 40314564Sdim } 41254721Semaste 42314564Sdim void Append(const Entry &e) { m_map.push_back(e); } 43254721Semaste 44314564Sdim void Clear() { m_map.clear(); } 45254721Semaste 46314564Sdim // Get an entries by index in a variety of forms. 47314564Sdim // 48341825Sdim // The caller is responsible for ensuring that the collection does not change 49341825Sdim // during while using the returned values. 50314564Sdim bool GetValueAtIndex(uint32_t idx, T &value) const { 51314564Sdim if (idx < m_map.size()) { 52314564Sdim value = m_map[idx].value; 53314564Sdim return true; 54254721Semaste } 55314564Sdim return false; 56314564Sdim } 57254721Semaste 58321369Sdim ConstString GetCStringAtIndexUnchecked(uint32_t idx) const { 59314564Sdim return m_map[idx].cstring; 60314564Sdim } 61254721Semaste 62341825Sdim // Use this function if you have simple types in your map that you can easily 63341825Sdim // copy when accessing values by index. 64314564Sdim T GetValueAtIndexUnchecked(uint32_t idx) const { return m_map[idx].value; } 65254721Semaste 66341825Sdim // Use this function if you have complex types in your map that you don't 67341825Sdim // want to copy when accessing values by index. 68314564Sdim const T &GetValueRefAtIndexUnchecked(uint32_t idx) const { 69314564Sdim return m_map[idx].value; 70314564Sdim } 71314564Sdim 72321369Sdim ConstString GetCStringAtIndex(uint32_t idx) const { 73321369Sdim return ((idx < m_map.size()) ? m_map[idx].cstring : ConstString()); 74314564Sdim } 75314564Sdim 76314564Sdim // Find the value for the unique string in the map. 77314564Sdim // 78341825Sdim // Return the value for \a unique_cstr if one is found, return \a fail_value 79341825Sdim // otherwise. This method works well for simple type 80314564Sdim // T values and only if there is a sensible failure value that can 81314564Sdim // be returned and that won't match any existing values. 82321369Sdim T Find(ConstString unique_cstr, T fail_value) const { 83353358Sdim auto pos = llvm::lower_bound(m_map, unique_cstr, Compare()); 84353358Sdim if (pos != m_map.end() && pos->cstring == unique_cstr) 85353358Sdim return pos->value; 86314564Sdim return fail_value; 87314564Sdim } 88254721Semaste 89341825Sdim // Get a pointer to the first entry that matches "name". nullptr will be 90341825Sdim // returned if there is no entry that matches "name". 91314564Sdim // 92341825Sdim // The caller is responsible for ensuring that the collection does not change 93341825Sdim // during while using the returned pointer. 94321369Sdim const Entry *FindFirstValueForName(ConstString unique_cstr) const { 95353358Sdim auto pos = llvm::lower_bound(m_map, unique_cstr, Compare()); 96353358Sdim if (pos != m_map.end() && pos->cstring == unique_cstr) 97321369Sdim return &(*pos); 98314564Sdim return nullptr; 99314564Sdim } 100296417Sdim 101341825Sdim // Get a pointer to the next entry that matches "name" from a previously 102341825Sdim // returned Entry pointer. nullptr will be returned if there is no subsequent 103341825Sdim // entry that matches "name". 104314564Sdim // 105341825Sdim // The caller is responsible for ensuring that the collection does not change 106341825Sdim // during while using the returned pointer. 107314564Sdim const Entry *FindNextValueForName(const Entry *entry_ptr) const { 108314564Sdim if (!m_map.empty()) { 109314564Sdim const Entry *first_entry = &m_map[0]; 110314564Sdim const Entry *after_last_entry = first_entry + m_map.size(); 111314564Sdim const Entry *next_entry = entry_ptr + 1; 112314564Sdim if (first_entry <= next_entry && next_entry < after_last_entry) { 113314564Sdim if (next_entry->cstring == entry_ptr->cstring) 114314564Sdim return next_entry; 115314564Sdim } 116254721Semaste } 117314564Sdim return nullptr; 118314564Sdim } 119254721Semaste 120321369Sdim size_t GetValues(ConstString unique_cstr, std::vector<T> &values) const { 121314564Sdim const size_t start_size = values.size(); 122314564Sdim 123353358Sdim for (const Entry &entry : llvm::make_range(std::equal_range( 124353358Sdim m_map.begin(), m_map.end(), unique_cstr, Compare()))) 125353358Sdim values.push_back(entry.value); 126254721Semaste 127314564Sdim return values.size() - start_size; 128314564Sdim } 129254721Semaste 130314564Sdim size_t GetValues(const RegularExpression ®ex, 131314564Sdim std::vector<T> &values) const { 132314564Sdim const size_t start_size = values.size(); 133254721Semaste 134314564Sdim const_iterator pos, end = m_map.end(); 135314564Sdim for (pos = m_map.begin(); pos != end; ++pos) { 136321369Sdim if (regex.Execute(pos->cstring.GetCString())) 137314564Sdim values.push_back(pos->value); 138254721Semaste } 139254721Semaste 140314564Sdim return values.size() - start_size; 141314564Sdim } 142254721Semaste 143314564Sdim // Get the total number of entries in this map. 144314564Sdim size_t GetSize() const { return m_map.size(); } 145254721Semaste 146314564Sdim // Returns true if this map is empty. 147314564Sdim bool IsEmpty() const { return m_map.empty(); } 148254721Semaste 149341825Sdim // Reserve memory for at least "n" entries in the map. This is useful to call 150341825Sdim // when you know you will be adding a lot of entries using 151341825Sdim // UniqueCStringMap::Append() (which should be followed by a call to 152341825Sdim // UniqueCStringMap::Sort()) or to UniqueCStringMap::Insert(). 153314564Sdim void Reserve(size_t n) { m_map.reserve(n); } 154254721Semaste 155341825Sdim // Sort the unsorted contents in this map. A typical code flow would be: 156314564Sdim // size_t approximate_num_entries = .... 157314564Sdim // UniqueCStringMap<uint32_t> my_map; 158314564Sdim // my_map.Reserve (approximate_num_entries); 159314564Sdim // for (...) 160314564Sdim // { 161314564Sdim // my_map.Append (UniqueCStringMap::Entry(GetName(...), GetValue(...))); 162314564Sdim // } 163314564Sdim // my_map.Sort(); 164353358Sdim void Sort() { llvm::sort(m_map.begin(), m_map.end(), Compare()); } 165254721Semaste 166341825Sdim // Since we are using a vector to contain our items it will always double its 167341825Sdim // memory consumption as things are added to the vector, so if you intend to 168341825Sdim // keep a UniqueCStringMap around and have a lot of entries in the map, you 169341825Sdim // will want to call this function to create a new vector and copy _only_ the 170341825Sdim // exact size needed as part of the finalization of the string map. 171314564Sdim void SizeToFit() { 172314564Sdim if (m_map.size() < m_map.capacity()) { 173314564Sdim collection temp(m_map.begin(), m_map.end()); 174314564Sdim m_map.swap(temp); 175254721Semaste } 176314564Sdim } 177254721Semaste 178353358Sdimprotected: 179353358Sdim struct Compare { 180353358Sdim bool operator()(const Entry &lhs, const Entry &rhs) { 181353358Sdim return operator()(lhs.cstring, rhs.cstring); 182254721Semaste } 183296417Sdim 184353358Sdim bool operator()(const Entry &lhs, ConstString rhs) { 185353358Sdim return operator()(lhs.cstring, rhs); 186353358Sdim } 187353358Sdim 188353358Sdim bool operator()(ConstString lhs, const Entry &rhs) { 189353358Sdim return operator()(lhs, rhs.cstring); 190353358Sdim } 191353358Sdim 192353358Sdim // This is only for uniqueness, not lexicographical ordering, so we can 193353358Sdim // just compare pointers. *However*, comparing pointers from different 194353358Sdim // allocations is UB, so we need compare their integral values instead. 195353358Sdim bool operator()(ConstString lhs, ConstString rhs) { 196353358Sdim return uintptr_t(lhs.GetCString()) < uintptr_t(rhs.GetCString()); 197353358Sdim } 198353358Sdim }; 199314564Sdim typedef std::vector<Entry> collection; 200314564Sdim typedef typename collection::iterator iterator; 201314564Sdim typedef typename collection::const_iterator const_iterator; 202314564Sdim collection m_map; 203254721Semaste}; 204254721Semaste 205254721Semaste} // namespace lldb_private 206254721Semaste 207296417Sdim#endif // liblldb_UniqueCStringMap_h_ 208