This is an archive of the discontinued LLVM Phabricator instance.

Differential D58970

Move RangeMap.h into Utility
ClosedPublic

Authored by labath on Mar 5 2019, 8:17 AM.

Details

Reviewers
zturner
jingham
JDevlieghere
clayborg
• espindola
Commits
rGb8093314ef72: Move RangeMap.h into Utility
rLLDB355509: Move RangeMap.h into Utility
rL355509: Move RangeMap.h into Utility
Summary

This file implements some general purpose data structures, and so it
belongs to the Utility module.

Diff Detail

Repository
rL LLVM

Event Timeline

labath created this revision.Mar 5 2019, 8:17 AM
Herald added a reviewer: • espindola. · View Herald TranscriptMar 5 2019, 8:17 AM
Herald added subscribers: MaskRay, arichardson, javed.absar and 2 others. · View Herald Transcript
Harbormaster completed remote builds in B28802: Diff 189328.Mar 5 2019, 8:17 AM
labath added a child revision: D58971: Move MemoryRegionInfo into the Utility module.Mar 5 2019, 8:18 AM
JDevlieghere accepted this revision.Mar 5 2019, 8:25 AM

This looks like a no-brainer. LGTM.

This revision is now accepted and ready to land.Mar 5 2019, 8:25 AM
Closed by commit rL355509: Move RangeMap.h into Utility (authored by labath). · Explain WhyMar 6 2019, 6:41 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptMar 6 2019, 6:41 AM
Herald added subscribers: llvm-commits, jdoerfert. · View Herald Transcript

Revision Contents

PathSize
lldb/
trunk/
include/
lldb/
Core/
950 lines
3 lines
Symbol/
5 lines
5 lines
7 lines
5 lines
5 lines
7 lines
7 lines
Target/
6 lines
4 lines
Utility/
947 lines
source/
Plugins/
ObjectFile/
ELF/
2 lines
JIT/
2 lines
Mach-O/
2 lines
2 lines
SymbolFile/
DWARF/
3 lines
5 lines
7 lines
2 lines
Target/
3 lines
unittests/
Core/
2 lines
54 lines
329 lines
Utility/
2 lines
54 lines
328 lines

Diff 189501

lldb/trunk/include/lldb/Core/RangeMap.h

//===-- RangeMap.h ----------------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef liblldb_RangeMap_h_
#define liblldb_RangeMap_h_
#include <algorithm>
#include <vector>
#include "llvm/ADT/SmallVector.h"
#include "lldb/lldb-private.h"
// Uncomment to make sure all Range objects are sorted when needed
//#define ASSERT_RANGEMAP_ARE_SORTED
namespace lldb_private {
//----------------------------------------------------------------------
// Templatized classes for dealing with generic ranges and also collections of
// ranges, or collections of ranges that have associated data.
//----------------------------------------------------------------------
//----------------------------------------------------------------------
// A simple range class where you get to define the type of the range
// base "B", and the type used for the range byte size "S".
//----------------------------------------------------------------------
template <typename B, typename S> struct Range {
typedef B BaseType;
typedef S SizeType;
BaseType base;
SizeType size;
Range() : base(0), size(0) {}
Range(BaseType b, SizeType s) : base(b), size(s) {}
void Clear(BaseType b = 0) {
base = b;
size = 0;
}
// Set the start value for the range, and keep the same size
BaseType GetRangeBase() const { return base; }
void SetRangeBase(BaseType b) { base = b; }
void Slide(BaseType slide) { base += slide; }
bool Union(const Range &rhs)
{
if (DoesAdjoinOrIntersect(rhs))
{
auto new_end = std::max<BaseType>(GetRangeEnd(), rhs.GetRangeEnd());
base = std::min<BaseType>(base, rhs.base);
size = new_end - base;
return true;
}
return false;
}
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());
}
// 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;
}
// 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 operator<(const Range &rhs) const {
if (base == rhs.base)
return size < rhs.size;
return base < rhs.base;
}
bool operator==(const Range &rhs) const {
return base == rhs.base && size == rhs.size;
}
bool operator!=(const Range &rhs) const {
return base != rhs.base || size != rhs.size;
}
};
//----------------------------------------------------------------------
// A range array class where you get to define the type of the ranges
// that the collection contains.
//----------------------------------------------------------------------
template <typename B, typename S, unsigned N> class RangeArray {
public:
typedef B BaseType;
typedef S SizeType;
typedef Range<B, S> Entry;
typedef llvm::SmallVector<Entry, N> Collection;
RangeArray() = default;
~RangeArray() = default;
void Append(const Entry &entry) { m_entries.push_back(entry); }
void Append(B base, S size) { m_entries.emplace_back(base, size); }
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;
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);
}
}
}
BaseType GetMinRangeBase(BaseType fail_value) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (m_entries.empty())
return fail_value;
// m_entries must be sorted, so if we aren't empty, we grab the first
// range's base
return m_entries.front().GetRangeBase();
}
BaseType GetMaxRangeEnd(BaseType fail_value) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (m_entries.empty())
return fail_value;
// m_entries must be sorted, so if we aren't empty, we grab the last
// range's end
return m_entries.back().GetRangeEnd();
}
void Slide(BaseType slide) {
typename Collection::iterator pos, end;
for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
pos->Slide(slide);
}
void Clear() { m_entries.clear(); }
bool IsEmpty() const { return m_entries.empty(); }
size_t GetSize() const { return m_entries.size(); }
const Entry *GetEntryAtIndex(size_t i) const {
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 {
#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;
}
protected:
Collection m_entries;
};
template <typename B, typename S> class RangeVector {
public:
typedef B BaseType;
typedef S SizeType;
typedef Range<B, S> Entry;
typedef std::vector<Entry> Collection;
RangeVector() = default;
~RangeVector() = default;
void Append(const Entry &entry) { m_entries.push_back(entry); }
void Append(B base, S size) { m_entries.emplace_back(base, size); }
// Insert an item into a sorted list and optionally combine it with any
// adjacent blocks if requested.
void Insert(const Entry &entry, bool combine) {
if (m_entries.empty()) {
m_entries.push_back(entry);
return;
}
auto begin = m_entries.begin();
auto end = m_entries.end();
auto pos = std::lower_bound(begin, end, entry);
if (combine) {
if (pos != end && pos->Union(entry)) {
CombinePrevAndNext(pos);
return;
}
if (pos != begin) {
auto prev = pos - 1;
if (prev->Union(entry)) {
CombinePrevAndNext(prev);
return;
}
}
}
m_entries.insert(pos, entry);
}
bool RemoveEntryAtIndex(uint32_t idx) {
if (idx < m_entries.size()) {
m_entries.erase(m_entries.begin() + idx);
return true;
}
return false;
}
void Sort() {
if (m_entries.size() > 1)
std::stable_sort(m_entries.begin(), m_entries.end());
}
#ifdef ASSERT_RANGEMAP_ARE_SORTED
bool IsSorted() const {
typename Collection::const_iterator pos, end, prev;
// First we determine if we can combine any of the Entry objects so we
// don't end up allocating and making a new collection for no reason
for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
prev = pos++) {
if (prev != end && *pos < *prev)
return false;
}
return true;
}
#endif
void CombineConsecutiveRanges() {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
// Can't combine if ranges if we have zero or one range
if (m_entries.size() > 1) {
// The list should be sorted prior to calling this function
typename Collection::iterator pos;
typename Collection::iterator end;
typename Collection::iterator prev;
bool can_combine = false;
// First we determine if we can combine any of the Entry objects so we
// don't end up allocating and making a new collection for no reason
for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
pos != end; prev = pos++) {
if (prev != end && prev->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);
}
}
}
BaseType GetMinRangeBase(BaseType fail_value) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (m_entries.empty())
return fail_value;
// m_entries must be sorted, so if we aren't empty, we grab the first
// range's base
return m_entries.front().GetRangeBase();
}
BaseType GetMaxRangeEnd(BaseType fail_value) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (m_entries.empty())
return fail_value;
// m_entries must be sorted, so if we aren't empty, we grab the last
// range's end
return m_entries.back().GetRangeEnd();
}
void Slide(BaseType slide) {
typename Collection::iterator pos, end;
for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
pos->Slide(slide);
}
void Clear() { m_entries.clear(); }
void Reserve(typename Collection::size_type size) { m_entries.reserve(size); }
bool IsEmpty() const { return m_entries.empty(); }
size_t GetSize() const { return m_entries.size(); }
const Entry *GetEntryAtIndex(size_t i) const {
return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
}
// Clients must ensure that "i" is a valid index prior to calling this
// function
Entry &GetEntryRef(size_t i) { return m_entries[i]; }
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 {
#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;
}
protected:
void CombinePrevAndNext(typename Collection::iterator pos) {
// Check if the prev or next entries in case they need to be unioned with
// the entry pointed to by "pos".
if (pos != m_entries.begin()) {
auto prev = pos - 1;
if (prev->Union(*pos))
m_entries.erase(pos);
pos = prev;
}
auto end = m_entries.end();
if (pos != end) {
auto next = pos + 1;
if (next != end) {
if (pos->Union(*next))
m_entries.erase(next);
}
}
return;
}
Collection m_entries;
};
//----------------------------------------------------------------------
// A simple range with data class where you get to define the type of
// the range base "B", the type used for the range byte size "S", and the type
// for the associated data "T".
//----------------------------------------------------------------------
template <typename B, typename S, typename T>
struct RangeData : public Range<B, S> {
typedef T DataType;
DataType data;
RangeData() : Range<B, S>(), data() {}
RangeData(B base, S size) : Range<B, S>(base, size), data() {}
RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
bool operator<(const RangeData &rhs) const {
if (this->base == rhs.base) {
if (this->size == rhs.size)
return this->data < rhs.data;
else
return this->size < rhs.size;
}
return this->base < rhs.base;
}
bool operator==(const RangeData &rhs) const {
return this->GetRangeBase() == rhs.GetRangeBase() &&
this->GetByteSize() == rhs.GetByteSize() && this->data == rhs.data;
}
bool operator!=(const RangeData &rhs) const {
return this->GetRangeBase() != rhs.GetRangeBase() ||
this->GetByteSize() != rhs.GetByteSize() || this->data != rhs.data;
}
};
template <typename B, typename S, typename T, unsigned N = 0>
class RangeDataVector {
public:
typedef RangeData<B, S, T> Entry;
typedef llvm::SmallVector<Entry, N> Collection;
RangeDataVector() = default;
~RangeDataVector() = 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 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);
}
Entry *GetMutableEntryAtIndex(size_t i) {
return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
}
// Clients must ensure that "i" is a valid index prior to calling this
// function
Entry &GetEntryRef(size_t i) { return m_entries[i]; }
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 {
const Entry *entry = FindEntryThatContains(addr);
if (entry)
return std::distance(m_entries.begin(), entry);
return UINT32_MAX;
}
uint32_t FindEntryIndexesThatContain(B addr,
std::vector<uint32_t> &indexes) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (!m_entries.empty()) {
for (const auto &entry : m_entries) {
if (entry.Contains(addr))
indexes.push_back(entry.data);
}
}
return indexes.size();
}
Entry *FindEntryThatContains(B addr) {
return const_cast<Entry *>(
static_cast<const RangeDataVector *>(this)->FindEntryThatContains(
addr));
}
const Entry *FindEntryThatContains(B addr) const {
return FindEntryThatContains(Entry(addr, 1));
}
const Entry *FindEntryThatContains(const Entry &range) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (!m_entries.empty()) {
typename Collection::const_iterator begin = m_entries.begin();
typename Collection::const_iterator end = m_entries.end();
typename Collection::const_iterator pos =
std::lower_bound(begin, end, range, BaseLessThan);
while (pos != begin && pos[-1].Contains(range))
--pos;
if (pos != end && pos->Contains(range))
return &(*pos);
}
return nullptr;
}
const Entry *FindEntryStartsAt(B addr) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (!m_entries.empty()) {
auto begin = m_entries.begin(), end = m_entries.end();
auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan);
if (pos != end && pos->base == addr)
return &(*pos);
}
return nullptr;
}
// This method will return the entry that contains the given address, or the
// entry following that address. If you give it an address of 0 and the
// first entry starts at address 0x100, you will get the entry at 0x100.
//
// For most uses, FindEntryThatContains is the correct one to use, this is a
// less commonly needed behavior. It was added for core file memory regions,
// where we want to present a gap in the memory regions as a distinct region,
// so we need to know the start address of the next memory section that
// exists.
const Entry *FindEntryThatContainsOrFollows(B addr) 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(m_entries.begin(), end, addr,
[](const Entry &lhs, B rhs_base) -> bool {
return lhs.GetRangeEnd() <= rhs_base;
});
while (pos != begin && pos[-1].Contains(addr))
--pos;
if (pos != end)
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;
}
};
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;
};
} // namespace lldb_private
#endif // liblldb_RangeMap_h_

