LLVM 20.0.0git
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
18namespace llvm {
19
20/// An associative container with fast insertion-order (deterministic)
21/// iteration over its elements. Plus the special blot operation.
22template <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
31public:
32#ifdef EXPENSIVE_CHECKS
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
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())
An associative container with fast insertion-order (deterministic) iteration over its elements.
Definition: BlotMapVector.h:22
const_iterator begin() const
Definition: BlotMapVector.h:52
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
iterator find(const KeyT &Key)
Definition: BlotMapVector.h:79
typename VectorTy::iterator iterator
Definition: BlotMapVector.h:47
typename VectorTy::const_iterator const_iterator
Definition: BlotMapVector.h:48
bool empty() const
ValueT & operator[](const KeyT &Arg)
Definition: BlotMapVector.h:55
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &InsertPair)
Definition: BlotMapVector.h:67
const_iterator end() const
Definition: BlotMapVector.h:53
const_iterator find(const KeyT &Key) const
Definition: BlotMapVector.h:86
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18