diff options
| -rw-r--r-- | lldb/include/lldb/Core/RangeMap.h | 1790 | ||||
| -rw-r--r-- | lldb/source/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 28d3083979d..75c37ac4720 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 <typename B, typename S> - 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 <typename B, typename S> 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 <typename B, typename S, unsigned N> - class RangeArray + bool + Contains(BaseType r) const { - public: - typedef B BaseType; - typedef S SizeType; - typedef Range<B,S> Entry; - typedef llvm::SmallVector<Entry, N> 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<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd())); - else - minimal_ranges.push_back (*pos); - } - // Use the swap technique in case our new vector is much smaller. - // We must swap when using the STL because std::vector objects never - // release or reduce the memory once it has been allocated/reserved. - m_entries.swap (minimal_ranges); - } - } - } + // 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 <typename B, typename S, typename T> struct RangeData : public Range<B, S> +{ + 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<B, S>(base, size), data() {} - protected: - Collection m_entries; - }; + RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {} - template <typename B, typename S> - class RangeVector + bool + operator<(const RangeData &rhs) const { - public: - typedef B BaseType; - typedef S SizeType; - typedef Range<B,S> Entry; - typedef std::vector<Entry> Collection; + if (this->base == rhs.base) + return Range<B, S>::operator<(rhs); - RangeVector() = default; + return this->base < rhs.base; + } - ~RangeVector() = default; + bool + operator==(const RangeData &rhs) const + { + return this->data == rhs.data && Range<B, S>::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 <typename E, typename C> 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<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd())); - else - minimal_ranges.push_back (*pos); - } - // Use the swap technique in case our new vector is much smaller. - // We must swap when using the STL because std::vector objects never - // release or reduce the memory once it has been allocated/reserved. - m_entries.swap (minimal_ranges); - } - } - } + 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 <typename B, typename S, typename T> - struct RangeData : public Range<B,S> - { - typedef T DataType; - - DataType data; - - RangeData () : - Range<B,S> (), - data () - { - } - - RangeData (B base, S size) : - Range<B,S> (base, size), - data () - { - } - - RangeData (B base, S size, DataType d) : - Range<B,S> (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<BaseType>(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 <typename B, typename S, typename T, unsigned N> - class RangeDataArray + } + + BaseType + GetMinRangeBase(BaseType fail_value) const { - public: - typedef RangeData<B,S,T> Entry; - typedef llvm::SmallVector<Entry, N> 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 <typename B, typename S, typename T> - class RangeDataVector + const Entry * + FindEntryThatContains(BaseType addr) const { - public: - typedef RangeData<B,S,T> Entry; - typedef std::vector<Entry> 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<uint32_t> &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<uint32_t> &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 <typename B, typename T> - 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 <typename B, typename T, unsigned N> - class AddressDataArray +template <typename E, typename S> class RangeDataVectorBase : public RangeVectorBase<E, S> +{ +public: + void + CombineConsecutiveEntriesWithEqualData() { - public: - typedef AddressData<B,T> Entry; - typedef llvm::SmallVector<Entry, N> 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<E, S>::Collection; + using RangeVectorBase<E, S>::VerifySorted; + using RangeVectorBase<E, S>::m_entries; +}; + +// Use public inheritance to define these types instead of alias templates because MSVC 2013 +// generates incorrect code for alias templates. + +template <typename B, typename S> class RangeVector : public RangeVectorBase<Range<B, S>, std::vector<Range<B, S>>> +{ +}; + +template <typename B, typename S, size_t N> +class RangeArray : public RangeVectorBase<Range<B, S>, llvm::SmallVector<Range<B, S>, N>> +{ +}; + +template <typename B, typename S, typename T> +class RangeDataVector : public RangeDataVectorBase<RangeData<B, S, T>, std::vector<RangeData<B, S, T>>> +{ +}; - protected: - Collection m_entries; - }; +template <typename B, typename S, typename T, size_t N> +class RangeDataArray : public RangeDataVectorBase<RangeData<B, S, T>, llvm::SmallVector<RangeData<B, S, T>, 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 c9f209e2c0f..61c9f20b658 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 <typename B, typename T> +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 <typename B, typename T, unsigned N> +class AddressDataArray +{ +public: + typedef AddressData<B,T> Entry; + typedef llvm::SmallVector<Entry, N> 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 { |
