From 015b0cc2582924075ca5b6215da664477cf76fff Mon Sep 17 00:00:00 2001 From: Todd Fiala Date: Tue, 2 Feb 2016 20:26:50 +0000 Subject: [PATCH] Revert "[NFC] Cleanup RangeMap.h" This reverts commit r259538. Caused 92 test failures on the OS X testbot. llvm-svn: 259556 --- lldb/include/lldb/Core/RangeMap.h | 1790 +++++++++++++++----- .../Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp | 175 -- 2 files changed, 1382 insertions(+), 583 deletions(-) diff --git a/lldb/include/lldb/Core/RangeMap.h b/lldb/include/lldb/Core/RangeMap.h index 75c37ac..28d3083 100644 --- a/lldb/include/lldb/Core/RangeMap.h +++ b/lldb/include/lldb/Core/RangeMap.h @@ -24,504 +24,1478 @@ // Uncomment to make sure all Range objects are sorted when needed //#define ASSERT_RANGEMAP_ARE_SORTED -namespace lldb_private -{ - -//---------------------------------------------------------------------- -// A simple range class where you get to define the type of the range -// base "B", and the type used for the range byte size "S". -//---------------------------------------------------------------------- -template struct Range -{ - typedef B BaseType; - typedef S SizeType; - - BaseType base; - SizeType size; - - Range() : base(0), size(0) {} - - Range(BaseType b, SizeType s) : base(b), size(s) {} - - void - Clear(BaseType b = 0) - { - base = b; - size = 0; - } - - BaseType - GetRangeBase() const - { - return base; - } - - void - SetRangeBase(BaseType b) - { - base = b; - } - - void - Slide(BaseType slide) - { - base += slide; - } - - BaseType - GetRangeEnd() const - { - return base + size; - } - - void - SetRangeEnd(BaseType end) +namespace lldb_private { + + //---------------------------------------------------------------------- + // Templatized classes for dealing with generic ranges and also + // collections of ranges, or collections of ranges that have associated + // data. + //---------------------------------------------------------------------- + + //---------------------------------------------------------------------- + // A simple range class where you get to define the type of the range + // base "B", and the type used for the range byte size "S". + //---------------------------------------------------------------------- + template + struct Range { - if (end > base) - size = end - base; - else + typedef B BaseType; + typedef S SizeType; + + BaseType base; + SizeType size; + + Range () : + base (0), + size (0) + { + } + + Range (BaseType b, SizeType s) : + base (b), + size (s) + { + } + + void + Clear (BaseType b = 0) + { + base = b; size = 0; - } + } - SizeType - GetByteSize() const - { - return size; - } + // Set the start value for the range, and keep the same size + BaseType + GetRangeBase () const + { + return base; + } + + void + SetRangeBase (BaseType b) + { + base = b; + } + + void + Slide (BaseType slide) + { + base += slide; + } + + BaseType + GetRangeEnd () const + { + return base + size; + } + + void + SetRangeEnd (BaseType end) + { + if (end > base) + size = end - base; + else + size = 0; + } + + SizeType + GetByteSize () const + { + return size; + } + + void + SetByteSize (SizeType s) + { + size = s; + } + + bool + IsValid() const + { + return size > 0; + } + + bool + Contains (BaseType r) const + { + return (GetRangeBase() <= r) && (r < GetRangeEnd()); + } + + bool + ContainsEndInclusive (BaseType r) const + { + return (GetRangeBase() <= r) && (r <= GetRangeEnd()); + } + + bool + Contains (const Range& range) const + { + return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd()); + } - void - SetByteSize(SizeType s) - { - size = s; - } + // Returns true if the two ranges adjoing or intersect + bool + DoesAdjoinOrIntersect (const Range &rhs) const + { + const BaseType lhs_base = this->GetRangeBase(); + const BaseType rhs_base = rhs.GetRangeBase(); + const BaseType lhs_end = this->GetRangeEnd(); + const BaseType rhs_end = rhs.GetRangeEnd(); + bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base); + return result; + } - bool - IsValid() const - { - return size > 0; - } + // Returns true if the two ranges intersect + bool + DoesIntersect (const Range &rhs) const + { + const BaseType lhs_base = this->GetRangeBase(); + const BaseType rhs_base = rhs.GetRangeBase(); + const BaseType lhs_end = this->GetRangeEnd(); + const BaseType rhs_end = rhs.GetRangeEnd(); + bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base); + return result; + } - bool - Contains(BaseType r) const + bool + operator < (const Range &rhs) const + { + if (base == rhs.base) + return size < rhs.size; + return base < rhs.base; + } + + bool + operator == (const Range &rhs) const + { + return base == rhs.base && size == rhs.size; + } + + bool + operator != (const Range &rhs) const + { + return base != rhs.base || size != rhs.size; + } + }; + + //---------------------------------------------------------------------- + // A range array class where you get to define the type of the ranges + // that the collection contains. + //---------------------------------------------------------------------- + + template + class RangeArray { - return (GetRangeBase() <= r) && (r < GetRangeEnd()); - } + public: + typedef B BaseType; + typedef S SizeType; + typedef Range Entry; + typedef llvm::SmallVector Collection; - bool - ContainsEndInclusive(BaseType r) const - { - return (GetRangeBase() <= r) && (r <= GetRangeEnd()); - } + RangeArray() = default; - bool - Contains(const Range &range) const - { - return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd()); - } + ~RangeArray() = default; - // Returns true if the two ranges adjoing or intersect - bool - DoesAdjoinOrIntersect(const Range &rhs) const - { - return GetRangeBase() <= rhs.GetRangeEnd() && GetRangeEnd() >= rhs.GetRangeBase(); - } + void + Append (const Entry &entry) + { + m_entries.push_back (entry); + } + + bool + RemoveEntrtAtIndex (uint32_t idx) + { + if (idx < m_entries.size()) + { + m_entries.erase (m_entries.begin() + idx); + return true; + } + return false; + } + + 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 - // Returns true if the two ranges intersect - bool - DoesIntersect(const Range &rhs) const - { - return GetRangeBase() < rhs.GetRangeEnd() && GetRangeEnd() > rhs.GetRangeBase(); - } + void + CombineConsecutiveRanges () + { +#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; + } + } + + // 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(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); + } + } + } - bool - operator<(const Range &rhs) const - { - return base == rhs.base ? size < rhs.size : base < rhs.base; - } + BaseType + GetMinRangeBase (BaseType fail_value) const + { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert (IsSorted()); +#endif + if (m_entries.empty()) + return fail_value; + // m_entries must be sorted, so if we aren't empty, we grab the + // first range's base + return m_entries.front().GetRangeBase(); + } - bool - operator==(const Range &rhs) const - { - return base == rhs.base && size == rhs.size; - } + BaseType + GetMaxRangeEnd (BaseType fail_value) const + { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert (IsSorted()); +#endif + if (m_entries.empty()) + return fail_value; + // m_entries must be sorted, so if we aren't empty, we grab the + // last range's end + return m_entries.back().GetRangeEnd(); + } + + void + Slide (BaseType slide) + { + typename Collection::iterator pos, end; + for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) + pos->Slide (slide); + } + + 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]; + } - bool - operator!=(const Range &rhs) const - { - return !(*this == rhs); - } -}; + Entry * + Back() + { + return (m_entries.empty() ? nullptr : &m_entries.back()); + } -//---------------------------------------------------------------------- -// A simple range with data class where you get to define the type of -// the range base "B", the type used for the range byte size "S", and -// the type for the associated data "T". -//---------------------------------------------------------------------- -template struct RangeData : public Range -{ - typedef T DataType; + const Entry * + Back() const + { + return (m_entries.empty() ? nullptr : &m_entries.back()); + } - DataType data; + 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; + } - RangeData() = default; + const Entry * + FindEntryThatContains (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 &(*pos); + } + else if (pos != begin) + { + --pos; + if (pos->Contains(addr)) + { + return &(*pos); + } + } + } + return nullptr; + } - RangeData(B base, S size) : Range(base, size), data() {} + 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; + } - RangeData(B base, S size, DataType d) : Range(base, size), data(d) {} + protected: + Collection m_entries; + }; - bool - operator<(const RangeData &rhs) const + template + class RangeVector { - if (this->base == rhs.base) - return Range::operator<(rhs); + public: + typedef B BaseType; + typedef S SizeType; + typedef Range Entry; + typedef std::vector Collection; - return this->base < rhs.base; - } + RangeVector() = default; - bool - operator==(const RangeData &rhs) const - { - return this->data == rhs.data && Range::operator==(rhs); - } - - bool - operator!=(const RangeData &rhs) const - { - return !(*this == rhs); - } -}; - -template class RangeVectorBase -{ -public: - typedef E Entry; - typedef C Collection; - typedef typename Entry::BaseType BaseType; - typedef typename Entry::SizeType SizeType; - - void - Append(const Entry &entry) - { - m_entries.push_back(entry); - } + ~RangeVector() = default; - bool - RemoveEntrtAtIndex(uint32_t idx) - { - if (idx >= m_entries.size()) + void + Append (const Entry &entry) + { + m_entries.push_back (entry); + } + + bool + RemoveEntrtAtIndex (uint32_t idx) + { + if (idx < m_entries.size()) + { + m_entries.erase (m_entries.begin() + idx); + return true; + } return false; - - m_entries.erase(m_entries.begin() + idx); - return true; - } - - void - Sort() - { - std::stable_sort(m_entries.begin(), m_entries.end()); - } - - void - CombineConsecutiveRanges() - { - VerifySorted(); - - // Can't combine ranges if we have zero or one range - if (m_entries.size() <= 1) - return; - - // 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 - bool can_combine = false; - for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) + } + + void + Sort () { - if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) + 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++) { - can_combine = true; - break; + if (prev != end && *pos < *prev) + return false; } + return true; } +#endif - // 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) + void + CombineConsecutiveRanges () { - Collection minimal_ranges; - for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) +#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) { - if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) - minimal_ranges.back().SetRangeEnd(std::max(prev->GetRangeEnd(), pos->GetRangeEnd())); - else - minimal_ranges.push_back(*pos); + // 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; + } + } + + // 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(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); + } } - - // 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); } - } - - BaseType - GetMinRangeBase(BaseType fail_value) const - { - VerifySorted(); - - if (m_entries.empty()) - return fail_value; - - // m_entries must be sorted, so if we aren't empty, we grab the first range's base - return m_entries.front().GetRangeBase(); - } - - BaseType - GetMaxRangeEnd(BaseType fail_value) const - { - VerifySorted(); - - if (m_entries.empty()) - return fail_value; - // m_entries must be sorted, so if we aren't empty, we grab the last range's end - return m_entries.back().GetRangeEnd(); - } - - void - Slide(BaseType slide) - { - for (auto pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) - pos->Slide(slide); - } - - void - Clear() - { - m_entries.clear(); - } + BaseType + GetMinRangeBase (BaseType fail_value) const + { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert (IsSorted()); +#endif + if (m_entries.empty()) + return fail_value; + // m_entries must be sorted, so if we aren't empty, we grab the + // first range's base + return m_entries.front().GetRangeBase(); + } + + BaseType + GetMaxRangeEnd (BaseType fail_value) const + { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert (IsSorted()); +#endif + if (m_entries.empty()) + return fail_value; + // m_entries must be sorted, so if we aren't empty, we grab the + // last range's end + return m_entries.back().GetRangeEnd(); + } + + void + Slide (BaseType slide) + { + typename Collection::iterator pos, end; + for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) + pos->Slide (slide); + } + + void + Clear () + { + m_entries.clear(); + } - bool - IsEmpty() const - { - return m_entries.empty(); - } + void + Reserve (typename Collection::size_type size) + { + m_entries.reserve (size); + } - size_t - GetSize() const + 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]; + } + + Entry * + Back() + { + return (m_entries.empty() ? nullptr : &m_entries.back()); + } + + const Entry * + Back() const + { + return (m_entries.empty() ? nullptr : &m_entries.back()); + } + + 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; + } + + const Entry * + FindEntryThatContains (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 &(*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; + } + + protected: + Collection m_entries; + }; + + //---------------------------------------------------------------------- + // A simple range with data class where you get to define the type of + // the range base "B", the type used for the range byte size "S", and + // the type for the associated data "T". + //---------------------------------------------------------------------- + template + struct RangeData : public Range { - return m_entries.size(); - } - - Entry * - GetEntryAtIndex(size_t i) + typedef T DataType; + + DataType data; + + RangeData () : + Range (), + data () + { + } + + RangeData (B base, S size) : + Range (base, size), + data () + { + } + + RangeData (B base, S size, DataType d) : + Range (base, size), + data (d) + { + } + + bool + operator < (const RangeData &rhs) const + { + if (this->base == rhs.base) + { + if (this->size == rhs.size) + return this->data < rhs.data; + else + return this->size < rhs.size; + } + return this->base < rhs.base; + } + + bool + operator == (const RangeData &rhs) const + { + return this->GetRangeBase() == rhs.GetRangeBase() && + this->GetByteSize() == rhs.GetByteSize() && + this->data == rhs.data; + } + + bool + operator != (const RangeData &rhs) const + { + return this->GetRangeBase() != rhs.GetRangeBase() || + this->GetByteSize() != rhs.GetByteSize() || + this->data != rhs.data; + } + }; + + template + class RangeDataArray { - return i < m_entries.size() ? &m_entries[i] : nullptr; - } + public: + typedef RangeData Entry; + typedef llvm::SmallVector Collection; - const Entry * - GetEntryAtIndex(size_t i) const - { - return i < m_entries.size() ? &m_entries[i] : nullptr; - } + RangeDataArray() = default; - // 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]; - } + ~RangeDataArray() = default; - Entry * - Back() - { - return m_entries.empty() ? nullptr : &m_entries.back(); - } + 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 - const Entry * - Back() const - { - return m_entries.empty() ? nullptr : &m_entries.back(); - } + 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); + } - uint32_t - FindEntryIndexThatContains(const Entry &range) const - { - VerifySorted(); + // 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]; + } - if (m_entries.empty()) + 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; + } - auto begin = m_entries.begin(), end = m_entries.end(), pos = std::lower_bound(begin, end, range, BaseLessThan); - if (pos != end && pos->Contains(range)) - return std::distance(begin, pos); - - if (pos != begin) + Entry * + FindEntryThatContains (B addr) { - --pos; - if (pos->Contains(range)) - return std::distance(begin, pos); +#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; } - return UINT32_MAX; - } - uint32_t - FindEntryIndexThatContains(BaseType addr) const - { - return FindEntryIndexThatContains(Entry(addr, 1)); - } + 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()); + } - Entry * - FindEntryThatContains(BaseType addr) - { - return GetEntryAtIndex(FindEntryIndexThatContains(addr)); - } + const Entry * + Back() const + { + return (m_entries.empty() ? nullptr : &m_entries.back()); + } - const Entry * - FindEntryThatContains(BaseType addr) const - { - return GetEntryAtIndex(FindEntryIndexThatContains(addr)); - } + protected: + Collection m_entries; + }; - const Entry * - FindEntryThatContains(const Entry &range) const + // Same as RangeDataArray, but uses std::vector as to not + // require static storage of N items in the class itself + template + class RangeDataVector { - return GetEntryAtIndex(FindEntryIndexThatContains(range)); - } + public: + typedef RangeData Entry; + typedef std::vector Collection; - void - Reserve(size_t size) - { - m_entries.resize(size); - } + RangeDataVector() = default; - // 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() - { - VerifySorted(); + ~RangeDataVector() = default; - for (auto pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) + void + Append (const Entry &entry) { - if (pos->GetByteSize() == 0) + 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++) { - // 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 (auto next = pos + 1; next != end; ++next) + if (prev != end && prev->data == pos->data) { - auto next_base = next->GetRangeBase(); - if (next_base > curr_base) + 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); + } + } + + // 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 () + { +#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) { - pos->SetByteSize(next_base - curr_base); - break; + auto next_base = next->GetRangeBase(); + if (next_base > curr_base) + { + pos->SetByteSize (next_base - curr_base); + break; + } } } } } - } + + void + Clear () + { + m_entries.clear(); + } - uint32_t - FindEntryIndexesThatContain(BaseType addr, std::vector &indexes) const - { - VerifySorted(); + void + Reserve (typename Collection::size_type size) + { + m_entries.resize (size); + } - if (!m_entries.empty()) + bool + IsEmpty () const { - for (const auto &entry : m_entries) + 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() ) { - if (entry.Contains(addr)) - indexes.push_back(entry.data); + 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); } + return UINT32_MAX; } - return indexes.size(); - } - - static bool - BaseLessThan(const Entry &lhs, const Entry &rhs) - { - return lhs.GetRangeBase() < rhs.GetRangeBase(); - } -protected: - void - VerifySorted() const - { + uint32_t + FindEntryIndexesThatContain(B addr, std::vector &indexes) const + { #ifdef ASSERT_RANGEMAP_ARE_SORTED - for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) - assert(prev == end || *pos >= *prev); + assert (IsSorted()); #endif - } - - Collection m_entries; -}; - -template class RangeDataVectorBase : public RangeVectorBase -{ -public: - void - CombineConsecutiveEntriesWithEqualData() - { - VerifySorted(); - // 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 - bool can_combine = false; - for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) + if (!m_entries.empty()) + { + typename Collection::const_iterator pos; + for (const auto &entry : m_entries) + { + if (entry.Contains(addr)) + indexes.push_back(entry.data); + } + } + return indexes.size() ; + } + + Entry * + FindEntryThatContains (B addr) { - if (prev != end && prev->data == pos->data) +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert (IsSorted()); +#endif + if ( !m_entries.empty() ) { - can_combine = true; - break; + 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; } - // 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) + const Entry * + FindEntryThatContains (B addr) const { - Collection minimal_ranges; - for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert (IsSorted()); +#endif + if ( !m_entries.empty() ) { - if (prev != end && prev->data == pos->data) - minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd()); - else - minimal_ranges.push_back(*pos); + 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); } - - // 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); + 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); + + while(pos != begin && pos[-1].Contains(range)) + --pos; + + if (pos != end && 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; + }; + + //---------------------------------------------------------------------- + // A simple range with data class where you get to define the type of + // the range base "B", the type used for the range byte size "S", and + // the type for the associated data "T". + //---------------------------------------------------------------------- + template + struct AddressData + { + typedef B BaseType; + typedef T DataType; + + BaseType addr; + DataType data; + + AddressData () : + addr (), + data () + { + } + + AddressData (B a, DataType d) : + addr (a), + data (d) + { } - } + + bool + operator < (const AddressData &rhs) const + { + if (this->addr == rhs.addr) + return this->data < rhs.data; + return this->addr < rhs.addr; + } + + bool + operator == (const AddressData &rhs) const + { + return this->addr == rhs.addr && + this->data == rhs.data; + } + + bool + operator != (const AddressData &rhs) const + { + return this->addr != rhs.addr || + this->data == rhs.data; + } + }; + + template + class AddressDataArray + { + public: + typedef AddressData Entry; + typedef llvm::SmallVector Collection; -protected: - using typename RangeVectorBase::Collection; - using RangeVectorBase::VerifySorted; - using RangeVectorBase::m_entries; -}; + AddressDataArray() = default; + + ~AddressDataArray() = 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 -// Use public inheritance to define these types instead of alias templates because MSVC 2013 -// generates incorrect code for alias templates. + 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); + } -template class RangeVector : public RangeVectorBase, std::vector>> -{ -}; + // 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]; + } -template -class RangeArray : public RangeVectorBase, llvm::SmallVector, N>> -{ -}; + static bool + BaseLessThan (const Entry& lhs, const Entry& rhs) + { + return lhs.addr < rhs.addr; + } + + Entry * + FindEntry (B addr, bool exact_match_only) + { +#ifdef ASSERT_RANGEMAP_ARE_SORTED + assert (IsSorted()); +#endif + if ( !m_entries.empty() ) + { + Entry entry; + entry.addr = addr; + 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].addr == addr) + --pos; + + if (pos != end) + { + if (pos->addr == addr || !exact_match_only) + return &(*pos); + } + } + return nullptr; + } + + const Entry * + FindNextEntry (const Entry *entry) + { + if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) + return entry + 1; + return nullptr; + } + + Entry * + Back() + { + return (m_entries.empty() ? nullptr : &m_entries.back()); + } -template -class RangeDataVector : public RangeDataVectorBase, std::vector>> -{ -}; + const Entry * + Back() const + { + return (m_entries.empty() ? nullptr : &m_entries.back()); + } -template -class RangeDataArray : public RangeDataVectorBase, llvm::SmallVector, N>> -{ -}; + protected: + Collection m_entries; + }; } // namespace lldb_private diff --git a/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp b/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp index 61c9f20..c9f209e 100644 --- a/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp +++ b/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp @@ -107,181 +107,6 @@ struct lldb_copy_dyld_cache_local_symbols_entry uint32_t nlistCount; }; -//---------------------------------------------------------------------- -// A simple range with data class where you get to define the type of -// the range base "B", the type used for the range byte size "S", and -// the type for the associated data "T". -//---------------------------------------------------------------------- -template -struct AddressData -{ - typedef B BaseType; - typedef T DataType; - - BaseType addr; - DataType data; - - AddressData () : - addr (), - data () - { - } - - AddressData (B a, DataType d) : - addr (a), - data (d) - { - } - - bool - operator < (const AddressData &rhs) const - { - if (this->addr == rhs.addr) - return this->data < rhs.data; - return this->addr < rhs.addr; - } - - bool - operator == (const AddressData &rhs) const - { - return this->addr == rhs.addr && - this->data == rhs.data; - } - - bool - operator != (const AddressData &rhs) const - { - return this->addr != rhs.addr || - this->data == rhs.data; - } -}; - -template -class AddressDataArray -{ -public: - typedef AddressData Entry; - typedef llvm::SmallVector Collection; - - AddressDataArray() = default; - - ~AddressDataArray() = 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 - 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.addr < rhs.addr; - } - - Entry * - FindEntry (B addr, bool exact_match_only) - { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert (IsSorted()); -#endif - if ( !m_entries.empty() ) - { - Entry entry; - entry.addr = addr; - 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].addr == addr) - --pos; - - if (pos != end) - { - if (pos->addr == addr || !exact_match_only) - return &(*pos); - } - } - return nullptr; - } - - const Entry * - FindNextEntry (const Entry *entry) - { - if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) - return entry + 1; - 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; -}; class RegisterContextDarwin_x86_64_Mach : public RegisterContextDarwin_x86_64 { -- 2.7.4