LLVM 17.0.0git
MapVector.h
Go to the documentation of this file.
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 std::vector.
14///
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_ADT_MAPVECTOR_H
18#define LLVM_ADT_MAPVECTOR_H
19
20#include "llvm/ADT/DenseMap.h"
22#include <cassert>
23#include <cstddef>
24#include <iterator>
25#include <type_traits>
26#include <utility>
27#include <vector>
28
29namespace 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.
34template<typename KeyT, typename ValueT,
35 typename MapType = DenseMap<KeyT, unsigned>,
36 typename VectorType = std::vector<std::pair<KeyT, ValueT>>>
37class MapVector {
38 MapType Map;
39 VectorType Vector;
40
41 static_assert(
42 std::is_integral_v<typename MapType::mapped_type>,
43 "The mapped_type of the specified Map must be an integral type");
44
45public:
46 using key_type = KeyT;
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.
57 Map.clear();
58 return std::move(Vector);
59 }
60
61 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 Map.reserve(NumEntries);
67 Vector.reserve(NumEntries);
68 }
69
70 iterator begin() { return Vector.begin(); }
71 const_iterator begin() const { return Vector.begin(); }
72 iterator end() { return Vector.end(); }
73 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 reverse_iterator rend() { return Vector.rend(); }
78 const_reverse_iterator rend() const { return Vector.rend(); }
79
80 bool empty() const {
81 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 void clear() {
90 Map.clear();
91 Vector.clear();
92 }
93
95 std::swap(Map, RHS.Map);
96 std::swap(Vector, RHS.Vector);
97 }
98
99 ValueT &operator[](const KeyT &Key) {
100 std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(Key, 0);
101 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
102 auto &I = Result.first->second;
103 if (Result.second) {
104 Vector.push_back(std::make_pair(Key, ValueT()));
105 I = Vector.size() - 1;
106 }
107 return Vector[I].second;
108 }
109
110 // Returns a copy of the value. Only allowed if ValueT is copyable.
111 ValueT lookup(const KeyT &Key) const {
112 static_assert(std::is_copy_constructible_v<ValueT>,
113 "Cannot call lookup() if ValueT is not copyable.");
114 typename MapType::const_iterator Pos = Map.find(Key);
115 return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
116 }
117
118 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
119 std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
120 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
121 auto &I = Result.first->second;
122 if (Result.second) {
123 Vector.push_back(std::make_pair(KV.first, KV.second));
124 I = Vector.size() - 1;
125 return std::make_pair(std::prev(end()), true);
126 }
127 return std::make_pair(begin() + I, false);
128 }
129
130 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
131 // Copy KV.first into the map, then move it into the vector.
132 std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
133 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
134 auto &I = Result.first->second;
135 if (Result.second) {
136 Vector.push_back(std::move(KV));
137 I = Vector.size() - 1;
138 return std::make_pair(std::prev(end()), true);
139 }
140 return std::make_pair(begin() + I, false);
141 }
142
143 size_type count(const KeyT &Key) const {
144 typename MapType::const_iterator Pos = Map.find(Key);
145 return Pos == Map.end()? 0 : 1;
146 }
147
148 iterator find(const KeyT &Key) {
149 typename MapType::const_iterator Pos = Map.find(Key);
150 return Pos == Map.end()? Vector.end() :
151 (Vector.begin() + Pos->second);
152 }
153
154 const_iterator find(const KeyT &Key) const {
155 typename MapType::const_iterator Pos = Map.find(Key);
156 return Pos == Map.end()? Vector.end() :
157 (Vector.begin() + Pos->second);
158 }
159
160 /// Remove the last element from the vector.
161 void pop_back() {
162 typename MapType::iterator Pos = Map.find(Vector.back().first);
163 Map.erase(Pos);
164 Vector.pop_back();
165 }
166
167 /// Remove the element given by Iterator.
168 ///
169 /// Returns an iterator to the element following the one which was removed,
170 /// which may be end().
171 ///
172 /// \note This is a deceivingly expensive operation (linear time). It's
173 /// usually better to use \a remove_if() if possible.
174 typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
175 Map.erase(Iterator->first);
176 auto Next = Vector.erase(Iterator);
177 if (Next == Vector.end())
178 return Next;
179
180 // Update indices in the map.
181 size_t Index = Next - Vector.begin();
182 for (auto &I : Map) {
183 assert(I.second != Index && "Index was already erased!");
184 if (I.second > Index)
185 --I.second;
186 }
187 return Next;
188 }
189
190 /// Remove all elements with the key value Key.
191 ///
192 /// Returns the number of elements removed.
193 size_type erase(const KeyT &Key) {
194 auto Iterator = find(Key);
195 if (Iterator == end())
196 return 0;
197 erase(Iterator);
198 return 1;
199 }
200
201 /// Remove the elements that match the predicate.
202 ///
203 /// Erase all elements that match \c Pred in a single pass. Takes linear
204 /// time.
205 template <class Predicate> void remove_if(Predicate Pred);
206};
207
208template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
209template <class Function>
211 auto O = Vector.begin();
212 for (auto I = O, E = Vector.end(); I != E; ++I) {
213 if (Pred(*I)) {
214 // Erase from the map.
215 Map.erase(I->first);
216 continue;
217 }
218
219 if (I != O) {
220 // Move the value and update the index in the map.
221 *O = std::move(*I);
222 Map[O->first] = O - Vector.begin();
223 }
224 ++O;
225 }
226 // Erase trailing entries in the vector.
227 Vector.erase(O, Vector.end());
228}
229
230/// A MapVector that performs no allocations if smaller than a certain
231/// size.
232template <typename KeyT, typename ValueT, unsigned N>
234 : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
235 SmallVector<std::pair<KeyT, ValueT>, N>> {
236};
237
238} // end namespace llvm
239
240#endif // LLVM_ADT_MAPVECTOR_H
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
Value * RHS
This class implements a map that also provides access to all stored values in a deterministic order.
Definition: MapVector.h:37
size_type count(const KeyT &Key) const
Definition: MapVector.h:143
typename VectorType::iterator iterator
Definition: MapVector.h:50
iterator end()
Definition: MapVector.h:72
void pop_back()
Remove the last element from the vector.
Definition: MapVector.h:161
const_reverse_iterator rbegin() const
Definition: MapVector.h:76
void swap(MapVector &RHS)
Definition: MapVector.h:94
reverse_iterator rend()
Definition: MapVector.h:77
ValueT & operator[](const KeyT &Key)
Definition: MapVector.h:99
const_iterator end() const
Definition: MapVector.h:73
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
Definition: MapVector.h:174
VectorType takeVector()
Clear the MapVector and return the underlying vector.
Definition: MapVector.h:56
typename VectorType::size_type size_type
Definition: MapVector.h:48
const std::pair< KeyT, ValueT > & back() const
Definition: MapVector.h:87
const std::pair< KeyT, ValueT > & front() const
Definition: MapVector.h:85
typename VectorType::const_reverse_iterator const_reverse_iterator
Definition: MapVector.h:53
typename VectorType::value_type value_type
Definition: MapVector.h:47
iterator find(const KeyT &Key)
Definition: MapVector.h:148
void remove_if(Predicate Pred)
Remove the elements that match the predicate.
bool empty() const
Definition: MapVector.h:80
const_iterator begin() const
Definition: MapVector.h:71
iterator begin()
Definition: MapVector.h:70
const_iterator find(const KeyT &Key) const
Definition: MapVector.h:154
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: MapVector.h:118
ValueT lookup(const KeyT &Key) const
Definition: MapVector.h:111
void reserve(size_type NumEntries)
Grow the MapVector so that it can contain at least NumEntries items before resizing again.
Definition: MapVector.h:65
typename VectorType::reverse_iterator reverse_iterator
Definition: MapVector.h:52
size_type size() const
Definition: MapVector.h:61
size_type erase(const KeyT &Key)
Remove all elements with the key value Key.
Definition: MapVector.h:193
typename VectorType::const_iterator const_iterator
Definition: MapVector.h:51
std::pair< KeyT, ValueT > & front()
Definition: MapVector.h:84
void clear()
Definition: MapVector.h:89
std::pair< iterator, bool > insert(std::pair< KeyT, ValueT > &&KV)
Definition: MapVector.h:130
const_reverse_iterator rend() const
Definition: MapVector.h:78
reverse_iterator rbegin()
Definition: MapVector.h:75
std::pair< KeyT, ValueT > & back()
Definition: MapVector.h:86
Base class of all SIMD vector types.
Definition: DerivedTypes.h:389
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:235