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 bool contains(const KeyT &Key) const { return Map.find(Key) != Map.end(); }
144
145 size_type count(const KeyT &Key) const { return contains(Key) ? 1 : 0; }
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
207template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
208template <class Function>
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.
231template <typename KeyT, typename ValueT, unsigned N>
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
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:145
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:160
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:173
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:147
void remove_if(Predicate Pred)
Remove the elements that match the predicate.
bool contains(const KeyT &Key) const
Definition: MapVector.h:143
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:153
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:192
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:400
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:860
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:234