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