Line data Source code
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 46982 : void Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {
20 : assert(!path.empty() && "Can't replace missing root");
21 46982 : path.front() = Entry(Root, Size, Offsets.first);
22 93964 : path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));
23 46982 : }
24 :
25 612193 : NodeRef Path::getLeftSibling(unsigned Level) const {
26 : // The root has no siblings.
27 612193 : if (Level == 0)
28 0 : return NodeRef();
29 :
30 : // Go up the tree until we can go left.
31 612193 : unsigned l = Level - 1;
32 640300 : while (l && path[l].offset == 0)
33 28107 : --l;
34 :
35 : // We can't go left.
36 1224386 : if (path[l].offset == 0)
37 82207 : return NodeRef();
38 :
39 : // NR is the subtree containing our left sibling.
40 529986 : NodeRef NR = path[l].subtree(path[l].offset - 1);
41 :
42 : // Keep right all the way down.
43 544265 : for (++l; l != Level; ++l)
44 14279 : NR = NR.subtree(NR.size() - 1);
45 529986 : return NR;
46 : }
47 :
48 1029768 : 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 846344 : l = Level - 1;
55 1740406 : while (path[l].offset == 0) {
56 : assert(l != 0 && "Cannot move beyond begin()");
57 23859 : --l;
58 : }
59 183424 : } else if (height() < Level)
60 : // end() may have created a height=0 path.
61 361872 : path.resize(Level + 1, Entry(nullptr, 0, 0));
62 :
63 : // NR is the subtree containing our left sibling.
64 2059536 : --path[l].offset;
65 1029768 : NodeRef NR = subtree(l);
66 :
67 : // Get the rightmost node in the subtree.
68 1090271 : for (++l; l != Level; ++l) {
69 121006 : path[l] = Entry(NR, NR.size() - 1);
70 60503 : NR = NR.subtree(NR.size() - 1);
71 : }
72 2059536 : path[l] = Entry(NR, NR.size() - 1);
73 1029768 : }
74 :
75 478657 : NodeRef Path::getRightSibling(unsigned Level) const {
76 : // The root has no siblings.
77 478657 : if (Level == 0)
78 0 : return NodeRef();
79 :
80 : // Go up the tree until we can go right.
81 478657 : unsigned l = Level - 1;
82 524094 : while (l && atLastEntry(l))
83 45437 : --l;
84 :
85 : // We can't go right.
86 478657 : if (atLastEntry(l))
87 180579 : return NodeRef();
88 :
89 : // NR is the subtree containing our right sibling.
90 298078 : NodeRef NR = path[l].subtree(path[l].offset + 1);
91 :
92 : // Keep left all the way down.
93 308819 : for (++l; l != Level; ++l)
94 10741 : NR = NR.subtree(0);
95 298078 : return NR;
96 : }
97 :
98 1687687 : 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 1687687 : unsigned l = Level - 1;
103 1766933 : while (l && atLastEntry(l))
104 79246 : --l;
105 :
106 : // NR is the subtree containing our right sibling. If we hit end(), we have
107 : // offset(0) == node(0).size().
108 3375374 : if (++path[l].offset == path[l].size)
109 : return;
110 1572202 : NodeRef NR = subtree(l);
111 :
112 1634209 : for (++l; l != Level; ++l) {
113 62007 : path[l] = Entry(NR, 0);
114 62007 : NR = NR.subtree(0);
115 : }
116 3144404 : path[l] = Entry(NR, 0);
117 : }
118 :
119 :
120 519644 : 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 519644 : if (!Nodes)
126 0 : return IdxPair();
127 :
128 : // Trivial algorithm: left-leaning even distribution.
129 519644 : const unsigned PerNode = (Elements + Grow) / Nodes;
130 519644 : const unsigned Extra = (Elements + Grow) % Nodes;
131 : IdxPair PosPair = IdxPair(Nodes, 0);
132 : unsigned Sum = 0;
133 1961096 : for (unsigned n = 0; n != Nodes; ++n) {
134 1441452 : Sum += NewSize[n] = PerNode + (n < Extra);
135 1441452 : if (PosPair.first == Nodes && Sum > Position)
136 519644 : 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 519644 : if (Grow) {
142 : assert(PosPair.first < Nodes && "Bad algebra");
143 : assert(NewSize[PosPair.first] && "Too few elements to need Grow");
144 519644 : --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 519644 : return PosPair;
157 : }
158 :
159 : } // namespace IntervalMapImpl
160 : } // namespace llvm
161 :
|
