1 //===--------- interval_map.h - A sorted interval map -----------*- 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 // Implements a coalescing interval map. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef ORC_RT_INTERVAL_MAP_H 14 #define ORC_RT_INTERVAL_MAP_H 15 16 #include "adt.h" 17 #include <cassert> 18 #include <map> 19 20 namespace __orc_rt { 21 22 enum class IntervalCoalescing { Enabled, Disabled }; 23 24 /// Maps intervals to keys with optional coalescing. 25 /// 26 /// NOTE: The interface is kept mostly compatible with LLVM's IntervalMap 27 /// collection to make it easy to swap over in the future if we choose 28 /// to. 29 template <typename KeyT, typename ValT> class IntervalMapBase { 30 private: 31 using KeyPairT = std::pair<KeyT, KeyT>; 32 33 struct Compare { 34 using is_transparent = std::true_type; 35 bool operator()(const KeyPairT &LHS, const KeyPairT &RHS) const { 36 return LHS < RHS; 37 } 38 bool operator()(const KeyPairT &LHS, const KeyT &RHS) const { 39 return LHS.first < RHS; 40 } 41 bool operator()(const KeyT &LHS, const KeyPairT &RHS) const { 42 return LHS < RHS.first; 43 } 44 }; 45 46 using ImplMap = std::map<KeyPairT, ValT, Compare>; 47 48 public: 49 using iterator = typename ImplMap::iterator; 50 using const_iterator = typename ImplMap::const_iterator; 51 using size_type = typename ImplMap::size_type; 52 53 bool empty() const { return Impl.empty(); } 54 55 void clear() { Impl.clear(); } 56 57 iterator begin() { return Impl.begin(); } 58 iterator end() { return Impl.end(); } 59 60 const_iterator begin() const { return Impl.begin(); } 61 const_iterator end() const { return Impl.end(); } 62 63 iterator find(KeyT K) { 64 // Early out if the key is clearly outside the range. 65 if (empty() || K < begin()->first.first || 66 K >= std::prev(end())->first.second) 67 return end(); 68 69 auto I = Impl.upper_bound(K); 70 assert(I != begin() && "Should have hit early out above"); 71 I = std::prev(I); 72 if (K < I->first.second) 73 return I; 74 return end(); 75 } 76 77 const_iterator find(KeyT K) const { 78 return const_cast<IntervalMapBase<KeyT, ValT> *>(this)->find(K); 79 } 80 81 ValT lookup(KeyT K, ValT NotFound = ValT()) const { 82 auto I = find(K); 83 if (I == end()) 84 return NotFound; 85 return I->second; 86 } 87 88 // Erase [KS, KE), which must be entirely containing within one existing 89 // range in the map. Removal is allowed to split the range. 90 void erase(KeyT KS, KeyT KE) { 91 if (empty()) 92 return; 93 94 auto J = Impl.upper_bound(KS); 95 96 // Check previous range. Bail out if range to remove is entirely after 97 // it. 98 auto I = std::prev(J); 99 if (KS >= I->first.second) 100 return; 101 102 // Assert that range is wholly contained. 103 assert(KE <= I->first.second); 104 105 auto Tmp = std::move(*I); 106 Impl.erase(I); 107 108 // Split-right -- introduce right-split range. 109 if (KE < Tmp.first.second) { 110 Impl.insert( 111 J, std::make_pair(std::make_pair(KE, Tmp.first.second), Tmp.second)); 112 J = std::prev(J); 113 } 114 115 // Split-left -- introduce left-split range. 116 if (KS > Tmp.first.first) 117 Impl.insert( 118 J, std::make_pair(std::make_pair(Tmp.first.first, KS), Tmp.second)); 119 } 120 121 protected: 122 ImplMap Impl; 123 }; 124 125 template <typename KeyT, typename ValT, IntervalCoalescing Coalescing> 126 class IntervalMap; 127 128 template <typename KeyT, typename ValT> 129 class IntervalMap<KeyT, ValT, IntervalCoalescing::Enabled> 130 : public IntervalMapBase<KeyT, ValT> { 131 public: 132 // Coalescing insert. Requires that ValTs be equality-comparable. 133 void insert(KeyT KS, KeyT KE, ValT V) { 134 auto J = this->Impl.upper_bound(KS); 135 136 // Coalesce-right if possible. Either way, J points at our insertion 137 // point. 138 if (J != this->end() && KE == J->first.first && J->second == V) { 139 KE = J->first.second; 140 auto Tmp = J++; 141 this->Impl.erase(Tmp); 142 } 143 144 // Coalesce-left if possible. 145 if (J != this->begin()) { 146 auto I = std::prev(J); 147 if (I->first.second == KS && I->second == V) { 148 KS = I->first.first; 149 this->Impl.erase(I); 150 } 151 } 152 this->Impl.insert(J, std::make_pair(std::make_pair(KS, KE), std::move(V))); 153 } 154 }; 155 156 template <typename KeyT, typename ValT> 157 class IntervalMap<KeyT, ValT, IntervalCoalescing::Disabled> 158 : public IntervalMapBase<KeyT, ValT> { 159 public: 160 // Non-coalescing insert. Does not require ValT to be equality-comparable. 161 void insert(KeyT KS, KeyT KE, ValT V) { 162 this->Impl.insert(std::make_pair(std::make_pair(KS, KE), std::move(V))); 163 } 164 }; 165 166 } // End namespace __orc_rt 167 168 #endif // ORC_RT_INTERVAL_MAP_H 169