From 7a2a5ce0589f8ac9b5c6ca8e7bf202061f7565aa Mon Sep 17 00:00:00 2001 From: Tamas Berghammer Date: Tue, 2 Feb 2016 18:18:13 +0000 Subject: [PATCH] [NFC] Cleanup RangeMap.h The file contained very similar 4 implementation of the same data structure with a lot of duplicated code and some minor API differences. This CL refactor the class to eliminate the duplicated codes and to unify the APIs. RangeMap.h also contained a class called AddressDataArray what have very little added functionality over an std::vector and used only by ObjectFileMacO The CL moves the class to ObjectFileMachO.cpp as it isn't belongs into RangeMap.h and shouldn't be used in new places anyway because of the little added functionality. Differential revision: http://reviews.llvm.org/D16769 llvm-svn: 259538 --- lldb/include/lldb/Core/RangeMap.h | 1790 +++++--------------- .../Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp | 175 ++ 2 files changed, 583 insertions(+), 1382 deletions(-) diff --git a/lldb/include/lldb/Core/RangeMap.h b/lldb/include/lldb/Core/RangeMap.h index 28d3083..75c37ac 100644 --- a/lldb/include/lldb/Core/RangeMap.h +++ b/lldb/include/lldb/Core/RangeMap.h @@ -24,1478 +24,504 @@ // Uncomment to make sure all Range objects are sorted when needed //#define ASSERT_RANGEMAP_ARE_SORTED -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 +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) { - 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; + 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) + { + if (end > base) + size = end - base; + else size = 0; - } + } - // 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()); - } + SizeType + GetByteSize() const + { + return size; + } - // 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; - } + void + SetByteSize(SizeType s) + { + size = s; + } - // 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 + IsValid() const + { + return size > 0; + } - 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 + bool + Contains(BaseType r) const { - public: - typedef B BaseType; - typedef S SizeType; - typedef Range Entry; - typedef llvm::SmallVector Collection; + return (GetRangeBase() <= r) && (r < GetRangeEnd()); + } - RangeArray() = default; + 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()); + } - 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 adjoing or intersect + bool + DoesAdjoinOrIntersect(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); - } - } - } + // Returns true if the two ranges intersect + bool + DoesIntersect(const Range &rhs) const + { + return GetRangeBase() < rhs.GetRangeEnd() && GetRangeEnd() > rhs.GetRangeBase(); + } - 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 : base < rhs.base; + } - 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 base == rhs.base && size == rhs.size; + } - Entry * - Back() - { - return (m_entries.empty() ? nullptr : &m_entries.back()); - } + bool + operator!=(const Range &rhs) const + { + return !(*this == rhs); + } +}; - const Entry * - Back() const - { - 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; - 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; - } + DataType data; - 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() = default; - 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) : Range(base, size), data() {} - protected: - Collection m_entries; - }; + RangeData(B base, S size, DataType d) : Range(base, size), data(d) {} - template - class RangeVector + bool + operator<(const RangeData &rhs) const { - public: - typedef B BaseType; - typedef S SizeType; - typedef Range Entry; - typedef std::vector Collection; + if (this->base == rhs.base) + return Range::operator<(rhs); - RangeVector() = default; + return this->base < rhs.base; + } - ~RangeVector() = default; + bool + operator==(const RangeData &rhs) const + { + return this->data == rhs.data && Range::operator==(rhs); + } - 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; - } + 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); + } + + bool + RemoveEntrtAtIndex(uint32_t idx) + { + if (idx >= m_entries.size()) 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 - 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); - } - } - } + m_entries.erase(m_entries.begin() + idx); + return true; + } - 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(); - } + void + Sort() + { + std::stable_sort(m_entries.begin(), m_entries.end()); + } - void - Reserve (typename Collection::size_type size) - { - m_entries.reserve (size); - } + void + CombineConsecutiveRanges() + { + VerifySorted(); - 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 + // 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++) { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert (IsSorted()); -#endif - if (!m_entries.empty()) + if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) { - 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); - } - } + can_combine = true; + break; } - 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 - { - 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 + + // 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) { - if (this->base == rhs.base) + Collection minimal_ranges; + for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) { - if (this->size == rhs.size) - return this->data < rhs.data; + if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) + minimal_ranges.back().SetRangeEnd(std::max(prev->GetRangeEnd(), pos->GetRangeEnd())); else - return this->size < rhs.size; + minimal_ranges.push_back(*pos); } - 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; + + // 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); } - }; - - template - class RangeDataArray + } + + BaseType + GetMinRangeBase(BaseType fail_value) const { - public: - typedef RangeData Entry; - typedef llvm::SmallVector Collection; + VerifySorted(); - RangeDataArray() = default; + if (m_entries.empty()) + return fail_value; - ~RangeDataArray() = default; + // m_entries must be sorted, so if we aren't empty, we grab the first range's base + return m_entries.front().GetRangeBase(); + } - 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 + BaseType + GetMaxRangeEnd(BaseType fail_value) const + { + VerifySorted(); - 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); - } + if (m_entries.empty()) + return fail_value; - // 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]; - } + // m_entries must be sorted, so if we aren't empty, we grab the last range's end + return m_entries.back().GetRangeEnd(); + } - 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); - } - } + 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(); + } + + bool + IsEmpty() const + { + return m_entries.empty(); + } + + size_t + GetSize() const + { + return m_entries.size(); + } + + Entry * + GetEntryAtIndex(size_t i) + { + return i < m_entries.size() ? &m_entries[i] : nullptr; + } + + 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(); + } + + uint32_t + FindEntryIndexThatContains(const Entry &range) const + { + VerifySorted(); + + if (m_entries.empty()) 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; - } + 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); - 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 + if (pos != begin) { -#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()); + --pos; + if (pos->Contains(range)) + return std::distance(begin, pos); } + return UINT32_MAX; + } - const Entry * - Back() const - { - return (m_entries.empty() ? nullptr : &m_entries.back()); - } + uint32_t + FindEntryIndexThatContains(BaseType addr) const + { + return FindEntryIndexThatContains(Entry(addr, 1)); + } - protected: - Collection m_entries; - }; + Entry * + FindEntryThatContains(BaseType addr) + { + return GetEntryAtIndex(FindEntryIndexThatContains(addr)); + } - // Same as RangeDataArray, but uses std::vector as to not - // require static storage of N items in the class itself - template - class RangeDataVector + const Entry * + FindEntryThatContains(BaseType addr) const { - public: - typedef RangeData Entry; - typedef std::vector Collection; + return GetEntryAtIndex(FindEntryIndexThatContains(addr)); + } - RangeDataVector() = default; + const Entry * + FindEntryThatContains(const Entry &range) const + { + return GetEntryAtIndex(FindEntryIndexThatContains(range)); + } - ~RangeDataVector() = default; + void + Reserve(size_t size) + { + m_entries.resize(size); + } - 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); - } - } - - // 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 () + // 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(); + + for (auto pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) { -#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) { - 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 (auto next = pos + 1; next != end; ++next) { - // 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) { - auto next_base = next->GetRangeBase(); - if (next_base > curr_base) - { - pos->SetByteSize (next_base - curr_base); - break; - } + pos->SetByteSize(next_base - curr_base); + break; } } } } - - void - Clear () - { - m_entries.clear(); - } + } - void - Reserve (typename Collection::size_type size) - { - m_entries.resize (size); - } + uint32_t + FindEntryIndexesThatContain(BaseType addr, std::vector &indexes) const + { + VerifySorted(); - bool - IsEmpty () const + if (!m_entries.empty()) { - 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() ) + for (const auto &entry : m_entries) { - 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); + if (entry.Contains(addr)) + indexes.push_back(entry.data); } - return UINT32_MAX; } + return indexes.size(); + } - uint32_t - FindEntryIndexesThatContain(B addr, std::vector &indexes) const - { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert (IsSorted()); -#endif + static bool + BaseLessThan(const Entry &lhs, const Entry &rhs) + { + return lhs.GetRangeBase() < rhs.GetRangeBase(); + } - 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) - { +protected: + void + VerifySorted() const + { #ifdef ASSERT_RANGEMAP_ARE_SORTED - assert (IsSorted()); + for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) + assert(prev == end || *pos >= *prev); #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; - } + } - 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; - } - - 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; - } - }; + Collection m_entries; +}; - template - class AddressDataArray +template class RangeDataVectorBase : public RangeVectorBase +{ +public: + void + CombineConsecutiveEntriesWithEqualData() { - public: - typedef AddressData Entry; - typedef llvm::SmallVector Collection; - - AddressDataArray() = default; + VerifySorted(); - ~AddressDataArray() = default; - - void - Append (const Entry &entry) - { - m_entries.push_back (entry); - } - - void - Sort () + // 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.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 && prev->data == pos->data) { - if (prev != end && *pos < *prev) - return false; + can_combine = true; + break; } - 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) + // 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) { - 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() ) + Collection minimal_ranges; + for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) { - 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); - } + if (prev != end && prev->data == pos->data) + minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd()); + else + minimal_ranges.push_back(*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()); + // 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); } + } + +protected: + using typename RangeVectorBase::Collection; + using RangeVectorBase::VerifySorted; + using RangeVectorBase::m_entries; +}; + +// Use public inheritance to define these types instead of alias templates because MSVC 2013 +// generates incorrect code for alias templates. + +template class RangeVector : public RangeVectorBase, std::vector>> +{ +}; + +template +class RangeArray : public RangeVectorBase, llvm::SmallVector, N>> +{ +}; + +template +class RangeDataVector : public RangeDataVectorBase, std::vector>> +{ +}; - protected: - Collection m_entries; - }; +template +class RangeDataArray : public RangeDataVectorBase, llvm::SmallVector, N>> +{ +}; } // namespace lldb_private diff --git a/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp b/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp index c9f209e..61c9f20 100644 --- a/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp +++ b/lldb/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp @@ -107,6 +107,181 @@ 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