LCOV - code coverage report
Current view: top level - include/llvm/ADT - DenseSet.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 50 51 98.0 %
Date: 2017-09-14 15:23:50 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/ADT/DenseSet.h - Dense probed hash table ------------*- 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 defines the DenseSet and SmallDenseSet classes.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #ifndef LLVM_ADT_DENSESET_H
      15             : #define LLVM_ADT_DENSESET_H
      16             : 
      17             : #include "llvm/ADT/DenseMap.h"
      18             : #include "llvm/ADT/DenseMapInfo.h"
      19             : #include "llvm/Support/type_traits.h"
      20             : #include <algorithm> 
      21             : #include <cstddef>
      22             : #include <initializer_list>
      23             : #include <iterator>
      24             : #include <utility>
      25             : 
      26             : namespace llvm {
      27             : 
      28             : namespace detail {
      29             : 
      30             : struct DenseSetEmpty {};
      31             : 
      32             : // Use the empty base class trick so we can create a DenseMap where the buckets
      33             : // contain only a single item.
      34           0 : template <typename KeyT> class DenseSetPair : public DenseSetEmpty {
      35             :   KeyT key;
      36             : 
      37             : public:
      38   637524441 :   KeyT &getFirst() { return key; }
      39      458364 :   const KeyT &getFirst() const { return key; }
      40             :   DenseSetEmpty &getSecond() { return *this; }
      41             :   const DenseSetEmpty &getSecond() const { return *this; }
      42             : };
      43             : 
      44             : /// Base class for DenseSet and DenseSmallSet.
      45             : ///
      46             : /// MapTy should be either
      47             : ///
      48             : ///   DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
      49             : ///            detail::DenseSetPair<ValueT>>
      50             : ///
      51             : /// or the equivalent SmallDenseMap type.  ValueInfoT must implement the
      52             : /// DenseMapInfo "concept".
      53             : template <typename ValueT, typename MapTy, typename ValueInfoT>
      54    89510954 : class DenseSetImpl {
      55             :   static_assert(sizeof(typename MapTy::value_type) == sizeof(ValueT),
      56             :                 "DenseMap buckets unexpectedly large!");
      57             :   MapTy TheMap;
      58             : 
      59             :   template <typename T>
      60             :   using const_arg_type_t = typename const_pointer_or_const_ref<T>::type;
      61             : 
      62             : public:
      63             :   using key_type = ValueT;
      64             :   using value_type = ValueT;
      65             :   using size_type = unsigned;
      66             : 
      67    77701203 :   explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
      68             : 
      69       14690 :   DenseSetImpl(std::initializer_list<ValueT> Elems)
      70       29380 :       : DenseSetImpl(Elems.size()) {
      71       29380 :     insert(Elems.begin(), Elems.end());
      72       14690 :   }
      73             : 
      74      969444 :   bool empty() const { return TheMap.empty(); }
      75       30372 :   size_type size() const { return TheMap.size(); }
      76          16 :   size_t getMemorySize() const { return TheMap.getMemorySize(); }
      77             : 
      78             :   /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
      79             :   /// the Size of the set.
      80             :   void resize(size_t Size) { TheMap.resize(Size); }
      81             : 
      82             :   /// Grow the DenseSet so that it can contain at least \p NumEntries items
      83             :   /// before resizing again.
      84        3492 :   void reserve(size_t Size) { TheMap.reserve(Size); }
      85             : 
      86             :   void clear() {
      87     7102185 :     TheMap.clear();
      88             :   }
      89             : 
      90             :   /// Return 1 if the specified key is in the set, 0 otherwise.
      91             :   size_type count(const_arg_type_t<ValueT> V) const {
      92    97935126 :     return TheMap.count(V);
      93             :   }
      94             : 
      95             :   bool erase(const ValueT &V) {
      96    30522718 :     return TheMap.erase(V);
      97             :   }
      98             : 
      99         115 :   void swap(DenseSetImpl &RHS) { TheMap.swap(RHS.TheMap); }
     100             : 
     101             :   // Iterators.
     102             : 
     103             :   class ConstIterator;
     104             : 
     105             :   class Iterator {
     106             :     typename MapTy::iterator I;
     107             :     friend class DenseSetImpl;
     108             :     friend class ConstIterator;
     109             : 
     110             :   public:
     111             :     using difference_type = typename MapTy::iterator::difference_type;
     112             :     using value_type = ValueT;
     113             :     using pointer = value_type *;
     114             :     using reference = value_type &;
     115             :     using iterator_category = std::forward_iterator_tag;
     116             : 
     117             :     Iterator() = default;
     118    21882229 :     Iterator(const typename MapTy::iterator &i) : I(i) {}
     119             : 
     120    24245025 :     ValueT &operator*() { return I->getFirst(); }
     121             :     const ValueT &operator*() const { return I->getFirst(); }
     122        2487 :     ValueT *operator->() { return &I->getFirst(); }
     123             :     const ValueT *operator->() const { return &I->getFirst(); }
     124             : 
     125     4695355 :     Iterator& operator++() { ++I; return *this; }
     126         384 :     Iterator operator++(int) { auto T = *this; ++I; return T; }
     127    16126618 :     bool operator==(const ConstIterator& X) const { return I == X.I; }
     128     9811096 :     bool operator!=(const ConstIterator& X) const { return I != X.I; }
     129             :   };
     130             : 
     131             :   class ConstIterator {
     132             :     typename MapTy::const_iterator I;
     133             :     friend class DenseSet;
     134             :     friend class Iterator;
     135             : 
     136             :   public:
     137             :     using difference_type = typename MapTy::const_iterator::difference_type;
     138             :     using value_type = ValueT;
     139             :     using pointer = value_type *;
     140             :     using reference = value_type &;
     141             :     using iterator_category = std::forward_iterator_tag;
     142             : 
     143         124 :     ConstIterator() = default;
     144    51875396 :     ConstIterator(const Iterator &B) : I(B.I) {}
     145      956044 :     ConstIterator(const typename MapTy::const_iterator &i) : I(i) {}
     146             : 
     147    14516586 :     const ValueT &operator*() const { return I->getFirst(); }
     148             :     const ValueT *operator->() const { return &I->getFirst(); }
     149             : 
     150    14454284 :     ConstIterator& operator++() { ++I; return *this; }
     151             :     ConstIterator operator++(int) { auto T = *this; ++I; return T; }
     152        1148 :     bool operator==(const ConstIterator& X) const { return I == X.I; }
     153    15409438 :     bool operator!=(const ConstIterator& X) const { return I != X.I; }
     154             :   };
     155             : 
     156             :   using iterator = Iterator;
     157             :   using const_iterator = ConstIterator;
     158             : 
     159    10212141 :   iterator begin() { return Iterator(TheMap.begin()); }
     160    42483850 :   iterator end() { return Iterator(TheMap.end()); }
     161             : 
     162     1821920 :   const_iterator begin() const { return ConstIterator(TheMap.begin()); }
     163     1912326 :   const_iterator end() const { return ConstIterator(TheMap.end()); }
     164             : 
     165      711292 :   iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
     166             :   const_iterator find(const_arg_type_t<ValueT> V) const {
     167       90152 :     return ConstIterator(TheMap.find(V));
     168             :   }
     169             : 
     170             :   /// Alternative version of find() which allows a different, and possibly less
     171             :   /// expensive, key type.
     172             :   /// The DenseMapInfo is responsible for supplying methods
     173             :   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
     174             :   /// used.
     175             :   template <class LookupKeyT>
     176             :   iterator find_as(const LookupKeyT &Val) {
     177    32138798 :     return Iterator(TheMap.find_as(Val));
     178             :   }
     179             :   template <class LookupKeyT>
     180             :   const_iterator find_as(const LookupKeyT &Val) const {
     181          16 :     return ConstIterator(TheMap.find_as(Val));
     182             :   }
     183             : 
     184      586562 :   void erase(Iterator I) { return TheMap.erase(I.I); }
     185             :   void erase(ConstIterator CI) { return TheMap.erase(CI.I); }
     186             : 
     187             :   std::pair<iterator, bool> insert(const ValueT &V) {
     188             :     detail::DenseSetEmpty Empty;
     189   148225312 :     return TheMap.try_emplace(V, Empty);
     190             :   }
     191             : 
     192             :   std::pair<iterator, bool> insert(ValueT &&V) {
     193             :     detail::DenseSetEmpty Empty;
     194    53973404 :     return TheMap.try_emplace(std::move(V), Empty);
     195             :   }
     196             : 
     197             :   /// Alternative version of insert that uses a different (and possibly less
     198             :   /// expensive) key type.
     199             :   template <typename LookupKeyT>
     200             :   std::pair<iterator, bool> insert_as(const ValueT &V,
     201             :                                       const LookupKeyT &LookupKey) {
     202     1614525 :     return TheMap.insert_as({V, detail::DenseSetEmpty()}, LookupKey);
     203             :   }
     204             :   template <typename LookupKeyT>
     205             :   std::pair<iterator, bool> insert_as(ValueT &&V, const LookupKeyT &LookupKey) {
     206             :     return TheMap.insert_as({std::move(V), detail::DenseSetEmpty()}, LookupKey);
     207             :   }
     208             : 
     209             :   // Range insertion of values.
     210             :   template<typename InputIt>
     211         244 :   void insert(InputIt I, InputIt E) {
     212       85070 :     for (; I != E; ++I)
     213       35061 :       insert(*I);
     214         244 :   }
     215             : };
     216             : 
     217             : } // end namespace detail
     218             : 
     219             : /// Implements a dense probed hash-table based set.
     220             : template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
     221    65524330 : class DenseSet : public detail::DenseSetImpl<
     222             :                      ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
     223             :                                       detail::DenseSetPair<ValueT>>,
     224             :                      ValueInfoT> {
     225             :   using BaseT =
     226             :       detail::DenseSetImpl<ValueT,
     227             :                            DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
     228             :                                     detail::DenseSetPair<ValueT>>,
     229             :                            ValueInfoT>;
     230             : 
     231             : public:
     232       14794 :   using BaseT::BaseT;
     233             : };
     234             : 
     235             : /// Implements a dense probed hash-table based set with some number of buckets
     236             : /// stored inline.
     237             : template <typename ValueT, unsigned InlineBuckets = 4,
     238             :           typename ValueInfoT = DenseMapInfo<ValueT>>
     239   101660334 : class SmallDenseSet
     240             :     : public detail::DenseSetImpl<
     241             :           ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
     242             :                                 ValueInfoT, detail::DenseSetPair<ValueT>>,
     243             :           ValueInfoT> {
     244             :   using BaseT = detail::DenseSetImpl<
     245             :       ValueT, SmallDenseMap<ValueT, detail::DenseSetEmpty, InlineBuckets,
     246             :                             ValueInfoT, detail::DenseSetPair<ValueT>>,
     247             :       ValueInfoT>;
     248             : 
     249             : public:
     250          12 :   using BaseT::BaseT;
     251             : };
     252             : 
     253             : } // end namespace llvm
     254             : 
     255             : #endif // LLVM_ADT_DENSESET_H

Generated by: LCOV version 1.13