compiler-rt/lib/orc/interval_set.h

   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