This is an archive of the discontinued LLVM Phabricator instance.

[NFC] Cleanup RangeMap.h
ClosedPublic

Authored by tberghammer on Feb 1 2016, 6:47 AM.

Download Raw Diff

Details

Reviewers

clayborg
labath

Commits

rG7a2a5ce0589f: [NFC] Cleanup RangeMap.h
rLLDB259538: [NFC] Cleanup RangeMap.h
rL259538: [NFC] Cleanup RangeMap.h

Summary

[NFC] Cleanup RangeMap.h

The file contained very similar 4 implementation of the same data
structure with a lot of duplicated code and some minor API differences.
This CL refactor the class to eliminate the duplicated codes and to
unify the APIs.

RangeMap.h also contained a class called AddressDataArray what have very
little added functionality over an std::vector and used only by
ObjectFileMachO The CL moves the class to ObjectFileMachO.cpp as it isn't
belongs into RangeMap.h and shouldn't be used in new places anyway
because of the little added functionality.

Note1: As the change touches most of the line of RangeMap.h I run clang-format on the full file because we lose the history anyway.
Note2: I would prefer to get rid of AddressDataArray all together but I don't understand ObjectFileMachO well enough to make the change with high confidence

Diff Detail

Repository: rL LLVM

Event Timeline

tberghammer updated this revision to Diff 46531.Feb 1 2016, 6:47 AM

tberghammer retitled this revision from to [NFC] Cleanup RangeMap.h.

tberghammer updated this object.

tberghammer added reviewers: clayborg, labath.

tberghammer added a subscriber: lldb-commits.

Looks fine. A few things I don't like, but I can live with:

Making constructors appear all on one line does save space, but it means you can't debug very well as stepping into these constructors will stop on the constructor line and then if you step, you will step over and out of the entire thing. Granted these classes are very simple and probably don't require debugging anymore, but it is a drawback to clang-format.
Many functions had variables that were put into temporaries like:

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;
}

were reduced to lines like the following:

bool
DoesAdjoinOrIntersect(const Range &rhs) const
{
    return GetRangeBase() <= rhs.GetRangeEnd() && GetRangeEnd() >= rhs.GetRangeBase();
}

So I see the efficiency, but if I step into this function now it means less useful debugging as you will be stepping into and out of functions and you will lose the values and not be able to see what is going on. The compiler will get rid of the temporary variables when it optimizes things so I am not sure why these changes make things better.

This revision is now accepted and ready to land.Feb 1 2016, 11:44 AM

In D16769#340936, @clayborg wrote:

Looks fine. A few things I don't like, but I can live with:

Making constructors appear all on one line does save space, but it means you can't debug very well as stepping into these constructors will stop on the constructor line and then if you step, you will step over and out of the entire thing. Granted these classes are very simple and probably don't require debugging anymore, but it is a drawback to clang-format.

I think if this is not the format we want then we should check clang-format to support our use case. In this specific case I think putting everything in 1 line is fine as you see the function arguments when you step in and I also think clang-format will do something different for constructors with more code in them.

Many functions had variables that were put into temporaries like:
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;
}
were reduced to lines like the following:
bool
DoesAdjoinOrIntersect(const Range &rhs) const
{
    return GetRangeBase() <= rhs.GetRangeEnd() && GetRangeEnd() >= rhs.GetRangeBase();
}
So I see the efficiency, but if I step into this function now it means less useful debugging as you will be stepping into and out of functions and you will lose the values and not be able to see what is going on. The compiler will get rid of the temporary variables when it optimizes things so I am not sure why these changes make things better.

I made these changes intentionally because I feel that inlining these temporaries improve the readability as you don't have to match the very similar 6-7 letter words by eye and it shouldn't hurt debugging too much because you can either evaluate the expression you are interested or just display "*this" or "rhs" as a frame variable. From efficiency perspective they won't matter if the types used are basic types (PODs) but if the compiler can optimize them out if they have a non-trivial constructor/destructor. I can revert those if you want.

No need to revert anything as these classes are stable now and don't need debugging. Just something to be aware of in other cases when you make future changes.

Closed by commit rL259538: [NFC] Cleanup RangeMap.h (authored by tberghammer). · Explain WhyFeb 2 2016, 10:22 AM

This revision was automatically updated to reflect the committed changes.

This needs to be reverted. We've got 92 tests failing when this hit:

http://lab.llvm.org:8080/green/job/lldb_build_test/16222/

In D16769#342069, @tfiala wrote:

This needs to be reverted. We've got 92 tests failing when this hit:

http://lab.llvm.org:8080/green/job/lldb_build_test/16222/

I'm in the process of testing the issues go away with the revert. I'll commit the revert after that.

In D16769#342073, @tfiala wrote:

In D16769#342069, @tfiala wrote:

This needs to be reverted. We've got 92 tests failing when this hit:

