clang/Serialization/ContinuousRangeMap.h

0001 //===- ContinuousRangeMap.h - Map with int range as key ---------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 //  This file defines the ContinuousRangeMap class, which is a highly
0010 //  specialized container used by serialization.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
0015 #define LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H
0016
0017 #include "clang/Basic/LLVM.h"
0018 #include "llvm/ADT/STLExtras.h"
0019 #include "llvm/ADT/SmallVector.h"
0020 #include <algorithm>
0021 #include <cassert>
0022 #include <utility>
0023
0024 namespace clang {
0025
0026 /// A map from continuous integer ranges to some value, with a very
0027 /// specialized interface.
0028 ///
0029 /// CRM maps from integer ranges to values. The ranges are continuous, i.e.
0030 /// where one ends, the next one begins. So if the map contains the stops I0-3,
0031 /// the first range is from I0 to I1, the second from I1 to I2, the third from
0032 /// I2 to I3 and the last from I3 to infinity.
0033 ///
0034 /// Ranges must be inserted in order. Inserting a new stop I4 into the map will
0035 /// shrink the fourth range to I3 to I4 and add the new range I4 to inf.
0036 template <typename Int, typename V, unsigned InitialCapacity>
0037 class ContinuousRangeMap {
0038 public:
0039   using value_type = std::pair<Int, V>;
0040   using reference = value_type &;
0041   using const_reference = const value_type &;
0042   using pointer = value_type *;
0043   using const_pointer = const value_type *;
0044
0045 private:
0046   using Representation = SmallVector<value_type, InitialCapacity>;
0047
0048   Representation Rep;
0049
0050   struct Compare {
0051     bool operator ()(const_reference L, Int R) const {
0052       return L.first < R;
0053     }
0054     bool operator ()(Int L, const_reference R) const {
0055       return L < R.first;
0056     }
0057     bool operator ()(Int L, Int R) const {
0058       return L < R;
0059     }
0060     bool operator ()(const_reference L, const_reference R) const {
0061       return L.first < R.first;
0062     }
0063   };
0064
0065 public:
0066   void insert(const value_type &Val) {
0067     if (!Rep.empty() && Rep.back() == Val)
0068       return;
0069
0070     assert((Rep.empty() || Rep.back().first < Val.first) &&
0071            "Must insert keys in order.");
0072     Rep.push_back(Val);
0073   }
0074
0075   void insertOrReplace(const value_type &Val) {
0076     iterator I = llvm::lower_bound(Rep, Val, Compare());
0077     if (I != Rep.end() && I->first == Val.first) {
0078       I->second = Val.second;
0079       return;
0080     }
0081
0082     Rep.insert(I, Val);
0083   }
0084
0085   using iterator = typename Representation::iterator;
0086   using const_iterator = typename Representation::const_iterator;
0087
0088   iterator begin() { return Rep.begin(); }
0089   iterator end() { return Rep.end(); }
0090   const_iterator begin() const { return Rep.begin(); }
0091   const_iterator end() const { return Rep.end(); }
0092
0093   iterator find(Int K) {
0094     iterator I = llvm::upper_bound(Rep, K, Compare());
0095     // I points to the first entry with a key > K, which is the range that
0096     // follows the one containing K.
0097     if (I == Rep.begin())
0098       return Rep.end();
0099     --I;
0100     return I;
0101   }
0102   const_iterator find(Int K) const {
0103     return const_cast<ContinuousRangeMap*>(this)->find(K);
0104   }
0105
0106   reference back() { return Rep.back(); }
0107   const_reference back() const { return Rep.back(); }
0108
0109   /// An object that helps properly build a continuous range map
0110   /// from a set of values.
0111   class Builder {
0112     ContinuousRangeMap &Self;
0113
0114   public:
0115     explicit Builder(ContinuousRangeMap &Self) : Self(Self) {}
0116     Builder(const Builder&) = delete;
0117     Builder &operator=(const Builder&) = delete;
0118
0119     ~Builder() {
0120       llvm::sort(Self.Rep, Compare());
0121       Self.Rep.erase(
0122           std::unique(
0123               Self.Rep.begin(), Self.Rep.end(),
0124               [](const_reference A, const_reference B) {
0125                 // FIXME: we should not allow any duplicate keys, but there are
0126                 // a lot of duplicate 0 -> 0 mappings to remove first.
0127                 assert((A == B || A.first != B.first) &&
0128                        "ContinuousRangeMap::Builder given non-unique keys");
0129                 return A == B;
0130               }),
0131           Self.Rep.end());
0132     }
0133
0134     void insert(const value_type &Val) {
0135       Self.Rep.push_back(Val);
0136     }
0137   };
0138
0139   friend class Builder;
0140 };
0141
0142 } // namespace clang
0143
0144 #endif // LLVM_CLANG_SERIALIZATION_CONTINUOUSRANGEMAP_H