contrib/llvm-project/clang/include/clang/Serialization/ContinuousRangeMap.h

   1 //===- ContinuousRangeMap.h - Map with int range as key ---------*- 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 //  This file defines the ContinuousRangeMap class, which is a highly
  10 //  specialized container used by serialization.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
  15 #define LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
  16
  17 #include "clang/Basic/LLVM.h"
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include <algorithm>
  21 #include <cassert>
  22 #include <utility>
  23
  24 namespace clang {
  25
  26 /// A map from continuous integer ranges to some value, with a very
  27 /// specialized interface.
  28 ///
  29 /// CRM maps from integer ranges to values. The ranges are continuous, i.e.
  30 /// where one ends, the next one begins. So if the map contains the stops I0-3,
  31 /// the first range is from I0 to I1, the second from I1 to I2, the third from
  32 /// I2 to I3 and the last from I3 to infinity.
  33 ///
  34 /// Ranges must be inserted in order. Inserting a new stop I4 into the map will
  35 /// shrink the fourth range to I3 to I4 and add the new range I4 to inf.
  36 template <typename Int, typename V, unsigned InitialCapacity>
  37 class ContinuousRangeMap {
  38 public:
  39   using value_type = std::pair<Int, V>;
  40   using reference = value_type &;
  41   using const_reference = const value_type &;
  42   using pointer = value_type *;
  43   using const_pointer = const value_type *;
  44
  45 private:
  46   using Representation = SmallVector<value_type, InitialCapacity>;
  47
  48   Representation Rep;
  49
  50   struct Compare {
  51     bool operator ()(const_reference L, Int R) const {
  52       return L.first < R;
  53     }
  54     bool operator ()(Int L, const_reference R) const {
  55       return L < R.first;
  56     }
  57     bool operator ()(Int L, Int R) const {
  58       return L < R;
  59     }
  60     bool operator ()(const_reference L, const_reference R) const {
  61       return L.first < R.first;
  62     }
  63   };
  64
  65 public:
  66   void insert(const value_type &Val) {
  67     if (!Rep.empty() && Rep.back() == Val)
  68       return;
  69
  70     assert((Rep.empty() || Rep.back().first < Val.first) &&
  71            "Must insert keys in order.");
  72     Rep.push_back(Val);
  73   }
  74
  75   void insertOrReplace(const value_type &Val) {
  76     iterator I = llvm::lower_bound(Rep, Val, Compare());
  77     if (I != Rep.end() && I->first == Val.first) {
  78       I->second = Val.second;
  79       return;
  80     }
  81
  82     Rep.insert(I, Val);
  83   }
  84
  85   using iterator = typename Representation::iterator;
  86   using const_iterator = typename Representation::const_iterator;
  87
  88   iterator begin() { return Rep.begin(); }
  89   iterator end() { return Rep.end(); }
  90   const_iterator begin() const { return Rep.begin(); }
  91   const_iterator end() const { return Rep.end(); }
  92
  93   iterator find(Int K) {
  94     iterator I = llvm::upper_bound(Rep, K, Compare());
  95     // I points to the first entry with a key > K, which is the range that
  96     // follows the one containing K.
  97     if (I == Rep.begin())
  98       return Rep.end();
  99     --I;
 100     return I;
 101   }
 102   const_iterator find(Int K) const {
 103     return const_cast<ContinuousRangeMap*>(this)->find(K);
 104   }
 105
 106   reference back() { return Rep.back(); }
 107   const_reference back() const { return Rep.back(); }
 108
 109   /// An object that helps properly build a continuous range map
 110   /// from a set of values.
 111   class Builder {
 112     ContinuousRangeMap &Self;
 113
 114   public:
 115     explicit Builder(ContinuousRangeMap &Self) : Self(Self) {}
 116     Builder(const Builder&) = delete;
 117     Builder &operator=(const Builder&) = delete;
 118
 119     ~Builder() {
 120       llvm::sort(Self.Rep, Compare());
 121       Self.Rep.erase(
 122           std::unique(
 123               Self.Rep.begin(), Self.Rep.end(),
 124               [](const_reference A, const_reference B) {
 125                 // FIXME: we should not allow any duplicate keys, but there are
 126                 // a lot of duplicate 0 -> 0 mappings to remove first.
 127                 assert((A == B || A.first != B.first) &&
 128                        "ContinuousRangeMap::Builder given non-unique keys");
 129                 return A == B;
 130               }),
 131           Self.Rep.end());
 132     }
 133
 134     void insert(const value_type &Val) {
 135       Self.Rep.push_back(Val);
 136     }
 137   };
 138
 139   friend class Builder;
 140 };
 141
 142 } // namespace clang
 143
 144 #endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H