labath created this revision.
labath added reviewers: clayborg, teemperor, tberghammer.
Herald added subscribers: JDevlieghere, mgorny.
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 <https://reviews.llvm.org/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.
https://reviews.llvm.org/D56170
Files:
include/lldb/Core/RangeMap.h
include/lldb/Symbol/DWARFCallFrameInfo.h
include/lldb/Symbol/LineTable.h
include/lldb/Symbol/Symtab.h
source/Plugins/Process/elf-core/ProcessElfCore.h
source/Plugins/Process/mach-core/ProcessMachCore.h
source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h
source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h
unittests/Core/CMakeLists.txt
unittests/Core/RangeMapTest.cpp
Index: unittests/Core/RangeMapTest.cpp
===================================================================
--- /dev/null
+++ unittests/Core/RangeMapTest.cpp
@@ -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, 0>;
+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);
+}
Index: unittests/Core/CMakeLists.txt
===================================================================
--- unittests/Core/CMakeLists.txt
+++ unittests/Core/CMakeLists.txt
@@ -1,5 +1,6 @@
add_lldb_unittest(LLDBCoreTests
MangledTest.cpp
+ RangeMapTest.cpp
RangeTest.cpp
RichManglingContextTest.cpp
StreamCallbackTest.cpp
Index: source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h
===================================================================
--- source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h
+++ source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h
@@ -156,7 +156,7 @@
typedef std::shared_ptr<OSOInfo> OSOInfoSP;
typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t,
- lldb::addr_t>
+ lldb::addr_t, 0>
FileRangeMap;
//------------------------------------------------------------------
@@ -299,7 +299,7 @@
lldb::addr_t m_oso_file_addr;
};
- typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, OSOEntry>
+ typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, OSOEntry, 0>
DebugMap;
//------------------------------------------------------------------
Index: source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
===================================================================
--- source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
+++ source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
@@ -440,7 +440,7 @@
TypeSet &type_set);
typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t,
- lldb_private::Variable *>
+ lldb_private::Variable *, 0>
GlobalVariableMap;
GlobalVariableMap &GetGlobalAranges();
Index: source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h
===================================================================
--- source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h
+++ source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h
@@ -19,7 +19,7 @@
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, 1>
RangeToDIE;
public:
Index: source/Plugins/Process/mach-core/ProcessMachCore.h
===================================================================
--- source/Plugins/Process/mach-core/ProcessMachCore.h
+++ source/Plugins/Process/mach-core/ProcessMachCore.h
@@ -130,9 +130,10 @@
// For ProcessMachCore only
//------------------------------------------------------------------
typedef lldb_private::Range<lldb::addr_t, lldb::addr_t> FileRange;
- typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, FileRange>
+ typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, FileRange,
+ 0>
VMRangeToFileOffset;
- typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t>
+ typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t, 0>
VMRangeToPermissions;
VMRangeToFileOffset m_core_aranges;
Index: source/Plugins/Process/elf-core/ProcessElfCore.h
===================================================================
--- source/Plugins/Process/elf-core/ProcessElfCore.h
+++ source/Plugins/Process/elf-core/ProcessElfCore.h
@@ -136,9 +136,10 @@
// 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,
+ 0>
VMRangeToFileOffset;
- typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t>
+ typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t, 0>
VMRangeToPermissions;
lldb::ModuleSP m_core_module_sp;
Index: include/lldb/Symbol/Symtab.h
===================================================================
--- include/lldb/Symbol/Symtab.h
+++ include/lldb/Symbol/Symtab.h
@@ -147,7 +147,7 @@
typedef std::vector<Symbol> collection;
typedef collection::iterator iterator;
typedef collection::const_iterator const_iterator;
- typedef RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t>
+ typedef RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t, 0>
FileRangeToIndexMap;
void InitNameIndexes();
void InitAddressIndexes();
Index: include/lldb/Symbol/LineTable.h
===================================================================
--- include/lldb/Symbol/LineTable.h
+++ include/lldb/Symbol/LineTable.h
@@ -230,7 +230,7 @@
/// A new line table if at least one line table entry was able
/// to be mapped.
//------------------------------------------------------------------
- typedef RangeDataVector<lldb::addr_t, lldb::addr_t, lldb::addr_t>
+ typedef RangeDataVector<lldb::addr_t, lldb::addr_t, lldb::addr_t, 0>
FileRangeMap;
LineTable *LinkLineTable(const FileRangeMap &file_range_map);
Index: include/lldb/Symbol/DWARFCallFrameInfo.h
===================================================================
--- include/lldb/Symbol/DWARFCallFrameInfo.h
+++ include/lldb/Symbol/DWARFCallFrameInfo.h
@@ -114,7 +114,7 @@
// Start address (file address), size, offset of FDE location used for
// finding an FDE for a given File address; the start address field is an
// offset into an individual Module.
- typedef RangeDataVector<lldb::addr_t, uint32_t, dw_offset_t> FDEEntryMap;
+ typedef RangeDataVector<lldb::addr_t, uint32_t, dw_offset_t, 0> FDEEntryMap;
bool IsEHFrame() const;
Index: include/lldb/Core/RangeMap.h
===================================================================
--- include/lldb/Core/RangeMap.h
+++ include/lldb/Core/RangeMap.h
@@ -633,201 +633,12 @@
}
};
-template <typename B, typename S, typename T, unsigned N> class RangeDataArray {
+template <typename B, typename S, typename T, unsigned N>
+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 @@
}
}
- // 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 @@
}
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,16 @@
}
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;
+ Entry entry;
+ entry.SetRangeBase(addr);
+ entry.SetByteSize(1);
+ return FindEntryThatContains(entry);
}
const Entry *FindEntryThatContains(const Entry &range) const {
_______________________________________________
lldb-commits mailing list
lldb-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
