MapVector.h revision 280031
1276479Sdim//===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- C++ -*-===// 2243789Sdim// 3243789Sdim// The LLVM Compiler Infrastructure 4243789Sdim// 5243789Sdim// This file is distributed under the University of Illinois Open Source 6243789Sdim// License. See LICENSE.TXT for details. 7243789Sdim// 8243789Sdim//===----------------------------------------------------------------------===// 9243789Sdim// 10243789Sdim// This file implements a map that provides insertion order iteration. The 11243789Sdim// interface is purposefully minimal. The key is assumed to be cheap to copy 12243789Sdim// and 2 copies are kept, one for indexing in a DenseMap, one for iteration in 13243789Sdim// a std::vector. 14243789Sdim// 15243789Sdim//===----------------------------------------------------------------------===// 16243789Sdim 17243789Sdim#ifndef LLVM_ADT_MAPVECTOR_H 18243789Sdim#define LLVM_ADT_MAPVECTOR_H 19243789Sdim 20243789Sdim#include "llvm/ADT/DenseMap.h" 21280031Sdim#include "llvm/ADT/SmallVector.h" 22243789Sdim#include <vector> 23243789Sdim 24243789Sdimnamespace llvm { 25243789Sdim 26243789Sdim/// This class implements a map that also provides access to all stored values 27243789Sdim/// in a deterministic order. The values are kept in a std::vector and the 28243789Sdim/// mapping is done with DenseMap from Keys to indexes in that vector. 29243789Sdimtemplate<typename KeyT, typename ValueT, 30243789Sdim typename MapType = llvm::DenseMap<KeyT, unsigned>, 31243789Sdim typename VectorType = std::vector<std::pair<KeyT, ValueT> > > 32243789Sdimclass MapVector { 33276479Sdim typedef typename VectorType::size_type size_type; 34243789Sdim 35243789Sdim MapType Map; 36243789Sdim VectorType Vector; 37243789Sdim 38243789Sdimpublic: 39243789Sdim typedef typename VectorType::iterator iterator; 40243789Sdim typedef typename VectorType::const_iterator const_iterator; 41280031Sdim typedef typename VectorType::reverse_iterator reverse_iterator; 42280031Sdim typedef typename VectorType::const_reverse_iterator const_reverse_iterator; 43243789Sdim 44280031Sdim size_type size() const { return Vector.size(); } 45243789Sdim 46280031Sdim iterator begin() { return Vector.begin(); } 47280031Sdim const_iterator begin() const { return Vector.begin(); } 48280031Sdim iterator end() { return Vector.end(); } 49280031Sdim const_iterator end() const { return Vector.end(); } 50243789Sdim 51280031Sdim reverse_iterator rbegin() { return Vector.rbegin(); } 52280031Sdim const_reverse_iterator rbegin() const { return Vector.rbegin(); } 53280031Sdim reverse_iterator rend() { return Vector.rend(); } 54280031Sdim const_reverse_iterator rend() const { return Vector.rend(); } 55243789Sdim 56243789Sdim bool empty() const { 57243789Sdim return Vector.empty(); 58243789Sdim } 59243789Sdim 60249423Sdim std::pair<KeyT, ValueT> &front() { return Vector.front(); } 61249423Sdim const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } 62249423Sdim std::pair<KeyT, ValueT> &back() { return Vector.back(); } 63249423Sdim const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } 64249423Sdim 65243789Sdim void clear() { 66243789Sdim Map.clear(); 67243789Sdim Vector.clear(); 68243789Sdim } 69243789Sdim 70243789Sdim ValueT &operator[](const KeyT &Key) { 71243789Sdim std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0); 72243789Sdim std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 73243789Sdim unsigned &I = Result.first->second; 74243789Sdim if (Result.second) { 75243789Sdim Vector.push_back(std::make_pair(Key, ValueT())); 76243789Sdim I = Vector.size() - 1; 77243789Sdim } 78243789Sdim return Vector[I].second; 79243789Sdim } 80243789Sdim 81249423Sdim ValueT lookup(const KeyT &Key) const { 82249423Sdim typename MapType::const_iterator Pos = Map.find(Key); 83249423Sdim return Pos == Map.end()? ValueT() : Vector[Pos->second].second; 84249423Sdim } 85249423Sdim 86249423Sdim std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 87249423Sdim std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0); 88249423Sdim std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 89249423Sdim unsigned &I = Result.first->second; 90249423Sdim if (Result.second) { 91249423Sdim Vector.push_back(std::make_pair(KV.first, KV.second)); 92249423Sdim I = Vector.size() - 1; 93276479Sdim return std::make_pair(std::prev(end()), true); 94249423Sdim } 95249423Sdim return std::make_pair(begin() + I, false); 96249423Sdim } 97249423Sdim 98276479Sdim size_type count(const KeyT &Key) const { 99243789Sdim typename MapType::const_iterator Pos = Map.find(Key); 100243789Sdim return Pos == Map.end()? 0 : 1; 101243789Sdim } 102249423Sdim 103249423Sdim iterator find(const KeyT &Key) { 104249423Sdim typename MapType::const_iterator Pos = Map.find(Key); 105249423Sdim return Pos == Map.end()? Vector.end() : 106249423Sdim (Vector.begin() + Pos->second); 107249423Sdim } 108249423Sdim 109249423Sdim const_iterator find(const KeyT &Key) const { 110249423Sdim typename MapType::const_iterator Pos = Map.find(Key); 111249423Sdim return Pos == Map.end()? Vector.end() : 112249423Sdim (Vector.begin() + Pos->second); 113249423Sdim } 114249423Sdim 115249423Sdim /// \brief Remove the last element from the vector. 116249423Sdim void pop_back() { 117249423Sdim typename MapType::iterator Pos = Map.find(Vector.back().first); 118249423Sdim Map.erase(Pos); 119249423Sdim Vector.pop_back(); 120249423Sdim } 121276479Sdim 122276479Sdim /// \brief Remove the element given by Iterator. 123276479Sdim /// 124276479Sdim /// Returns an iterator to the element following the one which was removed, 125276479Sdim /// which may be end(). 126276479Sdim /// 127276479Sdim /// \note This is a deceivingly expensive operation (linear time). It's 128276479Sdim /// usually better to use \a remove_if() if possible. 129276479Sdim typename VectorType::iterator erase(typename VectorType::iterator Iterator) { 130276479Sdim Map.erase(Iterator->first); 131276479Sdim auto Next = Vector.erase(Iterator); 132276479Sdim if (Next == Vector.end()) 133276479Sdim return Next; 134276479Sdim 135276479Sdim // Update indices in the map. 136276479Sdim size_t Index = Next - Vector.begin(); 137276479Sdim for (auto &I : Map) { 138276479Sdim assert(I.second != Index && "Index was already erased!"); 139276479Sdim if (I.second > Index) 140276479Sdim --I.second; 141276479Sdim } 142276479Sdim return Next; 143276479Sdim } 144276479Sdim 145280031Sdim /// \brief Remove all elements with the key value Key. 146280031Sdim /// 147280031Sdim /// Returns the number of elements removed. 148280031Sdim size_type erase(const KeyT &Key) { 149280031Sdim auto Iterator = find(Key); 150280031Sdim if (Iterator == end()) 151280031Sdim return 0; 152280031Sdim erase(Iterator); 153280031Sdim return 1; 154280031Sdim } 155280031Sdim 156276479Sdim /// \brief Remove the elements that match the predicate. 157276479Sdim /// 158276479Sdim /// Erase all elements that match \c Pred in a single pass. Takes linear 159276479Sdim /// time. 160276479Sdim template <class Predicate> void remove_if(Predicate Pred); 161243789Sdim}; 162243789Sdim 163276479Sdimtemplate <typename KeyT, typename ValueT, typename MapType, typename VectorType> 164276479Sdimtemplate <class Function> 165276479Sdimvoid MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) { 166276479Sdim auto O = Vector.begin(); 167276479Sdim for (auto I = O, E = Vector.end(); I != E; ++I) { 168276479Sdim if (Pred(*I)) { 169276479Sdim // Erase from the map. 170276479Sdim Map.erase(I->first); 171276479Sdim continue; 172276479Sdim } 173276479Sdim 174276479Sdim if (I != O) { 175276479Sdim // Move the value and update the index in the map. 176276479Sdim *O = std::move(*I); 177276479Sdim Map[O->first] = O - Vector.begin(); 178276479Sdim } 179276479Sdim ++O; 180276479Sdim } 181276479Sdim // Erase trailing entries in the vector. 182276479Sdim Vector.erase(O, Vector.end()); 183243789Sdim} 184243789Sdim 185280031Sdim/// \brief A MapVector that performs no allocations if smaller than a certain 186280031Sdim/// size. 187280031Sdimtemplate <typename KeyT, typename ValueT, unsigned N> 188280031Sdimstruct SmallMapVector 189280031Sdim : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>, 190280031Sdim SmallVector<std::pair<KeyT, ValueT>, N>> { 191280031Sdim}; 192280031Sdim 193276479Sdim} // end namespace llvm 194276479Sdim 195243789Sdim#endif 196