9 #ifndef LLDB_UTILITY_RANGEMAP_H
10 #define LLDB_UTILITY_RANGEMAP_H
15 #include "llvm/ADT/SmallVector.h"
29 template <
typename B,
typename S>
struct Range {
54 auto new_end = std::max<BaseType>(
GetRangeEnd(), rhs.GetRangeEnd());
55 base = std::min<BaseType>(
base, rhs.base);
64 const BaseType rhs_base = rhs.GetRangeBase();
66 const BaseType rhs_end = rhs.GetRangeEnd();
68 range.SetRangeBase(std::max(lhs_base, rhs_base));
69 range.SetRangeEnd(std::min(lhs_end, rhs_end));
97 return Contains(range.GetRangeBase()) &&
104 const BaseType rhs_base = rhs.GetRangeBase();
106 const BaseType rhs_end = rhs.GetRangeEnd();
107 bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
117 if (
base == rhs.base)
118 return size < rhs.size;
119 return base < rhs.base;
123 return base == rhs.base &&
size == rhs.size;
127 return base != rhs.base ||
size != rhs.size;
131 template <
typename B,
typename S,
unsigned N = 0>
class RangeVector {
144 #ifdef ASSERT_RANGEMAP_ARE_SORTED
145 assert(vec1.IsSorted() && vec2.IsSorted());
148 auto pos1 = vec1.
begin();
149 auto end1 = vec1.
end();
150 auto pos2 = vec2.
begin();
151 auto end2 = vec2.
end();
152 while (pos1 != end1 && pos2 != end2) {
156 if (pos1->GetRangeEnd() < pos2->GetRangeEnd())
167 for (
size_t i = 0; i <
GetSize(); ++i) {
187 auto pos = std::lower_bound(
begin,
end, entry);
189 if (pos !=
end && pos->Union(entry)) {
195 if (prev->Union(entry)) {
217 #ifdef ASSERT_RANGEMAP_ARE_SORTED
218 bool IsSorted()
const {
219 typename Collection::const_iterator pos,
end, prev;
224 if (prev !=
end && *pos < *prev)
232 #ifdef ASSERT_RANGEMAP_ARE_SORTED
235 auto first_intersect = std::adjacent_find(
237 return a.DoesAdjoinOrIntersect(b);
244 auto pos = std::next(first_intersect);
247 Entry &back = minimal_ranges.back();
251 minimal_ranges.push_back(*pos);
257 #ifdef ASSERT_RANGEMAP_ARE_SORTED
268 #ifdef ASSERT_RANGEMAP_ARE_SORTED
279 typename Collection::iterator pos,
end;
312 #ifdef ASSERT_RANGEMAP_ARE_SORTED
316 Entry entry(addr, 1);
318 typename Collection::const_iterator
end =
m_entries.end();
319 typename Collection::const_iterator pos =
322 if (pos !=
end && pos->Contains(addr)) {
323 return std::distance(
begin, pos);
324 }
else if (pos !=
begin) {
326 if (pos->Contains(addr))
327 return std::distance(
begin, pos);
334 #ifdef ASSERT_RANGEMAP_ARE_SORTED
338 Entry entry(addr, 1);
340 typename Collection::const_iterator
end =
m_entries.end();
341 typename Collection::const_iterator pos =
344 if (pos !=
end && pos->Contains(addr)) {
346 }
else if (pos !=
begin) {
348 if (pos->Contains(addr)) {
357 #ifdef ASSERT_RANGEMAP_ARE_SORTED
362 typename Collection::const_iterator
end =
m_entries.end();
363 typename Collection::const_iterator pos =
366 if (pos !=
end && pos->Contains(range)) {
368 }
else if (pos !=
begin) {
370 if (pos->Contains(range)) {
388 if (prev->Union(*pos))
397 if (pos->Union(*next))
409 template <
typename B,
typename S,
typename T>
425 template <
typename B,
typename S,
typename T>
433 template <
typename B,
typename S,
typename T,
unsigned N = 0,
452 if (a.base != b.base)
453 return a.base < b.base;
454 if (a.size != b.size)
455 return a.size < b.size;
456 return compare(a.data, b.data);
462 #ifdef ASSERT_RANGEMAP_ARE_SORTED
463 bool IsSorted()
const {
464 typename Collection::const_iterator pos, end, prev;
467 if (prev != end && *pos < *prev)
475 #ifdef ASSERT_RANGEMAP_ARE_SORTED
478 typename Collection::iterator pos;
479 typename Collection::iterator end;
480 typename Collection::iterator prev;
481 bool can_combine =
false;
486 if (prev != end && prev->data == pos->data) {
497 pos != end; prev = pos++) {
498 if (prev != end && prev->data == pos->data)
499 minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
501 minimal_ranges.push_back(*pos);
537 return std::distance(
m_entries.begin(), entry);
542 #ifdef ASSERT_RANGEMAP_ARE_SORTED
548 return indexes.size();
552 return const_cast<Entry *
>(
562 #ifdef ASSERT_RANGEMAP_ARE_SORTED
566 typename Collection::const_iterator begin =
m_entries.begin();
567 typename Collection::const_iterator end =
m_entries.end();
568 typename Collection::const_iterator pos =
571 while (pos != begin && pos[-1].
Contains(range))
574 if (pos != end && pos->Contains(range))
581 #ifdef ASSERT_RANGEMAP_ARE_SORTED
587 if (pos != end && pos->base == addr)
603 #ifdef ASSERT_RANGEMAP_ARE_SORTED
607 typename Collection::const_iterator begin =
m_entries.begin();
608 typename Collection::const_iterator end =
m_entries.end();
609 typename Collection::const_iterator pos =
610 std::lower_bound(
m_entries.begin(), end, addr,
611 [](
const Entry &lhs, B rhs_base) ->
bool {
612 return lhs.GetRangeEnd() <= rhs_base;
615 while (pos != begin && pos[-1].
Contains(addr))
637 size_t mid = (lo + hi) / 2;
656 std::vector<uint32_t> &indexes) {
657 size_t mid = (lo + hi) / 2;
671 if (addr < entry.
base)
675 indexes.push_back(entry.
data);
698 if (this->addr == rhs.
addr)
699 return this->data < rhs.
data;
700 return this->addr < rhs.
addr;
704 return this->addr == rhs.
addr && this->data == rhs.
data;
708 return this->addr != rhs.
addr || this->data == rhs.
data;
728 #ifdef ASSERT_RANGEMAP_ARE_SORTED
729 bool IsSorted()
const {
730 typename Collection::const_iterator pos, end, prev;
735 if (prev != end && *pos < *prev)
761 #ifdef ASSERT_RANGEMAP_ARE_SORTED
767 typename Collection::iterator begin =
m_entries.begin();
768 typename Collection::iterator end =
m_entries.end();
769 typename Collection::iterator pos =
772 while (pos != begin && pos[-1].addr == addr)
776 if (pos->addr == addr || !exact_match_only)
801 #endif // LLDB_UTILITY_RANGEMAP_H