1 //===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===//
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 the few non-templated functions in IntervalMap.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/ADT/IntervalMap.h"
14 #include <cassert>
15
16 namespace llvm {
17 namespace IntervalMapImpl {
18
replaceRoot(void * Root,unsigned Size,IdxPair Offsets)19 void Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {
20 assert(!path.empty() && "Can't replace missing root");
21 path.front() = Entry(Root, Size, Offsets.first);
22 path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));
23 }
24
getLeftSibling(unsigned Level) const25 NodeRef Path::getLeftSibling(unsigned Level) const {
26 // The root has no siblings.
27 if (Level == 0)
28 return NodeRef();
29
30 // Go up the tree until we can go left.
31 unsigned l = Level - 1;
32 while (l && path[l].offset == 0)
33 --l;
34
35 // We can't go left.
36 if (path[l].offset == 0)
37 return NodeRef();
38
39 // NR is the subtree containing our left sibling.
40 NodeRef NR = path[l].subtree(path[l].offset - 1);
41
42 // Keep right all the way down.
43 for (++l; l != Level; ++l)
44 NR = NR.subtree(NR.size() - 1);
45 return NR;
46 }
47
moveLeft(unsigned Level)48 void Path::moveLeft(unsigned Level) {
49 assert(Level != 0 && "Cannot move the root node");
50
51 // Go up the tree until we can go left.
52 unsigned l = 0;
53 if (valid()) {
54 l = Level - 1;
55 while (path[l].offset == 0) {
56 assert(l != 0 && "Cannot move beyond begin()");
57 --l;
58 }
59 } else if (height() < Level)
60 // end() may have created a height=0 path.
61 path.resize(Level + 1, Entry(nullptr, 0, 0));
62
63 // NR is the subtree containing our left sibling.
64 --path[l].offset;
65 NodeRef NR = subtree(l);
66
67 // Get the rightmost node in the subtree.
68 for (++l; l != Level; ++l) {
69 path[l] = Entry(NR, NR.size() - 1);
70 NR = NR.subtree(NR.size() - 1);
71 }
72 path[l] = Entry(NR, NR.size() - 1);
73 }
74
getRightSibling(unsigned Level) const75 NodeRef Path::getRightSibling(unsigned Level) const {
76 // The root has no siblings.
77 if (Level == 0)
78 return NodeRef();
79
80 // Go up the tree until we can go right.
81 unsigned l = Level - 1;
82 while (l && atLastEntry(l))
83 --l;
84
85 // We can't go right.
86 if (atLastEntry(l))
87 return NodeRef();
88
89 // NR is the subtree containing our right sibling.
90 NodeRef NR = path[l].subtree(path[l].offset + 1);
91
92 // Keep left all the way down.
93 for (++l; l != Level; ++l)
94 NR = NR.subtree(0);
95 return NR;
96 }
97
moveRight(unsigned Level)98 void Path::moveRight(unsigned Level) {
99 assert(Level != 0 && "Cannot move the root node");
100
101 // Go up the tree until we can go right.
102 unsigned l = Level - 1;
103 while (l && atLastEntry(l))
104 --l;
105
106 // NR is the subtree containing our right sibling. If we hit end(), we have
107 // offset(0) == node(0).size().
108 if (++path[l].offset == path[l].size)
109 return;
110 NodeRef NR = subtree(l);
111
112 for (++l; l != Level; ++l) {
113 path[l] = Entry(NR, 0);
114 NR = NR.subtree(0);
115 }
116 path[l] = Entry(NR, 0);
117 }
118
119
distribute(unsigned Nodes,unsigned Elements,unsigned Capacity,const unsigned * CurSize,unsigned NewSize[],unsigned Position,bool Grow)120 IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
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");
125 if (!Nodes)
126 return IdxPair();
127
128 // Trivial algorithm: left-leaning even distribution.
129 const unsigned PerNode = (Elements + Grow) / Nodes;
130 const unsigned Extra = (Elements + Grow) % Nodes;
131 IdxPair PosPair = IdxPair(Nodes, 0);
132 unsigned Sum = 0;
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]));
137 }
138 assert(Sum == Elements + Grow && "Bad distribution sum");
139
140 // Subtract the Grow element that was added.
141 if (Grow) {
142 assert(PosPair.first < Nodes && "Bad algebra");
143 assert(NewSize[PosPair.first] && "Too few elements to need Grow");
144 --NewSize[PosPair.first];
145 }
146
147 #ifndef NDEBUG
148 Sum = 0;
149 for (unsigned n = 0; n != Nodes; ++n) {
150 assert(NewSize[n] <= Capacity && "Overallocated node");
151 Sum += NewSize[n];
152 }
153 assert(Sum == Elements && "Bad distribution sum");
154 #endif
155
156 return PosPair;
157 }
158
159 } // namespace IntervalMapImpl
160 } // namespace llvm
161
162