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

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