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/DenseMap.h"
  21 #include <vector>
  22
  23 namespace llvm {
  24
  25 /// This class implements a map that also provides access to all stored values
  26 /// in a deterministic order. The values are kept in a std::vector and the
  27 /// mapping is done with DenseMap from Keys to indexes in that vector.
  28 template<typename KeyT, typename ValueT,
  29          typename MapType = llvm::DenseMap<KeyT, unsigned>,
  30          typename VectorType = std::vector<std::pair<KeyT, ValueT> > >
  31 class MapVector {
  32   typedef typename VectorType::size_type size_type;
  33
  34   MapType Map;
  35   VectorType Vector;
  36
  37 public:
  38   typedef typename VectorType::iterator iterator;
  39   typedef typename VectorType::const_iterator const_iterator;
  40
  41   size_type size() const {
  42     return Vector.size();
  43   }
  44
  45   iterator begin() {
  46     return Vector.begin();
  47   }
  48
  49   const_iterator begin() const {
  50     return Vector.begin();
  51   }
  52
  53   iterator end() {
  54     return Vector.end();
  55   }
  56
  57   const_iterator end() const {
  58     return Vector.end();
  59   }
  60
  61   bool empty() const {
  62     return Vector.empty();
  63   }
  64
  65   std::pair<KeyT, ValueT>       &front()       { return Vector.front(); }
  66   const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
  67   std::pair<KeyT, ValueT>       &back()        { return Vector.back(); }
  68   const std::pair<KeyT, ValueT> &back()  const { return Vector.back(); }
  69
  70   void clear() {
  71     Map.clear();
  72     Vector.clear();
  73   }
  74
  75   ValueT &operator[](const KeyT &Key) {
  76     std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
  77     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
  78     unsigned &I = Result.first->second;
  79     if (Result.second) {
  80       Vector.push_back(std::make_pair(Key, ValueT()));
  81       I = Vector.size() - 1;
  82     }
  83     return Vector[I].second;
  84   }
  85
  86   ValueT lookup(const KeyT &Key) const {
  87     typename MapType::const_iterator Pos = Map.find(Key);
  88     return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
  89   }
  90
  91   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
  92     std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
  93     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
  94     unsigned &I = Result.first->second;
  95     if (Result.second) {
  96       Vector.push_back(std::make_pair(KV.first, KV.second));
  97       I = Vector.size() - 1;
  98       return std::make_pair(std::prev(end()), true);
  99     }
 100     return std::make_pair(begin() + I, false);
 101   }
 102
 103   size_type count(const KeyT &Key) const {
 104     typename MapType::const_iterator Pos = Map.find(Key);
 105     return Pos == Map.end()? 0 : 1;
 106   }
 107
 108   iterator find(const KeyT &Key) {
 109     typename MapType::const_iterator Pos = Map.find(Key);
 110     return Pos == Map.end()? Vector.end() :
 111                             (Vector.begin() + Pos->second);
 112   }
 113
 114   const_iterator find(const KeyT &Key) const {
 115     typename MapType::const_iterator Pos = Map.find(Key);
 116     return Pos == Map.end()? Vector.end() :
 117                             (Vector.begin() + Pos->second);
 118   }
 119
 120   /// \brief Remove the last element from the vector.
 121   void pop_back() {
 122     typename MapType::iterator Pos = Map.find(Vector.back().first);
 123     Map.erase(Pos);
 124     Vector.pop_back();
 125   }
 126
 127   /// \brief Remove the element given by Iterator.
 128   ///
 129   /// Returns an iterator to the element following the one which was removed,
 130   /// which may be end().
 131   ///
 132   /// \note This is a deceivingly expensive operation (linear time).  It's
 133   /// usually better to use \a remove_if() if possible.
 134   typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
 135     Map.erase(Iterator->first);
 136     auto Next = Vector.erase(Iterator);
 137     if (Next == Vector.end())
 138       return Next;
 139
 140     // Update indices in the map.
 141     size_t Index = Next - Vector.begin();
 142     for (auto &I : Map) {
 143       assert(I.second != Index && "Index was already erased!");
 144       if (I.second > Index)
 145         --I.second;
 146     }
 147     return Next;
 148   }
 149
 150   /// \brief Remove all elements with the key value Key.
 151   ///
 152   /// Returns the number of elements removed.
 153   size_type erase(const KeyT &Key) {
 154     auto Iterator = find(Key);
 155     if (Iterator == end())
 156       return 0;
 157     erase(Iterator);
 158     return 1;
 159   }
 160
 161   /// \brief Remove the elements that match the predicate.
 162   ///
 163   /// Erase all elements that match \c Pred in a single pass.  Takes linear
 164   /// time.
 165   template <class Predicate> void remove_if(Predicate Pred);
 166 };
 167
 168 template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
 169 template <class Function>
 170 void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
 171   auto O = Vector.begin();
 172   for (auto I = O, E = Vector.end(); I != E; ++I) {
 173     if (Pred(*I)) {
 174       // Erase from the map.
 175       Map.erase(I->first);
 176       continue;
 177     }
 178
 179     if (I != O) {
 180       // Move the value and update the index in the map.
 181       *O = std::move(*I);
 182       Map[O->first] = O - Vector.begin();
 183     }
 184     ++O;
 185   }
 186   // Erase trailing entries in the vector.
 187   Vector.erase(O, Vector.end());
 188 }
 189
 190 } // end namespace llvm
 191
 192 #endif