interval_map.h

//===--------- interval_map.h - A sorted interval map -----------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Implements a coalescing interval map.
//
//===----------------------------------------------------------------------===//

#ifndef ORC_RT_INTERVAL_MAP_H
#define ORC_RT_INTERVAL_MAP_H

#include "adt.h"
#include <cassert>
#include <map>

namespace __orc_rt {

enum class IntervalCoalescing { Enabled, Disabled };

/// Maps intervals to keys with optional coalescing.
///
/// NOTE: The interface is kept mostly compatible with LLVM's IntervalMap
///       collection to make it easy to swap over in the future if we choose
///       to.
template <typename KeyT, typename ValT> class IntervalMapBase {
private:
  using KeyPairT = std::pair<KeyT, KeyT>;

  struct Compare {
    using is_transparent = std::true_type;
    bool operator()(const KeyPairT &LHS, const KeyPairT &RHS) const {
      return LHS < RHS;
    }
    bool operator()(const KeyPairT &LHS, const KeyT &RHS) const {
      return LHS.first < RHS;
    }
    bool operator()(const KeyT &LHS, const KeyPairT &RHS) const {
      return LHS < RHS.first;
    }
  };

  using ImplMap = std::map<KeyPairT, ValT, Compare>;

public:
  using iterator = typename ImplMap::iterator;
  using const_iterator = typename ImplMap::const_iterator;
  using size_type = typename ImplMap::size_type;

  bool empty() const { return Impl.empty(); }

  void clear() { Impl.clear(); }

  iterator begin() { return Impl.begin(); }
  iterator end() { return Impl.end(); }

  const_iterator begin() const { return Impl.begin(); }
  const_iterator end() const { return Impl.end(); }

  iterator find(KeyT K) {
    // Early out if the key is clearly outside the range.
    if (empty() || K < begin()->first.first ||
        K >= std::prev(end())->first.second)
      return end();

    auto I = Impl.upper_bound(K);
    assert(I != begin() && "Should have hit early out above");
    I = std::prev(I);
    if (K < I->first.second)
      return I;
    return end();
  }

  const_iterator find(KeyT K) const {
    return const_cast<IntervalMapBase<KeyT, ValT> *>(this)->find(K);
  }

  ValT lookup(KeyT K, ValT NotFound = ValT()) const {
    auto I = find(K);
    if (I == end())
      return NotFound;
    return I->second;
  }

  // Erase [KS, KE), which must be entirely containing within one existing
  // range in the map. Removal is allowed to split the range.
  void erase(KeyT KS, KeyT KE) {
    if (empty())
      return;

    auto J = Impl.upper_bound(KS);

    // Check previous range. Bail out if range to remove is entirely after
    // it.
    auto I = std::prev(J);
    if (KS >= I->first.second)
      return;

    // Assert that range is wholly contained.
    assert(KE <= I->first.second);

    auto Tmp = std::move(*I);
    Impl.erase(I);

    // Split-right -- introduce right-split range.
    if (KE < Tmp.first.second) {
      Impl.insert(
          J, std::make_pair(std::make_pair(KE, Tmp.first.second), Tmp.second));
      J = std::prev(J);
    }

    // Split-left -- introduce left-split range.
    if (KS > Tmp.first.first)
      Impl.insert(
          J, std::make_pair(std::make_pair(Tmp.first.first, KS), Tmp.second));
  }

protected:
  ImplMap Impl;
};

template <typename KeyT, typename ValT, IntervalCoalescing Coalescing>
class IntervalMap;

template <typename KeyT, typename ValT>
class IntervalMap<KeyT, ValT, IntervalCoalescing::Enabled>
    : public IntervalMapBase<KeyT, ValT> {
public:
  // Coalescing insert. Requires that ValTs be equality-comparable.
  void insert(KeyT KS, KeyT KE, ValT V) {
    auto J = this->Impl.upper_bound(KS);

    // Coalesce-right if possible. Either way, J points at our insertion
    // point.
    if (J != this->end() && KE == J->first.first && J->second == V) {
      KE = J->first.second;
      auto Tmp = J++;
      this->Impl.erase(Tmp);
    }

    // Coalesce-left if possible.
    if (J != this->begin()) {
      auto I = std::prev(J);
      if (I->first.second == KS && I->second == V) {
        KS = I->first.first;
        this->Impl.erase(I);
      }
    }
    this->Impl.insert(J, std::make_pair(std::make_pair(KS, KE), std::move(V)));
  }
};

template <typename KeyT, typename ValT>
class IntervalMap<KeyT, ValT, IntervalCoalescing::Disabled>
    : public IntervalMapBase<KeyT, ValT> {
public:
  // Non-coalescing insert. Does not require ValT to be equality-comparable.
  void insert(KeyT KS, KeyT KE, ValT V) {
    this->Impl.insert(std::make_pair(std::make_pair(KS, KE), std::move(V)));
  }
};

} // End namespace __orc_rt

#endif // ORC_RT_INTERVAL_MAP_H