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::size_type size_type; 34 35 MapType Map; 36 VectorType Vector; 37 38 public: 39 typedef typename VectorType::iterator iterator; 40 typedef typename VectorType::const_iterator const_iterator; 41 typedef typename VectorType::reverse_iterator reverse_iterator; 42 typedef typename VectorType::const_reverse_iterator const_reverse_iterator; 43 44 size_type size() const { return Vector.size(); } 45 46 iterator begin() { return Vector.begin(); } 47 const_iterator begin() const { return Vector.begin(); } 48 iterator end() { return Vector.end(); } 49 const_iterator end() const { return Vector.end(); } 50 51 reverse_iterator rbegin() { return Vector.rbegin(); } 52 const_reverse_iterator rbegin() const { return Vector.rbegin(); } 53 reverse_iterator rend() { return Vector.rend(); } 54 const_reverse_iterator rend() const { return Vector.rend(); } 55 56 bool empty() const { 57 return Vector.empty(); 58 } 59 60 std::pair<KeyT, ValueT> &front() { return Vector.front(); } 61 const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } 62 std::pair<KeyT, ValueT> &back() { return Vector.back(); } 63 const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } 64 65 void clear() { 66 Map.clear(); 67 Vector.clear(); 68 } 69 70 void swap(MapVector &RHS) { 71 std::swap(Map, RHS.Map); 72 std::swap(Vector, RHS.Vector); 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 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 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 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 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 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. 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 /// 129 /// Returns an iterator to the element following the one which was removed, 130 /// which may be end(). 131 /// 132 /// \note This is a deceivingly expensive operation (linear time). It's 133 /// usually better to use \a remove_if() if possible. 134 typename VectorType::iterator erase(typename VectorType::iterator Iterator) { 135 Map.erase(Iterator->first); 136 auto Next = Vector.erase(Iterator); 137 if (Next == Vector.end()) 138 return Next; 139 140 // Update indices in the map. 141 size_t Index = Next - Vector.begin(); 142 for (auto &I : Map) { 143 assert(I.second != Index && "Index was already erased!"); 144 if (I.second > Index) 145 --I.second; 146 } 147 return Next; 148 } 149 150 /// \brief Remove all elements with the key value Key. 151 /// 152 /// Returns the number of elements removed. 153 size_type erase(const KeyT &Key) { 154 auto Iterator = find(Key); 155 if (Iterator == end()) 156 return 0; 157 erase(Iterator); 158 return 1; 159 } 160 161 /// \brief Remove the elements that match the predicate. 162 /// 163 /// Erase all elements that match \c Pred in a single pass. Takes linear 164 /// time. 165 template <class Predicate> void remove_if(Predicate Pred); 166 }; 167 168 template <typename KeyT, typename ValueT, typename MapType, typename VectorType> 169 template <class Function> 170 void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { 171 auto O = Vector.begin(); 172 for (auto I = O, E = Vector.end(); I != E; ++I) { 173 if (Pred(*I)) { 174 // Erase from the map. 175 Map.erase(I->first); 176 continue; 177 } 178 179 if (I != O) { 180 // Move the value and update the index in the map. 181 *O = std::move(*I); 182 Map[O->first] = O - Vector.begin(); 183 } 184 ++O; 185 } 186 // Erase trailing entries in the vector. 187 Vector.erase(O, Vector.end()); 188 } 189 190 /// \brief A MapVector that performs no allocations if smaller than a certain 191 /// size. 192 template <typename KeyT, typename ValueT, unsigned N> 193 struct SmallMapVector 194 : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>, 195 SmallVector<std::pair<KeyT, ValueT>, N>> { 196 }; 197 198 } // end namespace llvm 199 200 #endif 201
