17namespace IntervalMapImpl {
20 assert(!path.
empty() &&
"Can't replace missing root");
21 path.
front() = Entry(Root,
Size, Offsets.first);
31 unsigned l = Level - 1;
32 while (l && path[l].
offset == 0)
43 for (++l; l != Level; ++l)
49 assert(Level != 0 &&
"Cannot move the root node");
55 while (path[l].
offset == 0) {
56 assert(l != 0 &&
"Cannot move beyond begin()");
59 }
else if (
height() < Level)
61 path.
resize(Level + 1, Entry(
nullptr, 0, 0));
68 for (++l; l != Level; ++l) {
69 path[l] = Entry(NR, NR.
size() - 1);
72 path[l] = Entry(NR, NR.
size() - 1);
81 unsigned l = Level - 1;
93 for (++l; l != Level; ++l)
99 assert(Level != 0 &&
"Cannot move the root node");
102 unsigned l = Level - 1;
112 for (++l; l != Level; ++l) {
113 path[l] = Entry(NR, 0);
116 path[l] = Entry(NR, 0);
121 const unsigned *CurSize,
unsigned NewSize[],
122 unsigned Position,
bool Grow) {
123 assert(Elements + Grow <= Nodes * Capacity &&
"Not enough room for elements");
124 assert(Position <= Elements &&
"Invalid position");
129 const unsigned PerNode = (Elements + Grow) / Nodes;
130 const unsigned Extra = (Elements + Grow) % Nodes;
133 for (
unsigned n = 0; n != Nodes; ++n) {
134 Sum += NewSize[n] = PerNode + (n < Extra);
135 if (PosPair.first == Nodes && Sum > Position)
136 PosPair =
IdxPair(n, Position - (Sum - NewSize[n]));
138 assert(Sum == Elements + Grow &&
"Bad distribution sum");
142 assert(PosPair.first < Nodes &&
"Bad algebra");
143 assert(NewSize[PosPair.first] &&
"Too few elements to need Grow");
144 --NewSize[PosPair.first];
149 for (
unsigned n = 0; n != Nodes; ++n) {
150 assert(NewSize[n] <= Capacity &&
"Overallocated node");
153 assert(Sum == Elements &&
"Bad distribution sum");
This file implements a coalescing interval map for small objects.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned size() const
size - Return the number of elements in the referenced node.
NodeRef & subtree(unsigned i) const
subtree - Access the i'th subtree reference in a branch node.
void replaceRoot(void *Root, unsigned Size, IdxPair Offsets)
replaceRoot - Replace the current root node with two new entries after the tree height has increased.
bool valid() const
valid - Return true if path is at a valid node, not at end().
NodeRef getLeftSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
unsigned offset(unsigned Level) const
bool atLastEntry(unsigned Level) const
atLastEntry - Return true if the path is at the last entry of the node at Level.
unsigned height() const
height - Return the height of the tree corresponding to this path.
void moveRight(unsigned Level)
moveRight - Move path to the left sibling at Level.
NodeRef getRightSibling(unsigned Level) const
getLeftSibling - Get the left sibling node at Level, or a null NodeRef.
unsigned size(unsigned Level) const
void moveLeft(unsigned Level)
moveLeft - Move path to the left sibling at Level.
NodeRef & subtree(unsigned Level) const
subtree - Get the subtree referenced from Level.
iterator insert(iterator I, T &&Elt)
std::pair< unsigned, unsigned > IdxPair
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...
This is an optimization pass for GlobalISel generic memory operations.