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