/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 | 1.04G | bool operator ()(Int L, const_reference R) const { |
55 | 1.04G | return L < R.first; |
56 | 1.04G | } clang::ContinuousRangeMap<unsigned int, int, 2u>::Compare::operator()(unsigned int, std::__1::pair<unsigned int, int> const&) const Line | Count | Source | 54 | 952M | bool operator ()(Int L, const_reference R) const { | 55 | 952M | return L < R.first; | 56 | 952M | } |
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 | 41.1M | bool operator ()(Int L, const_reference R) const { | 55 | 41.1M | return L < R.first; | 56 | 41.1M | } |
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 | 52.6M | bool operator ()(Int L, const_reference R) const { | 55 | 52.6M | return L < R.first; | 56 | 52.6M | } |
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 | 1.01M | bool operator ()(Int L, const_reference R) const { | 55 | 1.01M | return L < R.first; | 56 | 1.01M | } |
|
57 | | bool operator ()(Int L, Int R) const { |
58 | | return L < R; |
59 | | } |
60 | 1.11M | bool operator ()(const_reference L, const_reference R) const { |
61 | 1.11M | return L.first < R.first; |
62 | 1.11M | } |
63 | | }; |
64 | | |
65 | | public: |
66 | 150k | void insert(const value_type &Val) { |
67 | 150k | if (!Rep.empty() && Rep.back() == Val89.7k ) |
68 | 0 | return; |
69 | | |
70 | 150k | assert((Rep.empty() || Rep.back().first < Val.first) && |
71 | 150k | "Must insert keys in order."); |
72 | 0 | Rep.push_back(Val); |
73 | 150k | } clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::insert(std::__1::pair<unsigned int, clang::serialization::ModuleFile*> const&) Line | Count | Source | 66 | 85.5k | void insert(const value_type &Val) { | 67 | 85.5k | if (!Rep.empty() && Rep.back() == Val52.1k ) | 68 | 0 | return; | 69 | | | 70 | 85.5k | assert((Rep.empty() || Rep.back().first < Val.first) && | 71 | 85.5k | "Must insert keys in order."); | 72 | 0 | Rep.push_back(Val); | 73 | 85.5k | } |
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 64u>::insert(std::__1::pair<unsigned int, clang::serialization::ModuleFile*> const&) Line | Count | Source | 66 | 37.0k | void insert(const value_type &Val) { | 67 | 37.0k | if (!Rep.empty() && Rep.back() == Val22.1k ) | 68 | 0 | return; | 69 | | | 70 | 37.0k | assert((Rep.empty() || Rep.back().first < Val.first) && | 71 | 37.0k | "Must insert keys in order."); | 72 | 0 | Rep.push_back(Val); | 73 | 37.0k | } |
clang::ContinuousRangeMap<unsigned int, int, 2u>::insert(std::__1::pair<unsigned int, int> const&) Line | Count | Source | 66 | 8.89k | void insert(const value_type &Val) { | 67 | 8.89k | if (!Rep.empty() && Rep.back() == Val4.44k ) | 68 | 0 | return; | 69 | | | 70 | 8.89k | assert((Rep.empty() || Rep.back().first < Val.first) && | 71 | 8.89k | "Must insert keys in order."); | 72 | 0 | Rep.push_back(Val); | 73 | 8.89k | } |
clang::ContinuousRangeMap<unsigned long long, clang::serialization::ModuleFile*, 4u>::insert(std::__1::pair<unsigned long long, clang::serialization::ModuleFile*> const&) Line | Count | Source | 66 | 18.5k | void insert(const value_type &Val) { | 67 | 18.5k | if (!Rep.empty() && Rep.back() == Val11.0k ) | 68 | 0 | return; | 69 | | | 70 | 18.5k | assert((Rep.empty() || Rep.back().first < Val.first) && | 71 | 18.5k | "Must insert keys in order."); | 72 | 0 | Rep.push_back(Val); | 73 | 18.5k | } |
|
74 | | |
75 | 122k | void insertOrReplace(const value_type &Val) { |
76 | 122k | iterator I = llvm::lower_bound(Rep, Val, Compare()); |
77 | 122k | if (I != Rep.end() && I->first == Val.first8.89k ) { |
78 | 8.89k | I->second = Val.second; |
79 | 8.89k | return; |
80 | 8.89k | } |
81 | | |
82 | 113k | Rep.insert(I, Val); |
83 | 113k | } |
84 | | |
85 | | using iterator = typename Representation::iterator; |
86 | | using const_iterator = typename Representation::const_iterator; |
87 | | |
88 | | iterator begin() { return Rep.begin(); } |
89 | 326M | iterator end() { return Rep.end(); } clang::ContinuousRangeMap<unsigned int, int, 2u>::end() Line | Count | Source | 89 | 302M | iterator end() { return Rep.end(); } |
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::end() Line | Count | Source | 89 | 23.8M | iterator end() { return Rep.end(); } |
clang::ContinuousRangeMap<unsigned long long, clang::serialization::ModuleFile*, 4u>::end() Line | Count | Source | 89 | 513k | 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 | 496M | iterator find(Int K) { |
94 | 496M | iterator I = llvm::upper_bound(Rep, K, Compare()); |
95 | | // I points to the first entry with a key > K, which is the range that |
96 | | // follows the one containing K. |
97 | 496M | if (I == Rep.begin()) |
98 | 4.44k | return Rep.end(); |
99 | 496M | --I; |
100 | 496M | return I; |
101 | 496M | } clang::ContinuousRangeMap<unsigned int, int, 2u>::find(unsigned int) Line | Count | Source | 93 | 454M | iterator find(Int K) { | 94 | 454M | iterator I = llvm::upper_bound(Rep, K, Compare()); | 95 | | // I points to the first entry with a key > K, which is the range that | 96 | | // follows the one containing K. | 97 | 454M | if (I == Rep.begin()) | 98 | 4.44k | return Rep.end(); | 99 | 454M | --I; | 100 | 454M | return I; | 101 | 454M | } |
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 64u>::find(unsigned int) Line | Count | Source | 93 | 18.2M | iterator find(Int K) { | 94 | 18.2M | iterator I = llvm::upper_bound(Rep, K, Compare()); | 95 | | // I points to the first entry with a key > K, which is the range that | 96 | | // follows the one containing K. | 97 | 18.2M | if (I == Rep.begin()) | 98 | 0 | return Rep.end(); | 99 | 18.2M | --I; | 100 | 18.2M | return I; | 101 | 18.2M | } |
clang::ContinuousRangeMap<unsigned int, clang::serialization::ModuleFile*, 4u>::find(unsigned int) Line | Count | Source | 93 | 23.8M | iterator find(Int K) { | 94 | 23.8M | iterator I = llvm::upper_bound(Rep, K, Compare()); | 95 | | // I points to the first entry with a key > K, which is the range that | 96 | | // follows the one containing K. | 97 | 23.8M | if (I == Rep.begin()) | 98 | 0 | return Rep.end(); | 99 | 23.8M | --I; | 100 | 23.8M | return I; | 101 | 23.8M | } |
clang::ContinuousRangeMap<unsigned long long, clang::serialization::ModuleFile*, 4u>::find(unsigned long long) Line | Count | Source | 93 | 513k | iterator find(Int K) { | 94 | 513k | iterator I = llvm::upper_bound(Rep, K, Compare()); | 95 | | // I points to the first entry with a key > K, which is the range that | 96 | | // follows the one containing K. | 97 | 513k | if (I == Rep.begin()) | 98 | 0 | return Rep.end(); | 99 | 513k | --I; | 100 | 513k | return I; | 101 | 513k | } |
|
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 | 75.4k | explicit Builder(ContinuousRangeMap &Self) : Self(Self) {} |
116 | | Builder(const Builder&) = delete; |
117 | | Builder &operator=(const Builder&) = delete; |
118 | | |
119 | 75.4k | ~Builder() { |
120 | 75.4k | llvm::sort(Self.Rep, Compare()); |
121 | 75.4k | Self.Rep.erase( |
122 | 75.4k | std::unique( |
123 | 75.4k | Self.Rep.begin(), Self.Rep.end(), |
124 | 307k | [](const_reference A, const_reference B) { |
125 | | // FIXME: we should not allow any duplicate keys, but there are |
126 | | // a lot of duplicate 0 -> 0 mappings to remove first. |
127 | 307k | assert((A == B || A.first != B.first) && |
128 | 307k | "ContinuousRangeMap::Builder given non-unique keys"); |
129 | 0 | return A == B; |
130 | 307k | }), |
131 | 75.4k | Self.Rep.end()); |
132 | 75.4k | } |
133 | | |
134 | 314k | void insert(const value_type &Val) { |
135 | 314k | Self.Rep.push_back(Val); |
136 | 314k | } |
137 | | }; |
138 | | |
139 | | friend class Builder; |
140 | | }; |
141 | | |
142 | | } // namespace clang |
143 | | |
144 | | #endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H |