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