Coverage Report

Created: 2018-07-21 08:31

/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.01M
    bool operator ()(Int L, const_reference R) const {
56
5.01M
      return L < R.first;
57
5.01M
    }
clang::ContinuousRangeMap<unsigned int, int, 2u>::Compare::operator()(unsigned int, std::__1::pair<unsigned int, int> const&) const
Line
Count
Source
55
4.33M
    bool operator ()(Int L, const_reference R) const {
56
4.33M
      return L < R.first;
57
4.33M
    }
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.5k
    bool operator ()(Int L, const_reference R) const {
56
20.5k
      return L < R.first;
57
20.5k
    }
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
649k
    bool operator ()(Int L, const_reference R) const {
56
649k
      return L < R.first;
57
649k
    }
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.5k
    bool operator ()(Int L, const_reference R) const {
56
10.5k
      return L < R.first;
57
10.5k
    }
58
    bool operator ()(Int L, Int R) const {
59
      return L < R;
60
    }
61
282k
    bool operator ()(const_reference L, const_reference R) const {
62
282k
      return L.first < R.first;
63
282k
    }
64
  };
65
66
public:
67
43.7k
  void insert(const value_type &Val) {
68
43.7k
    if (!Rep.empty() && 
Rep.back() == Val14.4k
)
69
0
      return;
70
43.7k
71
43.7k
    assert((Rep.empty() || Rep.back().first < Val.first) &&
72
43.7k
           "Must insert keys in order.");
73
43.7k
    Rep.push_back(Val);
74
43.7k
  }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::insert(std::__1::pair<unsigned int, clang::serialization::ModuleFile*> const&)
Line
Count
Source
67
24.2k
  void insert(const value_type &Val) {
68
24.2k
    if (!Rep.empty() && 
Rep.back() == Val7.46k
)
69
0
      return;
70
24.2k
71
24.2k
    assert((Rep.empty() || Rep.back().first < Val.first) &&
72
24.2k
           "Must insert keys in order.");
73
24.2k
    Rep.push_back(Val);
74
24.2k
  }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 64u>::insert(std::__1::pair<unsigned int, clang::serialization::ModuleFile*> const&)
Line
Count
Source
67
11.8k
  void insert(const value_type &Val) {
68
11.8k
    if (!Rep.empty() && 
Rep.back() == Val4.08k
)
69
0
      return;
70
11.8k
71
11.8k
    assert((Rep.empty() || Rep.back().first < Val.first) &&
72
11.8k
           "Must insert keys in order.");
73
11.8k
    Rep.push_back(Val);
74
11.8k
  }
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() == Val865
)
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.90k
  void insert(const value_type &Val) {
68
5.90k
    if (!Rep.empty() && 
Rep.back() == Val2.04k
)
69
0
      return;
70
5.90k
71
5.90k
    assert((Rep.empty() || Rep.back().first < Val.first) &&
72
5.90k
           "Must insert keys in order.");
73
5.90k
    Rep.push_back(Val);
74
5.90k
  }
75
  
76
35.9k
  void insertOrReplace(const value_type &Val) {
77
35.9k
    iterator I = std::lower_bound(Rep.begin(), Rep.end(), Val, Compare());
78
35.9k
    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.2k
    
83
34.2k
    Rep.insert(I, Val);
84
34.2k
  }
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.45M
  iterator find(Int K) {
95
4.45M
    iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare());
96
4.45M
    // I points to the first entry with a key > K, which is the range that
97
4.45M
    // follows the one containing K.
98
4.45M
    if (I == Rep.begin())
99
865
      return Rep.end();
100
4.45M
    --I;
101
4.45M
    return I;
102
4.45M
  }
clang::ContinuousRangeMap<unsigned int, int, 2u>::find(unsigned int)
Line
Count
Source
94
3.84M
  iterator find(Int K) {
95
3.84M
    iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare());
96
3.84M
    // I points to the first entry with a key > K, which is the range that
97
3.84M
    // follows the one containing K.
98
3.84M
    if (I == Rep.begin())
99
865
      return Rep.end();
100
3.84M
    --I;
101
3.84M
    return I;
102
3.84M
  }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 64u>::find(unsigned int)
Line
Count
Source
94
13.5k
  iterator find(Int K) {
95
13.5k
    iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare());
96
13.5k
    // I points to the first entry with a key > K, which is the range that
97
13.5k
    // follows the one containing K.
98
13.5k
    if (I == Rep.begin())
99
0
      return Rep.end();
100
13.5k
    --I;
101
13.5k
    return I;
102
13.5k
  }
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::find(unsigned int)
Line
Count
Source
94
579k
  iterator find(Int K) {
95
579k
    iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare());
96
579k
    // I points to the first entry with a key > K, which is the range that
97
579k
    // follows the one containing K.
98
579k
    if (I == Rep.begin())
99
0
      return Rep.end();
100
579k
    --I;
101
579k
    return I;
102
579k
  }
clang::ContinuousRangeMap<unsigned long long, clang::serialization::ModuleFile*, 4u>::find(unsigned long long)
Line
Count
Source
94
9.84k
  iterator find(Int K) {
95
9.84k
    iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare());
96
9.84k
    // I points to the first entry with a key > K, which is the range that
97
9.84k
    // follows the one containing K.
98
9.84k
    if (I == Rep.begin())
99
0
      return Rep.end();
100
9.84k
    --I;
101
9.84k
    return I;
102
9.84k
  }
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.0k
    explicit Builder(ContinuousRangeMap &Self) : Self(Self) {}
117
    Builder(const Builder&) = delete;
118
    Builder &operator=(const Builder&) = delete;
119
    
120
14.0k
    ~Builder() {
121
14.0k
      llvm::sort(Self.Rep.begin(), Self.Rep.end(), Compare());
122
14.0k
      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.0k
    }
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