lldb/trunk/include/lldb/Core/dwarf.h

//===-- dwarf.h -------------------------------------------------*- C++ -*-===// //===-- dwarf.h -------------------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef DebugBase_dwarf_h_ #ifndef DebugBase_dwarf_h_
#define DebugBase_dwarf_h_ #define DebugBase_dwarf_h_
#include "lldb/Utility/RangeMap.h"
#include <stdint.h> #include <stdint.h>
// Get the DWARF constant definitions from llvm // Get the DWARF constant definitions from llvm
#include "llvm/BinaryFormat/Dwarf.h" #include "llvm/BinaryFormat/Dwarf.h"
#include "lldb/Core/RangeMap.h"
// and stuff them in our default namespace // and stuff them in our default namespace
using namespace llvm::dwarf; using namespace llvm::dwarf;
typedef uint32_t dw_uleb128_t; typedef uint32_t dw_uleb128_t;
typedef int32_t dw_sleb128_t; typedef int32_t dw_sleb128_t;
typedef uint16_t dw_attr_t; typedef uint16_t dw_attr_t;
typedef uint16_t dw_form_t; typedef uint16_t dw_form_t;
typedef uint16_t dw_tag_t; typedef uint16_t dw_tag_t;
▲ Show 20 Lines • Show All 58 Lines • Show Last 20 Lines

lldb/trunk/include/lldb/Symbol/ArmUnwindInfo.h

