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