1 //===-- RangeMap.h ----------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef liblldb_RangeMap_h_
11 #define liblldb_RangeMap_h_
18 // Other libraries and framework includes
19 #include "llvm/ADT/SmallVector.h"
22 #include "lldb/lldb-private.h"
24 // Uncomment to make sure all Range objects are sorted when needed
25 //#define ASSERT_RANGEMAP_ARE_SORTED
27 namespace lldb_private {
29 //----------------------------------------------------------------------
30 // Templatized classes for dealing with generic ranges and also
31 // collections of ranges, or collections of ranges that have associated
33 //----------------------------------------------------------------------
35 //----------------------------------------------------------------------
36 // A simple range class where you get to define the type of the range
37 // base "B", and the type used for the range byte size "S".
38 //----------------------------------------------------------------------
39 template <typename B, typename S> struct Range {
46 Range() : base(0), size(0) {}
48 Range(BaseType b, SizeType s) : base(b), size(s) {}
50 void Clear(BaseType b = 0) {
55 // Set the start value for the range, and keep the same size
56 BaseType GetRangeBase() const { return base; }
58 void SetRangeBase(BaseType b) { base = b; }
60 void Slide(BaseType slide) { base += slide; }
62 BaseType GetRangeEnd() const { return base + size; }
64 void SetRangeEnd(BaseType end) {
71 SizeType GetByteSize() const { return size; }
73 void SetByteSize(SizeType s) { size = s; }
75 bool IsValid() const { return size > 0; }
77 bool Contains(BaseType r) const {
78 return (GetRangeBase() <= r) && (r < GetRangeEnd());
81 bool ContainsEndInclusive(BaseType r) const {
82 return (GetRangeBase() <= r) && (r <= GetRangeEnd());
85 bool Contains(const Range &range) const {
86 return Contains(range.GetRangeBase()) &&
87 ContainsEndInclusive(range.GetRangeEnd());
90 // Returns true if the two ranges adjoing or intersect
91 bool DoesAdjoinOrIntersect(const Range &rhs) const {
92 const BaseType lhs_base = this->GetRangeBase();
93 const BaseType rhs_base = rhs.GetRangeBase();
94 const BaseType lhs_end = this->GetRangeEnd();
95 const BaseType rhs_end = rhs.GetRangeEnd();
96 bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
100 // Returns true if the two ranges intersect
101 bool DoesIntersect(const Range &rhs) const {
102 const BaseType lhs_base = this->GetRangeBase();
103 const BaseType rhs_base = rhs.GetRangeBase();
104 const BaseType lhs_end = this->GetRangeEnd();
105 const BaseType rhs_end = rhs.GetRangeEnd();
106 bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base);
110 bool operator<(const Range &rhs) const {
111 if (base == rhs.base)
112 return size < rhs.size;
113 return base < rhs.base;
116 bool operator==(const Range &rhs) const {
117 return base == rhs.base && size == rhs.size;
120 bool operator!=(const Range &rhs) const {
121 return base != rhs.base || size != rhs.size;
125 //----------------------------------------------------------------------
126 // A range array class where you get to define the type of the ranges
127 // that the collection contains.
128 //----------------------------------------------------------------------
130 template <typename B, typename S, unsigned N> class RangeArray {
134 typedef Range<B, S> Entry;
135 typedef llvm::SmallVector<Entry, N> Collection;
137 RangeArray() = default;
139 ~RangeArray() = default;
141 void Append(const Entry &entry) { m_entries.push_back(entry); }
143 void Append(B base, S size) { m_entries.emplace_back(base, size); }
145 bool RemoveEntrtAtIndex(uint32_t idx) {
146 if (idx < m_entries.size()) {
147 m_entries.erase(m_entries.begin() + idx);
154 if (m_entries.size() > 1)
155 std::stable_sort(m_entries.begin(), m_entries.end());
158 #ifdef ASSERT_RANGEMAP_ARE_SORTED
159 bool IsSorted() const {
160 typename Collection::const_iterator pos, end, prev;
161 // First we determine if we can combine any of the Entry objects so we
162 // don't end up allocating and making a new collection for no reason
163 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
165 if (prev != end && *pos < *prev)
172 void CombineConsecutiveRanges() {
173 #ifdef ASSERT_RANGEMAP_ARE_SORTED
176 // Can't combine if ranges if we have zero or one range
177 if (m_entries.size() > 1) {
178 // The list should be sorted prior to calling this function
179 typename Collection::iterator pos;
180 typename Collection::iterator end;
181 typename Collection::iterator prev;
182 bool can_combine = false;
183 // First we determine if we can combine any of the Entry objects so we
184 // don't end up allocating and making a new collection for no reason
185 for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
186 pos != end; prev = pos++) {
187 if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) {
193 // We we can combine at least one entry, then we make a new collection
194 // and populate it accordingly, and then swap it into place.
196 Collection minimal_ranges;
197 for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
198 pos != end; prev = pos++) {
199 if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
200 minimal_ranges.back().SetRangeEnd(
201 std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
203 minimal_ranges.push_back(*pos);
205 // Use the swap technique in case our new vector is much smaller.
206 // We must swap when using the STL because std::vector objects never
207 // release or reduce the memory once it has been allocated/reserved.
208 m_entries.swap(minimal_ranges);
213 BaseType GetMinRangeBase(BaseType fail_value) const {
214 #ifdef ASSERT_RANGEMAP_ARE_SORTED
217 if (m_entries.empty())
219 // m_entries must be sorted, so if we aren't empty, we grab the
220 // first range's base
221 return m_entries.front().GetRangeBase();
224 BaseType GetMaxRangeEnd(BaseType fail_value) const {
225 #ifdef ASSERT_RANGEMAP_ARE_SORTED
228 if (m_entries.empty())
230 // m_entries must be sorted, so if we aren't empty, we grab the
232 return m_entries.back().GetRangeEnd();
235 void Slide(BaseType slide) {
236 typename Collection::iterator pos, end;
237 for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
241 void Clear() { m_entries.clear(); }
243 bool IsEmpty() const { return m_entries.empty(); }
245 size_t GetSize() const { return m_entries.size(); }
247 const Entry *GetEntryAtIndex(size_t i) const {
248 return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
251 // Clients must ensure that "i" is a valid index prior to calling this
253 const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
255 Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
257 const Entry *Back() const {
258 return (m_entries.empty() ? nullptr : &m_entries.back());
261 static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
262 return lhs.GetRangeBase() < rhs.GetRangeBase();
265 uint32_t FindEntryIndexThatContains(B addr) const {
266 #ifdef ASSERT_RANGEMAP_ARE_SORTED
269 if (!m_entries.empty()) {
270 Entry entry(addr, 1);
271 typename Collection::const_iterator begin = m_entries.begin();
272 typename Collection::const_iterator end = m_entries.end();
273 typename Collection::const_iterator pos =
274 std::lower_bound(begin, end, entry, BaseLessThan);
276 if (pos != end && pos->Contains(addr)) {
277 return std::distance(begin, pos);
278 } else if (pos != begin) {
280 if (pos->Contains(addr))
281 return std::distance(begin, pos);
287 const Entry *FindEntryThatContains(B addr) const {
288 #ifdef ASSERT_RANGEMAP_ARE_SORTED
291 if (!m_entries.empty()) {
292 Entry entry(addr, 1);
293 typename Collection::const_iterator begin = m_entries.begin();
294 typename Collection::const_iterator end = m_entries.end();
295 typename Collection::const_iterator pos =
296 std::lower_bound(begin, end, entry, BaseLessThan);
298 if (pos != end && pos->Contains(addr)) {
300 } else if (pos != begin) {
302 if (pos->Contains(addr)) {
310 const Entry *FindEntryThatContains(const Entry &range) const {
311 #ifdef ASSERT_RANGEMAP_ARE_SORTED
314 if (!m_entries.empty()) {
315 typename Collection::const_iterator begin = m_entries.begin();
316 typename Collection::const_iterator end = m_entries.end();
317 typename Collection::const_iterator pos =
318 std::lower_bound(begin, end, range, BaseLessThan);
320 if (pos != end && pos->Contains(range)) {
322 } else if (pos != begin) {
324 if (pos->Contains(range)) {
333 Collection m_entries;
336 template <typename B, typename S> class RangeVector {
340 typedef Range<B, S> Entry;
341 typedef std::vector<Entry> Collection;
343 RangeVector() = default;
345 ~RangeVector() = default;
347 void Append(const Entry &entry) { m_entries.push_back(entry); }
349 void Append(B base, S size) { m_entries.emplace_back(base, size); }
351 bool RemoveEntrtAtIndex(uint32_t idx) {
352 if (idx < m_entries.size()) {
353 m_entries.erase(m_entries.begin() + idx);
360 if (m_entries.size() > 1)
361 std::stable_sort(m_entries.begin(), m_entries.end());
364 #ifdef ASSERT_RANGEMAP_ARE_SORTED
365 bool IsSorted() const {
366 typename Collection::const_iterator pos, end, prev;
367 // First we determine if we can combine any of the Entry objects so we
368 // don't end up allocating and making a new collection for no reason
369 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
371 if (prev != end && *pos < *prev)
378 void CombineConsecutiveRanges() {
379 #ifdef ASSERT_RANGEMAP_ARE_SORTED
382 // Can't combine if ranges if we have zero or one range
383 if (m_entries.size() > 1) {
384 // The list should be sorted prior to calling this function
385 typename Collection::iterator pos;
386 typename Collection::iterator end;
387 typename Collection::iterator prev;
388 bool can_combine = false;
389 // First we determine if we can combine any of the Entry objects so we
390 // don't end up allocating and making a new collection for no reason
391 for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
392 pos != end; prev = pos++) {
393 if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) {
399 // We we can combine at least one entry, then we make a new collection
400 // and populate it accordingly, and then swap it into place.
402 Collection minimal_ranges;
403 for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
404 pos != end; prev = pos++) {
405 if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
406 minimal_ranges.back().SetRangeEnd(
407 std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
409 minimal_ranges.push_back(*pos);
411 // Use the swap technique in case our new vector is much smaller.
412 // We must swap when using the STL because std::vector objects never
413 // release or reduce the memory once it has been allocated/reserved.
414 m_entries.swap(minimal_ranges);
419 BaseType GetMinRangeBase(BaseType fail_value) const {
420 #ifdef ASSERT_RANGEMAP_ARE_SORTED
423 if (m_entries.empty())
425 // m_entries must be sorted, so if we aren't empty, we grab the
426 // first range's base
427 return m_entries.front().GetRangeBase();
430 BaseType GetMaxRangeEnd(BaseType fail_value) const {
431 #ifdef ASSERT_RANGEMAP_ARE_SORTED
434 if (m_entries.empty())
436 // m_entries must be sorted, so if we aren't empty, we grab the
438 return m_entries.back().GetRangeEnd();
441 void Slide(BaseType slide) {
442 typename Collection::iterator pos, end;
443 for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
447 void Clear() { m_entries.clear(); }
449 void Reserve(typename Collection::size_type size) { m_entries.reserve(size); }
451 bool IsEmpty() const { return m_entries.empty(); }
453 size_t GetSize() const { return m_entries.size(); }
455 const Entry *GetEntryAtIndex(size_t i) const {
456 return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
459 // Clients must ensure that "i" is a valid index prior to calling this
461 const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
463 Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
465 const Entry *Back() const {
466 return (m_entries.empty() ? nullptr : &m_entries.back());
469 static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
470 return lhs.GetRangeBase() < rhs.GetRangeBase();
473 uint32_t FindEntryIndexThatContains(B addr) const {
474 #ifdef ASSERT_RANGEMAP_ARE_SORTED
477 if (!m_entries.empty()) {
478 Entry entry(addr, 1);
479 typename Collection::const_iterator begin = m_entries.begin();
480 typename Collection::const_iterator end = m_entries.end();
481 typename Collection::const_iterator pos =
482 std::lower_bound(begin, end, entry, BaseLessThan);
484 if (pos != end && pos->Contains(addr)) {
485 return std::distance(begin, pos);
486 } else if (pos != begin) {
488 if (pos->Contains(addr))
489 return std::distance(begin, pos);
495 const Entry *FindEntryThatContains(B addr) const {
496 #ifdef ASSERT_RANGEMAP_ARE_SORTED
499 if (!m_entries.empty()) {
500 Entry entry(addr, 1);
501 typename Collection::const_iterator begin = m_entries.begin();
502 typename Collection::const_iterator end = m_entries.end();
503 typename Collection::const_iterator pos =
504 std::lower_bound(begin, end, entry, BaseLessThan);
506 if (pos != end && pos->Contains(addr)) {
508 } else if (pos != begin) {
510 if (pos->Contains(addr)) {
518 const Entry *FindEntryThatContains(const Entry &range) const {
519 #ifdef ASSERT_RANGEMAP_ARE_SORTED
522 if (!m_entries.empty()) {
523 typename Collection::const_iterator begin = m_entries.begin();
524 typename Collection::const_iterator end = m_entries.end();
525 typename Collection::const_iterator pos =
526 std::lower_bound(begin, end, range, BaseLessThan);
528 if (pos != end && pos->Contains(range)) {
530 } else if (pos != begin) {
532 if (pos->Contains(range)) {
541 Collection m_entries;
544 //----------------------------------------------------------------------
545 // A simple range with data class where you get to define the type of
546 // the range base "B", the type used for the range byte size "S", and
547 // the type for the associated data "T".
548 //----------------------------------------------------------------------
549 template <typename B, typename S, typename T>
550 struct RangeData : public Range<B, S> {
555 RangeData() : Range<B, S>(), data() {}
557 RangeData(B base, S size) : Range<B, S>(base, size), data() {}
559 RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
561 bool operator<(const RangeData &rhs) const {
562 if (this->base == rhs.base) {
563 if (this->size == rhs.size)
564 return this->data < rhs.data;
566 return this->size < rhs.size;
568 return this->base < rhs.base;
571 bool operator==(const RangeData &rhs) const {
572 return this->GetRangeBase() == rhs.GetRangeBase() &&
573 this->GetByteSize() == rhs.GetByteSize() && this->data == rhs.data;
576 bool operator!=(const RangeData &rhs) const {
577 return this->GetRangeBase() != rhs.GetRangeBase() ||
578 this->GetByteSize() != rhs.GetByteSize() || this->data != rhs.data;
582 template <typename B, typename S, typename T, unsigned N> class RangeDataArray {
584 typedef RangeData<B, S, T> Entry;
585 typedef llvm::SmallVector<Entry, N> Collection;
587 RangeDataArray() = default;
589 ~RangeDataArray() = default;
591 void Append(const Entry &entry) { m_entries.push_back(entry); }
594 if (m_entries.size() > 1)
595 std::stable_sort(m_entries.begin(), m_entries.end());
598 #ifdef ASSERT_RANGEMAP_ARE_SORTED
599 bool IsSorted() const {
600 typename Collection::const_iterator pos, end, prev;
601 // First we determine if we can combine any of the Entry objects so we
602 // don't end up allocating and making a new collection for no reason
603 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
605 if (prev != end && *pos < *prev)
612 void CombineConsecutiveEntriesWithEqualData() {
613 #ifdef ASSERT_RANGEMAP_ARE_SORTED
616 typename Collection::iterator pos;
617 typename Collection::iterator end;
618 typename Collection::iterator prev;
619 bool can_combine = false;
620 // First we determine if we can combine any of the Entry objects so we
621 // don't end up allocating and making a new collection for no reason
622 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
624 if (prev != end && prev->data == pos->data) {
630 // We we can combine at least one entry, then we make a new collection
631 // and populate it accordingly, and then swap it into place.
633 Collection minimal_ranges;
634 for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
635 pos != end; prev = pos++) {
636 if (prev != end && prev->data == pos->data)
637 minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
639 minimal_ranges.push_back(*pos);
641 // Use the swap technique in case our new vector is much smaller.
642 // We must swap when using the STL because std::vector objects never
643 // release or reduce the memory once it has been allocated/reserved.
644 m_entries.swap(minimal_ranges);
648 void Clear() { m_entries.clear(); }
650 bool IsEmpty() const { return m_entries.empty(); }
652 size_t GetSize() const { return m_entries.size(); }
654 const Entry *GetEntryAtIndex(size_t i) const {
655 return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
658 // Clients must ensure that "i" is a valid index prior to calling this
660 const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
662 static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
663 return lhs.GetRangeBase() < rhs.GetRangeBase();
666 uint32_t FindEntryIndexThatContains(B addr) const {
667 #ifdef ASSERT_RANGEMAP_ARE_SORTED
670 if (!m_entries.empty()) {
671 Entry entry(addr, 1);
672 typename Collection::const_iterator begin = m_entries.begin();
673 typename Collection::const_iterator end = m_entries.end();
674 typename Collection::const_iterator pos =
675 std::lower_bound(begin, end, entry, BaseLessThan);
677 if (pos != end && pos->Contains(addr)) {
678 return std::distance(begin, pos);
679 } else if (pos != begin) {
681 if (pos->Contains(addr))
682 return std::distance(begin, pos);
688 Entry *FindEntryThatContains(B addr) {
689 #ifdef ASSERT_RANGEMAP_ARE_SORTED
692 if (!m_entries.empty()) {
694 entry.SetRangeBase(addr);
695 entry.SetByteSize(1);
696 typename Collection::iterator begin = m_entries.begin();
697 typename Collection::iterator end = m_entries.end();
698 typename Collection::iterator pos =
699 std::lower_bound(begin, end, entry, BaseLessThan);
701 if (pos != end && pos->Contains(addr)) {
703 } else if (pos != begin) {
705 if (pos->Contains(addr)) {
713 const Entry *FindEntryThatContains(B addr) const {
714 #ifdef ASSERT_RANGEMAP_ARE_SORTED
717 if (!m_entries.empty()) {
719 entry.SetRangeBase(addr);
720 entry.SetByteSize(1);
721 typename Collection::const_iterator begin = m_entries.begin();
722 typename Collection::const_iterator end = m_entries.end();
723 typename Collection::const_iterator pos =
724 std::lower_bound(begin, end, entry, BaseLessThan);
726 if (pos != end && pos->Contains(addr)) {
728 } else if (pos != begin) {
730 if (pos->Contains(addr)) {
738 const Entry *FindEntryThatContains(const Entry &range) const {
739 #ifdef ASSERT_RANGEMAP_ARE_SORTED
742 if (!m_entries.empty()) {
743 typename Collection::const_iterator begin = m_entries.begin();
744 typename Collection::const_iterator end = m_entries.end();
745 typename Collection::const_iterator pos =
746 std::lower_bound(begin, end, range, BaseLessThan);
748 if (pos != end && pos->Contains(range)) {
750 } else if (pos != begin) {
752 if (pos->Contains(range)) {
760 Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
762 const Entry *Back() const {
763 return (m_entries.empty() ? nullptr : &m_entries.back());
767 Collection m_entries;
770 // Same as RangeDataArray, but uses std::vector as to not
771 // require static storage of N items in the class itself
772 template <typename B, typename S, typename T> class RangeDataVector {
774 typedef RangeData<B, S, T> Entry;
775 typedef std::vector<Entry> Collection;
777 RangeDataVector() = default;
779 ~RangeDataVector() = default;
781 void Append(const Entry &entry) { m_entries.push_back(entry); }
784 if (m_entries.size() > 1)
785 std::stable_sort(m_entries.begin(), m_entries.end());
788 #ifdef ASSERT_RANGEMAP_ARE_SORTED
789 bool IsSorted() const {
790 typename Collection::const_iterator pos, end, prev;
791 // First we determine if we can combine any of the Entry objects so we
792 // don't end up allocating and making a new collection for no reason
793 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
795 if (prev != end && *pos < *prev)
802 void CombineConsecutiveEntriesWithEqualData() {
803 #ifdef ASSERT_RANGEMAP_ARE_SORTED
806 typename Collection::iterator pos;
807 typename Collection::iterator end;
808 typename Collection::iterator prev;
809 bool can_combine = false;
810 // First we determine if we can combine any of the Entry objects so we
811 // don't end up allocating and making a new collection for no reason
812 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
814 if (prev != end && prev->data == pos->data) {
820 // We we can combine at least one entry, then we make a new collection
821 // and populate it accordingly, and then swap it into place.
823 Collection minimal_ranges;
824 for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
825 pos != end; prev = pos++) {
826 if (prev != end && prev->data == pos->data)
827 minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
829 minimal_ranges.push_back(*pos);
831 // Use the swap technique in case our new vector is much smaller.
832 // We must swap when using the STL because std::vector objects never
833 // release or reduce the memory once it has been allocated/reserved.
834 m_entries.swap(minimal_ranges);
838 // Calculate the byte size of ranges with zero byte sizes by finding
839 // the next entry with a base address > the current base address
840 void CalculateSizesOfZeroByteSizeRanges(S full_size = 0) {
841 #ifdef ASSERT_RANGEMAP_ARE_SORTED
844 typename Collection::iterator pos;
845 typename Collection::iterator end;
846 typename Collection::iterator next;
847 for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) {
848 if (pos->GetByteSize() == 0) {
849 // Watch out for multiple entries with same address and make sure
850 // we find an entry that is greater than the current base address
851 // before we use that for the size
852 auto curr_base = pos->GetRangeBase();
853 for (next = pos + 1; next != end; ++next) {
854 auto next_base = next->GetRangeBase();
855 if (next_base > curr_base) {
856 pos->SetByteSize(next_base - curr_base);
860 if (next == end && full_size > curr_base)
861 pos->SetByteSize(full_size - curr_base);
866 void Clear() { m_entries.clear(); }
868 void Reserve(typename Collection::size_type size) { m_entries.resize(size); }
870 bool IsEmpty() const { return m_entries.empty(); }
872 size_t GetSize() const { return m_entries.size(); }
874 const Entry *GetEntryAtIndex(size_t i) const {
875 return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
878 Entry *GetMutableEntryAtIndex(size_t i) {
879 return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
882 // Clients must ensure that "i" is a valid index prior to calling this
884 const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
886 static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
887 return lhs.GetRangeBase() < rhs.GetRangeBase();
890 uint32_t FindEntryIndexThatContains(B addr) const {
891 #ifdef ASSERT_RANGEMAP_ARE_SORTED
894 if (!m_entries.empty()) {
895 Entry entry(addr, 1);
896 typename Collection::const_iterator begin = m_entries.begin();
897 typename Collection::const_iterator end = m_entries.end();
898 typename Collection::const_iterator pos =
899 std::lower_bound(begin, end, entry, BaseLessThan);
901 while (pos != begin && pos[-1].Contains(addr))
904 if (pos != end && pos->Contains(addr))
905 return std::distance(begin, pos);
910 uint32_t FindEntryIndexesThatContain(B addr,
911 std::vector<uint32_t> &indexes) const {
912 #ifdef ASSERT_RANGEMAP_ARE_SORTED
916 if (!m_entries.empty()) {
917 typename Collection::const_iterator pos;
918 for (const auto &entry : m_entries) {
919 if (entry.Contains(addr))
920 indexes.push_back(entry.data);
923 return indexes.size();
926 Entry *FindEntryThatContains(B addr) {
927 #ifdef ASSERT_RANGEMAP_ARE_SORTED
930 if (!m_entries.empty()) {
932 entry.SetRangeBase(addr);
933 entry.SetByteSize(1);
934 typename Collection::iterator begin = m_entries.begin();
935 typename Collection::iterator end = m_entries.end();
936 typename Collection::iterator pos =
937 std::lower_bound(begin, end, entry, BaseLessThan);
939 while (pos != begin && pos[-1].Contains(addr))
942 if (pos != end && pos->Contains(addr))
948 const Entry *FindEntryThatContains(B addr) const {
949 #ifdef ASSERT_RANGEMAP_ARE_SORTED
952 if (!m_entries.empty()) {
954 entry.SetRangeBase(addr);
955 entry.SetByteSize(1);
956 typename Collection::const_iterator begin = m_entries.begin();
957 typename Collection::const_iterator end = m_entries.end();
958 typename Collection::const_iterator pos =
959 std::lower_bound(begin, end, entry, BaseLessThan);
961 while (pos != begin && pos[-1].Contains(addr))
964 if (pos != end && pos->Contains(addr))
970 const Entry *FindEntryThatContains(const Entry &range) const {
971 #ifdef ASSERT_RANGEMAP_ARE_SORTED
974 if (!m_entries.empty()) {
975 typename Collection::const_iterator begin = m_entries.begin();
976 typename Collection::const_iterator end = m_entries.end();
977 typename Collection::const_iterator pos =
978 std::lower_bound(begin, end, range, BaseLessThan);
980 while (pos != begin && pos[-1].Contains(range))
983 if (pos != end && pos->Contains(range))
989 const Entry *FindEntryStartsAt(B addr) const {
990 #ifdef ASSERT_RANGEMAP_ARE_SORTED
993 if (!m_entries.empty()) {
994 auto begin = m_entries.begin(), end = m_entries.end();
995 auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan);
996 if (pos != end && pos->base == addr)
1002 // This method will return the entry that contains the given address, or the
1003 // entry following that address. If you give it an address of 0 and the first
1004 // entry starts at address 0x100, you will get the entry at 0x100.
1006 // For most uses, FindEntryThatContains is the correct one to use, this is a
1007 // less commonly needed behavior. It was added for core file memory regions,
1008 // where we want to present a gap in the memory regions as a distinct region,
1009 // so we need to know the start address of the next memory section that
1011 const Entry *FindEntryThatContainsOrFollows(B addr) const {
1012 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1015 if (!m_entries.empty()) {
1016 typename Collection::const_iterator begin = m_entries.begin();
1017 typename Collection::const_iterator end = m_entries.end();
1018 typename Collection::const_iterator pos =
1019 std::lower_bound(m_entries.begin(), end, addr,
1020 [](const Entry &lhs, B rhs_base) -> bool {
1021 return lhs.GetRangeEnd() <= rhs_base;
1024 while (pos != begin && pos[-1].Contains(addr))
1033 Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
1035 const Entry *Back() const {
1036 return (m_entries.empty() ? nullptr : &m_entries.back());
1040 Collection m_entries;
1043 //----------------------------------------------------------------------
1044 // A simple range with data class where you get to define the type of
1045 // the range base "B", the type used for the range byte size "S", and
1046 // the type for the associated data "T".
1047 //----------------------------------------------------------------------
1048 template <typename B, typename T> struct AddressData {
1055 AddressData() : addr(), data() {}
1057 AddressData(B a, DataType d) : addr(a), data(d) {}
1059 bool operator<(const AddressData &rhs) const {
1060 if (this->addr == rhs.addr)
1061 return this->data < rhs.data;
1062 return this->addr < rhs.addr;
1065 bool operator==(const AddressData &rhs) const {
1066 return this->addr == rhs.addr && this->data == rhs.data;
1069 bool operator!=(const AddressData &rhs) const {
1070 return this->addr != rhs.addr || this->data == rhs.data;
1074 template <typename B, typename T, unsigned N> class AddressDataArray {
1076 typedef AddressData<B, T> Entry;
1077 typedef llvm::SmallVector<Entry, N> Collection;
1079 AddressDataArray() = default;
1081 ~AddressDataArray() = default;
1083 void Append(const Entry &entry) { m_entries.push_back(entry); }
1086 if (m_entries.size() > 1)
1087 std::stable_sort(m_entries.begin(), m_entries.end());
1090 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1091 bool IsSorted() const {
1092 typename Collection::const_iterator pos, end, prev;
1093 // First we determine if we can combine any of the Entry objects so we
1094 // don't end up allocating and making a new collection for no reason
1095 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
1097 if (prev != end && *pos < *prev)
1104 void Clear() { m_entries.clear(); }
1106 bool IsEmpty() const { return m_entries.empty(); }
1108 size_t GetSize() const { return m_entries.size(); }
1110 const Entry *GetEntryAtIndex(size_t i) const {
1111 return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
1114 // Clients must ensure that "i" is a valid index prior to calling this
1116 const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
1118 static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
1119 return lhs.addr < rhs.addr;
1122 Entry *FindEntry(B addr, bool exact_match_only) {
1123 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1126 if (!m_entries.empty()) {
1129 typename Collection::iterator begin = m_entries.begin();
1130 typename Collection::iterator end = m_entries.end();
1131 typename Collection::iterator pos =
1132 std::lower_bound(begin, end, entry, BaseLessThan);
1134 while (pos != begin && pos[-1].addr == addr)
1138 if (pos->addr == addr || !exact_match_only)
1145 const Entry *FindNextEntry(const Entry *entry) {
1146 if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
1151 Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
1153 const Entry *Back() const {
1154 return (m_entries.empty() ? nullptr : &m_entries.back());
1158 Collection m_entries;
1161 } // namespace lldb_private
1163 #endif // liblldb_RangeMap_h_