1 //===- BlotMapVector.h - A MapVector with the blot operation -*- C++ -*----===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "llvm/ADT/DenseMap.h" 11 #include <vector> 12 #include <algorithm> 13 14 namespace llvm { 15 /// \brief An associative container with fast insertion-order (deterministic) 16 /// iteration over its elements. Plus the special blot operation. 17 template <class KeyT, class ValueT> class BlotMapVector { 18 /// Map keys to indices in Vector. 19 typedef DenseMap<KeyT, size_t> MapTy; 20 MapTy Map; 21 22 typedef std::vector<std::pair<KeyT, ValueT>> VectorTy; 23 /// Keys and values. 24 VectorTy Vector; 25 26 public: 27 typedef typename VectorTy::iterator iterator; 28 typedef typename VectorTy::const_iterator const_iterator; 29 iterator begin() { return Vector.begin(); } 30 iterator end() { return Vector.end(); } 31 const_iterator begin() const { return Vector.begin(); } 32 const_iterator end() const { return Vector.end(); } 33 34 #ifdef XDEBUG 35 ~BlotMapVector() { 36 assert(Vector.size() >= Map.size()); // May differ due to blotting. 37 for (typename MapTy::const_iterator I = Map.begin(), E = Map.end(); I != E; 38 ++I) { 39 assert(I->second < Vector.size()); 40 assert(Vector[I->second].first == I->first); 41 } 42 for (typename VectorTy::const_iterator I = Vector.begin(), E = Vector.end(); 43 I != E; ++I) 44 assert(!I->first || (Map.count(I->first) && 45 Map[I->first] == size_t(I - Vector.begin()))); 46 } 47 #endif 48 49 ValueT &operator[](const KeyT &Arg) { 50 std::pair<typename MapTy::iterator, bool> Pair = 51 Map.insert(std::make_pair(Arg, size_t(0))); 52 if (Pair.second) { 53 size_t Num = Vector.size(); 54 Pair.first->second = Num; 55 Vector.push_back(std::make_pair(Arg, ValueT())); 56 return Vector[Num].second; 57 } 58 return Vector[Pair.first->second].second; 59 } 60 61 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &InsertPair) { 62 std::pair<typename MapTy::iterator, bool> Pair = 63 Map.insert(std::make_pair(InsertPair.first, size_t(0))); 64 if (Pair.second) { 65 size_t Num = Vector.size(); 66 Pair.first->second = Num; 67 Vector.push_back(InsertPair); 68 return std::make_pair(Vector.begin() + Num, true); 69 } 70 return std::make_pair(Vector.begin() + Pair.first->second, false); 71 } 72 73 iterator find(const KeyT &Key) { 74 typename MapTy::iterator It = Map.find(Key); 75 if (It == Map.end()) 76 return Vector.end(); 77 return Vector.begin() + It->second; 78 } 79 80 const_iterator find(const KeyT &Key) const { 81 typename MapTy::const_iterator It = Map.find(Key); 82 if (It == Map.end()) 83 return Vector.end(); 84 return Vector.begin() + It->second; 85 } 86 87 /// This is similar to erase, but instead of removing the element from the 88 /// vector, it just zeros out the key in the vector. This leaves iterators 89 /// intact, but clients must be prepared for zeroed-out keys when iterating. 90 void blot(const KeyT &Key) { 91 typename MapTy::iterator It = Map.find(Key); 92 if (It == Map.end()) 93 return; 94 Vector[It->second].first = KeyT(); 95 Map.erase(It); 96 } 97 98 void clear() { 99 Map.clear(); 100 Vector.clear(); 101 } 102 103 bool empty() const { 104 assert(Map.empty() == Vector.empty()); 105 return Map.empty(); 106 } 107 }; 108 } // 109
