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 {
operatorCompare52     bool operator ()(const_reference L, Int R) const {
53       return L.first < R;
54     }
operatorCompare55     bool operator ()(Int L, const_reference R) const {
56       return L < R.first;
57     }
operatorCompare58     bool operator ()(Int L, Int R) const {
59       return L < R;
60     }
operatorCompare61     bool operator ()(const_reference L, const_reference R) const {
62       return L.first < R.first;
63     }
64   };
65 
66 public:
insert(const value_type & Val)67   void insert(const value_type &Val) {
68     if (!Rep.empty() && Rep.back() == Val)
69       return;
70 
71     assert((Rep.empty() || Rep.back().first < Val.first) &&
72            "Must insert keys in order.");
73     Rep.push_back(Val);
74   }
75 
insertOrReplace(const value_type & Val)76   void insertOrReplace(const value_type &Val) {
77     iterator I = std::lower_bound(Rep.begin(), Rep.end(), Val, Compare());
78     if (I != Rep.end() && I->first == Val.first) {
79       I->second = Val.second;
80       return;
81     }
82 
83     Rep.insert(I, Val);
84   }
85 
86   using iterator = typename Representation::iterator;
87   using const_iterator = typename Representation::const_iterator;
88 
begin()89   iterator begin() { return Rep.begin(); }
end()90   iterator end() { return Rep.end(); }
begin()91   const_iterator begin() const { return Rep.begin(); }
end()92   const_iterator end() const { return Rep.end(); }
93 
find(Int K)94   iterator find(Int K) {
95     iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare());
96     // I points to the first entry with a key > K, which is the range that
97     // follows the one containing K.
98     if (I == Rep.begin())
99       return Rep.end();
100     --I;
101     return I;
102   }
find(Int K)103   const_iterator find(Int K) const {
104     return const_cast<ContinuousRangeMap*>(this)->find(K);
105   }
106 
back()107   reference back() { return Rep.back(); }
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:
Builder(ContinuousRangeMap & Self)116     explicit Builder(ContinuousRangeMap &Self) : Self(Self) {}
117     Builder(const Builder&) = delete;
118     Builder &operator=(const Builder&) = delete;
119 
~Builder()120     ~Builder() {
121       llvm::sort(Self.Rep, Compare());
122       std::unique(Self.Rep.begin(), Self.Rep.end(),
123                   [](const_reference A, const_reference B) {
124         // FIXME: we should not allow any duplicate keys, but there are a lot of
125         // duplicate 0 -> 0 mappings to remove first.
126         assert((A == B || A.first != B.first) &&
127                "ContinuousRangeMap::Builder given non-unique keys");
128         return A == B;
129       });
130     }
131 
insert(const value_type & Val)132     void insert(const value_type &Val) {
133       Self.Rep.push_back(Val);
134     }
135   };
136 
137   friend class Builder;
138 };
139 
140 } // namespace clang
141 
142 #endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
143