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

          Line data    Source code
       1             : //===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector --*- 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 SparseBitVector class.  See the doxygen comment for
      11             : // SparseBitVector for more details on the algorithm used.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_ADT_SPARSEBITVECTOR_H
      16             : #define LLVM_ADT_SPARSEBITVECTOR_H
      17             : 
      18             : #include "llvm/Support/ErrorHandling.h"
      19             : #include "llvm/Support/MathExtras.h"
      20             : #include "llvm/Support/raw_ostream.h"
      21             : #include <cassert>
      22             : #include <climits>
      23             : #include <cstring>
      24             : #include <iterator>
      25             : #include <list>
      26             : 
      27             : namespace llvm {
      28             : 
      29             : /// SparseBitVector is an implementation of a bitvector that is sparse by only
      30             : /// storing the elements that have non-zero bits set.  In order to make this
      31             : /// fast for the most common cases, SparseBitVector is implemented as a linked
      32             : /// list of SparseBitVectorElements.  We maintain a pointer to the last
      33             : /// SparseBitVectorElement accessed (in the form of a list iterator), in order
      34             : /// to make multiple in-order test/set constant time after the first one is
      35             : /// executed.  Note that using vectors to store SparseBitVectorElement's does
      36             : /// not work out very well because it causes insertion in the middle to take
      37             : /// enormous amounts of time with a large amount of bits.  Other structures that
      38             : /// have better worst cases for insertion in the middle (various balanced trees,
      39             : /// etc) do not perform as well in practice as a linked list with this iterator
      40             : /// kept up to date.  They are also significantly more memory intensive.
      41             : 
      42             : template <unsigned ElementSize = 128> struct SparseBitVectorElement {
      43             : public:
      44             :   using BitWord = unsigned long;
      45             :   using size_type = unsigned;
      46             :   enum {
      47             :     BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
      48             :     BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
      49             :     BITS_PER_ELEMENT = ElementSize
      50             :   };
      51             : 
      52             : private:
      53             :   // Index of Element in terms of where first bit starts.
      54             :   unsigned ElementIndex;
      55             :   BitWord Bits[BITWORDS_PER_ELEMENT];
      56             : 
      57             :   SparseBitVectorElement() {
      58             :     ElementIndex = ~0U;
      59             :     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
      60             :   }
      61             : 
      62             : public:
      63      139227 :   explicit SparseBitVectorElement(unsigned Idx) {
      64      139227 :     ElementIndex = Idx;
      65      139227 :     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
      66             :   }
      67             : 
      68             :   // Comparison.
      69             :   bool operator==(const SparseBitVectorElement &RHS) const {
      70           1 :     if (ElementIndex != RHS.ElementIndex)
      71             :       return false;
      72           5 :     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
      73           2 :       if (Bits[i] != RHS.Bits[i])
      74             :         return false;
      75             :     return true;
      76             :   }
      77             : 
      78             :   bool operator!=(const SparseBitVectorElement &RHS) const {
      79           1 :     return !(*this == RHS);
      80             :   }
      81             : 
      82             :   // Return the bits that make up word Idx in our element.
      83             :   BitWord word(unsigned Idx) const {
      84             :     assert(Idx < BITWORDS_PER_ELEMENT);
      85      426051 :     return Bits[Idx];
      86             :   }
      87             : 
      88             :   unsigned index() const {
      89             :     return ElementIndex;
      90             :   }
      91             : 
      92             :   bool empty() const {
      93       38216 :     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
      94       19393 :       if (Bits[i])
      95             :         return false;
      96             :     return true;
      97             :   }
      98             : 
      99             :   void set(unsigned Idx) {
     100     1090556 :     Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
     101             :   }
     102             : 
     103             :   bool test_and_set(unsigned Idx) {
     104             :     bool old = test(Idx);
     105             :     if (!old) {
     106             :       set(Idx);
     107             :       return true;
     108             :     }
     109             :     return false;
     110             :   }
     111             : 
     112             :   void reset(unsigned Idx) {
     113       12604 :     Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
     114             :   }
     115             : 
     116             :   bool test(unsigned Idx) const {
     117     1968039 :     return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
     118             :   }
     119             : 
     120             :   size_type count() const {
     121             :     unsigned NumBits = 0;
     122      323045 :     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
     123      258436 :       NumBits += countPopulation(Bits[i]);
     124             :     return NumBits;
     125             :   }
     126             : 
     127             :   /// find_first - Returns the index of the first set bit.
     128             :   int find_first() const {
     129      567755 :     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
     130      485864 :       if (Bits[i] != 0)
     131      807946 :         return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
     132           0 :     llvm_unreachable("Illegal empty element");
     133             :   }
     134             : 
     135             :   /// find_last - Returns the index of the last set bit.
     136             :   int find_last() const {
     137         382 :     for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; ++I) {
     138         255 :       unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
     139         255 :       if (Bits[Idx] != 0)
     140         256 :         return Idx * BITWORD_SIZE + BITWORD_SIZE -
     141         384 :                countLeadingZeros(Bits[Idx]) - 1;
     142             :     }
     143           0 :     llvm_unreachable("Illegal empty element");
     144             :   }
     145             : 
     146             :   /// find_next - Returns the index of the next set bit starting from the
     147             :   /// "Curr" bit. Returns -1 if the next set bit is not found.
     148      402452 :   int find_next(unsigned Curr) const {
     149      402452 :     if (Curr >= BITS_PER_ELEMENT)
     150             :       return -1;
     151             : 
     152      402452 :     unsigned WordPos = Curr / BITWORD_SIZE;
     153      402452 :     unsigned BitPos = Curr % BITWORD_SIZE;
     154      402452 :     BitWord Copy = Bits[WordPos];
     155             :     assert(WordPos <= BITWORDS_PER_ELEMENT
     156             :            && "Word Position outside of element");
     157             : 
     158             :     // Mask off previous bits.
     159      402452 :     Copy &= ~0UL << BitPos;
     160             : 
     161      402452 :     if (Copy != 0)
     162        5388 :       return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
     163             : 
     164             :     // Check subsequent words.
     165      683674 :     for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
     166      306336 :       if (Bits[i] != 0)
     167       44840 :         return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
     168             :     return -1;
     169             :   }
     170             : 
     171             :   // Union this element with RHS and return true if this one changed.
     172             :   bool unionWith(const SparseBitVectorElement &RHS) {
     173             :     bool changed = false;
     174     1569910 :     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
     175      627964 :       BitWord old = changed ? 0 : Bits[i];
     176             : 
     177      627964 :       Bits[i] |= RHS.Bits[i];
     178      627964 :       if (!changed && old != Bits[i])
     179       69355 :         changed = true;
     180             :     }
     181             :     return changed;
     182             :   }
     183             : 
     184             :   // Return true if we have any bits in common with RHS
     185             :   bool intersects(const SparseBitVectorElement &RHS) const {
     186           0 :     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
     187           0 :       if (RHS.Bits[i] & Bits[i])
     188             :         return true;
     189             :     }
     190             :     return false;
     191             :   }
     192             : 
     193             :   // Intersect this Element with RHS and return true if this one changed.
     194             :   // BecameZero is set to true if this element became all-zero bits.
     195             :   bool intersectWith(const SparseBitVectorElement &RHS,
     196             :                      bool &BecameZero) {
     197             :     bool changed = false;
     198             :     bool allzero = true;
     199             : 
     200             :     BecameZero = false;
     201       34555 :     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
     202       13822 :       BitWord old = changed ? 0 : Bits[i];
     203             : 
     204       13822 :       Bits[i] &= RHS.Bits[i];
     205       13822 :       if (Bits[i] != 0)
     206        7351 :         allzero = false;
     207             : 
     208       13822 :       if (!changed && old != Bits[i])
     209        2439 :         changed = true;
     210             :     }
     211        6911 :     BecameZero = allzero;
     212             :     return changed;
     213             :   }
     214             : 
     215             :   // Intersect this Element with the complement of RHS and return true if this
     216             :   // one changed.  BecameZero is set to true if this element became all-zero
     217             :   // bits.
     218             :   bool intersectWithComplement(const SparseBitVectorElement &RHS,
     219             :                                bool &BecameZero) {
     220             :     bool changed = false;
     221             :     bool allzero = true;
     222             : 
     223             :     BecameZero = false;
     224       69650 :     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
     225       27860 :       BitWord old = changed ? 0 : Bits[i];
     226             : 
     227       27860 :       Bits[i] &= ~RHS.Bits[i];
     228       27860 :       if (Bits[i] != 0)
     229        6146 :         allzero = false;
     230             : 
     231       27860 :       if (!changed && old != Bits[i])
     232       13929 :         changed = true;
     233             :     }
     234       13930 :     BecameZero = allzero;
     235             :     return changed;
     236             :   }
     237             : 
     238             :   // Three argument version of intersectWithComplement that intersects
     239             :   // RHS1 & ~RHS2 into this element
     240             :   void intersectWithComplement(const SparseBitVectorElement &RHS1,
     241             :                                const SparseBitVectorElement &RHS2,
     242             :                                bool &BecameZero) {
     243           2 :     bool allzero = true;
     244             : 
     245           2 :     BecameZero = false;
     246           6 :     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
     247           4 :       Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
     248           4 :       if (Bits[i] != 0)
     249           1 :         allzero = false;
     250             :     }
     251           2 :     BecameZero = allzero;
     252             :   }
     253             : };
     254             : 
     255             : template <unsigned ElementSize = 128>
     256             : class SparseBitVector {
     257             :   using ElementList = std::list<SparseBitVectorElement<ElementSize>>;
     258             :   using ElementListIter = typename ElementList::iterator;
     259             :   using ElementListConstIter = typename ElementList::const_iterator;
     260             :   enum {
     261             :     BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
     262             :   };
     263             : 
     264             :   // Pointer to our current Element.
     265             :   ElementListIter CurrElementIter;
     266             :   ElementList Elements;
     267             : 
     268             :   // This is like std::lower_bound, except we do linear searching from the
     269             :   // current position.
     270     2972737 :   ElementListIter FindLowerBound(unsigned ElementIndex) {
     271             : 
     272     5945474 :     if (Elements.empty()) {
     273           0 :       CurrElementIter = Elements.begin();
     274           0 :       return Elements.begin();
     275             :     }
     276             : 
     277             :     // Make sure our current iterator is valid.
     278     8918211 :     if (CurrElementIter == Elements.end())
     279       13571 :       --CurrElementIter;
     280             : 
     281             :     // Search from our current iterator, either backwards or forwards,
     282             :     // depending on what element we are looking for.
     283     2972737 :     ElementListIter ElementIter = CurrElementIter;
     284     5945474 :     if (CurrElementIter->index() == ElementIndex) {
     285     2789588 :       return ElementIter;
     286      366298 :     } else if (CurrElementIter->index() > ElementIndex) {
     287      459504 :       while (ElementIter != Elements.begin()
     288      405768 :              && ElementIter->index() > ElementIndex)
     289             :         --ElementIter;
     290             :     } else {
     291      771707 :       while (ElementIter != Elements.end() &&
     292      242203 :              ElementIter->index() < ElementIndex)
     293             :         ++ElementIter;
     294             :     }
     295      183149 :     CurrElementIter = ElementIter;
     296      183149 :     return ElementIter;
     297             :   }
     298             : 
     299             :   // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
     300             :   // than it would be, in order to be efficient.
     301             :   class SparseBitVectorIterator {
     302             :   private:
     303             :     bool AtEnd;
     304             : 
     305             :     const SparseBitVector<ElementSize> *BitVector = nullptr;
     306             : 
     307             :     // Current element inside of bitmap.
     308             :     ElementListConstIter Iter;
     309             : 
     310             :     // Current bit number inside of our bitmap.
     311             :     unsigned BitNumber;
     312             : 
     313             :     // Current word number inside of our element.
     314             :     unsigned WordNumber;
     315             : 
     316             :     // Current bits from the element.
     317             :     typename SparseBitVectorElement<ElementSize>::BitWord Bits;
     318             : 
     319             :     // Move our iterator to the first non-zero bit in the bitmap.
     320    11102517 :     void AdvanceToFirstNonZero() {
     321    11102517 :       if (AtEnd)
     322             :         return;
     323    11126054 :       if (BitVector->Elements.empty()) {
     324     5185476 :         AtEnd = true;
     325     5185476 :         return;
     326             :       }
     327      755102 :       Iter = BitVector->Elements.begin();
     328      755102 :       BitNumber = Iter->index() * ElementSize;
     329     1132653 :       unsigned BitPos = Iter->find_first();
     330      377551 :       BitNumber += BitPos;
     331      377551 :       WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
     332     1132653 :       Bits = Iter->word(WordNumber);
     333      377551 :       Bits >>= BitPos % BITWORD_SIZE;
     334             :     }
     335             : 
     336             :     // Move our iterator to the next non-zero bit.
     337     1180265 :     void AdvanceToNextNonZero() {
     338     1180265 :       if (AtEnd)
     339             :         return;
     340             : 
     341     3829857 :       while (Bits && !(Bits & 1)) {
     342     1324796 :         Bits >>= 1;
     343     1324796 :         BitNumber += 1;
     344             :       }
     345             : 
     346             :       // See if we ran out of Bits in this word.
     347     1180265 :       if (!Bits) {
     348      804904 :         int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
     349             :         // If we ran out of set bits in this element, move to next element.
     350      402452 :         if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
     351      760478 :           ++Iter;
     352      380239 :           WordNumber = 0;
     353             : 
     354             :           // We may run out of elements in the bitmap.
     355      760478 :           if (Iter == BitVector->Elements.end()) {
     356      353952 :             AtEnd = true;
     357      353952 :             return;
     358             :           }
     359             :           // Set up for next non-zero word in bitmap.
     360       52574 :           BitNumber = Iter->index() * ElementSize;
     361       78861 :           NextSetBitNumber = Iter->find_first();
     362       26287 :           BitNumber += NextSetBitNumber;
     363       26287 :           WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
     364       78861 :           Bits = Iter->word(WordNumber);
     365       26287 :           Bits >>= NextSetBitNumber % BITWORD_SIZE;
     366             :         } else {
     367       22213 :           WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
     368       66639 :           Bits = Iter->word(WordNumber);
     369       22213 :           Bits >>= NextSetBitNumber % BITWORD_SIZE;
     370       44426 :           BitNumber = Iter->index() * ElementSize;
     371       22213 :           BitNumber += NextSetBitNumber;
     372             :         }
     373             :       }
     374             :     }
     375             : 
     376             :   public:
     377        9096 :     SparseBitVectorIterator() = default;
     378             : 
     379    11102517 :     SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
     380    22205034 :                             bool end = false):BitVector(RHS) {
     381    22205034 :       Iter = BitVector->Elements.begin();
     382    11102517 :       BitNumber = 0;
     383    11102517 :       Bits = 0;
     384    11102517 :       WordNumber = ~0;
     385    11102517 :       AtEnd = end;
     386    11102517 :       AdvanceToFirstNonZero();
     387             :     }
     388             : 
     389             :     // Preincrement.
     390             :     inline SparseBitVectorIterator& operator++() {
     391     1180265 :       ++BitNumber;
     392     1180265 :       Bits >>= 1;
     393     1180265 :       AdvanceToNextNonZero();
     394             :       return *this;
     395             :     }
     396             : 
     397             :     // Postincrement.
     398             :     inline SparseBitVectorIterator operator++(int) {
     399             :       SparseBitVectorIterator tmp = *this;
     400             :       ++*this;
     401             :       return tmp;
     402             :     }
     403             : 
     404             :     // Return the current set bit number.
     405             :     unsigned operator*() const {
     406             :       return BitNumber;
     407             :     }
     408             : 
     409             :     bool operator==(const SparseBitVectorIterator &RHS) const {
     410             :       // If they are both at the end, ignore the rest of the fields.
     411     6848382 :       if (AtEnd && RHS.AtEnd)
     412             :         return true;
     413             :       // Otherwise they are the same if they have the same bit number and
     414             :       // bitmap.
     415     1306680 :       return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
     416             :     }
     417             : 
     418             :     bool operator!=(const SparseBitVectorIterator &RHS) const {
     419     6665365 :       return !(*this == RHS);
     420             :     }
     421             :   };
     422             : 
     423             : public:
     424             :   using iterator = SparseBitVectorIterator;
     425             : 
     426     4990452 :   SparseBitVector() {
     427     3326968 :     CurrElementIter = Elements.begin();
     428             :   }
     429             : 
     430             :   // SparseBitVector copy ctor.
     431     8776917 :   SparseBitVector(const SparseBitVector &RHS) {
     432     5851278 :     ElementListConstIter ElementIter = RHS.Elements.begin();
     433     5993508 :     while (ElementIter != RHS.Elements.end()) {
     434      213345 :       Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
     435             :       ++ElementIter;
     436             :     }
     437             : 
     438     5851278 :     CurrElementIter = Elements.begin ();
     439     2925639 :   }
     440             : 
     441     9021891 :   ~SparseBitVector() = default;
     442             : 
     443             :   // Clear.
     444             :   void clear() {
     445      573578 :     Elements.clear();
     446             :   }
     447             : 
     448             :   // Assignment
     449       51981 :   SparseBitVector& operator=(const SparseBitVector& RHS) {
     450       51981 :     if (this == &RHS)
     451             :       return *this;
     452             : 
     453      103960 :     Elements.clear();
     454             : 
     455      103960 :     ElementListConstIter ElementIter = RHS.Elements.begin();
     456      220394 :     while (ElementIter != RHS.Elements.end()) {
     457      174651 :       Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
     458             :       ++ElementIter;
     459             :     }
     460             : 
     461      103960 :     CurrElementIter = Elements.begin ();
     462             : 
     463       51980 :     return *this;
     464             :   }
     465             : 
     466             :   // Test, Reset, and Set a bit in the bitmap.
     467     2514443 :   bool test(unsigned Idx) {
     468     5028886 :     if (Elements.empty())
     469             :       return false;
     470             : 
     471     1991353 :     unsigned ElementIndex = Idx / ElementSize;
     472     1991353 :     ElementListIter ElementIter = FindLowerBound(ElementIndex);
     473             : 
     474             :     // If we can't find an element that is supposed to contain this bit, there
     475             :     // is nothing more to do.
     476     5959966 :     if (ElementIter == Elements.end() ||
     477     1977260 :         ElementIter->index() != ElementIndex)
     478             :       return false;
     479     3936078 :     return ElementIter->test(Idx % ElementSize);
     480             :   }
     481             : 
     482       66497 :   void reset(unsigned Idx) {
     483      132994 :     if (Elements.empty())
     484             :       return;
     485             : 
     486       12604 :     unsigned ElementIndex = Idx / ElementSize;
     487       12604 :     ElementListIter ElementIter = FindLowerBound(ElementIndex);
     488             : 
     489             :     // If we can't find an element that is supposed to contain this bit, there
     490             :     // is nothing more to do.
     491       37812 :     if (ElementIter == Elements.end() ||
     492       12604 :         ElementIter->index() != ElementIndex)
     493             :       return;
     494       25208 :     ElementIter->reset(Idx % ElementSize);
     495             : 
     496             :     // When the element is zeroed out, delete it.
     497       25208 :     if (ElementIter->empty()) {
     498       12034 :       ++CurrElementIter;
     499       12034 :       Elements.erase(ElementIter);
     500             :     }
     501             :   }
     502             : 
     503     1090556 :   void set(unsigned Idx) {
     504     1090556 :     unsigned ElementIndex = Idx / ElementSize;
     505     1090556 :     ElementListIter ElementIter;
     506     2181112 :     if (Elements.empty()) {
     507      365328 :       ElementIter = Elements.emplace(Elements.end(), ElementIndex);
     508             :     } else {
     509      968780 :       ElementIter = FindLowerBound(ElementIndex);
     510             : 
     511     2897884 :       if (ElementIter == Elements.end() ||
     512      960324 :           ElementIter->index() != ElementIndex) {
     513             :         // We may have hit the beginning of our SparseBitVector, in which case,
     514             :         // we may need to insert right after this element, which requires moving
     515             :         // the current iterator forward one, because insert does insert before.
     516       43891 :         if (ElementIter != Elements.end() &&
     517        8993 :             ElementIter->index() < ElementIndex)
     518             :           ++ElementIter;
     519       34898 :         ElementIter = Elements.emplace(ElementIter, ElementIndex);
     520             :       }
     521             :     }
     522     1090556 :     CurrElementIter = ElementIter;
     523             : 
     524     2181112 :     ElementIter->set(Idx % ElementSize);
     525     1090556 :   }
     526             : 
     527           2 :   bool test_and_set(unsigned Idx) {
     528           2 :     bool old = test(Idx);
     529           2 :     if (!old) {
     530           1 :       set(Idx);
     531           1 :       return true;
     532             :     }
     533             :     return false;
     534             :   }
     535             : 
     536             :   bool operator!=(const SparseBitVector &RHS) const {
     537             :     return !(*this == RHS);
     538             :   }
     539             : 
     540           2 :   bool operator==(const SparseBitVector &RHS) const {
     541           4 :     ElementListConstIter Iter1 = Elements.begin();
     542           4 :     ElementListConstIter Iter2 = RHS.Elements.begin();
     543             : 
     544           8 :     for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
     545             :          ++Iter1, ++Iter2) {
     546           3 :       if (*Iter1 != *Iter2)
     547             :         return false;
     548             :     }
     549           8 :     return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
     550             :   }
     551             : 
     552             :   // Union our bitmap with the RHS and return true if we changed.
     553      350360 :   bool operator|=(const SparseBitVector &RHS) {
     554      350360 :     if (this == &RHS)
     555             :       return false;
     556             : 
     557      350359 :     bool changed = false;
     558      700718 :     ElementListIter Iter1 = Elements.begin();
     559      700718 :     ElementListConstIter Iter2 = RHS.Elements.begin();
     560             : 
     561             :     // If RHS is empty, we are done
     562      700718 :     if (RHS.Elements.empty())
     563             :       return false;
     564             : 
     565     1443024 :     while (Iter2 != RHS.Elements.end()) {
     566     1407556 :       if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
     567      120126 :         Elements.insert(Iter1, *Iter2);
     568       40042 :         ++Iter2;
     569       40042 :         changed = true;
     570      662222 :       } else if (Iter1->index() == Iter2->index()) {
     571      313982 :         changed |= Iter1->unionWith(*Iter2);
     572      313982 :         ++Iter1;
     573             :         ++Iter2;
     574             :       } else {
     575             :         ++Iter1;
     576             :       }
     577             :     }
     578      700718 :     CurrElementIter = Elements.begin();
     579      350359 :     return changed;
     580             :   }
     581             : 
     582             :   // Intersect our bitmap with the RHS and return true if ours changed.
     583        6208 :   bool operator&=(const SparseBitVector &RHS) {
     584        6208 :     if (this == &RHS)
     585             :       return false;
     586             : 
     587        6207 :     bool changed = false;
     588       12414 :     ElementListIter Iter1 = Elements.begin();
     589       12414 :     ElementListConstIter Iter2 = RHS.Elements.begin();
     590             : 
     591             :     // Check if both bitmaps are empty.
     592       12459 :     if (Elements.empty() && RHS.Elements.empty())
     593             :       return false;
     594             : 
     595             :     // Loop through, intersecting as we go, erasing elements when necessary.
     596       26832 :     while (Iter2 != RHS.Elements.end()) {
     597       14712 :       if (Iter1 == Elements.end()) {
     598         294 :         CurrElementIter = Elements.begin();
     599         147 :         return changed;
     600             :       }
     601             : 
     602       14418 :       if (Iter1->index() > Iter2->index()) {
     603             :         ++Iter2;
     604       14042 :       } else if (Iter1->index() == Iter2->index()) {
     605             :         bool BecameZero;
     606        6911 :         changed |= Iter1->intersectWith(*Iter2, BecameZero);
     607        6911 :         if (BecameZero) {
     608         175 :           ElementListIter IterTmp = Iter1;
     609         175 :           ++Iter1;
     610         350 :           Elements.erase(IterTmp);
     611             :         } else {
     612             :           ++Iter1;
     613             :         }
     614        6911 :         ++Iter2;
     615             :       } else {
     616         110 :         ElementListIter IterTmp = Iter1;
     617         110 :         ++Iter1;
     618         220 :         Elements.erase(IterTmp);
     619         110 :         changed = true;
     620             :       }
     621             :     }
     622       12120 :     if (Iter1 != Elements.end()) {
     623         332 :       Elements.erase(Iter1, Elements.end());
     624          83 :       changed = true;
     625             :     }
     626       12120 :     CurrElementIter = Elements.begin();
     627        6060 :     return changed;
     628             :   }
     629             : 
     630             :   // Intersect our bitmap with the complement of the RHS and return true
     631             :   // if ours changed.
     632     1391164 :   bool intersectWithComplement(const SparseBitVector &RHS) {
     633     1391164 :     if (this == &RHS) {
     634           3 :       if (!empty()) {
     635           2 :         clear();
     636           2 :         return true;
     637             :       }
     638             :       return false;
     639             :     }
     640             : 
     641     1391161 :     bool changed = false;
     642     2782322 :     ElementListIter Iter1 = Elements.begin();
     643     2782322 :     ElementListConstIter Iter2 = RHS.Elements.begin();
     644             : 
     645             :     // If either our bitmap or RHS is empty, we are done
     646     2899538 :     if (Elements.empty() || RHS.Elements.empty())
     647             :       return false;
     648             : 
     649             :     // Loop through, intersecting as we go, erasing elements when necessary.
     650       54620 :     while (Iter2 != RHS.Elements.end()) {
     651       28632 :       if (Iter1 == Elements.end()) {
     652           0 :         CurrElementIter = Elements.begin();
     653           0 :         return changed;
     654             :       }
     655             : 
     656       28632 :       if (Iter1->index() > Iter2->index()) {
     657             :         ++Iter2;
     658       28630 :       } else if (Iter1->index() == Iter2->index()) {
     659             :         bool BecameZero;
     660       13930 :         changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
     661       13930 :         if (BecameZero) {
     662        8429 :           ElementListIter IterTmp = Iter1;
     663        8429 :           ++Iter1;
     664       16858 :           Elements.erase(IterTmp);
     665             :         } else {
     666             :           ++Iter1;
     667             :         }
     668       13930 :         ++Iter2;
     669             :       } else {
     670             :         ++Iter1;
     671             :       }
     672             :     }
     673       25988 :     CurrElementIter = Elements.begin();
     674       12994 :     return changed;
     675             :   }
     676             : 
     677             :   bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
     678             :     return intersectWithComplement(*RHS);
     679             :   }
     680             : 
     681             :   //  Three argument version of intersectWithComplement.
     682             :   //  Result of RHS1 & ~RHS2 is stored into this bitmap.
     683           5 :   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
     684             :                                const SparseBitVector<ElementSize> &RHS2)
     685             :   {
     686           5 :     if (this == &RHS1) {
     687           2 :       intersectWithComplement(RHS2);
     688           2 :       return;
     689           3 :     } else if (this == &RHS2) {
     690           2 :       SparseBitVector RHS2Copy(RHS2);
     691           1 :       intersectWithComplement(RHS1, RHS2Copy);
     692             :       return;
     693             :     }
     694             : 
     695           4 :     Elements.clear();
     696           4 :     CurrElementIter = Elements.begin();
     697           4 :     ElementListConstIter Iter1 = RHS1.Elements.begin();
     698           4 :     ElementListConstIter Iter2 = RHS2.Elements.begin();
     699             : 
     700             :     // If RHS1 is empty, we are done
     701             :     // If RHS2 is empty, we still have to copy RHS1
     702           4 :     if (RHS1.Elements.empty())
     703             :       return;
     704             : 
     705             :     // Loop through, intersecting as we go, erasing elements when necessary.
     706           8 :     while (Iter2 != RHS2.Elements.end()) {
     707           4 :       if (Iter1 == RHS1.Elements.end())
     708             :         return;
     709             : 
     710           4 :       if (Iter1->index() > Iter2->index()) {
     711             :         ++Iter2;
     712           4 :       } else if (Iter1->index() == Iter2->index()) {
     713           2 :         bool BecameZero = false;
     714           4 :         Elements.emplace_back(Iter1->index());
     715          10 :         Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
     716           2 :         if (BecameZero)
     717           1 :           Elements.pop_back();
     718           2 :         ++Iter1;
     719           2 :         ++Iter2;
     720             :       } else {
     721           0 :         Elements.push_back(*Iter1++);
     722             :       }
     723             :     }
     724             : 
     725             :     // copy the remaining elements
     726           2 :     std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));
     727             :   }
     728             : 
     729             :   void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
     730             :                                const SparseBitVector<ElementSize> *RHS2) {
     731             :     intersectWithComplement(*RHS1, *RHS2);
     732             :   }
     733             : 
     734             :   bool intersects(const SparseBitVector<ElementSize> *RHS) const {
     735             :     return intersects(*RHS);
     736             :   }
     737             : 
     738             :   // Return true if we share any bits in common with RHS
     739          69 :   bool intersects(const SparseBitVector<ElementSize> &RHS) const {
     740         138 :     ElementListConstIter Iter1 = Elements.begin();
     741         138 :     ElementListConstIter Iter2 = RHS.Elements.begin();
     742             : 
     743             :     // Check if both bitmaps are empty.
     744         138 :     if (Elements.empty() && RHS.Elements.empty())
     745             :       return false;
     746             : 
     747             :     // Loop through, intersecting stopping when we hit bits in common.
     748         138 :     while (Iter2 != RHS.Elements.end()) {
     749           0 :       if (Iter1 == Elements.end())
     750             :         return false;
     751             : 
     752           0 :       if (Iter1->index() > Iter2->index()) {
     753             :         ++Iter2;
     754           0 :       } else if (Iter1->index() == Iter2->index()) {
     755           0 :         if (Iter1->intersects(*Iter2))
     756             :           return true;
     757           0 :         ++Iter1;
     758             :         ++Iter2;
     759             :       } else {
     760             :         ++Iter1;
     761             :       }
     762             :     }
     763             :     return false;
     764             :   }
     765             : 
     766             :   // Return true iff all bits set in this SparseBitVector are
     767             :   // also set in RHS.
     768             :   bool contains(const SparseBitVector<ElementSize> &RHS) const {
     769             :     SparseBitVector<ElementSize> Result(*this);
     770             :     Result &= RHS;
     771             :     return (Result == RHS);
     772             :   }
     773             : 
     774             :   // Return the first set bit in the bitmap.  Return -1 if no bits are set.
     775             :   int find_first() const {
     776         278 :     if (Elements.empty())
     777             :       return -1;
     778         405 :     const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
     779         270 :     return (First.index() * ElementSize) + First.find_first();
     780             :   }
     781             : 
     782             :   // Return the last set bit in the bitmap.  Return -1 if no bits are set.
     783         250 :   int find_last() const {
     784         500 :     if (Elements.empty())
     785             :       return -1;
     786         384 :     const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
     787         256 :     return (Last.index() * ElementSize) + Last.find_last();
     788             :   }
     789             : 
     790             :   // Return true if the SparseBitVector is empty
     791             :   bool empty() const {
     792     3883174 :     return Elements.empty();
     793             :   }
     794             : 
     795             :   unsigned count() const {
     796       59546 :     unsigned BitCount = 0;
     797      119092 :     for (ElementListConstIter Iter = Elements.begin();
     798      248310 :          Iter != Elements.end();
     799             :          ++Iter)
     800       64609 :       BitCount += Iter->count();
     801             : 
     802             :     return BitCount;
     803             :   }
     804             : 
     805             :   iterator begin() const {
     806     5563027 :     return iterator(this);
     807             :   }
     808             : 
     809             :   iterator end() const {
     810     5539490 :     return iterator(this, true);
     811             :   }
     812             : };
     813             : 
     814             : // Convenience functions to allow Or and And without dereferencing in the user
     815             : // code.
     816             : 
     817             : template <unsigned ElementSize>
     818             : inline bool operator |=(SparseBitVector<ElementSize> &LHS,
     819             :                         const SparseBitVector<ElementSize> *RHS) {
     820             :   return LHS |= *RHS;
     821             : }
     822             : 
     823             : template <unsigned ElementSize>
     824             : inline bool operator |=(SparseBitVector<ElementSize> *LHS,
     825             :                         const SparseBitVector<ElementSize> &RHS) {
     826             :   return LHS->operator|=(RHS);
     827             : }
     828             : 
     829             : template <unsigned ElementSize>
     830             : inline bool operator &=(SparseBitVector<ElementSize> *LHS,
     831             :                         const SparseBitVector<ElementSize> &RHS) {
     832             :   return LHS->operator&=(RHS);
     833             : }
     834             : 
     835             : template <unsigned ElementSize>
     836             : inline bool operator &=(SparseBitVector<ElementSize> &LHS,
     837             :                         const SparseBitVector<ElementSize> *RHS) {
     838             :   return LHS &= *RHS;
     839             : }
     840             : 
     841             : // Convenience functions for infix union, intersection, difference operators.
     842             : 
     843             : template <unsigned ElementSize>
     844             : inline SparseBitVector<ElementSize>
     845             : operator|(const SparseBitVector<ElementSize> &LHS,
     846             :           const SparseBitVector<ElementSize> &RHS) {
     847             :   SparseBitVector<ElementSize> Result(LHS);
     848             :   Result |= RHS;
     849             :   return Result;
     850             : }
     851             : 
     852             : template <unsigned ElementSize>
     853             : inline SparseBitVector<ElementSize>
     854             : operator&(const SparseBitVector<ElementSize> &LHS,
     855             :           const SparseBitVector<ElementSize> &RHS) {
     856             :   SparseBitVector<ElementSize> Result(LHS);
     857             :   Result &= RHS;
     858             :   return Result;
     859             : }
     860             : 
     861             : template <unsigned ElementSize>
     862             : inline SparseBitVector<ElementSize>
     863             : operator-(const SparseBitVector<ElementSize> &LHS,
     864             :           const SparseBitVector<ElementSize> &RHS) {
     865             :   SparseBitVector<ElementSize> Result;
     866             :   Result.intersectWithComplement(LHS, RHS);
     867             :   return Result;
     868             : }
     869             : 
     870             : // Dump a SparseBitVector to a stream
     871             : template <unsigned ElementSize>
     872             : void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
     873             :   out << "[";
     874             : 
     875             :   typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
     876             :     be = LHS.end();
     877             :   if (bi != be) {
     878             :     out << *bi;
     879             :     for (++bi; bi != be; ++bi) {
     880             :       out << " " << *bi;
     881             :     }
     882             :   }
     883             :   out << "]\n";
     884             : }
     885             : 
     886             : } // end namespace llvm
     887             : 
     888             : #endif // LLVM_ADT_SPARSEBITVECTOR_H

Generated by: LCOV version 1.13