MapVector.h revision 327952
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 30namespace 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. 35template<typename KeyT, typename ValueT, 36 typename MapType = DenseMap<KeyT, unsigned>, 37 typename VectorType = std::vector<std::pair<KeyT, ValueT>>> 38class 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 45public: 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 /// Grow the MapVector so that it can contain at least \p NumEntries items 60 /// before resizing again. 61 void reserve(size_type NumEntries) { 62 Map.reserve(NumEntries); 63 Vector.reserve(NumEntries); 64 } 65 66 iterator begin() { return Vector.begin(); } 67 const_iterator begin() const { return Vector.begin(); } 68 iterator end() { return Vector.end(); } 69 const_iterator end() const { return Vector.end(); } 70 71 reverse_iterator rbegin() { return Vector.rbegin(); } 72 const_reverse_iterator rbegin() const { return Vector.rbegin(); } 73 reverse_iterator rend() { return Vector.rend(); } 74 const_reverse_iterator rend() const { return Vector.rend(); } 75 76 bool empty() const { 77 return Vector.empty(); 78 } 79 80 std::pair<KeyT, ValueT> &front() { return Vector.front(); } 81 const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } 82 std::pair<KeyT, ValueT> &back() { return Vector.back(); } 83 const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } 84 85 void clear() { 86 Map.clear(); 87 Vector.clear(); 88 } 89 90 void swap(MapVector &RHS) { 91 std::swap(Map, RHS.Map); 92 std::swap(Vector, RHS.Vector); 93 } 94 95 ValueT &operator[](const KeyT &Key) { 96 std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0); 97 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 98 unsigned &I = Result.first->second; 99 if (Result.second) { 100 Vector.push_back(std::make_pair(Key, ValueT())); 101 I = Vector.size() - 1; 102 } 103 return Vector[I].second; 104 } 105 106 // Returns a copy of the value. Only allowed if ValueT is copyable. 107 ValueT lookup(const KeyT &Key) const { 108 static_assert(std::is_copy_constructible<ValueT>::value, 109 "Cannot call lookup() if ValueT is not copyable."); 110 typename MapType::const_iterator Pos = Map.find(Key); 111 return Pos == Map.end()? ValueT() : Vector[Pos->second].second; 112 } 113 114 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 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::make_pair(KV.first, KV.second)); 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 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { 127 // Copy KV.first into the map, then move it into the vector. 128 std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0); 129 std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 130 unsigned &I = Result.first->second; 131 if (Result.second) { 132 Vector.push_back(std::move(KV)); 133 I = Vector.size() - 1; 134 return std::make_pair(std::prev(end()), true); 135 } 136 return std::make_pair(begin() + I, false); 137 } 138 139 size_type count(const KeyT &Key) const { 140 typename MapType::const_iterator Pos = Map.find(Key); 141 return Pos == Map.end()? 0 : 1; 142 } 143 144 iterator find(const KeyT &Key) { 145 typename MapType::const_iterator Pos = Map.find(Key); 146 return Pos == Map.end()? Vector.end() : 147 (Vector.begin() + Pos->second); 148 } 149 150 const_iterator find(const KeyT &Key) const { 151 typename MapType::const_iterator Pos = Map.find(Key); 152 return Pos == Map.end()? Vector.end() : 153 (Vector.begin() + Pos->second); 154 } 155 156 /// \brief Remove the last element from the vector. 157 void pop_back() { 158 typename MapType::iterator Pos = Map.find(Vector.back().first); 159 Map.erase(Pos); 160 Vector.pop_back(); 161 } 162 163 /// \brief Remove the element given by Iterator. 164 /// 165 /// Returns an iterator to the element following the one which was removed, 166 /// which may be end(). 167 /// 168 /// \note This is a deceivingly expensive operation (linear time). It's 169 /// usually better to use \a remove_if() if possible. 170 typename VectorType::iterator erase(typename VectorType::iterator Iterator) { 171 Map.erase(Iterator->first); 172 auto Next = Vector.erase(Iterator); 173 if (Next == Vector.end()) 174 return Next; 175 176 // Update indices in the map. 177 size_t Index = Next - Vector.begin(); 178 for (auto &I : Map) { 179 assert(I.second != Index && "Index was already erased!"); 180 if (I.second > Index) 181 --I.second; 182 } 183 return Next; 184 } 185 186 /// \brief Remove all elements with the key value Key. 187 /// 188 /// Returns the number of elements removed. 189 size_type erase(const KeyT &Key) { 190 auto Iterator = find(Key); 191 if (Iterator == end()) 192 return 0; 193 erase(Iterator); 194 return 1; 195 } 196 197 /// \brief Remove the elements that match the predicate. 198 /// 199 /// Erase all elements that match \c Pred in a single pass. Takes linear 200 /// time. 201 template <class Predicate> void remove_if(Predicate Pred); 202}; 203 204template <typename KeyT, typename ValueT, typename MapType, typename VectorType> 205template <class Function> 206void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { 207 auto O = Vector.begin(); 208 for (auto I = O, E = Vector.end(); I != E; ++I) { 209 if (Pred(*I)) { 210 // Erase from the map. 211 Map.erase(I->first); 212 continue; 213 } 214 215 if (I != O) { 216 // Move the value and update the index in the map. 217 *O = std::move(*I); 218 Map[O->first] = O - Vector.begin(); 219 } 220 ++O; 221 } 222 // Erase trailing entries in the vector. 223 Vector.erase(O, Vector.end()); 224} 225 226/// \brief A MapVector that performs no allocations if smaller than a certain 227/// size. 228template <typename KeyT, typename ValueT, unsigned N> 229struct SmallMapVector 230 : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>, 231 SmallVector<std::pair<KeyT, ValueT>, N>> { 232}; 233 234} // end namespace llvm 235 236#endif // LLVM_ADT_MAPVECTOR_H 237