IntervalMap.cpp revision 360660
1247738Sbapt//===- lib/Support/IntervalMap.cpp - A sorted interval map ----------------===//
2247738Sbapt//
3247738Sbapt// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4247738Sbapt// See https://llvm.org/LICENSE.txt for license information.
5247738Sbapt// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6247738Sbapt//
7247738Sbapt//===----------------------------------------------------------------------===//
8247738Sbapt//
9247738Sbapt// This file implements the few non-templated functions in IntervalMap.
10247738Sbapt//
11247738Sbapt//===----------------------------------------------------------------------===//
12247738Sbapt
13247738Sbapt#include "llvm/ADT/IntervalMap.h"
14247738Sbapt
15247738Sbaptnamespace llvm {
16247738Sbaptnamespace IntervalMapImpl {
17247738Sbapt
18247738Sbaptvoid Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {
19247738Sbapt  assert(!path.empty() && "Can't replace missing root");
20247738Sbapt  path.front() = Entry(Root, Size, Offsets.first);
21247738Sbapt  path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));
22247738Sbapt}
23247738Sbapt
24247738SbaptNodeRef Path::getLeftSibling(unsigned Level) const {
25247738Sbapt  // The root has no siblings.
26247738Sbapt  if (Level == 0)
27247738Sbapt    return NodeRef();
28247738Sbapt
29247738Sbapt  // Go up the tree until we can go left.
30247738Sbapt  unsigned l = Level - 1;
31247738Sbapt  while (l && path[l].offset == 0)
32247738Sbapt    --l;
33247738Sbapt
34247738Sbapt  // We can't go left.
35247738Sbapt  if (path[l].offset == 0)
36247738Sbapt    return NodeRef();
37247738Sbapt
38247738Sbapt  // NR is the subtree containing our left sibling.
39247738Sbapt  NodeRef NR = path[l].subtree(path[l].offset - 1);
40247738Sbapt
41247738Sbapt  // Keep right all the way down.
42247738Sbapt  for (++l; l != Level; ++l)
43247738Sbapt    NR = NR.subtree(NR.size() - 1);
44247738Sbapt  return NR;
45247738Sbapt}
46247738Sbapt
47247738Sbaptvoid Path::moveLeft(unsigned Level) {
48247738Sbapt  assert(Level != 0 && "Cannot move the root node");
49247738Sbapt
50247738Sbapt  // Go up the tree until we can go left.
51247738Sbapt  unsigned l = 0;
52247738Sbapt  if (valid()) {
53247738Sbapt    l = Level - 1;
54247738Sbapt    while (path[l].offset == 0) {
55247738Sbapt      assert(l != 0 && "Cannot move beyond begin()");
56247738Sbapt      --l;
57247738Sbapt    }
58247738Sbapt  } else if (height() < Level)
59247738Sbapt    // end() may have created a height=0 path.
60247738Sbapt    path.resize(Level + 1, Entry(nullptr, 0, 0));
61247738Sbapt
62247738Sbapt  // NR is the subtree containing our left sibling.
63247738Sbapt  --path[l].offset;
64247738Sbapt  NodeRef NR = subtree(l);
65247738Sbapt
66247738Sbapt  // Get the rightmost node in the subtree.
67247738Sbapt  for (++l; l != Level; ++l) {
68247738Sbapt    path[l] = Entry(NR, NR.size() - 1);
69247738Sbapt    NR = NR.subtree(NR.size() - 1);
70247738Sbapt  }
71247738Sbapt  path[l] = Entry(NR, NR.size() - 1);
72247738Sbapt}
73247738Sbapt
74247738SbaptNodeRef Path::getRightSibling(unsigned Level) const {
75247738Sbapt  // The root has no siblings.
76247738Sbapt  if (Level == 0)
77247738Sbapt    return NodeRef();
78247738Sbapt
79247738Sbapt  // Go up the tree until we can go right.
80247738Sbapt  unsigned l = Level - 1;
81247738Sbapt  while (l && atLastEntry(l))
82247738Sbapt    --l;
83247738Sbapt
84247738Sbapt  // We can't go right.
85247738Sbapt  if (atLastEntry(l))
86247738Sbapt    return NodeRef();
87247738Sbapt
88247738Sbapt  // NR is the subtree containing our right sibling.
89247738Sbapt  NodeRef NR = path[l].subtree(path[l].offset + 1);
90247738Sbapt
91247738Sbapt  // Keep left all the way down.
92247738Sbapt  for (++l; l != Level; ++l)
93247738Sbapt    NR = NR.subtree(0);
94247738Sbapt  return NR;
95247738Sbapt}
96247738Sbapt
97247738Sbaptvoid Path::moveRight(unsigned Level) {
98247738Sbapt  assert(Level != 0 && "Cannot move the root node");
99247738Sbapt
100247738Sbapt  // Go up the tree until we can go right.
101247738Sbapt  unsigned l = Level - 1;
102247738Sbapt  while (l && atLastEntry(l))
103247738Sbapt    --l;
104247738Sbapt
105247738Sbapt  // NR is the subtree containing our right sibling. If we hit end(), we have
106247738Sbapt  // offset(0) == node(0).size().
107247738Sbapt  if (++path[l].offset == path[l].size)
108247738Sbapt    return;
109247738Sbapt  NodeRef NR = subtree(l);
110247738Sbapt
111247738Sbapt  for (++l; l != Level; ++l) {
112247738Sbapt    path[l] = Entry(NR, 0);
113247738Sbapt    NR = NR.subtree(0);
114247738Sbapt  }
115247738Sbapt  path[l] = Entry(NR, 0);
116247738Sbapt}
117247738Sbapt
118247738Sbapt
119247738SbaptIdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
120247738Sbapt                   const unsigned *CurSize, unsigned NewSize[],
121247738Sbapt                   unsigned Position, bool Grow) {
122247738Sbapt  assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements");
123247738Sbapt  assert(Position <= Elements && "Invalid position");
124247738Sbapt  if (!Nodes)
125247738Sbapt    return IdxPair();
126247738Sbapt
127247738Sbapt  // Trivial algorithm: left-leaning even distribution.
128247738Sbapt  const unsigned PerNode = (Elements + Grow) / Nodes;
129247738Sbapt  const unsigned Extra = (Elements + Grow) % Nodes;
130247738Sbapt  IdxPair PosPair = IdxPair(Nodes, 0);
131247738Sbapt  unsigned Sum = 0;
132247738Sbapt  for (unsigned n = 0; n != Nodes; ++n) {
133247738Sbapt    Sum += NewSize[n] = PerNode + (n < Extra);
134247738Sbapt    if (PosPair.first == Nodes && Sum > Position)
135247738Sbapt      PosPair = IdxPair(n, Position - (Sum - NewSize[n]));
136247738Sbapt  }
137247738Sbapt  assert(Sum == Elements + Grow && "Bad distribution sum");
138247738Sbapt
139247738Sbapt  // Subtract the Grow element that was added.
140247738Sbapt  if (Grow) {
141247738Sbapt    assert(PosPair.first < Nodes && "Bad algebra");
142247738Sbapt    assert(NewSize[PosPair.first] && "Too few elements to need Grow");
143247738Sbapt    --NewSize[PosPair.first];
144247738Sbapt  }
145247738Sbapt
146247738Sbapt#ifndef NDEBUG
147247738Sbapt  Sum = 0;
148247738Sbapt  for (unsigned n = 0; n != Nodes; ++n) {
149247738Sbapt    assert(NewSize[n] <= Capacity && "Overallocated node");
150247738Sbapt    Sum += NewSize[n];
151247738Sbapt  }
152247738Sbapt  assert(Sum == Elements && "Bad distribution sum");
153247738Sbapt#endif
154247738Sbapt
155247738Sbapt  return PosPair;
156247738Sbapt}
157247738Sbapt
158247738Sbapt} // namespace IntervalMapImpl
159247738Sbapt} // namespace llvm
160247738Sbapt
161247738Sbapt