LCOV - code coverage report
Current view: top level - include/llvm/ADT - MapVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 383 455 84.2 %
Date: 2018-10-14 09:39:32 Functions: 210 244 86.1 %
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    10243302 : 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       15228 :     Map.clear();
      58             :     return std::move(Vector);
      59             :   }
      60             : 
      61     5359395 :   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       43805 :     Map.reserve(NumEntries);
      67       43805 :     Vector.reserve(NumEntries);
      68             :   }
      69             : 
      70             :   iterator begin() { return Vector.begin(); }
      71      335410 :   const_iterator begin() const { return Vector.begin(); }
      72             :   iterator end() { return Vector.end(); }
      73    23587309 :   const_iterator end() const { return Vector.end(); }
      74             : 
      75             :   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     6483493 :     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      225054 :   void clear() {
      90    21717174 :     Map.clear();
      91             :     Vector.clear();
      92      225054 :   }
      93             : 
      94             :   void swap(MapVector &RHS) {
      95         197 :     std::swap(Map, RHS.Map);
      96             :     std::swap(Vector, RHS.Vector);
      97             :   }
      98             : 
      99    31803949 :   ValueT &operator[](const KeyT &Key) {
     100    31804041 :     std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(Key, 0);
     101    31803857 :     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
     102    31803856 :     auto &I = Result.first->second;
     103    31803948 :     if (Result.second) {
     104    24236865 :       Vector.push_back(std::make_pair(Key, ValueT()));
     105    42037959 :       I = Vector.size() - 1;
     106             :     }
     107    63607896 :     return Vector[I].second;
     108             :   }
     109      381794 : 
     110      381794 :   // Returns a copy of the value.  Only allowed if ValueT is copyable.
     111      398021 :   ValueT lookup(const KeyT &Key) const {
     112      381794 :     static_assert(std::is_copy_constructible<ValueT>::value,
     113      381794 :                   "Cannot call lookup() if ValueT is not copyable.");
     114      267662 :     typename MapType::const_iterator Pos = Map.find(Key);
     115      350953 :     return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
     116             :   }
     117      763588 : 
     118          60 :   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
     119      620434 :     std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
     120      620434 :     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
     121      620434 :     auto &I = Result.first->second;
     122      620434 :     if (Result.second) {
     123      630475 :       Vector.push_back(std::make_pair(KV.first, KV.second));
     124      257398 :       I = Vector.size() - 1;
     125      328863 :       return std::make_pair(std::prev(end()), true);
     126       10041 :     }
     127     1250789 :     return std::make_pair(begin() + I, false);
     128             :   }
     129    13022328 : 
     130    14769943 :   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
     131    13022303 :     // Copy KV.first into the map, then move it into the vector.
     132    14769968 :     std::pair<KeyT, typename MapType::mapped_type> Pair = std::make_pair(KV.first, 0);
     133    14769968 :     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
     134    15322008 :     auto &I = Result.first->second;
     135    27493380 :     if (Result.second) {
     136     1142752 :       Vector.push_back(std::move(KV));
     137    28165934 :       I = Vector.size() - 1;
     138       10161 :       return std::make_pair(std::prev(end()), true);
     139       10275 :     }
     140      625324 :     return std::make_pair(begin() + I, false);
     141       10283 :   }
     142       20754 : 
     143         114 :   size_type count(const KeyT &Key) const {
     144      274902 :     typename MapType::const_iterator Pos = Map.find(Key);
     145      274811 :     return Pos == Map.end()? 0 : 1;
     146         344 :   }
     147         681 : 
     148    15356584 :   iterator find(const KeyT &Key) {
     149    15357079 :     typename MapType::const_iterator Pos = Map.find(Key);
     150        1726 :     return Pos == Map.end()? Vector.end() :
     151    15356429 :                             (Vector.begin() + Pos->second);
     152        1740 :   }
     153        1825 : 
     154     1474665 :   const_iterator find(const KeyT &Key) const {
     155        1581 :     typename MapType::const_iterator Pos = Map.find(Key);
     156     1474581 :     return Pos == Map.end()? Vector.end() :
     157     1476296 :                             (Vector.begin() + Pos->second);
     158     1483188 :   }
     159     2086626 : 
     160     1480824 :   /// Remove the last element from the vector.
     161     2344573 :   void pop_back() {
     162      615253 :     typename MapType::iterator Pos = Map.find(Vector.back().first);
     163      615253 :     Map.erase(Pos);
     164      789911 :     Vector.pop_back();
     165      108916 :   }
     166        1768 : 
     167     1210338 :   /// Remove the element given by Iterator.
     168         642 :   ///
     169         668 :   /// Returns an iterator to the element following the one which was removed,
     170         641 :   /// which may be end().
     171         668 :   ///
     172        1120 :   /// \note This is a deceivingly expensive operation (linear time).  It's
     173        1044 :   /// usually better to use \a remove_if() if possible.
     174      724261 :   typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
     175      724660 :     Map.erase(Iterator->first);
     176       77356 :     auto Next = Vector.erase(Iterator);
     177      724142 :     if (Next == Vector.end())
     178    14806844 :       return Next;
     179    14469603 : 
     180         373 :     // Update indices in the map.
     181    14566516 :     size_t Index = Next - Vector.begin();
     182     1615463 :     for (auto &I : Map) {
     183       10152 :       assert(I.second != Index && "Index was already erased!");
     184     1538786 :       if (I.second > Index)
     185      723861 :         --I.second;
     186       10624 :     }
     187       97478 :     return Next;
     188       20370 :   }
     189         259 : 
     190          55 :   /// Remove all elements with the key value Key.
     191         121 :   ///
     192         338 :   /// Returns the number of elements removed.
     193     7689749 :   size_type erase(const KeyT &Key) {
     194     7690439 :     auto Iterator = find(Key);
     195     7690343 :     if (Iterator == end())
     196        1891 :       return 0;
     197      424948 :     erase(Iterator);
     198      426588 :     return 1;
     199        1890 :   }
     200        1932 : 
     201        1934 :   /// Remove the elements that match the predicate.
     202        1646 :   ///
     203        3280 :   /// Erase all elements that match \c Pred in a single pass.  Takes linear
     204      905567 :   /// time.
     205      915581 :   template <class Predicate> void remove_if(Predicate Pred);
     206        1131 : };
     207       11172 : 
     208       11256 : template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
     209       10042 : template <class Function>
     210       10042 : void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
     211       10083 :   auto O = Vector.begin();
     212       21741 :   for (auto I = O, E = Vector.end(); I != E; ++I) {
     213        1575 :     if (Pred(*I)) {
     214       28916 :       // Erase from the map.
     215       30498 :       Map.erase(I->first);
     216           0 :       continue;
     217       28940 :     }
     218           2 : 
     219          26 :     if (I != O) {
     220      744240 :       // Move the value and update the index in the map.
     221      744241 :       *O = std::move(*I);
     222        1601 :       Map[O->first] = O - Vector.begin();
     223      746928 :     }
     224        1140 :     ++O;
     225       81785 :   }
     226       79086 :   // Erase trailing entries in the vector.
     227       29401 :   Vector.erase(O, Vector.end());
     228      136741 : }
     229       28266 : 
     230      665128 : /// A MapVector that performs no allocations if smaller than a certain
     231      693398 : /// size.
     232           5 : template <typename KeyT, typename ValueT, unsigned N>
     233     1668895 : struct SmallMapVector
     234           1 :     : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
     235           1 :                 SmallVector<std::pair<KeyT, ValueT>, N>> {
     236           0 : };
     237           0 : 
     238             : } // end namespace llvm
     239             : 
     240           1 : #endif // LLVM_ADT_MAPVECTOR_H

Generated by: LCOV version 1.13