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;
operatorCompare35     bool operator()(const KeyPairT &LHS, const KeyPairT &RHS) const {
36       return LHS < RHS;
37     }
operatorCompare38     bool operator()(const KeyPairT &LHS, const KeyT &RHS) const {
39       return LHS.first < RHS;
40     }
operatorCompare41     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 
empty()53   bool empty() const { return Impl.empty(); }
54 
clear()55   void clear() { Impl.clear(); }
56 
begin()57   iterator begin() { return Impl.begin(); }
end()58   iterator end() { return Impl.end(); }
59 
begin()60   const_iterator begin() const { return Impl.begin(); }
end()61   const_iterator end() const { return Impl.end(); }
62 
find(KeyT K)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 
find(KeyT K)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.
erase(KeyT KS,KeyT KE)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.
insert(KeyT KS,KeyT KE,ValT V)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.
insert(KeyT KS,KeyT KE,ValT V)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