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