1 //===- ContinuousRangeMap.h - Map with int range as key ---------*- C++ -*-===// 2 // 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 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the ContinuousRangeMap class, which is a highly 10 // specialized container used by serialization. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H 15 #define LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H 16 17 #include "clang/Basic/LLVM.h" 18 #include "llvm/ADT/STLExtras.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include <algorithm> 21 #include <cassert> 22 #include <utility> 23 24 namespace clang { 25 26 /// A map from continuous integer ranges to some value, with a very 27 /// specialized interface. 28 /// 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. 33 /// 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 { 38 public: 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 *; 44 45 private: 46 using Representation = SmallVector<value_type, InitialCapacity>; 47 48 Representation Rep; 49 50 struct Compare { 51 bool operator ()(const_reference L, Int R) const { 52 return L.first < R; 53 } 54 bool operator ()(Int L, const_reference R) const { 55 return L < R.first; 56 } 57 bool operator ()(Int L, Int R) const { 58 return L < R; 59 } 60 bool operator ()(const_reference L, const_reference R) const { 61 return L.first < R.first; 62 } 63 }; 64 65 public: 66 void insert(const value_type &Val) { 67 if (!Rep.empty() && Rep.back() == Val) 68 return; 69 70 assert((Rep.empty() || Rep.back().first < Val.first) && 71 "Must insert keys in order."); 72 Rep.push_back(Val); 73 } 74 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; 79 return; 80 } 81 82 Rep.insert(I, Val); 83 } 84 85 using iterator = typename Representation::iterator; 86 using const_iterator = typename Representation::const_iterator; 87 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(); } 92 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. 97 if (I == Rep.begin()) 98 return Rep.end(); 99 --I; 100 return I; 101 } 102 const_iterator find(Int K) const { 103 return const_cast<ContinuousRangeMap*>(this)->find(K); 104 } 105 106 reference back() { return Rep.back(); } 107 const_reference back() const { return Rep.back(); } 108 109 /// An object that helps properly build a continuous range map 110 /// from a set of values. 111 class Builder { 112 ContinuousRangeMap &Self; 113 114 public: 115 explicit Builder(ContinuousRangeMap &Self) : Self(Self) {} 116 Builder(const Builder&) = delete; 117 Builder &operator=(const Builder&) = delete; 118 119 ~Builder() { 120 llvm::sort(Self.Rep, Compare()); 121 Self.Rep.erase( 122 std::unique( 123 Self.Rep.begin(), Self.Rep.end(), 124 [](const_reference A, const_reference B) { 125 // FIXME: we should not allow any duplicate keys, but there are 126 // a lot of duplicate 0 -> 0 mappings to remove first. 127 assert((A == B || A.first != B.first) && 128 "ContinuousRangeMap::Builder given non-unique keys"); 129 return A == B; 130 }), 131 Self.Rep.end()); 132 } 133 134 void insert(const value_type &Val) { 135 Self.Rep.push_back(Val); 136 } 137 }; 138 139 friend class Builder; 140 }; 141 142 } // namespace clang 143 144 #endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H 145