include/llvm/ADT/MapVector.h

   1 //===- llvm/ADT/MapVector.h - Map w/ deterministic value order --*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements a map that provides insertion order iteration. The
  10 // interface is purposefully minimal. The key is assumed to be cheap to copy
  11 // and 2 copies are kept, one for indexing in a DenseMap, one for iteration in
  12 // a std::vector.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_ADT_MAPVECTOR_H
  17 #define LLVM_ADT_MAPVECTOR_H
  18
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include <algorithm>
  22 #include <cassert>
  23 #include <cstddef>
  24 #include <iterator>
  25 #include <type_traits>
  26 #include <utility>
  27 #include <vector>
  28
  29 namespace llvm {
  30
  31 /// This class implements a map that also provides access to all stored values
  32 /// in a deterministic order. The values are kept in a std::vector and the
  33 /// mapping is done with DenseMap from Keys to indexes in that vector.
  34 template<typename KeyT, typename ValueT,
  35          typename MapType = DenseMap<KeyT, unsigned>,
  36          typename VectorType = std::vector<std::pair<KeyT, ValueT>>>
  37 class MapVector {
  38   MapType Map;
  39   VectorType Vector;
  40
  41   static_assert(
  42       std::is_integral<typename MapType::mapped_type>::value,
  43       "The mapped_type of the specified Map must be an integral type");
  44
  45 public:
  46   using value_type = typename VectorType::value_type;
  47   using size_type = typename VectorType::size_type;
  48
  49   using iterator = typename VectorType::iterator;
  50   using const_iterator = typename VectorType::const_iterator;
  51   using reverse_iterator = typename VectorType::reverse_iterator;
  52   using const_reverse_iterator = typename VectorType::const_reverse_iterator;
  53
  54   /// Clear the MapVector and return the underlying vector.
  55   VectorType takeVector() {
  56     Map.clear();
  57     return std::move(Vector);
  58   }
  59
  60   size_type size() const { return Vector.size(); }
  61
  62   /// Grow the MapVector so that it can contain at least \p NumEntries items
  63   /// before resizing again.
  64   void reserve(size_type NumEntries) {
  65     Map.reserve(NumEntries);
  66     Vector.reserve(NumEntries);
  67   }
  68
  69   iterator begin() { return Vector.begin(); }
  70   const_iterator begin() const { return Vector.begin(); }
  71   iterator end() { return Vector.end(); }
  72   const_iterator end() const { return Vector.end(); }
  73
  74   reverse_iterator rbegin() { return Vector.rbegin(); }
  75   const_reverse_iterator rbegin() const { return Vector.rbegin(); }
  76   reverse_iterator rend() { return Vector.rend(); }
  77   const_reverse_iterator rend() const { return Vector.rend(); }
  78
  79   bool empty() const {
  80     return Vector.empty();
  81   }
  82
  83   std::pair<KeyT, ValueT>       &front()       { return Vector.front(); }
  84   const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
  85   std::pair<KeyT, ValueT>       &back()        { return Vector.back(); }
  86   const std::pair<KeyT, ValueT> &back()  const { return Vector.back(); }
  87
  88   void clear() {
  89     Map.clear();
  90     Vector.clear();
  91   }
  92
  93   void swap(MapVector &RHS) {
  94     std::swap(Map, RHS.Map);
  95     std::swap(Vector, RHS.Vector);
  96   }
  97
  98   ValueT &operator[](const KeyT &Key) {
  99     std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(Key, 0);
 100     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
 101     auto &I = Result.first->second;
 102     if (Result.second) {
 103       Vector.push_back(std::make_pair(Key, ValueT()));
 104       I = Vector.size() - 1;
 105     }
 106     return Vector[I].second;
 107   }
 108
 109   // Returns a copy of the value.  Only allowed if ValueT is copyable.
 110   ValueT lookup(const KeyT &Key) const {
 111     static_assert(std::is_copy_constructible<ValueT>::value,
 112                   "Cannot call lookup() if ValueT is not copyable.");
 113     typename MapType::const_iterator Pos = Map.find(Key);
 114     return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
 115   }
 116
 117   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
 118     std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
 119     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
 120     auto &I = Result.first->second;
 121     if (Result.second) {
 122       Vector.push_back(std::make_pair(KV.first, KV.second));
 123       I = Vector.size() - 1;
 124       return std::make_pair(std::prev(end()), true);
 125     }
 126     return std::make_pair(begin() + I, false);
 127   }
 128
 129   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
 130     // Copy KV.first into the map, then move it into the vector.
 131     std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
 132     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
 133     auto &I = Result.first->second;
 134     if (Result.second) {
 135       Vector.push_back(std::move(KV));
 136       I = Vector.size() - 1;
 137       return std::make_pair(std::prev(end()), true);
 138     }
 139     return std::make_pair(begin() + I, false);
 140   }
 141
 142   size_type count(const KeyT &Key) const {
 143     typename MapType::const_iterator Pos = Map.find(Key);
 144     return Pos == Map.end()? 0 : 1;
 145   }
 146
 147   iterator find(const KeyT &Key) {
 148     typename MapType::const_iterator Pos = Map.find(Key);
 149     return Pos == Map.end()? Vector.end() :
 150                             (Vector.begin() + Pos->second);
 151   }
 152
 153   const_iterator find(const KeyT &Key) const {
 154     typename MapType::const_iterator Pos = Map.find(Key);
 155     return Pos == Map.end()? Vector.end() :
 156                             (Vector.begin() + Pos->second);
 157   }
 158
 159   /// Remove the last element from the vector.
 160   void pop_back() {
 161     typename MapType::iterator Pos = Map.find(Vector.back().first);
 162     Map.erase(Pos);
 163     Vector.pop_back();
 164   }
 165
 166   /// Remove the element given by Iterator.
 167   ///
 168   /// Returns an iterator to the element following the one which was removed,
 169   /// which may be end().
 170   ///
 171   /// \note This is a deceivingly expensive operation (linear time).  It's
 172   /// usually better to use \a remove_if() if possible.
 173   typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
 174     Map.erase(Iterator->first);
 175     auto Next = Vector.erase(Iterator);
 176     if (Next == Vector.end())
 177       return Next;
 178
 179     // Update indices in the map.
 180     size_t Index = Next - Vector.begin();
 181     for (auto &I : Map) {
 182       assert(I.second != Index && "Index was already erased!");
 183       if (I.second > Index)
 184         --I.second;
 185     }
 186     return Next;
 187   }
 188
 189   /// Remove all elements with the key value Key.
 190   ///
 191   /// Returns the number of elements removed.
 192   size_type erase(const KeyT &Key) {
 193     auto Iterator = find(Key);
 194     if (Iterator == end())
 195       return 0;
 196     erase(Iterator);
 197     return 1;
 198   }
 199
 200   /// Remove the elements that match the predicate.
 201   ///
 202   /// Erase all elements that match \c Pred in a single pass.  Takes linear
 203   /// time.
 204   template <class Predicate> void remove_if(Predicate Pred);
 205 };
 206
 207 template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
 208 template <class Function>
 209 void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
 210   auto O = Vector.begin();
 211   for (auto I = O, E = Vector.end(); I != E; ++I) {
 212     if (Pred(*I)) {
 213       // Erase from the map.
 214       Map.erase(I->first);
 215       continue;
 216     }
 217
 218     if (I != O) {
 219       // Move the value and update the index in the map.
 220       *O = std::move(*I);
 221       Map[O->first] = O - Vector.begin();
 222     }
 223     ++O;
 224   }
 225   // Erase trailing entries in the vector.
 226   Vector.erase(O, Vector.end());
 227 }
 228
 229 /// A MapVector that performs no allocations if smaller than a certain
 230 /// size.
 231 template <typename KeyT, typename ValueT, unsigned N>
 232 struct SmallMapVector
 233     : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
 234                 SmallVector<std::pair<KeyT, ValueT>, N>> {
 235 };
 236
 237 } // end namespace llvm
 238
 239 #endif // LLVM_ADT_MAPVECTOR_H