This revision was automatically updated to reflect the committed changes.
Closed by commit rL259538: [NFC] Cleanup RangeMap.h (authored by tberghammer).
Changed prior to commit:
http://reviews.llvm.org/D16769?vs=46531&id=46673#toc
Repository:
rL LLVM
http://reviews.llvm.org/D16769
Files:
lldb/trunk/include/lldb/Core/RangeMap.h
lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp
Index: lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp
===================================================================
--- lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp
+++ lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp
@@ -107,6 +107,181 @@
uint32_t nlistCount;
};
+//----------------------------------------------------------------------
+// A simple range with data class where you get to define the type of
+// the range base "B", the type used for the range byte size "S", and
+// the type for the associated data "T".
+//----------------------------------------------------------------------
+template <typename B, typename T>
+struct AddressData
+{
+ typedef B BaseType;
+ typedef T DataType;
+
+ BaseType addr;
+ DataType data;
+
+ AddressData () :
+ addr (),
+ data ()
+ {
+ }
+
+ AddressData (B a, DataType d) :
+ addr (a),
+ data (d)
+ {
+ }
+
+ bool
+ operator < (const AddressData &rhs) const
+ {
+ if (this->addr == rhs.addr)
+ return this->data < rhs.data;
+ return this->addr < rhs.addr;
+ }
+
+ bool
+ operator == (const AddressData &rhs) const
+ {
+ return this->addr == rhs.addr &&
+ this->data == rhs.data;
+ }
+
+ bool
+ operator != (const AddressData &rhs) const
+ {
+ return this->addr != rhs.addr ||
+ this->data == rhs.data;
+ }
+};
+
+template <typename B, typename T, unsigned N>
+class AddressDataArray
+{
+public:
+ typedef AddressData<B,T> Entry;
+ typedef llvm::SmallVector<Entry, N> Collection;
+
+ AddressDataArray() = default;
+
+ ~AddressDataArray() = default;
+
+ void
+ Append (const Entry &entry)
+ {
+ m_entries.push_back (entry);
+ }
+
+ void
+ Sort ()
+ {
+ if (m_entries.size() > 1)
+ std::stable_sort (m_entries.begin(), m_entries.end());
+ }
+
+#ifdef ASSERT_RANGEMAP_ARE_SORTED
+ bool
+ IsSorted () const
+ {
+ typename Collection::const_iterator pos, end, prev;
+ // First we determine if we can combine any of the Entry objects so we
+ // don't end up allocating and making a new collection for no reason
+ for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
+ {
+ if (prev != end && *pos < *prev)
+ return false;
+ }
+ return true;
+ }
+#endif
+
+ void
+ Clear ()
+ {
+ m_entries.clear();
+ }
+
+ bool
+ IsEmpty () const
+ {
+ return m_entries.empty();
+ }
+
+ size_t
+ GetSize () const
+ {
+ return m_entries.size();
+ }
+
+ const Entry *
+ GetEntryAtIndex (size_t i) const
+ {
+ return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
+ }
+
+ // Clients must ensure that "i" is a valid index prior to calling this function
+ const Entry &
+ GetEntryRef (size_t i) const
+ {
+ return m_entries[i];
+ }
+
+ static bool
+ BaseLessThan (const Entry& lhs, const Entry& rhs)
+ {
+ return lhs.addr < rhs.addr;
+ }
+
+ Entry *
+ FindEntry (B addr, bool exact_match_only)
+ {
+#ifdef ASSERT_RANGEMAP_ARE_SORTED
+ assert (IsSorted());
+#endif
+ if ( !m_entries.empty() )
+ {
+ Entry entry;
+ entry.addr = addr;
+ typename Collection::iterator begin = m_entries.begin();
+ typename Collection::iterator end = m_entries.end();
+ typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
+
+ while(pos != begin && pos[-1].addr == addr)
+ --pos;
+
+ if (pos != end)
+ {
+ if (pos->addr == addr || !exact_match_only)
+ return &(*pos);
+ }
+ }
+ return nullptr;
+ }
+
+ const Entry *
+ FindNextEntry (const Entry *entry)
+ {
+ if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
+ return entry + 1;
+ return nullptr;
+ }
+
+ Entry *
+ Back()
+ {
+ return (m_entries.empty() ? nullptr : &m_entries.back());
+ }
+
+ const Entry *
+ Back() const
+ {
+ return (m_entries.empty() ? nullptr : &m_entries.back());
+ }
+
+protected:
+ Collection m_entries;
+};
class RegisterContextDarwin_x86_64_Mach : public RegisterContextDarwin_x86_64
{
Index: lldb/trunk/include/lldb/Core/RangeMap.h
===================================================================
--- lldb/trunk/include/lldb/Core/RangeMap.h
+++ lldb/trunk/include/lldb/Core/RangeMap.h
@@ -24,1478 +24,504 @@
// Uncomment to make sure all Range objects are sorted when needed
//#define ASSERT_RANGEMAP_ARE_SORTED
-namespace lldb_private {
-
- //----------------------------------------------------------------------
- // Templatized classes for dealing with generic ranges and also
- // collections of ranges, or collections of ranges that have associated
- // data.
- //----------------------------------------------------------------------
-
- //----------------------------------------------------------------------
- // A simple range class where you get to define the type of the range
- // base "B", and the type used for the range byte size "S".
- //----------------------------------------------------------------------
- template <typename B, typename S>
- struct Range
- {
- 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;
+namespace lldb_private
+{
+
+//----------------------------------------------------------------------
+// A simple range class where you get to define the type of the range
+// base "B", and the type used for the range byte size "S".
+//----------------------------------------------------------------------
+template <typename B, typename S> struct Range
+{
+ typedef B BaseType;
+ typedef S SizeType;
+
+ BaseType base;
+ SizeType size;
+
+ Range() : base(0), size(0) {}
+
+ Range(BaseType b, SizeType s) : base(b), size(s) {}
+
+ void
+ Clear(BaseType b = 0)
+ {
+ base = b;
+ size = 0;
+ }
+
+ BaseType
+ GetRangeBase() const
+ {
+ return base;
+ }
+
+ void
+ SetRangeBase(BaseType b)
+ {
+ base = b;
+ }
+
+ void
+ Slide(BaseType slide)
+ {
+ base += slide;
+ }
+
+ BaseType
+ GetRangeEnd() const
+ {
+ return base + size;
+ }
+
+ void
+ SetRangeEnd(BaseType end)
+ {
+ if (end > base)
+ size = end - base;
+ else
size = 0;
- }
+ }
- // Set the start value for the range, and keep the same size
- BaseType
- GetRangeBase () const
- {
- return base;
- }
-
- void
- SetRangeBase (BaseType b)
- {
- base = b;
- }
-
- void
- Slide (BaseType slide)
- {
- base += slide;
- }
-
- BaseType
- GetRangeEnd () const
- {
- return base + size;
- }
-
- void
- SetRangeEnd (BaseType end)
- {
- if (end > base)
- size = end - base;
- else
- size = 0;
- }
-
- SizeType
- GetByteSize () const
- {
- return size;
- }
-
- void
- SetByteSize (SizeType s)
- {
- size = s;
- }
-
- bool
- IsValid() const
- {
- return size > 0;
- }
-
- bool
- Contains (BaseType r) const
- {
- return (GetRangeBase() <= r) && (r < GetRangeEnd());
- }
-
- bool
- ContainsEndInclusive (BaseType r) const
- {
- return (GetRangeBase() <= r) && (r <= GetRangeEnd());
- }
-
- bool
- Contains (const Range& range) const
- {
- return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd());
- }
+ SizeType
+ GetByteSize() const
+ {
+ return size;
+ }
- // Returns true if the two ranges adjoing or intersect
- bool
- DoesAdjoinOrIntersect (const Range &rhs) const
- {
- const BaseType lhs_base = this->GetRangeBase();
- const BaseType rhs_base = rhs.GetRangeBase();
- const BaseType lhs_end = this->GetRangeEnd();
- const BaseType rhs_end = rhs.GetRangeEnd();
- bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
- return result;
- }
+ void
+ SetByteSize(SizeType s)
+ {
+ size = s;
+ }
- // Returns true if the two ranges intersect
- bool
- DoesIntersect (const Range &rhs) const
- {
- const BaseType lhs_base = this->GetRangeBase();
- const BaseType rhs_base = rhs.GetRangeBase();
- const BaseType lhs_end = this->GetRangeEnd();
- const BaseType rhs_end = rhs.GetRangeEnd();
- bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base);
- return result;
- }
+ bool
+ IsValid() const
+ {
+ return size > 0;
+ }
- bool
- operator < (const Range &rhs) const
- {
- if (base == rhs.base)
- return size < rhs.size;
- return base < rhs.base;
- }
-
- bool
- operator == (const Range &rhs) const
- {
- return base == rhs.base && size == rhs.size;
- }
-
- bool
- operator != (const Range &rhs) const
- {
- return base != rhs.base || size != rhs.size;
- }
- };
-
- //----------------------------------------------------------------------
- // A range array class where you get to define the type of the ranges
- // that the collection contains.
- //----------------------------------------------------------------------
-
- template <typename B, typename S, unsigned N>
- class RangeArray
- {
- public:
- typedef B BaseType;
- typedef S SizeType;
- typedef Range<B,S> Entry;
- typedef llvm::SmallVector<Entry, N> Collection;
+ bool
+ Contains(BaseType r) const
+ {
+ return (GetRangeBase() <= r) && (r < GetRangeEnd());
+ }
- RangeArray() = default;
+ bool
+ ContainsEndInclusive(BaseType r) const
+ {
+ return (GetRangeBase() <= r) && (r <= GetRangeEnd());
+ }
- ~RangeArray() = default;
+ bool
+ Contains(const Range &range) const
+ {
+ return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd());
+ }
- void
- Append (const Entry &entry)
- {
- m_entries.push_back (entry);
- }
-
- bool
- RemoveEntrtAtIndex (uint32_t idx)
- {
- if (idx < m_entries.size())
- {
- m_entries.erase (m_entries.begin() + idx);
- return true;
- }
- return false;
- }
-
- void
- Sort ()
- {
- if (m_entries.size() > 1)
- std::stable_sort (m_entries.begin(), m_entries.end());
- }
-
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- bool
- IsSorted () const
- {
- typename Collection::const_iterator pos, end, prev;
- // First we determine if we can combine any of the Entry objects so we
- // don't end up allocating and making a new collection for no reason
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && *pos < *prev)
- return false;
- }
- return true;
- }
-#endif
+ // Returns true if the two ranges adjoing or intersect
+ bool
+ DoesAdjoinOrIntersect(const Range &rhs) const
+ {
+ return GetRangeBase() <= rhs.GetRangeEnd() && GetRangeEnd() >= rhs.GetRangeBase();
+ }
- void
- CombineConsecutiveRanges ()
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- // Can't combine if ranges if we have zero or one range
- if (m_entries.size() > 1)
- {
- // The list should be sorted prior to calling this function
- typename Collection::iterator pos;
- typename Collection::iterator end;
- typename Collection::iterator prev;
- bool can_combine = false;
- // First we determine if we can combine any of the Entry objects so we
- // don't end up allocating and making a new collection for no reason
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
- {
- can_combine = true;
- break;
- }
- }
-
- // We we can combine at least one entry, then we make a new collection
- // and populate it accordingly, and then swap it into place.
- if (can_combine)
- {
- Collection minimal_ranges;
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
- minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
- else
- minimal_ranges.push_back (*pos);
- }
- // Use the swap technique in case our new vector is much smaller.
- // We must swap when using the STL because std::vector objects never
- // release or reduce the memory once it has been allocated/reserved.
- m_entries.swap (minimal_ranges);
- }
- }
- }
+ // Returns true if the two ranges intersect
+ bool
+ DoesIntersect(const Range &rhs) const
+ {
+ return GetRangeBase() < rhs.GetRangeEnd() && GetRangeEnd() > rhs.GetRangeBase();
+ }
- BaseType
- GetMinRangeBase (BaseType fail_value) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if (m_entries.empty())
- return fail_value;
- // m_entries must be sorted, so if we aren't empty, we grab the
- // first range's base
- return m_entries.front().GetRangeBase();
- }
+ bool
+ operator<(const Range &rhs) const
+ {
+ return base == rhs.base ? size < rhs.size : base < rhs.base;
+ }
- BaseType
- GetMaxRangeEnd (BaseType fail_value) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if (m_entries.empty())
- return fail_value;
- // m_entries must be sorted, so if we aren't empty, we grab the
- // last range's end
- return m_entries.back().GetRangeEnd();
- }
-
- void
- Slide (BaseType slide)
- {
- typename Collection::iterator pos, end;
- for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
- pos->Slide (slide);
- }
-
- void
- Clear ()
- {
- m_entries.clear();
- }
-
- bool
- IsEmpty () const
- {
- return m_entries.empty();
- }
-
- size_t
- GetSize () const
- {
- return m_entries.size();
- }
-
- const Entry *
- GetEntryAtIndex (size_t i) const
- {
- return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
- }
-
- // Clients must ensure that "i" is a valid index prior to calling this function
- const Entry &
- GetEntryRef (size_t i) const
- {
- return m_entries[i];
- }
+ bool
+ operator==(const Range &rhs) const
+ {
+ return base == rhs.base && size == rhs.size;
+ }
- Entry *
- Back()
- {
- return (m_entries.empty() ? nullptr : &m_entries.back());
- }
+ bool
+ operator!=(const Range &rhs) const
+ {
+ return !(*this == rhs);
+ }
+};
- const Entry *
- Back() const
- {
- return (m_entries.empty() ? nullptr : &m_entries.back());
- }
+//----------------------------------------------------------------------
+// A simple range with data class where you get to define the type of
+// the range base "B", the type used for the range byte size "S", and
+// the type for the associated data "T".
+//----------------------------------------------------------------------
+template <typename B, typename S, typename T> struct RangeData : public Range<B, S>
+{
+ typedef T DataType;
- static bool
- BaseLessThan (const Entry& lhs, const Entry& rhs)
- {
- return lhs.GetRangeBase() < rhs.GetRangeBase();
- }
-
- uint32_t
- FindEntryIndexThatContains (B addr) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if (!m_entries.empty())
- {
- Entry entry (addr, 1);
- typename Collection::const_iterator begin = m_entries.begin();
- typename Collection::const_iterator end = m_entries.end();
- typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
-
- if (pos != end && pos->Contains(addr))
- {
- return std::distance (begin, pos);
- }
- else if (pos != begin)
- {
- --pos;
- if (pos->Contains(addr))
- return std::distance (begin, pos);
- }
- }
- return UINT32_MAX;
- }
+ DataType data;
- const Entry *
- FindEntryThatContains (B addr) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if (!m_entries.empty())
- {
- Entry entry (addr, 1);
- typename Collection::const_iterator begin = m_entries.begin();
- typename Collection::const_iterator end = m_entries.end();
- typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
-
- if (pos != end && pos->Contains(addr))
- {
- return &(*pos);
- }
- else if (pos != begin)
- {
- --pos;
- if (pos->Contains(addr))
- {
- return &(*pos);
- }
- }
- }
- return nullptr;
- }
+ RangeData() = default;
- const Entry *
- FindEntryThatContains (const Entry &range) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if (!m_entries.empty())
- {
- typename Collection::const_iterator begin = m_entries.begin();
- typename Collection::const_iterator end = m_entries.end();
- typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
-
- if (pos != end && pos->Contains(range))
- {
- return &(*pos);
- }
- else if (pos != begin)
- {
- --pos;
- if (pos->Contains(range))
- {
- return &(*pos);
- }
- }
- }
- return nullptr;
- }
+ RangeData(B base, S size) : Range<B, S>(base, size), data() {}
- protected:
- Collection m_entries;
- };
+ RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
- template <typename B, typename S>
- class RangeVector
+ bool
+ operator<(const RangeData &rhs) const
{
- public:
- typedef B BaseType;
- typedef S SizeType;
- typedef Range<B,S> Entry;
- typedef std::vector<Entry> Collection;
+ if (this->base == rhs.base)
+ return Range<B, S>::operator<(rhs);
- RangeVector() = default;
+ return this->base < rhs.base;
+ }
- ~RangeVector() = default;
+ bool
+ operator==(const RangeData &rhs) const
+ {
+ return this->data == rhs.data && Range<B, S>::operator==(rhs);
+ }
- void
- Append (const Entry &entry)
- {
- m_entries.push_back (entry);
- }
-
- bool
- RemoveEntrtAtIndex (uint32_t idx)
- {
- if (idx < m_entries.size())
- {
- m_entries.erase (m_entries.begin() + idx);
- return true;
- }
+ bool
+ operator!=(const RangeData &rhs) const
+ {
+ return !(*this == rhs);
+ }
+};
+
+template <typename E, typename C> class RangeVectorBase
+{
+public:
+ typedef E Entry;
+ typedef C Collection;
+ typedef typename Entry::BaseType BaseType;
+ typedef typename Entry::SizeType SizeType;
+
+ void
+ Append(const Entry &entry)
+ {
+ m_entries.push_back(entry);
+ }
+
+ bool
+ RemoveEntrtAtIndex(uint32_t idx)
+ {
+ if (idx >= m_entries.size())
return false;
- }
-
- void
- Sort ()
- {
- if (m_entries.size() > 1)
- std::stable_sort (m_entries.begin(), m_entries.end());
- }
-
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- bool
- IsSorted () const
- {
- typename Collection::const_iterator pos, end, prev;
- // First we determine if we can combine any of the Entry objects so we
- // don't end up allocating and making a new collection for no reason
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && *pos < *prev)
- return false;
- }
- return true;
- }
-#endif
- void
- CombineConsecutiveRanges ()
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- // Can't combine if ranges if we have zero or one range
- if (m_entries.size() > 1)
- {
- // The list should be sorted prior to calling this function
- typename Collection::iterator pos;
- typename Collection::iterator end;
- typename Collection::iterator prev;
- bool can_combine = false;
- // First we determine if we can combine any of the Entry objects so we
- // don't end up allocating and making a new collection for no reason
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
- {
- can_combine = true;
- break;
- }
- }
-
- // We we can combine at least one entry, then we make a new collection
- // and populate it accordingly, and then swap it into place.
- if (can_combine)
- {
- Collection minimal_ranges;
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
- minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
- else
- minimal_ranges.push_back (*pos);
- }
- // Use the swap technique in case our new vector is much smaller.
- // We must swap when using the STL because std::vector objects never
- // release or reduce the memory once it has been allocated/reserved.
- m_entries.swap (minimal_ranges);
- }
- }
- }
+ m_entries.erase(m_entries.begin() + idx);
+ return true;
+ }
- BaseType
- GetMinRangeBase (BaseType fail_value) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if (m_entries.empty())
- return fail_value;
- // m_entries must be sorted, so if we aren't empty, we grab the
- // first range's base
- return m_entries.front().GetRangeBase();
- }
-
- BaseType
- GetMaxRangeEnd (BaseType fail_value) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if (m_entries.empty())
- return fail_value;
- // m_entries must be sorted, so if we aren't empty, we grab the
- // last range's end
- return m_entries.back().GetRangeEnd();
- }
-
- void
- Slide (BaseType slide)
- {
- typename Collection::iterator pos, end;
- for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
- pos->Slide (slide);
- }
-
- void
- Clear ()
- {
- m_entries.clear();
- }
+ void
+ Sort()
+ {
+ std::stable_sort(m_entries.begin(), m_entries.end());
+ }
- void
- Reserve (typename Collection::size_type size)
- {
- m_entries.reserve (size);
- }
+ void
+ CombineConsecutiveRanges()
+ {
+ VerifySorted();
- bool
- IsEmpty () const
- {
- return m_entries.empty();
- }
-
- size_t
- GetSize () const
- {
- return m_entries.size();
- }
-
- const Entry *
- GetEntryAtIndex (size_t i) const
- {
- return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
- }
-
- // Clients must ensure that "i" is a valid index prior to calling this function
- const Entry &
- GetEntryRef (size_t i) const
- {
- return m_entries[i];
- }
-
- Entry *
- Back()
- {
- return (m_entries.empty() ? nullptr : &m_entries.back());
- }
-
- const Entry *
- Back() const
- {
- return (m_entries.empty() ? nullptr : &m_entries.back());
- }
-
- static bool
- BaseLessThan (const Entry& lhs, const Entry& rhs)
- {
- return lhs.GetRangeBase() < rhs.GetRangeBase();
- }
-
- uint32_t
- FindEntryIndexThatContains (B addr) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if (!m_entries.empty())
- {
- Entry entry (addr, 1);
- typename Collection::const_iterator begin = m_entries.begin();
- typename Collection::const_iterator end = m_entries.end();
- typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
-
- if (pos != end && pos->Contains(addr))
- {
- return std::distance (begin, pos);
- }
- else if (pos != begin)
- {
- --pos;
- if (pos->Contains(addr))
- return std::distance (begin, pos);
- }
- }
- return UINT32_MAX;
- }
-
- const Entry *
- FindEntryThatContains (B addr) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if (!m_entries.empty())
- {
- Entry entry (addr, 1);
- typename Collection::const_iterator begin = m_entries.begin();
- typename Collection::const_iterator end = m_entries.end();
- typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
-
- if (pos != end && pos->Contains(addr))
- {
- return &(*pos);
- }
- else if (pos != begin)
- {
- --pos;
- if (pos->Contains(addr))
- {
- return &(*pos);
- }
- }
- }
- return nullptr;
- }
-
- const Entry *
- FindEntryThatContains (const Entry &range) const
+ // Can't combine ranges if we have zero or one range
+ if (m_entries.size() <= 1)
+ return;
+
+ // First we determine if we can combine any of the Entry objects so we don't end up
+ // allocating and making a new collection for no reason
+ bool can_combine = false;
+ for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
{
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if (!m_entries.empty())
+ if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
{
- typename Collection::const_iterator begin = m_entries.begin();
- typename Collection::const_iterator end = m_entries.end();
- typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
-
- if (pos != end && pos->Contains(range))
- {
- return &(*pos);
- }
- else if (pos != begin)
- {
- --pos;
- if (pos->Contains(range))
- {
- return &(*pos);
- }
- }
+ can_combine = true;
+ break;
}
- return nullptr;
- }
-
- protected:
- Collection m_entries;
- };
-
- //----------------------------------------------------------------------
- // A simple range with data class where you get to define the type of
- // the range base "B", the type used for the range byte size "S", and
- // the type for the associated data "T".
- //----------------------------------------------------------------------
- template <typename B, typename S, typename T>
- struct RangeData : public Range<B,S>
- {
- typedef T DataType;
-
- DataType data;
-
- RangeData () :
- Range<B,S> (),
- data ()
- {
- }
-
- RangeData (B base, S size) :
- Range<B,S> (base, size),
- data ()
- {
- }
-
- RangeData (B base, S size, DataType d) :
- Range<B,S> (base, size),
- data (d)
- {
}
-
- bool
- operator < (const RangeData &rhs) const
+
+ // We we can combine at least one entry, then we make a new collection and populate it
+ // accordingly, and then swap it into place.
+ if (can_combine)
{
- if (this->base == rhs.base)
+ Collection minimal_ranges;
+ for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
{
- if (this->size == rhs.size)
- return this->data < rhs.data;
+ if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
+ minimal_ranges.back().SetRangeEnd(std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
else
- return this->size < rhs.size;
+ minimal_ranges.push_back(*pos);
}
- return this->base < rhs.base;
- }
-
- bool
- operator == (const RangeData &rhs) const
- {
- return this->GetRangeBase() == rhs.GetRangeBase() &&
- this->GetByteSize() == rhs.GetByteSize() &&
- this->data == rhs.data;
- }
-
- bool
- operator != (const RangeData &rhs) const
- {
- return this->GetRangeBase() != rhs.GetRangeBase() ||
- this->GetByteSize() != rhs.GetByteSize() ||
- this->data != rhs.data;
+
+ // Use the swap technique in case our new vector is much smaller. We must swap when
+ // using the STL because std::vector objects never release or reduce the memory once it
+ // has been allocated/reserved.
+ m_entries.swap(minimal_ranges);
}
- };
-
- template <typename B, typename S, typename T, unsigned N>
- class RangeDataArray
+ }
+
+ BaseType
+ GetMinRangeBase(BaseType fail_value) const
{
- public:
- typedef RangeData<B,S,T> Entry;
- typedef llvm::SmallVector<Entry, N> Collection;
+ VerifySorted();
- RangeDataArray() = default;
+ if (m_entries.empty())
+ return fail_value;
- ~RangeDataArray() = default;
+ // m_entries must be sorted, so if we aren't empty, we grab the first range's base
+ return m_entries.front().GetRangeBase();
+ }
- void
- Append (const Entry &entry)
- {
- m_entries.push_back (entry);
- }
-
- void
- Sort ()
- {
- if (m_entries.size() > 1)
- std::stable_sort (m_entries.begin(), m_entries.end());
- }
-
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- bool
- IsSorted () const
- {
- typename Collection::const_iterator pos, end, prev;
- // First we determine if we can combine any of the Entry objects so we
- // don't end up allocating and making a new collection for no reason
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && *pos < *prev)
- return false;
- }
- return true;
- }
-#endif
+ BaseType
+ GetMaxRangeEnd(BaseType fail_value) const
+ {
+ VerifySorted();
- void
- CombineConsecutiveEntriesWithEqualData ()
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- typename Collection::iterator pos;
- typename Collection::iterator end;
- typename Collection::iterator prev;
- bool can_combine = false;
- // First we determine if we can combine any of the Entry objects so we
- // don't end up allocating and making a new collection for no reason
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && prev->data == pos->data)
- {
- can_combine = true;
- break;
- }
- }
-
- // We we can combine at least one entry, then we make a new collection
- // and populate it accordingly, and then swap it into place.
- if (can_combine)
- {
- Collection minimal_ranges;
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && prev->data == pos->data)
- minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
- else
- minimal_ranges.push_back (*pos);
- }
- // Use the swap technique in case our new vector is much smaller.
- // We must swap when using the STL because std::vector objects never
- // release or reduce the memory once it has been allocated/reserved.
- m_entries.swap (minimal_ranges);
- }
- }
-
- void
- Clear ()
- {
- m_entries.clear();
- }
-
- bool
- IsEmpty () const
- {
- return m_entries.empty();
- }
-
- size_t
- GetSize () const
- {
- return m_entries.size();
- }
-
- const Entry *
- GetEntryAtIndex (size_t i) const
- {
- return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
- }
+ if (m_entries.empty())
+ return fail_value;
- // Clients must ensure that "i" is a valid index prior to calling this function
- const Entry &
- GetEntryRef (size_t i) const
- {
- return m_entries[i];
- }
+ // m_entries must be sorted, so if we aren't empty, we grab the last range's end
+ return m_entries.back().GetRangeEnd();
+ }
- static bool
- BaseLessThan (const Entry& lhs, const Entry& rhs)
- {
- return lhs.GetRangeBase() < rhs.GetRangeBase();
- }
-
- uint32_t
- FindEntryIndexThatContains (B addr) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if ( !m_entries.empty() )
- {
- Entry entry (addr, 1);
- typename Collection::const_iterator begin = m_entries.begin();
- typename Collection::const_iterator end = m_entries.end();
- typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
-
- if (pos != end && pos->Contains(addr))
- {
- return std::distance (begin, pos);
- }
- else if (pos != begin)
- {
- --pos;
- if (pos->Contains(addr))
- return std::distance (begin, pos);
- }
- }
+ void
+ Slide(BaseType slide)
+ {
+ for (auto pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
+ pos->Slide(slide);
+ }
+
+ void
+ Clear()
+ {
+ m_entries.clear();
+ }
+
+ bool
+ IsEmpty() const
+ {
+ return m_entries.empty();
+ }
+
+ size_t
+ GetSize() const
+ {
+ return m_entries.size();
+ }
+
+ Entry *
+ GetEntryAtIndex(size_t i)
+ {
+ return i < m_entries.size() ? &m_entries[i] : nullptr;
+ }
+
+ const Entry *
+ GetEntryAtIndex(size_t i) const
+ {
+ return i < m_entries.size() ? &m_entries[i] : nullptr;
+ }
+
+ // Clients must ensure that "i" is a valid index prior to calling this function
+ const Entry &
+ GetEntryRef(size_t i) const
+ {
+ return m_entries[i];
+ }
+
+ Entry *
+ Back()
+ {
+ return m_entries.empty() ? nullptr : &m_entries.back();
+ }
+
+ const Entry *
+ Back() const
+ {
+ return m_entries.empty() ? nullptr : &m_entries.back();
+ }
+
+ uint32_t
+ FindEntryIndexThatContains(const Entry &range) const
+ {
+ VerifySorted();
+
+ if (m_entries.empty())
return UINT32_MAX;
- }
- Entry *
- FindEntryThatContains (B addr)
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if ( !m_entries.empty() )
- {
- Entry entry;
- entry.SetRangeBase(addr);
- entry.SetByteSize(1);
- typename Collection::iterator begin = m_entries.begin();
- typename Collection::iterator end = m_entries.end();
- typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
-
- if (pos != end && pos->Contains(addr))
- {
- return &(*pos);
- }
- else if (pos != begin)
- {
- --pos;
- if (pos->Contains(addr))
- {
- return &(*pos);
- }
- }
- }
- return nullptr;
- }
+ auto begin = m_entries.begin(), end = m_entries.end(), pos = std::lower_bound(begin, end, range, BaseLessThan);
+ if (pos != end && pos->Contains(range))
+ return std::distance(begin, pos);
- const Entry *
- FindEntryThatContains (B addr) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if ( !m_entries.empty() )
- {
- Entry entry;
- entry.SetRangeBase(addr);
- entry.SetByteSize(1);
- typename Collection::const_iterator begin = m_entries.begin();
- typename Collection::const_iterator end = m_entries.end();
- typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
-
- if (pos != end && pos->Contains(addr))
- {
- return &(*pos);
- }
- else if (pos != begin)
- {
- --pos;
- if (pos->Contains(addr))
- {
- return &(*pos);
- }
- }
- }
- return nullptr;
- }
-
- const Entry *
- FindEntryThatContains (const Entry &range) const
+ if (pos != begin)
{
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if ( !m_entries.empty() )
- {
- typename Collection::const_iterator begin = m_entries.begin();
- typename Collection::const_iterator end = m_entries.end();
- typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
-
- if (pos != end && pos->Contains(range))
- {
- return &(*pos);
- }
- else if (pos != begin)
- {
- --pos;
- if (pos->Contains(range))
- {
- return &(*pos);
- }
- }
- }
- return nullptr;
- }
-
- Entry *
- Back()
- {
- return (m_entries.empty() ? nullptr : &m_entries.back());
+ --pos;
+ if (pos->Contains(range))
+ return std::distance(begin, pos);
}
+ return UINT32_MAX;
+ }
- const Entry *
- Back() const
- {
- return (m_entries.empty() ? nullptr : &m_entries.back());
- }
+ uint32_t
+ FindEntryIndexThatContains(BaseType addr) const
+ {
+ return FindEntryIndexThatContains(Entry(addr, 1));
+ }
- protected:
- Collection m_entries;
- };
+ Entry *
+ FindEntryThatContains(BaseType addr)
+ {
+ return GetEntryAtIndex(FindEntryIndexThatContains(addr));
+ }
- // Same as RangeDataArray, but uses std::vector as to not
- // require static storage of N items in the class itself
- template <typename B, typename S, typename T>
- class RangeDataVector
+ const Entry *
+ FindEntryThatContains(BaseType addr) const
{
- public:
- typedef RangeData<B,S,T> Entry;
- typedef std::vector<Entry> Collection;
+ return GetEntryAtIndex(FindEntryIndexThatContains(addr));
+ }
- RangeDataVector() = default;
+ const Entry *
+ FindEntryThatContains(const Entry &range) const
+ {
+ return GetEntryAtIndex(FindEntryIndexThatContains(range));
+ }
- ~RangeDataVector() = default;
+ void
+ Reserve(size_t size)
+ {
+ m_entries.resize(size);
+ }
- void
- Append (const Entry &entry)
- {
- m_entries.push_back (entry);
- }
-
- void
- Sort ()
- {
- if (m_entries.size() > 1)
- std::stable_sort (m_entries.begin(), m_entries.end());
- }
-
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- bool
- IsSorted () const
- {
- typename Collection::const_iterator pos, end, prev;
- // First we determine if we can combine any of the Entry objects so we
- // don't end up allocating and making a new collection for no reason
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && *pos < *prev)
- return false;
- }
- return true;
- }
-#endif
-
- void
- CombineConsecutiveEntriesWithEqualData ()
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- typename Collection::iterator pos;
- typename Collection::iterator end;
- typename Collection::iterator prev;
- bool can_combine = false;
- // First we determine if we can combine any of the Entry objects so we
- // don't end up allocating and making a new collection for no reason
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && prev->data == pos->data)
- {
- can_combine = true;
- break;
- }
- }
-
- // We we can combine at least one entry, then we make a new collection
- // and populate it accordingly, and then swap it into place.
- if (can_combine)
- {
- Collection minimal_ranges;
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
- {
- if (prev != end && prev->data == pos->data)
- minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
- else
- minimal_ranges.push_back (*pos);
- }
- // Use the swap technique in case our new vector is much smaller.
- // We must swap when using the STL because std::vector objects never
- // release or reduce the memory once it has been allocated/reserved.
- m_entries.swap (minimal_ranges);
- }
- }
-
- // Calculate the byte size of ranges with zero byte sizes by finding
- // the next entry with a base address > the current base address
- void
- CalculateSizesOfZeroByteSizeRanges ()
+ // Calculate the byte size of ranges with zero byte sizes by finding the next entry with a
+ // base address > the current base address
+ void
+ CalculateSizesOfZeroByteSizeRanges()
+ {
+ VerifySorted();
+
+ for (auto pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
{
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- typename Collection::iterator pos;
- typename Collection::iterator end;
- typename Collection::iterator next;
- for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
+ if (pos->GetByteSize() == 0)
{
- if (pos->GetByteSize() == 0)
+ // Watch out for multiple entries with same address and make sure we find an entry
+ //that is greater than the current base address before we use that for the size
+ auto curr_base = pos->GetRangeBase();
+ for (auto next = pos + 1; next != end; ++next)
{
- // Watch out for multiple entries with same address and make sure
- // we find an entry that is greater than the current base address
- // before we use that for the size
- auto curr_base = pos->GetRangeBase();
- for (next = pos + 1; next != end; ++next)
+ auto next_base = next->GetRangeBase();
+ if (next_base > curr_base)
{
- auto next_base = next->GetRangeBase();
- if (next_base > curr_base)
- {
- pos->SetByteSize (next_base - curr_base);
- break;
- }
+ pos->SetByteSize(next_base - curr_base);
+ break;
}
}
}
}
-
- void
- Clear ()
- {
- m_entries.clear();
- }
-
- void
- Reserve (typename Collection::size_type size)
- {
- m_entries.resize (size);
- }
-
- 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.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;
- }
+ }
- uint32_t
- FindEntryIndexesThatContain(B addr, std::vector<uint32_t> &indexes) const
- {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
+ uint32_t
+ FindEntryIndexesThatContain(BaseType addr, std::vector<uint32_t> &indexes) const
+ {
+ VerifySorted();
- if (!m_entries.empty())
- {
- typename Collection::const_iterator pos;
- for (const auto &entry : m_entries)
- {
- if (entry.Contains(addr))
- indexes.push_back(entry.data);
- }
- }
- return indexes.size() ;
- }
-
- Entry *
- FindEntryThatContains (B addr)
+ if (!m_entries.empty())
{
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if ( !m_entries.empty() )
+ for (const auto &entry : m_entries)
{
- 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);
+ if (entry.Contains(addr))
+ indexes.push_back(entry.data);
}
- return nullptr;
}
+ return indexes.size();
+ }
- 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;
+ static bool
+ BaseLessThan(const Entry &lhs, const Entry &rhs)
+ {
+ return lhs.GetRangeBase() < rhs.GetRangeBase();
+ }
- if (pos != end && pos->Contains(addr))
- return &(*pos);
- }
- return nullptr;
- }
-
- const Entry *
- FindEntryThatContains (const Entry &range) const
- {
+protected:
+ void
+ VerifySorted() const
+ {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
+ for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
+ assert(prev == end || *pos >= *prev);
#endif
- if ( !m_entries.empty() )
- {
- typename Collection::const_iterator begin = m_entries.begin();
- typename Collection::const_iterator end = m_entries.end();
- typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
-
- while(pos != begin && pos[-1].Contains(range))
- --pos;
+ }
- if (pos != end && pos->Contains(range))
- return &(*pos);
- }
- return nullptr;
- }
-
- Entry *
- Back()
- {
- return (m_entries.empty() ? nullptr : &m_entries.back());
- }
-
- const Entry *
- Back() const
- {
- return (m_entries.empty() ? nullptr : &m_entries.back());
- }
-
- protected:
- Collection m_entries;
- };
-
- //----------------------------------------------------------------------
- // A simple range with data class where you get to define the type of
- // the range base "B", the type used for the range byte size "S", and
- // the type for the associated data "T".
- //----------------------------------------------------------------------
- template <typename B, typename T>
- struct AddressData
- {
- typedef B BaseType;
- typedef T DataType;
-
- BaseType addr;
- DataType data;
-
- AddressData () :
- addr (),
- data ()
- {
- }
-
- AddressData (B a, DataType d) :
- addr (a),
- data (d)
- {
- }
-
- bool
- operator < (const AddressData &rhs) const
- {
- if (this->addr == rhs.addr)
- return this->data < rhs.data;
- return this->addr < rhs.addr;
- }
-
- bool
- operator == (const AddressData &rhs) const
- {
- return this->addr == rhs.addr &&
- this->data == rhs.data;
- }
-
- bool
- operator != (const AddressData &rhs) const
- {
- return this->addr != rhs.addr ||
- this->data == rhs.data;
- }
- };
+ Collection m_entries;
+};
- template <typename B, typename T, unsigned N>
- class AddressDataArray
+template <typename E, typename S> class RangeDataVectorBase : public RangeVectorBase<E, S>
+{
+public:
+ void
+ CombineConsecutiveEntriesWithEqualData()
{
- public:
- typedef AddressData<B,T> Entry;
- typedef llvm::SmallVector<Entry, N> Collection;
-
- AddressDataArray() = default;
+ VerifySorted();
- ~AddressDataArray() = default;
-
- void
- Append (const Entry &entry)
- {
- m_entries.push_back (entry);
- }
-
- void
- Sort ()
- {
- if (m_entries.size() > 1)
- std::stable_sort (m_entries.begin(), m_entries.end());
- }
-
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- bool
- IsSorted () const
+ // First we determine if we can combine any of the Entry objects so we
+ // don't end up allocating and making a new collection for no reason
+ bool can_combine = false;
+ for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
{
- typename Collection::const_iterator pos, end, prev;
- // First we determine if we can combine any of the Entry objects so we
- // don't end up allocating and making a new collection for no reason
- for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
+ if (prev != end && prev->data == pos->data)
{
- if (prev != end && *pos < *prev)
- return false;
+ can_combine = true;
+ break;
}
- return true;
- }
-#endif
-
- void
- Clear ()
- {
- m_entries.clear();
- }
-
- bool
- IsEmpty () const
- {
- return m_entries.empty();
- }
-
- size_t
- GetSize () const
- {
- return m_entries.size();
- }
-
- const Entry *
- GetEntryAtIndex (size_t i) const
- {
- return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
- }
-
- // Clients must ensure that "i" is a valid index prior to calling this function
- const Entry &
- GetEntryRef (size_t i) const
- {
- return m_entries[i];
}
- static bool
- BaseLessThan (const Entry& lhs, const Entry& rhs)
- {
- return lhs.addr < rhs.addr;
- }
-
- Entry *
- FindEntry (B addr, bool exact_match_only)
+ // 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)
{
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
- assert (IsSorted());
-#endif
- if ( !m_entries.empty() )
+ Collection minimal_ranges;
+ for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
{
- Entry entry;
- entry.addr = addr;
- typename Collection::iterator begin = m_entries.begin();
- typename Collection::iterator end = m_entries.end();
- typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
-
- while(pos != begin && pos[-1].addr == addr)
- --pos;
-
- if (pos != end)
- {
- if (pos->addr == addr || !exact_match_only)
- return &(*pos);
- }
+ if (prev != end && prev->data == pos->data)
+ minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
+ else
+ minimal_ranges.push_back(*pos);
}
- return nullptr;
- }
-
- const Entry *
- FindNextEntry (const Entry *entry)
- {
- if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
- return entry + 1;
- return nullptr;
- }
-
- Entry *
- Back()
- {
- return (m_entries.empty() ? nullptr : &m_entries.back());
- }
-
- const Entry *
- Back() const
- {
- return (m_entries.empty() ? nullptr : &m_entries.back());
- }
- protected:
- Collection m_entries;
- };
+ // Use the swap technique in case our new vector is much smaller.
+ // We must swap when using the STL because std::vector objects never
+ // release or reduce the memory once it has been allocated/reserved.
+ m_entries.swap(minimal_ranges);
+ }
+ }
+
+protected:
+ using typename RangeVectorBase<E, S>::Collection;
+ using RangeVectorBase<E, S>::VerifySorted;
+ using RangeVectorBase<E, S>::m_entries;
+};
+
+// Use public inheritance to define these types instead of alias templates because MSVC 2013
+// generates incorrect code for alias templates.
+
+template <typename B, typename S> class RangeVector : public RangeVectorBase<Range<B, S>, std::vector<Range<B, S>>>
+{
+};
+
+template <typename B, typename S, size_t N>
+class RangeArray : public RangeVectorBase<Range<B, S>, llvm::SmallVector<Range<B, S>, N>>
+{
+};
+
+template <typename B, typename S, typename T>
+class RangeDataVector : public RangeDataVectorBase<RangeData<B, S, T>, std::vector<RangeData<B, S, T>>>
+{
+};
+
+template <typename B, typename S, typename T, size_t N>
+class RangeDataArray : public RangeDataVectorBase<RangeData<B, S, T>, llvm::SmallVector<RangeData<B, S, T>, N>>
+{
+};
} // namespace lldb_private
_______________________________________________
lldb-commits mailing list
lldb-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
