]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This file implements the few non-templated functions in IntervalMap. | |
11 | // | |
12 | //===----------------------------------------------------------------------===// | |
13 | ||
14 | #include "llvm/ADT/IntervalMap.h" | |
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. | |
1a4d82fc | 61 | path.resize(Level + 1, Entry(nullptr, 0, 0)); |
223e47cc LB |
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 |