Line data Source code
1 : //===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
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 std::vector.
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 <algorithm>
23 : #include <cassert>
24 : #include <cstddef>
25 : #include <iterator>
26 : #include <type_traits>
27 : #include <utility>
28 : #include <vector>
29 :
30 : namespace llvm {
31 :
32 : /// This class implements a map that also provides access to all stored values
33 : /// in a deterministic order. The values are kept in a std::vector and the
34 : /// mapping is done with DenseMap from Keys to indexes in that vector.
35 : template<typename KeyT, typename ValueT,
36 : typename MapType = DenseMap<KeyT, unsigned>,
37 : typename VectorType = std::vector<std::pair<KeyT, ValueT>>>
38 10344213 : class MapVector {
39 : MapType Map;
40 : VectorType Vector;
41 :
42 : static_assert(
43 : std::is_integral<typename MapType::mapped_type>::value,
44 : "The mapped_type of the specified Map must be an integral type");
45 :
46 : public:
47 : using value_type = typename VectorType::value_type;
48 : using size_type = typename VectorType::size_type;
49 :
50 : using iterator = typename VectorType::iterator;
51 : using const_iterator = typename VectorType::const_iterator;
52 : using reverse_iterator = typename VectorType::reverse_iterator;
53 : using const_reverse_iterator = typename VectorType::const_reverse_iterator;
54 :
55 : /// Clear the MapVector and return the underlying vector.
56 : VectorType takeVector() {
57 15437 : Map.clear();
58 : return std::move(Vector);
59 : }
60 :
61 6178408 : size_type size() const { return Vector.size(); }
62 :
63 : /// Grow the MapVector so that it can contain at least \p NumEntries items
64 : /// before resizing again.
65 : void reserve(size_type NumEntries) {
66 43813 : Map.reserve(NumEntries);
67 43813 : Vector.reserve(NumEntries);
68 : }
69 :
70 : iterator begin() { return Vector.begin(); }
71 335870 : const_iterator begin() const { return Vector.begin(); }
72 : iterator end() { return Vector.end(); }
73 25148377 : const_iterator end() const { return Vector.end(); }
74 :
75 : reverse_iterator rbegin() { return Vector.rbegin(); }
76 : const_reverse_iterator rbegin() const { return Vector.rbegin(); }
77 2 : reverse_iterator rend() { return Vector.rend(); }
78 : const_reverse_iterator rend() const { return Vector.rend(); }
79 :
80 : bool empty() const {
81 6477246 : return Vector.empty();
82 : }
83 :
84 : std::pair<KeyT, ValueT> &front() { return Vector.front(); }
85 : const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
86 : std::pair<KeyT, ValueT> &back() { return Vector.back(); }
87 : const std::pair<KeyT, ValueT> &back() const { return Vector.back(); }
88 :
89 225130 : void clear() {
90 23020769 : Map.clear();
91 : Vector.clear();
92 225130 : }
93 :
94 : void swap(MapVector &RHS) {
95 197 : std::swap(Map, RHS.Map);
96 : std::swap(Vector, RHS.Vector);
97 : }
98 :
99 40761366 : ValueT &operator[](const KeyT &Key) {
100 40761458 : std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(Key, 0);
101 40761274 : std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
102 40761274 : auto &I = Result.first->second;
103 40761366 : if (Result.second) {
104 33202004 : Vector.push_back(std::make_pair(Key, ValueT()));
105 59962165 : I = Vector.size() - 1;
106 : }
107 81522732 : return Vector[I].second;
108 : }
109 380956 :
110 380956 : // Returns a copy of the value. Only allowed if ValueT is copyable.
111 397198 : ValueT lookup(const KeyT &Key) const {
112 380956 : static_assert(std::is_copy_constructible<ValueT>::value,
113 380956 : "Cannot call lookup() if ValueT is not copyable.");
114 267460 : typename MapType::const_iterator Pos = Map.find(Key);
115 350590 : return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
116 : }
117 761912 :
118 60 : std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
119 623947 : std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
120 623947 : std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
121 623947 : auto &I = Result.first->second;
122 623947 : if (Result.second) {
123 633988 : Vector.push_back(std::make_pair(KV.first, KV.second));
124 257967 : I = Vector.size() - 1;
125 329749 : return std::make_pair(std::prev(end()), true);
126 10041 : }
127 1257815 : return std::make_pair(begin() + I, false);
128 : }
129 21990464 :
130 23743021 : std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
131 21990439 : // Copy KV.first into the map, then move it into the vector.
132 23743046 : std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
133 23743046 : std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
134 24295149 : auto &I = Result.first->second;
135 45434616 : if (Result.second) {
136 1146426 : Vector.push_back(std::move(KV));
137 46109524 : I = Vector.size() - 1;
138 10161 : return std::make_pair(std::prev(end()), true);
139 10275 : }
140 626592 : return std::make_pair(begin() + I, false);
141 10283 : }
142 20754 :
143 114 : size_type count(const KeyT &Key) const {
144 275736 : typename MapType::const_iterator Pos = Map.find(Key);
145 275645 : return Pos == Map.end()? 0 : 1;
146 344 : }
147 681 :
148 22078134 : iterator find(const KeyT &Key) {
149 22078629 : typename MapType::const_iterator Pos = Map.find(Key);
150 1725 : return Pos == Map.end()? Vector.end() :
151 22077979 : (Vector.begin() + Pos->second);
152 1739 : }
153 1824 :
154 1478801 : const_iterator find(const KeyT &Key) const {
155 1581 : typename MapType::const_iterator Pos = Map.find(Key);
156 1478717 : return Pos == Map.end()? Vector.end() :
157 1480432 : (Vector.begin() + Pos->second);
158 1487324 : }
159 2090574 :
160 1483509 : /// Remove the last element from the vector.
161 2350131 : void pop_back() {
162 615065 : typename MapType::iterator Pos = Map.find(Vector.back().first);
163 615065 : Map.erase(Pos);
164 791183 : Vector.pop_back();
165 108922 : }
166 1768 :
167 1209962 : /// Remove the element given by Iterator.
168 642 : ///
169 668 : /// Returns an iterator to the element following the one which was removed,
170 641 : /// which may be end().
171 668 : ///
172 1120 : /// \note This is a deceivingly expensive operation (linear time). It's
173 1044 : /// usually better to use \a remove_if() if possible.
174 6320334 : typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
175 6320733 : Map.erase(Iterator->first);
176 77466 : auto Next = Vector.erase(Iterator);
177 6320215 : if (Next == Vector.end())
178 19880390 : return Next;
179 15847835 :
180 373 : // Update indices in the map.
181 17844128 : size_t Index = Next - Vector.begin();
182 47963296 : for (auto &I : Map) {
183 10152 : assert(I.second != Index && "Index was already erased!");
184 45987239 : if (I.second > Index)
185 23831389 : --I.second;
186 10624 : }
187 1996858 : return Next;
188 20370 : }
189 259 :
190 55 : /// Remove all elements with the key value Key.
191 121 : ///
192 338 : /// Returns the number of elements removed.
193 14418194 : size_type erase(const KeyT &Key) {
194 14418884 : auto Iterator = find(Key);
195 14418788 : if (Iterator == end())
196 1891 : return 0;
197 6019642 : erase(Iterator);
198 6021282 : return 1;
199 1890 : }
200 1932 :
201 1934 : /// Remove the elements that match the predicate.
202 1646 : ///
203 3280 : /// Erase all elements that match \c Pred in a single pass. Takes linear
204 905188 : /// time.
205 915202 : template <class Predicate> void remove_if(Predicate Pred);
206 1132 : };
207 11173 :
208 11257 : template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
209 10042 : template <class Function>
210 10042 : void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
211 10083 : auto O = Vector.begin();
212 21741 : for (auto I = O, E = Vector.end(); I != E; ++I) {
213 1575 : if (Pred(*I)) {
214 28901 : // Erase from the map.
215 30483 : Map.erase(I->first);
216 0 : continue;
217 28925 : }
218 2 :
219 26 : if (I != O) {
220 744016 : // Move the value and update the index in the map.
221 744017 : *O = std::move(*I);
222 1601 : Map[O->first] = O - Vector.begin();
223 746705 : }
224 1141 : ++O;
225 81794 : }
226 79094 : // Erase trailing entries in the vector.
227 29387 : Vector.erase(O, Vector.end());
228 136720 : }
229 28251 :
230 664896 : /// A MapVector that performs no allocations if smaller than a certain
231 693151 : /// size.
232 5 : template <typename KeyT, typename ValueT, unsigned N>
233 1756033 : struct SmallMapVector
234 1 : : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
235 1 : SmallVector<std::pair<KeyT, ValueT>, N>> {
236 0 : };
237 0 :
238 : } // end namespace llvm
239 :
240 1 : #endif // LLVM_ADT_MAPVECTOR_H
|
