MapVector.h revision 276479
1273562Smarcel//===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- C++ -*-===// 2273562Smarcel// 3273562Smarcel// The LLVM Compiler Infrastructure 4273562Smarcel// 5273562Smarcel// This file is distributed under the University of Illinois Open Source 6273562Smarcel// License. See LICENSE.TXT for details. 7273562Smarcel// 8273562Smarcel//===----------------------------------------------------------------------===// 9273562Smarcel// 10273562Smarcel// This file implements a map that provides insertion order iteration. The 11273562Smarcel// interface is purposefully minimal. The key is assumed to be cheap to copy 12273562Smarcel// and 2 copies are kept, one for indexing in a DenseMap, one for iteration in 13273562Smarcel// a std::vector. 14273562Smarcel// 15273562Smarcel//===----------------------------------------------------------------------===// 16273562Smarcel 17273562Smarcel#ifndef LLVM_ADT_MAPVECTOR_H 18273562Smarcel#define LLVM_ADT_MAPVECTOR_H 19273562Smarcel 20273562Smarcel#include "llvm/ADT/DenseMap.h" 21273562Smarcel#include <vector> 22273562Smarcel 23273562Smarcelnamespace 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. 28template<typename KeyT, typename ValueT, 29 typename MapType = llvm::DenseMap<KeyT, unsigned>, 30 typename VectorType = std::vector<std::pair<KeyT, ValueT> > > 31class MapVector { 32 typedef typename VectorType::size_type size_type; 33 34 MapType Map; 35 VectorType Vector; 36 37public: 38 typedef typename VectorType::iterator iterator; 39 typedef typename VectorType::const_iterator const_iterator; 40 41 size_type size() const { 42 return Vector.size(); 43 } 44 45 iterator begin() { 46 return Vector.begin(); 47 } 48 49 const_iterator begin() const { 50 return Vector.begin(); 51 } 52 53 iterator end() { 54 return Vector.end(); 55 } 56 57 const_iterator end() const { 58 return Vector.end(); 59 } 60 61 bool empty() const { 62 return Vector.empty(); 63 } 64 65 std::pair<KeyT, ValueT> &front() { return Vector.front(); } 66 const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } 67 std::pair<KeyT, ValueT> &back() { return Vector.back(); } 68 const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } 69 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 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 the elements that match the predicate. 151 /// 152 /// Erase all elements that match \c Pred in a single pass. Takes linear 153 /// time. 154 template <class Predicate> void remove_if(Predicate Pred); 155}; 156 157template <typename KeyT, typename ValueT, typename MapType, typename VectorType> 158template <class Function> 159void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { 160 auto O = Vector.begin(); 161 for (auto I = O, E = Vector.end(); I != E; ++I) { 162 if (Pred(*I)) { 163 // Erase from the map. 164 Map.erase(I->first); 165 continue; 166 } 167 168 if (I != O) { 169 // Move the value and update the index in the map. 170 *O = std::move(*I); 171 Map[O->first] = O - Vector.begin(); 172 } 173 ++O; 174 } 175 // Erase trailing entries in the vector. 176 Vector.erase(O, Vector.end()); 177} 178 179} // end namespace llvm 180 181#endif 182