Coverage Report

Created: 2018-09-25 23:22

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