1 //===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- 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 // This file implements a map that provides insertion order iteration. The 11 // interface is purposefully minimal. The key is assumed to be cheap to copy 12 // and 2 copies are kept, one for indexing in a DenseMap, one for iteration in 13 // a std::vector. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #ifndef LLVM_ADT_MAPVECTOR_H 18 #define LLVM_ADT_MAPVECTOR_H 19 20 #include "llvm/ADT/DenseMap.h" 21 #include <vector> 22 23 namespace llvm { 24 25 /// This class implements a map that also provides access to all stored values 26 /// in a deterministic order. The values are kept in a std::vector and the 27 /// mapping is done with DenseMap from Keys to indexes in that vector. 28 template<typename KeyT, typename ValueT, 29 typename MapType = llvm::DenseMap<KeyT, unsigned>, 30 typename VectorType = std::vector<std::pair<KeyT, ValueT> > > 31 class MapVector { 32 typedef typename VectorType::size_type size_type; 33 34 MapType Map; 35 VectorType Vector; 36 37 public: 38 typedef typename VectorType::iterator iterator; 39 typedef typename VectorType::const_iterator const_iterator; 40 size()41 size_type size() const { 42 return Vector.size(); 43 } 44 begin()45 iterator begin() { 46 return Vector.begin(); 47 } 48 begin()49 const_iterator begin() const { 50 return Vector.begin(); 51 } 52 end()53 iterator end() { 54 return Vector.end(); 55 } 56 end()57 const_iterator end() const { 58 return Vector.end(); 59 } 60 empty()61 bool empty() const { 62 return Vector.empty(); 63 } 64 front()65 std::pair<KeyT, ValueT> &front() { return Vector.front(); } front()66 const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } back()67 std::pair<KeyT, ValueT> &back() { return Vector.back(); } back()68 const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } 69 clear()70 void clear() { 71 Map.clear(); 72 Vector.clear(); 73 } 74 75 ValueT &operator[](const KeyT &Key) { 76 std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0); 77 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 78 unsigned &I = Result.first->second; 79 if (Result.second) { 80 Vector.push_back(std::make_pair(Key, ValueT())); 81 I = Vector.size() - 1; 82 } 83 return Vector[I].second; 84 } 85 lookup(const KeyT & Key)86 ValueT lookup(const KeyT &Key) const { 87 typename MapType::const_iterator Pos = Map.find(Key); 88 return Pos == Map.end()? ValueT() : Vector[Pos->second].second; 89 } 90 insert(const std::pair<KeyT,ValueT> & KV)91 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 92 std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0); 93 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 94 unsigned &I = Result.first->second; 95 if (Result.second) { 96 Vector.push_back(std::make_pair(KV.first, KV.second)); 97 I = Vector.size() - 1; 98 return std::make_pair(std::prev(end()), true); 99 } 100 return std::make_pair(begin() + I, false); 101 } 102 count(const KeyT & Key)103 size_type count(const KeyT &Key) const { 104 typename MapType::const_iterator Pos = Map.find(Key); 105 return Pos == Map.end()? 0 : 1; 106 } 107 find(const KeyT & Key)108 iterator find(const KeyT &Key) { 109 typename MapType::const_iterator Pos = Map.find(Key); 110 return Pos == Map.end()? Vector.end() : 111 (Vector.begin() + Pos->second); 112 } 113 find(const KeyT & Key)114 const_iterator find(const KeyT &Key) const { 115 typename MapType::const_iterator Pos = Map.find(Key); 116 return Pos == Map.end()? Vector.end() : 117 (Vector.begin() + Pos->second); 118 } 119 120 /// \brief Remove the last element from the vector. pop_back()121 void pop_back() { 122 typename MapType::iterator Pos = Map.find(Vector.back().first); 123 Map.erase(Pos); 124 Vector.pop_back(); 125 } 126 127 /// \brief Remove the element given by Iterator. 128 /// Returns an iterator to the element following the one which was removed, 129 /// which may be end(). erase(typename VectorType::iterator Iterator)130 typename VectorType::iterator erase(typename VectorType::iterator Iterator) { 131 typename MapType::iterator MapIterator = Map.find(Iterator->first); 132 Map.erase(MapIterator); 133 return Vector.erase(Iterator); 134 } 135 }; 136 137 } 138 139 #endif 140