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
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(path.begin() + 1, Entry(subtree(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(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
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(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
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(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
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(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
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