| //===-- RangeMap.h ----------------------------------------------*- C++ -*-===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef liblldb_RangeMap_h_ |
| #define liblldb_RangeMap_h_ |
| |
| #include <vector> |
| |
| #include "lldb/lldb-private.h" |
| #include "llvm/ADT/SmallVector.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; |
| } |
| |
| 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()); |
| } |
| |
| bool |
| Overlap (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 () : |
| m_entries () |
| { |
| } |
| |
| ~RangeArray() |
| { |
| } |
| |
| 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 |
| 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->Overlap(*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->Overlap(*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 |
| { |
| if (i<m_entries.size()) |
| return &m_entries[i]; |
| return NULL; |
| } |
| |
| // 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() |
| { |
| if (m_entries.empty()) |
| return NULL; |
| return &m_entries.back(); |
| } |
| |
| const Entry * |
| Back() const |
| { |
| if (m_entries.empty()) |
| return NULL; |
| return &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 NULL; |
| } |
| |
| 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 NULL; |
| } |
| |
| 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 () : |
| m_entries () |
| { |
| } |
| |
| ~RangeVector() |
| { |
| } |
| |
| 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 |
| 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->Overlap(*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->Overlap(*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 |
| { |
| if (i<m_entries.size()) |
| return &m_entries[i]; |
| return NULL; |
| } |
| |
| // 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() |
| { |
| if (m_entries.empty()) |
| return NULL; |
| return &m_entries.back(); |
| } |
| |
| const Entry * |
| Back() const |
| { |
| if (m_entries.empty()) |
| return NULL; |
| return &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 NULL; |
| } |
| |
| 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 NULL; |
| } |
| |
| 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 |
| { |
| 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> |
| class RangeDataArray |
| { |
| public: |
| typedef RangeData<B,S,T> Entry; |
| typedef llvm::SmallVector<Entry, N> Collection; |
| |
| |
| RangeDataArray () |
| { |
| } |
| |
| ~RangeDataArray() |
| { |
| } |
| |
| 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 |
| { |
| if (i<m_entries.size()) |
| return &m_entries[i]; |
| return NULL; |
| } |
| |
| // 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() ) |
| { |
| 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; |
| } |
| |
| 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 NULL; |
| } |
| 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 NULL; |
| } |
| |
| 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 NULL; |
| } |
| |
| Entry * |
| Back() |
| { |
| if (!m_entries.empty()) |
| return &m_entries.back(); |
| return NULL; |
| } |
| |
| const Entry * |
| Back() const |
| { |
| if (!m_entries.empty()) |
| return &m_entries.back(); |
| return NULL; |
| } |
| |
| protected: |
| Collection m_entries; |
| }; |
| |
| // 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 |
| { |
| public: |
| typedef RangeData<B,S,T> Entry; |
| typedef std::vector<Entry> Collection; |
| |
| RangeDataVector () |
| { |
| } |
| |
| ~RangeDataVector() |
| { |
| } |
| |
| 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 () |
| { |
| #ifdef ASSERT_RANGEMAP_ARE_SORTED |
| assert (IsSorted()); |
| #endif |
| typename Collection::iterator pos; |
| typename Collection::iterator end; |
| typename Collection::iterator next; |
| for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) |
| { |
| if (pos->GetByteSize() == 0) |
| { |
| // Watch out for multiple entries with same address and make sure |
| // we find an entry that is greater than the current base address |
| // before we use that for the size |
| auto curr_base = pos->GetRangeBase(); |
| for (next = pos + 1; next != end; ++next) |
| { |
| auto next_base = next->GetRangeBase(); |
| if (next_base > curr_base) |
| { |
| pos->SetByteSize (next_base - curr_base); |
| break; |
| } |
| } |
| } |
| } |
| |
| } |
| |
| void |
| Clear () |
| { |
| m_entries.clear(); |
| } |
| |
| void |
| Reserve (typename Collection::size_type size) |
| { |
| m_entries.resize (size); |
| } |
| |
| bool |
| IsEmpty () const |
| { |
| return m_entries.empty(); |
| } |
| |
| size_t |
| GetSize () const |
| { |
| return m_entries.size(); |
| } |
| |
| const Entry * |
| GetEntryAtIndex (size_t i) const |
| { |
| if (i<m_entries.size()) |
| return &m_entries[i]; |
| return NULL; |
| } |
| |
| // 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() ) |
| { |
| Entry entry (addr, 1); |
| typename Collection::const_iterator begin = m_entries.begin(); |
| typename Collection::const_iterator end = m_entries.end(); |
| typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); |
| |
| while(pos != begin && pos[-1].Contains(addr)) |
| --pos; |
| |
| if (pos != end && pos->Contains(addr)) |
| return std::distance (begin, pos); |
| } |
| return UINT32_MAX; |
| } |
| |
| 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); |
| |
| while(pos != begin && pos[-1].Contains(addr)) |
| --pos; |
| |
| if (pos != end && pos->Contains(addr)) |
| return &(*pos); |
| } |
| return NULL; |
| } |
| 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 NULL; |
| } |
| |
| 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 NULL; |
| } |
| |
| Entry * |
| Back() |
| { |
| if (!m_entries.empty()) |
| return &m_entries.back(); |
| return NULL; |
| } |
| |
| const Entry * |
| Back() const |
| { |
| if (!m_entries.empty()) |
| return &m_entries.back(); |
| return NULL; |
| } |
| |
| 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 () |
| { |
| } |
| |
| ~AddressDataArray() |
| { |
| } |
| |
| 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 |
| { |
| if (i<m_entries.size()) |
| return &m_entries[i]; |
| return NULL; |
| } |
| |
| // 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 NULL; |
| } |
| |
| const Entry * |
| FindNextEntry (const Entry *entry) |
| { |
| if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) |
| return entry + 1; |
| return NULL; |
| } |
| |
| Entry * |
| Back() |
| { |
| if (!m_entries.empty()) |
| return &m_entries.back(); |
| return NULL; |
| } |
| |
| const Entry * |
| Back() const |
| { |
| if (!m_entries.empty()) |
| return &m_entries.back(); |
| return NULL; |
| } |
| |
| protected: |
| Collection m_entries; |
| }; |
| |
| } // namespace lldb_private |
| |
| #endif // liblldb_RangeMap_h_ |
