1243789Sdim//===- llvm/ADT/MapVector.h - Map with 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/ArrayRef.h" 21243789Sdim#include "llvm/ADT/DenseMap.h" 22249423Sdim#include "llvm/ADT/STLExtras.h" 23243789Sdim#include <vector> 24243789Sdim 25243789Sdimnamespace llvm { 26243789Sdim 27243789Sdim/// This class implements a map that also provides access to all stored values 28243789Sdim/// in a deterministic order. The values are kept in a std::vector and the 29243789Sdim/// mapping is done with DenseMap from Keys to indexes in that vector. 30243789Sdimtemplate<typename KeyT, typename ValueT, 31243789Sdim typename MapType = llvm::DenseMap<KeyT, unsigned>, 32243789Sdim typename VectorType = std::vector<std::pair<KeyT, ValueT> > > 33243789Sdimclass MapVector { 34243789Sdim typedef typename VectorType::size_type SizeType; 35243789Sdim 36243789Sdim MapType Map; 37243789Sdim VectorType Vector; 38243789Sdim 39243789Sdimpublic: 40243789Sdim typedef typename VectorType::iterator iterator; 41243789Sdim typedef typename VectorType::const_iterator const_iterator; 42243789Sdim 43243789Sdim SizeType size() const { 44243789Sdim return Vector.size(); 45243789Sdim } 46243789Sdim 47243789Sdim iterator begin() { 48243789Sdim return Vector.begin(); 49243789Sdim } 50243789Sdim 51243789Sdim const_iterator begin() const { 52243789Sdim return Vector.begin(); 53243789Sdim } 54243789Sdim 55243789Sdim iterator end() { 56243789Sdim return Vector.end(); 57243789Sdim } 58243789Sdim 59243789Sdim const_iterator end() const { 60243789Sdim return Vector.end(); 61243789Sdim } 62243789Sdim 63243789Sdim bool empty() const { 64243789Sdim return Vector.empty(); 65243789Sdim } 66243789Sdim 67249423Sdim std::pair<KeyT, ValueT> &front() { return Vector.front(); } 68249423Sdim const std::pair<KeyT, ValueT> &front() const { return Vector.front(); } 69249423Sdim std::pair<KeyT, ValueT> &back() { return Vector.back(); } 70249423Sdim const std::pair<KeyT, ValueT> &back() const { return Vector.back(); } 71249423Sdim 72243789Sdim void clear() { 73243789Sdim Map.clear(); 74243789Sdim Vector.clear(); 75243789Sdim } 76243789Sdim 77243789Sdim ValueT &operator[](const KeyT &Key) { 78243789Sdim std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0); 79243789Sdim std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 80243789Sdim unsigned &I = Result.first->second; 81243789Sdim if (Result.second) { 82243789Sdim Vector.push_back(std::make_pair(Key, ValueT())); 83243789Sdim I = Vector.size() - 1; 84243789Sdim } 85243789Sdim return Vector[I].second; 86243789Sdim } 87243789Sdim 88249423Sdim ValueT lookup(const KeyT &Key) const { 89249423Sdim typename MapType::const_iterator Pos = Map.find(Key); 90249423Sdim return Pos == Map.end()? ValueT() : Vector[Pos->second].second; 91249423Sdim } 92249423Sdim 93249423Sdim std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 94249423Sdim std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0); 95249423Sdim std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair); 96249423Sdim unsigned &I = Result.first->second; 97249423Sdim if (Result.second) { 98249423Sdim Vector.push_back(std::make_pair(KV.first, KV.second)); 99249423Sdim I = Vector.size() - 1; 100249423Sdim return std::make_pair(llvm::prior(end()), true); 101249423Sdim } 102249423Sdim return std::make_pair(begin() + I, false); 103249423Sdim } 104249423Sdim 105243789Sdim unsigned count(const KeyT &Key) const { 106243789Sdim typename MapType::const_iterator Pos = Map.find(Key); 107243789Sdim return Pos == Map.end()? 0 : 1; 108243789Sdim } 109249423Sdim 110249423Sdim iterator find(const KeyT &Key) { 111249423Sdim typename MapType::const_iterator Pos = Map.find(Key); 112249423Sdim return Pos == Map.end()? Vector.end() : 113249423Sdim (Vector.begin() + Pos->second); 114249423Sdim } 115249423Sdim 116249423Sdim const_iterator find(const KeyT &Key) const { 117249423Sdim typename MapType::const_iterator Pos = Map.find(Key); 118249423Sdim return Pos == Map.end()? Vector.end() : 119249423Sdim (Vector.begin() + Pos->second); 120249423Sdim } 121249423Sdim 122249423Sdim /// \brief Remove the last element from the vector. 123249423Sdim void pop_back() { 124249423Sdim typename MapType::iterator Pos = Map.find(Vector.back().first); 125249423Sdim Map.erase(Pos); 126249423Sdim Vector.pop_back(); 127249423Sdim } 128243789Sdim}; 129243789Sdim 130243789Sdim} 131243789Sdim 132243789Sdim#endif 133