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