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