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 ~BlotMapVector()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 begin()50 iterator begin() { return Vector.begin(); } end()51 iterator end() { return Vector.end(); } begin()52 const_iterator begin() const { return Vector.begin(); } end()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 insert(const std::pair<KeyT,ValueT> & InsertPair)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 find(const KeyT & Key)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 find(const KeyT & Key)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. blot(const KeyT & Key)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 clear()103 void clear() { 104 Map.clear(); 105 Vector.clear(); 106 } 107 empty()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