17#ifndef LLVM_ADT_MAPVECTOR_H
18#define LLVM_ADT_MAPVECTOR_H
35 typename MapType = DenseMap<KeyT, unsigned>,
36 typename VectorType = std::vector<std::pair<KeyT, ValueT>>>
42 std::is_integral_v<typename MapType::mapped_type>,
43 "The mapped_type of the specified Map must be an integral type");
50 using iterator =
typename VectorType::iterator;
66 Map.reserve(NumEntries);
67 Vector.reserve(NumEntries);
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(); }
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;
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;
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;
123 Vector.push_back(std::make_pair(KV.first, KV.second));
125 return std::make_pair(std::prev(
end()),
true);
127 return std::make_pair(
begin() +
I,
false);
130 std::pair<iterator, bool>
insert(std::pair<KeyT, ValueT> &&KV) {
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;
136 Vector.push_back(std::move(KV));
138 return std::make_pair(std::prev(
end()),
true);
140 return std::make_pair(
begin() +
I,
false);
143 bool contains(
const KeyT &Key)
const {
return Map.find(Key) != Map.end(); }
148 typename MapType::const_iterator Pos = Map.find(Key);
149 return Pos == Map.end()?
Vector.end() :
150 (
Vector.begin() + Pos->second);
154 typename MapType::const_iterator Pos = Map.find(Key);
155 return Pos == Map.end()?
Vector.end() :
156 (
Vector.begin() + Pos->second);
161 typename MapType::iterator Pos = Map.find(
Vector.back().first);
173 typename VectorType::iterator
erase(
typename VectorType::iterator Iterator) {
174 Map.erase(Iterator->first);
175 auto Next =
Vector.erase(Iterator);
181 for (
auto &
I : Map) {
182 assert(
I.second !=
Index &&
"Index was already erased!");
193 auto Iterator =
find(Key);
194 if (Iterator ==
end())
204 template <
class Predicate>
void remove_if(Predicate Pred);
207template <
typename KeyT,
typename ValueT,
typename MapType,
typename VectorType>
208template <
class Function>
221 Map[O->first] = O -
Vector.begin();
231template <
typename KeyT,
typename ValueT,
unsigned N>
233 :
MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
234 SmallVector<std::pair<KeyT, ValueT>, N>> {
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This class implements a map that also provides access to all stored values in a deterministic order.
size_type count(const KeyT &Key) const
typename VectorType::iterator iterator
void pop_back()
Remove the last element from the vector.
const_reverse_iterator rbegin() const
void swap(MapVector &RHS)
ValueT & operator[](const KeyT &Key)
const_iterator end() const
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
VectorType takeVector()
Clear the MapVector and return the underlying vector.
typename VectorType::size_type size_type
const std::pair< KeyT, ValueT > & back() const
const std::pair< KeyT, ValueT > & front() const
typename VectorType::const_reverse_iterator const_reverse_iterator
typename VectorType::value_type value_type
iterator find(const KeyT &Key)
void remove_if(Predicate Pred)
Remove the elements that match the predicate.
bool contains(const KeyT &Key) const
const_iterator begin() const
const_iterator find(const KeyT &Key) const
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
ValueT lookup(const KeyT &Key) const
void reserve(size_type NumEntries)
Grow the MapVector so that it can contain at least NumEntries items before resizing again.
typename VectorType::reverse_iterator reverse_iterator
size_type erase(const KeyT &Key)
Remove all elements with the key value Key.
typename VectorType::const_iterator const_iterator
std::pair< KeyT, ValueT > & front()
std::pair< iterator, bool > insert(std::pair< KeyT, ValueT > &&KV)
const_reverse_iterator rend() const
reverse_iterator rbegin()
std::pair< KeyT, ValueT > & back()
Base class of all SIMD vector types.
This is an optimization pass for GlobalISel generic memory operations.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A MapVector that performs no allocations if smaller than a certain size.