99 #ifndef LLVM_ADT_INTERVALMAP_H 100 #define LLVM_ADT_INTERVALMAP_H 137 template <
typename T>
164 template <
typename T>
189 namespace IntervalMapImpl {
220 template <
typename T1,
typename T2,
unsigned N>
223 enum { Capacity =
N };
233 template <
unsigned M>
235 unsigned j,
unsigned Count) {
236 assert(i + Count <= M &&
"Invalid source range");
237 assert(j + Count <=
N &&
"Invalid dest range");
238 for (
unsigned e = i + Count; i != e; ++i, ++j) {
239 first[j] = Other.
first[i];
240 second[j] = Other.
second[i];
248 void moveLeft(
unsigned i,
unsigned j,
unsigned Count) {
249 assert(j <= i &&
"Use moveRight shift elements right");
250 copy(*
this, i, j, Count);
257 void moveRight(
unsigned i,
unsigned j,
unsigned Count) {
258 assert(i <= j &&
"Use moveLeft shift elements left");
259 assert(j + Count <=
N &&
"Invalid range");
261 first[j + Count] = first[i + Count];
262 second[j + Count] = second[i + Count];
271 moveLeft(j, i, Size - j);
285 moveRight(i, i + 1, Size - i);
295 Sib.
copy(*
this, 0, SSize, Count);
296 erase(0, Count, Size);
307 Sib.
copy(*
this, Size-Count, 0, Count);
320 unsigned Count = std::min(std::min(
unsigned(Add), SSize),
N - Size);
325 unsigned Count = std::min(std::min(
unsigned(-Add), Size),
N - SSize);
326 transferToLeftSib(Size, Sib, SSize, Count);
337 template <
typename NodeT>
339 unsigned CurSize[],
const unsigned NewSize[]) {
341 for (
int n = Nodes - 1; n; --n) {
342 if (CurSize[n] == NewSize[n])
344 for (
int m = n - 1; m != -1; --m) {
345 int d = Node[n]->adjustFromLeftSib(CurSize[n], *Node[m], CurSize[m],
346 NewSize[n] - CurSize[n]);
350 if (CurSize[n] >= NewSize[n])
359 for (
unsigned n = 0; n != Nodes - 1; ++n) {
360 if (CurSize[n] == NewSize[n])
362 for (
unsigned m = n + 1; m != Nodes; ++m) {
363 int d = Node[m]->adjustFromLeftSib(CurSize[m], *Node[n], CurSize[n],
364 CurSize[n] - NewSize[n]);
368 if (CurSize[n] >= NewSize[n])
374 for (
unsigned n = 0; n != Nodes; n++)
375 assert(CurSize[n] == NewSize[n] &&
"Insufficient element shuffle");
413 const unsigned *CurSize,
unsigned NewSize[],
436 template <
typename KeyT,
typename ValT>
445 static_cast<unsigned>(2*
sizeof(KeyT)+
sizeof(
ValT)),
447 LeafSize = DesiredLeafSize > MinLeafSize ? DesiredLeafSize : MinLeafSize
458 BranchSize = AllocBytes /
459 static_cast<unsigned>(
sizeof(KeyT) +
sizeof(
void*))
492 struct CacheAlignedPointerTraits {
493 static inline void *getAsVoidPointer(
void *
P) {
return P; }
494 static inline void *getFromVoidPointer(
void *P) {
return P; }
507 template <
typename NodeT>
508 NodeRef(NodeT *p,
unsigned n) : pip(p, n - 1) {
509 assert(n <= NodeT::Capacity &&
"Size too big for node");
526 template <
typename NodeT>
528 return *
reinterpret_cast<NodeT*
>(pip.
getPointer());
563 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
566 const KeyT &
start(
unsigned i)
const {
return this->
first[i].first; }
567 const KeyT &
stop(
unsigned i)
const {
return this->
first[i].second; }
571 KeyT &
stop(
unsigned i) {
return this->
first[i].second; }
581 assert(i <= Size && Size <=
N &&
"Bad indices");
582 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
583 "Index is past the needed point");
584 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
597 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
598 "Index is past the needed point");
599 while (Traits::stopLess(stop(i), x)) ++i;
600 assert(i <
N &&
"Unsafe intervals");
610 unsigned i = safeFind(0, x);
611 return Traits::startLess(x, start(i)) ?
NotFound : value(i);
614 unsigned insertFrom(
unsigned &Pos,
unsigned Size, KeyT a, KeyT b, ValT y);
626 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
630 assert(i <= Size && Size <=
N &&
"Invalid index");
631 assert(!Traits::stopLess(b, a) &&
"Invalid interval");
634 assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
635 assert((i == Size || !Traits::stopLess(stop(i), a)));
636 assert((i == Size || Traits::stopLess(b, start(i))) &&
"Overlapping insert");
639 if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
642 if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
643 stop(i - 1) = stop(i);
644 this->erase(i, Size);
664 if (value(i) == y && Traits::adjacent(b, start(i))) {
674 this->shift(i, Size);
700 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
703 const KeyT &
stop(
unsigned i)
const {
return this->
second[i]; }
716 assert(i <= Size && Size <=
N &&
"Bad indices");
717 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
718 "Index to findFrom is past the needed point");
719 while (i != Size && Traits::stopLess(stop(i), x)) ++i;
731 assert((i == 0 || Traits::stopLess(stop(i - 1), x)) &&
732 "Index is past the needed point");
733 while (Traits::stopLess(stop(i), x)) ++i;
734 assert(i <
N &&
"Unsafe intervals");
742 return subtree(safeFind(0, x));
751 assert(Size <
N &&
"branch node overflow");
752 assert(i <= Size &&
"Bad insert position");
753 this->shift(i, Size);
779 Entry(
void *Node,
unsigned Size,
unsigned Offset)
780 : node(Node),
size(Size), offset(Offset) {}
782 Entry(
NodeRef Node,
unsigned Offset)
785 NodeRef &subtree(
unsigned i)
const {
786 return reinterpret_cast<NodeRef*
>(node)[i];
795 template <
typename NodeT> NodeT &
node(
unsigned Level)
const {
796 return *
reinterpret_cast<NodeT*
>(path[
Level].node);
803 template <
typename NodeT> NodeT &
leaf()
const {
804 return *
reinterpret_cast<NodeT*
>(path.
back().node);
823 return path[
Level].subtree(path[Level].offset);
829 path[
Level] = Entry(subtree(Level - 1), offset(Level));
851 subtree(Level - 1).setSize(Size);
860 path.
push_back(Entry(Node, Size, Offset));
878 void moveLeft(
unsigned Level);
883 while (height() < Height)
884 push(subtree(height()), 0);
890 NodeRef getRightSibling(
unsigned Level)
const;
895 void moveRight(
unsigned Level);
899 for (
unsigned i = 0, e = path.
size(); i != e; ++i)
900 if (path[i].offset != 0)
921 ++path[
Level].offset;
931 template <
typename KeyT,
typename ValT,
945 DesiredRootBranchCap = (
sizeof(
RootLeaf) -
sizeof(KeyT)) /
947 RootBranchCap = DesiredRootBranchCap ? DesiredRootBranchCap : 1
954 struct RootBranchData {
983 template <
typename T>
989 assert(!branched() &&
"Cannot acces leaf data in branched root");
990 return dataAs<RootLeaf>();
993 assert(!branched() &&
"Cannot acces leaf data in branched root");
994 return dataAs<RootLeaf>();
997 RootBranchData &rootBranchData()
const {
998 assert(branched() &&
"Cannot access branch data in non-branched root");
999 return dataAs<RootBranchData>();
1001 RootBranchData &rootBranchData() {
1002 assert(branched() &&
"Cannot access branch data in non-branched root");
1003 return dataAs<RootBranchData>();
1006 const RootBranch &rootBranch()
const {
return rootBranchData().node; }
1007 RootBranch &rootBranch() {
return rootBranchData().node; }
1008 KeyT rootBranchStart()
const {
return rootBranchData().start; }
1009 KeyT &rootBranchStart() {
return rootBranchData().start; }
1011 template <
typename NodeT> NodeT *newNode() {
1012 return new(allocator.template Allocate<NodeT>()) NodeT();
1015 template <
typename NodeT>
void deleteNode(NodeT *
P) {
1017 allocator.Deallocate(P);
1020 IdxPair branchRoot(
unsigned Position);
1021 IdxPair splitRoot(
unsigned Position);
1023 void switchRootToBranch() {
1024 rootLeaf().~RootLeaf();
1026 new (&rootBranchData()) RootBranchData();
1029 void switchRootToLeaf() {
1030 rootBranchData().~RootBranchData();
1035 bool branched()
const {
return height > 0; }
1037 ValT treeSafeLookup(KeyT x, ValT
NotFound)
const;
1045 "Insufficient alignment");
1051 rootLeaf().~RootLeaf();
1056 return rootSize == 0;
1061 assert(!
empty() &&
"Empty IntervalMap has no start");
1062 return !branched() ? rootLeaf().start(0) : rootBranchStart();
1067 assert(!
empty() &&
"Empty IntervalMap has no stop");
1068 return !branched() ? rootLeaf().stop(rootSize - 1) :
1069 rootBranch().stop(rootSize - 1);
1073 ValT
lookup(KeyT x, ValT NotFound = ValT())
const {
1074 if (
empty() || Traits::startLess(x, start()) || Traits::stopLess(stop(), x))
1076 return branched() ? treeSafeLookup(x, NotFound) :
1077 rootLeaf().safeLookup(x, NotFound);
1084 if (branched() || rootSize == RootLeaf::Capacity)
1085 return find(a).insert(a, b, y);
1088 unsigned p = rootLeaf().findFrom(0, rootSize, a);
1089 rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
1095 class const_iterator;
1097 friend class const_iterator;
1098 friend class iterator;
1101 const_iterator
I(*
this);
1113 const_iterator
I(*
this);
1126 const_iterator
find(KeyT x)
const {
1127 const_iterator
I(*
this);
1141 assert(Traits::nonEmpty(a, b));
1142 const_iterator
I =
find(a);
1148 return !Traits::stopLess(b, I.start());
1154 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1157 assert(branched() &&
"treeLookup assumes a branched root");
1160 for (
unsigned h = height-1; h; --h)
1162 return NR.
get<
Leaf>().safeLookup(x, NotFound);
1167 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1170 using namespace IntervalMapImpl;
1172 const unsigned Nodes = RootLeaf::Capacity / Leaf::Capacity + 1;
1175 unsigned size[Nodes];
1176 IdxPair NewOffset(0, Position);
1182 NewOffset =
distribute(Nodes, rootSize, Leaf::Capacity,
nullptr, size,
1187 NodeRef node[Nodes];
1188 for (
unsigned n = 0; n != Nodes; ++n) {
1189 Leaf *L = newNode<Leaf>();
1190 L->
copy(rootLeaf(), pos, 0, size[n]);
1191 node[n] = NodeRef(L, size[n]);
1196 switchRootToBranch();
1197 for (
unsigned n = 0; n != Nodes; ++n) {
1198 rootBranch().stop(n) = node[n].template get<Leaf>().stop(size[n]-1);
1199 rootBranch().subtree(n) = node[n];
1201 rootBranchStart() = node[0].template get<Leaf>().start(0);
1208 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1211 using namespace IntervalMapImpl;
1213 const unsigned Nodes = RootBranch::Capacity / Branch::Capacity + 1;
1216 unsigned Size[Nodes];
1217 IdxPair NewOffset(0, Position);
1223 NewOffset =
distribute(Nodes, rootSize, Leaf::Capacity,
nullptr, Size,
1228 NodeRef Node[Nodes];
1229 for (
unsigned n = 0; n != Nodes; ++n) {
1230 Branch *
B = newNode<Branch>();
1231 B->
copy(rootBranch(), Pos, 0, Size[n]);
1232 Node[n] = NodeRef(B, Size[n]);
1236 for (
unsigned n = 0; n != Nodes; ++n) {
1237 rootBranch().stop(n) = Node[n].template get<Branch>().stop(Size[n]-1);
1238 rootBranch().subtree(n) = Node[n];
1246 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1254 for (
unsigned i = 0; i != rootSize; ++i)
1255 Refs.
push_back(rootBranch().subtree(i));
1258 for (
unsigned h = height - 1; h; --h) {
1259 for (
unsigned i = 0, e = Refs.
size(); i != e; ++i) {
1260 for (
unsigned j = 0, s = Refs[i].
size(); j != s; ++j)
1262 (this->*f)(Refs[i], h);
1265 Refs.
swap(NextRefs);
1269 for (
unsigned i = 0, e = Refs.
size(); i != e; ++i)
1270 (this->*f)(Refs[i], 0);
1273 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1279 deleteNode(&Node.
get<
Leaf>());
1282 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1286 visitNodes(&IntervalMap::deleteNode);
1296 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1298 public std::iterator<std::bidirectional_iterator_tag, ValT> {
1314 assert(map &&
"Invalid iterator");
1315 return map->branched();
1325 void pathFillFind(KeyT x);
1326 void treeFind(KeyT x);
1327 void treeAdvanceTo(KeyT x);
1331 assert(valid() &&
"Cannot access invalid iterator");
1338 assert(valid() &&
"Cannot access invalid iterator");
1345 assert(valid() &&
"Cannot access invalid iterator");
1365 const KeyT &
start()
const {
return unsafeStart(); }
1368 const KeyT &
stop()
const {
return unsafeStop(); }
1371 const ValT &
value()
const {
return unsafeValue(); }
1376 assert(map == RHS.
map &&
"Cannot compare iterators from different maps");
1378 return !RHS.
valid();
1381 return &path.template leaf<Leaf>() == &RHS.
path.template leaf<Leaf>();
1397 setRoot(map->rootSize);
1402 assert(valid() &&
"Cannot increment end()");
1417 if (path.
leafOffset() && (valid() || !branched()))
1437 setRoot(map->rootLeaf().
findFrom(0, map->rootSize, x));
1456 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1460 for (
unsigned i = map->height - path.height() - 1; i; --i) {
1461 unsigned p = NR.
get<
Branch>().safeFind(0, x);
1470 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1473 setRoot(map->rootBranch().findFrom(0, map->rootSize, x));
1480 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1484 if (!Traits::stopLess(path.leaf<
Leaf>().
stop(path.leafSize() - 1), x)) {
1485 path.leafOffset() = path.leaf<
Leaf>().safeFind(path.leafOffset(), x);
1493 if (path.height()) {
1494 for (
unsigned l = path.height() - 1; l; --l) {
1495 if (!Traits::stopLess(path.node<
Branch>(l).
stop(path.offset(l)), x)) {
1497 path.offset(l + 1) =
1498 path.node<
Branch>(l + 1).safeFind(path.offset(l + 1), x);
1499 return pathFillFind(x);
1504 if (!Traits::stopLess(map->rootBranch().stop(path.offset(0)), x)) {
1505 path.offset(1) = path.node<
Branch>(1).safeFind(path.offset(1), x);
1506 return pathFillFind(x);
1511 setRoot(map->rootBranch().findFrom(path.offset(0), map->rootSize, x));
1520 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1528 void setNodeStop(
unsigned Level, KeyT Stop);
1530 template <
typename NodeT>
bool overflow(
unsigned Level);
1531 void treeInsert(KeyT a, KeyT b, ValT y);
1532 void eraseNode(
unsigned Level);
1533 void treeErase(
bool UpdateRoot =
true);
1534 bool canCoalesceLeft(KeyT Start, ValT x);
1535 bool canCoalesceRight(KeyT Stop, ValT x);
1544 void setStart(KeyT a);
1549 void setStop(KeyT b);
1554 void setValue(ValT x);
1567 this->unsafeStop() = b;
1569 if (this->path.atLastEntry(this->path.height()))
1570 setNodeStop(this->path.height(), b);
1579 void insert(KeyT a, KeyT b, ValT y);
1585 const_iterator::operator++();
1596 const_iterator::operator--();
1612 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1615 using namespace IntervalMapImpl;
1616 Path &P = this->path;
1617 if (!this->branched()) {
1618 unsigned i = P.leafOffset();
1620 return i && Node.
value(i-1) == Value &&
1621 Traits::adjacent(Node.
stop(i-1), Start);
1624 if (
unsigned i = P.leafOffset()) {
1626 return Node.
value(i-1) == Value && Traits::adjacent(Node.
stop(i-1), Start);
1627 }
else if (NodeRef NR = P.getLeftSibling(P.height())) {
1628 unsigned i = NR.size() - 1;
1630 return Node.
value(i) == Value && Traits::adjacent(Node.
stop(i), Start);
1640 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1643 using namespace IntervalMapImpl;
1644 Path &P = this->path;
1645 unsigned i = P.leafOffset() + 1;
1646 if (!this->branched()) {
1647 if (i >= P.leafSize())
1650 return Node.
value(i) == Value && Traits::adjacent(Stop, Node.
start(i));
1653 if (i < P.leafSize()) {
1655 return Node.
value(i) == Value && Traits::adjacent(Stop, Node.
start(i));
1656 }
else if (NodeRef NR = P.getRightSibling(P.height())) {
1658 return Node.
value(0) == Value && Traits::adjacent(Stop, Node.
start(0));
1664 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1681 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1684 assert(Traits::nonEmpty(a, this->stop()) &&
"Cannot move start beyond stop");
1685 KeyT &CurStart = this->unsafeStart();
1686 if (!Traits::startLess(a, CurStart) || !canCoalesceLeft(a, this->value())) {
1694 setStartUnchecked(a);
1697 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1700 assert(Traits::nonEmpty(this->start(), b) &&
"Cannot move stop beyond start");
1701 if (Traits::startLess(b, this->stop()) ||
1702 !canCoalesceRight(b, this->value())) {
1703 setStopUnchecked(b);
1707 KeyT a = this->start();
1709 setStartUnchecked(a);
1712 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1715 setValueUnchecked(x);
1716 if (canCoalesceRight(this->stop(), x)) {
1717 KeyT a = this->start();
1719 setStartUnchecked(a);
1721 if (canCoalesceLeft(this->start(), x)) {
1723 KeyT a = this->start();
1725 setStartUnchecked(a);
1735 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1738 assert(Level &&
"Cannot insert next to the root");
1739 bool SplitRoot =
false;
1745 if (IM.rootSize < RootBranch::Capacity) {
1746 IM.rootBranch().
insert(P.
offset(0), IM.rootSize, Node, Stop);
1765 if (P.
size(Level) == Branch::Capacity) {
1767 assert(!SplitRoot &&
"Cannot overflow after splitting the root");
1768 SplitRoot = overflow<Branch>(
Level);
1774 setNodeStop(Level, Stop);
1780 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1783 if (this->branched())
1784 return treeInsert(a, b, y);
1792 if (Size <= RootLeaf::Capacity) {
1793 P.
setSize(0, IM.rootSize = Size);
1802 treeInsert(a, b, y);
1805 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1808 using namespace IntervalMapImpl;
1809 Path &P = this->path;
1812 P.legalizeForInsert(this->map->height);
1815 if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<
Leaf>().
start(0))) {
1817 if (NodeRef Sib = P.getLeftSibling(P.height())) {
1819 unsigned SibOfs = Sib.size() - 1;
1820 if (SibLeaf.
value(SibOfs) == y &&
1821 Traits::adjacent(SibLeaf.
stop(SibOfs), a)) {
1829 if (Traits::stopLess(b, CurLeaf.
start(0)) &&
1830 (y != CurLeaf.
value(0) || !Traits::adjacent(b, CurLeaf.
start(0)))) {
1832 setNodeStop(P.height(), SibLeaf.
stop(SibOfs) = b);
1837 a = SibLeaf.
start(SibOfs);
1843 this->map->rootBranchStart() = a;
1848 unsigned Size = P.leafSize();
1849 bool Grow = P.leafOffset() ==
Size;
1850 Size = P.leaf<
Leaf>().insertFrom(P.leafOffset(),
Size, a, b, y);
1853 if (Size > Leaf::Capacity) {
1854 overflow<Leaf>(P.height());
1855 Grow = P.leafOffset() == P.leafSize();
1856 Size = P.leaf<
Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
1857 assert(Size <= Leaf::Capacity &&
"overflow() didn't make room");
1861 P.setSize(P.height(),
Size);
1865 setNodeStop(P.height(), b);
1869 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1875 if (this->branched())
1882 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1891 IM.deleteNode(&Node);
1892 eraseNode(IM.height);
1894 if (UpdateRoot && IM.branched() && P.
valid() && P.
atBegin())
1895 IM.rootBranchStart() = P.
leaf<
Leaf>().start(0);
1901 unsigned NewSize = P.
leafSize() - 1;
1902 P.
setSize(IM.height, NewSize);
1905 setNodeStop(IM.height, Node.
stop(NewSize - 1));
1907 }
else if (UpdateRoot && P.
atBegin())
1908 IM.rootBranchStart() = P.
leaf<
Leaf>().start(0);
1915 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1918 assert(Level &&
"Cannot erase root node");
1927 IM.switchRootToLeaf();
1934 if (P.
size(Level) == 1) {
1936 IM.deleteNode(&Parent);
1941 unsigned NewSize = P.
size(Level) - 1;
1944 if (P.
offset(Level) == NewSize) {
1945 setNodeStop(Level, Parent.
stop(NewSize - 1));
1963 template <
typename KeyT,
typename ValT,
unsigned N,
typename Traits>
1964 template <
typename NodeT>
1967 using namespace IntervalMapImpl;
1968 Path &P = this->path;
1969 unsigned CurSize[4];
1972 unsigned Elements = 0;
1973 unsigned Offset = P.offset(Level);
1976 NodeRef LeftSib = P.getLeftSibling(Level);
1978 Offset += Elements = CurSize[Nodes] = LeftSib.size();
1979 Node[Nodes++] = &LeftSib.get<NodeT>();
1983 Elements += CurSize[Nodes] = P.size(Level);
1984 Node[Nodes++] = &P.node<NodeT>(
Level);
1987 NodeRef RightSib = P.getRightSibling(Level);
1989 Elements += CurSize[Nodes] = RightSib.size();
1990 Node[Nodes++] = &RightSib.get<NodeT>();
1994 unsigned NewNode = 0;
1995 if (Elements + 1 > Nodes * NodeT::Capacity) {
1997 NewNode = Nodes == 1 ? 1 : Nodes - 1;
1998 CurSize[Nodes] = CurSize[NewNode];
1999 Node[Nodes] = Node[NewNode];
2000 CurSize[NewNode] = 0;
2001 Node[NewNode] = this->map->template newNode<NodeT>();
2006 unsigned NewSize[4];
2007 IdxPair NewOffset =
distribute(Nodes, Elements, NodeT::Capacity,
2008 CurSize, NewSize, Offset,
true);
2016 bool SplitRoot =
false;
2019 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
2020 if (NewNode && Pos == NewNode) {
2021 SplitRoot = insertNode(Level, NodeRef(Node[Pos], NewSize[Pos]), Stop);
2024 P.setSize(Level, NewSize[Pos]);
2025 setNodeStop(Level, Stop);
2027 if (Pos + 1 == Nodes)
2034 while(Pos != NewOffset.first) {
2038 P.offset(Level) = NewOffset.second;
2058 template <
typename MapA,
typename MapB>
2060 using KeyType =
typename MapA::KeyType;
2061 using Traits =
typename MapA::KeyTraits;
2063 typename MapA::const_iterator posA;
2064 typename MapB::const_iterator posB;
2073 if (Traits::stopLess(posA.stop(), posB.start())) {
2075 posA.advanceTo(posB.start());
2076 if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2078 }
else if (Traits::stopLess(posB.stop(), posA.start())) {
2080 posB.advanceTo(posA.start());
2081 if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2089 posA.advanceTo(posB.start());
2090 if (!posA.valid() || !Traits::stopLess(posB.stop(), posA.start()))
2093 posB.advanceTo(posA.start());
2094 if (!posB.valid() || !Traits::stopLess(posA.stop(), posB.start()))
2103 posB(posA.valid() ? b.
find(posA.start()) : b.
end()) { advance(); }
2107 return posA.valid() && posB.valid();
2111 const typename MapA::const_iterator &
a()
const {
return posA; }
2114 const typename MapB::const_iterator &
b()
const {
return posB; }
2118 KeyType ak = a().start();
2119 KeyType bk = b().start();
2120 return Traits::startLess(ak, bk) ? bk : ak;
2125 KeyType ak = a().stop();
2126 KeyType bk = b().stop();
2127 return Traits::startLess(ak, bk) ? ak : bk;
2145 if (Traits::startLess(posB.stop(), posA.stop()))
2158 if (Traits::stopLess(posA.stop(), x))
2160 if (Traits::stopLess(posB.stop(), x))
2168 #endif // LLVM_ADT_INTERVALMAP_H unsigned safeFind(unsigned i, KeyT x) const
safeFind - Find an interval that is known to exist.
void setValueUnchecked(ValT x)
setValueUnchecked - Change the mapped value of the current interval without checking for coalescing...
bool valid() const
valid - Return true if path is at a valid node, not at end().
const_iterator end(StringRef path)
Get end iterator over path.
void setValue(ValT x)
setValue - Change the mapped value of the current interval.
void transferToLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count)
transferToLeftSib - Transfer elements to a left sibling node.
void setInt(IntType IntVal)
void copy(const NodeBase< T1, T2, M > &Other, unsigned i, unsigned j, unsigned Count)
copy - Copy elements from another node.
void adjustSiblingSizes(NodeT *Node[], unsigned Nodes, unsigned CurSize[], const unsigned NewSize[])
IntervalMapImpl::adjustSiblingSizes - Move elements between sibling nodes.
const KeyT & stop(unsigned i) const
This class represents lattice values for constants.
PointerTy getPointer() const
const MapB::const_iterator & b() const
b - access the right hand side in the overlap.
void legalizeForInsert(unsigned Level)
legalizeForInsert - Prepare the path for an insertion at Level.
IntervalMapOverlaps - Iterate over the overlaps of mapped intervals in two IntervalMaps.
void push_back(const T &Elt)
NodeT & node(unsigned Level) const
IntervalMapOverlaps & operator++()
Preincrement - Move to the next overlap.
void skipA()
skipA - Move to the next overlap that doesn't involve a().
const_iterator(const IntervalMap &map)
void moveLeft(unsigned Level)
moveLeft - Move path to the left sibling at Level.
void pop()
pop - Remove the last path entry.
bool valid() const
valid - Return true if the current position is valid, false for end().
int adjustFromLeftSib(unsigned Size, NodeBase &Sib, unsigned SSize, int Add)
adjustFromLeftSib - Adjust the number if elements in this node by moving elements to or from a left s...
unsigned & offset(unsigned Level)
void setMap(const IntervalMap &m)
setMap - Change the map iterated over.
bool operator!=(const const_iterator &RHS) const
void fillLeft(unsigned Height)
fillLeft - Grow path to Height by taking leftmost branches.
static bool adjacent(const T &a, const T &b)
adjacent - Return true when the intervals [x;a) and [b;y) can coalesce.
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
const_iterator begin() const
bool atBegin() const
atBegin - Return true if path is at begin().
void setRoot(unsigned Offset)
static bool stopLess(const T &b, const T &x)
stopLess - Return true if x is not in [a;b].
const_iterator & operator++()
preincrement - move to the next interval.
ValT safeLookup(KeyT x, ValT NotFound) const
safeLookup - Lookup mapped value for a safe key.
unsigned safeFind(unsigned i, KeyT x) const
safeFind - Find a subtree that is known to exist.
bool operator==(const NodeRef &RHS) const
void advanceTo(KeyT x)
advanceTo - Move to the first interval with stop >= x, or end().
void * getOpaqueValue() const
KeyT & unsafeStart() const
unsafeStart - Writable access to start() for iterator.
RecyclingAllocator - This class wraps an Allocator, adding the functionality of recycling deleted obj...
void treeAdvanceTo(KeyT x)
treeAdvanceTo - Find position after the current one.
Position
Position to insert a new instruction relative to an existing instruction.
ValT lookup(KeyT x, ValT NotFound=ValT()) const
lookup - Return the mapped value at x or NotFound.
NodeT & get() const
get - Dereference as a NodeT reference.
KeyT start() const
start - Return the smallest mapped key in a non-empty map.
static bool startLess(const T &x, const T &a)
startLess - Return true if x is not in [a;b).
unsigned findFrom(unsigned i, unsigned Size, KeyT x) const
findFrom - Find the first subtree after i that may contain x.
unsigned height() const
height - Return the height of the tree corresponding to this path.
void erase()
erase - Erase the current interval.
bool operator==(const const_iterator &RHS) const
void clear()
clear - Remove all entries.
NodeRef & subtree(unsigned i) const
subtree - Access the i'th subtree reference in a branch node.
IntervalMap(Allocator &a)
KeyType stop() const
stop - End of the overlapping interval.
const_iterator find(KeyT x) const
find - Return an iterator pointing to the first interval ending at or after x, or end()...
void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop)
insert - Insert a new (subtree, stop) pair.
KeyType start() const
start - Beginning of the overlapping interval.
void erase(unsigned i, unsigned j, unsigned Size)
erase - Erase elements [i;j).
void transferToRightSib(unsigned Size, NodeBase &Sib, unsigned SSize, unsigned Count)
transferToRightSib - Transfer elements to a right sibling node.
void setStartUnchecked(KeyT a)
setStartUnchecked - Move the start of the current interval without checking for coalescing or overlap...
bool valid() const
valid - Return true if iterator is at an overlap.
IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity, const unsigned *CurSize, unsigned NewSize[], unsigned Position, bool Grow)
IntervalMapImpl::distribute - Compute a new distribution of node elements after an overflow or underf...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void replaceRoot(void *Root, unsigned Size, IdxPair Offsets)
replaceRoot - Replace the current root node with two new entries after the tree height has increased...
typename Sizer::Allocator Allocator
const KeyT & stop(unsigned i) const
void swap(SmallVectorImpl &RHS)
Sentinel value for when no action was found in the specified table.
const MapA::const_iterator & a() const
a - access the left hand side in the overlap.
void moveRight(unsigned i, unsigned j, unsigned Count)
moveRight - Move elements to the right.
const_iterator end() const
void find(KeyT x)
find - Move to the first interval with stop >= x, or end().
const KeyT & start() const
start - Return the beginning of the current interval.
NodeRef & subtree(unsigned Level) const
subtree - Get the subtree referenced from Level.
const_iterator & operator--()
predecrement - move to the previous interval.
void goToBegin()
goToBegin - Move to the first interval in map.
KeyT stop() const
stop - Return the largest mapped key in a non-empty map.
void setStop(KeyT b)
setStop - Move the end of the current interval.
const KeyT & start(unsigned i) const
unsigned leafSize() const
bool atBegin() const
atBegin - Return true if the current position is the first map entry.
static bool startLess(const T &x, const T &a)
startLess - Return true if x is not in [a;b].
IntervalMapOverlaps(const MapA &a, const MapB &b)
IntervalMapOverlaps - Create an iterator for the overlaps of a and b.
const_iterator operator++(int)
postincrement - Dont do that!
llvm::AlignedCharArray< alignof(llvm::detail::AlignerImpl< T1, T2, T3, T4, T5, T6, T7, T8, T9, T10 >), sizeof(::llvm::detail::SizerImpl< T1, T2, T3, T4, T5, T6, T7, T8, T9, T10 >)>::buffer char buffer[Size]
static bool stopLess(const T &b, const T &x)
stopLess - Return true if x is not in [a;b).
void skipB()
skipB - Move to the next overlap that doesn't involve b().
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
unsigned size(unsigned Level) const
const ValT & value(unsigned i) const
NodeRef safeLookup(KeyT x) const
safeLookup - Get the subtree containing x, Assuming that x is in range.
void moveLeft(unsigned i, unsigned j, unsigned Count)
moveLeft - Move elements to the left.
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
std::pair< unsigned, unsigned > IdxPair
void goToEnd()
goToEnd - Move beyond the last interval in map.
void setStart(KeyT a)
setStart - Move the start of the current interval.
unsigned leafOffset() const
unsigned findFrom(unsigned i, unsigned Size, KeyT x) const
findFrom - Find the first interval after i that may contain x.
void advanceTo(KeyType x)
advanceTo - Move to the first overlapping interval with stopLess(x, stop()).
const ValT & value() const
value - Return the mapped value at the current interval.
bool operator!=(const NodeRef &RHS) const
bool empty() const
empty - Return true when no intervals are mapped.
void reset(unsigned Level)
reset - Reset cached information about node(Level) from subtree(Level -1).
void erase(unsigned i, unsigned Size)
erase - Erase element at i.
This union template exposes a suitably aligned and sized character array member which can hold elemen...
static void clear(coro::Shape &Shape)
void pathFillFind(KeyT x)
pathFillFind - Complete path by searching for x.
void push(NodeRef Node, unsigned Offset)
push - Add entry to path.
const KeyT & stop() const
stop - Return the end of the current interval.
void moveRight(unsigned Level)
moveRight - Move path to the left sibling at Level.
unsigned offset(unsigned Level) const
void insert(KeyT a, KeyT b, ValT y)
insert - Insert mapping [a;b] -> y before the current position.
#define LLVM_ALIGNAS(x)
LLVM_ALIGNAS Used to specify a minimum alignment for a structure or variable.
static bool nonEmpty(const T &a, const T &b)
nonEmpty - Return true if [a;b] is non-empty.
KeyT & unsafeStop() const
unsafeStop - Writable access to stop() for iterator.
unsigned size() const
size - Return the number of elements in the referenced node.
LLVM_NODISCARD bool empty() const
void treeFind(KeyT x)
treeFind - Find in a branched tree.
IntervalMapImpl::Path path
unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y)
insertFrom - Add mapping of [a;b] to y if possible, coalescing as much as possible.
NodeRef & subtree(unsigned i)
const_iterator operator--(int)
postdecrement - Dont do that!
const NodeRef & subtree(unsigned i) const
To bit_cast(const From &from) noexcept
bool atLastEntry(unsigned Level) const
atLastEntry - Return true if the path is at the last entry of the node at Level.
void setStopUnchecked(KeyT b)
setStopUnchecked - Move the end of the current interval without checking for coalescing or overlaps...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void setRoot(void *Node, unsigned Size, unsigned Offset)
setRoot - Clear the path and set a new root node.
void setSize(unsigned n)
setSize - Update the node size.
static bool adjacent(const T &a, const T &b)
adjacent - Return true when the intervals [x;a] and [b;y] can coalesce.
LLVM Value Representation.
void shift(unsigned i, unsigned Size)
shift - Shift elements [i;size) 1 position to the right.
const ValT & operator*() const
bool operator==(uint64_t V1, const APInt &V2)
static bool nonEmpty(const T &a, const T &b)
nonEmpty - Return true if [a;b) is non-empty.
OutputIt copy(R &&Range, OutputIt Out)
SlotIndex - An opaque wrapper around machine indexes.
void setSize(unsigned Level, unsigned Size)
setSize - Set the size of a node both in the path and in the tree.
NodeRef(NodeT *p, unsigned n)
NodeRef - Create a reference to the node p with n elements.
bool overlaps(KeyT a, KeyT b)
overlaps(a, b) - Return true if the intervals in this map overlap with the interval [a;b]...
ValT & unsafeValue() const
unsafeValue - Writable access to value() for iterator.