IntervalMap.cpp revision 360660 
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
15namespace llvm {
16namespace IntervalMapImpl {
17
18void 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
24NodeRef 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
47void 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
74NodeRef 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
97void 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
119IdxPair 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