contrib/llvm/tools/clang/include/clang/Serialization/ContinuousRangeMap.h

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