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
16namespace llvm {
17namespace IntervalMapImpl {
18
19void 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(I: path.begin() + 1, Elt: Entry(subtree(Level: 0), Offsets.second));
23}
24
25NodeRef 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(i: path[l].offset - 1);
41
42 // Keep right all the way down.
43 for (++l; l != Level; ++l)
44 NR = NR.subtree(i: NR.size() - 1);
45 return NR;
46}
47
48void 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(N: Level + 1, NV: Entry(nullptr, 0, 0));
62
63 // NR is the subtree containing our left sibling.
64 --path[l].offset;
65 NodeRef NR = subtree(Level: 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(i: NR.size() - 1);
71 }
72 path[l] = Entry(NR, NR.size() - 1);
73}
74
75NodeRef 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(Level: l))
83 --l;
84
85 // We can't go right.
86 if (atLastEntry(Level: l))
87 return NodeRef();
88
89 // NR is the subtree containing our right sibling.
90 NodeRef NR = path[l].subtree(i: path[l].offset + 1);
91
92 // Keep left all the way down.
93 for (++l; l != Level; ++l)
94 NR = NR.subtree(i: 0);
95 return NR;
96}
97
98void 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(Level: 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(Level: l);
111
112 for (++l; l != Level; ++l) {
113 path[l] = Entry(NR, 0);
114 NR = NR.subtree(i: 0);
115 }
116 path[l] = Entry(NR, 0);
117}
118
119
120IdxPair 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