1 //===- BlotMapVector.h - A MapVector with the blot operation ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H
11 #define LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H
13 #include "llvm/ADT/DenseMap.h"
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.
25 using MapTy = DenseMap<KeyT, size_t>;
29 using VectorTy = std::vector<std::pair<KeyT, ValueT>>;
33 #ifdef EXPENSIVE_CHECKS
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;
38 assert(I->second < Vector.size());
39 assert(Vector[I->second].first == I->first);
41 for (typename VectorTy::const_iterator I = Vector.begin(), E = Vector.end();
43 assert(!I->first || (Map.count(I->first) &&
44 Map[I->first] == size_t(I - Vector.begin())));
48 using iterator = typename VectorTy::iterator;
49 using const_iterator = typename VectorTy::const_iterator;
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(); }
56 ValueT &operator[](const KeyT &Arg) {
57 std::pair<typename MapTy::iterator, bool> Pair =
58 Map.insert(std::make_pair(Arg, size_t(0)));
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;
65 return Vector[Pair.first->second].second;
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)));
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);
77 return std::make_pair(Vector.begin() + Pair.first->second, false);
80 iterator find(const KeyT &Key) {
81 typename MapTy::iterator It = Map.find(Key);
84 return Vector.begin() + It->second;
87 const_iterator find(const KeyT &Key) const {
88 typename MapTy::const_iterator It = Map.find(Key);
91 return Vector.begin() + It->second;
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);
101 Vector[It->second].first = KeyT();
111 assert(Map.empty() == Vector.empty());
116 } // end namespace llvm
118 #endif // LLVM_LIB_TRANSFORMS_OBJCARC_BLOTMAPVECTOR_H