This revision was automatically updated to reflect the committed changes. Closed by commit rL363357: Make UniqueCStringMap work with non-default-constructible types and other… (authored by labath, committed by ). Herald added a project: LLVM. Herald added a subscriber: llvm-commits.
Changed prior to commit: https://reviews.llvm.org/D63268?vs=204537&id=204707#toc Repository: rL LLVM CHANGES SINCE LAST ACTION https://reviews.llvm.org/D63268/new/ https://reviews.llvm.org/D63268 Files: lldb/trunk/include/lldb/Core/UniqueCStringMap.h lldb/trunk/include/lldb/Symbol/Symtab.h lldb/trunk/source/Symbol/Symtab.cpp lldb/trunk/unittests/Core/CMakeLists.txt lldb/trunk/unittests/Core/UniqueCStringMapTest.cpp
Index: lldb/trunk/unittests/Core/UniqueCStringMapTest.cpp =================================================================== --- lldb/trunk/unittests/Core/UniqueCStringMapTest.cpp +++ lldb/trunk/unittests/Core/UniqueCStringMapTest.cpp @@ -0,0 +1,53 @@ +//===-- UniqueCStringMapTest.cpp --------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "lldb/Core/UniqueCStringMap.h" +#include "gmock/gmock.h" + +using namespace lldb_private; + +namespace { +struct NoDefault { + int x; + + NoDefault(int x) : x(x) {} + NoDefault() = delete; + + friend bool operator==(NoDefault lhs, NoDefault rhs) { + return lhs.x == rhs.x; + } + + friend llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, + NoDefault x) { + return OS << "NoDefault{" << x.x << "}"; + } +}; +} // namespace + +TEST(UniqueCStringMap, NoDefaultConstructor) { + using MapT = UniqueCStringMap<NoDefault>; + using EntryT = MapT::Entry; + + MapT Map; + ConstString Foo("foo"), Bar("bar"); + + Map.Append(Foo, NoDefault(42)); + EXPECT_THAT(Map.Find(Foo, NoDefault(47)), NoDefault(42)); + EXPECT_THAT(Map.Find(Bar, NoDefault(47)), NoDefault(47)); + EXPECT_THAT(Map.FindFirstValueForName(Foo), + testing::Pointee(testing::Field(&EntryT::value, NoDefault(42)))); + EXPECT_THAT(Map.FindFirstValueForName(Bar), nullptr); + + std::vector<NoDefault> Values; + EXPECT_THAT(Map.GetValues(Foo, Values), 1); + EXPECT_THAT(Values, testing::ElementsAre(NoDefault(42))); + + Values.clear(); + EXPECT_THAT(Map.GetValues(Bar, Values), 0); + EXPECT_THAT(Values, testing::IsEmpty()); +} Index: lldb/trunk/unittests/Core/CMakeLists.txt =================================================================== --- lldb/trunk/unittests/Core/CMakeLists.txt +++ lldb/trunk/unittests/Core/CMakeLists.txt @@ -2,6 +2,7 @@ MangledTest.cpp RichManglingContextTest.cpp StreamCallbackTest.cpp + UniqueCStringMapTest.cpp LINK_LIBS lldbCore Index: lldb/trunk/source/Symbol/Symtab.cpp =================================================================== --- lldb/trunk/source/Symbol/Symtab.cpp +++ lldb/trunk/source/Symbol/Symtab.cpp @@ -288,10 +288,8 @@ // Instantiation of the demangler is expensive, so better use a single one // for all entries during batch processing. RichManglingContext rmc; - NameToIndexMap::Entry entry; - - for (entry.value = 0; entry.value < num_symbols; ++entry.value) { - Symbol *symbol = &m_symbols[entry.value]; + for (uint32_t value = 0; value < num_symbols; ++value) { + Symbol *symbol = &m_symbols[value]; // Don't let trampolines get into the lookup by name map If we ever need // the trampoline symbols to be searchable by name we can remove this and @@ -303,52 +301,46 @@ // If the symbol's name string matched a Mangled::ManglingScheme, it is // stored in the mangled field. Mangled &mangled = symbol->GetMangled(); - entry.cstring = mangled.GetMangledName(); - if (entry.cstring) { - m_name_to_index.Append(entry); + if (ConstString name = mangled.GetMangledName()) { + m_name_to_index.Append(name, value); if (symbol->ContainsLinkerAnnotations()) { // If the symbol has linker annotations, also add the version without // the annotations. - entry.cstring = ConstString(m_objfile->StripLinkerSymbolAnnotations( - entry.cstring.GetStringRef())); - m_name_to_index.Append(entry); + ConstString stripped = ConstString( + m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef())); + m_name_to_index.Append(stripped, value); } const SymbolType type = symbol->GetType(); if (type == eSymbolTypeCode || type == eSymbolTypeResolver) { if (mangled.DemangleWithRichManglingInfo(rmc, lldb_skip_name)) - RegisterMangledNameEntry(entry, class_contexts, backlog, rmc); + RegisterMangledNameEntry(value, class_contexts, backlog, rmc); } } // Symbol name strings that didn't match a Mangled::ManglingScheme, are // stored in the demangled field. - entry.cstring = mangled.GetDemangledName(symbol->GetLanguage()); - if (entry.cstring) { - m_name_to_index.Append(entry); + if (ConstString name = mangled.GetDemangledName(symbol->GetLanguage())) { + m_name_to_index.Append(name, value); if (symbol->ContainsLinkerAnnotations()) { // If the symbol has linker annotations, also add the version without // the annotations. - entry.cstring = ConstString(m_objfile->StripLinkerSymbolAnnotations( - entry.cstring.GetStringRef())); - m_name_to_index.Append(entry); + name = ConstString( + m_objfile->StripLinkerSymbolAnnotations(name.GetStringRef())); + m_name_to_index.Append(name, value); } - } - // If the demangled name turns out to be an ObjC name, and is a category - // name, add the version without categories to the index too. - ObjCLanguage::MethodName objc_method(entry.cstring.GetStringRef(), true); - if (objc_method.IsValid(true)) { - entry.cstring = objc_method.GetSelector(); - m_selector_to_index.Append(entry); - - ConstString objc_method_no_category( - objc_method.GetFullNameWithoutCategory(true)); - if (objc_method_no_category) { - entry.cstring = objc_method_no_category; - m_name_to_index.Append(entry); + // If the demangled name turns out to be an ObjC name, and is a category + // name, add the version without categories to the index too. + ObjCLanguage::MethodName objc_method(name.GetStringRef(), true); + if (objc_method.IsValid(true)) { + m_selector_to_index.Append(objc_method.GetSelector(), value); + + if (ConstString objc_method_no_category = + objc_method.GetFullNameWithoutCategory(true)) + m_name_to_index.Append(objc_method_no_category, value); } } } @@ -369,7 +361,7 @@ } void Symtab::RegisterMangledNameEntry( - NameToIndexMap::Entry &entry, std::set<const char *> &class_contexts, + uint32_t value, std::set<const char *> &class_contexts, std::vector<std::pair<NameToIndexMap::Entry, const char *>> &backlog, RichManglingContext &rmc) { // Only register functions that have a base name. @@ -379,7 +371,7 @@ return; // The base name will be our entry's name. - entry.cstring = ConstString(base_name); + NameToIndexMap::Entry entry(ConstString(base_name), value); rmc.ParseFunctionDeclContextName(); llvm::StringRef decl_context = rmc.GetBufferRef(); @@ -447,24 +439,21 @@ std::lock_guard<std::recursive_mutex> guard(m_mutex); // Create the name index vector to be able to quickly search by name - NameToIndexMap::Entry entry; const size_t num_indexes = indexes.size(); for (size_t i = 0; i < num_indexes; ++i) { - entry.value = indexes[i]; + uint32_t value = indexes[i]; assert(i < m_symbols.size()); - const Symbol *symbol = &m_symbols[entry.value]; + const Symbol *symbol = &m_symbols[value]; const Mangled &mangled = symbol->GetMangled(); if (add_demangled) { - entry.cstring = mangled.GetDemangledName(symbol->GetLanguage()); - if (entry.cstring) - name_to_index_map.Append(entry); + if (ConstString name = mangled.GetDemangledName(symbol->GetLanguage())) + name_to_index_map.Append(name, value); } if (add_mangled) { - entry.cstring = mangled.GetMangledName(); - if (entry.cstring) - name_to_index_map.Append(entry); + if (ConstString name = mangled.GetMangledName()) + name_to_index_map.Append(name, value); } } } Index: lldb/trunk/include/lldb/Symbol/Symtab.h =================================================================== --- lldb/trunk/include/lldb/Symbol/Symtab.h +++ lldb/trunk/include/lldb/Symbol/Symtab.h @@ -190,7 +190,7 @@ SymbolContextList &sc_list); void RegisterMangledNameEntry( - NameToIndexMap::Entry &entry, std::set<const char *> &class_contexts, + uint32_t value, std::set<const char *> &class_contexts, std::vector<std::pair<NameToIndexMap::Entry, const char *>> &backlog, RichManglingContext &rmc); Index: lldb/trunk/include/lldb/Core/UniqueCStringMap.h =================================================================== --- lldb/trunk/include/lldb/Core/UniqueCStringMap.h +++ lldb/trunk/include/lldb/Core/UniqueCStringMap.h @@ -26,16 +26,10 @@ template <typename T> class UniqueCStringMap { public: struct Entry { - Entry() {} - - Entry(ConstString cstr) : cstring(cstr), value() {} - Entry(ConstString cstr, const T &v) : cstring(cstr), value(v) {} - // This is only for uniqueness, not lexicographical ordering, so we can - // just compare pointers. - bool operator<(const Entry &rhs) const { - return cstring.GetCString() < rhs.cstring.GetCString(); + friend bool operator<(const Entry &lhs, const Entry &rhs) { + return Compare()(lhs, rhs); } ConstString cstring; @@ -53,17 +47,6 @@ void Clear() { m_map.clear(); } - // Call this function to always keep the map sorted when putting entries into - // the map. - void Insert(ConstString unique_cstr, const T &value) { - typename UniqueCStringMap<T>::Entry e(unique_cstr, value); - m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e); - } - - void Insert(const Entry &e) { - m_map.insert(std::upper_bound(m_map.begin(), m_map.end(), e), e); - } - // Get an entries by index in a variety of forms. // // The caller is responsible for ensuring that the collection does not change @@ -101,13 +84,9 @@ // T values and only if there is a sensible failure value that can // be returned and that won't match any existing values. T Find(ConstString unique_cstr, T fail_value) const { - Entry search_entry(unique_cstr); - const_iterator end = m_map.end(); - const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry); - if (pos != end) { - if (pos->cstring == unique_cstr) - return pos->value; - } + auto pos = llvm::lower_bound(m_map, unique_cstr, Compare()); + if (pos != m_map.end() && pos->cstring == unique_cstr) + return pos->value; return fail_value; } @@ -117,10 +96,8 @@ // The caller is responsible for ensuring that the collection does not change // during while using the returned pointer. const Entry *FindFirstValueForName(ConstString unique_cstr) const { - Entry search_entry(unique_cstr); - const_iterator end = m_map.end(); - const_iterator pos = std::lower_bound(m_map.begin(), end, search_entry); - if (pos != end && pos->cstring == unique_cstr) + auto pos = llvm::lower_bound(m_map, unique_cstr, Compare()); + if (pos != m_map.end() && pos->cstring == unique_cstr) return &(*pos); return nullptr; } @@ -147,15 +124,9 @@ size_t GetValues(ConstString unique_cstr, std::vector<T> &values) const { const size_t start_size = values.size(); - Entry search_entry(unique_cstr); - const_iterator pos, end = m_map.end(); - for (pos = std::lower_bound(m_map.begin(), end, search_entry); pos != end; - ++pos) { - if (pos->cstring == unique_cstr) - values.push_back(pos->value); - else - break; - } + for (const Entry &entry : llvm::make_range(std::equal_range( + m_map.begin(), m_map.end(), unique_cstr, Compare()))) + values.push_back(entry.value); return values.size() - start_size; } @@ -208,28 +179,27 @@ } } - size_t Erase(ConstString unique_cstr) { - size_t num_removed = 0; - Entry search_entry(unique_cstr); - iterator end = m_map.end(); - iterator begin = m_map.begin(); - iterator lower_pos = std::lower_bound(begin, end, search_entry); - if (lower_pos != end) { - if (lower_pos->cstring == unique_cstr) { - iterator upper_pos = std::upper_bound(lower_pos, end, search_entry); - if (lower_pos == upper_pos) { - m_map.erase(lower_pos); - num_removed = 1; - } else { - num_removed = std::distance(lower_pos, upper_pos); - m_map.erase(lower_pos, upper_pos); - } - } +protected: + struct Compare { + bool operator()(const Entry &lhs, const Entry &rhs) { + return operator()(lhs.cstring, rhs.cstring); } - return num_removed; - } -protected: + bool operator()(const Entry &lhs, ConstString rhs) { + return operator()(lhs.cstring, rhs); + } + + bool operator()(ConstString lhs, const Entry &rhs) { + return operator()(lhs, rhs.cstring); + } + + // This is only for uniqueness, not lexicographical ordering, so we can + // just compare pointers. *However*, comparing pointers from different + // allocations is UB, so we need compare their integral values instead. + bool operator()(ConstString lhs, ConstString rhs) { + return uintptr_t(lhs.GetCString()) < uintptr_t(rhs.GetCString()); + } + }; typedef std::vector<Entry> collection; typedef typename collection::iterator iterator; typedef typename collection::const_iterator const_iterator;
_______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
