|
150
|
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"
|
|
173
|
14 #include <cassert>
|
|
150
|
15
|
|
|
16 namespace llvm {
|
|
|
17 namespace IntervalMapImpl {
|
|
|
18
|
|
|
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
|
|
|
25 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
|
|
|
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
|
|
|
75 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
|
|
|
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
|
|
|
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
|
