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 "llvm/ADT/SmallVector.h" 22 #include <vector> 23 24 namespace llvm { 25 26 /// This class implements a map that also provides access to all stored values 27 /// in a deterministic order. The values are kept in a std::vector and the 28 /// mapping is done with DenseMap from Keys to indexes in that vector. 29 template<typename KeyT, typename ValueT, 30 typename MapType = llvm::DenseMap<KeyT, unsigned>, 31 typename VectorType = std::vector<std::pair<KeyT, ValueT> > > 32 class MapVector { 33 typedef typename VectorType::value_type value_type; 34 typedef typename VectorType::size_type size_type; 35 36 MapType Map; 37 VectorType Vector; 38 39 public: 40 typedef typename VectorType::iterator iterator; 41 typedef typename VectorType::const_iterator const_iterator; 42 typedef typename VectorType::reverse_iterator reverse_iterator; 43 typedef typename VectorType::const_reverse_iterator const_reverse_iterator; 44 45 /// Clear the MapVector and return the underlying vector. 46 VectorType takeVector() { 47 Map.clear(); 48 return std::move(Vector); 49 } 50 51 size_type size() const { return Vector.size(); } 52 53 iterator begin() { return Vector.begin(); } 54 const_iterator begin() const { return Vector.begin(); } 55 iterator end() { return Vector.end(); } 56 const_iterator end() const { return Vector.end(); } 57 58 reverse_iterator rbegin() { return Vector.rbegin(); } 59 const_reverse_iterator rbegin() const { return Vector.rbegin(); } 60 reverse_iterator rend() { return Vector.rend(); } 61 const_reverse_iterator rend() const { return Vector.rend(); } 62 63 bool empty() const { 64 return Vector.empty(); 65 } 66 67 std::pair<KeyT, ValueT> &front() { return Vector.front(); } 68 const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } 69 std::pair<KeyT, ValueT> &back() { return Vector.back(); } 70 const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } 71 72 void clear() { 73 Map.clear(); 74 Vector.clear(); 75 } 76 77 void swap(MapVector &RHS) { 78 std::swap(Map, RHS.Map); 79 std::swap(Vector, RHS.Vector); 80 } 81 82 ValueT &operator[](const KeyT &Key) { 83 std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0); 84 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 85 unsigned &I = Result.first->second; 86 if (Result.second) { 87 Vector.push_back(std::make_pair(Key, ValueT())); 88 I = Vector.size() - 1; 89 } 90 return Vector[I].second; 91 } 92 93 // Returns a copy of the value. Only allowed if ValueT is copyable. 94 ValueT lookup(const KeyT &Key) const { 95 static_assert(std::is_copy_constructible<ValueT>::value, 96 "Cannot call lookup() if ValueT is not copyable."); 97 typename MapType::const_iterator Pos = Map.find(Key); 98 return Pos == Map.end()? ValueT() : Vector[Pos->second].second; 99 } 100 101 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 102 std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0); 103 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 104 unsigned &I = Result.first->second; 105 if (Result.second) { 106 Vector.push_back(std::make_pair(KV.first, KV.second)); 107 I = Vector.size() - 1; 108 return std::make_pair(std::prev(end()), true); 109 } 110 return std::make_pair(begin() + I, false); 111 } 112 113 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { 114 // Copy KV.first into the map, then move it into the vector. 115 std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0); 116 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 117 unsigned &I = Result.first->second; 118 if (Result.second) { 119 Vector.push_back(std::move(KV)); 120 I = Vector.size() - 1; 121 return std::make_pair(std::prev(end()), true); 122 } 123 return std::make_pair(begin() + I, false); 124 } 125 126 size_type count(const KeyT &Key) const { 127 typename MapType::const_iterator Pos = Map.find(Key); 128 return Pos == Map.end()? 0 : 1; 129 } 130 131 iterator find(const KeyT &Key) { 132 typename MapType::const_iterator Pos = Map.find(Key); 133 return Pos == Map.end()? Vector.end() : 134 (Vector.begin() + Pos->second); 135 } 136 137 const_iterator find(const KeyT &Key) const { 138 typename MapType::const_iterator Pos = Map.find(Key); 139 return Pos == Map.end()? Vector.end() : 140 (Vector.begin() + Pos->second); 141 } 142 143 /// \brief Remove the last element from the vector. 144 void pop_back() { 145 typename MapType::iterator Pos = Map.find(Vector.back().first); 146 Map.erase(Pos); 147 Vector.pop_back(); 148 } 149 150 /// \brief Remove the element given by Iterator. 151 /// 152 /// Returns an iterator to the element following the one which was removed, 153 /// which may be end(). 154 /// 155 /// \note This is a deceivingly expensive operation (linear time). It's 156 /// usually better to use \a remove_if() if possible. 157 typename VectorType::iterator erase(typename VectorType::iterator Iterator) { 158 Map.erase(Iterator->first); 159 auto Next = Vector.erase(Iterator); 160 if (Next == Vector.end()) 161 return Next; 162 163 // Update indices in the map. 164 size_t Index = Next - Vector.begin(); 165 for (auto &I : Map) { 166 assert(I.second != Index && "Index was already erased!"); 167 if (I.second > Index) 168 --I.second; 169 } 170 return Next; 171 } 172 173 /// \brief Remove all elements with the key value Key. 174 /// 175 /// Returns the number of elements removed. 176 size_type erase(const KeyT &Key) { 177 auto Iterator = find(Key); 178 if (Iterator == end()) 179 return 0; 180 erase(Iterator); 181 return 1; 182 } 183 184 /// \brief Remove the elements that match the predicate. 185 /// 186 /// Erase all elements that match \c Pred in a single pass. Takes linear 187 /// time. 188 template <class Predicate> void remove_if(Predicate Pred); 189 }; 190 191 template <typename KeyT, typename ValueT, typename MapType, typename VectorType> 192 template <class Function> 193 void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { 194 auto O = Vector.begin(); 195 for (auto I = O, E = Vector.end(); I != E; ++I) { 196 if (Pred(*I)) { 197 // Erase from the map. 198 Map.erase(I->first); 199 continue; 200 } 201 202 if (I != O) { 203 // Move the value and update the index in the map. 204 *O = std::move(*I); 205 Map[O->first] = O - Vector.begin(); 206 } 207 ++O; 208 } 209 // Erase trailing entries in the vector. 210 Vector.erase(O, Vector.end()); 211 } 212 213 /// \brief A MapVector that performs no allocations if smaller than a certain 214 /// size. 215 template <typename KeyT, typename ValueT, unsigned N> 216 struct SmallMapVector 217 : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>, 218 SmallVector<std::pair<KeyT, ValueT>, N>> { 219 }; 220 221 } // end namespace llvm 222 223 #endif 224
