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