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