LCOV - code coverage report
Current view: top level - include/llvm/ADT - MapVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 80 81 98.8 %
Date: 2018-05-20 00:06:23 Functions: 288 299 96.3 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13