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