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