Home | History | Annotate | Download | only in Serialization 
      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/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&) = delete;
    113     Builder &operator=(const Builder&) = delete;
    114 
    115   public:
    116     explicit Builder(ContinuousRangeMap &Self) : Self(Self) { }
    117 
    118     ~Builder() {
    119       std::sort(Self.Rep.begin(), Self.Rep.end(), Compare());
    120       std::unique(Self.Rep.begin(), Self.Rep.end(),
    121                   [](const_reference A, const_reference B) {
    122         // FIXME: we should not allow any duplicate keys, but there are a lot of
    123         // duplicate 0 -> 0 mappings to remove first.
    124         assert((A == B || A.first != B.first) &&
    125                "ContinuousRangeMap::Builder given non-unique keys");
    126         return A == B;
    127       });
    128     }
    129 
    130     void insert(const value_type &Val) {
    131       Self.Rep.push_back(Val);
    132     }
    133   };
    134   friend class Builder;
    135 };
    136 
    137 }
    138 
    139 #endif
    140