Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Support/IntervalMap.cpp
Line
Count
Source (jump to first uncovered line)
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
317k
void Path::replaceRoot(void *Root, unsigned Size, IdxPair Offsets) {
19
317k
  assert(!path.empty() && "Can't replace missing root");
20
317k
  path.front() = Entry(Root, Size, Offsets.first);
21
317k
  path.insert(path.begin() + 1, Entry(subtree(0), Offsets.second));
22
317k
}
23
24
1.63M
NodeRef Path::getLeftSibling(unsigned Level) const {
25
1.63M
  // The root has no siblings.
26
1.63M
  if (Level == 0)
27
0
    return NodeRef();
28
1.63M
29
1.63M
  // Go up the tree until we can go left.
30
1.63M
  unsigned l = Level - 1;
31
1.66M
  while (l && 
path[l].offset == 0354k
)
32
27.4k
    --l;
33
1.63M
34
1.63M
  // We can't go left.
35
1.63M
  if (path[l].offset == 0)
36
288k
    return NodeRef();
37
1.34M
38
1.34M
  // NR is the subtree containing our left sibling.
39
1.34M
  NodeRef NR = path[l].subtree(path[l].offset - 1);
40
1.34M
41
1.34M
  // Keep right all the way down.
42
1.36M
  for (++l; l != Level; 
++l15.2k
)
43
15.2k
    NR = NR.subtree(NR.size() - 1);
44
1.34M
  return NR;
45
1.34M
}
46
47
3.33M
void Path::moveLeft(unsigned Level) {
48
3.33M
  assert(Level != 0 && "Cannot move the root node");
49
3.33M
50
3.33M
  // Go up the tree until we can go left.
51
3.33M
  unsigned l = 0;
52
3.33M
  if (valid()) {
53
2.18M
    l = Level - 1;
54
2.21M
    while (path[l].offset == 0) {
55
29.1k
      assert(l != 0 && "Cannot move beyond begin()");
56
29.1k
      --l;
57
29.1k
    }
58
2.18M
  } else 
if (1.15M
height() < Level1.15M
)
59
1.15M
    // end() may have created a height=0 path.
60
1.15M
    path.resize(Level + 1, Entry(nullptr, 0, 0));
61
3.33M
62
3.33M
  // NR is the subtree containing our left sibling.
63
3.33M
  --path[l].offset;
64
3.33M
  NodeRef NR = subtree(l);
65
3.33M
66
3.33M
  // Get the rightmost node in the subtree.
67
3.59M
  for (++l; l != Level; 
++l252k
) {
68
252k
    path[l] = Entry(NR, NR.size() - 1);
69
252k
    NR = NR.subtree(NR.size() - 1);
70
252k
  }
71
3.33M
  path[l] = Entry(NR, NR.size() - 1);
72
3.33M
}
73
74
1.24M
NodeRef Path::getRightSibling(unsigned Level) const {
75
1.24M
  // The root has no siblings.
76
1.24M
  if (Level == 0)
77
0
    return NodeRef();
78
1.24M
79
1.24M
  // Go up the tree until we can go right.
80
1.24M
  unsigned l = Level - 1;
81
1.36M
  while (l && 
atLastEntry(l)303k
)
82
119k
    --l;
83
1.24M
84
1.24M
  // We can't go right.
85
1.24M
  if (atLastEntry(l))
86
675k
    return NodeRef();
87
567k
88
567k
  // NR is the subtree containing our right sibling.
89
567k
  NodeRef NR = path[l].subtree(path[l].offset + 1);
90
567k
91
567k
  // Keep left all the way down.
92
576k
  for (++l; l != Level; 
++l9.79k
)
93
9.79k
    NR = NR.subtree(0);
94
567k
  return NR;
95
567k
}
96
97
8.18M
void Path::moveRight(unsigned Level) {
98
8.18M
  assert(Level != 0 && "Cannot move the root node");
99
8.18M
100
8.18M
  // Go up the tree until we can go right.
101
8.18M
  unsigned l = Level - 1;
102
8.50M
  while (l && 
atLastEntry(l)3.56M
)
103
325k
    --l;
104
8.18M
105
8.18M
  // NR is the subtree containing our right sibling. If we hit end(), we have
106
8.18M
  // offset(0) == node(0).size().
107
8.18M
  if (++path[l].offset == path[l].size)
108
1.85M
    return;
109
6.33M
  NodeRef NR = subtree(l);
110
6.33M
111
6.60M
  for (++l; l != Level; 
++l270k
) {
112
270k
    path[l] = Entry(NR, 0);
113
270k
    NR = NR.subtree(0);
114
270k
  }
115
6.33M
  path[l] = Entry(NR, 0);
116
6.33M
}
117
118
119
IdxPair distribute(unsigned Nodes, unsigned Elements, unsigned Capacity,
120
                   const unsigned *CurSize, unsigned NewSize[],
121
1.55M
                   unsigned Position, bool Grow) {
122
1.55M
  assert(Elements + Grow <= Nodes * Capacity && "Not enough room for elements");
123
1.55M
  assert(Position <= Elements && "Invalid position");
124
1.55M
  if (!Nodes)
125
0
    return IdxPair();
126
1.55M
127
1.55M
  // Trivial algorithm: left-leaning even distribution.
128
1.55M
  const unsigned PerNode = (Elements + Grow) / Nodes;
129
1.55M
  const unsigned Extra = (Elements + Grow) % Nodes;
130
1.55M
  IdxPair PosPair = IdxPair(Nodes, 0);
131
1.55M
  unsigned Sum = 0;
132
5.45M
  for (unsigned n = 0; n != Nodes; 
++n3.89M
) {
133
3.89M
    Sum += NewSize[n] = PerNode + (n < Extra);
134
3.89M
    if (PosPair.first == Nodes && 
Sum > Position3.13M
)
135
1.55M
      PosPair = IdxPair(n, Position - (Sum - NewSize[n]));
136
3.89M
  }
137
1.55M
  assert(Sum == Elements + Grow && "Bad distribution sum");
138
1.55M
139
1.55M
  // Subtract the Grow element that was added.
140
1.55M
  if (Grow) {
141
1.55M
    assert(PosPair.first < Nodes && "Bad algebra");
142
1.55M
    assert(NewSize[PosPair.first] && "Too few elements to need Grow");
143
1.55M
    --NewSize[PosPair.first];
144
1.55M
  }
145
1.55M
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
1.55M
  return PosPair;
156
1.55M
}
157
158
} // namespace IntervalMapImpl
159
} // namespace llvm
160