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 <utility>
22 
23 namespace clang {
24 
25 /// \brief A map from continuous integer ranges to some value, with a very
26 /// specialized interface.
27 ///
28 /// CRM maps from integer ranges to values. The ranges are continuous, i.e.
29 /// where one ends, the next one begins. So if the map contains the stops I0-3,
30 /// the first range is from I0 to I1, the second from I1 to I2, the third from
31 /// I2 to I3 and the last from I3 to infinity.
32 ///
33 /// Ranges must be inserted in order. Inserting a new stop I4 into the map will
34 /// shrink the fourth range to I3 to I4 and add the new range I4 to inf.
35 template <typename Int, typename V, unsigned InitialCapacity>
36 class ContinuousRangeMap {
37 public:
38   typedef std::pair<Int, V> value_type;
39   typedef value_type &reference;
40   typedef const value_type &const_reference;
41   typedef value_type *pointer;
42   typedef const value_type *const_pointer;
43 
44 private:
45   typedef SmallVector<value_type, InitialCapacity> Representation;
46   Representation Rep;
47 
48   struct Compare {
operatorCompare49     bool operator ()(const_reference L, Int R) const {
50       return L.first < R;
51     }
operatorCompare52     bool operator ()(Int L, const_reference R) const {
53       return L < R.first;
54     }
operatorCompare55     bool operator ()(Int L, Int R) const {
56       return L < R;
57     }
operatorCompare58     bool operator ()(const_reference L, const_reference R) const {
59       return L.first < R.first;
60     }
61   };
62 
63 public:
insert(const value_type & Val)64   void insert(const value_type &Val) {
65     if (!Rep.empty() && Rep.back() == Val)
66       return;
67 
68     assert((Rep.empty() || Rep.back().first < Val.first) &&
69            "Must insert keys in order.");
70     Rep.push_back(Val);
71   }
72 
insertOrReplace(const value_type & Val)73   void insertOrReplace(const value_type &Val) {
74     iterator I = std::lower_bound(Rep.begin(), Rep.end(), Val, Compare());
75     if (I != Rep.end() && I->first == Val.first) {
76       I->second = Val.second;
77       return;
78     }
79 
80     Rep.insert(I, Val);
81   }
82 
83   typedef typename Representation::iterator iterator;
84   typedef typename Representation::const_iterator const_iterator;
85 
begin()86   iterator begin() { return Rep.begin(); }
end()87   iterator end() { return Rep.end(); }
begin()88   const_iterator begin() const { return Rep.begin(); }
end()89   const_iterator end() const { return Rep.end(); }
90 
find(Int K)91   iterator find(Int K) {
92     iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare());
93     // I points to the first entry with a key > K, which is the range that
94     // follows the one containing K.
95     if (I == Rep.begin())
96       return Rep.end();
97     --I;
98     return I;
99   }
find(Int K)100   const_iterator find(Int K) const {
101     return const_cast<ContinuousRangeMap*>(this)->find(K);
102   }
103 
back()104   reference back() { return Rep.back(); }
back()105   const_reference back() const { return Rep.back(); }
106 
107   /// \brief An object that helps properly build a continuous range map
108   /// from a set of values.
109   class Builder {
110     ContinuousRangeMap &Self;
111 
112     Builder(const Builder&) = delete;
113     Builder &operator=(const Builder&) = delete;
114 
115   public:
Builder(ContinuousRangeMap & Self)116     explicit Builder(ContinuousRangeMap &Self) : Self(Self) { }
117 
~Builder()118     ~Builder() {
119       std::sort(Self.Rep.begin(), Self.Rep.end(), Compare());
120       std::unique(Self.Rep.begin(), Self.Rep.end(),
121                   [](const_reference A, const_reference B) {
122         // FIXME: we should not allow any duplicate keys, but there are a lot of
123         // duplicate 0 -> 0 mappings to remove first.
124         assert((A == B || A.first != B.first) &&
125                "ContinuousRangeMap::Builder given non-unique keys");
126         return A == B;
127       });
128     }
129 
insert(const value_type & Val)130     void insert(const value_type &Val) {
131       Self.Rep.push_back(Val);
132     }
133   };
134   friend class Builder;
135 };
136 
137 }
138 
139 #endif
140