16#ifndef LLVM_ADT_INTERVALTREE_H
17#define LLVM_ADT_INTERVALTREE_H
245 std::is_pointer<T>::value>;
247template <
typename PointT,
typename ValueT,
251 "PointT must be a fundamental type");
253 "ValueT must be a fundamental or pointer type");
270 IntervalNode *
Left =
nullptr;
271 IntervalNode *
Right =
nullptr;
272 unsigned BucketIntervalsStart = 0;
273 unsigned BucketIntervalsSize = 0;
276 PointType middle()
const {
return MiddlePoint; }
277 unsigned start()
const {
return BucketIntervalsStart; }
278 unsigned size()
const {
return BucketIntervalsSize; }
280 IntervalNode(
PointType Point,
unsigned Start)
281 : MiddlePoint(Point), BucketIntervalsStart(Start) {}
287 IntervalNode *Root =
nullptr;
288 IntervalVector Intervals;
290 PointsVector EndPoints;
308 void deleteTree(IntervalNode *
Node) {
310 deleteTree(
Node->Left);
311 deleteTree(
Node->Right);
312 Node->~IntervalNode();
313 NodeAllocator.Deallocate(
Node);
319 unsigned Start,
unsigned Size,
bool HexFormat =
true) {
321 "Start + Size must be in bounds of the IntervalSet");
322 const char *
Format = HexFormat ?
"[0x%08x,0x%08x] " :
"[%2d,%2d] ";
324 for (
unsigned Position = Start; Position < Start +
Size; ++Position)
326 IntervalSet[Position]->right());
334 void printNode(raw_ostream &
OS,
unsigned Level, IntervalNode *
Node,
335 bool HexFormat =
true) {
336 const char *
Format = HexFormat ?
"MP:0x%08x " :
"MP:%2d ";
339 OS.indent(Level * 2);
341 printList(
OS, IntervalSet,
Node->start(),
Node->size(), HexFormat);
344 PrintNodeData(
"IR", IntervalsRight);
345 PrintNodeData(
"IL", IntervalsLeft);
349 void printTree(raw_ostream &
OS,
unsigned Level, IntervalNode *
Node,
350 bool HexFormat =
true) {
352 printNode(
OS, Level,
Node, HexFormat);
354 printTree(
OS, Level,
Node->Left, HexFormat);
355 printTree(
OS, Level,
Node->Right, HexFormat);
366 IntervalNode *createTree(
unsigned &IntervalsSize,
int PointsBeginIndex,
367 int PointsEndIndex,
int ReferencesBeginIndex,
368 int ReferencesSize) {
379 if (PointsBeginIndex > PointsEndIndex ||
380 ReferencesBeginIndex >= ReferencesSize)
383 int MiddleIndex = (PointsBeginIndex + PointsEndIndex) / 2;
384 PointType MiddlePoint = EndPoints[MiddleIndex];
386 unsigned NewBucketStart = IntervalsSize;
387 unsigned NewBucketSize = 0;
388 int ReferencesRightIndex = ReferencesSize;
391 new (NodeAllocator) IntervalNode(MiddlePoint, NewBucketStart);
396 for (
int Index = ReferencesBeginIndex;
Index < ReferencesRightIndex;) {
400 IntervalsLeft[IntervalsSize] = References[
Index];
401 IntervalsRight[IntervalsSize] = References[
Index];
403 Root->BucketIntervalsSize = ++NewBucketSize;
405 if (
Index < --ReferencesRightIndex)
407 if (ReferencesRightIndex < --ReferencesSize)
408 std::swap(References[ReferencesRightIndex],
409 References[ReferencesSize]);
413 if (References[
Index]->left() > MiddlePoint) {
414 if (
Index < --ReferencesRightIndex)
422 if (NewBucketSize > 1) {
424 std::stable_sort(IntervalsLeft.begin() + NewBucketStart,
425 IntervalsLeft.begin() + NewBucketStart + NewBucketSize,
427 return LHS->left() < RHS->left();
430 std::stable_sort(IntervalsRight.begin() + NewBucketStart,
431 IntervalsRight.begin() + NewBucketStart + NewBucketSize,
433 return LHS->right() > RHS->right();
437 if (PointsBeginIndex <= MiddleIndex - 1) {
438 Root->Left = createTree(IntervalsSize, PointsBeginIndex, MiddleIndex - 1,
439 ReferencesBeginIndex, ReferencesRightIndex);
442 if (MiddleIndex + 1 <= PointsEndIndex) {
443 Root->Right = createTree(IntervalsSize, MiddleIndex + 1, PointsEndIndex,
444 ReferencesRightIndex, ReferencesSize);
465 IntervalNode *
Node =
nullptr;
477 if (Point ==
Node->middle()) {
478 if (
Node->size() == 0) {
485 if (Point < Node->middle()) {
489 if (
Node->size() && (*AscendingBuckets)[
Node->start()]->left(Point)) {
495 (*DescendingBuckets)[
Node->start()]->right(Point)) {
507 void nextInterval() {
511 if (++Index < Node->
size()) {
512 if (
Node->middle() == Point)
514 if (Point < Node->middle()) {
516 if (!(*AscendingBuckets)[
Node->start() + Index]->left(Point)) {
524 if (!(*DescendingBuckets)[
Node->start() + Index]->right(Point)) {
533 if (Point ==
Node->middle()) {
544 find_iterator() =
default;
549 Point(Point),
Index(0) {
554 return (Point <= Node->middle())
555 ? (*AscendingBuckets)[
Node->start() +
Index]
556 : (*DescendingBuckets)[
Node->start() +
Index];
577 return (!
LHS.Node && !
RHS.Node && !
LHS.Index && !
RHS.Index) ||
593 : NodeAllocator(NodeAllocator) {}
597 bool empty()
const {
return Root ==
nullptr; }
604 IntervalsLeft.clear();
605 IntervalsRight.clear();
611 assert(
empty() &&
"Invalid insertion. Interval tree already constructed.");
618 assert(!
empty() &&
"Interval tree it is not constructed.");
629 std::stable_sort(IntervalSet.
begin(), IntervalSet.
end(),
631 return Sort == Sorting::Ascending
632 ? (LHS->right() - LHS->left()) >
633 (RHS->right() - RHS->left())
634 : (LHS->right() - LHS->left()) <
635 (RHS->right() - RHS->left());
643 printTree(
OS, 0, Root, HexFormat);
648 assert(
empty() &&
"Interval tree already constructed.");
655 References.push_back(std::addressof(
Data));
657 std::stable_sort(Points.
begin(), Points.
end());
661 EndPoints.assign(Points.
begin(), Points.
end());
663 IntervalsLeft.resize(Intervals.size());
664 IntervalsRight.resize(Intervals.size());
669 unsigned IntervalsSize = 0;
671 createTree(IntervalsSize, 0, EndPoints.size() - 1,
672 0, References.size());
684 :
find_iterator(&IntervalsLeft, &IntervalsRight, Root, Point);
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallSet class.
This file defines the SmallVector class.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Allocate memory in an ever growing pool, as if by bump-pointer.
An interval data composed by a Left and Right points and an associated Value.
bool right(const PointType &Point) const
Return true if Point is inside the right bound of closed interval [Left;Right].
virtual ~IntervalData()=default
IntervalData(PointType Left, PointType Right, ValueType Value)
bool left(const PointType &Point) const
Return true if Point is inside the left bound of closed interval [Left;Right].
bool contains(const PointType &Point) const
Return true when Point is contained in interval [Left;Right].
find_iterator operator++(int)
std::forward_iterator_tag iterator_category
friend bool operator!=(const find_iterator &LHS, const find_iterator &RHS)
friend bool operator==(const find_iterator &LHS, const find_iterator &RHS)
Comparison operators.
find_iterator & operator++()
const DataType * operator->() const
Dereference operators.
const DataType & operator*() const
SmallVector< const DataType *, 4 > IntervalReferences
BumpPtrAllocator Allocator
void clear()
Remove all entries.
bool empty() const
Return true when no intervals are mapped.
void print(raw_ostream &OS, bool HexFormat=true)
Print the interval tree.
void insert(PointType Left, PointType Right, ValueType Value)
Add a mapping of [Left;Right] to Value.
IntervalTree(Allocator &NodeAllocator)
find_iterator find_end() const
Iterator to end find operation.
static void sortIntervals(IntervalReferences &IntervalSet, Sorting Sort)
Sort the given intervals using the following sort options: Ascending: return the intervals with the s...
void create()
Create the interval tree.
find_iterator find(PointType Point) const
Iterator to start a find operation; it returns find_end() if the tree has not been built.
IntervalReferences getContaining(PointType Point) const
Return all the intervals in their natural tree location, that contain the given point.
iterator erase(const_iterator CI)
void push_back(const T &Elt)
LLVM Value Representation.
This class implements an extremely fast bulk output stream that can only output to a stream.
This is an optimization pass for GlobalISel generic memory operations.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
std::bool_constant< std::is_fundamental< T >::value||std::is_pointer< T >::value > ValueTypeIsValid
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
std::bool_constant< std::is_fundamental< T >::value > PointTypeIsValid
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.