1 //===- ContinuousRangeMap.h - Map with int range as key ---------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines the ContinuousRangeMap class, which is a highly
10 // specialized container used by serialization.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
15 #define LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
17 #include "clang/Basic/LLVM.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallVector.h"
26 /// A map from continuous integer ranges to some value, with a very
27 /// specialized interface.
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.
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 {
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 *;
46 using Representation = SmallVector<value_type, InitialCapacity>;
51 bool operator ()(const_reference L, Int R) const {
54 bool operator ()(Int L, const_reference R) const {
57 bool operator ()(Int L, Int R) const {
60 bool operator ()(const_reference L, const_reference R) const {
61 return L.first < R.first;
66 void insert(const value_type &Val) {
67 if (!Rep.empty() && Rep.back() == Val)
70 assert((Rep.empty() || Rep.back().first < Val.first) &&
71 "Must insert keys in order.");
75 void insertOrReplace(const value_type &Val) {
76 iterator I = llvm::lower_bound(Rep, Val, Compare());
77 if (I != Rep.end() && I->first == Val.first) {
78 I->second = Val.second;
85 using iterator = typename Representation::iterator;
86 using const_iterator = typename Representation::const_iterator;
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(); }
93 iterator find(Int K) {
94 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.
102 const_iterator find(Int K) const {
103 return const_cast<ContinuousRangeMap*>(this)->find(K);
106 reference back() { return Rep.back(); }
107 const_reference back() const { return Rep.back(); }
109 /// An object that helps properly build a continuous range map
110 /// from a set of values.
112 ContinuousRangeMap &Self;
115 explicit Builder(ContinuousRangeMap &Self) : Self(Self) {}
116 Builder(const Builder&) = delete;
117 Builder &operator=(const Builder&) = delete;
120 llvm::sort(Self.Rep, Compare());
121 std::unique(Self.Rep.begin(), Self.Rep.end(),
122 [](const_reference A, const_reference B) {
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");
131 void insert(const value_type &Val) {
132 Self.Rep.push_back(Val);
136 friend class Builder;
141 #endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H