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