LLVM 18.0.0git
IntervalTree.h
Go to the documentation of this file.
1//===-- IntervalTree.h ------------------------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements an interval tree.
10//
11// Further information:
12// https://en.wikipedia.org/wiki/Interval_tree
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_ADT_INTERVALTREE_H
17#define LLVM_ADT_INTERVALTREE_H
18
19#include "llvm/ADT/SmallSet.h"
22#include "llvm/Support/Format.h"
24#include <algorithm>
25#include <cassert>
26#include <iterator>
27
28// IntervalTree is a light tree data structure to hold intervals. It allows
29// finding all intervals that overlap with any given point. At this time,
30// it does not support any deletion or rebalancing operations.
31//
32// The IntervalTree is designed to be set up once, and then queried without
33// any further additions.
34//
35// Synopsis:
36// Closed intervals delimited by PointT objects are mapped to ValueT objects.
37//
38// Restrictions:
39// PointT must be a fundamental type.
40// ValueT must be a fundamental or pointer type.
41//
42// template <typename PointT, typename ValueT, typename DataT>
43// class IntervalTree {
44// public:
45//
46// IntervalTree();
47// ~IntervalTree():
48//
49// using IntervalReferences = SmallVector<IntervalData *>;
50//
51// void create();
52// void insert(PointT Left, PointT Right, ValueT Value);
53//
54// IntervalReferences getContaining(PointT Point);
55// static void sortIntervals(IntervalReferences &Intervals, Sorting Sort);
56//
57// find_iterator begin(PointType Point) const;
58// find_iterator end() const;
59//
60// bool empty() const;
61// void clear();
62//
63// void print(raw_ostream &OS, bool HexFormat = true);
64// };
65//
66//===----------------------------------------------------------------------===//
67//
68// In the below given dataset
69//
70// [a, b] <- (x)
71//
72// 'a' and 'b' describe a range and 'x' the value for that interval.
73//
74// The following data are purely for illustrative purposes:
75//
76// [30, 35] <- (3035), [39, 50] <- (3950), [55, 61] <- (5561),
77// [31, 56] <- (3156), [12, 21] <- (1221), [25, 41] <- (2541),
78// [49, 65] <- (4965), [71, 79] <- (7179), [11, 16] <- (1116),
79// [20, 30] <- (2030), [36, 54] <- (3654), [60, 70] <- (6070),
80// [74, 80] <- (7480), [15, 40] <- (1540), [43, 43] <- (4343),
81// [50, 75] <- (5075), [10, 85] <- (1085)
82//
83// The data represents a set of overlapping intervals:
84//
85// 30--35 39------------50 55----61
86// 31------------------------56
87// 12--------21 25------------41 49-------------65 71-----79
88// 11----16 20-----30 36----------------54 60------70 74---- 80
89// 15---------------------40 43--43 50--------------------75
90// 10----------------------------------------------------------------------85
91//
92// The items are stored in a binary tree with each node storing:
93//
94// MP: A middle point.
95// IL: All intervals whose left value are completely to the left of the middle
96// point. They are sorted in ascending order by their beginning point.
97// IR: All intervals whose right value are completely to the right of the
98// middle point. They are sorted in descending order by their ending point.
99// LS: Left subtree.
100// RS: Right subtree.
101//
102// As IL and IR will contain the same intervals, in order to optimize space,
103// instead of storing intervals on each node, we use two vectors that will
104// contain the intervals described by IL and IR. Each node will contain an
105// index into that vector (global bucket), to indicate the beginning of the
106// intervals assigned to the node.
107//
108// The following is the output from print():
109//
110// 0: MP:43 IR [10,85] [31,56] [36,54] [39,50] [43,43]
111// 0: MP:43 IL [10,85] [31,56] [36,54] [39,50] [43,43]
112// 1: MP:25 IR [25,41] [15,40] [20,30]
113// 1: MP:25 IL [15,40] [20,30] [25,41]
114// 2: MP:15 IR [12,21] [11,16]
115// 2: MP:15 IL [11,16] [12,21]
116// 2: MP:36 IR []
117// 2: MP:36 IL []
118// 3: MP:31 IR [30,35]
119// 3: MP:31 IL [30,35]
120// 1: MP:61 IR [50,75] [60,70] [49,65] [55,61]
121// 1: MP:61 IL [49,65] [50,75] [55,61] [60,70]
122// 2: MP:74 IR [74,80] [71,79]
123// 2: MP:74 IL [71,79] [74,80]
124//
125// with:
126// 0: Root Node.
127// MP: Middle point.
128// IL: Intervals to the left (in ascending order by beginning point).
129// IR: Intervals to the right (in descending order by ending point).
130//
131// Root
132// |
133// V
134// +------------MP:43------------+
135// | IL IR |
136// | [10,85] [10,85] |
137// LS | [31,56] [31,56] | RS
138// | [36,54] [36,54] |
139// | [39,50] [39,50] |
140// | [43,43] [43,43] |
141// V V
142// +------------MP:25------------+ MP:61------------+
143// | IL IR | IL IR |
144// | [15,40] [25,41] | [49,65] [50,75] |
145// LS | [20,30] [15,40] | RS [50,75] [60,70] | RS
146// | [25,41] [20,30] | [55,61] [49,65] |
147// | | [60,70] [55,61] |
148// V V V
149// MP:15 +-------MP:36 MP:74
150// IL IR | IL IR IL IR
151// [11,16] [12,21] LS | [] [] [71,79] [74,80]
152// [12,21] [11,16] | [74,80] [71,79]
153// V
154// MP:31
155// IL IR
156// [30,35] [30,35]
157//
158// The creation of an interval tree is done in 2 steps:
159// 1) Insert the interval items by calling
160// void insert(PointT Left, PointT Right, ValueT Value);
161// Left, Right: the interval left and right limits.
162// Value: the data associated with that specific interval.
163//
164// 2) Create the interval tree by calling
165// void create();
166//
167// Once the tree is created, it is switched to query mode.
168// Query the tree by using iterators or container.
169//
170// a) Iterators over intervals overlapping the given point with very weak
171// ordering guarantees.
172// find_iterator begin(PointType Point) const;
173// find_iterator end() const;
174// Point: a target point to be tested for inclusion in any interval.
175//
176// b) Container:
177// IntervalReferences getContaining(PointT Point);
178// Point: a target point to be tested for inclusion in any interval.
179// Returns vector with all the intervals containing the target point.
180//
181// The returned intervals are in their natural tree location. They can
182// be sorted:
183//
184// static void sortIntervals(IntervalReferences &Intervals, Sorting Sort);
185//
186// Ability to print the constructed interval tree:
187// void print(raw_ostream &OS, bool HexFormat = true);
188// Display the associated data in hexadecimal format.
189
190namespace llvm {
191
192//===----------------------------------------------------------------------===//
193//--- IntervalData ----//
194//===----------------------------------------------------------------------===//
195/// An interval data composed by a \a Left and \a Right points and an
196/// associated \a Value.
197/// \a PointT corresponds to the interval endpoints type.
198/// \a ValueT corresponds to the interval value type.
199template <typename PointT, typename ValueT> class IntervalData {
200protected:
201 using PointType = PointT;
203
204private:
205 PointType Left;
206 PointType Right;
208
209public:
210 IntervalData() = delete;
212 : Left(Left), Right(Right), Value(Value) {
213 assert(Left <= Right && "'Left' must be less or equal to 'Right'");
214 }
215 virtual ~IntervalData() = default;
216 PointType left() const { return Left; }
217 PointType right() const { return Right; }
218 ValueType value() const { return Value; }
219
220 /// Return true if \a Point is inside the left bound of closed interval \a
221 /// [Left;Right]. This is Left <= Point for closed intervals.
222 bool left(const PointType &Point) const { return left() <= Point; }
223
224 /// Return true if \a Point is inside the right bound of closed interval \a
225 /// [Left;Right]. This is Point <= Right for closed intervals.
226 bool right(const PointType &Point) const { return Point <= right(); }
227
228 /// Return true when \a Point is contained in interval \a [Left;Right].
229 /// This is Left <= Point <= Right for closed intervals.
230 bool contains(const PointType &Point) const {
231 return left(Point) && right(Point);
232 }
233};
234
235//===----------------------------------------------------------------------===//
236//--- IntervalTree ----//
237//===----------------------------------------------------------------------===//
238// Helper class template that is used by the IntervalTree to ensure that one
239// does instantiate using only fundamental and/or pointer types.
240template <typename T>
241using PointTypeIsValid = std::bool_constant<std::is_fundamental<T>::value>;
242
243template <typename T>
244using ValueTypeIsValid = std::bool_constant<std::is_fundamental<T>::value ||
245 std::is_pointer<T>::value>;
246
247template <typename PointT, typename ValueT,
248 typename DataT = IntervalData<PointT, ValueT>>
251 "PointT must be a fundamental type");
253 "ValueT must be a fundamental or pointer type");
254
255public:
256 using PointType = PointT;
258 using DataType = DataT;
260
261 enum class Sorting { Ascending, Descending };
263
264private:
267
268 class IntervalNode {
269 PointType MiddlePoint; // MP - Middle point.
270 IntervalNode *Left = nullptr; // LS - Left subtree.
271 IntervalNode *Right = nullptr; // RS - Right subtree.
272 unsigned BucketIntervalsStart = 0; // Starting index in global bucket.
273 unsigned BucketIntervalsSize = 0; // Size of bucket.
274
275 public:
276 PointType middle() const { return MiddlePoint; }
277 unsigned start() const { return BucketIntervalsStart; }
278 unsigned size() const { return BucketIntervalsSize; }
279
280 IntervalNode(PointType Point, unsigned Start)
281 : MiddlePoint(Point), BucketIntervalsStart(Start) {}
282
283 friend IntervalTree;
284 };
285
286 Allocator &NodeAllocator; // Allocator used for creating interval nodes.
287 IntervalNode *Root = nullptr; // Interval tree root.
288 IntervalVector Intervals; // Storage for each interval and all of the fields
289 // point back into it.
290 PointsVector EndPoints; // Sorted left and right points of all the intervals.
291
292 // These vectors provide storage that nodes carve buckets of overlapping
293 // intervals out of. All intervals are recorded on each vector.
294 // The bucket with the intervals associated to a node, is determined by
295 // the fields 'BucketIntervalStart' and 'BucketIntervalSize' in the node.
296 // The buckets in the first vector are sorted in ascending order using
297 // the left value and the buckets in the second vector are sorted in
298 // descending order using the right value. Every interval in a bucket
299 // contains the middle point for the node.
300 IntervalReferences IntervalsLeft; // Intervals to the left of middle point.
301 IntervalReferences IntervalsRight; // Intervals to the right of middle point.
302
303 // Working vector used during the tree creation to sort the intervals. It is
304 // cleared once the tree is created.
305 IntervalReferences References;
306
307 /// Recursively delete the constructed tree.
308 void deleteTree(IntervalNode *Node) {
309 if (Node) {
310 deleteTree(Node->Left);
311 deleteTree(Node->Right);
312 Node->~IntervalNode();
313 NodeAllocator.Deallocate(Node);
314 }
315 }
316
317 /// Print the interval list (left and right) for a given \a Node.
318 static void printList(raw_ostream &OS, IntervalReferences &IntervalSet,
319 unsigned Start, unsigned Size, bool HexFormat = true) {
320 assert(Start + Size <= IntervalSet.size() &&
321 "Start + Size must be in bounds of the IntervalSet");
322 const char *Format = HexFormat ? "[0x%08x,0x%08x] " : "[%2d,%2d] ";
323 if (Size) {
324 for (unsigned Position = Start; Position < Start + Size; ++Position)
325 OS << format(Format, IntervalSet[Position]->left(),
326 IntervalSet[Position]->right());
327 } else {
328 OS << "[]";
329 }
330 OS << "\n";
331 }
332
333 /// Print an interval tree \a Node.
334 void printNode(raw_ostream &OS, unsigned Level, IntervalNode *Node,
335 bool HexFormat = true) {
336 const char *Format = HexFormat ? "MP:0x%08x " : "MP:%2d ";
337 auto PrintNodeData = [&](StringRef Text, IntervalReferences &IntervalSet) {
338 OS << format("%5d: ", Level);
339 OS.indent(Level * 2);
340 OS << format(Format, Node->middle()) << Text << " ";
341 printList(OS, IntervalSet, Node->start(), Node->size(), HexFormat);
342 };
343
344 PrintNodeData("IR", IntervalsRight);
345 PrintNodeData("IL", IntervalsLeft);
346 }
347
348 /// Recursively print all the interval nodes.
349 void printTree(raw_ostream &OS, unsigned Level, IntervalNode *Node,
350 bool HexFormat = true) {
351 if (Node) {
352 printNode(OS, Level, Node, HexFormat);
353 ++Level;
354 printTree(OS, Level, Node->Left, HexFormat);
355 printTree(OS, Level, Node->Right, HexFormat);
356 }
357 }
358
359 /// Recursively construct the interval tree.
360 /// IntervalsSize: Number of intervals that have been processed and it will
361 /// be used as the start for the intervals bucket for a node.
362 /// PointsBeginIndex, PointsEndIndex: Determine the range into the EndPoints
363 /// vector of end points to be processed.
364 /// ReferencesBeginIndex, ReferencesSize: Determine the range into the
365 /// intervals being processed.
366 IntervalNode *createTree(unsigned &IntervalsSize, int PointsBeginIndex,
367 int PointsEndIndex, int ReferencesBeginIndex,
368 int ReferencesSize) {
369 // We start by taking the entire range of all the intervals and dividing
370 // it in half at x_middle (in practice, x_middle should be picked to keep
371 // the tree relatively balanced).
372 // This gives three sets of intervals, those completely to the left of
373 // x_middle which we'll call S_left, those completely to the right of
374 // x_middle which we'll call S_right, and those overlapping x_middle
375 // which we'll call S_middle.
376 // The intervals in S_left and S_right are recursively divided in the
377 // same manner until there are no intervals remaining.
378
379 if (PointsBeginIndex > PointsEndIndex ||
380 ReferencesBeginIndex >= ReferencesSize)
381 return nullptr;
382
383 int MiddleIndex = (PointsBeginIndex + PointsEndIndex) / 2;
384 PointType MiddlePoint = EndPoints[MiddleIndex];
385
386 unsigned NewBucketStart = IntervalsSize;
387 unsigned NewBucketSize = 0;
388 int ReferencesRightIndex = ReferencesSize;
389
390 IntervalNode *Root =
391 new (NodeAllocator) IntervalNode(MiddlePoint, NewBucketStart);
392
393 // A quicksort implementation where all the intervals that overlap
394 // with the pivot are put into the "bucket", and "References" is the
395 // partition space where we recursively sort the remaining intervals.
396 for (int Index = ReferencesBeginIndex; Index < ReferencesRightIndex;) {
397
398 // Current interval contains the middle point.
399 if (References[Index]->contains(MiddlePoint)) {
400 IntervalsLeft[IntervalsSize] = References[Index];
401 IntervalsRight[IntervalsSize] = References[Index];
402 ++IntervalsSize;
403 Root->BucketIntervalsSize = ++NewBucketSize;
404
405 if (Index < --ReferencesRightIndex)
406 std::swap(References[Index], References[ReferencesRightIndex]);
407 if (ReferencesRightIndex < --ReferencesSize)
408 std::swap(References[ReferencesRightIndex],
409 References[ReferencesSize]);
410 continue;
411 }
412
413 if (References[Index]->left() > MiddlePoint) {
414 if (Index < --ReferencesRightIndex)
415 std::swap(References[Index], References[ReferencesRightIndex]);
416 continue;
417 }
418 ++Index;
419 }
420
421 // Sort intervals on the left and right of the middle point.
422 if (NewBucketSize > 1) {
423 // Sort the intervals in ascending order by their beginning point.
424 std::stable_sort(IntervalsLeft.begin() + NewBucketStart,
425 IntervalsLeft.begin() + NewBucketStart + NewBucketSize,
426 [](const DataType *LHS, const DataType *RHS) {
427 return LHS->left() < RHS->left();
428 });
429 // Sort the intervals in descending order by their ending point.
430 std::stable_sort(IntervalsRight.begin() + NewBucketStart,
431 IntervalsRight.begin() + NewBucketStart + NewBucketSize,
432 [](const DataType *LHS, const DataType *RHS) {
433 return LHS->right() > RHS->right();
434 });
435 }
436
437 if (PointsBeginIndex <= MiddleIndex - 1) {
438 Root->Left = createTree(IntervalsSize, PointsBeginIndex, MiddleIndex - 1,
439 ReferencesBeginIndex, ReferencesRightIndex);
440 }
441
442 if (MiddleIndex + 1 <= PointsEndIndex) {
443 Root->Right = createTree(IntervalsSize, MiddleIndex + 1, PointsEndIndex,
444 ReferencesRightIndex, ReferencesSize);
445 }
446
447 return Root;
448 }
449
450public:
452 public:
453 using iterator_category = std::forward_iterator_tag;
456 using pointer = DataType *;
458
459 private:
460 const IntervalReferences *AscendingBuckets = nullptr;
461 const IntervalReferences *DescendingBuckets = nullptr;
462
463 // Current node and index while traversing the intervals that contain
464 // the reference point.
465 IntervalNode *Node = nullptr;
466 PointType Point = {};
467 unsigned Index = 0;
468
469 // For the current node, check if we have intervals that contain the
470 // reference point. We return when the node does have intervals that
471 // contain such point. Otherwise we keep descending on that branch.
472 void initNode() {
473 Index = 0;
474 while (Node) {
475 // Return if the reference point is the same as the middle point or
476 // the current node doesn't have any intervals at all.
477 if (Point == Node->middle()) {
478 if (Node->size() == 0) {
479 // No intervals that contain the reference point.
480 Node = nullptr;
481 }
482 return;
483 }
484
485 if (Point < Node->middle()) {
486 // The reference point can be at the left or right of the middle
487 // point. Return if the current node has intervals that contain the
488 // reference point; otherwise descend on the respective branch.
489 if (Node->size() && (*AscendingBuckets)[Node->start()]->left(Point)) {
490 return;
491 }
492 Node = Node->Left;
493 } else {
494 if (Node->size() &&
495 (*DescendingBuckets)[Node->start()]->right(Point)) {
496 return;
497 }
498 Node = Node->Right;
499 }
500 }
501 }
502
503 // Given the current node (which was initialized by initNode), move to
504 // the next interval in the list of intervals that contain the reference
505 // point. Otherwise move to the next node, as the intervals contained
506 // in that node, can contain the reference point.
507 void nextInterval() {
508 // If there are available intervals that contain the reference point,
509 // traverse them; otherwise move to the left or right node, depending
510 // on the middle point value.
511 if (++Index < Node->size()) {
512 if (Node->middle() == Point)
513 return;
514 if (Point < Node->middle()) {
515 // Reference point is on the left.
516 if (!(*AscendingBuckets)[Node->start() + Index]->left(Point)) {
517 // The intervals don't contain the reference point. Move to the
518 // next node, preserving the descending order.
519 Node = Node->Left;
520 initNode();
521 }
522 } else {
523 // Reference point is on the right.
524 if (!(*DescendingBuckets)[Node->start() + Index]->right(Point)) {
525 // The intervals don't contain the reference point. Move to the
526 // next node, preserving the ascending order.
527 Node = Node->Right;
528 initNode();
529 }
530 }
531 } else {
532 // We have traversed all the intervals in the current node.
533 if (Point == Node->middle()) {
534 Node = nullptr;
535 Index = 0;
536 return;
537 }
538 // Select a branch based on the middle point.
539 Node = Point < Node->middle() ? Node->Left : Node->Right;
540 initNode();
541 }
542 }
543
544 find_iterator() = default;
545 explicit find_iterator(const IntervalReferences *Left,
546 const IntervalReferences *Right, IntervalNode *Node,
547 PointType Point)
548 : AscendingBuckets(Left), DescendingBuckets(Right), Node(Node),
549 Point(Point), Index(0) {
550 initNode();
551 }
552
553 const DataType *current() const {
554 return (Point <= Node->middle())
555 ? (*AscendingBuckets)[Node->start() + Index]
556 : (*DescendingBuckets)[Node->start() + Index];
557 }
558
559 public:
561 nextInterval();
562 return *this;
563 }
564
566 find_iterator Iter(*this);
567 nextInterval();
568 return Iter;
569 }
570
571 /// Dereference operators.
572 const DataType *operator->() const { return current(); }
573 const DataType &operator*() const { return *(current()); }
574
575 /// Comparison operators.
576 friend bool operator==(const find_iterator &LHS, const find_iterator &RHS) {
577 return (!LHS.Node && !RHS.Node && !LHS.Index && !RHS.Index) ||
578 (LHS.Point == RHS.Point && LHS.Node == RHS.Node &&
579 LHS.Index == RHS.Index);
580 }
581 friend bool operator!=(const find_iterator &LHS, const find_iterator &RHS) {
582 return !(LHS == RHS);
583 }
584
586 };
587
588private:
589 find_iterator End;
590
591public:
592 explicit IntervalTree(Allocator &NodeAllocator)
593 : NodeAllocator(NodeAllocator) {}
595
596 /// Return true when no intervals are mapped.
597 bool empty() const { return Root == nullptr; }
598
599 /// Remove all entries.
600 void clear() {
601 deleteTree(Root);
602 Root = nullptr;
603 Intervals.clear();
604 IntervalsLeft.clear();
605 IntervalsRight.clear();
606 EndPoints.clear();
607 }
608
609 /// Add a mapping of [Left;Right] to \a Value.
611 assert(empty() && "Invalid insertion. Interval tree already constructed.");
612 Intervals.emplace_back(Left, Right, Value);
613 }
614
615 /// Return all the intervals in their natural tree location, that
616 /// contain the given point.
618 assert(!empty() && "Interval tree it is not constructed.");
619 IntervalReferences IntervalSet;
620 for (find_iterator Iter = find(Point), E = find_end(); Iter != E; ++Iter)
621 IntervalSet.push_back(const_cast<DataType *>(&(*Iter)));
622 return IntervalSet;
623 }
624
625 /// Sort the given intervals using the following sort options:
626 /// Ascending: return the intervals with the smallest at the front.
627 /// Descending: return the intervals with the biggest at the front.
628 static void sortIntervals(IntervalReferences &IntervalSet, Sorting Sort) {
629 std::stable_sort(IntervalSet.begin(), IntervalSet.end(),
630 [Sort](const DataType *RHS, const DataType *LHS) {
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());
636 });
637 }
638
639 /// Print the interval tree.
640 /// When \a HexFormat is true, the interval tree interval ranges and
641 /// associated values are printed in hexadecimal format.
642 void print(raw_ostream &OS, bool HexFormat = true) {
643 printTree(OS, 0, Root, HexFormat);
644 }
645
646 /// Create the interval tree.
647 void create() {
648 assert(empty() && "Interval tree already constructed.");
649 // Sorted vector of unique end points values of all the intervals.
650 // Records references to the collected intervals.
652 for (const DataType &Data : Intervals) {
653 Points.push_back(Data.left());
654 Points.push_back(Data.right());
655 References.push_back(std::addressof(Data));
656 }
657 std::stable_sort(Points.begin(), Points.end());
658 auto Last = std::unique(Points.begin(), Points.end());
659 Points.erase(Last, Points.end());
660
661 EndPoints.assign(Points.begin(), Points.end());
662
663 IntervalsLeft.resize(Intervals.size());
664 IntervalsRight.resize(Intervals.size());
665
666 // Given a set of n intervals, construct a data structure so that
667 // we can efficiently retrieve all intervals overlapping another
668 // interval or point.
669 unsigned IntervalsSize = 0;
670 Root =
671 createTree(IntervalsSize, /*PointsBeginIndex=*/0, EndPoints.size() - 1,
672 /*ReferencesBeginIndex=*/0, References.size());
673
674 // Save to clear this storage, as it used only to sort the intervals.
675 References.clear();
676 }
677
678 /// Iterator to start a find operation; it returns find_end() if the
679 /// tree has not been built.
680 /// There is no support to iterate over all the elements of the tree.
682 return empty()
683 ? find_end()
684 : find_iterator(&IntervalsLeft, &IntervalsRight, Root, Point);
685 }
686
687 /// Iterator to end find operation.
688 find_iterator find_end() const { return End; }
689};
690
691} // namespace llvm
692
693#endif // LLVM_ADT_INTERVALTREE_H
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
uint64_t Size
bool End
Definition: ELF_riscv.cpp:469
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the SmallSet class.
This file defines the SmallVector class.
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Definition: Value.cpp:470
Value * RHS
Value * LHS
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
An interval data composed by a Left and Right points and an associated Value.
Definition: IntervalTree.h:199
bool right(const PointType &Point) const
Return true if Point is inside the right bound of closed interval [Left;Right].
Definition: IntervalTree.h:226
virtual ~IntervalData()=default
IntervalData(PointType Left, PointType Right, ValueType Value)
Definition: IntervalTree.h:211
bool left(const PointType &Point) const
Return true if Point is inside the left bound of closed interval [Left;Right].
Definition: IntervalTree.h:222
PointType right() const
Definition: IntervalTree.h:217
bool contains(const PointType &Point) const
Return true when Point is contained in interval [Left;Right].
Definition: IntervalTree.h:230
ValueType value() const
Definition: IntervalTree.h:218
PointType left() const
Definition: IntervalTree.h:216
std::forward_iterator_tag iterator_category
Definition: IntervalTree.h:453
friend bool operator!=(const find_iterator &LHS, const find_iterator &RHS)
Definition: IntervalTree.h:581
friend bool operator==(const find_iterator &LHS, const find_iterator &RHS)
Comparison operators.
Definition: IntervalTree.h:576
const DataType * operator->() const
Dereference operators.
Definition: IntervalTree.h:572
const DataType & operator*() const
Definition: IntervalTree.h:573
SmallVector< const DataType *, 4 > IntervalReferences
Definition: IntervalTree.h:262
BumpPtrAllocator Allocator
Definition: IntervalTree.h:259
void clear()
Remove all entries.
Definition: IntervalTree.h:600
bool empty() const
Return true when no intervals are mapped.
Definition: IntervalTree.h:597
void print(raw_ostream &OS, bool HexFormat=true)
Print the interval tree.
Definition: IntervalTree.h:642
void insert(PointType Left, PointType Right, ValueType Value)
Add a mapping of [Left;Right] to Value.
Definition: IntervalTree.h:610
IntervalTree(Allocator &NodeAllocator)
Definition: IntervalTree.h:592
find_iterator find_end() const
Iterator to end find operation.
Definition: IntervalTree.h:688
static void sortIntervals(IntervalReferences &IntervalSet, Sorting Sort)
Sort the given intervals using the following sort options: Ascending: return the intervals with the s...
Definition: IntervalTree.h:628
void create()
Create the interval tree.
Definition: IntervalTree.h:647
find_iterator find(PointType Point) const
Iterator to start a find operation; it returns find_end() if the tree has not been built.
Definition: IntervalTree.h:681
IntervalReferences getContaining(PointType Point) const
Return all the intervals in their natural tree location, that contain the given point.
Definition: IntervalTree.h:617
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
void push_back(const T &Elt)
Definition: SmallVector.h:416
LLVM Value Representation.
Definition: Value.h:74
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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.
Definition: STLExtras.h:1685
std::bool_constant< std::is_fundamental< T >::value||std::is_pointer< T >::value > ValueTypeIsValid
Definition: IntervalTree.h:245
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition: Allocator.h:375
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:125
std::bool_constant< std::is_fundamental< T >::value > PointTypeIsValid
Definition: IntervalTree.h:241
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860