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
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 IntervalMap
27/// collection to make it easy to swap over in the future if we choose
28/// 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 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
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 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
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_rt
167
168#endif // ORC_RT_INTERVAL_MAP_H
169

source code of compiler-rt/lib/orc/interval_map.h