1 | //===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- 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 | /// \file |
10 | /// This file implements a map that provides insertion order iteration. The |
11 | /// interface is purposefully minimal. The key is assumed to be cheap to copy |
12 | /// and 2 copies are kept, one for indexing in a DenseMap, one for iteration in |
13 | /// a SmallVector. |
14 | /// |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #ifndef LLVM_ADT_MAPVECTOR_H |
18 | #define LLVM_ADT_MAPVECTOR_H |
19 | |
20 | #include "llvm/ADT/DenseMap.h" |
21 | #include "llvm/ADT/SmallVector.h" |
22 | #include <cassert> |
23 | #include <cstddef> |
24 | #include <iterator> |
25 | #include <type_traits> |
26 | #include <utility> |
27 | |
28 | namespace llvm { |
29 | |
30 | /// This class implements a map that also provides access to all stored values |
31 | /// in a deterministic order. The values are kept in a SmallVector<*, 0> and the |
32 | /// mapping is done with DenseMap from Keys to indexes in that vector. |
33 | template <typename KeyT, typename ValueT, |
34 | typename MapType = DenseMap<KeyT, unsigned>, |
35 | typename VectorType = SmallVector<std::pair<KeyT, ValueT>, 0>> |
36 | class MapVector { |
37 | MapType Map; |
38 | VectorType Vector; |
39 | |
40 | static_assert( |
41 | std::is_integral_v<typename MapType::mapped_type>, |
42 | "The mapped_type of the specified Map must be an integral type" ); |
43 | |
44 | public: |
45 | using key_type = KeyT; |
46 | using value_type = typename VectorType::value_type; |
47 | using size_type = typename VectorType::size_type; |
48 | |
49 | using iterator = typename VectorType::iterator; |
50 | using const_iterator = typename VectorType::const_iterator; |
51 | using reverse_iterator = typename VectorType::reverse_iterator; |
52 | using const_reverse_iterator = typename VectorType::const_reverse_iterator; |
53 | |
54 | /// Clear the MapVector and return the underlying vector. |
55 | VectorType takeVector() { |
56 | Map.clear(); |
57 | return std::move(Vector); |
58 | } |
59 | |
60 | size_type size() const { return Vector.size(); } |
61 | |
62 | /// Grow the MapVector so that it can contain at least \p NumEntries items |
63 | /// before resizing again. |
64 | void reserve(size_type NumEntries) { |
65 | Map.reserve(NumEntries); |
66 | Vector.reserve(NumEntries); |
67 | } |
68 | |
69 | iterator begin() { return Vector.begin(); } |
70 | const_iterator begin() const { return Vector.begin(); } |
71 | iterator end() { return Vector.end(); } |
72 | const_iterator end() const { return Vector.end(); } |
73 | |
74 | reverse_iterator rbegin() { return Vector.rbegin(); } |
75 | const_reverse_iterator rbegin() const { return Vector.rbegin(); } |
76 | reverse_iterator rend() { return Vector.rend(); } |
77 | const_reverse_iterator rend() const { return Vector.rend(); } |
78 | |
79 | bool empty() const { |
80 | return Vector.empty(); |
81 | } |
82 | |
83 | std::pair<KeyT, ValueT> &front() { return Vector.front(); } |
84 | const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } |
85 | std::pair<KeyT, ValueT> &back() { return Vector.back(); } |
86 | const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } |
87 | |
88 | void clear() { |
89 | Map.clear(); |
90 | Vector.clear(); |
91 | } |
92 | |
93 | void swap(MapVector &RHS) { |
94 | std::swap(Map, RHS.Map); |
95 | std::swap(Vector, RHS.Vector); |
96 | } |
97 | |
98 | ValueT &operator[](const KeyT &Key) { |
99 | std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(Key, 0); |
100 | std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); |
101 | auto &I = Result.first->second; |
102 | if (Result.second) { |
103 | Vector.push_back(std::make_pair(Key, ValueT())); |
104 | I = Vector.size() - 1; |
105 | } |
106 | return Vector[I].second; |
107 | } |
108 | |
109 | // Returns a copy of the value. Only allowed if ValueT is copyable. |
110 | ValueT lookup(const KeyT &Key) const { |
111 | static_assert(std::is_copy_constructible_v<ValueT>, |
112 | "Cannot call lookup() if ValueT is not copyable." ); |
113 | typename MapType::const_iterator Pos = Map.find(Key); |
114 | return Pos == Map.end()? ValueT() : Vector[Pos->second].second; |
115 | } |
116 | |
117 | template <typename... Ts> |
118 | std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&...Args) { |
119 | auto [It, Inserted] = Map.insert(std::make_pair(Key, 0)); |
120 | if (Inserted) { |
121 | It->second = Vector.size(); |
122 | Vector.emplace_back(std::piecewise_construct, std::forward_as_tuple(Key), |
123 | std::forward_as_tuple(std::forward<Ts>(Args)...)); |
124 | return std::make_pair(std::prev(end()), true); |
125 | } |
126 | return std::make_pair(begin() + It->second, false); |
127 | } |
128 | template <typename... Ts> |
129 | std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&...Args) { |
130 | auto [It, Inserted] = Map.insert(std::make_pair(Key, 0)); |
131 | if (Inserted) { |
132 | It->second = Vector.size(); |
133 | Vector.emplace_back(std::piecewise_construct, |
134 | std::forward_as_tuple(std::move(Key)), |
135 | std::forward_as_tuple(std::forward<Ts>(Args)...)); |
136 | return std::make_pair(std::prev(end()), true); |
137 | } |
138 | return std::make_pair(begin() + It->second, false); |
139 | } |
140 | |
141 | std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { |
142 | return try_emplace(KV.first, KV.second); |
143 | } |
144 | std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { |
145 | return try_emplace(std::move(KV.first), std::move(KV.second)); |
146 | } |
147 | |
148 | template <typename V> |
149 | std::pair<iterator, bool> insert_or_assign(const KeyT &Key, V &&Val) { |
150 | auto Ret = try_emplace(Key, std::forward<V>(Val)); |
151 | if (!Ret.second) |
152 | Ret.first->second = std::forward<V>(Val); |
153 | return Ret; |
154 | } |
155 | template <typename V> |
156 | std::pair<iterator, bool> insert_or_assign(KeyT &&Key, V &&Val) { |
157 | auto Ret = try_emplace(std::move(Key), std::forward<V>(Val)); |
158 | if (!Ret.second) |
159 | Ret.first->second = std::forward<V>(Val); |
160 | return Ret; |
161 | } |
162 | |
163 | bool contains(const KeyT &Key) const { return Map.find(Key) != Map.end(); } |
164 | |
165 | size_type count(const KeyT &Key) const { return contains(Key) ? 1 : 0; } |
166 | |
167 | iterator find(const KeyT &Key) { |
168 | typename MapType::const_iterator Pos = Map.find(Key); |
169 | return Pos == Map.end()? Vector.end() : |
170 | (Vector.begin() + Pos->second); |
171 | } |
172 | |
173 | const_iterator find(const KeyT &Key) const { |
174 | typename MapType::const_iterator Pos = Map.find(Key); |
175 | return Pos == Map.end()? Vector.end() : |
176 | (Vector.begin() + Pos->second); |
177 | } |
178 | |
179 | /// Remove the last element from the vector. |
180 | void pop_back() { |
181 | typename MapType::iterator Pos = Map.find(Vector.back().first); |
182 | Map.erase(Pos); |
183 | Vector.pop_back(); |
184 | } |
185 | |
186 | /// Remove the element given by Iterator. |
187 | /// |
188 | /// Returns an iterator to the element following the one which was removed, |
189 | /// which may be end(). |
190 | /// |
191 | /// \note This is a deceivingly expensive operation (linear time). It's |
192 | /// usually better to use \a remove_if() if possible. |
193 | typename VectorType::iterator erase(typename VectorType::iterator Iterator) { |
194 | Map.erase(Iterator->first); |
195 | auto Next = Vector.erase(Iterator); |
196 | if (Next == Vector.end()) |
197 | return Next; |
198 | |
199 | // Update indices in the map. |
200 | size_t Index = Next - Vector.begin(); |
201 | for (auto &I : Map) { |
202 | assert(I.second != Index && "Index was already erased!" ); |
203 | if (I.second > Index) |
204 | --I.second; |
205 | } |
206 | return Next; |
207 | } |
208 | |
209 | /// Remove all elements with the key value Key. |
210 | /// |
211 | /// Returns the number of elements removed. |
212 | size_type erase(const KeyT &Key) { |
213 | auto Iterator = find(Key); |
214 | if (Iterator == end()) |
215 | return 0; |
216 | erase(Iterator); |
217 | return 1; |
218 | } |
219 | |
220 | /// Remove the elements that match the predicate. |
221 | /// |
222 | /// Erase all elements that match \c Pred in a single pass. Takes linear |
223 | /// time. |
224 | template <class Predicate> void remove_if(Predicate Pred); |
225 | }; |
226 | |
227 | template <typename KeyT, typename ValueT, typename MapType, typename VectorType> |
228 | template <class Function> |
229 | void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { |
230 | auto O = Vector.begin(); |
231 | for (auto I = O, E = Vector.end(); I != E; ++I) { |
232 | if (Pred(*I)) { |
233 | // Erase from the map. |
234 | Map.erase(I->first); |
235 | continue; |
236 | } |
237 | |
238 | if (I != O) { |
239 | // Move the value and update the index in the map. |
240 | *O = std::move(*I); |
241 | Map[O->first] = O - Vector.begin(); |
242 | } |
243 | ++O; |
244 | } |
245 | // Erase trailing entries in the vector. |
246 | Vector.erase(O, Vector.end()); |
247 | } |
248 | |
249 | /// A MapVector that performs no allocations if smaller than a certain |
250 | /// size. |
251 | template <typename KeyT, typename ValueT, unsigned N> |
252 | struct SmallMapVector |
253 | : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>, |
254 | SmallVector<std::pair<KeyT, ValueT>, N>> { |
255 | }; |
256 | |
257 | } // end namespace llvm |
258 | |
259 | #endif // LLVM_ADT_MAPVECTOR_H |
260 | |