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 =
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
118