LCOV - code coverage report
Current view: top level - include/llvm/ADT - MapVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 79 81 97.5 %
Date: 2018-02-20 03:34:22 Functions: 257 268 95.9 %
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    12505517 : class MapVector {
      39             :   using value_type = typename VectorType::value_type;
      40             :   using size_type = typename VectorType::size_type;
      41             : 
      42             :   MapType Map;
      43             :   VectorType Vector;
      44             : 
      45             : public:
      46             :   using iterator = typename VectorType::iterator;
      47             :   using const_iterator = typename VectorType::const_iterator;
      48             :   using reverse_iterator = typename VectorType::reverse_iterator;
      49             :   using const_reverse_iterator = typename VectorType::const_reverse_iterator;
      50             : 
      51             :   /// Clear the MapVector and return the underlying vector.
      52             :   VectorType takeVector() {
      53       10902 :     Map.clear();
      54             :     return std::move(Vector);
      55             :   }
      56             : 
      57     1463305 :   size_type size() const { return Vector.size(); }
      58             : 
      59             :   /// Grow the MapVector so that it can contain at least \p NumEntries items
      60             :   /// before resizing again.
      61             :   void reserve(size_type NumEntries) {
      62       33774 :     Map.reserve(NumEntries);
      63       33776 :     Vector.reserve(NumEntries);
      64             :   }
      65             : 
      66             :   iterator begin() { return Vector.begin(); }
      67      170618 :   const_iterator begin() const { return Vector.begin(); }
      68             :   iterator end() { return Vector.end(); }
      69     2600040 :   const_iterator end() const { return Vector.end(); }
      70             : 
      71           2 :   reverse_iterator rbegin() { return Vector.rbegin(); }
      72             :   const_reverse_iterator rbegin() const { return Vector.rbegin(); }
      73           2 :   reverse_iterator rend() { return Vector.rend(); }
      74             :   const_reverse_iterator rend() const { return Vector.rend(); }
      75             : 
      76             :   bool empty() const {
      77     5419330 :     return Vector.empty();
      78             :   }
      79             : 
      80             :   std::pair<KeyT, ValueT>       &front()       { return Vector.front(); }
      81             :   const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
      82             :   std::pair<KeyT, ValueT>       &back()        { return Vector.back(); }
      83             :   const std::pair<KeyT, ValueT> &back()  const { return Vector.back(); }
      84             : 
      85      142753 :   void clear() {
      86     6288648 :     Map.clear();
      87      746191 :     Vector.clear();
      88      142753 :   }
      89             : 
      90             :   void swap(MapVector &RHS) {
      91         179 :     std::swap(Map, RHS.Map);
      92             :     std::swap(Vector, RHS.Vector);
      93             :   }
      94             : 
      95    17658490 :   ValueT &operator[](const KeyT &Key) {
      96    14820361 :     std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
      97    17658409 :     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
      98    17658411 :     unsigned &I = Result.first->second;
      99    17658492 :     if (Result.second) {
     100    20036802 :       Vector.push_back(std::make_pair(Key, ValueT()));
     101    18156894 :       I = Vector.size() - 1;
     102             :     }
     103    35316984 :     return Vector[I].second;
     104             :   }
     105             : 
     106             :   // Returns a copy of the value.  Only allowed if ValueT is copyable.
     107      169646 :   ValueT lookup(const KeyT &Key) const {
     108             :     static_assert(std::is_copy_constructible<ValueT>::value,
     109             :                   "Cannot call lookup() if ValueT is not copyable.");
     110      169646 :     typename MapType::const_iterator Pos = Map.find(Key);
     111      336044 :     return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
     112             :   }
     113             : 
     114          60 :   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
     115          60 :     std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
     116          60 :     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
     117          60 :     unsigned &I = Result.first->second;
     118          60 :     if (Result.second) {
     119         120 :       Vector.push_back(std::make_pair(KV.first, KV.second));
     120         120 :       I = Vector.size() - 1;
     121             :       return std::make_pair(std::prev(end()), true);
     122             :     }
     123           0 :     return std::make_pair(begin() + I, false);
     124             :   }
     125             : 
     126      233459 :   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
     127             :     // Copy KV.first into the map, then move it into the vector.
     128      232281 :     std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
     129      233459 :     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
     130      233459 :     unsigned &I = Result.first->second;
     131      233459 :     if (Result.second) {
     132      151009 :       Vector.push_back(std::move(KV));
     133      301785 :       I = Vector.size() - 1;
     134             :       return std::make_pair(std::prev(end()), true);
     135             :     }
     136       82450 :     return std::make_pair(begin() + I, false);
     137             :   }
     138             : 
     139           1 :   size_type count(const KeyT &Key) const {
     140      778703 :     typename MapType::const_iterator Pos = Map.find(Key);
     141      778562 :     return Pos == Map.end()? 0 : 1;
     142             :   }
     143             : 
     144     8806516 :   iterator find(const KeyT &Key) {
     145    17613032 :     typename MapType::const_iterator Pos = Map.find(Key);
     146           0 :     return Pos == Map.end()? Vector.end() :
     147    19405259 :                             (Vector.begin() + Pos->second);
     148             :   }
     149             : 
     150     2433911 :   const_iterator find(const KeyT &Key) const {
     151     2433911 :     typename MapType::const_iterator Pos = Map.find(Key);
     152             :     return Pos == Map.end()? Vector.end() :
     153     4867641 :                             (Vector.begin() + Pos->second);
     154             :   }
     155             : 
     156             :   /// \brief Remove the last element from the vector.
     157       27121 :   void pop_back() {
     158       54240 :     typename MapType::iterator Pos = Map.find(Vector.back().first);
     159       27121 :     Map.erase(Pos);
     160             :     Vector.pop_back();
     161       27121 :   }
     162             : 
     163             :   /// \brief Remove the element given by Iterator.
     164             :   ///
     165             :   /// Returns an iterator to the element following the one which was removed,
     166             :   /// which may be end().
     167             :   ///
     168             :   /// \note This is a deceivingly expensive operation (linear time).  It's
     169             :   /// usually better to use \a remove_if() if possible.
     170      156944 :   typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
     171      156944 :     Map.erase(Iterator->first);
     172       28979 :     auto Next = Vector.erase(Iterator);
     173      156944 :     if (Next == Vector.end())
     174       86227 :       return Next;
     175             : 
     176             :     // Update indices in the map.
     177       70721 :     size_t Index = Next - Vector.begin();
     178     1196227 :     for (auto &I : Map) {
     179             :       assert(I.second != Index && "Index was already erased!");
     180     1054793 :       if (I.second > Index)
     181      389153 :         --I.second;
     182             :     }
     183       70717 :     return Next;
     184             :   }
     185             : 
     186             :   /// \brief Remove all elements with the key value Key.
     187             :   ///
     188             :   /// Returns the number of elements removed.
     189     2170051 :   size_type erase(const KeyT &Key) {
     190     2170051 :     auto Iterator = find(Key);
     191     2170051 :     if (Iterator == end())
     192             :       return 0;
     193      156400 :     erase(Iterator);
     194       27925 :     return 1;
     195             :   }
     196             : 
     197             :   /// \brief Remove the elements that match the predicate.
     198             :   ///
     199             :   /// Erase all elements that match \c Pred in a single pass.  Takes linear
     200             :   /// time.
     201             :   template <class Predicate> void remove_if(Predicate Pred);
     202             : };
     203             : 
     204             : template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
     205             : template <class Function>
     206          17 : void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
     207             :   auto O = Vector.begin();
     208        2991 :   for (auto I = O, E = Vector.end(); I != E; ++I) {
     209        4473 :     if (Pred(*I)) {
     210             :       // Erase from the map.
     211        1493 :       Map.erase(I->first);
     212             :       continue;
     213             :     }
     214             : 
     215        1469 :     if (I != O) {
     216             :       // Move the value and update the index in the map.
     217             :       *O = std::move(*I);
     218        2944 :       Map[O->first] = O - Vector.begin();
     219             :     }
     220           6 :     ++O;
     221             :   }
     222             :   // Erase trailing entries in the vector.
     223          14 :   Vector.erase(O, Vector.end());
     224          17 : }
     225             : 
     226             : /// \brief A MapVector that performs no allocations if smaller than a certain
     227             : /// size.
     228             : template <typename KeyT, typename ValueT, unsigned N>
     229      451102 : struct SmallMapVector
     230             :     : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
     231             :                 SmallVector<std::pair<KeyT, ValueT>, N>> {
     232             : };
     233             : 
     234             : } // end namespace llvm
     235             : 
     236             : #endif // LLVM_ADT_MAPVECTOR_H

Generated by: LCOV version 1.13