Author: Pavel Labath Date: 2020-07-27T10:06:56+02:00 New Revision: 81d7ebaf5c369d42b77f9e3e47e2ac22c306ec04
URL: https://github.com/llvm/llvm-project/commit/81d7ebaf5c369d42b77f9e3e47e2ac22c306ec04 DIFF: https://github.com/llvm/llvm-project/commit/81d7ebaf5c369d42b77f9e3e47e2ac22c306ec04.diff LOG: [lldb/Utility] Fix a bug in RangeMap::CombineConsecutiveRanges The function didn't combine a large entry which overlapped several other entries, if those other entries were not overlapping among each other. E.g., (0,20),(5,6),(10,11) produced (0,20),(10,11) Now it just produced (0,20). Added: Modified: lldb/include/lldb/Utility/RangeMap.h lldb/unittests/Utility/RangeMapTest.cpp Removed: ################################################################################ diff --git a/lldb/include/lldb/Utility/RangeMap.h b/lldb/include/lldb/Utility/RangeMap.h index fb24c5a43479..118fdfd85fa9 100644 --- a/lldb/include/lldb/Utility/RangeMap.h +++ b/lldb/include/lldb/Utility/RangeMap.h @@ -194,41 +194,25 @@ template <typename B, typename S, unsigned N = 0> class RangeVector { #ifdef ASSERT_RANGEMAP_ARE_SORTED assert(IsSorted()); #endif - // Can't combine if ranges if we have zero or one range - if (m_entries.size() > 1) { - // The list should be sorted prior to calling this function - 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->DoesAdjoinOrIntersect(*pos)) { - can_combine = true; - break; - } - } + auto first_intersect = std::adjacent_find( + m_entries.begin(), m_entries.end(), [](const Entry &a, const Entry &b) { + return a.DoesAdjoinOrIntersect(b); + }); + if (first_intersect == m_entries.end()) + return; - // 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->DoesAdjoinOrIntersect(*pos)) - minimal_ranges.back().SetRangeEnd( - std::max<BaseType>(prev->GetRangeEnd(), 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); - } + // We we can combine at least one entry, then we make a new collection and + // populate it accordingly, and then swap it into place. + auto pos = std::next(first_intersect); + Collection minimal_ranges(m_entries.begin(), pos); + for (; pos != m_entries.end(); ++pos) { + Entry &back = minimal_ranges.back(); + if (back.DoesAdjoinOrIntersect(*pos)) + back.SetRangeEnd(std::max(back.GetRangeEnd(), pos->GetRangeEnd())); + else + minimal_ranges.push_back(*pos); } + m_entries.swap(minimal_ranges); } BaseType GetMinRangeBase(BaseType fail_value) const { @@ -353,6 +337,10 @@ template <typename B, typename S, unsigned N = 0> class RangeVector { return nullptr; } + using const_iterator = typename Collection::const_iterator; + const_iterator begin() const { return m_entries.begin(); } + const_iterator end() const { return m_entries.end(); } + protected: void CombinePrevAndNext(typename Collection::iterator pos) { // Check if the prev or next entries in case they need to be unioned with diff --git a/lldb/unittests/Utility/RangeMapTest.cpp b/lldb/unittests/Utility/RangeMapTest.cpp index 8a243b656218..97432dca983d 100644 --- a/lldb/unittests/Utility/RangeMapTest.cpp +++ b/lldb/unittests/Utility/RangeMapTest.cpp @@ -12,6 +12,32 @@ using namespace lldb_private; +TEST(RangeVector, CombineConsecutiveRanges) { + using RangeVector = RangeVector<uint32_t, uint32_t>; + using Entry = RangeVector::Entry; + + RangeVector V; + V.Append(0, 1); + V.Append(5, 1); + V.Append(6, 1); + V.Append(10, 9); + V.Append(15, 1); + V.Append(20, 9); + V.Append(21, 9); + V.Sort(); + V.CombineConsecutiveRanges(); + EXPECT_THAT(V, testing::ElementsAre(Entry(0, 1), Entry(5, 2), Entry(10, 9), + Entry(20, 10))); + + V.Clear(); + V.Append(0, 20); + V.Append(5, 1); + V.Append(10, 1); + V.Sort(); + V.CombineConsecutiveRanges(); + EXPECT_THAT(V, testing::ElementsAre(Entry(0, 20))); +} + using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>; using EntryT = RangeDataVectorT::Entry; _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
