Go to the documentation of this file.
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 {
59 auto new_end = std::max<BaseType>(
GetRangeEnd(), rhs.GetRangeEnd());
60 base = std::min<BaseType>(
base, rhs.base);
69 const BaseType rhs_base = rhs.GetRangeBase();
71 const BaseType rhs_end = rhs.GetRangeEnd();
73 range.SetRangeBase(std::max(lhs_base, rhs_base));
74 range.SetRangeEnd(std::min(lhs_end, rhs_end));
102 return Contains(range.GetRangeBase()) &&
109 const BaseType rhs_base = rhs.GetRangeBase();
111 const BaseType rhs_end = rhs.GetRangeEnd();
112 bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
122 if (
base == rhs.base)
123 return size < rhs.size;
124 return base < rhs.base;
128 return base == rhs.base &&
size == rhs.size;
132 return base != rhs.base ||
size != rhs.size;
136 template <
typename B,
typename S,
unsigned N = 0>
class RangeVector {
149 #ifdef ASSERT_RANGEMAP_ARE_SORTED
150 assert(vec1.IsSorted() && vec2.IsSorted());
153 auto pos1 = vec1.
begin();
154 auto end1 = vec1.
end();
155 auto pos2 = vec2.
begin();
156 auto end2 = vec2.
end();
157 while (pos1 != end1 && pos2 != end2) {
161 if (pos1->GetRangeEnd() < pos2->GetRangeEnd())
172 for (
size_t i = 0; i <
GetSize(); ++i) {
192 auto pos = std::lower_bound(
begin,
end, entry);
194 if (pos !=
end && pos->Union(entry)) {
200 if (prev->Union(entry)) {
222 #ifdef ASSERT_RANGEMAP_ARE_SORTED
223 bool IsSorted()
const {
224 typename Collection::const_iterator pos,
end, prev;
229 if (prev !=
end && *pos < *prev)
237 #ifdef ASSERT_RANGEMAP_ARE_SORTED
240 auto first_intersect = std::adjacent_find(
242 return a.DoesAdjoinOrIntersect(b);
249 auto pos = std::next(first_intersect);
252 Entry &back = minimal_ranges.back();
256 minimal_ranges.push_back(*pos);
262 #ifdef ASSERT_RANGEMAP_ARE_SORTED
273 #ifdef ASSERT_RANGEMAP_ARE_SORTED
284 typename Collection::iterator pos,
end;
317 #ifdef ASSERT_RANGEMAP_ARE_SORTED
321 Entry entry(addr, 1);
323 typename Collection::const_iterator
end =
m_entries.end();
324 typename Collection::const_iterator pos =
327 if (pos !=
end && pos->Contains(addr)) {
328 return std::distance(
begin, pos);
329 }
else if (pos !=
begin) {
331 if (pos->Contains(addr))
332 return std::distance(
begin, pos);
339 #ifdef ASSERT_RANGEMAP_ARE_SORTED
343 Entry entry(addr, 1);
345 typename Collection::const_iterator
end =
m_entries.end();
346 typename Collection::const_iterator pos =
349 if (pos !=
end && pos->Contains(addr)) {
351 }
else if (pos !=
begin) {
353 if (pos->Contains(addr)) {
362 #ifdef ASSERT_RANGEMAP_ARE_SORTED
367 typename Collection::const_iterator
end =
m_entries.end();
368 typename Collection::const_iterator pos =
371 if (pos !=
end && pos->Contains(range)) {
373 }
else if (pos !=
begin) {
375 if (pos->Contains(range)) {
393 if (prev->Union(*pos))
402 if (pos->Union(*next))
414 template <
typename B,
typename S,
typename T>
430 template <
typename B,
typename S,
typename T>
438 template <
typename B,
typename S,
typename T,
unsigned N = 0,
464 if (a.base != b.base)
465 return a.base < b.base;
466 if (a.size != b.size)
467 return a.size < b.size;
468 return compare(a.data, b.data);
474 #ifdef ASSERT_RANGEMAP_ARE_SORTED
475 bool IsSorted()
const {
476 typename Collection::const_iterator pos,
end, prev;
479 if (prev !=
end && *pos < *prev)
487 #ifdef ASSERT_RANGEMAP_ARE_SORTED
490 typename Collection::iterator pos;
491 typename Collection::iterator
end;
492 typename Collection::iterator prev;
493 bool can_combine =
false;
498 if (prev !=
end && prev->data == pos->data) {
509 pos !=
end; prev = pos++) {
510 if (prev !=
end && prev->data == pos->data)
511 minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
513 minimal_ranges.push_back(*pos);
549 return std::distance(
m_entries.begin(), entry);
554 #ifdef ASSERT_RANGEMAP_ARE_SORTED
560 return indexes.size();
564 return const_cast<Entry *
>(
574 #ifdef ASSERT_RANGEMAP_ARE_SORTED
579 typename Collection::const_iterator
end =
m_entries.end();
580 typename Collection::const_iterator pos =
586 if (pos !=
end && pos->Contains(range))
593 #ifdef ASSERT_RANGEMAP_ARE_SORTED
599 if (pos !=
end && pos->base == addr)
615 #ifdef ASSERT_RANGEMAP_ARE_SORTED
620 typename Collection::const_iterator
end =
m_entries.end();
621 typename Collection::const_iterator pos = llvm::lower_bound(
636 #ifdef ASSERT_RANGEMAP_ARE_SORTED
642 return std::distance(
m_entries.begin(), entry);
663 size_t mid = (lo + hi) / 2;
682 std::vector<uint32_t> &indexes) {
683 size_t mid = (lo + hi) / 2;
697 if (addr < entry.
base)
701 indexes.push_back(entry.
data);
724 if (this->addr == rhs.
addr)
725 return this->data < rhs.
data;
726 return this->addr < rhs.
addr;
730 return this->addr == rhs.
addr && this->data == rhs.
data;
734 return this->addr != rhs.
addr || this->data == rhs.
data;
754 #ifdef ASSERT_RANGEMAP_ARE_SORTED
755 bool IsSorted()
const {
756 typename Collection::const_iterator pos, end, prev;
761 if (prev != end && *pos < *prev)
787 #ifdef ASSERT_RANGEMAP_ARE_SORTED
793 typename Collection::iterator begin =
m_entries.begin();
794 typename Collection::iterator end =
m_entries.end();
795 typename Collection::iterator pos =
798 while (pos != begin && pos[-1].addr == addr)
802 if (pos->addr == addr || !exact_match_only)
827 #endif // LLDB_UTILITY_RANGEMAP_H
void FindEntryIndexesThatContain(B addr, size_t lo, size_t hi, std::vector< uint32_t > &indexes)
lldb_private::Range< B, S > Range
uint32_t FindEntryIndexThatContainsOrFollows(B addr) const
BaseType GetRangeBase() const
const Entry * Back() const
const Entry * FindEntryThatContains(const Entry &range) const
bool DoesIntersect(const Range &rhs) const
uint32_t FindEntryIndexThatContains(B addr) const
Entry & GetEntryRef(size_t i)
~AddressDataArray()=default
static RangeVector GetOverlaps(const RangeVector &vec1, const RangeVector &vec2)
const Entry & GetEntryRef(size_t i) const
AddressData< B, T > Entry
llvm::SmallVector< Entry, N > Collection
const Entry * Back() const
typename Collection::const_iterator const_iterator
bool operator==(const Range &rhs) const
BaseType GetMinRangeBase(BaseType fail_value) const
Entry & GetEntryRef(size_t i)
llvm::SmallVector< Entry, N > Collection
AugmentedRangeData(const RangeData< B, S, T > &rd)
const Entry * GetEntryAtIndex(size_t i) const
Range(BaseType b, SizeType s)
void Reserve(typename Collection::size_type size)
static bool BaseLessThan(const Entry &lhs, const Entry &rhs)
void CombineConsecutiveRanges()
void Append(const Entry &entry)
RangeData< B, S, T > Entry
bool operator<(const Range &rhs) const
bool operator==(const AddressData &rhs) const
RangeData(B base, S size)
Entry * FindEntryThatContains(B addr)
void SetRangeEnd(BaseType end)
const Entry * Back() const
void Append(const Entry &entry)
uint32_t FindEntryIndexesThatContain(B addr, std::vector< uint32_t > &indexes)
const_iterator begin() const
bool ContainsEndInclusive(BaseType r) const
bool operator!=(const Range &rhs) const
static bool Compare(BreakpointLocationSP lhs, lldb::break_id_t val)
const Entry * FindNextEntry(const Entry *entry)
typename Collection::const_iterator const_iterator
void Slide(BaseType slide)
void Append(const Entry &entry)
const Entry * FindEntryThatContains(const Entry &range) const
RangeDataVector(Compare compare=Compare())
void Slide(BaseType slide)
void Insert(const Entry &entry, bool combine)
bool operator==(const RangeVector &rhs) const
BaseType GetMaxRangeEnd(BaseType fail_value) const
void CombinePrevAndNext(typename Collection::iterator pos)
uint32_t FindEntryIndexThatContains(B addr) const
const Entry * FindEntryStartsAt(B addr) const
const Entry & GetEntryRef(size_t i) const
bool DoesAdjoinOrIntersect(const Range &rhs) const
Range Intersect(const Range &rhs) const
bool RemoveEntryAtIndex(uint32_t idx)
llvm::SmallVector< AugmentedEntry, N > Collection
void Append(B base, S size)
RangeData(B base, S size, DataType d)
void SetRangeBase(BaseType b)
SizeType GetByteSize() const
void SetByteSize(SizeType s)
Entry * FindEntry(B addr, bool exact_match_only)
bool Erase(uint32_t start, uint32_t end)
const_iterator end() const
bool Contains(const Range &range) const
const_iterator begin() const
AddressData(B a, DataType d)
const Entry * FindEntryThatContains(B addr) const
A class that represents a running process on the host machine.
Entry * GetMutableEntryAtIndex(size_t i)
const Entry * GetEntryAtIndex(size_t i) const
static bool BaseLessThan(const Entry &lhs, const Entry &rhs)
AddressDataArray()=default
const Entry & GetEntryRef(size_t i) const
const Entry * FindEntryThatContains(B addr) const
AugmentedRangeData< B, S, T > AugmentedEntry
B ComputeUpperBounds(size_t lo, size_t hi)
const Entry * FindEntryThatContainsOrFollows(B addr) const
bool operator<(const AddressData &rhs) const
static bool BaseLessThan(const Entry &lhs, const Entry &rhs)
const_iterator end() const
void CombineConsecutiveEntriesWithEqualData()
bool Contains(BaseType r) const
bool Union(const Range &rhs)
const Entry * GetEntryAtIndex(size_t i) const
~RangeDataVector()=default
bool operator!=(const AddressData &rhs) const
BaseType GetRangeEnd() const