Author: labath Date: Wed Mar 6 06:41:43 2019 New Revision: 355509 URL: http://llvm.org/viewvc/llvm-project?rev=355509&view=rev Log: Move RangeMap.h into Utility
Summary: This file implements some general purpose data structures, and so it belongs to the Utility module. Reviewers: zturner, jingham, JDevlieghere, clayborg, espindola Subscribers: emaste, mgorny, javed.absar, arichardson, MaskRay, lldb-commits Differential Revision: https://reviews.llvm.org/D58970 Added: lldb/trunk/include/lldb/Utility/RangeMap.h - copied, changed from r355476, lldb/trunk/include/lldb/Core/RangeMap.h lldb/trunk/unittests/Utility/RangeMapTest.cpp - copied, changed from r355476, lldb/trunk/unittests/Core/RangeMapTest.cpp lldb/trunk/unittests/Utility/RangeTest.cpp - copied, changed from r355476, lldb/trunk/unittests/Core/RangeTest.cpp Removed: lldb/trunk/include/lldb/Core/RangeMap.h lldb/trunk/unittests/Core/RangeMapTest.cpp lldb/trunk/unittests/Core/RangeTest.cpp Modified: lldb/trunk/include/lldb/Core/dwarf.h lldb/trunk/include/lldb/Symbol/ArmUnwindInfo.h lldb/trunk/include/lldb/Symbol/Block.h lldb/trunk/include/lldb/Symbol/CompactUnwindInfo.h lldb/trunk/include/lldb/Symbol/DWARFCallFrameInfo.h lldb/trunk/include/lldb/Symbol/LineTable.h lldb/trunk/include/lldb/Symbol/Symtab.h lldb/trunk/include/lldb/Symbol/Variable.h lldb/trunk/include/lldb/Target/Memory.h lldb/trunk/include/lldb/Target/MemoryRegionInfo.h lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp lldb/trunk/source/Plugins/ObjectFile/JIT/ObjectFileJIT.cpp lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.h lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h lldb/trunk/source/Target/Memory.cpp lldb/trunk/unittests/Core/CMakeLists.txt lldb/trunk/unittests/Utility/CMakeLists.txt Removed: lldb/trunk/include/lldb/Core/RangeMap.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Core/RangeMap.h?rev=355508&view=auto ============================================================================== --- lldb/trunk/include/lldb/Core/RangeMap.h (original) +++ lldb/trunk/include/lldb/Core/RangeMap.h (removed) @@ -1,950 +0,0 @@ -//===-- RangeMap.h ----------------------------------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef liblldb_RangeMap_h_ -#define liblldb_RangeMap_h_ - -#include <algorithm> -#include <vector> - -#include "llvm/ADT/SmallVector.h" - -#include "lldb/lldb-private.h" - -// 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 { - typedef B BaseType; - typedef S SizeType; - - BaseType base; - SizeType size; - - Range() : base(0), size(0) {} - - Range(BaseType b, SizeType s) : base(b), size(s) {} - - void Clear(BaseType b = 0) { - base = b; - size = 0; - } - - // 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; } - - bool Union(const Range &rhs) - { - if (DoesAdjoinOrIntersect(rhs)) - { - auto new_end = std::max<BaseType>(GetRangeEnd(), rhs.GetRangeEnd()); - base = std::min<BaseType>(base, rhs.base); - size = new_end - base; - return true; - } - return false; - } - - 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()); - } - - // 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; - } - - // 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 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 { -public: - typedef B BaseType; - typedef S SizeType; - typedef Range<B, S> Entry; - typedef llvm::SmallVector<Entry, N> Collection; - - RangeArray() = default; - - ~RangeArray() = default; - - void Append(const Entry &entry) { m_entries.push_back(entry); } - - void Append(B base, S size) { m_entries.emplace_back(base, size); } - - 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; - 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); - } - } - } - - BaseType GetMinRangeBase(BaseType fail_value) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (m_entries.empty()) - return fail_value; - // m_entries must be sorted, so if we aren't empty, we grab the first - // range's base - return m_entries.front().GetRangeBase(); - } - - BaseType GetMaxRangeEnd(BaseType fail_value) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (m_entries.empty()) - return fail_value; - // m_entries must be sorted, so if we aren't empty, we grab the last - // range's end - return m_entries.back().GetRangeEnd(); - } - - void Slide(BaseType slide) { - typename Collection::iterator pos, end; - for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) - pos->Slide(slide); - } - - void Clear() { m_entries.clear(); } - - bool IsEmpty() const { return m_entries.empty(); } - - size_t GetSize() const { return m_entries.size(); } - - const Entry *GetEntryAtIndex(size_t i) const { - return ((i < m_entries.size()) ? &m_entries[i] : nullptr); - } - - // Clients must ensure that "i" is a valid index prior to calling this - // function - const Entry &GetEntryRef(size_t i) const { return m_entries[i]; } - - Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); } - - const Entry *Back() const { - return (m_entries.empty() ? nullptr : &m_entries.back()); - } - - static bool BaseLessThan(const Entry &lhs, const Entry &rhs) { - return lhs.GetRangeBase() < rhs.GetRangeBase(); - } - - uint32_t FindEntryIndexThatContains(B addr) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry(addr, 1); - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, entry, BaseLessThan); - - if (pos != end && pos->Contains(addr)) { - return std::distance(begin, pos); - } else if (pos != begin) { - --pos; - if (pos->Contains(addr)) - return std::distance(begin, pos); - } - } - return UINT32_MAX; - } - - const Entry *FindEntryThatContains(B addr) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry(addr, 1); - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, entry, BaseLessThan); - - if (pos != end && pos->Contains(addr)) { - return &(*pos); - } else if (pos != begin) { - --pos; - if (pos->Contains(addr)) { - return &(*pos); - } - } - } - return nullptr; - } - - const Entry *FindEntryThatContains(const Entry &range) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, range, BaseLessThan); - - if (pos != end && pos->Contains(range)) { - return &(*pos); - } else if (pos != begin) { - --pos; - if (pos->Contains(range)) { - return &(*pos); - } - } - } - return nullptr; - } - -protected: - Collection m_entries; -}; - -template <typename B, typename S> class RangeVector { -public: - typedef B BaseType; - typedef S SizeType; - typedef Range<B, S> Entry; - typedef std::vector<Entry> Collection; - - RangeVector() = default; - - ~RangeVector() = default; - - void Append(const Entry &entry) { m_entries.push_back(entry); } - - void Append(B base, S size) { m_entries.emplace_back(base, size); } - - // Insert an item into a sorted list and optionally combine it with any - // adjacent blocks if requested. - void Insert(const Entry &entry, bool combine) { - if (m_entries.empty()) { - m_entries.push_back(entry); - return; - } - auto begin = m_entries.begin(); - auto end = m_entries.end(); - auto pos = std::lower_bound(begin, end, entry); - if (combine) { - if (pos != end && pos->Union(entry)) { - CombinePrevAndNext(pos); - return; - } - if (pos != begin) { - auto prev = pos - 1; - if (prev->Union(entry)) { - CombinePrevAndNext(prev); - return; - } - } - } - m_entries.insert(pos, entry); - } - - bool RemoveEntryAtIndex(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 - - 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); - } - } - } - - 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 Reserve(typename Collection::size_type size) { m_entries.reserve(size); } - - 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 - Entry &GetEntryRef(size_t i) { return m_entries[i]; } - const Entry &GetEntryRef(size_t i) const { return m_entries[i]; } - - Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); } - - const Entry *Back() const { - return (m_entries.empty() ? nullptr : &m_entries.back()); - } - - static bool BaseLessThan(const Entry &lhs, const Entry &rhs) { - return lhs.GetRangeBase() < rhs.GetRangeBase(); - } - - uint32_t FindEntryIndexThatContains(B addr) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry(addr, 1); - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, entry, BaseLessThan); - - if (pos != end && pos->Contains(addr)) { - return std::distance(begin, pos); - } else if (pos != begin) { - --pos; - if (pos->Contains(addr)) - return std::distance(begin, pos); - } - } - return UINT32_MAX; - } - - const Entry *FindEntryThatContains(B addr) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - Entry entry(addr, 1); - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, entry, BaseLessThan); - - if (pos != end && pos->Contains(addr)) { - return &(*pos); - } else if (pos != begin) { - --pos; - if (pos->Contains(addr)) { - return &(*pos); - } - } - } - return nullptr; - } - - const Entry *FindEntryThatContains(const Entry &range) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - typename Collection::const_iterator begin = m_entries.begin(); - typename Collection::const_iterator end = m_entries.end(); - typename Collection::const_iterator pos = - std::lower_bound(begin, end, range, BaseLessThan); - - if (pos != end && pos->Contains(range)) { - return &(*pos); - } else if (pos != begin) { - --pos; - if (pos->Contains(range)) { - return &(*pos); - } - } - } - return nullptr; - } - -protected: - - void CombinePrevAndNext(typename Collection::iterator pos) { - // Check if the prev or next entries in case they need to be unioned with - // the entry pointed to by "pos". - if (pos != m_entries.begin()) { - auto prev = pos - 1; - if (prev->Union(*pos)) - m_entries.erase(pos); - pos = prev; - } - - auto end = m_entries.end(); - if (pos != end) { - auto next = pos + 1; - if (next != end) { - if (pos->Union(*next)) - m_entries.erase(next); - } - } - return; - } - - 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 { - if (this->base == rhs.base) { - if (this->size == rhs.size) - return this->data < rhs.data; - else - return this->size < rhs.size; - } - return this->base < rhs.base; - } - - bool operator==(const RangeData &rhs) const { - return this->GetRangeBase() == rhs.GetRangeBase() && - this->GetByteSize() == rhs.GetByteSize() && this->data == rhs.data; - } - - bool operator!=(const RangeData &rhs) const { - return this->GetRangeBase() != rhs.GetRangeBase() || - this->GetByteSize() != rhs.GetByteSize() || this->data != rhs.data; - } -}; - -template <typename B, typename S, typename T, unsigned N = 0> -class RangeDataVector { -public: - typedef RangeData<B, S, T> Entry; - typedef llvm::SmallVector<Entry, N> Collection; - - RangeDataVector() = default; - - ~RangeDataVector() = default; - - void Append(const Entry &entry) { m_entries.push_back(entry); } - - void Sort() { - if (m_entries.size() > 1) - std::stable_sort(m_entries.begin(), m_entries.end()); - } - -#ifdef ASSERT_RANGEMAP_ARE_SORTED - bool IsSorted() const { - typename Collection::const_iterator pos, end, prev; - // First we determine if we can combine any of the Entry objects so we - // don't end up allocating and making a new collection for no reason - for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; - prev = pos++) { - if (prev != end && *pos < *prev) - return false; - } - return true; - } -#endif - - void CombineConsecutiveEntriesWithEqualData() { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - typename Collection::iterator pos; - typename Collection::iterator end; - typename Collection::iterator prev; - bool can_combine = false; - // First we determine if we can combine any of the Entry objects so we - // don't end up allocating and making a new collection for no reason - for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; - prev = pos++) { - if (prev != end && prev->data == pos->data) { - can_combine = true; - break; - } - } - - // We we can combine at least one entry, then we make a new collection and - // populate it accordingly, and then swap it into place. - if (can_combine) { - Collection minimal_ranges; - for (pos = m_entries.begin(), end = m_entries.end(), prev = end; - pos != end; prev = pos++) { - if (prev != end && prev->data == pos->data) - minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd()); - else - minimal_ranges.push_back(*pos); - } - // Use the swap technique in case our new vector is much smaller. We must - // swap when using the STL because std::vector objects never release or - // reduce the memory once it has been allocated/reserved. - m_entries.swap(minimal_ranges); - } - } - - void Clear() { m_entries.clear(); } - - bool IsEmpty() const { return m_entries.empty(); } - - size_t GetSize() const { return m_entries.size(); } - - const Entry *GetEntryAtIndex(size_t i) const { - return ((i < m_entries.size()) ? &m_entries[i] : nullptr); - } - - Entry *GetMutableEntryAtIndex(size_t i) { - return ((i < m_entries.size()) ? &m_entries[i] : nullptr); - } - - // Clients must ensure that "i" is a valid index prior to calling this - // function - Entry &GetEntryRef(size_t i) { return m_entries[i]; } - 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 { - const Entry *entry = FindEntryThatContains(addr); - if (entry) - return std::distance(m_entries.begin(), entry); - return UINT32_MAX; - } - - uint32_t FindEntryIndexesThatContain(B addr, - std::vector<uint32_t> &indexes) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - - if (!m_entries.empty()) { - for (const auto &entry : m_entries) { - if (entry.Contains(addr)) - indexes.push_back(entry.data); - } - } - return indexes.size(); - } - - Entry *FindEntryThatContains(B addr) { - return const_cast<Entry *>( - static_cast<const RangeDataVector *>(this)->FindEntryThatContains( - addr)); - } - - const Entry *FindEntryThatContains(B addr) const { - return FindEntryThatContains(Entry(addr, 1)); - } - - 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; - } - - const Entry *FindEntryStartsAt(B addr) const { -#ifdef ASSERT_RANGEMAP_ARE_SORTED - assert(IsSorted()); -#endif - if (!m_entries.empty()) { - auto begin = m_entries.begin(), end = m_entries.end(); - auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan); - if (pos != end && pos->base == addr) - return &(*pos); - } - return nullptr; - } - - // This method will return the entry that contains the given address, or the - // entry following that address. If you give it an address of 0 and the - // first entry starts at address 0x100, you will get the entry at 0x100. - // - // For most uses, FindEntryThatContains is the correct one to use, this is a - // less commonly needed behavior. It was added for core file memory regions, - // where we want to present a gap in the memory regions as a distinct region, - // so we need to know the start address of the next memory section that - // exists. - const Entry *FindEntryThatContainsOrFollows(B addr) 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(m_entries.begin(), end, addr, - [](const Entry &lhs, B rhs_base) -> bool { - return lhs.GetRangeEnd() <= rhs_base; - }); - - while (pos != begin && pos[-1].Contains(addr)) - --pos; - - if (pos != end) - 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; - } -}; - -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; -}; - -} // namespace lldb_private - -#endif // liblldb_RangeMap_h_ Modified: lldb/trunk/include/lldb/Core/dwarf.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Core/dwarf.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Core/dwarf.h (original) +++ lldb/trunk/include/lldb/Core/dwarf.h Wed Mar 6 06:41:43 2019 @@ -9,13 +9,12 @@ #ifndef DebugBase_dwarf_h_ #define DebugBase_dwarf_h_ +#include "lldb/Utility/RangeMap.h" #include <stdint.h> // Get the DWARF constant definitions from llvm #include "llvm/BinaryFormat/Dwarf.h" -#include "lldb/Core/RangeMap.h" - // and stuff them in our default namespace using namespace llvm::dwarf; Modified: lldb/trunk/include/lldb/Symbol/ArmUnwindInfo.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Symbol/ArmUnwindInfo.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Symbol/ArmUnwindInfo.h (original) +++ lldb/trunk/include/lldb/Symbol/ArmUnwindInfo.h Wed Mar 6 06:41:43 2019 @@ -9,12 +9,11 @@ #ifndef liblldb_ArmUnwindInfo_h_ #define liblldb_ArmUnwindInfo_h_ -#include <vector> - -#include "lldb/Core/RangeMap.h" #include "lldb/Symbol/ObjectFile.h" #include "lldb/Utility/DataExtractor.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" +#include <vector> /* * Unwind information reader and parser for the ARM exception handling ABI Modified: lldb/trunk/include/lldb/Symbol/Block.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Symbol/Block.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Symbol/Block.h (original) +++ lldb/trunk/include/lldb/Symbol/Block.h Wed Mar 6 06:41:43 2019 @@ -9,17 +9,16 @@ #ifndef liblldb_Block_h_ #define liblldb_Block_h_ -#include <vector> - #include "lldb/Core/AddressRange.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Symbol/CompilerType.h" #include "lldb/Symbol/LineEntry.h" #include "lldb/Symbol/SymbolContext.h" #include "lldb/Symbol/SymbolContextScope.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/Stream.h" #include "lldb/Utility/UserID.h" #include "lldb/lldb-private.h" +#include <vector> namespace lldb_private { Modified: lldb/trunk/include/lldb/Symbol/CompactUnwindInfo.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Symbol/CompactUnwindInfo.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Symbol/CompactUnwindInfo.h (original) +++ lldb/trunk/include/lldb/Symbol/CompactUnwindInfo.h Wed Mar 6 06:41:43 2019 @@ -9,14 +9,13 @@ #ifndef liblldb_CompactUnwindInfo_h_ #define liblldb_CompactUnwindInfo_h_ -#include <mutex> -#include <vector> - -#include "lldb/Core/RangeMap.h" #include "lldb/Symbol/ObjectFile.h" #include "lldb/Symbol/UnwindPlan.h" #include "lldb/Utility/DataExtractor.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" +#include <mutex> +#include <vector> namespace lldb_private { Modified: lldb/trunk/include/lldb/Symbol/DWARFCallFrameInfo.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Symbol/DWARFCallFrameInfo.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Symbol/DWARFCallFrameInfo.h (original) +++ lldb/trunk/include/lldb/Symbol/DWARFCallFrameInfo.h Wed Mar 6 06:41:43 2019 @@ -13,12 +13,11 @@ #include <mutex> #include "lldb/Core/AddressRange.h" -#include "lldb/Utility/Flags.h" - -#include "lldb/Core/RangeMap.h" #include "lldb/Core/dwarf.h" #include "lldb/Symbol/ObjectFile.h" #include "lldb/Symbol/UnwindPlan.h" +#include "lldb/Utility/Flags.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/VMRange.h" #include "lldb/lldb-private.h" Modified: lldb/trunk/include/lldb/Symbol/LineTable.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Symbol/LineTable.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Symbol/LineTable.h (original) +++ lldb/trunk/include/lldb/Symbol/LineTable.h Wed Mar 6 06:41:43 2019 @@ -9,13 +9,12 @@ #ifndef liblldb_LineTable_h_ #define liblldb_LineTable_h_ -#include <vector> - #include "lldb/Core/ModuleChild.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Core/Section.h" #include "lldb/Symbol/LineEntry.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" +#include <vector> namespace lldb_private { Modified: lldb/trunk/include/lldb/Symbol/Symtab.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Symbol/Symtab.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Symbol/Symtab.h (original) +++ lldb/trunk/include/lldb/Symbol/Symtab.h Wed Mar 6 06:41:43 2019 @@ -9,13 +9,12 @@ #ifndef liblldb_Symtab_h_ #define liblldb_Symtab_h_ -#include <mutex> -#include <vector> - -#include "lldb/Core/RangeMap.h" #include "lldb/Core/UniqueCStringMap.h" #include "lldb/Symbol/Symbol.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" +#include <mutex> +#include <vector> namespace lldb_private { Modified: lldb/trunk/include/lldb/Symbol/Variable.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Symbol/Variable.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Symbol/Variable.h (original) +++ lldb/trunk/include/lldb/Symbol/Variable.h Wed Mar 6 06:41:43 2019 @@ -9,17 +9,16 @@ #ifndef liblldb_Variable_h_ #define liblldb_Variable_h_ -#include <memory> -#include <vector> - #include "lldb/Core/Mangled.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Expression/DWARFExpression.h" #include "lldb/Symbol/Declaration.h" #include "lldb/Utility/CompletionRequest.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/UserID.h" #include "lldb/lldb-enumerations.h" #include "lldb/lldb-private.h" +#include <memory> +#include <vector> namespace lldb_private { Modified: lldb/trunk/include/lldb/Target/Memory.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Target/Memory.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Target/Memory.h (original) +++ lldb/trunk/include/lldb/Target/Memory.h Wed Mar 6 06:41:43 2019 @@ -9,14 +9,12 @@ #ifndef liblldb_Memory_h_ #define liblldb_Memory_h_ +#include "lldb/Utility/RangeMap.h" +#include "lldb/lldb-private.h" #include <map> #include <mutex> #include <vector> - -#include "lldb/Core/RangeMap.h" -#include "lldb/lldb-private.h" - namespace lldb_private { //---------------------------------------------------------------------- // A class to track memory that was read from a live process between Modified: lldb/trunk/include/lldb/Target/MemoryRegionInfo.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Target/MemoryRegionInfo.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Target/MemoryRegionInfo.h (original) +++ lldb/trunk/include/lldb/Target/MemoryRegionInfo.h Wed Mar 6 06:41:43 2019 @@ -10,9 +10,9 @@ #ifndef lldb_MemoryRegionInfo_h #define lldb_MemoryRegionInfo_h -#include "lldb/Core/RangeMap.h" -#include "llvm/Support/FormatProviders.h" #include "lldb/Utility/ConstString.h" +#include "lldb/Utility/RangeMap.h" +#include "llvm/Support/FormatProviders.h" namespace lldb_private { class MemoryRegionInfo { Copied: lldb/trunk/include/lldb/Utility/RangeMap.h (from r355476, lldb/trunk/include/lldb/Core/RangeMap.h) URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/include/lldb/Utility/RangeMap.h?p2=lldb/trunk/include/lldb/Utility/RangeMap.h&p1=lldb/trunk/include/lldb/Core/RangeMap.h&r1=355476&r2=355509&rev=355509&view=diff ============================================================================== --- lldb/trunk/include/lldb/Core/RangeMap.h (original) +++ lldb/trunk/include/lldb/Utility/RangeMap.h Wed Mar 6 06:41:43 2019 @@ -6,8 +6,8 @@ // //===----------------------------------------------------------------------===// -#ifndef liblldb_RangeMap_h_ -#define liblldb_RangeMap_h_ +#ifndef LLDB_UTILITY_RANGEMAP_H +#define LLDB_UTILITY_RANGEMAP_H #include <algorithm> #include <vector> @@ -53,10 +53,8 @@ template <typename B, typename S> struct void Slide(BaseType slide) { base += slide; } - bool Union(const Range &rhs) - { - if (DoesAdjoinOrIntersect(rhs)) - { + bool Union(const Range &rhs) { + if (DoesAdjoinOrIntersect(rhs)) { auto new_end = std::max<BaseType>(GetRangeEnd(), rhs.GetRangeEnd()); base = std::min<BaseType>(base, rhs.base); size = new_end - base; @@ -569,7 +567,6 @@ public: } protected: - void CombinePrevAndNext(typename Collection::iterator pos) { // Check if the prev or next entries in case they need to be unioned with // the entry pointed to by "pos". @@ -579,7 +576,7 @@ protected: m_entries.erase(pos); pos = prev; } - + auto end = m_entries.end(); if (pos != end) { auto next = pos + 1; @@ -947,4 +944,4 @@ protected: } // namespace lldb_private -#endif // liblldb_RangeMap_h_ +#endif // LLDB_UTILITY_RANGEMAP_H Modified: lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp (original) +++ lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp Wed Mar 6 06:41:43 2019 @@ -16,7 +16,6 @@ #include "lldb/Core/Module.h" #include "lldb/Core/ModuleSpec.h" #include "lldb/Core/PluginManager.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Core/Section.h" #include "lldb/Host/FileSystem.h" #include "lldb/Symbol/DWARFCallFrameInfo.h" @@ -26,6 +25,7 @@ #include "lldb/Utility/ArchSpec.h" #include "lldb/Utility/DataBufferHeap.h" #include "lldb/Utility/Log.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/Status.h" #include "lldb/Utility/Stream.h" #include "lldb/Utility/Timer.h" Modified: lldb/trunk/source/Plugins/ObjectFile/JIT/ObjectFileJIT.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/ObjectFile/JIT/ObjectFileJIT.cpp?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/source/Plugins/ObjectFile/JIT/ObjectFileJIT.cpp (original) +++ lldb/trunk/source/Plugins/ObjectFile/JIT/ObjectFileJIT.cpp Wed Mar 6 06:41:43 2019 @@ -14,7 +14,6 @@ #include "lldb/Core/Module.h" #include "lldb/Core/ModuleSpec.h" #include "lldb/Core/PluginManager.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Core/Section.h" #include "lldb/Core/StreamFile.h" #include "lldb/Host/Host.h" @@ -28,6 +27,7 @@ #include "lldb/Utility/DataBufferHeap.h" #include "lldb/Utility/FileSpec.h" #include "lldb/Utility/Log.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/StreamString.h" #include "lldb/Utility/Timer.h" #include "lldb/Utility/UUID.h" Modified: lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp (original) +++ lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp Wed Mar 6 06:41:43 2019 @@ -17,7 +17,6 @@ #include "lldb/Core/Module.h" #include "lldb/Core/ModuleSpec.h" #include "lldb/Core/PluginManager.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Core/Section.h" #include "lldb/Core/StreamFile.h" #include "lldb/Host/Host.h" @@ -35,6 +34,7 @@ #include "lldb/Utility/DataBuffer.h" #include "lldb/Utility/FileSpec.h" #include "lldb/Utility/Log.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/RegisterValue.h" #include "lldb/Utility/Status.h" #include "lldb/Utility/StreamString.h" Modified: lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.h (original) +++ lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.h Wed Mar 6 06:41:43 2019 @@ -11,10 +11,10 @@ #include "lldb/Core/Address.h" #include "lldb/Core/FileSpecList.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Host/SafeMachO.h" #include "lldb/Symbol/ObjectFile.h" #include "lldb/Utility/FileSpec.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/UUID.h" //---------------------------------------------------------------------- Modified: lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h (original) +++ lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h Wed Mar 6 06:41:43 2019 @@ -10,10 +10,9 @@ #define SymbolFileDWARF_DWARFDebugAranges_h_ #include "DWARFDebugArangeSet.h" +#include "lldb/Utility/RangeMap.h" #include <list> -#include "lldb/Core/RangeMap.h" - class SymbolFileDWARF; class DWARFDebugAranges { Modified: lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h (original) +++ lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h Wed Mar 6 06:41:43 2019 @@ -19,9 +19,6 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/Support/Threading.h" -#include "lldb/Utility/Flags.h" - -#include "lldb/Core/RangeMap.h" #include "lldb/Core/UniqueCStringMap.h" #include "lldb/Core/dwarf.h" #include "lldb/Expression/DWARFExpression.h" @@ -29,6 +26,8 @@ #include "lldb/Symbol/SymbolContext.h" #include "lldb/Symbol/SymbolFile.h" #include "lldb/Utility/ConstString.h" +#include "lldb/Utility/Flags.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/lldb-private.h" #include "DWARFDataExtractor.h" Modified: lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp (original) +++ lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp Wed Mar 6 06:41:43 2019 @@ -12,9 +12,9 @@ #include "lldb/Core/Module.h" #include "lldb/Core/ModuleList.h" #include "lldb/Core/PluginManager.h" -#include "lldb/Core/RangeMap.h" #include "lldb/Core/Section.h" #include "lldb/Host/FileSystem.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/RegularExpression.h" #include "lldb/Utility/Timer.h" Modified: lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h (original) +++ lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h Wed Mar 6 06:41:43 2019 @@ -9,14 +9,13 @@ #ifndef SymbolFileDWARF_SymbolFileDWARFDebugMap_h_ #define SymbolFileDWARF_SymbolFileDWARFDebugMap_h_ +#include "lldb/Symbol/SymbolFile.h" +#include "lldb/Utility/RangeMap.h" +#include "llvm/Support/Chrono.h" #include <bitset> #include <map> #include <vector> -#include "lldb/Core/RangeMap.h" -#include "lldb/Symbol/SymbolFile.h" -#include "llvm/Support/Chrono.h" - #include "UniqueDWARFASTType.h" class SymbolFileDWARF; Modified: lldb/trunk/source/Target/Memory.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/source/Target/Memory.cpp?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/source/Target/Memory.cpp (original) +++ lldb/trunk/source/Target/Memory.cpp Wed Mar 6 06:41:43 2019 @@ -7,11 +7,10 @@ //===----------------------------------------------------------------------===// #include "lldb/Target/Memory.h" - -#include "lldb/Core/RangeMap.h" #include "lldb/Target/Process.h" #include "lldb/Utility/DataBufferHeap.h" #include "lldb/Utility/Log.h" +#include "lldb/Utility/RangeMap.h" #include "lldb/Utility/State.h" #include <cinttypes> Modified: lldb/trunk/unittests/Core/CMakeLists.txt URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/unittests/Core/CMakeLists.txt?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/unittests/Core/CMakeLists.txt (original) +++ lldb/trunk/unittests/Core/CMakeLists.txt Wed Mar 6 06:41:43 2019 @@ -1,7 +1,5 @@ add_lldb_unittest(LLDBCoreTests MangledTest.cpp - RangeMapTest.cpp - RangeTest.cpp RichManglingContextTest.cpp StreamCallbackTest.cpp Removed: lldb/trunk/unittests/Core/RangeMapTest.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/unittests/Core/RangeMapTest.cpp?rev=355508&view=auto ============================================================================== --- lldb/trunk/unittests/Core/RangeMapTest.cpp (original) +++ lldb/trunk/unittests/Core/RangeMapTest.cpp (removed) @@ -1,54 +0,0 @@ -//===-- RangeTest.cpp ----------------------------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#include "lldb/Core/RangeMap.h" -#include "gmock/gmock.h" -#include "gtest/gtest.h" - -using namespace lldb_private; - -using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>; -using EntryT = RangeDataVectorT::Entry; - -static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) { - return testing::Pointee(testing::Field(&EntryT::data, ID)); -} - -TEST(RangeDataVector, FindEntryThatContains) { - RangeDataVectorT Map; - uint32_t NextID = 0; - Map.Append(EntryT(0, 10, NextID++)); - Map.Append(EntryT(10, 10, NextID++)); - Map.Append(EntryT(20, 10, NextID++)); - Map.Sort(); - - EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0)); - EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0)); - EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1)); - EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1)); - EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2)); - EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2)); - EXPECT_THAT(Map.FindEntryThatContains(30), nullptr); -} - -TEST(RangeDataVector, FindEntryThatContains_Overlap) { - RangeDataVectorT Map; - uint32_t NextID = 0; - Map.Append(EntryT(0, 40, NextID++)); - Map.Append(EntryT(10, 20, NextID++)); - Map.Append(EntryT(20, 10, NextID++)); - Map.Sort(); - - // With overlapping intervals, the intention seems to be to return the first - // interval which contains the address. - EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0)); - - // However, this does not always succeed. - // TODO: This should probably return the range (0, 40) as well. - EXPECT_THAT(Map.FindEntryThatContains(35), nullptr); -} Removed: lldb/trunk/unittests/Core/RangeTest.cpp URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/unittests/Core/RangeTest.cpp?rev=355508&view=auto ============================================================================== --- lldb/trunk/unittests/Core/RangeTest.cpp (original) +++ lldb/trunk/unittests/Core/RangeTest.cpp (removed) @@ -1,329 +0,0 @@ -//===-- RangeTest.cpp ----------------------------------------*- C++ -*-===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#include "lldb/Core/RangeMap.h" - -#include <cstdint> -#include <type_traits> - -#include "gtest/gtest.h" - -using namespace lldb; -using namespace lldb_private; - -TEST(RangeTest, SizeTypes) { - Range<lldb::addr_t, uint32_t> r; - static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeBase())>::value, - "RangeBase type is not equal to the given one."); - static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeEnd())>::value, - "RangeEnd type is not equal to the given one."); - static_assert(std::is_same<uint32_t, decltype(r.GetByteSize())>::value, - "Size type is not equal to the given one."); -} - -typedef Range<lldb::addr_t, uint32_t> RangeT; - -TEST(RangeTest, DefaultConstructor) { - RangeT r; - EXPECT_FALSE(r.IsValid()); - EXPECT_EQ(0U, r.GetByteSize()); - EXPECT_EQ(0U, r.GetRangeBase()); - EXPECT_EQ(0U, r.GetRangeEnd()); -} - -TEST(RangeTest, Constructor) { - RangeT r(3, 5); - EXPECT_TRUE(r.IsValid()); - EXPECT_EQ(5U, r.GetByteSize()); - EXPECT_EQ(3U, r.GetRangeBase()); - EXPECT_EQ(8U, r.GetRangeEnd()); -} - -TEST(RangeTest, Copy) { - RangeT orig(3, 5); - RangeT r = orig; - EXPECT_TRUE(r.IsValid()); - EXPECT_EQ(5U, r.GetByteSize()); - EXPECT_EQ(3U, r.GetRangeBase()); - EXPECT_EQ(8U, r.GetRangeEnd()); -} - -TEST(RangeTest, Clear) { - RangeT r(3, 5); - r.Clear(); - EXPECT_TRUE(r == RangeT()); -} - -TEST(RangeTest, ClearWithStarAddress) { - RangeT r(3, 5); - r.Clear(4); - EXPECT_TRUE(r == RangeT(4, 0)); -} - -TEST(RangeTest, SetRangeBase) { - RangeT r(3, 5); - r.SetRangeBase(6); - EXPECT_EQ(6U, r.GetRangeBase()); - EXPECT_EQ(11U, r.GetRangeEnd()); - EXPECT_EQ(5U, r.GetByteSize()); -} - -TEST(RangeTest, Slide) { - RangeT r(3, 5); - r.Slide(1); - EXPECT_EQ(4U, r.GetRangeBase()); - EXPECT_EQ(9U, r.GetRangeEnd()); - EXPECT_EQ(5U, r.GetByteSize()); - - r.Slide(2); - EXPECT_EQ(6U, r.GetRangeBase()); - EXPECT_EQ(11U, r.GetRangeEnd()); - EXPECT_EQ(5U, r.GetByteSize()); -} - -TEST(RangeTest, SlideZero) { - RangeT r(3, 5); - r.Slide(0); - EXPECT_EQ(3U, r.GetRangeBase()); - EXPECT_EQ(8U, r.GetRangeEnd()); - EXPECT_EQ(5U, r.GetByteSize()); -} - -TEST(RangeTest, ContainsAddr) { - RangeT r(3, 5); - EXPECT_FALSE(r.Contains(0)); - EXPECT_FALSE(r.Contains(1)); - EXPECT_FALSE(r.Contains(2)); - EXPECT_TRUE(r.Contains(3)); - EXPECT_TRUE(r.Contains(4)); - EXPECT_TRUE(r.Contains(5)); - EXPECT_TRUE(r.Contains(6)); - EXPECT_TRUE(r.Contains(7)); - EXPECT_FALSE(r.Contains(8)); - EXPECT_FALSE(r.Contains(9)); - EXPECT_FALSE(r.Contains(10)); -} - -TEST(RangeTest, ContainsAddrInvalid) { - RangeT r; - EXPECT_FALSE(r.Contains(0)); - EXPECT_FALSE(r.Contains(1)); - EXPECT_FALSE(r.Contains(2)); - EXPECT_FALSE(r.Contains(3)); - EXPECT_FALSE(r.Contains(4)); -} - -TEST(RangeTest, ContainsEndInclusive) { - RangeT r(3, 5); - EXPECT_FALSE(r.ContainsEndInclusive(0)); - EXPECT_FALSE(r.ContainsEndInclusive(1)); - EXPECT_FALSE(r.ContainsEndInclusive(2)); - EXPECT_TRUE(r.ContainsEndInclusive(3)); - EXPECT_TRUE(r.ContainsEndInclusive(4)); - EXPECT_TRUE(r.ContainsEndInclusive(5)); - EXPECT_TRUE(r.ContainsEndInclusive(6)); - EXPECT_TRUE(r.ContainsEndInclusive(7)); - EXPECT_TRUE(r.ContainsEndInclusive(8)); - EXPECT_FALSE(r.ContainsEndInclusive(9)); - EXPECT_FALSE(r.ContainsEndInclusive(10)); -} - -TEST(RangeTest, ContainsEndInclusiveInvalid) { - RangeT r; - // FIXME: This is probably not intended. - EXPECT_TRUE(r.ContainsEndInclusive(0)); - - EXPECT_FALSE(r.ContainsEndInclusive(1)); - EXPECT_FALSE(r.ContainsEndInclusive(2)); -} - -TEST(RangeTest, ContainsRange) { - RangeT r(3, 5); - - // Range always contains itself. - EXPECT_TRUE(r.Contains(r)); - // Invalid range. - EXPECT_FALSE(r.Contains(RangeT())); - // Range starts and ends before. - EXPECT_FALSE(r.Contains(RangeT(0, 3))); - // Range starts before but contains beginning. - EXPECT_FALSE(r.Contains(RangeT(0, 4))); - // Range starts before but contains beginning and more. - EXPECT_FALSE(r.Contains(RangeT(0, 5))); - // Range starts before and contains the other. - EXPECT_FALSE(r.Contains(RangeT(0, 9))); - // Range is fully inside. - EXPECT_TRUE(r.Contains(RangeT(4, 3))); - // Range has same start, but not as large. - EXPECT_TRUE(r.Contains(RangeT(3, 4))); - // Range has same end, but starts earlier. - EXPECT_TRUE(r.Contains(RangeT(4, 4))); - // Range starts inside, but stops after the end of r. - EXPECT_FALSE(r.Contains(RangeT(4, 5))); - // Range starts directly after r. - EXPECT_FALSE(r.Contains(RangeT(8, 2))); - // Range starts directly after r. - EXPECT_FALSE(r.Contains(RangeT(9, 2))); - - // Invalid range with different start. - // FIXME: The first two probably not intended. - EXPECT_TRUE(r.Contains(RangeT(3, 0))); - EXPECT_TRUE(r.Contains(RangeT(4, 0))); - EXPECT_FALSE(r.Contains(RangeT(8, 0))); -} - -TEST(RangeTest, ContainsRangeStartingFromZero) { - RangeT r(0, 3); - EXPECT_TRUE(r.Contains(r)); - - // FIXME: This is probably not intended. - EXPECT_TRUE(r.Contains(RangeT())); -} - -TEST(RangeTest, Union) { - RangeT r(3, 5); - - // Ranges that we can't merge because it's not adjoin/intersecting. - EXPECT_FALSE(r.Union(RangeT(9, 1))); - // Check that we didn't modify our range. - EXPECT_EQ(r, RangeT(3, 5)); - - // Another range we can't merge, but before r. - EXPECT_FALSE(r.Union(RangeT(1, 1))); - EXPECT_EQ(r, RangeT(3, 5)); - - // Merge an adjoin range after. - EXPECT_TRUE(r.Union(RangeT(8, 2))); - EXPECT_EQ(r, RangeT(3, 7)); - - // Merge an adjoin range before. - EXPECT_TRUE(r.Union(RangeT(1, 2))); - EXPECT_EQ(r, RangeT(1, 9)); - - // Merge an intersecting range after. - EXPECT_TRUE(r.Union(RangeT(8, 3))); - EXPECT_EQ(r, RangeT(1, 10)); - - // Merge an intersecting range before. - EXPECT_TRUE(r.Union(RangeT(0, 1))); - EXPECT_EQ(r, RangeT(0, 11)); - - // Merge a few ranges inside that shouldn't do anything. - EXPECT_TRUE(r.Union(RangeT(0, 3))); - EXPECT_EQ(r, RangeT(0, 11)); - EXPECT_TRUE(r.Union(RangeT(5, 1))); - EXPECT_EQ(r, RangeT(0, 11)); - EXPECT_TRUE(r.Union(RangeT(9, 2))); - EXPECT_EQ(r, RangeT(0, 11)); -} - -TEST(RangeTest, DoesAdjoinOrIntersect) { - RangeT r(3, 4); - - EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(1, 1))); - EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(1, 2))); - EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(2, 2))); - EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(4, 2))); - EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(6, 2))); - EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(7, 2))); - EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(8, 2))); -} - -TEST(RangeTest, DoesIntersect) { - RangeT r(3, 4); - - EXPECT_FALSE(r.DoesIntersect(RangeT(1, 1))); - EXPECT_FALSE(r.DoesIntersect(RangeT(1, 2))); - EXPECT_TRUE(r.DoesIntersect(RangeT(2, 2))); - EXPECT_TRUE(r.DoesIntersect(RangeT(4, 2))); - EXPECT_TRUE(r.DoesIntersect(RangeT(6, 2))); - EXPECT_FALSE(r.DoesIntersect(RangeT(7, 2))); - EXPECT_FALSE(r.DoesIntersect(RangeT(8, 2))); -} - -TEST(RangeTest, LessThan) { - RangeT r(10, 20); - - // Equal range. - EXPECT_FALSE(r < RangeT(10, 20)); - EXPECT_FALSE(RangeT(10, 20) < r); - - auto expect_ordered_less_than = [](RangeT r1, RangeT r2) { - EXPECT_TRUE(r1 < r2); - EXPECT_FALSE(r2 < r1); - }; - - // Same start, but bigger size. - expect_ordered_less_than(r, RangeT(10, 21)); - - // Start before and ends before. - expect_ordered_less_than(RangeT(9, 20), r); - - // Start before and equal size. - expect_ordered_less_than(RangeT(9, 21), r); - - // Start before and bigger size. - expect_ordered_less_than(RangeT(9, 22), r); - - // Start after and ends before. - expect_ordered_less_than(r, RangeT(11, 18)); - - // Start after and equal size. - expect_ordered_less_than(r, RangeT(11, 19)); - - // Start after and bigger size. - expect_ordered_less_than(r, RangeT(11, 20)); -} - -TEST(RangeTest, Equal) { - RangeT r(10, 20); - - // Equal range. - EXPECT_TRUE(r == RangeT(10, 20)); - - // Same start, different size. - EXPECT_FALSE(r == RangeT(10, 21)); - - // Different start, same size. - EXPECT_FALSE(r == RangeT(9, 20)); - - // Different start, different size. - EXPECT_FALSE(r == RangeT(9, 21)); - EXPECT_FALSE(r == RangeT(11, 19)); -} - -TEST(RangeTest, NotEqual) { - RangeT r(10, 20); - - EXPECT_FALSE(r != RangeT(10, 20)); - - EXPECT_TRUE(r != RangeT(10, 21)); - EXPECT_TRUE(r != RangeT(9, 20)); - EXPECT_TRUE(r != RangeT(9, 21)); -} - -// Comparison tests for invalid ranges (size == 0). - -TEST(RangeTest, LessThanInvalid) { - EXPECT_TRUE(RangeT() < RangeT(1, 0)); - EXPECT_TRUE(RangeT() < RangeT(2, 0)); - EXPECT_TRUE(RangeT(1, 0) < RangeT(2, 0)); -} - -TEST(RangeTest, EqualInvalid) { - RangeT r; - EXPECT_TRUE(r == RangeT()); - // Another invalid range, but with a different start. - EXPECT_FALSE(r == RangeT(3, 0)); -} - -TEST(RangeTest, NotEqualInvalid) { - RangeT r; - EXPECT_FALSE(r != RangeT()); - EXPECT_FALSE(r == RangeT(3, 0)); -} Modified: lldb/trunk/unittests/Utility/CMakeLists.txt URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/unittests/Utility/CMakeLists.txt?rev=355509&r1=355508&r2=355509&view=diff ============================================================================== --- lldb/trunk/unittests/Utility/CMakeLists.txt (original) +++ lldb/trunk/unittests/Utility/CMakeLists.txt Wed Mar 6 06:41:43 2019 @@ -19,6 +19,8 @@ add_lldb_unittest(UtilityTests NameMatchesTest.cpp PredicateTest.cpp ProcessInfoTest.cpp + RangeMapTest.cpp + RangeTest.cpp RegisterValueTest.cpp ReproducerTest.cpp ReproducerInstrumentationTest.cpp Copied: lldb/trunk/unittests/Utility/RangeMapTest.cpp (from r355476, lldb/trunk/unittests/Core/RangeMapTest.cpp) URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/unittests/Utility/RangeMapTest.cpp?p2=lldb/trunk/unittests/Utility/RangeMapTest.cpp&p1=lldb/trunk/unittests/Core/RangeMapTest.cpp&r1=355476&r2=355509&rev=355509&view=diff ============================================================================== --- lldb/trunk/unittests/Core/RangeMapTest.cpp (original) +++ lldb/trunk/unittests/Utility/RangeMapTest.cpp Wed Mar 6 06:41:43 2019 @@ -6,7 +6,7 @@ // //===----------------------------------------------------------------------===// -#include "lldb/Core/RangeMap.h" +#include "lldb/Utility/RangeMap.h" #include "gmock/gmock.h" #include "gtest/gtest.h" Copied: lldb/trunk/unittests/Utility/RangeTest.cpp (from r355476, lldb/trunk/unittests/Core/RangeTest.cpp) URL: http://llvm.org/viewvc/llvm-project/lldb/trunk/unittests/Utility/RangeTest.cpp?p2=lldb/trunk/unittests/Utility/RangeTest.cpp&p1=lldb/trunk/unittests/Core/RangeTest.cpp&r1=355476&r2=355509&rev=355509&view=diff ============================================================================== --- lldb/trunk/unittests/Core/RangeTest.cpp (original) +++ lldb/trunk/unittests/Utility/RangeTest.cpp Wed Mar 6 06:41:43 2019 @@ -6,8 +6,7 @@ // //===----------------------------------------------------------------------===// -#include "lldb/Core/RangeMap.h" - +#include "lldb/Utility/RangeMap.h" #include <cstdint> #include <type_traits> _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
