• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
replaceRoot(void * Root,unsigned Size,IdxPair Offsets)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 
getLeftSibling(unsigned Level) const25 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 
moveLeft(unsigned Level)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.
61     path.resize(Level + 1, Entry(nullptr, 0, 0));
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 
getRightSibling(unsigned Level) const75 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 
moveRight(unsigned Level)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 
distribute(unsigned Nodes,unsigned Elements,unsigned Capacity,const unsigned * CurSize,unsigned NewSize[],unsigned Position,bool Grow)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 
162