LLVM  10.0.0svn
BlotMapVector.h
Go to the documentation of this file.
1 //===- BlotMapVector.h - A MapVector with the blot operation ----*- 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 #ifndef LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H
10 #define LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H
11 
12 #include "llvm/ADT/DenseMap.h"
13 #include <cassert>
14 #include <cstddef>
15 #include <utility>
16 #include <vector>
17 
18 namespace llvm {
19 
20 /// An associative container with fast insertion-order (deterministic)
21 /// iteration over its elements. Plus the special blot operation.
22 template <class KeyT, class ValueT> class BlotMapVector {
23  /// Map keys to indices in Vector.
25  MapTy Map;
26 
27  /// Keys and values.
28  using VectorTy = std::vector<std::pair<KeyT, ValueT>>;
29  VectorTy Vector;
30 
31 public:
32 #ifdef EXPENSIVE_CHECKS
33  ~BlotMapVector() {
34  assert(Vector.size() >= Map.size()); // May differ due to blotting.
35  for (typename MapTy::const_iterator I = Map.begin(), E = Map.end(); I != E;
36  ++I) {
37  assert(I->second < Vector.size());
38  assert(Vector[I->second].first == I->first);
39  }
40  for (typename VectorTy::const_iterator I = Vector.begin(), E = Vector.end();
41  I != E; ++I)
42  assert(!I->first || (Map.count(I->first) &&
43  Map[I->first] == size_t(I - Vector.begin())));
44  }
45 #endif
46 
47  using iterator = typename VectorTy::iterator;
48  using const_iterator = typename VectorTy::const_iterator;
49 
50  iterator begin() { return Vector.begin(); }
51  iterator end() { return Vector.end(); }
52  const_iterator begin() const { return Vector.begin(); }
53  const_iterator end() const { return Vector.end(); }
54 
55  ValueT &operator[](const KeyT &Arg) {
56  std::pair<typename MapTy::iterator, bool> Pair =
57  Map.insert(std::make_pair(Arg, size_t(0)));
58  if (Pair.second) {
59  size_t Num = Vector.size();
60  Pair.first->second = Num;
61  Vector.push_back(std::make_pair(Arg, ValueT()));
62  return Vector[Num].second;
63  }
64  return Vector[Pair.first->second].second;
65  }
66 
67  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &InsertPair) {
68  std::pair<typename MapTy::iterator, bool> Pair =
69  Map.insert(std::make_pair(InsertPair.first, size_t(0)));
70  if (Pair.second) {
71  size_t Num = Vector.size();
72  Pair.first->second = Num;
73  Vector.push_back(InsertPair);
74  return std::make_pair(Vector.begin() + Num, true);
75  }
76  return std::make_pair(Vector.begin() + Pair.first->second, false);
77  }
78 
79  iterator find(const KeyT &Key) {
80  typename MapTy::iterator It = Map.find(Key);
81  if (It == Map.end())
82  return Vector.end();
83  return Vector.begin() + It->second;
84  }
85 
86  const_iterator find(const KeyT &Key) const {
87  typename MapTy::const_iterator It = Map.find(Key);
88  if (It == Map.end())
89  return Vector.end();
90  return Vector.begin() + It->second;
91  }
92 
93  /// This is similar to erase, but instead of removing the element from the
94  /// vector, it just zeros out the key in the vector. This leaves iterators
95  /// intact, but clients must be prepared for zeroed-out keys when iterating.
96  void blot(const KeyT &Key) {
97  typename MapTy::iterator It = Map.find(Key);
98  if (It == Map.end())
99  return;
100  Vector[It->second].first = KeyT();
101  Map.erase(It);
102  }
103 
104  void clear() {
105  Map.clear();
106  Vector.clear();
107  }
108 
109  bool empty() const {
110  assert(Map.empty() == Vector.empty());
111  return Map.empty();
112  }
113 };
114 
115 } // end namespace llvm
116 
117 #endif // LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H
const_iterator end() const
Definition: BlotMapVector.h:53
This class represents lattice values for constants.
Definition: AllocatorList.h:23
typename VectorTy::const_iterator const_iterator
Definition: BlotMapVector.h:48
ValueT & operator[](const KeyT &Arg)
Definition: BlotMapVector.h:55
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
Key
PAL metadata keys.
const_iterator begin() const
Definition: BlotMapVector.h:52
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:176
iterator find(const KeyT &Key)
Definition: BlotMapVector.h:79
bool erase(const KeyT &Val)
Definition: DenseMap.h:298
const_iterator find(const KeyT &Key) const
Definition: BlotMapVector.h:86
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &InsertPair)
Definition: BlotMapVector.h:67
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
unsigned size() const
Definition: DenseMap.h:125
An associative container with fast insertion-order (deterministic) iteration over its elements...
Definition: BlotMapVector.h:22
typename VectorTy::iterator iterator
Definition: BlotMapVector.h:47
bool empty() const
iterator begin()
Definition: DenseMap.h:99
#define I(x, y, z)
Definition: MD5.cpp:58
iterator end()
Definition: DenseMap.h:108
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:122
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void blot(const KeyT &Key)
This is similar to erase, but instead of removing the element from the vector, it just zeros out the ...
Definition: BlotMapVector.h:96