Author: labath Date: Thu Jan 3 23:14:17 2019 New Revision: 350380 URL: http://llvm.org/viewvc/llvm-project?rev=350380&view=rev Log: RangeMap.h: merge RangeDataArray and RangeDataVector
Summary: The main difference between the classes was supposed to be the fact that one is backed by llvm::SmallVector, and the other by std::vector. However, over the years, they have accumulated various other differences too. This essentially removes the std::vector version, as that is pretty much identical to llvm::SmallVector<T, 0>, and combines their interfaces. It does not attempt to do a more significant refactoring, even though there is still a lot of duplication in this file, as it is hard to tell which quirk of some API is depended on by somebody (and, a previous, more ambitious attempt at this in D16769 has failed). I also add some tests, including one which demonstrates one of the quirks/bugs of the API I have noticed in the process. Reviewers: clayborg, teemperor, tberghammer Subscribers: mgorny, JDevlieghere, lldb-commits Differential Revision: https://reviews.llvm.org/D56170 Added: lldb/trunk/unittests/Core/RangeMapTest.cpp Modified: lldb/trunk/include/lldb/Core/RangeMap.h lldb/trunk/source/Plugins/Process/elf-core/ProcessElfCore.h lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h lldb/trunk/unittests/Core/CMakeLists.txt Modified: lldb/trunk/include/lldb/Core/RangeMap.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Core/RangeMap.h?rev=350380&r1=350379&r2=350380&view=diff ============================================================================== --- lldb/trunk/include/lldb/Core/RangeMap.h (original) +++ lldb/trunk/include/lldb/Core/RangeMap.h Thu Jan 3 23:14:17 2019 @@ -633,201 +633,12 @@ struct RangeData : public Range<B, S> { } }; -template <typename B, typename S, typename T, unsigned N> class RangeDataArray { +template <typename B, typename S, typename T, unsigned N = 0> +class RangeDataVector { public: typedef RangeData<B, S, T> Entry; typedef llvm::SmallVector<Entry, N> Collection; - RangeDataArray() = default; - - ~RangeDataArray() = default; - - void Append(const Entry &entry) { m_entries.push_back(entry); } - - void Sort() { - if (m_entries.size() > 1) - std::stable_sort(m_entries.begin(), m_entries.end()); - } - -#ifdef ASSERT_RANGEMAP_ARE_SORTED - bool IsSorted() const { - typename Collection::const_iterator pos, end, prev; - // First we determine if we can combine any of the Entry objects so we - // don't end up allocating and making a new collection for no reason - for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; - prev = pos++) { - if (prev != end && *pos < *prev) - return false; - } - return true; - } -#endif - - void CombineConsecutiveEntriesWithEqualData() { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - typename Collection::iterator pos; - typename Collection::iterator end; - typename Collection::iterator prev; - bool can_combine = false; - // First we determine if we can combine any of the Entry objects so we - // don't end up allocating and making a new collection for no reason - for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; - prev = pos++) { - if (prev != end && prev->data == pos->data) { - can_combine = true; - break; - } - } - - // We we can combine at least one entry, then we make a new collection and - // populate it accordingly, and then swap it into place. - if (can_combine) { - Collection minimal_ranges; - for (pos = m_entries.begin(), end = m_entries.end(), prev = end; - pos != end; prev = pos++) { - if (prev != end && prev->data == pos->data) - minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd()); - else - minimal_ranges.push_back(*pos); - } - // Use the swap technique in case our new vector is much smaller. We must - // swap when using the STL because std::vector objects never release or - // reduce the memory once it has been allocated/reserved. - m_entries.swap(minimal_ranges); - } - } - - void Clear() { m_entries.clear(); } - - bool IsEmpty() const { return m_entries.empty(); } - - size_t GetSize() const { return m_entries.size(); } - - const Entry *GetEntryAtIndex(size_t i) const { - return ((i < m_entries.size()) ? &m_entries[i] : nullptr); - } - - // Clients must ensure that "i" is a valid index prior to calling this - // function - const Entry &GetEntryRef(size_t i) const { return m_entries[i]; } - - static bool BaseLessThan(const Entry &lhs, const Entry &rhs) { - return lhs.GetRangeBase() < rhs.GetRangeBase(); - } - - uint32_t FindEntryIndexThatContains(B addr) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry(addr, 1); - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, entry, BaseLessThan); - - if (pos != end && pos->Contains(addr)) { - return std::distance(begin, pos); - } else if (pos != begin) { - --pos; - if (pos->Contains(addr)) - return std::distance(begin, pos); - } - } - return UINT32_MAX; - } - - Entry *FindEntryThatContains(B addr) { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry; - entry.SetRangeBase(addr); - entry.SetByteSize(1); - typename Collection::iterator begin = m_entries.begin(); - typename Collection::iterator end = m_entries.end(); - typename Collection::iterator pos = - std::lower_bound(begin, end, entry, BaseLessThan); - - if (pos != end && pos->Contains(addr)) { - return &(*pos); - } else if (pos != begin) { - --pos; - if (pos->Contains(addr)) { - return &(*pos); - } - } - } - return nullptr; - } - - const Entry *FindEntryThatContains(B addr) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry; - entry.SetRangeBase(addr); - entry.SetByteSize(1); - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, entry, BaseLessThan); - - if (pos != end && pos->Contains(addr)) { - return &(*pos); - } else if (pos != begin) { - --pos; - if (pos->Contains(addr)) { - return &(*pos); - } - } - } - return nullptr; - } - - const Entry *FindEntryThatContains(const Entry &range) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, range, BaseLessThan); - - if (pos != end && pos->Contains(range)) { - return &(*pos); - } else if (pos != begin) { - --pos; - if (pos->Contains(range)) { - return &(*pos); - } - } - } - return nullptr; - } - - Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); } - - const Entry *Back() const { - return (m_entries.empty() ? nullptr : &m_entries.back()); - } - -protected: - Collection m_entries; -}; - -// Same as RangeDataArray, but uses std::vector as to not require static -// storage of N items in the class itself -template <typename B, typename S, typename T> class RangeDataVector { -public: - typedef RangeData<B, S, T> Entry; - typedef std::vector<Entry> Collection; - RangeDataVector() = default; ~RangeDataVector() = default; @@ -889,38 +700,8 @@ public: } } - // Calculate the byte size of ranges with zero byte sizes by finding the next - // entry with a base address > the current base address - void CalculateSizesOfZeroByteSizeRanges(S full_size = 0) { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - typename Collection::iterator pos; - typename Collection::iterator end; - typename Collection::iterator next; - for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) { - if (pos->GetByteSize() == 0) { - // Watch out for multiple entries with same address and make sure we - // find an entry that is greater than the current base address before - // we use that for the size - auto curr_base = pos->GetRangeBase(); - for (next = pos + 1; next != end; ++next) { - auto next_base = next->GetRangeBase(); - if (next_base > curr_base) { - pos->SetByteSize(next_base - curr_base); - break; - } - } - if (next == end && full_size > curr_base) - pos->SetByteSize(full_size - curr_base); - } - } - } - void Clear() { m_entries.clear(); } - void Reserve(typename Collection::size_type size) { m_entries.resize(size); } - bool IsEmpty() const { return m_entries.empty(); } size_t GetSize() const { return m_entries.size(); } @@ -942,22 +723,9 @@ public: } uint32_t FindEntryIndexThatContains(B addr) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry(addr, 1); - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, entry, BaseLessThan); - - while (pos != begin && pos[-1].Contains(addr)) - --pos; - - if (pos != end && pos->Contains(addr)) - return std::distance(begin, pos); - } + const Entry *entry = FindEntryThatContains(addr); + if (entry) + return std::distance(m_entries.begin(), entry); return UINT32_MAX; } @@ -977,47 +745,13 @@ public: } Entry *FindEntryThatContains(B addr) { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry; - entry.SetRangeBase(addr); - entry.SetByteSize(1); - typename Collection::iterator begin = m_entries.begin(); - typename Collection::iterator end = m_entries.end(); - typename Collection::iterator pos = - std::lower_bound(begin, end, entry, BaseLessThan); - - while (pos != begin && pos[-1].Contains(addr)) - --pos; - - if (pos != end && pos->Contains(addr)) - return &(*pos); - } - return nullptr; + return const_cast<Entry *>( + static_cast<const RangeDataVector *>(this)->FindEntryThatContains( + addr)); } const Entry *FindEntryThatContains(B addr) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry; - entry.SetRangeBase(addr); - entry.SetByteSize(1); - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, entry, BaseLessThan); - - while (pos != begin && pos[-1].Contains(addr)) - --pos; - - if (pos != end && pos->Contains(addr)) - return &(*pos); - } - return nullptr; + return FindEntryThatContains(Entry(addr, 1)); } const Entry *FindEntryThatContains(const Entry &range) const { Modified: lldb/trunk/source/Plugins/Process/elf-core/ProcessElfCore.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/Process/elf-core/ProcessElfCore.h?rev=350380&r1=350379&r2=350380&view=diff ============================================================================== --- lldb/trunk/source/Plugins/Process/elf-core/ProcessElfCore.h (original) +++ lldb/trunk/source/Plugins/Process/elf-core/ProcessElfCore.h Thu Jan 3 23:14:17 2019 @@ -136,7 +136,7 @@ private: // For ProcessElfCore only //------------------------------------------------------------------ typedef lldb_private::Range<lldb::addr_t, lldb::addr_t> FileRange; - typedef lldb_private::RangeDataArray<lldb::addr_t, lldb::addr_t, FileRange, 1> + typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, FileRange> VMRangeToFileOffset; typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t> VMRangeToPermissions; Modified: lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h?rev=350380&r1=350379&r2=350380&view=diff ============================================================================== --- lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h (original) +++ lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h Thu Jan 3 23:14:17 2019 @@ -19,7 +19,7 @@ class SymbolFileDWARF; class DWARFDebugAranges { protected: - typedef lldb_private::RangeDataArray<dw_addr_t, uint32_t, dw_offset_t, 1> + typedef lldb_private::RangeDataVector<dw_addr_t, uint32_t, dw_offset_t> RangeToDIE; public: Modified: lldb/trunk/unittests/Core/CMakeLists.txt URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/unittests/Core/CMakeLists.txt?rev=350380&r1=350379&r2=350380&view=diff ============================================================================== --- lldb/trunk/unittests/Core/CMakeLists.txt (original) +++ lldb/trunk/unittests/Core/CMakeLists.txt Thu Jan 3 23:14:17 2019 @@ -1,5 +1,6 @@ add_lldb_unittest(LLDBCoreTests MangledTest.cpp + RangeMapTest.cpp RangeTest.cpp RichManglingContextTest.cpp StreamCallbackTest.cpp Added: lldb/trunk/unittests/Core/RangeMapTest.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/unittests/Core/RangeMapTest.cpp?rev=350380&view=auto ============================================================================== --- lldb/trunk/unittests/Core/RangeMapTest.cpp (added) +++ lldb/trunk/unittests/Core/RangeMapTest.cpp Thu Jan 3 23:14:17 2019 @@ -0,0 +1,55 @@ +//===-- RangeTest.cpp ----------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "lldb/Core/RangeMap.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +using namespace lldb_private; + +using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>; +using EntryT = RangeDataVectorT::Entry; + +static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) { + return testing::Pointee(testing::Field(&EntryT::data, ID)); +} + +TEST(RangeDataVector, FindEntryThatContains) { + RangeDataVectorT Map; + uint32_t NextID = 0; + Map.Append(EntryT(0, 10, NextID++)); + Map.Append(EntryT(10, 10, NextID++)); + Map.Append(EntryT(20, 10, NextID++)); + Map.Sort(); + + EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0)); + EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0)); + EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1)); + EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1)); + EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2)); + EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2)); + EXPECT_THAT(Map.FindEntryThatContains(30), nullptr); +} + +TEST(RangeDataVector, FindEntryThatContains_Overlap) { + RangeDataVectorT Map; + uint32_t NextID = 0; + Map.Append(EntryT(0, 40, NextID++)); + Map.Append(EntryT(10, 20, NextID++)); + Map.Append(EntryT(20, 10, NextID++)); + Map.Sort(); + + // With overlapping intervals, the intention seems to be to return the first + // interval which contains the address. + EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0)); + + // However, this does not always succeed. + // TODO: This should probably return the range (0, 40) as well. + EXPECT_THAT(Map.FindEntryThatContains(35), nullptr); +} _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
