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

          Line data    Source code
       1             : //===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- 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 the SmallBitVector class.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #ifndef LLVM_ADT_SMALLBITVECTOR_H
      15             : #define LLVM_ADT_SMALLBITVECTOR_H
      16             : 
      17             : #include "llvm/ADT/BitVector.h"
      18             : #include "llvm/ADT/iterator_range.h"
      19             : #include "llvm/Support/MathExtras.h"
      20             : #include <algorithm>
      21             : #include <cassert>
      22             : #include <climits>
      23             : #include <cstddef>
      24             : #include <cstdint>
      25             : #include <limits>
      26             : #include <utility>
      27             : 
      28             : namespace llvm {
      29             : 
      30             : /// This is a 'bitvector' (really, a variable-sized bit array), optimized for
      31             : /// the case when the array is small. It contains one pointer-sized field, which
      32             : /// is directly used as a plain collection of bits when possible, or as a
      33             : /// pointer to a larger heap-allocated array when necessary. This allows normal
      34             : /// "small" cases to be fast without losing generality for large inputs.
      35             : class SmallBitVector {
      36             :   // TODO: In "large" mode, a pointer to a BitVector is used, leading to an
      37             :   // unnecessary level of indirection. It would be more efficient to use a
      38             :   // pointer to memory containing size, allocation size, and the array of bits.
      39             :   uintptr_t X = 1;
      40             : 
      41             :   enum {
      42             :     // The number of bits in this class.
      43             :     NumBaseBits = sizeof(uintptr_t) * CHAR_BIT,
      44             : 
      45             :     // One bit is used to discriminate between small and large mode. The
      46             :     // remaining bits are used for the small-mode representation.
      47             :     SmallNumRawBits = NumBaseBits - 1,
      48             : 
      49             :     // A few more bits are used to store the size of the bit set in small mode.
      50             :     // Theoretically this is a ceil-log2. These bits are encoded in the most
      51             :     // significant bits of the raw bits.
      52             :     SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
      53             :                         NumBaseBits == 64 ? 6 :
      54             :                         SmallNumRawBits),
      55             : 
      56             :     // The remaining bits are used to store the actual set in small mode.
      57             :     SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits
      58             :   };
      59             : 
      60             :   static_assert(NumBaseBits == 64 || NumBaseBits == 32,
      61             :                 "Unsupported word size");
      62             : 
      63             : public:
      64             :   using size_type = unsigned;
      65             : 
      66             :   // Encapsulation of a single bit.
      67             :   class reference {
      68             :     SmallBitVector &TheVector;
      69             :     unsigned BitPos;
      70             : 
      71             :   public:
      72             :     reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}
      73             : 
      74             :     reference(const reference&) = default;
      75             : 
      76             :     reference& operator=(reference t) {
      77           4 :       *this = bool(t);
      78             :       return *this;
      79             :     }
      80             : 
      81     1498287 :     reference& operator=(bool t) {
      82     1498287 :       if (t)
      83     1433433 :         TheVector.set(BitPos);
      84             :       else
      85       64856 :         TheVector.reset(BitPos);
      86     1498287 :       return *this;
      87             :     }
      88             : 
      89             :     operator bool() const {
      90      172059 :       return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);
      91             :     }
      92             :   };
      93             : 
      94             : private:
      95             :   bool isSmall() const {
      96    11211278 :     return X & uintptr_t(1);
      97             :   }
      98             : 
      99             :   BitVector *getPointer() const {
     100             :     assert(!isSmall());
     101      331301 :     return reinterpret_cast<BitVector *>(X);
     102             :   }
     103             : 
     104             :   void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
     105     1188201 :     X = 1;
     106     1188201 :     setSmallSize(NewSize);
     107     1188201 :     setSmallBits(NewSmallBits);
     108             :   }
     109             : 
     110             :   void switchToLarge(BitVector *BV) {
     111       12985 :     X = reinterpret_cast<uintptr_t>(BV);
     112             :     assert(!isSmall() && "Tried to use an unaligned pointer");
     113             :   }
     114             : 
     115             :   // Return all the bits used for the "small" representation; this includes
     116             :   // bits for the size as well as the element bits.
     117             :   uintptr_t getSmallRawBits() const {
     118             :     assert(isSmall());
     119     5443941 :     return X >> 1;
     120             :   }
     121             : 
     122             :   void setSmallRawBits(uintptr_t NewRawBits) {
     123             :     assert(isSmall());
     124     4104610 :     X = (NewRawBits << 1) | uintptr_t(1);
     125             :   }
     126             : 
     127             :   // Return the size.
     128    15840854 :   size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
     129             : 
     130             :   void setSmallSize(size_t Size) {
     131     1894927 :     setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
     132             :   }
     133             : 
     134             :   // Return the element bits.
     135             :   uintptr_t getSmallBits() const {
     136    13264284 :     return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
     137             :   }
     138             : 
     139             :   void setSmallBits(uintptr_t NewBits) {
     140    11253743 :     setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
     141     3751248 :                     (getSmallSize() << SmallNumDataBits));
     142             :   }
     143             : 
     144             : public:
     145             :   /// Creates an empty bitvector.
     146      380364 :   SmallBitVector() = default;
     147             : 
     148             :   /// Creates a bitvector of specified number of bits. All bits are initialized
     149             :   /// to the specified value.
     150      908231 :   explicit SmallBitVector(unsigned s, bool t = false) {
     151      736847 :     if (s <= SmallNumDataBits)
     152      907440 :       switchToSmall(t ? ~uintptr_t(0) : 0, s);
     153             :     else
     154         791 :       switchToLarge(new BitVector(s, t));
     155      736847 :   }
     156             : 
     157             :   /// SmallBitVector copy ctor.
     158        6605 :   SmallBitVector(const SmallBitVector &RHS) {
     159        6605 :     if (RHS.isSmall())
     160        6600 :       X = RHS.X;
     161             :     else
     162           5 :       switchToLarge(new BitVector(*RHS.getPointer()));
     163        6605 :   }
     164             : 
     165      145554 :   SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
     166       42480 :     RHS.X = 1;
     167             :   }
     168             : 
     169     7595780 :   ~SmallBitVector() {
     170     3797890 :     if (!isSmall())
     171       25966 :       delete getPointer();
     172     3797890 :   }
     173             : 
     174             :   using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
     175             :   using set_iterator = const_set_bits_iterator;
     176             : 
     177             :   const_set_bits_iterator set_bits_begin() const {
     178       19065 :     return const_set_bits_iterator(*this);
     179             :   }
     180             : 
     181             :   const_set_bits_iterator set_bits_end() const {
     182       19064 :     return const_set_bits_iterator(*this, -1);
     183             :   }
     184             : 
     185             :   iterator_range<const_set_bits_iterator> set_bits() const {
     186       57177 :     return make_range(set_bits_begin(), set_bits_end());
     187             :   }
     188             : 
     189             :   /// Tests whether there are no bits in this bitvector.
     190             :   bool empty() const {
     191      104230 :     return isSmall() ? getSmallSize() == 0 : getPointer()->empty();
     192             :   }
     193             : 
     194             :   /// Returns the number of bits in this bitvector.
     195             :   size_t size() const {
     196     3291118 :     return isSmall() ? getSmallSize() : getPointer()->size();
     197             :   }
     198             : 
     199             :   /// Returns the number of bits which are set.
     200       31760 :   size_type count() const {
     201       31760 :     if (isSmall()) {
     202       31735 :       uintptr_t Bits = getSmallBits();
     203       31735 :       return countPopulation(Bits);
     204             :     }
     205          25 :     return getPointer()->count();
     206             :   }
     207             : 
     208             :   /// Returns true if any bit is set.
     209      508747 :   bool any() const {
     210      508747 :     if (isSmall())
     211      508743 :       return getSmallBits() != 0;
     212           4 :     return getPointer()->any();
     213             :   }
     214             : 
     215             :   /// Returns true if all bits are set.
     216       23780 :   bool all() const {
     217       23780 :     if (isSmall())
     218       47552 :       return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
     219           4 :     return getPointer()->all();
     220             :   }
     221             : 
     222             :   /// Returns true if none of the bits are set.
     223          21 :   bool none() const {
     224          21 :     if (isSmall())
     225          16 :       return getSmallBits() == 0;
     226          10 :     return getPointer()->none();
     227             :   }
     228             : 
     229             :   /// Returns the index of the first set bit, -1 if none of the bits are set.
     230      139126 :   int find_first() const {
     231      139126 :     if (isSmall()) {
     232      139112 :       uintptr_t Bits = getSmallBits();
     233      139112 :       if (Bits == 0)
     234             :         return -1;
     235      135718 :       return countTrailingZeros(Bits);
     236             :     }
     237          28 :     return getPointer()->find_first();
     238             :   }
     239             : 
     240           5 :   int find_last() const {
     241           5 :     if (isSmall()) {
     242           1 :       uintptr_t Bits = getSmallBits();
     243           1 :       if (Bits == 0)
     244             :         return -1;
     245           0 :       return NumBaseBits - countLeadingZeros(Bits);
     246             :     }
     247           8 :     return getPointer()->find_last();
     248             :   }
     249             : 
     250             :   /// Returns the index of the first unset bit, -1 if all of the bits are set.
     251           5 :   int find_first_unset() const {
     252           5 :     if (isSmall()) {
     253           2 :       if (count() == getSmallSize())
     254             :         return -1;
     255             : 
     256           0 :       uintptr_t Bits = getSmallBits();
     257           0 :       return countTrailingOnes(Bits);
     258             :     }
     259           8 :     return getPointer()->find_first_unset();
     260             :   }
     261             : 
     262           5 :   int find_last_unset() const {
     263           5 :     if (isSmall()) {
     264           2 :       if (count() == getSmallSize())
     265             :         return -1;
     266             : 
     267           0 :       uintptr_t Bits = getSmallBits();
     268           0 :       return NumBaseBits - countLeadingOnes(Bits);
     269             :     }
     270           8 :     return getPointer()->find_last_unset();
     271             :   }
     272             : 
     273             :   /// Returns the index of the next set bit following the "Prev" bit.
     274             :   /// Returns -1 if the next set bit is not found.
     275      115759 :   int find_next(unsigned Prev) const {
     276      115759 :     if (isSmall()) {
     277      115704 :       uintptr_t Bits = getSmallBits();
     278             :       // Mask off previous bits.
     279      115704 :       Bits &= ~uintptr_t(0) << (Prev + 1);
     280      144223 :       if (Bits == 0 || Prev + 1 >= getSmallSize())
     281             :         return -1;
     282       28519 :       return countTrailingZeros(Bits);
     283             :     }
     284         110 :     return getPointer()->find_next(Prev);
     285             :   }
     286             : 
     287             :   /// Returns the index of the next unset bit following the "Prev" bit.
     288             :   /// Returns -1 if the next unset bit is not found.
     289          12 :   int find_next_unset(unsigned Prev) const {
     290          12 :     if (isSmall()) {
     291           0 :       ++Prev;
     292           0 :       uintptr_t Bits = getSmallBits();
     293             :       // Mask in previous bits.
     294           0 :       uintptr_t Mask = (1 << Prev) - 1;
     295           0 :       Bits |= Mask;
     296             : 
     297           0 :       if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
     298             :         return -1;
     299           0 :       return countTrailingOnes(Bits);
     300             :     }
     301          24 :     return getPointer()->find_next_unset(Prev);
     302             :   }
     303             : 
     304             :   /// find_prev - Returns the index of the first set bit that precedes the
     305             :   /// the bit at \p PriorTo.  Returns -1 if all previous bits are unset.
     306           8 :   int find_prev(unsigned PriorTo) const {
     307           8 :     if (isSmall()) {
     308           0 :       if (PriorTo == 0)
     309             :         return -1;
     310             : 
     311           0 :       --PriorTo;
     312           0 :       uintptr_t Bits = getSmallBits();
     313           0 :       Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
     314           0 :       if (Bits == 0)
     315             :         return -1;
     316             : 
     317           0 :       return NumBaseBits - countLeadingZeros(Bits) - 1;
     318             :     }
     319          16 :     return getPointer()->find_prev(PriorTo);
     320             :   }
     321             : 
     322             :   /// Clear all bits.
     323      280761 :   void clear() {
     324      280761 :     if (!isSmall())
     325           4 :       delete getPointer();
     326      280761 :     switchToSmall(0, 0);
     327      280761 :   }
     328             : 
     329             :   /// Grow or shrink the bitvector.
     330      371699 :   void resize(unsigned N, bool t = false) {
     331      371699 :     if (!isSmall()) {
     332        6147 :       getPointer()->resize(N, t);
     333      365552 :     } else if (SmallNumDataBits >= N) {
     334      353417 :       uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0;
     335      706726 :       setSmallSize(N);
     336      353363 :       setSmallBits(NewBits | getSmallBits());
     337             :     } else {
     338       12189 :       BitVector *BV = new BitVector(N, t);
     339       12189 :       uintptr_t OldBits = getSmallBits();
     340       24529 :       for (size_t i = 0, e = getSmallSize(); i != e; ++i)
     341         453 :         (*BV)[i] = (OldBits >> i) & 1;
     342             :       switchToLarge(BV);
     343             :     }
     344      371699 :   }
     345             : 
     346             :   void reserve(unsigned N) {
     347             :     if (isSmall()) {
     348             :       if (N > SmallNumDataBits) {
     349             :         uintptr_t OldBits = getSmallRawBits();
     350             :         size_t SmallSize = getSmallSize();
     351             :         BitVector *BV = new BitVector(SmallSize);
     352             :         for (size_t i = 0; i < SmallSize; ++i)
     353             :           if ((OldBits >> i) & 1)
     354             :             BV->set(i);
     355             :         BV->reserve(N);
     356             :         switchToLarge(BV);
     357             :       }
     358             :     } else {
     359             :       getPointer()->reserve(N);
     360             :     }
     361             :   }
     362             : 
     363             :   // Set, reset, flip
     364           6 :   SmallBitVector &set() {
     365           6 :     if (isSmall())
     366             :       setSmallBits(~uintptr_t(0));
     367             :     else
     368           2 :       getPointer()->set();
     369           6 :     return *this;
     370             :   }
     371             : 
     372     1694077 :   SmallBitVector &set(unsigned Idx) {
     373     1694077 :     if (isSmall()) {
     374             :       assert(Idx <= static_cast<unsigned>(
     375             :                         std::numeric_limits<uintptr_t>::digits) &&
     376             :              "undefined behavior");
     377     1655119 :       setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
     378             :     }
     379             :     else
     380       38958 :       getPointer()->set(Idx);
     381     1694077 :     return *this;
     382             :   }
     383             : 
     384             :   /// Efficiently set a range of bits in [I, E)
     385      160932 :   SmallBitVector &set(unsigned I, unsigned E) {
     386             :     assert(I <= E && "Attempted to set backwards range!");
     387             :     assert(E <= size() && "Attempted to set out-of-bounds range!");
     388      160932 :     if (I == E) return *this;
     389      160932 :     if (isSmall()) {
     390      160833 :       uintptr_t EMask = ((uintptr_t)1) << E;
     391      160833 :       uintptr_t IMask = ((uintptr_t)1) << I;
     392      160833 :       uintptr_t Mask = EMask - IMask;
     393      160833 :       setSmallBits(getSmallBits() | Mask);
     394             :     } else
     395          99 :       getPointer()->set(I, E);
     396             :     return *this;
     397             :   }
     398             : 
     399       84759 :   SmallBitVector &reset() {
     400       84759 :     if (isSmall())
     401             :       setSmallBits(0);
     402             :     else
     403       21625 :       getPointer()->reset();
     404       84759 :     return *this;
     405             :   }
     406             : 
     407       79585 :   SmallBitVector &reset(unsigned Idx) {
     408       79585 :     if (isSmall())
     409       61014 :       setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
     410             :     else
     411       18571 :       getPointer()->reset(Idx);
     412       79585 :     return *this;
     413             :   }
     414             : 
     415             :   /// Efficiently reset a range of bits in [I, E)
     416      219522 :   SmallBitVector &reset(unsigned I, unsigned E) {
     417             :     assert(I <= E && "Attempted to reset backwards range!");
     418             :     assert(E <= size() && "Attempted to reset out-of-bounds range!");
     419      219522 :     if (I == E) return *this;
     420      219522 :     if (isSmall()) {
     421      219519 :       uintptr_t EMask = ((uintptr_t)1) << E;
     422      219519 :       uintptr_t IMask = ((uintptr_t)1) << I;
     423      219519 :       uintptr_t Mask = EMask - IMask;
     424      219519 :       setSmallBits(getSmallBits() & ~Mask);
     425             :     } else
     426           3 :       getPointer()->reset(I, E);
     427             :     return *this;
     428             :   }
     429             : 
     430        2998 :   SmallBitVector &flip() {
     431        2998 :     if (isSmall())
     432        2995 :       setSmallBits(~getSmallBits());
     433             :     else
     434           3 :       getPointer()->flip();
     435        2998 :     return *this;
     436             :   }
     437             : 
     438           2 :   SmallBitVector &flip(unsigned Idx) {
     439           2 :     if (isSmall())
     440           0 :       setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
     441             :     else
     442           2 :       getPointer()->flip(Idx);
     443           2 :     return *this;
     444             :   }
     445             : 
     446             :   // No argument flip.
     447             :   SmallBitVector operator~() const {
     448             :     return SmallBitVector(*this).flip();
     449             :   }
     450             : 
     451             :   // Indexing.
     452             :   reference operator[](unsigned Idx) {
     453             :     assert(Idx < size() && "Out-of-bounds Bit access.");
     454     1670344 :     return reference(*this, Idx);
     455             :   }
     456             : 
     457     1645382 :   bool operator[](unsigned Idx) const {
     458             :     assert(Idx < size() && "Out-of-bounds Bit access.");
     459     1645382 :     if (isSmall())
     460     1606685 :       return ((getSmallBits() >> Idx) & 1) != 0;
     461       77394 :     return getPointer()->operator[](Idx);
     462             :   }
     463             : 
     464             :   bool test(unsigned Idx) const {
     465        1175 :     return (*this)[Idx];
     466             :   }
     467             : 
     468             :   /// Test if any common bits are set.
     469          10 :   bool anyCommon(const SmallBitVector &RHS) const {
     470          11 :     if (isSmall() && RHS.isSmall())
     471           2 :       return (getSmallBits() & RHS.getSmallBits()) != 0;
     472          18 :     if (!isSmall() && !RHS.isSmall())
     473          16 :       return getPointer()->anyCommon(*RHS.getPointer());
     474             : 
     475           4 :     for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
     476           0 :       if (test(i) && RHS.test(i))
     477             :         return true;
     478             :     return false;
     479             :   }
     480             : 
     481             :   // Comparison operators.
     482       74398 :   bool operator==(const SmallBitVector &RHS) const {
     483      148796 :     if (size() != RHS.size())
     484             :       return false;
     485       74398 :     if (isSmall())
     486      105644 :       return getSmallBits() == RHS.getSmallBits();
     487             :     else
     488       43152 :       return *getPointer() == *RHS.getPointer();
     489             :   }
     490             : 
     491             :   bool operator!=(const SmallBitVector &RHS) const {
     492       74373 :     return !(*this == RHS);
     493             :   }
     494             : 
     495             :   // Intersection, union, disjoint union.
     496         349 :   SmallBitVector &operator&=(const SmallBitVector &RHS) {
     497        1047 :     resize(std::max(size(), RHS.size()));
     498         349 :     if (isSmall())
     499         698 :       setSmallBits(getSmallBits() & RHS.getSmallBits());
     500           0 :     else if (!RHS.isSmall())
     501           0 :       getPointer()->operator&=(*RHS.getPointer());
     502             :     else {
     503           0 :       SmallBitVector Copy = RHS;
     504           0 :       Copy.resize(size());
     505           0 :       getPointer()->operator&=(*Copy.getPointer());
     506             :     }
     507         349 :     return *this;
     508             :   }
     509             : 
     510             :   /// Reset bits that are set in RHS. Same as *this &= ~RHS.
     511           7 :   SmallBitVector &reset(const SmallBitVector &RHS) {
     512          12 :     if (isSmall() && RHS.isSmall())
     513           6 :       setSmallBits(getSmallBits() & ~RHS.getSmallBits());
     514           6 :     else if (!isSmall() && !RHS.isSmall())
     515           2 :       getPointer()->reset(*RHS.getPointer());
     516             :     else
     517         162 :       for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
     518         150 :         if (RHS.test(i))
     519         100 :           reset(i);
     520             : 
     521           7 :     return *this;
     522             :   }
     523             : 
     524             :   /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
     525          40 :   bool test(const SmallBitVector &RHS) const {
     526          48 :     if (isSmall() && RHS.isSmall())
     527           8 :       return (getSmallBits() & ~RHS.getSmallBits()) != 0;
     528          68 :     if (!isSmall() && !RHS.isSmall())
     529          60 :       return getPointer()->test(*RHS.getPointer());
     530             : 
     531             :     unsigned i, e;
     532         224 :     for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
     533         304 :       if (test(i) && !RHS.test(i))
     534             :         return true;
     535             : 
     536           4 :     for (e = size(); i != e; ++i)
     537           1 :       if (test(i))
     538             :         return true;
     539             : 
     540             :     return false;
     541             :   }
     542             : 
     543       52838 :   SmallBitVector &operator|=(const SmallBitVector &RHS) {
     544      158514 :     resize(std::max(size(), RHS.size()));
     545       52838 :     if (isSmall())
     546       93404 :       setSmallBits(getSmallBits() | RHS.getSmallBits());
     547        6136 :     else if (!RHS.isSmall())
     548       12272 :       getPointer()->operator|=(*RHS.getPointer());
     549             :     else {
     550           0 :       SmallBitVector Copy = RHS;
     551           0 :       Copy.resize(size());
     552           0 :       getPointer()->operator|=(*Copy.getPointer());
     553             :     }
     554       52838 :     return *this;
     555             :   }
     556             : 
     557           1 :   SmallBitVector &operator^=(const SmallBitVector &RHS) {
     558           3 :     resize(std::max(size(), RHS.size()));
     559           1 :     if (isSmall())
     560           0 :       setSmallBits(getSmallBits() ^ RHS.getSmallBits());
     561           1 :     else if (!RHS.isSmall())
     562           2 :       getPointer()->operator^=(*RHS.getPointer());
     563             :     else {
     564           0 :       SmallBitVector Copy = RHS;
     565           0 :       Copy.resize(size());
     566           0 :       getPointer()->operator^=(*Copy.getPointer());
     567             :     }
     568           1 :     return *this;
     569             :   }
     570             : 
     571           6 :   SmallBitVector &operator<<=(unsigned N) {
     572           6 :     if (isSmall())
     573           3 :       setSmallBits(getSmallBits() << N);
     574             :     else
     575           3 :       getPointer()->operator<<=(N);
     576           6 :     return *this;
     577             :   }
     578             : 
     579           6 :   SmallBitVector &operator>>=(unsigned N) {
     580           6 :     if (isSmall())
     581           4 :       setSmallBits(getSmallBits() >> N);
     582             :     else
     583           2 :       getPointer()->operator>>=(N);
     584           6 :     return *this;
     585             :   }
     586             : 
     587             :   // Assignment operator.
     588      145559 :   const SmallBitVector &operator=(const SmallBitVector &RHS) {
     589      145559 :     if (isSmall()) {
     590      104077 :       if (RHS.isSmall())
     591      104077 :         X = RHS.X;
     592             :       else
     593           0 :         switchToLarge(new BitVector(*RHS.getPointer()));
     594             :     } else {
     595       41482 :       if (!RHS.isSmall())
     596       82964 :         *getPointer() = *RHS.getPointer();
     597             :       else {
     598           0 :         delete getPointer();
     599           0 :         X = RHS.X;
     600             :       }
     601             :     }
     602      145559 :     return *this;
     603             :   }
     604             : 
     605             :   const SmallBitVector &operator=(SmallBitVector &&RHS) {
     606             :     if (this != &RHS) {
     607           3 :       clear();
     608             :       swap(RHS);
     609             :     }
     610             :     return *this;
     611             :   }
     612             : 
     613             :   void swap(SmallBitVector &RHS) {
     614          10 :     std::swap(X, RHS.X);
     615             :   }
     616             : 
     617             :   /// Add '1' bits from Mask to this vector. Don't resize.
     618             :   /// This computes "*this |= Mask".
     619           6 :   void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
     620           6 :     if (isSmall())
     621           5 :       applyMask<true, false>(Mask, MaskWords);
     622             :     else
     623           1 :       getPointer()->setBitsInMask(Mask, MaskWords);
     624           6 :   }
     625             : 
     626             :   /// Clear any bits in this vector that are set in Mask. Don't resize.
     627             :   /// This computes "*this &= ~Mask".
     628             :   void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
     629             :     if (isSmall())
     630             :       applyMask<false, false>(Mask, MaskWords);
     631             :     else
     632             :       getPointer()->clearBitsInMask(Mask, MaskWords);
     633             :   }
     634             : 
     635             :   /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
     636             :   /// This computes "*this |= ~Mask".
     637           3 :   void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
     638           3 :     if (isSmall())
     639           0 :       applyMask<true, true>(Mask, MaskWords);
     640             :     else
     641           3 :       getPointer()->setBitsNotInMask(Mask, MaskWords);
     642           3 :   }
     643             : 
     644             :   /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
     645             :   /// This computes "*this &= Mask".
     646           1 :   void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
     647           1 :     if (isSmall())
     648           0 :       applyMask<false, true>(Mask, MaskWords);
     649             :     else
     650           1 :       getPointer()->clearBitsNotInMask(Mask, MaskWords);
     651           1 :   }
     652             : 
     653             : private:
     654             :   template <bool AddBits, bool InvertMask>
     655             :   void applyMask(const uint32_t *Mask, unsigned MaskWords) {
     656             :     assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
     657           5 :     uintptr_t M = Mask[0];
     658             :     if (NumBaseBits == 64)
     659           5 :       M |= uint64_t(Mask[1]) << 32;
     660             :     if (InvertMask)
     661           0 :       M = ~M;
     662             :     if (AddBits)
     663          10 :       setSmallBits(getSmallBits() | M);
     664             :     else
     665           0 :       setSmallBits(getSmallBits() & ~M);
     666             :   }
     667             : };
     668             : 
     669             : inline SmallBitVector
     670             : operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
     671             :   SmallBitVector Result(LHS);
     672             :   Result &= RHS;
     673             :   return Result;
     674             : }
     675             : 
     676             : inline SmallBitVector
     677             : operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
     678        2513 :   SmallBitVector Result(LHS);
     679        2513 :   Result |= RHS;
     680             :   return Result;
     681             : }
     682             : 
     683             : inline SmallBitVector
     684             : operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
     685             :   SmallBitVector Result(LHS);
     686             :   Result ^= RHS;
     687             :   return Result;
     688             : }
     689             : 
     690             : } // end namespace llvm
     691             : 
     692             : namespace std {
     693             : 
     694             : /// Implement std::swap in terms of BitVector swap.
     695             : inline void
     696             : swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
     697           2 :   LHS.swap(RHS);
     698             : }
     699             : 
     700             : } // end namespace std
     701             : 
     702             : #endif // LLVM_ADT_SMALLBITVECTOR_H

Generated by: LCOV version 1.13