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 | // This file implements a map that provides insertion order iteration. The |
10 | // interface is purposefully minimal. The key is assumed to be cheap to copy |
11 | // and 2 copies are kept, one for indexing in a DenseMap, one for iteration in |
12 | // a std::vector. |
13 | // |
14 | //===----------------------------------------------------------------------===// |
15 | |
16 | #ifndef LLVM_ADT_MAPVECTOR_H |
17 | #define LLVM_ADT_MAPVECTOR_H |
18 | |
19 | #include "llvm/ADT/DenseMap.h" |
20 | #include "llvm/ADT/SmallVector.h" |
21 | #include <algorithm> |
22 | #include <cassert> |
23 | #include <cstddef> |
24 | #include <iterator> |
25 | #include <type_traits> |
26 | #include <utility> |
27 | #include <vector> |
28 | |
29 | namespace llvm { |
30 | |
31 | /// This class implements a map that also provides access to all stored values |
32 | /// in a deterministic order. The values are kept in a std::vector and the |
33 | /// mapping is done with DenseMap from Keys to indexes in that vector. |
34 | template<typename KeyT, typename ValueT, |
35 | typename MapType = DenseMap<KeyT, unsigned>, |
36 | typename VectorType = std::vector<std::pair<KeyT, ValueT>>> |
37 | class MapVector { |
38 | MapType Map; |
39 | VectorType Vector; |
40 | |
41 | static_assert( |
42 | std::is_integral<typename MapType::mapped_type>::value, |
43 | "The mapped_type of the specified Map must be an integral type" ); |
44 | |
45 | public: |
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<ValueT>::value, |
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 | std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { |
118 | std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0); |
119 | std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); |
120 | auto &I = Result.first->second; |
121 | if (Result.second) { |
122 | Vector.push_back(std::make_pair(KV.first, KV.second)); |
123 | I = Vector.size() - 1; |
124 | return std::make_pair(std::prev(end()), true); |
125 | } |
126 | return std::make_pair(begin() + I, false); |
127 | } |
128 | |
129 | std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { |
130 | // Copy KV.first into the map, then move it into the vector. |
131 | std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0); |
132 | std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); |
133 | auto &I = Result.first->second; |
134 | if (Result.second) { |
135 | Vector.push_back(std::move(KV)); |
136 | I = Vector.size() - 1; |
137 | return std::make_pair(std::prev(end()), true); |
138 | } |
139 | return std::make_pair(begin() + I, false); |
140 | } |
141 | |
142 | size_type count(const KeyT &Key) const { |
143 | typename MapType::const_iterator Pos = Map.find(Key); |
144 | return Pos == Map.end()? 0 : 1; |
145 | } |
146 | |
147 | iterator find(const KeyT &Key) { |
148 | typename MapType::const_iterator Pos = Map.find(Key); |
149 | return Pos == Map.end()? Vector.end() : |
150 | (Vector.begin() + Pos->second); |
151 | } |
152 | |
153 | const_iterator find(const KeyT &Key) const { |
154 | typename MapType::const_iterator Pos = Map.find(Key); |
155 | return Pos == Map.end()? Vector.end() : |
156 | (Vector.begin() + Pos->second); |
157 | } |
158 | |
159 | /// Remove the last element from the vector. |
160 | void pop_back() { |
161 | typename MapType::iterator Pos = Map.find(Vector.back().first); |
162 | Map.erase(Pos); |
163 | Vector.pop_back(); |
164 | } |
165 | |
166 | /// Remove the element given by Iterator. |
167 | /// |
168 | /// Returns an iterator to the element following the one which was removed, |
169 | /// which may be end(). |
170 | /// |
171 | /// \note This is a deceivingly expensive operation (linear time). It's |
172 | /// usually better to use \a remove_if() if possible. |
173 | typename VectorType::iterator erase(typename VectorType::iterator Iterator) { |
174 | Map.erase(Iterator->first); |
175 | auto Next = Vector.erase(Iterator); |
176 | if (Next == Vector.end()) |
177 | return Next; |
178 | |
179 | // Update indices in the map. |
180 | size_t Index = Next - Vector.begin(); |
181 | for (auto &I : Map) { |
182 | assert(I.second != Index && "Index was already erased!" ); |
183 | if (I.second > Index) |
184 | --I.second; |
185 | } |
186 | return Next; |
187 | } |
188 | |
189 | /// Remove all elements with the key value Key. |
190 | /// |
191 | /// Returns the number of elements removed. |
192 | size_type erase(const KeyT &Key) { |
193 | auto Iterator = find(Key); |
194 | if (Iterator == end()) |
195 | return 0; |
196 | erase(Iterator); |
197 | return 1; |
198 | } |
199 | |
200 | /// Remove the elements that match the predicate. |
201 | /// |
202 | /// Erase all elements that match \c Pred in a single pass. Takes linear |
203 | /// time. |
204 | template <class Predicate> void remove_if(Predicate Pred); |
205 | }; |
206 | |
207 | template <typename KeyT, typename ValueT, typename MapType, typename VectorType> |
208 | template <class Function> |
209 | void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { |
210 | auto O = Vector.begin(); |
211 | for (auto I = O, E = Vector.end(); I != E; ++I) { |
212 | if (Pred(*I)) { |
213 | // Erase from the map. |
214 | Map.erase(I->first); |
215 | continue; |
216 | } |
217 | |
218 | if (I != O) { |
219 | // Move the value and update the index in the map. |
220 | *O = std::move(*I); |
221 | Map[O->first] = O - Vector.begin(); |
222 | } |
223 | ++O; |
224 | } |
225 | // Erase trailing entries in the vector. |
226 | Vector.erase(O, Vector.end()); |
227 | } |
228 | |
229 | /// A MapVector that performs no allocations if smaller than a certain |
230 | /// size. |
231 | template <typename KeyT, typename ValueT, unsigned N> |
232 | struct SmallMapVector |
233 | : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>, |
234 | SmallVector<std::pair<KeyT, ValueT>, N>> { |
235 | }; |
236 | |
237 | } // end namespace llvm |
238 | |
239 | #endif // LLVM_ADT_MAPVECTOR_H |
240 | |