169 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// Implements a coalescing interval map.10//11//===----------------------------------------------------------------------===//12 13#ifndef ORC_RT_INTERVAL_MAP_H14#define ORC_RT_INTERVAL_MAP_H15 16#include "adt.h"17#include <cassert>18#include <map>19 20namespace orc_rt {21 22enum 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 IntervalMap27/// collection to make it easy to swap over in the future if we choose28/// to.29template <typename KeyT, typename ValT> class IntervalMapBase {30private: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 48public: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 existing89 // 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 after97 // 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 121protected:122 ImplMap Impl;123};124 125template <typename KeyT, typename ValT, IntervalCoalescing Coalescing>126class IntervalMap;127 128template <typename KeyT, typename ValT>129class IntervalMap<KeyT, ValT, IntervalCoalescing::Enabled>130 : public IntervalMapBase<KeyT, ValT> {131public: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 insertion137 // 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 156template <typename KeyT, typename ValT>157class IntervalMap<KeyT, ValT, IntervalCoalescing::Disabled>158 : public IntervalMapBase<KeyT, ValT> {159public: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_rt167 168#endif // ORC_RT_INTERVAL_MAP_H169