1//===--------- interval_set.h - A sorted interval set -----------*- 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 set.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef ORC_RT_INTERVAL_SET_H
14#define ORC_RT_INTERVAL_SET_H
15
16#include "interval_map.h"
17
18namespace __orc_rt {
19
20/// Implements a coalescing interval set.
21///
22/// Adjacent intervals are coalesced.
23///
24/// NOTE: The interface is kept mostly compatible with LLVM's IntervalMap
25///       collection to make it easy to swap over in the future if we choose
26///       to.
27template <typename KeyT, IntervalCoalescing Coalescing>
28class IntervalSet {
29private:
30  using ImplMap = IntervalMap<KeyT, std::monostate, Coalescing>;
31public:
32
33  using value_type = std::pair<KeyT, KeyT>;
34
35  class const_iterator {
36    friend class IntervalSet;
37  public:
38    using difference_type = typename ImplMap::iterator::difference_type;
39    using value_type = IntervalSet::value_type;
40    using pointer = const value_type *;
41    using reference = const value_type &;
42    using iterator_category = std::input_iterator_tag;
43
44    const_iterator() = default;
45    const value_type &operator*() const { return I->first; }
46    const value_type *operator->() const { return &I->first; }
47    const_iterator &operator++() { ++I; return *this; }
48    const_iterator operator++(int) { auto Tmp = I; ++I; return Tmp; }
49    friend bool operator==(const const_iterator &LHS,
50                           const const_iterator &RHS) {
51      return LHS.I == RHS.I;
52    }
53    friend bool operator!=(const const_iterator &LHS,
54                           const const_iterator &RHS) {
55      return LHS.I != RHS.I;
56    }
57  private:
58    const_iterator(typename ImplMap::const_iterator I) : I(std::move(I)) {}
59    typename ImplMap::const_iterator I;
60  };
61
62  bool empty() const { return Map.empty(); }
63
64  void clear() { Map.clear(); }
65
66  const_iterator begin() const { return const_iterator(Map.begin()); }
67  const_iterator end() const { return const_iterator(Map.end()); }
68
69  const_iterator find(KeyT K) const {
70    return const_iterator(Map.find(K));
71  }
72
73  void insert(KeyT KS, KeyT KE) {
74    Map.insert(std::move(KS), std::move(KE), std::monostate());
75  }
76
77  void erase(KeyT KS, KeyT KE) {
78    Map.erase(KS, KE);
79  }
80
81private:
82  ImplMap Map;
83};
84
85} // End namespace __orc_rt
86
87#endif // ORC_RT_INTERVAL_SET_H
88