http://lab.llvm.org:8080/green/job/lldb_build_test/16222/

I'm in the process of testing the issues go away with the revert. I'll commit the revert after that.

Reverted with r259556.

labath mentioned this in D56170: RangeMap.h: merge RangeDataArray and RangeDataVector.Dec 31 2018, 3:09 AM

labath mentioned this in rL350380: RangeMap.h: merge RangeDataArray and RangeDataVector.Jan 3 2019, 11:18 PM

labath mentioned this in rLLDB350380: RangeMap.h: merge RangeDataArray and RangeDataVector.

Revision Contents

Path

Size

lldb/

trunk/

include/

lldb/

Core/

RangeMap.h

1798 lines

source/

Plugins/

ObjectFile/

Mach-O/

ObjectFileMachO.cpp

175 lines

Diff 46673

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

	Show All 18 Lines
	#include "llvm/ADT/SmallVector.h"			#include "llvm/ADT/SmallVector.h"

	// Project includes			// Project includes
	#include "lldb/lldb-private.h"			#include "lldb/lldb-private.h"

	// Uncomment to make sure all Range objects are sorted when needed			// Uncomment to make sure all Range objects are sorted when needed
	//#define ASSERT_RANGEMAP_ARE_SORTED			//#define ASSERT_RANGEMAP_ARE_SORTED

	namespace lldb_private {			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			// 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".			// base "B", and the type used for the range byte size "S".
	//----------------------------------------------------------------------			//----------------------------------------------------------------------
	template <typename B, typename S>			template <typename B, typename S> struct Range
	struct Range
	{			{
	typedef B BaseType;			typedef B BaseType;
	typedef S SizeType;			typedef S SizeType;

	BaseType base;			BaseType base;
	SizeType size;			SizeType size;

	Range () :			Range() : base(0), size(0) {}
	base (0),
	size (0)
	{
	}

	Range (BaseType b, SizeType s) :			Range(BaseType b, SizeType s) : base(b), size(s) {}
	base (b),
	size (s)
	{
	}

	void			void
	Clear (BaseType b = 0)			Clear(BaseType b = 0)
	{			{
	base = b;			base = b;
	size = 0;			size = 0;
	}			}

	// Set the start value for the range, and keep the same size
	BaseType			BaseType
	GetRangeBase () const			GetRangeBase() const
	{			{
	return base;			return base;
	}			}

	void			void
	SetRangeBase (BaseType b)			SetRangeBase(BaseType b)
	{			{
	base = b;			base = b;
	}			}

	void			void
	Slide (BaseType slide)			Slide(BaseType slide)
	{			{
	base += slide;			base += slide;
	}			}

	BaseType			BaseType
	GetRangeEnd () const			GetRangeEnd() const
	{			{
	return base + size;			return base + size;
	}			}

	void			void
	SetRangeEnd (BaseType end)			SetRangeEnd(BaseType end)
	{			{
	if (end > base)			if (end > base)
	size = end - base;			size = end - base;
	else			else
	size = 0;			size = 0;
	}			}

	SizeType			SizeType
	GetByteSize () const			GetByteSize() const
	{			{
	return size;			return size;
	}			}

	void			void
	SetByteSize (SizeType s)			SetByteSize(SizeType s)
	{			{
	size = s;			size = s;
	}			}

	bool			bool
	IsValid() const			IsValid() const
	{			{
	return size > 0;			return size > 0;
	}			}

	bool			bool
	Contains (BaseType r) const			Contains(BaseType r) const
	{			{
	return (GetRangeBase() <= r) && (r < GetRangeEnd());			return (GetRangeBase() <= r) && (r < GetRangeEnd());
	}			}

	bool			bool
	ContainsEndInclusive (BaseType r) const			ContainsEndInclusive(BaseType r) const
	{			{
	return (GetRangeBase() <= r) && (r <= GetRangeEnd());			return (GetRangeBase() <= r) && (r <= GetRangeEnd());
	}			}

	bool			bool
	Contains (const Range& range) const			Contains(const Range &range) const
	{			{
	return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd());			return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd());
	}			}

	// Returns true if the two ranges adjoing or intersect			// Returns true if the two ranges adjoing or intersect
	bool			bool
	DoesAdjoinOrIntersect (const Range &rhs) const			DoesAdjoinOrIntersect(const Range &rhs) const
	{			{
	const BaseType lhs_base = this->GetRangeBase();			return GetRangeBase() <= rhs.GetRangeEnd() && GetRangeEnd() >= rhs.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			// Returns true if the two ranges intersect
	bool			bool
	DoesIntersect (const Range &rhs) const			DoesIntersect(const Range &rhs) const
	{			{
	const BaseType lhs_base = this->GetRangeBase();			return GetRangeBase() < rhs.GetRangeEnd() && GetRangeEnd() > rhs.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			bool
	operator < (const Range &rhs) const			operator<(const Range &rhs) const
	{			{
	if (base == rhs.base)			return base == rhs.base ? size < rhs.size : base < rhs.base;
	return size < rhs.size;
	return base < rhs.base;
	}			}

	bool			bool
	operator == (const Range &rhs) const			operator==(const Range &rhs) const
	{			{
	return base == rhs.base && size == rhs.size;			return base == rhs.base && size == rhs.size;
	}			}

	bool			bool
	operator != (const Range &rhs) const			operator!=(const Range &rhs) const
	{			{
	return base != rhs.base \|\| size != rhs.size;			return !(*this == rhs);
	}			}
	};			};

	//----------------------------------------------------------------------			//----------------------------------------------------------------------
	// A range array class where you get to define the type of the ranges			// A simple range with data class where you get to define the type of
	// that the collection contains.			// 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>
	template <typename B, typename S, unsigned N>
	class RangeArray
	{			{
	public:			typedef T DataType;
	typedef B BaseType;
	typedef S SizeType;
	typedef Range<B,S> Entry;
	typedef llvm::SmallVector<Entry, N> Collection;

	RangeArray() = default;			DataType data;

	~RangeArray() = default;			RangeData() = default;

	void			RangeData(B base, S size) : Range<B, S>(base, size), data() {}
	Append (const Entry &entry)
	{
	m_entries.push_back (entry);
	}

	bool			RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
	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			bool
	IsSorted () const			operator<(const RangeData &rhs) 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;			if (this->base == rhs.base)
	for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)			return Range<B, S>::operator<(rhs);
	pos->Slide (slide);
	}

	void			return this->base < rhs.base;
	Clear ()
	{
	m_entries.clear();
	}			}

	bool			bool
	IsEmpty () const			operator==(const RangeData &rhs) 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 this->data == rhs.data && Range<B, S>::operator==(rhs);
	}
	}
	}
	return nullptr;
	}			}

	const Entry *			bool
	FindEntryThatContains (const Entry &range) const			operator!=(const RangeData &rhs) 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 !(*this == rhs);
	}
	}
	}			}
	return nullptr;
	}

	protected:
	Collection m_entries;
	};			};

	template <typename B, typename S>			template <typename E, typename C> class RangeVectorBase
	class RangeVector
	{			{
	public:			public:
	typedef B BaseType;			typedef E Entry;
	typedef S SizeType;			typedef C Collection;
	typedef Range<B,S> Entry;			typedef typename Entry::BaseType BaseType;
	typedef std::vector<Entry> Collection;			typedef typename Entry::SizeType SizeType;

	RangeVector() = default;

	~RangeVector() = default;

	void			void
	Append (const Entry &entry)			Append(const Entry &entry)
	{			{
	m_entries.push_back (entry);			m_entries.push_back(entry);
	}			}

	bool			bool
	RemoveEntrtAtIndex (uint32_t idx)			RemoveEntrtAtIndex(uint32_t idx)
	{			{
	if (idx < m_entries.size())			if (idx >= m_entries.size())
	{			return false;

	m_entries.erase (m_entries.begin() + idx);			m_entries.erase(m_entries.begin() + idx);
	return true;			return true;
	}			}
	return false;
	}

	void			void
	Sort ()			Sort()
	{			{
	if (m_entries.size() > 1)
	std::stable_sort (m_entries.begin(), m_entries.end());			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			void
	CombineConsecutiveRanges ()			CombineConsecutiveRanges()
	{			{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED			VerifySorted();
	assert (IsSorted());
	#endif			// Can't combine ranges if we have zero or one range
	// Can't combine if ranges if we have zero or one range			if (m_entries.size() <= 1)
	if (m_entries.size() > 1)			return;
	{
	// The list should be sorted prior to calling this function			// First we determine if we can combine any of the Entry objects so we don't end up
	typename Collection::iterator pos;			// allocating and making a new collection for no reason
	typename Collection::iterator end;
	typename Collection::iterator prev;
	bool can_combine = false;			bool can_combine = false;
	// First we determine if we can combine any of the Entry objects so we			for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
	// 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))			if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
	{			{
	can_combine = true;			can_combine = true;
	break;			break;
	}			}
	}			}

	// We we can combine at least one entry, then we make a new collection			// We we can combine at least one entry, then we make a new collection and populate it
	// and populate it accordingly, and then swap it into place.			// accordingly, and then swap it into place.
	if (can_combine)			if (can_combine)
	{			{
	Collection minimal_ranges;			Collection minimal_ranges;
	for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)			for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
	{			{
	if (prev != end && prev->DoesAdjoinOrIntersect(*pos))			if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
	minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));			minimal_ranges.back().SetRangeEnd(std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
	else			else
	minimal_ranges.push_back (*pos);			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			// Use the swap technique in case our new vector is much smaller. We must swap when
	// release or reduce the memory once it has been allocated/reserved.			// using the STL because std::vector objects never release or reduce the memory once it
				// has been allocated/reserved.
	m_entries.swap (minimal_ranges);			m_entries.swap(minimal_ranges);
	}			}
	}			}
	}

	BaseType			BaseType
	GetMinRangeBase (BaseType fail_value) const			GetMinRangeBase(BaseType fail_value) const
	{			{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED			VerifySorted();
	assert (IsSorted());
	#endif
	if (m_entries.empty())			if (m_entries.empty())
	return fail_value;			return fail_value;
	// m_entries must be sorted, so if we aren't empty, we grab the
	// first range's base			// m_entries must be sorted, so if we aren't empty, we grab the first range's base
	return m_entries.front().GetRangeBase();			return m_entries.front().GetRangeBase();
	}			}

	BaseType			BaseType
	GetMaxRangeEnd (BaseType fail_value) const			GetMaxRangeEnd(BaseType fail_value) const
	{			{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED			VerifySorted();
	assert (IsSorted());
	#endif
	if (m_entries.empty())			if (m_entries.empty())
	return fail_value;			return fail_value;
	// m_entries must be sorted, so if we aren't empty, we grab the
	// last range's end			// m_entries must be sorted, so if we aren't empty, we grab the last range's end
	return m_entries.back().GetRangeEnd();			return m_entries.back().GetRangeEnd();
	}			}

	void			void
	Slide (BaseType slide)			Slide(BaseType slide)
	{			{
	typename Collection::iterator pos, end;			for (auto pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
	for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
	pos->Slide (slide);			pos->Slide(slide);
	}			}

	void			void
	Clear ()			Clear()
	{			{
	m_entries.clear();			m_entries.clear();
	}			}

	void
	Reserve (typename Collection::size_type size)
	{
	m_entries.reserve (size);
	}

	bool			bool
	IsEmpty () const			IsEmpty() const
	{			{
	return m_entries.empty();			return m_entries.empty();
	}			}

	size_t			size_t
	GetSize () const			GetSize() const
	{			{
	return m_entries.size();			return m_entries.size();
	}			}

				Entry *
				GetEntryAtIndex(size_t i)
				{
				return i < m_entries.size() ? &m_entries[i] : nullptr;
				}

	const Entry *			const Entry *
	GetEntryAtIndex (size_t i) const			GetEntryAtIndex(size_t i) const
	{			{
	return ((i < m_entries.size()) ? &m_entries[i] : nullptr);			return i < m_entries.size() ? &m_entries[i] : nullptr;
	}			}

	// Clients must ensure that "i" is a valid index prior to calling this function			// Clients must ensure that "i" is a valid index prior to calling this function
	const Entry &			const Entry &
	GetEntryRef (size_t i) const			GetEntryRef(size_t i) const
	{			{
	return m_entries[i];			return m_entries[i];
	}			}

	Entry *			Entry *
	Back()			Back()
	{			{
	return (m_entries.empty() ? nullptr : &m_entries.back());			return m_entries.empty() ? nullptr : &m_entries.back();
	}			}

	const Entry *			const Entry *
	Back() const			Back() const
	{			{
	return (m_entries.empty() ? nullptr : &m_entries.back());			return m_entries.empty() ? nullptr : &m_entries.back();
	}

	static bool
	BaseLessThan (const Entry& lhs, const Entry& rhs)
	{
	return lhs.GetRangeBase() < rhs.GetRangeBase();
	}			}

	uint32_t			uint32_t
	FindEntryIndexThatContains (B addr) const			FindEntryIndexThatContains(const Entry &range) const
	{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED
	assert (IsSorted());
	#endif
	if (!m_entries.empty())
	{			{
	Entry entry (addr, 1);			VerifySorted();
	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))			if (m_entries.empty())
	{
	return std::distance (begin, pos);
	}
	else if (pos != begin)
	{
	--pos;
	if (pos->Contains(addr))
	return std::distance (begin, pos);
	}
	}
	return UINT32_MAX;			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);

				auto begin = m_entries.begin(), end = m_entries.end(), pos = std::lower_bound(begin, end, range, BaseLessThan);
	if (pos != end && pos->Contains(range))			if (pos != end && pos->Contains(range))
	{			return std::distance(begin, pos);
	return &(*pos);
	}			if (pos != begin)
	else if (pos != begin)
	{			{
	--pos;			--pos;
	if (pos->Contains(range))			if (pos->Contains(range))
	{			return std::distance(begin, pos);
	return &(*pos);
	}
	}
	}
	return nullptr;
	}

	protected:
	Collection m_entries;
	};

	//----------------------------------------------------------------------
	// A simple range with data class where you get to define the type of
	// the range base "B", the type used for the range byte size "S", and
	// the type for the associated data "T".
	//----------------------------------------------------------------------
	template <typename B, typename S, typename T>
	struct RangeData : public Range<B,S>
	{
	typedef T DataType;

	DataType data;

	RangeData () :
	Range<B,S> (),
	data ()
	{
	}			}
				return UINT32_MAX;
	RangeData (B base, S size) :
	Range<B,S> (base, size),
	data ()
	{
	}			}

	RangeData (B base, S size, DataType d) :			uint32_t
	Range<B,S> (base, size),			FindEntryIndexThatContains(BaseType addr) const
	data (d)
	{			{
				return FindEntryIndexThatContains(Entry(addr, 1));
	}			}

	bool			Entry *
	operator < (const RangeData &rhs) const			FindEntryThatContains(BaseType addr)
	{
	if (this->base == rhs.base)
	{			{
	if (this->size == rhs.size)			return GetEntryAtIndex(FindEntryIndexThatContains(addr));
	return this->data < rhs.data;
	else
	return this->size < rhs.size;
	}
	return this->base < rhs.base;
	}			}

	bool			const Entry *
	operator == (const RangeData &rhs) const			FindEntryThatContains(BaseType addr) const
	{			{
	return this->GetRangeBase() == rhs.GetRangeBase() &&			return GetEntryAtIndex(FindEntryIndexThatContains(addr));
	this->GetByteSize() == rhs.GetByteSize() &&
	this->data == rhs.data;
	}			}

	bool			const Entry *
	operator != (const RangeData &rhs) const			FindEntryThatContains(const Entry &range) const
	{			{
	return this->GetRangeBase() != rhs.GetRangeBase() \|\|			return GetEntryAtIndex(FindEntryIndexThatContains(range));
	this->GetByteSize() != rhs.GetByteSize() \|\|
	this->data != rhs.data;
	}			}
	};

	template <typename B, typename S, typename T, unsigned N>
	class RangeDataArray
	{
	public:
	typedef RangeData<B,S,T> Entry;
	typedef llvm::SmallVector<Entry, N> Collection;

	RangeDataArray() = default;

	~RangeDataArray() = default;

	void			void
	Append (const Entry &entry)			Reserve(size_t size)
	{			{
	m_entries.push_back (entry);			m_entries.resize(size);
	}			}

				// Calculate the byte size of ranges with zero byte sizes by finding the next entry with a
				// base address > the current base address
	void			void
	Sort ()			CalculateSizesOfZeroByteSizeRanges()
	{			{
	if (m_entries.size() > 1)			VerifySorted();
	std::stable_sort (m_entries.begin(), m_entries.end());
	}

	#ifdef ASSERT_RANGEMAP_ARE_SORTED			for (auto pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
	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)			if (pos->GetByteSize() == 0)
	return false;
	}
	return true;
	}
	#endif

	void
	CombineConsecutiveEntriesWithEqualData ()
	{			{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED			// Watch out for multiple entries with same address and make sure we find an entry
	assert (IsSorted());			//that is greater than the current base address before we use that for the size
	#endif			auto curr_base = pos->GetRangeBase();
	typename Collection::iterator pos;			for (auto next = pos + 1; next != end; ++next)
	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)			auto next_base = next->GetRangeBase();
				if (next_base > curr_base)
	{			{
	can_combine = true;			pos->SetByteSize(next_base - curr_base);
	break;			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			uint32_t
	Clear ()			FindEntryIndexesThatContain(BaseType addr, std::vector<uint32_t> &indexes) const
	{			{
	m_entries.clear();			VerifySorted();
	}

	bool			if (!m_entries.empty())
	IsEmpty () const
	{			{
	return m_entries.empty();			for (const auto &entry : m_entries)
	}

	size_t
	GetSize () const
	{			{
	return m_entries.size();			if (entry.Contains(addr))
				indexes.push_back(entry.data);
	}			}

	const Entry *
	GetEntryAtIndex (size_t i) const
	{
	return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
	}			}
				return indexes.size();
	// 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			static bool
	BaseLessThan (const Entry& lhs, const Entry& rhs)			BaseLessThan(const Entry &lhs, const Entry &rhs)
	{			{
	return lhs.GetRangeBase() < rhs.GetRangeBase();			return lhs.GetRangeBase() < rhs.GetRangeBase();
	}			}

	uint32_t			protected:
	FindEntryIndexThatContains (B addr) const			void
	{			VerifySorted() 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;
	}

	Entry *
	FindEntryThatContains (B addr)
	{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED
	assert (IsSorted());
	#endif
	if ( !m_entries.empty() )
	{
	Entry entry;
	entry.SetRangeBase(addr);
	entry.SetByteSize(1);
	typename Collection::iterator begin = m_entries.begin();
	typename Collection::iterator end = m_entries.end();
	typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);

	if (pos != end && pos->Contains(addr))
	{
	return &(*pos);
	}
	else if (pos != begin)
	{
	--pos;
	if (pos->Contains(addr))
	{
	return &(*pos);
	}
	}
	}
	return nullptr;
	}

	const Entry *
	FindEntryThatContains (B addr) const
	{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED
	assert (IsSorted());
	#endif
	if ( !m_entries.empty() )
	{
	Entry entry;
	entry.SetRangeBase(addr);
	entry.SetByteSize(1);
	typename Collection::const_iterator begin = m_entries.begin();
	typename Collection::const_iterator end = m_entries.end();
	typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);

	if (pos != end && pos->Contains(addr))
	{
	return &(*pos);
	}
	else if (pos != begin)
	{
	--pos;
	if (pos->Contains(addr))
	{
	return &(*pos);
	}
	}
	}
	return nullptr;
	}

	const Entry *
	FindEntryThatContains (const Entry &range) const
	{			{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED			#ifdef ASSERT_RANGEMAP_ARE_SORTED
	assert (IsSorted());			for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
				assert(prev == end \|\| pos >= prev);
	#endif			#endif
	if ( !m_entries.empty() )
	{
	typename Collection::const_iterator begin = m_entries.begin();
	typename Collection::const_iterator end = m_entries.end();
	typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);

	if (pos != end && pos->Contains(range))
	{
	return &(*pos);
	}
	else if (pos != begin)
	{
	--pos;
	if (pos->Contains(range))
	{
	return &(*pos);
	}
	}
	}
	return nullptr;
	}			}

	Entry *
	Back()
	{
	return (m_entries.empty() ? nullptr : &m_entries.back());
	}

	const Entry *
	Back() const
	{
	return (m_entries.empty() ? nullptr : &m_entries.back());
	}

	protected:
	Collection m_entries;			Collection m_entries;
	};			};

	// Same as RangeDataArray, but uses std::vector as to not			template <typename E, typename S> class RangeDataVectorBase : public RangeVectorBase<E, S>
	// require static storage of N items in the class itself
	template <typename B, typename S, typename T>
	class RangeDataVector
	{			{
	public:			public:
	typedef RangeData<B,S,T> Entry;
	typedef std::vector<Entry> Collection;

	RangeDataVector() = default;

	~RangeDataVector() = default;

	void			void
	Append (const Entry &entry)			CombineConsecutiveEntriesWithEqualData()
	{
	m_entries.push_back (entry);
	}

	void
	Sort ()
	{			{
	if (m_entries.size() > 1)			VerifySorted();
	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			// 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			// 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;			bool can_combine = false;
	// First we determine if we can combine any of the Entry objects so we			for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
	// don't end up allocating and making a new collection for no reason
	for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
	{			{
	if (prev != end && prev->data == pos->data)			if (prev != end && prev->data == pos->data)
	{			{
	can_combine = true;			can_combine = true;
	break;			break;
	}			}
	}			}

	// We we can combine at least one entry, then we make a new collection			// We we can combine at least one entry, then we make a new collection
	// and populate it accordingly, and then swap it into place.			// and populate it accordingly, and then swap it into place.
	if (can_combine)			if (can_combine)
	{			{
	Collection minimal_ranges;			Collection minimal_ranges;
	for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)			for (auto pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
	{			{
	if (prev != end && prev->data == pos->data)			if (prev != end && prev->data == pos->data)
	minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());			minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
	else			else
	minimal_ranges.push_back (*pos);			minimal_ranges.push_back(*pos);
	}			}

	// Use the swap technique in case our new vector is much smaller.			// Use the swap technique in case our new vector is much smaller.
	// We must swap when using the STL because std::vector objects never			// We must swap when using the STL because std::vector objects never
	// release or reduce the memory once it has been allocated/reserved.			// release or reduce the memory once it has been allocated/reserved.
	m_entries.swap (minimal_ranges);			m_entries.swap(minimal_ranges);
	}			}
	}			}

	// Calculate the byte size of ranges with zero byte sizes by finding
	// the next entry with a base address > the current base address
	void
	CalculateSizesOfZeroByteSizeRanges ()
	{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED
	assert (IsSorted());
	#endif
	typename Collection::iterator pos;
	typename Collection::iterator end;
	typename Collection::iterator next;
	for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
	{
	if (pos->GetByteSize() == 0)
	{
	// Watch out for multiple entries with same address and make sure
	// we find an entry that is greater than the current base address
	// before we use that for the size
	auto curr_base = pos->GetRangeBase();
	for (next = pos + 1; next != end; ++next)
	{
	auto next_base = next->GetRangeBase();
	if (next_base > curr_base)
	{
	pos->SetByteSize (next_base - curr_base);
	break;
	}
	}
	}
	}
	}

	void
	Clear ()
	{
	m_entries.clear();
	}

	void
	Reserve (typename Collection::size_type size)
	{
	m_entries.resize (size);
	}

	bool
	IsEmpty () const
	{
	return m_entries.empty();
	}

	size_t
	GetSize () const
	{
	return m_entries.size();
	}

	const Entry *
	GetEntryAtIndex (size_t i) const
	{
	return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
	}

	// Clients must ensure that "i" is a valid index prior to calling this function
	const Entry &
	GetEntryRef (size_t i) const
	{
	return m_entries[i];
	}

	static bool
	BaseLessThan (const Entry& lhs, const Entry& rhs)
	{
	return lhs.GetRangeBase() < rhs.GetRangeBase();
	}

	uint32_t
	FindEntryIndexThatContains (B addr) const
	{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED
	assert (IsSorted());
	#endif
	if ( !m_entries.empty() )
	{
	Entry entry (addr, 1);
	typename Collection::const_iterator begin = m_entries.begin();
	typename Collection::const_iterator end = m_entries.end();
	typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);

	while(pos != begin && pos[-1].Contains(addr))
	--pos;

	if (pos != end && pos->Contains(addr))
	return std::distance (begin, pos);
	}
	return UINT32_MAX;
	}

	uint32_t
	FindEntryIndexesThatContain(B addr, std::vector<uint32_t> &indexes) const
	{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED
	assert (IsSorted());
	#endif

	if (!m_entries.empty())
	{
	typename Collection::const_iterator pos;
	for (const auto &entry : m_entries)
	{
	if (entry.Contains(addr))
	indexes.push_back(entry.data);
	}
	}
	return indexes.size() ;
	}

	Entry *
	FindEntryThatContains (B addr)
	{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED
	assert (IsSorted());
	#endif
	if ( !m_entries.empty() )
	{
	Entry entry;
	entry.SetRangeBase(addr);
	entry.SetByteSize(1);
	typename Collection::iterator begin = m_entries.begin();
	typename Collection::iterator end = m_entries.end();
	typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);

	while(pos != begin && pos[-1].Contains(addr))
	--pos;

	if (pos != end && pos->Contains(addr))
	return &(*pos);
	}
	return nullptr;
	}

	const Entry *
	FindEntryThatContains (B addr) const
	{
	#ifdef ASSERT_RANGEMAP_ARE_SORTED
	assert (IsSorted());
	#endif
	if ( !m_entries.empty() )
	{
	Entry entry;
	entry.SetRangeBase(addr);
	entry.SetByteSize(1);
	typename Collection::const_iterator begin = m_entries.begin();
	typename Collection::const_iterator end = m_entries.end();
	typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);

	while(pos != begin && pos[-1].Contains(addr))
	--pos;

	if (pos != end && 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);

	while(pos != begin && pos[-1].Contains(range))
	--pos;

	if (pos != end && pos->Contains(range))
	return &(*pos);
	}
	return nullptr;
	}

	Entry *
	Back()
	{
	return (m_entries.empty() ? nullptr : &m_entries.back());
	}

	const Entry *
	Back() const
	{
	return (m_entries.empty() ? nullptr : &m_entries.back());
	}

	protected:			protected:
	Collection m_entries;			using typename RangeVectorBase<E, S>::Collection;
				using RangeVectorBase<E, S>::VerifySorted;
				using RangeVectorBase<E, S>::m_entries;
	};			};

	//----------------------------------------------------------------------			// Use public inheritance to define these types instead of alias templates because MSVC 2013
	// A simple range with data class where you get to define the type of			// generates incorrect code for alias templates.
	// 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			template <typename B, typename S> class RangeVector : public RangeVectorBase<Range<B, S>, std::vector<Range<B, S>>>
	operator != (const AddressData &rhs) const
	{			{
	return this->addr != rhs.addr \|\|
	this->data == rhs.data;
	}
	};			};

	template <typename B, typename T, unsigned N>			template <typename B, typename S, size_t N>
	class AddressDataArray			class RangeArray : public RangeVectorBase<Range<B, S>, llvm::SmallVector<Range<B, S>, N>>
	{
	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 *			template <typename B, typename S, typename T>
	Back()			class RangeDataVector : public RangeDataVectorBase<RangeData<B, S, T>, std::vector<RangeData<B, S, T>>>
	{			{
	return (m_entries.empty() ? nullptr : &m_entries.back());			};
	}

	const Entry *			template <typename B, typename S, typename T, size_t N>
	Back() const			class RangeDataArray : public RangeDataVectorBase<RangeData<B, S, T>, llvm::SmallVector<RangeData<B, S, T>, N>>
	{			{
	return (m_entries.empty() ? nullptr : &m_entries.back());
	}

	protected:
	Collection m_entries;
	};			};

	} // namespace lldb_private			} // namespace lldb_private

	#endif // liblldb_RangeMap_h_			#endif // liblldb_RangeMap_h_

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

