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 18 namespace llvm { 19 20 /// An associative container with fast insertion-order (deterministic) 21 /// iteration over its elements. Plus the special blot operation. 22 template <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 31 public: 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