LCOV - code coverage report
Current view: top level - include/llvm/ADT - MapVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 89 90 98.9 %
Date: 2017-09-14 15:23:50 Functions: 232 243 95.5 %
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    30622025 : 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         509 :     Map.clear();
      54        1018 :     return std::move(Vector);
      55             :   }
      56             : 
      57      779885 :   size_type size() const { return Vector.size(); }
      58             : 
      59     8771512 :   iterator begin() { return Vector.begin(); }
      60       79460 :   const_iterator begin() const { return Vector.begin(); }
      61    18895637 :   iterator end() { return Vector.end(); }
      62      787550 :   const_iterator end() const { return Vector.end(); }
      63             : 
      64       23470 :   reverse_iterator rbegin() { return Vector.rbegin(); }
      65             :   const_reverse_iterator rbegin() const { return Vector.rbegin(); }
      66       23470 :   reverse_iterator rend() { return Vector.rend(); }
      67             :   const_reverse_iterator rend() const { return Vector.rend(); }
      68             : 
      69             :   bool empty() const {
      70    13490195 :     return Vector.empty();
      71             :   }
      72             : 
      73             :   std::pair<KeyT, ValueT>       &front()       { return Vector.front(); }
      74             :   const std::pair<KeyT, ValueT> &front() const { return Vector.front(); }
      75       69628 :   std::pair<KeyT, ValueT>       &back()        { return Vector.back(); }
      76             :   const std::pair<KeyT, ValueT> &back()  const { return Vector.back(); }
      77             : 
      78      143309 :   void clear() {
      79     3045049 :     Map.clear();
      80     5480597 :     Vector.clear();
      81      143309 :   }
      82             : 
      83             :   void swap(MapVector &RHS) {
      84         165 :     std::swap(Map, RHS.Map);
      85         330 :     std::swap(Vector, RHS.Vector);
      86             :   }
      87             : 
      88     9348127 :   ValueT &operator[](const KeyT &Key) {
      89    28044381 :     std::pair<KeyT, unsigned> Pair = std::make_pair(Key, 0);
      90    18696254 :     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
      91     9348127 :     unsigned &I = Result.first->second;
      92     9348127 :     if (Result.second) {
      93    18032572 :       Vector.push_back(std::make_pair(Key, ValueT()));
      94     9519162 :       I = Vector.size() - 1;
      95             :     }
      96    18696254 :     return Vector[I].second;
      97             :   }
      98             : 
      99             :   // Returns a copy of the value.  Only allowed if ValueT is copyable.
     100       58766 :   ValueT lookup(const KeyT &Key) const {
     101             :     static_assert(std::is_copy_constructible<ValueT>::value,
     102             :                   "Cannot call lookup() if ValueT is not copyable.");
     103       58766 :     typename MapType::const_iterator Pos = Map.find(Key);
     104      176548 :     return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
     105             :   }
     106             : 
     107          60 :   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
     108         180 :     std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
     109         120 :     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
     110          60 :     unsigned &I = Result.first->second;
     111          60 :     if (Result.second) {
     112         180 :       Vector.push_back(std::make_pair(KV.first, KV.second));
     113         120 :       I = Vector.size() - 1;
     114         240 :       return std::make_pair(std::prev(end()), true);
     115             :     }
     116           0 :     return std::make_pair(begin() + I, false);
     117             :   }
     118             : 
     119       87660 :   std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
     120             :     // Copy KV.first into the map, then move it into the vector.
     121      262980 :     std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
     122      175320 :     std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
     123       87660 :     unsigned &I = Result.first->second;
     124       87660 :     if (Result.second) {
     125      102694 :       Vector.push_back(std::move(KV));
     126      102772 :       I = Vector.size() - 1;
     127      205466 :       return std::make_pair(std::prev(end()), true);
     128             :     }
     129      145066 :     return std::make_pair(begin() + I, false);
     130             :   }
     131             : 
     132           1 :   size_type count(const KeyT &Key) const {
     133      672113 :     typename MapType::const_iterator Pos = Map.find(Key);
     134     1344226 :     return Pos == Map.end()? 0 : 1;
     135             :   }
     136             : 
     137     5737936 :   iterator find(const KeyT &Key) {
     138    11475872 :     typename MapType::const_iterator Pos = Map.find(Key);
     139    21841714 :     return Pos == Map.end()? Vector.end() :
     140    13684154 :                             (Vector.begin() + Pos->second);
     141             :   }
     142             : 
     143      711353 :   const_iterator find(const KeyT &Key) const {
     144      711353 :     typename MapType::const_iterator Pos = Map.find(Key);
     145     2102519 :     return Pos == Map.end()? Vector.end() :
     146     2165392 :                             (Vector.begin() + Pos->second);
     147             :   }
     148             : 
     149             :   /// \brief Remove the last element from the vector.
     150       17410 :   void pop_back() {
     151       34820 :     typename MapType::iterator Pos = Map.find(Vector.back().first);
     152       34820 :     Map.erase(Pos);
     153       17412 :     Vector.pop_back();
     154       17410 :   }
     155             : 
     156             :   /// \brief Remove the element given by Iterator.
     157             :   ///
     158             :   /// Returns an iterator to the element following the one which was removed,
     159             :   /// which may be end().
     160             :   ///
     161             :   /// \note This is a deceivingly expensive operation (linear time).  It's
     162             :   /// usually better to use \a remove_if() if possible.
     163       43503 :   typename VectorType::iterator erase(typename VectorType::iterator Iterator) {
     164       43503 :     Map.erase(Iterator->first);
     165      130505 :     auto Next = Vector.erase(Iterator);
     166      130501 :     if (Next == Vector.end())
     167       29709 :       return Next;
     168             : 
     169             :     // Update indices in the map.
     170       41378 :     size_t Index = Next - Vector.begin();
     171      161408 :     for (auto &I : Map) {
     172             :       assert(I.second != Index && "Index was already erased!");
     173      120026 :       if (I.second > Index)
     174       75004 :         --I.second;
     175             :     }
     176       13794 :     return Next;
     177             :   }
     178             : 
     179             :   /// \brief Remove all elements with the key value Key.
     180             :   ///
     181             :   /// Returns the number of elements removed.
     182      465803 :   size_type erase(const KeyT &Key) {
     183      465803 :     auto Iterator = find(Key);
     184      931602 :     if (Iterator == end())
     185             :       return 0;
     186       42969 :     erase(Iterator);
     187           3 :     return 1;
     188             :   }
     189             : 
     190             :   /// \brief Remove the elements that match the predicate.
     191             :   ///
     192             :   /// Erase all elements that match \c Pred in a single pass.  Takes linear
     193             :   /// time.
     194             :   template <class Predicate> void remove_if(Predicate Pred);
     195             : };
     196             : 
     197             : template <typename KeyT, typename ValueT, typename MapType, typename VectorType>
     198             : template <class Function>
     199          13 : void MapVector<KeyT, ValueT, MapType, VectorType>::remove_if(Function Pred) {
     200          26 :   auto O = Vector.begin();
     201        2203 :   for (auto I = O, E = Vector.end(); I != E; ++I) {
     202        5479 :     if (Pred(*I)) {
     203             :       // Erase from the map.
     204        1147 :       Map.erase(I->first);
     205             :       continue;
     206             :     }
     207             : 
     208        1019 :     if (I != O) {
     209             :       // Move the value and update the index in the map.
     210        2038 :       *O = std::move(*I);
     211        4070 :       Map[O->first] = O - Vector.begin();
     212             :     }
     213           6 :     ++O;
     214             :   }
     215             :   // Erase trailing entries in the vector.
     216          61 :   Vector.erase(O, Vector.end());
     217          13 : }
     218             : 
     219             : /// \brief A MapVector that performs no allocations if smaller than a certain
     220             : /// size.
     221             : template <typename KeyT, typename ValueT, unsigned N>
     222       25095 : struct SmallMapVector
     223             :     : MapVector<KeyT, ValueT, SmallDenseMap<KeyT, unsigned, N>,
     224             :                 SmallVector<std::pair<KeyT, ValueT>, N>> {
     225             : };
     226             : 
     227             : } // end namespace llvm
     228             : 
     229             : #endif // LLVM_ADT_MAPVECTOR_H

Generated by: LCOV version 1.13