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