include/llvm/ADT/MapVector.h

   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/ArrayRef.h"
  21 #include "llvm/ADT/DenseMap.h"
  22 #include "llvm/ADT/STLExtras.h"
  23 #include <vector>
  24
  25 namespace llvm {
  26
  27 /// This class implements a map that also provides access to all stored values
  28 /// in a deterministic order. The values are kept in a std::vector and the
  29 /// mapping is done with DenseMap from Keys to indexes in that vector.
  30 template<typename KeyT, typename ValueT,
  31          typename MapType = llvm::DenseMap<KeyT, unsigned>,
  32          typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
  33 class MapVector {
  34   typedef typename VectorType::size_type SizeType;
  35
  36   MapType Map;
  37   VectorType Vector;
  38
  39 public:
  40   typedef typename VectorType::iterator iterator;
  41   typedef typename VectorType::const_iterator const_iterator;
  42
  43   SizeType size() const {
  44     return Vector.size();
  45   }
  46
  47   iterator begin() {
  48     return Vector.begin();
  49   }
  50
  51   const_iterator begin() const {
  52     return Vector.begin();
  53   }
  54
  55   iterator end() {
  56     return Vector.end();
  57   }
  58
  59   const_iterator end() const {
  60     return Vector.end();
  61   }
  62
  63   bool empty() const {
  64     return Vector.empty();
  65   }
  66
  67   std::pair<KeyT, ValueT>       &front()       { return Vector.front(); }
  68   const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
  69   std::pair<KeyT, ValueT>       &back()        { return Vector.back(); }
  70   const std::pair<KeyT, ValueT> &back()  const { return Vector.back(); }
  71
  72   void clear() {
  73     Map.clear();
  74     Vector.clear();
  75   }
  76
  77   ValueT &operator[](const KeyT &Key) {
  78     std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
  79     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
  80     unsigned &I = Result.first->second;
  81     if (Result.second) {
  82       Vector.push_back(std::make_pair(Key, ValueT()));
  83       I = Vector.size() - 1;
  84     }
  85     return Vector[I].second;
  86   }
  87
  88   ValueT lookup(const KeyT &Key) const {
  89     typename MapType::const_iterator Pos = Map.find(Key);
  90     return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
  91   }
  92
  93   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
  94     std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
  95     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
  96     unsigned &I = Result.first->second;
  97     if (Result.second) {
  98       Vector.push_back(std::make_pair(KV.first, KV.second));
  99       I = Vector.size() - 1;
 100       return std::make_pair(llvm::prior(end()), true);
 101     }
 102     return std::make_pair(begin() + I, false);
 103   }
 104
 105   unsigned count(const KeyT &Key) const {
 106     typename MapType::const_iterator Pos = Map.find(Key);
 107     return Pos == Map.end()? 0 : 1;
 108   }
 109
 110   iterator find(const KeyT &Key) {
 111     typename MapType::const_iterator Pos = Map.find(Key);
 112     return Pos == Map.end()? Vector.end() :
 113                             (Vector.begin() + Pos->second);
 114   }
 115
 116   const_iterator find(const KeyT &Key) const {
 117     typename MapType::const_iterator Pos = Map.find(Key);
 118     return Pos == Map.end()? Vector.end() :
 119                             (Vector.begin() + Pos->second);
 120   }
 121
 122   /// \brief Remove the last element from the vector.
 123   void pop_back() {
 124     typename MapType::iterator Pos = Map.find(Vector.back().first);
 125     Map.erase(Pos);
 126     Vector.pop_back();
 127   }
 128 };
 129
 130 }
 131
 132 #endif