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.
24 using MapTy = DenseMap<KeyT, size_t>;
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
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 = Map.try_emplace(Arg);
57 if (Pair.second) {
58 size_t Num = Vector.size();
59 Pair.first->second = Num;
60 Vector.push_back(std::make_pair(Arg, ValueT()));
61 return Vector[Num].second;
62 }
63 return Vector[Pair.first->second].second;
64 }
65
66 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &InsertPair) {
67 std::pair<typename MapTy::iterator, bool> Pair =
68 Map.insert(std::make_pair(InsertPair.first, size_t(0)));
69 if (Pair.second) {
70 size_t Num = Vector.size();
71 Pair.first->second = Num;
72 Vector.push_back(InsertPair);
73 return std::make_pair(Vector.begin() + Num, true);
74 }
75 return std::make_pair(Vector.begin() + Pair.first->second, false);
76 }
77
78 iterator find(const KeyT &Key) {
79 typename MapTy::iterator It = Map.find(Key);
80 if (It == Map.end())
81 return Vector.end();
82 return Vector.begin() + It->second;
83 }
84
85 const_iterator find(const KeyT &Key) const {
86 typename MapTy::const_iterator It = Map.find(Key);
87 if (It == Map.end())
88 return Vector.end();
89 return Vector.begin() + It->second;
90 }
91
92 /// This is similar to erase, but instead of removing the element from the
93 /// vector, it just zeros out the key in the vector. This leaves iterators
94 /// intact, but clients must be prepared for zeroed-out keys when iterating.
95 void blot(const KeyT &Key) {
96 typename MapTy::iterator It = Map.find(Key);
97 if (It == Map.end())
98 return;
99 Vector[It->second].first = KeyT();
100 Map.erase(It);
101 }
102
103 void clear() {
104 Map.clear();
105 Vector.clear();
106 }
107
108 bool empty() const {
109 assert(Map.empty() == Vector.empty());
110 return Map.empty();
111 }
112};
113
114} // end namespace llvm
115
116#endif // LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H
117