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