Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 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 |