LCOV - code coverage report
Current view: top level - include/llvm/ADT - SmallSet.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 38 39 97.4 %
Date: 2017-09-14 15:23:50 Functions: 107 110 97.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- 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 SmallSet class.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #ifndef LLVM_ADT_SMALLSET_H
      15             : #define LLVM_ADT_SMALLSET_H
      16             : 
      17             : #include "llvm/ADT/None.h"
      18             : #include "llvm/ADT/SmallPtrSet.h"
      19             : #include "llvm/ADT/SmallVector.h"
      20             : #include "llvm/Support/Compiler.h"
      21             : #include <cstddef>
      22             : #include <functional>
      23             : #include <set>
      24             : #include <utility>
      25             : 
      26             : namespace llvm {
      27             : 
      28             : /// SmallSet - This maintains a set of unique values, optimizing for the case
      29             : /// when the set is small (less than N).  In this case, the set can be
      30             : /// maintained with no mallocs.  If the set gets large, we expand to using an
      31             : /// std::set to maintain reasonable lookup times.
      32             : ///
      33             : /// Note that this set does not provide a way to iterate over members in the
      34             : /// set.
      35             : template <typename T, unsigned N, typename C = std::less<T>>
      36    56734004 : class SmallSet {
      37             :   /// Use a SmallVector to hold the elements here (even though it will never
      38             :   /// reach its 'large' stage) to avoid calling the default ctors of elements
      39             :   /// we will never use.
      40             :   SmallVector<T, N> Vector;
      41             :   std::set<T, C> Set;
      42             : 
      43             :   using VIterator = typename SmallVector<T, N>::const_iterator;
      44             :   using mutable_iterator = typename SmallVector<T, N>::iterator;
      45             : 
      46             :   // In small mode SmallPtrSet uses linear search for the elements, so it is
      47             :   // not a good idea to choose this value too high. You may consider using a
      48             :   // DenseSet<> instead if you expect many elements in the set.
      49             :   static_assert(N <= 32, "N should be small");
      50             : 
      51             : public:
      52             :   using size_type = size_t;
      53             : 
      54    56704650 :   SmallSet() = default;
      55             : 
      56             :   LLVM_NODISCARD bool empty() const {
      57     7618188 :     return Vector.empty() && Set.empty();
      58             :   }
      59             : 
      60             :   size_type size() const {
      61      801184 :     return isSmall() ? Vector.size() : Set.size();
      62             :   }
      63             : 
      64             :   /// count - Return 1 if the element is in the set, 0 otherwise.
      65    10541930 :   size_type count(const T &V) const {
      66    10541930 :     if (isSmall()) {
      67             :       // Since the collection is small, just do a linear search.
      68    10277850 :       return vfind(V) == Vector.end() ? 0 : 1;
      69             :     } else {
      70      369729 :       return Set.count(V);
      71             :     }
      72             :   }
      73             : 
      74             :   /// insert - Insert an element into the set if it isn't already there.
      75             :   /// Returns true if the element is inserted (it was not in the set before).
      76             :   /// The first value of the returned pair is unused and provided for
      77             :   /// partial compatibility with the standard library self-associative container
      78             :   /// concept.
      79             :   // FIXME: Add iterators that abstract over the small and large form, and then
      80             :   // return those here.
      81    23698715 :   std::pair<NoneType, bool> insert(const T &V) {
      82    23698715 :     if (!isSmall())
      83     3134360 :       return std::make_pair(None, Set.insert(V).second);
      84             : 
      85    22131535 :     VIterator I = vfind(V);
      86    22131770 :     if (I != Vector.end())    // Don't reinsert if it already exists.
      87     5965878 :       return std::make_pair(None, false);
      88    32331314 :     if (Vector.size() < N) {
      89    16111914 :       Vector.push_back(V);
      90    16111914 :       return std::make_pair(None, true);
      91             :     }
      92             : 
      93             :     // Otherwise, grow from vector to set.
      94      378666 :     while (!Vector.empty()) {
      95      974769 :       Set.insert(Vector.back());
      96      324923 :       Vector.pop_back();
      97             :     }
      98      107486 :     Set.insert(V);
      99       53743 :     return std::make_pair(None, true);
     100             :   }
     101             : 
     102             :   template <typename IterT>
     103             :   void insert(IterT I, IterT E) {
     104       61268 :     for (; I != E; ++I)
     105       29015 :       insert(*I);
     106             :   }
     107             : 
     108       40656 :   bool erase(const T &V) {
     109       40656 :     if (!isSmall())
     110       46058 :       return Set.erase(V);
     111       56175 :     for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
     112        8233 :       if (*I == V) {
     113        6137 :         Vector.erase(I);
     114        4939 :         return true;
     115             :       }
     116             :     return false;
     117             :   }
     118             : 
     119             :   void clear() {
     120     2848582 :     Vector.clear();
     121     2848582 :     Set.clear();
     122             :   }
     123             : 
     124             : private:
     125    69367178 :   bool isSmall() const { return Set.empty(); }
     126             : 
     127         312 :   VIterator vfind(const T &V) const {
     128   135541605 :     for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
     129    47131778 :       if (*I == V)
     130             :         return I;
     131           0 :     return Vector.end();
     132             :   }
     133             : };
     134             : 
     135             : /// If this set is of pointer values, transparently switch over to using
     136             : /// SmallPtrSet for performance.
     137             : template <typename PointeeType, unsigned N>
     138     6397120 : class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
     139             : 
     140             : } // end namespace llvm
     141             : 
     142             : #endif // LLVM_ADT_SMALLSET_H

Generated by: LCOV version 1.13