88 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// Implements a coalescing interval set.10//11//===----------------------------------------------------------------------===//12 13#ifndef ORC_RT_INTERVAL_SET_H14#define ORC_RT_INTERVAL_SET_H15 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 IntervalMap25/// collection to make it easy to swap over in the future if we choose26/// 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_rt86 87#endif // ORC_RT_INTERVAL_SET_H88