Coverage Report

Created: 2020-02-25 14:32

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Serialization/ContinuousRangeMap.h
Line
Count
Source (jump to first uncovered line)
1
//===- ContinuousRangeMap.h - Map with int range as key ---------*- C++ -*-===//
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 defines the ContinuousRangeMap class, which is a highly
10
//  specialized container used by serialization.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
15
#define LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
16
17
#include "clang/Basic/LLVM.h"
18
#include "llvm/ADT/STLExtras.h"
19
#include "llvm/ADT/SmallVector.h"
20
#include <algorithm>
21
#include <cassert>
22
#include <utility>
23
24
namespace clang {
25
26
/// A map from continuous integer ranges to some value, with a very
27
/// specialized interface.
28
///
29
/// CRM maps from integer ranges to values. The ranges are continuous, i.e.
30
/// where one ends, the next one begins. So if the map contains the stops I0-3,
31
/// the first range is from I0 to I1, the second from I1 to I2, the third from
32
/// I2 to I3 and the last from I3 to infinity.
33
///
34
/// Ranges must be inserted in order. Inserting a new stop I4 into the map will
35
/// shrink the fourth range to I3 to I4 and add the new range I4 to inf.
36
template <typename Int, typename V, unsigned InitialCapacity>
37
class ContinuousRangeMap {
38
public:
39
  using value_type = std::pair<Int, V>;
40
  using reference = value_type &;
41
  using const_reference = const value_type &;
42
  using pointer = value_type *;
43
  using const_pointer = const value_type *;
44
45
private:
46
  using Representation = SmallVector<value_type, InitialCapacity>;
47
48
  Representation Rep;
49
50
  struct Compare {
51
    bool operator ()(const_reference L, Int R) const {
52
      return L.first < R;
53
    }
54
430M
    bool operator ()(Int L, const_reference R) const {
55
430M
      return L < R.first;
56
430M
    }
clang::ContinuousRangeMap<unsigned int, int, 2u>::Compare::operator()(unsigned int, std::__1::pair<unsigned int, int> const&) const
Line
Count
Source
54
390M
    bool operator ()(Int L, const_reference R) const {
55
390M
      return L < R.first;
56
390M
    }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 64u>::Compare::operator()(unsigned int, std::__1::pair<unsigned int, clang::serialization::ModuleFile*> const&) const
Line
Count
Source
54
8.63M
    bool operator ()(Int L, const_reference R) const {
55
8.63M
      return L < R.first;
56
8.63M
    }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::Compare::operator()(unsigned int, std::__1::pair<unsigned int, clang::serialization::ModuleFile*> const&) const
Line
Count
Source
54
30.8M
    bool operator ()(Int L, const_reference R) const {
55
30.8M
      return L < R.first;
56
30.8M
    }
clang::ContinuousRangeMap<unsigned long long, clang::serialization::ModuleFile*, 4u>::Compare::operator()(unsigned long long, std::__1::pair<unsigned long long, clang::serialization::ModuleFile*> const&) const
Line
Count
Source
54
71.0k
    bool operator ()(Int L, const_reference R) const {
55
71.0k
      return L < R.first;
56
71.0k
    }
57
    bool operator ()(Int L, Int R) const {
58
      return L < R;
59
    }
60
1.65M
    bool operator ()(const_reference L, const_reference R) const {
61
1.65M
      return L.first < R.first;
62
1.65M
    }
63
  };
64
65
public:
66
167k
  void insert(const value_type &Val) {
67
167k
    if (!Rep.empty() && 
Rep.back() == Val114k
)
68
0
      return;
69
167k
70
167k
    assert((Rep.empty() || Rep.back().first < Val.first) &&
71
167k
           "Must insert keys in order.");
72
167k
    Rep.push_back(Val);
73
167k
  }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::insert(std::__1::pair<unsigned int, clang::serialization::ModuleFile*> const&)
Line
Count
Source
66
96.6k
  void insert(const value_type &Val) {
67
96.6k
    if (!Rep.empty() && 
Rep.back() == Val67.1k
)
68
0
      return;
69
96.6k
70
96.6k
    assert((Rep.empty() || Rep.back().first < Val.first) &&
71
96.6k
           "Must insert keys in order.");
72
96.6k
    Rep.push_back(Val);
73
96.6k
  }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 64u>::insert(std::__1::pair<unsigned int, clang::serialization::ModuleFile*> const&)
Line
Count
Source
66
40.7k
  void insert(const value_type &Val) {
67
40.7k
    if (!Rep.empty() && 
Rep.back() == Val27.8k
)
68
0
      return;
69
40.7k
70
40.7k
    assert((Rep.empty() || Rep.back().first < Val.first) &&
71
40.7k
           "Must insert keys in order.");
72
40.7k
    Rep.push_back(Val);
73
40.7k
  }
clang::ContinuousRangeMap<unsigned int, int, 2u>::insert(std::__1::pair<unsigned int, int> const&)
Line
Count
Source
66
10.3k
  void insert(const value_type &Val) {
67
10.3k
    if (!Rep.empty() && 
Rep.back() == Val5.15k
)
68
0
      return;
69
10.3k
70
10.3k
    assert((Rep.empty() || Rep.back().first < Val.first) &&
71
10.3k
           "Must insert keys in order.");
72
10.3k
    Rep.push_back(Val);
73
10.3k
  }
clang::ContinuousRangeMap<unsigned long long, clang::serialization::ModuleFile*, 4u>::insert(std::__1::pair<unsigned long long, clang::serialization::ModuleFile*> const&)
Line
Count
Source
66
20.3k
  void insert(const value_type &Val) {
67
20.3k
    if (!Rep.empty() && 
Rep.back() == Val13.9k
)
68
0
      return;
69
20.3k
70
20.3k
    assert((Rep.empty() || Rep.back().first < Val.first) &&
71
20.3k
           "Must insert keys in order.");
72
20.3k
    Rep.push_back(Val);
73
20.3k
  }
74
75
137k
  void insertOrReplace(const value_type &Val) {
76
137k
    iterator I = llvm::lower_bound(Rep, Val, Compare());
77
137k
    if (I != Rep.end() && 
I->first == Val.first10.3k
) {
78
10.3k
      I->second = Val.second;
79
10.3k
      return;
80
10.3k
    }
81
126k
82
126k
    Rep.insert(I, Val);
83
126k
  }
84
85
  using iterator = typename Representation::iterator;
86
  using const_iterator = typename Representation::const_iterator;
87
88
  iterator begin() { return Rep.begin(); }
89
145M
  iterator end() { return Rep.end(); }
clang::ContinuousRangeMap<unsigned int, int, 2u>::end()
Line
Count
Source
89
132M
  iterator end() { return Rep.end(); }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::end()
Line
Count
Source
89
13.1M
  iterator end() { return Rep.end(); }
clang::ContinuousRangeMap<unsigned long long, clang::serialization::ModuleFile*, 4u>::end()
Line
Count
Source
89
40.9k
  iterator end() { return Rep.end(); }
90
103
  const_iterator begin() const { return Rep.begin(); }
clang::ContinuousRangeMap<unsigned long long, clang::serialization::ModuleFile*, 4u>::begin() const
Line
Count
Source
90
6
  const_iterator begin() const { return Rep.begin(); }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 64u>::begin() const
Line
Count
Source
90
6
  const_iterator begin() const { return Rep.begin(); }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::begin() const
Line
Count
Source
90
35
  const_iterator begin() const { return Rep.begin(); }
clang::ContinuousRangeMap<unsigned int, int, 2u>::begin() const
Line
Count
Source
90
56
  const_iterator begin() const { return Rep.begin(); }
91
2.23k
  const_iterator end() const { return Rep.end(); }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 64u>::end() const
Line
Count
Source
91
2.13k
  const_iterator end() const { return Rep.end(); }
clang::ContinuousRangeMap<unsigned long long, clang::serialization::ModuleFile*, 4u>::end() const
Line
Count
Source
91
6
  const_iterator end() const { return Rep.end(); }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::end() const
Line
Count
Source
91
35
  const_iterator end() const { return Rep.end(); }
clang::ContinuousRangeMap<unsigned int, int, 2u>::end() const
Line
Count
Source
91
56
  const_iterator end() const { return Rep.end(); }
92
93
197M
  iterator find(Int K) {
94
197M
    iterator I = llvm::upper_bound(Rep, K, Compare());
95
197M
    // I points to the first entry with a key > K, which is the range that
96
197M
    // follows the one containing K.
97
197M
    if (I == Rep.begin())
98
5.15k
      return Rep.end();
99
197M
    --I;
100
197M
    return I;
101
197M
  }
clang::ContinuousRangeMap<unsigned int, int, 2u>::find(unsigned int)
Line
Count
Source
93
181M
  iterator find(Int K) {
94
181M
    iterator I = llvm::upper_bound(Rep, K, Compare());
95
181M
    // I points to the first entry with a key > K, which is the range that
96
181M
    // follows the one containing K.
97
181M
    if (I == Rep.begin())
98
5.15k
      return Rep.end();
99
181M
    --I;
100
181M
    return I;
101
181M
  }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 64u>::find(unsigned int)
Line
Count
Source
93
2.43M
  iterator find(Int K) {
94
2.43M
    iterator I = llvm::upper_bound(Rep, K, Compare());
95
2.43M
    // I points to the first entry with a key > K, which is the range that
96
2.43M
    // follows the one containing K.
97
2.43M
    if (I == Rep.begin())
98
0
      return Rep.end();
99
2.43M
    --I;
100
2.43M
    return I;
101
2.43M
  }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::find(unsigned int)
Line
Count
Source
93
13.1M
  iterator find(Int K) {
94
13.1M
    iterator I = llvm::upper_bound(Rep, K, Compare());
95
13.1M
    // I points to the first entry with a key > K, which is the range that
96
13.1M
    // follows the one containing K.
97
13.1M
    if (I == Rep.begin())
98
0
      return Rep.end();
99
13.1M
    --I;
100
13.1M
    return I;
101
13.1M
  }
clang::ContinuousRangeMap<unsigned long long, clang::serialization::ModuleFile*, 4u>::find(unsigned long long)
Line
Count
Source
93
40.9k
  iterator find(Int K) {
94
40.9k
    iterator I = llvm::upper_bound(Rep, K, Compare());
95
40.9k
    // I points to the first entry with a key > K, which is the range that
96
40.9k
    // follows the one containing K.
97
40.9k
    if (I == Rep.begin())
98
0
      return Rep.end();
99
40.9k
    --I;
100
40.9k
    return I;
101
40.9k
  }
102
1.67k
  const_iterator find(Int K) const {
103
1.67k
    return const_cast<ContinuousRangeMap*>(this)->find(K);
104
1.67k
  }
105
106
  reference back() { return Rep.back(); }
107
  const_reference back() const { return Rep.back(); }
108
109
  /// An object that helps properly build a continuous range map
110
  /// from a set of values.
111
  class Builder {
112
    ContinuousRangeMap &Self;
113
114
  public:
115
99.1k
    explicit Builder(ContinuousRangeMap &Self) : Self(Self) {}
116
    Builder(const Builder&) = delete;
117
    Builder &operator=(const Builder&) = delete;
118
119
99.1k
    ~Builder() {
120
99.1k
      llvm::sort(Self.Rep, Compare());
121
99.1k
      Self.Rep.erase(
122
99.1k
          std::unique(
123
99.1k
              Self.Rep.begin(), Self.Rep.end(),
124
457k
              [](const_reference A, const_reference B) {
125
457k
                // FIXME: we should not allow any duplicate keys, but there are
126
457k
                // a lot of duplicate 0 -> 0 mappings to remove first.
127
457k
                assert((A == B || A.first != B.first) &&
128
457k
                       "ContinuousRangeMap::Builder given non-unique keys");
129
457k
                return A == B;
130
457k
              }),
131
99.1k
          Self.Rep.end());
132
99.1k
    }
133
134
466k
    void insert(const value_type &Val) {
135
466k
      Self.Rep.push_back(Val);
136
466k
    }
137
  };
138
139
  friend class Builder;
140
};
141
142
} // namespace clang
143
144
#endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H