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