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 18 namespace __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. 27 template <typename KeyT, IntervalCoalescing Coalescing> 28 class IntervalSet { 29 private: 30 using ImplMap = IntervalMap<KeyT, std::monostate, Coalescing>; 31 public: 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 81 private: 82 ImplMap Map; 83 }; 84 85 } // End namespace __orc_rt 86 87 #endif // ORC_RT_INTERVAL_SET_H 88