clang  6.0.0svn
ContinuousRangeMap.h
Go to the documentation of this file.
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/SmallVector.h"
20 #include <algorithm>
21 #include <cassert>
22 #include <utility>
23 
24 namespace clang {
25 
26 /// \brief 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>
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:
47 
48  Representation Rep;
49 
50  struct Compare {
51  bool operator ()(const_reference L, Int R) const {
52  return L.first < R;
53  }
54  bool operator ()(Int L, const_reference R) const {
55  return L < R.first;
56  }
57  bool operator ()(Int L, Int R) const {
58  return L < R;
59  }
60  bool operator ()(const_reference L, const_reference R) const {
61  return L.first < R.first;
62  }
63  };
64 
65 public:
66  void insert(const value_type &Val) {
67  if (!Rep.empty() && Rep.back() == Val)
68  return;
69 
70  assert((Rep.empty() || Rep.back().first < Val.first) &&
71  "Must insert keys in order.");
72  Rep.push_back(Val);
73  }
74 
75  void insertOrReplace(const value_type &Val) {
76  iterator I = std::lower_bound(Rep.begin(), Rep.end(), Val, Compare());
77  if (I != Rep.end() && I->first == Val.first) {
78  I->second = Val.second;
79  return;
80  }
81 
82  Rep.insert(I, Val);
83  }
84 
85  using iterator = typename Representation::iterator;
86  using const_iterator = typename Representation::const_iterator;
87 
88  iterator begin() { return Rep.begin(); }
89  iterator end() { return Rep.end(); }
90  const_iterator begin() const { return Rep.begin(); }
91  const_iterator end() const { return Rep.end(); }
92 
93  iterator find(Int K) {
94  iterator I = std::upper_bound(Rep.begin(), Rep.end(), 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  if (I == Rep.begin())
98  return Rep.end();
99  --I;
100  return I;
101  }
102  const_iterator find(Int K) const {
103  return const_cast<ContinuousRangeMap*>(this)->find(K);
104  }
105 
106  reference back() { return Rep.back(); }
107  const_reference back() const { return Rep.back(); }
108 
109  /// \brief 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  explicit Builder(ContinuousRangeMap &Self) : Self(Self) {}
116  Builder(const Builder&) = delete;
117  Builder &operator=(const Builder&) = delete;
118 
120  std::sort(Self.Rep.begin(), Self.Rep.end(), Compare());
121  std::unique(Self.Rep.begin(), Self.Rep.end(),
123  // FIXME: we should not allow any duplicate keys, but there are a lot of
124  // duplicate 0 -> 0 mappings to remove first.
125  assert((A == B || A.first != B.first) &&
126  "ContinuousRangeMap::Builder given non-unique keys");
127  return A == B;
128  });
129  }
130 
131  void insert(const value_type &Val) {
132  Self.Rep.push_back(Val);
133  }
134  };
135 
136  friend class Builder;
137 };
138 
139 } // namespace clang
140 
141 #endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
void insert(const value_type &Val)
const_iterator begin() const
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
const_reference back() const
void insertOrReplace(const value_type &Val)
Builder(ContinuousRangeMap &Self)
std::pair< serialization::IdentID, ModuleFile * > value_type
An object that helps properly build a continuous range map from a set of values.
Dataflow Directional Tag Classes.
A map from continuous integer ranges to some value, with a very specialized interface.
const_iterator end() const
const_iterator find(Int K) const
void insert(const value_type &Val)