//===-- ArmUnwindInfo.h -----------------------------------------*- C++ -*-===// //===-- ArmUnwindInfo.h -----------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef liblldb_ArmUnwindInfo_h_ #ifndef liblldb_ArmUnwindInfo_h_
#define liblldb_ArmUnwindInfo_h_ #define liblldb_ArmUnwindInfo_h_
#include <vector>
#include "lldb/Core/RangeMap.h"
#include "lldb/Symbol/ObjectFile.h" #include "lldb/Symbol/ObjectFile.h"
#include "lldb/Utility/DataExtractor.h" #include "lldb/Utility/DataExtractor.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/lldb-private.h" #include "lldb/lldb-private.h"
#include <vector>
/* /*
* Unwind information reader and parser for the ARM exception handling ABI * Unwind information reader and parser for the ARM exception handling ABI
* *
* Implemented based on: * Implemented based on:
* Exception Handling ABI for the ARM Architecture * Exception Handling ABI for the ARM Architecture
* Document number: ARM IHI 0038A (current through ABI r2.09) * Document number: ARM IHI 0038A (current through ABI r2.09)
* Date of Issue: 25th January 2007, reissued 30th November 2012 * Date of Issue: 25th January 2007, reissued 30th November 2012
▲ Show 20 Lines • Show All 44 Lines • Show Last 20 Lines

lldb/trunk/include/lldb/Symbol/Block.h

//===-- Block.h -------------------------------------------------*- C++ -*-===// //===-- Block.h -------------------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef liblldb_Block_h_ #ifndef liblldb_Block_h_
#define liblldb_Block_h_ #define liblldb_Block_h_
#include <vector>
#include "lldb/Core/AddressRange.h" #include "lldb/Core/AddressRange.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Symbol/CompilerType.h" #include "lldb/Symbol/CompilerType.h"
#include "lldb/Symbol/LineEntry.h" #include "lldb/Symbol/LineEntry.h"
#include "lldb/Symbol/SymbolContext.h" #include "lldb/Symbol/SymbolContext.h"
#include "lldb/Symbol/SymbolContextScope.h" #include "lldb/Symbol/SymbolContextScope.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/Utility/Stream.h" #include "lldb/Utility/Stream.h"
#include "lldb/Utility/UserID.h" #include "lldb/Utility/UserID.h"
#include "lldb/lldb-private.h" #include "lldb/lldb-private.h"
#include <vector>
namespace lldb_private { namespace lldb_private {
//---------------------------------------------------------------------- //----------------------------------------------------------------------
/// @class Block Block.h "lldb/Symbol/Block.h" /// @class Block Block.h "lldb/Symbol/Block.h"
/// A class that describes a single lexical block. /// A class that describes a single lexical block.
/// ///
/// A Function object owns a BlockList object which owns one or more /// A Function object owns a BlockList object which owns one or more
▲ Show 20 Lines • Show All 411 Lines • Show Last 20 Lines

lldb/trunk/include/lldb/Symbol/CompactUnwindInfo.h

//===-- CompactUnwindInfo.h -------------------------------------*- C++ -*-===// //===-- CompactUnwindInfo.h -------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef liblldb_CompactUnwindInfo_h_ #ifndef liblldb_CompactUnwindInfo_h_
#define liblldb_CompactUnwindInfo_h_ #define liblldb_CompactUnwindInfo_h_
#include <mutex>
#include <vector>
#include "lldb/Core/RangeMap.h"
#include "lldb/Symbol/ObjectFile.h" #include "lldb/Symbol/ObjectFile.h"
#include "lldb/Symbol/UnwindPlan.h" #include "lldb/Symbol/UnwindPlan.h"
#include "lldb/Utility/DataExtractor.h" #include "lldb/Utility/DataExtractor.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/lldb-private.h" #include "lldb/lldb-private.h"
#include <mutex>
#include <vector>
namespace lldb_private { namespace lldb_private {
// Compact Unwind info is an unwind format used on Darwin. The unwind // Compact Unwind info is an unwind format used on Darwin. The unwind
// instructions for typical compiler-generated functions can be expressed in a // instructions for typical compiler-generated functions can be expressed in a
// 32-bit encoding. The format includes a two-level index so the unwind // 32-bit encoding. The format includes a two-level index so the unwind
// information for a function can be found by two binary searches in the // information for a function can be found by two binary searches in the
// section. It can represent both stack frames that use a frame-pointer // section. It can represent both stack frames that use a frame-pointer
▲ Show 20 Lines • Show All 141 Lines • Show Last 20 Lines

lldb/trunk/include/lldb/Symbol/DWARFCallFrameInfo.h

//===-- DWARFCallFrameInfo.h ------------------------------------*- C++ -*-===// //===-- DWARFCallFrameInfo.h ------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef liblldb_DWARFCallFrameInfo_h_ #ifndef liblldb_DWARFCallFrameInfo_h_
#define liblldb_DWARFCallFrameInfo_h_ #define liblldb_DWARFCallFrameInfo_h_
#include <map> #include <map>
#include <mutex> #include <mutex>
#include "lldb/Core/AddressRange.h" #include "lldb/Core/AddressRange.h"
#include "lldb/Utility/Flags.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Core/dwarf.h" #include "lldb/Core/dwarf.h"
#include "lldb/Symbol/ObjectFile.h" #include "lldb/Symbol/ObjectFile.h"
#include "lldb/Symbol/UnwindPlan.h" #include "lldb/Symbol/UnwindPlan.h"
#include "lldb/Utility/Flags.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/Utility/VMRange.h" #include "lldb/Utility/VMRange.h"
#include "lldb/lldb-private.h" #include "lldb/lldb-private.h"
namespace lldb_private { namespace lldb_private {
// DWARFCallFrameInfo is a class which can read eh_frame and DWARF Call Frame // DWARFCallFrameInfo is a class which can read eh_frame and DWARF Call Frame
// Information FDEs. It stores little information internally. Only two APIs // Information FDEs. It stores little information internally. Only two APIs
// are exported - one to find the high/low pc values of a function given a text // are exported - one to find the high/low pc values of a function given a text
▲ Show 20 Lines • Show All 136 Lines • Show Last 20 Lines

lldb/trunk/include/lldb/Symbol/LineTable.h

//===-- LineTable.h ---------------------------------------------*- C++ -*-===// //===-- LineTable.h ---------------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef liblldb_LineTable_h_ #ifndef liblldb_LineTable_h_
#define liblldb_LineTable_h_ #define liblldb_LineTable_h_
#include <vector>
#include "lldb/Core/ModuleChild.h" #include "lldb/Core/ModuleChild.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Core/Section.h" #include "lldb/Core/Section.h"
#include "lldb/Symbol/LineEntry.h" #include "lldb/Symbol/LineEntry.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/lldb-private.h" #include "lldb/lldb-private.h"
#include <vector>
namespace lldb_private { namespace lldb_private {
//---------------------------------------------------------------------- //----------------------------------------------------------------------
/// @class LineSequence LineTable.h "lldb/Symbol/LineTable.h" An abstract base /// @class LineSequence LineTable.h "lldb/Symbol/LineTable.h" An abstract base
/// class used during symbol table creation. /// class used during symbol table creation.
//---------------------------------------------------------------------- //----------------------------------------------------------------------
class LineSequence { class LineSequence {
▲ Show 20 Lines • Show All 353 Lines • Show Last 20 Lines

lldb/trunk/include/lldb/Symbol/Symtab.h

//===-- Symtab.h ------------------------------------------------*- C++ -*-===// //===-- Symtab.h ------------------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef liblldb_Symtab_h_ #ifndef liblldb_Symtab_h_
#define liblldb_Symtab_h_ #define liblldb_Symtab_h_
#include <mutex>
#include <vector>
#include "lldb/Core/RangeMap.h"
#include "lldb/Core/UniqueCStringMap.h" #include "lldb/Core/UniqueCStringMap.h"
#include "lldb/Symbol/Symbol.h" #include "lldb/Symbol/Symbol.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/lldb-private.h" #include "lldb/lldb-private.h"
#include <mutex>
#include <vector>
namespace lldb_private { namespace lldb_private {
class Symtab { class Symtab {
public: public:
typedef std::vector<uint32_t> IndexCollection; typedef std::vector<uint32_t> IndexCollection;
typedef UniqueCStringMap<uint32_t> NameToIndexMap; typedef UniqueCStringMap<uint32_t> NameToIndexMap;
▲ Show 20 Lines • Show All 187 Lines • Show Last 20 Lines

lldb/trunk/include/lldb/Symbol/Variable.h

//===-- Variable.h -----------------------------------------------*- C++-*-===// //===-- Variable.h -----------------------------------------------*- C++-*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef liblldb_Variable_h_ #ifndef liblldb_Variable_h_
#define liblldb_Variable_h_ #define liblldb_Variable_h_
#include <memory>
#include <vector>
#include "lldb/Core/Mangled.h" #include "lldb/Core/Mangled.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Expression/DWARFExpression.h" #include "lldb/Expression/DWARFExpression.h"
#include "lldb/Symbol/Declaration.h" #include "lldb/Symbol/Declaration.h"
#include "lldb/Utility/CompletionRequest.h" #include "lldb/Utility/CompletionRequest.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/Utility/UserID.h" #include "lldb/Utility/UserID.h"
#include "lldb/lldb-enumerations.h" #include "lldb/lldb-enumerations.h"
#include "lldb/lldb-private.h" #include "lldb/lldb-private.h"
#include <memory>
#include <vector>
namespace lldb_private { namespace lldb_private {
class Variable : public UserID, public std::enable_shared_from_this<Variable> { class Variable : public UserID, public std::enable_shared_from_this<Variable> {
public: public:
typedef RangeVector<lldb::addr_t, lldb::addr_t> RangeList; typedef RangeVector<lldb::addr_t, lldb::addr_t> RangeList;
//------------------------------------------------------------------ //------------------------------------------------------------------
▲ Show 20 Lines • Show All 110 Lines • Show Last 20 Lines

lldb/trunk/include/lldb/Target/Memory.h

//===-- Memory.h ------------------------------------------------*- C++ -*-===// //===-- Memory.h ------------------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef liblldb_Memory_h_ #ifndef liblldb_Memory_h_
#define liblldb_Memory_h_ #define liblldb_Memory_h_
#include "lldb/Utility/RangeMap.h"
#include "lldb/lldb-private.h"
#include <map> #include <map>
#include <mutex> #include <mutex>
#include <vector> #include <vector>
#include "lldb/Core/RangeMap.h"
#include "lldb/lldb-private.h"
namespace lldb_private { namespace lldb_private {
//---------------------------------------------------------------------- //----------------------------------------------------------------------
// A class to track memory that was read from a live process between // A class to track memory that was read from a live process between
// runs. // runs.
//---------------------------------------------------------------------- //----------------------------------------------------------------------
class MemoryCache { class MemoryCache {
public: public:
//------------------------------------------------------------------ //------------------------------------------------------------------
▲ Show 20 Lines • Show All 130 Lines • Show Last 20 Lines

lldb/trunk/include/lldb/Target/MemoryRegionInfo.h

//===-- MemoryRegionInfo.h ---------------------------------------*- C++ //===-- MemoryRegionInfo.h ---------------------------------------*- C++
//-*-===// //-*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef lldb_MemoryRegionInfo_h #ifndef lldb_MemoryRegionInfo_h
#define lldb_MemoryRegionInfo_h #define lldb_MemoryRegionInfo_h
#include "lldb/Core/RangeMap.h"
#include "llvm/Support/FormatProviders.h"
#include "lldb/Utility/ConstString.h" #include "lldb/Utility/ConstString.h"
#include "lldb/Utility/RangeMap.h"
#include "llvm/Support/FormatProviders.h"
namespace lldb_private { namespace lldb_private {
class MemoryRegionInfo { class MemoryRegionInfo {
public: public:
typedef Range<lldb::addr_t, lldb::addr_t> RangeType; typedef Range<lldb::addr_t, lldb::addr_t> RangeType;
enum OptionalBool { eDontKnow = -1, eNo = 0, eYes = 1 }; enum OptionalBool { eDontKnow = -1, eNo = 0, eYes = 1 };
▲ Show 20 Lines • Show All 129 Lines • Show Last 20 Lines

lldb/trunk/include/lldb/Utility/RangeMap.h

//===-- RangeMap.h ----------------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef LLDB_UTILITY_RANGEMAP_H
#define LLDB_UTILITY_RANGEMAP_H
#include <algorithm>
#include <vector>
#include "llvm/ADT/SmallVector.h"
#include "lldb/lldb-private.h"
// Uncomment to make sure all Range objects are sorted when needed
//#define ASSERT_RANGEMAP_ARE_SORTED
namespace lldb_private {
//----------------------------------------------------------------------
// Templatized classes for dealing with generic ranges and also collections of
// ranges, or collections of ranges that have associated data.
//----------------------------------------------------------------------
//----------------------------------------------------------------------
// A simple range class where you get to define the type of the range
// base "B", and the type used for the range byte size "S".
//----------------------------------------------------------------------
template <typename B, typename S> struct Range {
typedef B BaseType;
typedef S SizeType;
BaseType base;
SizeType size;
Range() : base(0), size(0) {}
Range(BaseType b, SizeType s) : base(b), size(s) {}
void Clear(BaseType b = 0) {
base = b;
size = 0;
}
// Set the start value for the range, and keep the same size
BaseType GetRangeBase() const { return base; }
void SetRangeBase(BaseType b) { base = b; }
void Slide(BaseType slide) { base += slide; }
bool Union(const Range &rhs) {
if (DoesAdjoinOrIntersect(rhs)) {
auto new_end = std::max<BaseType>(GetRangeEnd(), rhs.GetRangeEnd());
base = std::min<BaseType>(base, rhs.base);
size = new_end - base;
return true;
}
return false;
}
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());
}
// 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;
}
// 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 operator<(const Range &rhs) const {
if (base == rhs.base)
return size < rhs.size;
return base < rhs.base;
}
bool operator==(const Range &rhs) const {
return base == rhs.base && size == rhs.size;
}
bool operator!=(const Range &rhs) const {
return base != rhs.base || size != rhs.size;
}
};
//----------------------------------------------------------------------
// A range array class where you get to define the type of the ranges
// that the collection contains.
//----------------------------------------------------------------------
template <typename B, typename S, unsigned N> class RangeArray {
public:
typedef B BaseType;
typedef S SizeType;
typedef Range<B, S> Entry;
typedef llvm::SmallVector<Entry, N> Collection;
RangeArray() = default;
~RangeArray() = default;
void Append(const Entry &entry) { m_entries.push_back(entry); }
void Append(B base, S size) { m_entries.emplace_back(base, size); }
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;
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);
}
}
}
BaseType GetMinRangeBase(BaseType fail_value) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (m_entries.empty())
return fail_value;
// m_entries must be sorted, so if we aren't empty, we grab the first
// range's base
return m_entries.front().GetRangeBase();
}
BaseType GetMaxRangeEnd(BaseType fail_value) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (m_entries.empty())
return fail_value;
// m_entries must be sorted, so if we aren't empty, we grab the last
// range's end
return m_entries.back().GetRangeEnd();
}
void Slide(BaseType slide) {
typename Collection::iterator pos, end;
for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
pos->Slide(slide);
}
void Clear() { m_entries.clear(); }
bool IsEmpty() const { return m_entries.empty(); }
size_t GetSize() const { return m_entries.size(); }
const Entry *GetEntryAtIndex(size_t i) const {
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 {
#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;
}
protected:
Collection m_entries;
};
template <typename B, typename S> class RangeVector {
public:
typedef B BaseType;
typedef S SizeType;
typedef Range<B, S> Entry;
typedef std::vector<Entry> Collection;
RangeVector() = default;
~RangeVector() = default;
void Append(const Entry &entry) { m_entries.push_back(entry); }
void Append(B base, S size) { m_entries.emplace_back(base, size); }
// Insert an item into a sorted list and optionally combine it with any
// adjacent blocks if requested.
void Insert(const Entry &entry, bool combine) {
if (m_entries.empty()) {
m_entries.push_back(entry);
return;
}
auto begin = m_entries.begin();
auto end = m_entries.end();
auto pos = std::lower_bound(begin, end, entry);
if (combine) {
if (pos != end && pos->Union(entry)) {
CombinePrevAndNext(pos);
return;
}
if (pos != begin) {
auto prev = pos - 1;
if (prev->Union(entry)) {
CombinePrevAndNext(prev);
return;
}
}
}
m_entries.insert(pos, entry);
}
bool RemoveEntryAtIndex(uint32_t idx) {
if (idx < m_entries.size()) {
m_entries.erase(m_entries.begin() + idx);
return true;
}
return false;
}
void Sort() {
if (m_entries.size() > 1)
std::stable_sort(m_entries.begin(), m_entries.end());
}
#ifdef ASSERT_RANGEMAP_ARE_SORTED
bool IsSorted() const {
typename Collection::const_iterator pos, end, prev;
// First we determine if we can combine any of the Entry objects so we
// don't end up allocating and making a new collection for no reason
for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
prev = pos++) {
if (prev != end && *pos < *prev)
return false;
}
return true;
}
#endif
void CombineConsecutiveRanges() {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
// Can't combine if ranges if we have zero or one range
if (m_entries.size() > 1) {
// The list should be sorted prior to calling this function
typename Collection::iterator pos;
typename Collection::iterator end;
typename Collection::iterator prev;
bool can_combine = false;
// First we determine if we can combine any of the Entry objects so we
// don't end up allocating and making a new collection for no reason
for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
pos != end; prev = pos++) {
if (prev != end && prev->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);
}
}
}
BaseType GetMinRangeBase(BaseType fail_value) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (m_entries.empty())
return fail_value;
// m_entries must be sorted, so if we aren't empty, we grab the first
// range's base
return m_entries.front().GetRangeBase();
}
BaseType GetMaxRangeEnd(BaseType fail_value) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (m_entries.empty())
return fail_value;
// m_entries must be sorted, so if we aren't empty, we grab the last
// range's end
return m_entries.back().GetRangeEnd();
}
void Slide(BaseType slide) {
typename Collection::iterator pos, end;
for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
pos->Slide(slide);
}
void Clear() { m_entries.clear(); }
void Reserve(typename Collection::size_type size) { m_entries.reserve(size); }
bool IsEmpty() const { return m_entries.empty(); }
size_t GetSize() const { return m_entries.size(); }
const Entry *GetEntryAtIndex(size_t i) const {
return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
}
// Clients must ensure that "i" is a valid index prior to calling this
// function
Entry &GetEntryRef(size_t i) { return m_entries[i]; }
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 {
#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;
}
protected:
void CombinePrevAndNext(typename Collection::iterator pos) {
// Check if the prev or next entries in case they need to be unioned with
// the entry pointed to by "pos".
if (pos != m_entries.begin()) {
auto prev = pos - 1;
if (prev->Union(*pos))
m_entries.erase(pos);
pos = prev;
}
auto end = m_entries.end();
if (pos != end) {
auto next = pos + 1;
if (next != end) {
if (pos->Union(*next))
m_entries.erase(next);
}
}
return;
}
Collection m_entries;
};
//----------------------------------------------------------------------
// A simple range with data class where you get to define the type of
// the range base "B", the type used for the range byte size "S", and the type
// for the associated data "T".
//----------------------------------------------------------------------
template <typename B, typename S, typename T>
struct RangeData : public Range<B, S> {
typedef T DataType;
DataType data;
RangeData() : Range<B, S>(), data() {}
RangeData(B base, S size) : Range<B, S>(base, size), data() {}
RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
bool operator<(const RangeData &rhs) const {
if (this->base == rhs.base) {
if (this->size == rhs.size)
return this->data < rhs.data;
else
return this->size < rhs.size;
}
return this->base < rhs.base;
}
bool operator==(const RangeData &rhs) const {
return this->GetRangeBase() == rhs.GetRangeBase() &&
this->GetByteSize() == rhs.GetByteSize() && this->data == rhs.data;
}
bool operator!=(const RangeData &rhs) const {
return this->GetRangeBase() != rhs.GetRangeBase() ||
this->GetByteSize() != rhs.GetByteSize() || this->data != rhs.data;
}
};
template <typename B, typename S, typename T, unsigned N = 0>
class RangeDataVector {
public:
typedef RangeData<B, S, T> Entry;
typedef llvm::SmallVector<Entry, N> Collection;
RangeDataVector() = default;
~RangeDataVector() = 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 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);
}
Entry *GetMutableEntryAtIndex(size_t i) {
return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
}
// Clients must ensure that "i" is a valid index prior to calling this
// function
Entry &GetEntryRef(size_t i) { return m_entries[i]; }
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 {
const Entry *entry = FindEntryThatContains(addr);
if (entry)
return std::distance(m_entries.begin(), entry);
return UINT32_MAX;
}
uint32_t FindEntryIndexesThatContain(B addr,
std::vector<uint32_t> &indexes) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (!m_entries.empty()) {
for (const auto &entry : m_entries) {
if (entry.Contains(addr))
indexes.push_back(entry.data);
}
}
return indexes.size();
}
Entry *FindEntryThatContains(B addr) {
return const_cast<Entry *>(
static_cast<const RangeDataVector *>(this)->FindEntryThatContains(
addr));
}
const Entry *FindEntryThatContains(B addr) const {
return FindEntryThatContains(Entry(addr, 1));
}
const Entry *FindEntryThatContains(const Entry &range) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (!m_entries.empty()) {
typename Collection::const_iterator begin = m_entries.begin();
typename Collection::const_iterator end = m_entries.end();
typename Collection::const_iterator pos =
std::lower_bound(begin, end, range, BaseLessThan);
while (pos != begin && pos[-1].Contains(range))
--pos;
if (pos != end && pos->Contains(range))
return &(*pos);
}
return nullptr;
}
const Entry *FindEntryStartsAt(B addr) const {
#ifdef ASSERT_RANGEMAP_ARE_SORTED
assert(IsSorted());
#endif
if (!m_entries.empty()) {
auto begin = m_entries.begin(), end = m_entries.end();
auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan);
if (pos != end && pos->base == addr)
return &(*pos);
}
return nullptr;
}
// This method will return the entry that contains the given address, or the
// entry following that address. If you give it an address of 0 and the
// first entry starts at address 0x100, you will get the entry at 0x100.
//
// For most uses, FindEntryThatContains is the correct one to use, this is a
// less commonly needed behavior. It was added for core file memory regions,
// where we want to present a gap in the memory regions as a distinct region,
// so we need to know the start address of the next memory section that
// exists.
const Entry *FindEntryThatContainsOrFollows(B addr) 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(m_entries.begin(), end, addr,
[](const Entry &lhs, B rhs_base) -> bool {
return lhs.GetRangeEnd() <= rhs_base;
});
while (pos != begin && pos[-1].Contains(addr))
--pos;
if (pos != end)
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;
}
};
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;
};
} // namespace lldb_private
#endif // LLDB_UTILITY_RANGEMAP_H

lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp

Show All 10 Lines
#include <algorithm> #include <algorithm>
#include <cassert> #include <cassert>
#include <unordered_map> #include <unordered_map>
#include "lldb/Core/FileSpecList.h" #include "lldb/Core/FileSpecList.h"
#include "lldb/Core/Module.h" #include "lldb/Core/Module.h"
#include "lldb/Core/ModuleSpec.h" #include "lldb/Core/ModuleSpec.h"
#include "lldb/Core/PluginManager.h" #include "lldb/Core/PluginManager.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Core/Section.h" #include "lldb/Core/Section.h"
#include "lldb/Host/FileSystem.h" #include "lldb/Host/FileSystem.h"
#include "lldb/Symbol/DWARFCallFrameInfo.h" #include "lldb/Symbol/DWARFCallFrameInfo.h"
#include "lldb/Symbol/SymbolContext.h" #include "lldb/Symbol/SymbolContext.h"
#include "lldb/Target/SectionLoadList.h" #include "lldb/Target/SectionLoadList.h"
#include "lldb/Target/Target.h" #include "lldb/Target/Target.h"
#include "lldb/Utility/ArchSpec.h" #include "lldb/Utility/ArchSpec.h"
#include "lldb/Utility/DataBufferHeap.h" #include "lldb/Utility/DataBufferHeap.h"
#include "lldb/Utility/Log.h" #include "lldb/Utility/Log.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/Utility/Status.h" #include "lldb/Utility/Status.h"
#include "lldb/Utility/Stream.h" #include "lldb/Utility/Stream.h"
#include "lldb/Utility/Timer.h" #include "lldb/Utility/Timer.h"
#include "llvm/ADT/IntervalMap.h" #include "llvm/ADT/IntervalMap.h"
#include "llvm/ADT/PointerUnion.h" #include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/StringRef.h" #include "llvm/ADT/StringRef.h"
#include "llvm/Object/Decompressor.h" #include "llvm/Object/Decompressor.h"
▲ Show 20 Lines • Show All 3,454 Lines • Show Last 20 Lines

lldb/trunk/source/Plugins/ObjectFile/JIT/ObjectFileJIT.cpp

//===-- ObjectFileJIT.cpp ---------------------------------------*- C++ -*-===// //===-- ObjectFileJIT.cpp ---------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#include "llvm/ADT/StringRef.h" #include "llvm/ADT/StringRef.h"
#include "ObjectFileJIT.h" #include "ObjectFileJIT.h"
#include "lldb/Core/Debugger.h" #include "lldb/Core/Debugger.h"
#include "lldb/Core/FileSpecList.h" #include "lldb/Core/FileSpecList.h"
#include "lldb/Core/Module.h" #include "lldb/Core/Module.h"
#include "lldb/Core/ModuleSpec.h" #include "lldb/Core/ModuleSpec.h"
#include "lldb/Core/PluginManager.h" #include "lldb/Core/PluginManager.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Core/Section.h" #include "lldb/Core/Section.h"
#include "lldb/Core/StreamFile.h" #include "lldb/Core/StreamFile.h"
#include "lldb/Host/Host.h" #include "lldb/Host/Host.h"
#include "lldb/Symbol/ObjectFile.h" #include "lldb/Symbol/ObjectFile.h"
#include "lldb/Target/Platform.h" #include "lldb/Target/Platform.h"
#include "lldb/Target/Process.h" #include "lldb/Target/Process.h"
#include "lldb/Target/SectionLoadList.h" #include "lldb/Target/SectionLoadList.h"
#include "lldb/Target/Target.h" #include "lldb/Target/Target.h"
#include "lldb/Utility/ArchSpec.h" #include "lldb/Utility/ArchSpec.h"
#include "lldb/Utility/DataBuffer.h" #include "lldb/Utility/DataBuffer.h"
#include "lldb/Utility/DataBufferHeap.h" #include "lldb/Utility/DataBufferHeap.h"
#include "lldb/Utility/FileSpec.h" #include "lldb/Utility/FileSpec.h"
#include "lldb/Utility/Log.h" #include "lldb/Utility/Log.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/Utility/StreamString.h" #include "lldb/Utility/StreamString.h"
#include "lldb/Utility/Timer.h" #include "lldb/Utility/Timer.h"
#include "lldb/Utility/UUID.h" #include "lldb/Utility/UUID.h"
#ifndef __APPLE__ #ifndef __APPLE__
#include "Utility/UuidCompatibility.h" #include "Utility/UuidCompatibility.h"
#endif #endif
▲ Show 20 Lines • Show All 224 Lines • Show Last 20 Lines

lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.h

//===-- ObjectFileMachO.h ---------------------------------------*- C++ -*-===// //===-- ObjectFileMachO.h ---------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef liblldb_ObjectFileMachO_h_ #ifndef liblldb_ObjectFileMachO_h_
#define liblldb_ObjectFileMachO_h_ #define liblldb_ObjectFileMachO_h_
#include "lldb/Core/Address.h" #include "lldb/Core/Address.h"
#include "lldb/Core/FileSpecList.h" #include "lldb/Core/FileSpecList.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Host/SafeMachO.h" #include "lldb/Host/SafeMachO.h"
#include "lldb/Symbol/ObjectFile.h" #include "lldb/Symbol/ObjectFile.h"
#include "lldb/Utility/FileSpec.h" #include "lldb/Utility/FileSpec.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/Utility/UUID.h" #include "lldb/Utility/UUID.h"
//---------------------------------------------------------------------- //----------------------------------------------------------------------
// This class needs to be hidden as eventually belongs in a plugin that // This class needs to be hidden as eventually belongs in a plugin that
// will export the ObjectFile protocol // will export the ObjectFile protocol
//---------------------------------------------------------------------- //----------------------------------------------------------------------
class ObjectFileMachO : public lldb_private::ObjectFile { class ObjectFileMachO : public lldb_private::ObjectFile {
public: public:
▲ Show 20 Lines • Show All 193 Lines • Show Last 20 Lines

lldb/trunk/source/Plugins/ObjectFile/Mach-O/ObjectFileMachO.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show All 11 Lines
#include "Plugins/Process/Utility/RegisterContextDarwin_arm64.h" #include "Plugins/Process/Utility/RegisterContextDarwin_arm64.h"
#include "Plugins/Process/Utility/RegisterContextDarwin_i386.h" #include "Plugins/Process/Utility/RegisterContextDarwin_i386.h"
#include "Plugins/Process/Utility/RegisterContextDarwin_x86_64.h" #include "Plugins/Process/Utility/RegisterContextDarwin_x86_64.h"
#include "lldb/Core/Debugger.h" #include "lldb/Core/Debugger.h"
#include "lldb/Core/FileSpecList.h" #include "lldb/Core/FileSpecList.h"
#include "lldb/Core/Module.h" #include "lldb/Core/Module.h"
#include "lldb/Core/ModuleSpec.h" #include "lldb/Core/ModuleSpec.h"
#include "lldb/Core/PluginManager.h" #include "lldb/Core/PluginManager.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Core/Section.h" #include "lldb/Core/Section.h"
#include "lldb/Core/StreamFile.h" #include "lldb/Core/StreamFile.h"
#include "lldb/Host/Host.h" #include "lldb/Host/Host.h"
#include "lldb/Symbol/DWARFCallFrameInfo.h" #include "lldb/Symbol/DWARFCallFrameInfo.h"
#include "lldb/Symbol/ObjectFile.h" #include "lldb/Symbol/ObjectFile.h"
#include "lldb/Target/DynamicLoader.h" #include "lldb/Target/DynamicLoader.h"
#include "lldb/Target/MemoryRegionInfo.h" #include "lldb/Target/MemoryRegionInfo.h"
#include "lldb/Target/Platform.h" #include "lldb/Target/Platform.h"
#include "lldb/Target/Process.h" #include "lldb/Target/Process.h"
#include "lldb/Target/SectionLoadList.h" #include "lldb/Target/SectionLoadList.h"
#include "lldb/Target/Target.h" #include "lldb/Target/Target.h"
#include "lldb/Target/Thread.h" #include "lldb/Target/Thread.h"
#include "lldb/Target/ThreadList.h" #include "lldb/Target/ThreadList.h"
#include "lldb/Utility/ArchSpec.h" #include "lldb/Utility/ArchSpec.h"
#include "lldb/Utility/DataBuffer.h" #include "lldb/Utility/DataBuffer.h"
#include "lldb/Utility/FileSpec.h" #include "lldb/Utility/FileSpec.h"
#include "lldb/Utility/Log.h" #include "lldb/Utility/Log.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/Utility/RegisterValue.h" #include "lldb/Utility/RegisterValue.h"
#include "lldb/Utility/Status.h" #include "lldb/Utility/Status.h"
#include "lldb/Utility/StreamString.h" #include "lldb/Utility/StreamString.h"
#include "lldb/Utility/Timer.h" #include "lldb/Utility/Timer.h"
#include "lldb/Utility/UUID.h" #include "lldb/Utility/UUID.h"
#include "lldb/Host/SafeMachO.h" #include "lldb/Host/SafeMachO.h"
▲ Show 20 Lines • Show All 6,334 Lines • Show Last 20 Lines

lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h

//===-- DWARFDebugAranges.h -------------------------------------*- C++ -*-===// //===-- DWARFDebugAranges.h -------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef SymbolFileDWARF_DWARFDebugAranges_h_ #ifndef SymbolFileDWARF_DWARFDebugAranges_h_
#define SymbolFileDWARF_DWARFDebugAranges_h_ #define SymbolFileDWARF_DWARFDebugAranges_h_
#include "DWARFDebugArangeSet.h" #include "DWARFDebugArangeSet.h"
#include "lldb/Utility/RangeMap.h"
#include <list> #include <list>
#include "lldb/Core/RangeMap.h"
class SymbolFileDWARF; class SymbolFileDWARF;
class DWARFDebugAranges { class DWARFDebugAranges {
protected: protected:
typedef lldb_private::RangeDataVector<dw_addr_t, uint32_t, dw_offset_t> typedef lldb_private::RangeDataVector<dw_addr_t, uint32_t, dw_offset_t>
RangeToDIE; RangeToDIE;
public: public:
▲ Show 20 Lines • Show All 41 Lines • Show Last 20 Lines

lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

Show All 13 Lines
#include <mutex> #include <mutex>
#include <set> #include <set>
#include <unordered_map> #include <unordered_map>
#include <vector> #include <vector>
#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseMap.h"
#include "llvm/Support/Threading.h" #include "llvm/Support/Threading.h"
#include "lldb/Utility/Flags.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Core/UniqueCStringMap.h" #include "lldb/Core/UniqueCStringMap.h"
#include "lldb/Core/dwarf.h" #include "lldb/Core/dwarf.h"
#include "lldb/Expression/DWARFExpression.h" #include "lldb/Expression/DWARFExpression.h"
#include "lldb/Symbol/DebugMacros.h" #include "lldb/Symbol/DebugMacros.h"
#include "lldb/Symbol/SymbolContext.h" #include "lldb/Symbol/SymbolContext.h"
#include "lldb/Symbol/SymbolFile.h" #include "lldb/Symbol/SymbolFile.h"
#include "lldb/Utility/ConstString.h" #include "lldb/Utility/ConstString.h"
#include "lldb/Utility/Flags.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/lldb-private.h" #include "lldb/lldb-private.h"
#include "DWARFDataExtractor.h" #include "DWARFDataExtractor.h"
#include "DWARFDefines.h" #include "DWARFDefines.h"
#include "DWARFIndex.h" #include "DWARFIndex.h"
#include "UniqueDWARFASTType.h" #include "UniqueDWARFASTType.h"
//---------------------------------------------------------------------- //----------------------------------------------------------------------
▲ Show 20 Lines • Show All 475 Lines • Show Last 20 Lines

lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h

//===-- SymbolFileDWARFDebugMap.h ------------------------------*- C++ -*-===// //===-- SymbolFileDWARFDebugMap.h ------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#ifndef SymbolFileDWARF_SymbolFileDWARFDebugMap_h_ #ifndef SymbolFileDWARF_SymbolFileDWARFDebugMap_h_
#define SymbolFileDWARF_SymbolFileDWARFDebugMap_h_ #define SymbolFileDWARF_SymbolFileDWARFDebugMap_h_
#include "lldb/Symbol/SymbolFile.h"
#include "lldb/Utility/RangeMap.h"
#include "llvm/Support/Chrono.h"
#include <bitset> #include <bitset>
#include <map> #include <map>
#include <vector> #include <vector>
#include "lldb/Core/RangeMap.h"
#include "lldb/Symbol/SymbolFile.h"
#include "llvm/Support/Chrono.h"
#include "UniqueDWARFASTType.h" #include "UniqueDWARFASTType.h"
class SymbolFileDWARF; class SymbolFileDWARF;
class DWARFDebugAranges; class DWARFDebugAranges;
class DWARFDeclContext; class DWARFDeclContext;
class SymbolFileDWARFDebugMap : public lldb_private::SymbolFile { class SymbolFileDWARFDebugMap : public lldb_private::SymbolFile {
public: public:
▲ Show 20 Lines • Show All 363 Lines • Show Last 20 Lines

lldb/trunk/source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.cpp

//===-- SymbolFileDWARFDebugMap.cpp -----------------------------*- C++ -*-===// //===-- SymbolFileDWARFDebugMap.cpp -----------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#include "SymbolFileDWARFDebugMap.h" #include "SymbolFileDWARFDebugMap.h"
#include "DWARFDebugAranges.h" #include "DWARFDebugAranges.h"
#include "lldb/Core/Module.h" #include "lldb/Core/Module.h"
#include "lldb/Core/ModuleList.h" #include "lldb/Core/ModuleList.h"
#include "lldb/Core/PluginManager.h" #include "lldb/Core/PluginManager.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Core/Section.h" #include "lldb/Core/Section.h"
#include "lldb/Host/FileSystem.h" #include "lldb/Host/FileSystem.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/Utility/RegularExpression.h" #include "lldb/Utility/RegularExpression.h"
#include "lldb/Utility/Timer.h" #include "lldb/Utility/Timer.h"
//#define DEBUG_OSO_DMAP // DO NOT CHECKIN WITH THIS NOT COMMENTED OUT //#define DEBUG_OSO_DMAP // DO NOT CHECKIN WITH THIS NOT COMMENTED OUT
#if defined(DEBUG_OSO_DMAP) #if defined(DEBUG_OSO_DMAP)
#include "lldb/Core/StreamFile.h" #include "lldb/Core/StreamFile.h"
#endif #endif
▲ Show 20 Lines • Show All 1,419 Lines • Show Last 20 Lines

lldb/trunk/source/Target/Memory.cpp

//===-- Memory.cpp ----------------------------------------------*- C++ -*-===// //===-- Memory.cpp ----------------------------------------------*- C++ -*-===//
// //
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information. // See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// //
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
#include "lldb/Target/Memory.h" #include "lldb/Target/Memory.h"
#include "lldb/Core/RangeMap.h"
#include "lldb/Target/Process.h" #include "lldb/Target/Process.h"
#include "lldb/Utility/DataBufferHeap.h" #include "lldb/Utility/DataBufferHeap.h"
#include "lldb/Utility/Log.h" #include "lldb/Utility/Log.h"
#include "lldb/Utility/RangeMap.h"
#include "lldb/Utility/State.h" #include "lldb/Utility/State.h"
#include <cinttypes> #include <cinttypes>
#include <memory> #include <memory>
using namespace lldb; using namespace lldb;
using namespace lldb_private; using namespace lldb_private;
▲ Show 20 Lines • Show All 397 Lines • Show Last 20 Lines

lldb/trunk/unittests/Core/CMakeLists.txt

add_lldb_unittest(LLDBCoreTests add_lldb_unittest(LLDBCoreTests
MangledTest.cpp MangledTest.cpp
RangeMapTest.cpp
RangeTest.cpp
RichManglingContextTest.cpp RichManglingContextTest.cpp
StreamCallbackTest.cpp StreamCallbackTest.cpp
LINK_LIBS LINK_LIBS
lldbCore lldbCore
lldbHost lldbHost
lldbSymbol lldbSymbol
lldbPluginObjectFileELF lldbPluginObjectFileELF
Show All 13 Lines

lldb/trunk/unittests/Core/RangeMapTest.cpp

//===-- RangeTest.cpp ----------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "lldb/Core/RangeMap.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"
using namespace lldb_private;
using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>;
using EntryT = RangeDataVectorT::Entry;
static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {
return testing::Pointee(testing::Field(&EntryT::data, ID));
}
TEST(RangeDataVector, FindEntryThatContains) {
RangeDataVectorT Map;
uint32_t NextID = 0;
Map.Append(EntryT(0, 10, NextID++));
Map.Append(EntryT(10, 10, NextID++));
Map.Append(EntryT(20, 10, NextID++));
Map.Sort();
EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0));
EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0));
EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1));
EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1));
EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2));
EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2));
EXPECT_THAT(Map.FindEntryThatContains(30), nullptr);
}
TEST(RangeDataVector, FindEntryThatContains_Overlap) {
RangeDataVectorT Map;
uint32_t NextID = 0;
Map.Append(EntryT(0, 40, NextID++));
Map.Append(EntryT(10, 20, NextID++));
Map.Append(EntryT(20, 10, NextID++));
Map.Sort();
// With overlapping intervals, the intention seems to be to return the first
// interval which contains the address.
EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0));
// However, this does not always succeed.
// TODO: This should probably return the range (0, 40) as well.
EXPECT_THAT(Map.FindEntryThatContains(35), nullptr);
}

lldb/trunk/unittests/Core/RangeTest.cpp

//===-- RangeTest.cpp ----------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "lldb/Core/RangeMap.h"
#include <cstdint>
#include <type_traits>
#include "gtest/gtest.h"
using namespace lldb;
using namespace lldb_private;
TEST(RangeTest, SizeTypes) {
Range<lldb::addr_t, uint32_t> r;
static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeBase())>::value,
"RangeBase type is not equal to the given one.");
static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeEnd())>::value,
"RangeEnd type is not equal to the given one.");
static_assert(std::is_same<uint32_t, decltype(r.GetByteSize())>::value,
"Size type is not equal to the given one.");
}
typedef Range<lldb::addr_t, uint32_t> RangeT;
TEST(RangeTest, DefaultConstructor) {
RangeT r;
EXPECT_FALSE(r.IsValid());
EXPECT_EQ(0U, r.GetByteSize());
EXPECT_EQ(0U, r.GetRangeBase());
EXPECT_EQ(0U, r.GetRangeEnd());
}
TEST(RangeTest, Constructor) {
RangeT r(3, 5);
EXPECT_TRUE(r.IsValid());
EXPECT_EQ(5U, r.GetByteSize());
EXPECT_EQ(3U, r.GetRangeBase());
EXPECT_EQ(8U, r.GetRangeEnd());
}
TEST(RangeTest, Copy) {
RangeT orig(3, 5);
RangeT r = orig;
EXPECT_TRUE(r.IsValid());
EXPECT_EQ(5U, r.GetByteSize());
EXPECT_EQ(3U, r.GetRangeBase());
EXPECT_EQ(8U, r.GetRangeEnd());
}
TEST(RangeTest, Clear) {
RangeT r(3, 5);
r.Clear();
EXPECT_TRUE(r == RangeT());
}
TEST(RangeTest, ClearWithStarAddress) {
RangeT r(3, 5);
r.Clear(4);
EXPECT_TRUE(r == RangeT(4, 0));
}
TEST(RangeTest, SetRangeBase) {
RangeT r(3, 5);
r.SetRangeBase(6);
EXPECT_EQ(6U, r.GetRangeBase());
EXPECT_EQ(11U, r.GetRangeEnd());
EXPECT_EQ(5U, r.GetByteSize());
}
TEST(RangeTest, Slide) {
RangeT r(3, 5);
r.Slide(1);
EXPECT_EQ(4U, r.GetRangeBase());
EXPECT_EQ(9U, r.GetRangeEnd());
EXPECT_EQ(5U, r.GetByteSize());
r.Slide(2);
EXPECT_EQ(6U, r.GetRangeBase());
EXPECT_EQ(11U, r.GetRangeEnd());
EXPECT_EQ(5U, r.GetByteSize());
}
TEST(RangeTest, SlideZero) {
RangeT r(3, 5);
r.Slide(0);
EXPECT_EQ(3U, r.GetRangeBase());
EXPECT_EQ(8U, r.GetRangeEnd());
EXPECT_EQ(5U, r.GetByteSize());
}
TEST(RangeTest, ContainsAddr) {
RangeT r(3, 5);
EXPECT_FALSE(r.Contains(0));
EXPECT_FALSE(r.Contains(1));
EXPECT_FALSE(r.Contains(2));
EXPECT_TRUE(r.Contains(3));
EXPECT_TRUE(r.Contains(4));
EXPECT_TRUE(r.Contains(5));
EXPECT_TRUE(r.Contains(6));
EXPECT_TRUE(r.Contains(7));
EXPECT_FALSE(r.Contains(8));
EXPECT_FALSE(r.Contains(9));
EXPECT_FALSE(r.Contains(10));
}
TEST(RangeTest, ContainsAddrInvalid) {
RangeT r;
EXPECT_FALSE(r.Contains(0));
EXPECT_FALSE(r.Contains(1));
EXPECT_FALSE(r.Contains(2));
EXPECT_FALSE(r.Contains(3));
EXPECT_FALSE(r.Contains(4));
}
TEST(RangeTest, ContainsEndInclusive) {
RangeT r(3, 5);
EXPECT_FALSE(r.ContainsEndInclusive(0));
EXPECT_FALSE(r.ContainsEndInclusive(1));
EXPECT_FALSE(r.ContainsEndInclusive(2));
EXPECT_TRUE(r.ContainsEndInclusive(3));
EXPECT_TRUE(r.ContainsEndInclusive(4));
EXPECT_TRUE(r.ContainsEndInclusive(5));
EXPECT_TRUE(r.ContainsEndInclusive(6));
EXPECT_TRUE(r.ContainsEndInclusive(7));
EXPECT_TRUE(r.ContainsEndInclusive(8));
EXPECT_FALSE(r.ContainsEndInclusive(9));
EXPECT_FALSE(r.ContainsEndInclusive(10));
}
TEST(RangeTest, ContainsEndInclusiveInvalid) {
RangeT r;
// FIXME: This is probably not intended.
EXPECT_TRUE(r.ContainsEndInclusive(0));
EXPECT_FALSE(r.ContainsEndInclusive(1));
EXPECT_FALSE(r.ContainsEndInclusive(2));
}
TEST(RangeTest, ContainsRange) {
RangeT r(3, 5);
// Range always contains itself.
EXPECT_TRUE(r.Contains(r));
// Invalid range.
EXPECT_FALSE(r.Contains(RangeT()));
// Range starts and ends before.
EXPECT_FALSE(r.Contains(RangeT(0, 3)));
// Range starts before but contains beginning.
EXPECT_FALSE(r.Contains(RangeT(0, 4)));
// Range starts before but contains beginning and more.
EXPECT_FALSE(r.Contains(RangeT(0, 5)));
// Range starts before and contains the other.
EXPECT_FALSE(r.Contains(RangeT(0, 9)));
// Range is fully inside.
EXPECT_TRUE(r.Contains(RangeT(4, 3)));
// Range has same start, but not as large.
EXPECT_TRUE(r.Contains(RangeT(3, 4)));
// Range has same end, but starts earlier.
EXPECT_TRUE(r.Contains(RangeT(4, 4)));
// Range starts inside, but stops after the end of r.
EXPECT_FALSE(r.Contains(RangeT(4, 5)));
// Range starts directly after r.
EXPECT_FALSE(r.Contains(RangeT(8, 2)));
// Range starts directly after r.
EXPECT_FALSE(r.Contains(RangeT(9, 2)));
// Invalid range with different start.
// FIXME: The first two probably not intended.
EXPECT_TRUE(r.Contains(RangeT(3, 0)));
EXPECT_TRUE(r.Contains(RangeT(4, 0)));
EXPECT_FALSE(r.Contains(RangeT(8, 0)));
}
TEST(RangeTest, ContainsRangeStartingFromZero) {
RangeT r(0, 3);
EXPECT_TRUE(r.Contains(r));
// FIXME: This is probably not intended.
EXPECT_TRUE(r.Contains(RangeT()));
}
TEST(RangeTest, Union) {
RangeT r(3, 5);
// Ranges that we can't merge because it's not adjoin/intersecting.
EXPECT_FALSE(r.Union(RangeT(9, 1)));
// Check that we didn't modify our range.
EXPECT_EQ(r, RangeT(3, 5));
// Another range we can't merge, but before r.
EXPECT_FALSE(r.Union(RangeT(1, 1)));
EXPECT_EQ(r, RangeT(3, 5));
// Merge an adjoin range after.
EXPECT_TRUE(r.Union(RangeT(8, 2)));
EXPECT_EQ(r, RangeT(3, 7));
// Merge an adjoin range before.
EXPECT_TRUE(r.Union(RangeT(1, 2)));
EXPECT_EQ(r, RangeT(1, 9));
// Merge an intersecting range after.
EXPECT_TRUE(r.Union(RangeT(8, 3)));
EXPECT_EQ(r, RangeT(1, 10));
// Merge an intersecting range before.
EXPECT_TRUE(r.Union(RangeT(0, 1)));
EXPECT_EQ(r, RangeT(0, 11));
// Merge a few ranges inside that shouldn't do anything.
EXPECT_TRUE(r.Union(RangeT(0, 3)));
EXPECT_EQ(r, RangeT(0, 11));
EXPECT_TRUE(r.Union(RangeT(5, 1)));
EXPECT_EQ(r, RangeT(0, 11));
EXPECT_TRUE(r.Union(RangeT(9, 2)));
EXPECT_EQ(r, RangeT(0, 11));
}
TEST(RangeTest, DoesAdjoinOrIntersect) {
RangeT r(3, 4);
EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(1, 1)));
EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(1, 2)));
EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(2, 2)));
EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(4, 2)));
EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(6, 2)));
EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(7, 2)));
EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(8, 2)));
}
TEST(RangeTest, DoesIntersect) {
RangeT r(3, 4);
EXPECT_FALSE(r.DoesIntersect(RangeT(1, 1)));
EXPECT_FALSE(r.DoesIntersect(RangeT(1, 2)));
EXPECT_TRUE(r.DoesIntersect(RangeT(2, 2)));
EXPECT_TRUE(r.DoesIntersect(RangeT(4, 2)));
EXPECT_TRUE(r.DoesIntersect(RangeT(6, 2)));
EXPECT_FALSE(r.DoesIntersect(RangeT(7, 2)));
EXPECT_FALSE(r.DoesIntersect(RangeT(8, 2)));
}
TEST(RangeTest, LessThan) {
RangeT r(10, 20);
// Equal range.
EXPECT_FALSE(r < RangeT(10, 20));
EXPECT_FALSE(RangeT(10, 20) < r);
auto expect_ordered_less_than = [](RangeT r1, RangeT r2) {
EXPECT_TRUE(r1 < r2);
EXPECT_FALSE(r2 < r1);
};
// Same start, but bigger size.
expect_ordered_less_than(r, RangeT(10, 21));
// Start before and ends before.
expect_ordered_less_than(RangeT(9, 20), r);
// Start before and equal size.
expect_ordered_less_than(RangeT(9, 21), r);
// Start before and bigger size.
expect_ordered_less_than(RangeT(9, 22), r);
// Start after and ends before.
expect_ordered_less_than(r, RangeT(11, 18));
// Start after and equal size.
expect_ordered_less_than(r, RangeT(11, 19));
// Start after and bigger size.
expect_ordered_less_than(r, RangeT(11, 20));
}
TEST(RangeTest, Equal) {
RangeT r(10, 20);
// Equal range.
EXPECT_TRUE(r == RangeT(10, 20));
// Same start, different size.
EXPECT_FALSE(r == RangeT(10, 21));
// Different start, same size.
EXPECT_FALSE(r == RangeT(9, 20));
// Different start, different size.
EXPECT_FALSE(r == RangeT(9, 21));
EXPECT_FALSE(r == RangeT(11, 19));
}
TEST(RangeTest, NotEqual) {
RangeT r(10, 20);
EXPECT_FALSE(r != RangeT(10, 20));
EXPECT_TRUE(r != RangeT(10, 21));
EXPECT_TRUE(r != RangeT(9, 20));
EXPECT_TRUE(r != RangeT(9, 21));
}
// Comparison tests for invalid ranges (size == 0).
TEST(RangeTest, LessThanInvalid) {
EXPECT_TRUE(RangeT() < RangeT(1, 0));
EXPECT_TRUE(RangeT() < RangeT(2, 0));
EXPECT_TRUE(RangeT(1, 0) < RangeT(2, 0));
}
TEST(RangeTest, EqualInvalid) {
RangeT r;
EXPECT_TRUE(r == RangeT());
// Another invalid range, but with a different start.
EXPECT_FALSE(r == RangeT(3, 0));
}
TEST(RangeTest, NotEqualInvalid) {
RangeT r;
EXPECT_FALSE(r != RangeT());
EXPECT_FALSE(r == RangeT(3, 0));
}

lldb/trunk/unittests/Utility/CMakeLists.txt

Show All 13 Linesadd_lldb_unittest(UtilityTests
FileSpecTest.cpp FileSpecTest.cpp
FlagsTest.cpp FlagsTest.cpp
JSONTest.cpp JSONTest.cpp
ListenerTest.cpp ListenerTest.cpp
LogTest.cpp LogTest.cpp
NameMatchesTest.cpp NameMatchesTest.cpp
PredicateTest.cpp PredicateTest.cpp
ProcessInfoTest.cpp ProcessInfoTest.cpp
RangeMapTest.cpp
RangeTest.cpp
RegisterValueTest.cpp RegisterValueTest.cpp
ReproducerTest.cpp ReproducerTest.cpp
ReproducerInstrumentationTest.cpp ReproducerInstrumentationTest.cpp
ScalarTest.cpp ScalarTest.cpp
StateTest.cpp StateTest.cpp
StatusTest.cpp StatusTest.cpp
StreamTeeTest.cpp StreamTeeTest.cpp
StreamTest.cpp StreamTest.cpp
Show All 24 Lines

lldb/trunk/unittests/Utility/RangeMapTest.cpp

//===-- RangeTest.cpp ----------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "lldb/Utility/RangeMap.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"
using namespace lldb_private;
using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>;
using EntryT = RangeDataVectorT::Entry;
static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {
return testing::Pointee(testing::Field(&EntryT::data, ID));
}
TEST(RangeDataVector, FindEntryThatContains) {
RangeDataVectorT Map;
uint32_t NextID = 0;
Map.Append(EntryT(0, 10, NextID++));
Map.Append(EntryT(10, 10, NextID++));
Map.Append(EntryT(20, 10, NextID++));
Map.Sort();
EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0));
EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0));
EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1));
EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1));
EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2));
EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2));
EXPECT_THAT(Map.FindEntryThatContains(30), nullptr);
}
TEST(RangeDataVector, FindEntryThatContains_Overlap) {
RangeDataVectorT Map;
uint32_t NextID = 0;
Map.Append(EntryT(0, 40, NextID++));
Map.Append(EntryT(10, 20, NextID++));
Map.Append(EntryT(20, 10, NextID++));
Map.Sort();
// With overlapping intervals, the intention seems to be to return the first
// interval which contains the address.
EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0));
// However, this does not always succeed.
// TODO: This should probably return the range (0, 40) as well.
EXPECT_THAT(Map.FindEntryThatContains(35), nullptr);
}

lldb/trunk/unittests/Utility/RangeTest.cpp

//===-- RangeTest.cpp ----------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "lldb/Utility/RangeMap.h"
#include <cstdint>
#include <type_traits>
#include "gtest/gtest.h"
using namespace lldb;
using namespace lldb_private;
TEST(RangeTest, SizeTypes) {
Range<lldb::addr_t, uint32_t> r;
static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeBase())>::value,
"RangeBase type is not equal to the given one.");
static_assert(std::is_same<lldb::addr_t, decltype(r.GetRangeEnd())>::value,
"RangeEnd type is not equal to the given one.");
static_assert(std::is_same<uint32_t, decltype(r.GetByteSize())>::value,
"Size type is not equal to the given one.");
}
typedef Range<lldb::addr_t, uint32_t> RangeT;
TEST(RangeTest, DefaultConstructor) {
RangeT r;
EXPECT_FALSE(r.IsValid());
EXPECT_EQ(0U, r.GetByteSize());
EXPECT_EQ(0U, r.GetRangeBase());
EXPECT_EQ(0U, r.GetRangeEnd());
}
TEST(RangeTest, Constructor) {
RangeT r(3, 5);
EXPECT_TRUE(r.IsValid());
EXPECT_EQ(5U, r.GetByteSize());
EXPECT_EQ(3U, r.GetRangeBase());
EXPECT_EQ(8U, r.GetRangeEnd());
}
TEST(RangeTest, Copy) {
RangeT orig(3, 5);
RangeT r = orig;
EXPECT_TRUE(r.IsValid());
EXPECT_EQ(5U, r.GetByteSize());
EXPECT_EQ(3U, r.GetRangeBase());
EXPECT_EQ(8U, r.GetRangeEnd());
}
TEST(RangeTest, Clear) {
RangeT r(3, 5);
r.Clear();
EXPECT_TRUE(r == RangeT());
}
TEST(RangeTest, ClearWithStarAddress) {
RangeT r(3, 5);
r.Clear(4);
EXPECT_TRUE(r == RangeT(4, 0));
}
TEST(RangeTest, SetRangeBase) {
RangeT r(3, 5);
r.SetRangeBase(6);
EXPECT_EQ(6U, r.GetRangeBase());
EXPECT_EQ(11U, r.GetRangeEnd());
EXPECT_EQ(5U, r.GetByteSize());
}
TEST(RangeTest, Slide) {
RangeT r(3, 5);
r.Slide(1);
EXPECT_EQ(4U, r.GetRangeBase());
EXPECT_EQ(9U, r.GetRangeEnd());
EXPECT_EQ(5U, r.GetByteSize());
r.Slide(2);
EXPECT_EQ(6U, r.GetRangeBase());
EXPECT_EQ(11U, r.GetRangeEnd());
EXPECT_EQ(5U, r.GetByteSize());
}
TEST(RangeTest, SlideZero) {
RangeT r(3, 5);
r.Slide(0);
EXPECT_EQ(3U, r.GetRangeBase());
EXPECT_EQ(8U, r.GetRangeEnd());
EXPECT_EQ(5U, r.GetByteSize());
}
TEST(RangeTest, ContainsAddr) {
RangeT r(3, 5);
EXPECT_FALSE(r.Contains(0));
EXPECT_FALSE(r.Contains(1));
EXPECT_FALSE(r.Contains(2));
EXPECT_TRUE(r.Contains(3));
EXPECT_TRUE(r.Contains(4));
EXPECT_TRUE(r.Contains(5));
EXPECT_TRUE(r.Contains(6));
EXPECT_TRUE(r.Contains(7));
EXPECT_FALSE(r.Contains(8));
EXPECT_FALSE(r.Contains(9));
EXPECT_FALSE(r.Contains(10));
}
TEST(RangeTest, ContainsAddrInvalid) {
RangeT r;
EXPECT_FALSE(r.Contains(0));
EXPECT_FALSE(r.Contains(1));
EXPECT_FALSE(r.Contains(2));
EXPECT_FALSE(r.Contains(3));
EXPECT_FALSE(r.Contains(4));
}
TEST(RangeTest, ContainsEndInclusive) {
RangeT r(3, 5);
EXPECT_FALSE(r.ContainsEndInclusive(0));
EXPECT_FALSE(r.ContainsEndInclusive(1));
EXPECT_FALSE(r.ContainsEndInclusive(2));
EXPECT_TRUE(r.ContainsEndInclusive(3));
EXPECT_TRUE(r.ContainsEndInclusive(4));
EXPECT_TRUE(r.ContainsEndInclusive(5));
EXPECT_TRUE(r.ContainsEndInclusive(6));
EXPECT_TRUE(r.ContainsEndInclusive(7));
EXPECT_TRUE(r.ContainsEndInclusive(8));
EXPECT_FALSE(r.ContainsEndInclusive(9));
EXPECT_FALSE(r.ContainsEndInclusive(10));
}
TEST(RangeTest, ContainsEndInclusiveInvalid) {
RangeT r;
// FIXME: This is probably not intended.
EXPECT_TRUE(r.ContainsEndInclusive(0));
EXPECT_FALSE(r.ContainsEndInclusive(1));
EXPECT_FALSE(r.ContainsEndInclusive(2));
}
TEST(RangeTest, ContainsRange) {
RangeT r(3, 5);
// Range always contains itself.
EXPECT_TRUE(r.Contains(r));
// Invalid range.
EXPECT_FALSE(r.Contains(RangeT()));
// Range starts and ends before.
EXPECT_FALSE(r.Contains(RangeT(0, 3)));
// Range starts before but contains beginning.
EXPECT_FALSE(r.Contains(RangeT(0, 4)));
// Range starts before but contains beginning and more.
EXPECT_FALSE(r.Contains(RangeT(0, 5)));
// Range starts before and contains the other.
EXPECT_FALSE(r.Contains(RangeT(0, 9)));
// Range is fully inside.
EXPECT_TRUE(r.Contains(RangeT(4, 3)));
// Range has same start, but not as large.
EXPECT_TRUE(r.Contains(RangeT(3, 4)));
// Range has same end, but starts earlier.
EXPECT_TRUE(r.Contains(RangeT(4, 4)));
// Range starts inside, but stops after the end of r.
EXPECT_FALSE(r.Contains(RangeT(4, 5)));
// Range starts directly after r.
EXPECT_FALSE(r.Contains(RangeT(8, 2)));
// Range starts directly after r.
EXPECT_FALSE(r.Contains(RangeT(9, 2)));
// Invalid range with different start.
// FIXME: The first two probably not intended.
EXPECT_TRUE(r.Contains(RangeT(3, 0)));
EXPECT_TRUE(r.Contains(RangeT(4, 0)));
EXPECT_FALSE(r.Contains(RangeT(8, 0)));
}
TEST(RangeTest, ContainsRangeStartingFromZero) {
RangeT r(0, 3);
EXPECT_TRUE(r.Contains(r));
// FIXME: This is probably not intended.
EXPECT_TRUE(r.Contains(RangeT()));
}
TEST(RangeTest, Union) {
RangeT r(3, 5);
// Ranges that we can't merge because it's not adjoin/intersecting.
EXPECT_FALSE(r.Union(RangeT(9, 1)));
// Check that we didn't modify our range.
EXPECT_EQ(r, RangeT(3, 5));
// Another range we can't merge, but before r.
EXPECT_FALSE(r.Union(RangeT(1, 1)));
EXPECT_EQ(r, RangeT(3, 5));
// Merge an adjoin range after.
EXPECT_TRUE(r.Union(RangeT(8, 2)));
EXPECT_EQ(r, RangeT(3, 7));
// Merge an adjoin range before.
EXPECT_TRUE(r.Union(RangeT(1, 2)));
EXPECT_EQ(r, RangeT(1, 9));
// Merge an intersecting range after.
EXPECT_TRUE(r.Union(RangeT(8, 3)));
EXPECT_EQ(r, RangeT(1, 10));
// Merge an intersecting range before.
EXPECT_TRUE(r.Union(RangeT(0, 1)));
EXPECT_EQ(r, RangeT(0, 11));
// Merge a few ranges inside that shouldn't do anything.
EXPECT_TRUE(r.Union(RangeT(0, 3)));
EXPECT_EQ(r, RangeT(0, 11));
EXPECT_TRUE(r.Union(RangeT(5, 1)));
EXPECT_EQ(r, RangeT(0, 11));
EXPECT_TRUE(r.Union(RangeT(9, 2)));
EXPECT_EQ(r, RangeT(0, 11));
}
TEST(RangeTest, DoesAdjoinOrIntersect) {
RangeT r(3, 4);
EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(1, 1)));
EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(1, 2)));
EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(2, 2)));
EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(4, 2)));
EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(6, 2)));
EXPECT_TRUE(r.DoesAdjoinOrIntersect(RangeT(7, 2)));
EXPECT_FALSE(r.DoesAdjoinOrIntersect(RangeT(8, 2)));
}
TEST(RangeTest, DoesIntersect) {
RangeT r(3, 4);
EXPECT_FALSE(r.DoesIntersect(RangeT(1, 1)));
EXPECT_FALSE(r.DoesIntersect(RangeT(1, 2)));
EXPECT_TRUE(r.DoesIntersect(RangeT(2, 2)));
EXPECT_TRUE(r.DoesIntersect(RangeT(4, 2)));
EXPECT_TRUE(r.DoesIntersect(RangeT(6, 2)));
EXPECT_FALSE(r.DoesIntersect(RangeT(7, 2)));
EXPECT_FALSE(r.DoesIntersect(RangeT(8, 2)));
}
TEST(RangeTest, LessThan) {
RangeT r(10, 20);
// Equal range.
EXPECT_FALSE(r < RangeT(10, 20));
EXPECT_FALSE(RangeT(10, 20) < r);
auto expect_ordered_less_than = [](RangeT r1, RangeT r2) {
EXPECT_TRUE(r1 < r2);
EXPECT_FALSE(r2 < r1);
};
// Same start, but bigger size.
expect_ordered_less_than(r, RangeT(10, 21));
// Start before and ends before.
expect_ordered_less_than(RangeT(9, 20), r);
// Start before and equal size.
expect_ordered_less_than(RangeT(9, 21), r);
// Start before and bigger size.
expect_ordered_less_than(RangeT(9, 22), r);
// Start after and ends before.
expect_ordered_less_than(r, RangeT(11, 18));
// Start after and equal size.
expect_ordered_less_than(r, RangeT(11, 19));
// Start after and bigger size.
expect_ordered_less_than(r, RangeT(11, 20));
}
TEST(RangeTest, Equal) {
RangeT r(10, 20);
// Equal range.
EXPECT_TRUE(r == RangeT(10, 20));
// Same start, different size.
EXPECT_FALSE(r == RangeT(10, 21));
// Different start, same size.
EXPECT_FALSE(r == RangeT(9, 20));
// Different start, different size.
EXPECT_FALSE(r == RangeT(9, 21));
EXPECT_FALSE(r == RangeT(11, 19));
}
TEST(RangeTest, NotEqual) {
RangeT r(10, 20);
EXPECT_FALSE(r != RangeT(10, 20));
EXPECT_TRUE(r != RangeT(10, 21));
EXPECT_TRUE(r != RangeT(9, 20));
EXPECT_TRUE(r != RangeT(9, 21));
}
// Comparison tests for invalid ranges (size == 0).
TEST(RangeTest, LessThanInvalid) {
EXPECT_TRUE(RangeT() < RangeT(1, 0));
EXPECT_TRUE(RangeT() < RangeT(2, 0));
EXPECT_TRUE(RangeT(1, 0) < RangeT(2, 0));
}
TEST(RangeTest, EqualInvalid) {
RangeT r;
EXPECT_TRUE(r == RangeT());
// Another invalid range, but with a different start.
EXPECT_FALSE(r == RangeT(3, 0));
}
TEST(RangeTest, NotEqualInvalid) {
RangeT r;
EXPECT_FALSE(r != RangeT());
EXPECT_FALSE(r == RangeT(3, 0));
}
lldb/trunk/unittests/Core/RangeMapTest.cpp