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