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   typedef typename Representation::iterator iterator;
  73   typedef typename Representation::const_iterator const_iterator;
  74
  75   iterator begin() { return Rep.begin(); }
  76   iterator end() { return Rep.end(); }
  77   const_iterator begin() const { return Rep.begin(); }
  78   const_iterator end() const { return Rep.end(); }
  79
  80   iterator find(Int K) {
  81     iterator I = std::upper_bound(Rep.begin(), Rep.end(), K, Compare());
  82     // I points to the first entry with a key > K, which is the range that
  83     // follows the one containing K.
  84     if (I == Rep.begin())
  85       return Rep.end();
  86     --I;
  87     return I;
  88   }
  89   const_iterator find(Int K) const {
  90     return const_cast<ContinuousRangeMap*>(this)->find(K);
  91   }
  92
  93   reference back() { return Rep.back(); }
  94   const_reference back() const { return Rep.back(); }
  95
  96   /// \brief An object that helps properly build a continuous range map
  97   /// from a set of values.
  98   class Builder {
  99     ContinuousRangeMap &Self;
 100
 101     Builder(const Builder&); // DO NOT IMPLEMENT
 102     Builder &operator=(const Builder&); // DO NOT IMPLEMENT
 103
 104   public:
 105     explicit Builder(ContinuousRangeMap &Self) : Self(Self) { }
 106
 107     ~Builder() {
 108       std::sort(Self.Rep.begin(), Self.Rep.end(), Compare());
 109     }
 110
 111     void insert(const value_type &Val) {
 112       Self.Rep.push_back(Val);
 113     }
 114   };
 115   friend class Builder;
 116 };
 117
 118 }
 119
 120 #endif