compiler-rt/lib/orc/interval_map.h

   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