This file is larger than 256 KB, so syntax highlighting is disabled by default.

	Show First 20 Lines • Show All 101 Lines • ▼ Show 20 Lines
	};			};
	struct lldb_copy_dyld_cache_local_symbols_entry			struct lldb_copy_dyld_cache_local_symbols_entry
	{			{
	uint32_t dylibOffset;			uint32_t dylibOffset;
	uint32_t nlistStartIndex;			uint32_t nlistStartIndex;
	uint32_t nlistCount;			uint32_t nlistCount;
	};			};

				//----------------------------------------------------------------------
				// A simple range with data class where you get to define the type of
				// the range base "B", the type used for the range byte size "S", and
				// the type for the associated data "T".
				//----------------------------------------------------------------------
				template <typename B, typename T>
				struct AddressData
				{
				typedef B BaseType;
				typedef T DataType;

				BaseType addr;
				DataType data;

				AddressData () :
				addr (),
				data ()
				{
				}

				AddressData (B a, DataType d) :
				addr (a),
				data (d)
				{
				}

				bool
				operator < (const AddressData &rhs) const
				{
				if (this->addr == rhs.addr)
				return this->data < rhs.data;
				return this->addr < rhs.addr;
				}

				bool
				operator == (const AddressData &rhs) const
				{
				return this->addr == rhs.addr &&
				this->data == rhs.data;
				}

				bool
				operator != (const AddressData &rhs) const
				{
				return this->addr != rhs.addr \|\|
				this->data == rhs.data;
				}
				};

				template <typename B, typename T, unsigned N>
				class AddressDataArray
				{
				public:
				typedef AddressData<B,T> Entry;
				typedef llvm::SmallVector<Entry, N> Collection;

				AddressDataArray() = default;

				~AddressDataArray() = default;

				void
				Append (const Entry &entry)
				{
				m_entries.push_back (entry);
				}

				void
				Sort ()
				{
				if (m_entries.size() > 1)
				std::stable_sort (m_entries.begin(), m_entries.end());
				}

				#ifdef ASSERT_RANGEMAP_ARE_SORTED
				bool
				IsSorted () const
				{
				typename Collection::const_iterator pos, end, prev;
				// First we determine if we can combine any of the Entry objects so we
				// don't end up allocating and making a new collection for no reason
				for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
				{
				if (prev != end && pos < prev)
				return false;
				}
				return true;
				}
				#endif

				void
				Clear ()
				{
				m_entries.clear();
				}

				bool
				IsEmpty () const
				{
				return m_entries.empty();
				}

				size_t
				GetSize () const
				{
				return m_entries.size();
				}

				const Entry *
				GetEntryAtIndex (size_t i) const
				{
				return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
				}

				// Clients must ensure that "i" is a valid index prior to calling this function
				const Entry &
				GetEntryRef (size_t i) const
				{
				return m_entries[i];
				}

				static bool
				BaseLessThan (const Entry& lhs, const Entry& rhs)
				{
				return lhs.addr < rhs.addr;
				}

				Entry *
				FindEntry (B addr, bool exact_match_only)
				{
				#ifdef ASSERT_RANGEMAP_ARE_SORTED
				assert (IsSorted());
				#endif
				if ( !m_entries.empty() )
				{
				Entry entry;
				entry.addr = addr;
				typename Collection::iterator begin = m_entries.begin();
				typename Collection::iterator end = m_entries.end();
				typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);

				while(pos != begin && pos[-1].addr == addr)
				--pos;

				if (pos != end)
				{
				if (pos->addr == addr \|\| !exact_match_only)
				return &(*pos);
				}
				}
				return nullptr;
				}

				const Entry *
				FindNextEntry (const Entry *entry)
				{
				if (entry >= &m_entries.begin() && entry + 1 < &m_entries.end())
				return entry + 1;
				return nullptr;
				}

				Entry *
				Back()
				{
				return (m_entries.empty() ? nullptr : &m_entries.back());
				}

				const Entry *
				Back() const
				{
				return (m_entries.empty() ? nullptr : &m_entries.back());
				}

				protected:
				Collection m_entries;
				};

	class RegisterContextDarwin_x86_64_Mach : public RegisterContextDarwin_x86_64			class RegisterContextDarwin_x86_64_Mach : public RegisterContextDarwin_x86_64
	{			{
	public:			public:
	RegisterContextDarwin_x86_64_Mach (lldb_private::Thread &thread, const DataExtractor &data) :			RegisterContextDarwin_x86_64_Mach (lldb_private::Thread &thread, const DataExtractor &data) :
	RegisterContextDarwin_x86_64 (thread, 0)			RegisterContextDarwin_x86_64 (thread, 0)
	{			{
	SetRegisterDataFrom_LC_THREAD (data);			SetRegisterDataFrom_LC_THREAD (data);
	▲ Show 20 Lines • Show All 5,993 Lines • Show Last 20 Lines