Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. //===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector --*- C++ -*-===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. ///
  9. /// \file
  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.   explicit SparseBitVectorElement(unsigned Idx) {
  64.     ElementIndex = Idx;
  65.     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
  66.   }
  67.  
  68.   // Comparison.
  69.   bool operator==(const SparseBitVectorElement &RHS) const {
  70.     if (ElementIndex != RHS.ElementIndex)
  71.       return false;
  72.     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
  73.       if (Bits[i] != RHS.Bits[i])
  74.         return false;
  75.     return true;
  76.   }
  77.  
  78.   bool operator!=(const SparseBitVectorElement &RHS) const {
  79.     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.     return Bits[Idx];
  86.   }
  87.  
  88.   unsigned index() const {
  89.     return ElementIndex;
  90.   }
  91.  
  92.   bool empty() const {
  93.     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
  94.       if (Bits[i])
  95.         return false;
  96.     return true;
  97.   }
  98.  
  99.   void set(unsigned Idx) {
  100.     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.     Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
  114.   }
  115.  
  116.   bool test(unsigned Idx) const {
  117.     return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
  118.   }
  119.  
  120.   size_type count() const {
  121.     unsigned NumBits = 0;
  122.     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
  123.       NumBits += llvm::popcount(Bits[i]);
  124.     return NumBits;
  125.   }
  126.  
  127.   /// find_first - Returns the index of the first set bit.
  128.   int find_first() const {
  129.     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
  130.       if (Bits[i] != 0)
  131.         return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
  132.     llvm_unreachable("Illegal empty element");
  133.   }
  134.  
  135.   /// find_last - Returns the index of the last set bit.
  136.   int find_last() const {
  137.     for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; ++I) {
  138.       unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
  139.       if (Bits[Idx] != 0)
  140.         return Idx * BITWORD_SIZE + BITWORD_SIZE -
  141.                countLeadingZeros(Bits[Idx]) - 1;
  142.     }
  143.     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.   int find_next(unsigned Curr) const {
  149.     if (Curr >= BITS_PER_ELEMENT)
  150.       return -1;
  151.  
  152.     unsigned WordPos = Curr / BITWORD_SIZE;
  153.     unsigned BitPos = Curr % BITWORD_SIZE;
  154.     BitWord Copy = Bits[WordPos];
  155.     assert(WordPos <= BITWORDS_PER_ELEMENT
  156.            && "Word Position outside of element");
  157.  
  158.     // Mask off previous bits.
  159.     Copy &= ~0UL << BitPos;
  160.  
  161.     if (Copy != 0)
  162.       return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
  163.  
  164.     // Check subsequent words.
  165.     for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
  166.       if (Bits[i] != 0)
  167.         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.     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
  175.       BitWord old = changed ? 0 : Bits[i];
  176.  
  177.       Bits[i] |= RHS.Bits[i];
  178.       if (!changed && old != Bits[i])
  179.         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.     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
  187.       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.     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
  202.       BitWord old = changed ? 0 : Bits[i];
  203.  
  204.       Bits[i] &= RHS.Bits[i];
  205.       if (Bits[i] != 0)
  206.         allzero = false;
  207.  
  208.       if (!changed && old != Bits[i])
  209.         changed = true;
  210.     }
  211.     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.     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
  225.       BitWord old = changed ? 0 : Bits[i];
  226.  
  227.       Bits[i] &= ~RHS.Bits[i];
  228.       if (Bits[i] != 0)
  229.         allzero = false;
  230.  
  231.       if (!changed && old != Bits[i])
  232.         changed = true;
  233.     }
  234.     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.     bool allzero = true;
  244.  
  245.     BecameZero = false;
  246.     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
  247.       Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
  248.       if (Bits[i] != 0)
  249.         allzero = false;
  250.     }
  251.     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.   ElementList Elements;
  265.   // Pointer to our current Element. This has no visible effect on the external
  266.   // state of a SparseBitVector, it's just used to improve performance in the
  267.   // common case of testing/modifying bits with similar indices.
  268.   mutable ElementListIter CurrElementIter;
  269.  
  270.   // This is like std::lower_bound, except we do linear searching from the
  271.   // current position.
  272.   ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const {
  273.  
  274.     // We cache a non-const iterator so we're forced to resort to const_cast to
  275.     // get the begin/end in the case where 'this' is const. To avoid duplication
  276.     // of code with the only difference being whether the const cast is present
  277.     // 'this' is always const in this particular function and we sort out the
  278.     // difference in FindLowerBound and FindLowerBoundConst.
  279.     ElementListIter Begin =
  280.         const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin();
  281.     ElementListIter End =
  282.         const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end();
  283.  
  284.     if (Elements.empty()) {
  285.       CurrElementIter = Begin;
  286.       return CurrElementIter;
  287.     }
  288.  
  289.     // Make sure our current iterator is valid.
  290.     if (CurrElementIter == End)
  291.       --CurrElementIter;
  292.  
  293.     // Search from our current iterator, either backwards or forwards,
  294.     // depending on what element we are looking for.
  295.     ElementListIter ElementIter = CurrElementIter;
  296.     if (CurrElementIter->index() == ElementIndex) {
  297.       return ElementIter;
  298.     } else if (CurrElementIter->index() > ElementIndex) {
  299.       while (ElementIter != Begin
  300.              && ElementIter->index() > ElementIndex)
  301.         --ElementIter;
  302.     } else {
  303.       while (ElementIter != End &&
  304.              ElementIter->index() < ElementIndex)
  305.         ++ElementIter;
  306.     }
  307.     CurrElementIter = ElementIter;
  308.     return ElementIter;
  309.   }
  310.   ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const {
  311.     return FindLowerBoundImpl(ElementIndex);
  312.   }
  313.   ElementListIter FindLowerBound(unsigned ElementIndex) {
  314.     return FindLowerBoundImpl(ElementIndex);
  315.   }
  316.  
  317.   // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
  318.   // than it would be, in order to be efficient.
  319.   class SparseBitVectorIterator {
  320.   private:
  321.     bool AtEnd;
  322.  
  323.     const SparseBitVector<ElementSize> *BitVector = nullptr;
  324.  
  325.     // Current element inside of bitmap.
  326.     ElementListConstIter Iter;
  327.  
  328.     // Current bit number inside of our bitmap.
  329.     unsigned BitNumber;
  330.  
  331.     // Current word number inside of our element.
  332.     unsigned WordNumber;
  333.  
  334.     // Current bits from the element.
  335.     typename SparseBitVectorElement<ElementSize>::BitWord Bits;
  336.  
  337.     // Move our iterator to the first non-zero bit in the bitmap.
  338.     void AdvanceToFirstNonZero() {
  339.       if (AtEnd)
  340.         return;
  341.       if (BitVector->Elements.empty()) {
  342.         AtEnd = true;
  343.         return;
  344.       }
  345.       Iter = BitVector->Elements.begin();
  346.       BitNumber = Iter->index() * ElementSize;
  347.       unsigned BitPos = Iter->find_first();
  348.       BitNumber += BitPos;
  349.       WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
  350.       Bits = Iter->word(WordNumber);
  351.       Bits >>= BitPos % BITWORD_SIZE;
  352.     }
  353.  
  354.     // Move our iterator to the next non-zero bit.
  355.     void AdvanceToNextNonZero() {
  356.       if (AtEnd)
  357.         return;
  358.  
  359.       while (Bits && !(Bits & 1)) {
  360.         Bits >>= 1;
  361.         BitNumber += 1;
  362.       }
  363.  
  364.       // See if we ran out of Bits in this word.
  365.       if (!Bits) {
  366.         int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
  367.         // If we ran out of set bits in this element, move to next element.
  368.         if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
  369.           ++Iter;
  370.           WordNumber = 0;
  371.  
  372.           // We may run out of elements in the bitmap.
  373.           if (Iter == BitVector->Elements.end()) {
  374.             AtEnd = true;
  375.             return;
  376.           }
  377.           // Set up for next non-zero word in bitmap.
  378.           BitNumber = Iter->index() * ElementSize;
  379.           NextSetBitNumber = Iter->find_first();
  380.           BitNumber += NextSetBitNumber;
  381.           WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
  382.           Bits = Iter->word(WordNumber);
  383.           Bits >>= NextSetBitNumber % BITWORD_SIZE;
  384.         } else {
  385.           WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
  386.           Bits = Iter->word(WordNumber);
  387.           Bits >>= NextSetBitNumber % BITWORD_SIZE;
  388.           BitNumber = Iter->index() * ElementSize;
  389.           BitNumber += NextSetBitNumber;
  390.         }
  391.       }
  392.     }
  393.  
  394.   public:
  395.     SparseBitVectorIterator() = default;
  396.  
  397.     SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
  398.                             bool end = false):BitVector(RHS) {
  399.       Iter = BitVector->Elements.begin();
  400.       BitNumber = 0;
  401.       Bits = 0;
  402.       WordNumber = ~0;
  403.       AtEnd = end;
  404.       AdvanceToFirstNonZero();
  405.     }
  406.  
  407.     // Preincrement.
  408.     inline SparseBitVectorIterator& operator++() {
  409.       ++BitNumber;
  410.       Bits >>= 1;
  411.       AdvanceToNextNonZero();
  412.       return *this;
  413.     }
  414.  
  415.     // Postincrement.
  416.     inline SparseBitVectorIterator operator++(int) {
  417.       SparseBitVectorIterator tmp = *this;
  418.       ++*this;
  419.       return tmp;
  420.     }
  421.  
  422.     // Return the current set bit number.
  423.     unsigned operator*() const {
  424.       return BitNumber;
  425.     }
  426.  
  427.     bool operator==(const SparseBitVectorIterator &RHS) const {
  428.       // If they are both at the end, ignore the rest of the fields.
  429.       if (AtEnd && RHS.AtEnd)
  430.         return true;
  431.       // Otherwise they are the same if they have the same bit number and
  432.       // bitmap.
  433.       return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
  434.     }
  435.  
  436.     bool operator!=(const SparseBitVectorIterator &RHS) const {
  437.       return !(*this == RHS);
  438.     }
  439.   };
  440.  
  441. public:
  442.   using iterator = SparseBitVectorIterator;
  443.  
  444.   SparseBitVector() : Elements(), CurrElementIter(Elements.begin()) {}
  445.  
  446.   SparseBitVector(const SparseBitVector &RHS)
  447.       : Elements(RHS.Elements), CurrElementIter(Elements.begin()) {}
  448.   SparseBitVector(SparseBitVector &&RHS)
  449.       : Elements(std::move(RHS.Elements)), CurrElementIter(Elements.begin()) {}
  450.  
  451.   // Clear.
  452.   void clear() {
  453.     Elements.clear();
  454.   }
  455.  
  456.   // Assignment
  457.   SparseBitVector& operator=(const SparseBitVector& RHS) {
  458.     if (this == &RHS)
  459.       return *this;
  460.  
  461.     Elements = RHS.Elements;
  462.     CurrElementIter = Elements.begin();
  463.     return *this;
  464.   }
  465.   SparseBitVector &operator=(SparseBitVector &&RHS) {
  466.     Elements = std::move(RHS.Elements);
  467.     CurrElementIter = Elements.begin();
  468.     return *this;
  469.   }
  470.  
  471.   // Test, Reset, and Set a bit in the bitmap.
  472.   bool test(unsigned Idx) const {
  473.     if (Elements.empty())
  474.       return false;
  475.  
  476.     unsigned ElementIndex = Idx / ElementSize;
  477.     ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex);
  478.  
  479.     // If we can't find an element that is supposed to contain this bit, there
  480.     // is nothing more to do.
  481.     if (ElementIter == Elements.end() ||
  482.         ElementIter->index() != ElementIndex)
  483.       return false;
  484.     return ElementIter->test(Idx % ElementSize);
  485.   }
  486.  
  487.   void reset(unsigned Idx) {
  488.     if (Elements.empty())
  489.       return;
  490.  
  491.     unsigned ElementIndex = Idx / ElementSize;
  492.     ElementListIter ElementIter = FindLowerBound(ElementIndex);
  493.  
  494.     // If we can't find an element that is supposed to contain this bit, there
  495.     // is nothing more to do.
  496.     if (ElementIter == Elements.end() ||
  497.         ElementIter->index() != ElementIndex)
  498.       return;
  499.     ElementIter->reset(Idx % ElementSize);
  500.  
  501.     // When the element is zeroed out, delete it.
  502.     if (ElementIter->empty()) {
  503.       ++CurrElementIter;
  504.       Elements.erase(ElementIter);
  505.     }
  506.   }
  507.  
  508.   void set(unsigned Idx) {
  509.     unsigned ElementIndex = Idx / ElementSize;
  510.     ElementListIter ElementIter;
  511.     if (Elements.empty()) {
  512.       ElementIter = Elements.emplace(Elements.end(), ElementIndex);
  513.     } else {
  514.       ElementIter = FindLowerBound(ElementIndex);
  515.  
  516.       if (ElementIter == Elements.end() ||
  517.           ElementIter->index() != ElementIndex) {
  518.         // We may have hit the beginning of our SparseBitVector, in which case,
  519.         // we may need to insert right after this element, which requires moving
  520.         // the current iterator forward one, because insert does insert before.
  521.         if (ElementIter != Elements.end() &&
  522.             ElementIter->index() < ElementIndex)
  523.           ++ElementIter;
  524.         ElementIter = Elements.emplace(ElementIter, ElementIndex);
  525.       }
  526.     }
  527.     CurrElementIter = ElementIter;
  528.  
  529.     ElementIter->set(Idx % ElementSize);
  530.   }
  531.  
  532.   bool test_and_set(unsigned Idx) {
  533.     bool old = test(Idx);
  534.     if (!old) {
  535.       set(Idx);
  536.       return true;
  537.     }
  538.     return false;
  539.   }
  540.  
  541.   bool operator!=(const SparseBitVector &RHS) const {
  542.     return !(*this == RHS);
  543.   }
  544.  
  545.   bool operator==(const SparseBitVector &RHS) const {
  546.     ElementListConstIter Iter1 = Elements.begin();
  547.     ElementListConstIter Iter2 = RHS.Elements.begin();
  548.  
  549.     for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
  550.          ++Iter1, ++Iter2) {
  551.       if (*Iter1 != *Iter2)
  552.         return false;
  553.     }
  554.     return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
  555.   }
  556.  
  557.   // Union our bitmap with the RHS and return true if we changed.
  558.   bool operator|=(const SparseBitVector &RHS) {
  559.     if (this == &RHS)
  560.       return false;
  561.  
  562.     bool changed = false;
  563.     ElementListIter Iter1 = Elements.begin();
  564.     ElementListConstIter Iter2 = RHS.Elements.begin();
  565.  
  566.     // If RHS is empty, we are done
  567.     if (RHS.Elements.empty())
  568.       return false;
  569.  
  570.     while (Iter2 != RHS.Elements.end()) {
  571.       if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
  572.         Elements.insert(Iter1, *Iter2);
  573.         ++Iter2;
  574.         changed = true;
  575.       } else if (Iter1->index() == Iter2->index()) {
  576.         changed |= Iter1->unionWith(*Iter2);
  577.         ++Iter1;
  578.         ++Iter2;
  579.       } else {
  580.         ++Iter1;
  581.       }
  582.     }
  583.     CurrElementIter = Elements.begin();
  584.     return changed;
  585.   }
  586.  
  587.   // Intersect our bitmap with the RHS and return true if ours changed.
  588.   bool operator&=(const SparseBitVector &RHS) {
  589.     if (this == &RHS)
  590.       return false;
  591.  
  592.     bool changed = false;
  593.     ElementListIter Iter1 = Elements.begin();
  594.     ElementListConstIter Iter2 = RHS.Elements.begin();
  595.  
  596.     // Check if both bitmaps are empty.
  597.     if (Elements.empty() && RHS.Elements.empty())
  598.       return false;
  599.  
  600.     // Loop through, intersecting as we go, erasing elements when necessary.
  601.     while (Iter2 != RHS.Elements.end()) {
  602.       if (Iter1 == Elements.end()) {
  603.         CurrElementIter = Elements.begin();
  604.         return changed;
  605.       }
  606.  
  607.       if (Iter1->index() > Iter2->index()) {
  608.         ++Iter2;
  609.       } else if (Iter1->index() == Iter2->index()) {
  610.         bool BecameZero;
  611.         changed |= Iter1->intersectWith(*Iter2, BecameZero);
  612.         if (BecameZero) {
  613.           ElementListIter IterTmp = Iter1;
  614.           ++Iter1;
  615.           Elements.erase(IterTmp);
  616.         } else {
  617.           ++Iter1;
  618.         }
  619.         ++Iter2;
  620.       } else {
  621.         ElementListIter IterTmp = Iter1;
  622.         ++Iter1;
  623.         Elements.erase(IterTmp);
  624.         changed = true;
  625.       }
  626.     }
  627.     if (Iter1 != Elements.end()) {
  628.       Elements.erase(Iter1, Elements.end());
  629.       changed = true;
  630.     }
  631.     CurrElementIter = Elements.begin();
  632.     return changed;
  633.   }
  634.  
  635.   // Intersect our bitmap with the complement of the RHS and return true
  636.   // if ours changed.
  637.   bool intersectWithComplement(const SparseBitVector &RHS) {
  638.     if (this == &RHS) {
  639.       if (!empty()) {
  640.         clear();
  641.         return true;
  642.       }
  643.       return false;
  644.     }
  645.  
  646.     bool changed = false;
  647.     ElementListIter Iter1 = Elements.begin();
  648.     ElementListConstIter Iter2 = RHS.Elements.begin();
  649.  
  650.     // If either our bitmap or RHS is empty, we are done
  651.     if (Elements.empty() || RHS.Elements.empty())
  652.       return false;
  653.  
  654.     // Loop through, intersecting as we go, erasing elements when necessary.
  655.     while (Iter2 != RHS.Elements.end()) {
  656.       if (Iter1 == Elements.end()) {
  657.         CurrElementIter = Elements.begin();
  658.         return changed;
  659.       }
  660.  
  661.       if (Iter1->index() > Iter2->index()) {
  662.         ++Iter2;
  663.       } else if (Iter1->index() == Iter2->index()) {
  664.         bool BecameZero;
  665.         changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
  666.         if (BecameZero) {
  667.           ElementListIter IterTmp = Iter1;
  668.           ++Iter1;
  669.           Elements.erase(IterTmp);
  670.         } else {
  671.           ++Iter1;
  672.         }
  673.         ++Iter2;
  674.       } else {
  675.         ++Iter1;
  676.       }
  677.     }
  678.     CurrElementIter = Elements.begin();
  679.     return changed;
  680.   }
  681.  
  682.   bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
  683.     return intersectWithComplement(*RHS);
  684.   }
  685.  
  686.   //  Three argument version of intersectWithComplement.
  687.   //  Result of RHS1 & ~RHS2 is stored into this bitmap.
  688.   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
  689.                                const SparseBitVector<ElementSize> &RHS2)
  690.   {
  691.     if (this == &RHS1) {
  692.       intersectWithComplement(RHS2);
  693.       return;
  694.     } else if (this == &RHS2) {
  695.       SparseBitVector RHS2Copy(RHS2);
  696.       intersectWithComplement(RHS1, RHS2Copy);
  697.       return;
  698.     }
  699.  
  700.     Elements.clear();
  701.     CurrElementIter = Elements.begin();
  702.     ElementListConstIter Iter1 = RHS1.Elements.begin();
  703.     ElementListConstIter Iter2 = RHS2.Elements.begin();
  704.  
  705.     // If RHS1 is empty, we are done
  706.     // If RHS2 is empty, we still have to copy RHS1
  707.     if (RHS1.Elements.empty())
  708.       return;
  709.  
  710.     // Loop through, intersecting as we go, erasing elements when necessary.
  711.     while (Iter2 != RHS2.Elements.end()) {
  712.       if (Iter1 == RHS1.Elements.end())
  713.         return;
  714.  
  715.       if (Iter1->index() > Iter2->index()) {
  716.         ++Iter2;
  717.       } else if (Iter1->index() == Iter2->index()) {
  718.         bool BecameZero = false;
  719.         Elements.emplace_back(Iter1->index());
  720.         Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
  721.         if (BecameZero)
  722.           Elements.pop_back();
  723.         ++Iter1;
  724.         ++Iter2;
  725.       } else {
  726.         Elements.push_back(*Iter1++);
  727.       }
  728.     }
  729.  
  730.     // copy the remaining elements
  731.     std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));
  732.   }
  733.  
  734.   void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
  735.                                const SparseBitVector<ElementSize> *RHS2) {
  736.     intersectWithComplement(*RHS1, *RHS2);
  737.   }
  738.  
  739.   bool intersects(const SparseBitVector<ElementSize> *RHS) const {
  740.     return intersects(*RHS);
  741.   }
  742.  
  743.   // Return true if we share any bits in common with RHS
  744.   bool intersects(const SparseBitVector<ElementSize> &RHS) const {
  745.     ElementListConstIter Iter1 = Elements.begin();
  746.     ElementListConstIter Iter2 = RHS.Elements.begin();
  747.  
  748.     // Check if both bitmaps are empty.
  749.     if (Elements.empty() && RHS.Elements.empty())
  750.       return false;
  751.  
  752.     // Loop through, intersecting stopping when we hit bits in common.
  753.     while (Iter2 != RHS.Elements.end()) {
  754.       if (Iter1 == Elements.end())
  755.         return false;
  756.  
  757.       if (Iter1->index() > Iter2->index()) {
  758.         ++Iter2;
  759.       } else if (Iter1->index() == Iter2->index()) {
  760.         if (Iter1->intersects(*Iter2))
  761.           return true;
  762.         ++Iter1;
  763.         ++Iter2;
  764.       } else {
  765.         ++Iter1;
  766.       }
  767.     }
  768.     return false;
  769.   }
  770.  
  771.   // Return true iff all bits set in this SparseBitVector are
  772.   // also set in RHS.
  773.   bool contains(const SparseBitVector<ElementSize> &RHS) const {
  774.     SparseBitVector<ElementSize> Result(*this);
  775.     Result &= RHS;
  776.     return (Result == RHS);
  777.   }
  778.  
  779.   // Return the first set bit in the bitmap.  Return -1 if no bits are set.
  780.   int find_first() const {
  781.     if (Elements.empty())
  782.       return -1;
  783.     const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
  784.     return (First.index() * ElementSize) + First.find_first();
  785.   }
  786.  
  787.   // Return the last set bit in the bitmap.  Return -1 if no bits are set.
  788.   int find_last() const {
  789.     if (Elements.empty())
  790.       return -1;
  791.     const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
  792.     return (Last.index() * ElementSize) + Last.find_last();
  793.   }
  794.  
  795.   // Return true if the SparseBitVector is empty
  796.   bool empty() const {
  797.     return Elements.empty();
  798.   }
  799.  
  800.   unsigned count() const {
  801.     unsigned BitCount = 0;
  802.     for (ElementListConstIter Iter = Elements.begin();
  803.          Iter != Elements.end();
  804.          ++Iter)
  805.       BitCount += Iter->count();
  806.  
  807.     return BitCount;
  808.   }
  809.  
  810.   iterator begin() const {
  811.     return iterator(this);
  812.   }
  813.  
  814.   iterator end() const {
  815.     return iterator(this, true);
  816.   }
  817. };
  818.  
  819. // Convenience functions to allow Or and And without dereferencing in the user
  820. // code.
  821.  
  822. template <unsigned ElementSize>
  823. inline bool operator |=(SparseBitVector<ElementSize> &LHS,
  824.                         const SparseBitVector<ElementSize> *RHS) {
  825.   return LHS |= *RHS;
  826. }
  827.  
  828. template <unsigned ElementSize>
  829. inline bool operator |=(SparseBitVector<ElementSize> *LHS,
  830.                         const SparseBitVector<ElementSize> &RHS) {
  831.   return LHS->operator|=(RHS);
  832. }
  833.  
  834. template <unsigned ElementSize>
  835. inline bool operator &=(SparseBitVector<ElementSize> *LHS,
  836.                         const SparseBitVector<ElementSize> &RHS) {
  837.   return LHS->operator&=(RHS);
  838. }
  839.  
  840. template <unsigned ElementSize>
  841. inline bool operator &=(SparseBitVector<ElementSize> &LHS,
  842.                         const SparseBitVector<ElementSize> *RHS) {
  843.   return LHS &= *RHS;
  844. }
  845.  
  846. // Convenience functions for infix union, intersection, difference operators.
  847.  
  848. template <unsigned ElementSize>
  849. inline SparseBitVector<ElementSize>
  850. operator|(const SparseBitVector<ElementSize> &LHS,
  851.           const SparseBitVector<ElementSize> &RHS) {
  852.   SparseBitVector<ElementSize> Result(LHS);
  853.   Result |= RHS;
  854.   return Result;
  855. }
  856.  
  857. template <unsigned ElementSize>
  858. inline SparseBitVector<ElementSize>
  859. operator&(const SparseBitVector<ElementSize> &LHS,
  860.           const SparseBitVector<ElementSize> &RHS) {
  861.   SparseBitVector<ElementSize> Result(LHS);
  862.   Result &= RHS;
  863.   return Result;
  864. }
  865.  
  866. template <unsigned ElementSize>
  867. inline SparseBitVector<ElementSize>
  868. operator-(const SparseBitVector<ElementSize> &LHS,
  869.           const SparseBitVector<ElementSize> &RHS) {
  870.   SparseBitVector<ElementSize> Result;
  871.   Result.intersectWithComplement(LHS, RHS);
  872.   return Result;
  873. }
  874.  
  875. // Dump a SparseBitVector to a stream
  876. template <unsigned ElementSize>
  877. void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
  878.   out << "[";
  879.  
  880.   typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
  881.     be = LHS.end();
  882.   if (bi != be) {
  883.     out << *bi;
  884.     for (++bi; bi != be; ++bi) {
  885.       out << " " << *bi;
  886.     }
  887.   }
  888.   out << "]\n";
  889. }
  890.  
  891. } // end namespace llvm
  892.  
  893. #endif // LLVM_ADT_SPARSEBITVECTOR_H
  894.