LLVM  6.0.0svn
SparseBitVector.h
Go to the documentation of this file.
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 
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;
46  enum {
47  BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
49  BITS_PER_ELEMENT = ElementSize
50  };
51 
52 private:
53  // Index of Element in terms of where first bit starts.
54  unsigned ElementIndex;
56 
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 {
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 += 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  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.
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.
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.
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
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>
257  using ElementList = std::list<SparseBitVectorElement<ElementSize>>;
258  using ElementListIter = typename ElementList::iterator;
259  using ElementListConstIter = typename ElementList::const_iterator;
260  enum {
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  ElementListIter FindLowerBound(unsigned ElementIndex) {
271 
272  if (Elements.empty()) {
273  CurrElementIter = Elements.begin();
274  return Elements.begin();
275  }
276 
277  // Make sure our current iterator is valid.
278  if (CurrElementIter == Elements.end())
279  --CurrElementIter;
280 
281  // Search from our current iterator, either backwards or forwards,
282  // depending on what element we are looking for.
283  ElementListIter ElementIter = CurrElementIter;
284  if (CurrElementIter->index() == ElementIndex) {
285  return ElementIter;
286  } else if (CurrElementIter->index() > ElementIndex) {
287  while (ElementIter != Elements.begin()
288  && ElementIter->index() > ElementIndex)
289  --ElementIter;
290  } else {
291  while (ElementIter != Elements.end() &&
292  ElementIter->index() < ElementIndex)
293  ++ElementIter;
294  }
295  CurrElementIter = ElementIter;
296  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.
318 
319  // Move our iterator to the first non-zero bit in the bitmap.
320  void AdvanceToFirstNonZero() {
321  if (AtEnd)
322  return;
323  if (BitVector->Elements.empty()) {
324  AtEnd = true;
325  return;
326  }
327  Iter = BitVector->Elements.begin();
328  BitNumber = Iter->index() * ElementSize;
329  unsigned BitPos = Iter->find_first();
330  BitNumber += BitPos;
331  WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
332  Bits = Iter->word(WordNumber);
333  Bits >>= BitPos % BITWORD_SIZE;
334  }
335 
336  // Move our iterator to the next non-zero bit.
337  void AdvanceToNextNonZero() {
338  if (AtEnd)
339  return;
340 
341  while (Bits && !(Bits & 1)) {
342  Bits >>= 1;
343  BitNumber += 1;
344  }
345 
346  // See if we ran out of Bits in this word.
347  if (!Bits) {
348  int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
349  // If we ran out of set bits in this element, move to next element.
350  if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
351  ++Iter;
352  WordNumber = 0;
353 
354  // We may run out of elements in the bitmap.
355  if (Iter == BitVector->Elements.end()) {
356  AtEnd = true;
357  return;
358  }
359  // Set up for next non-zero word in bitmap.
360  BitNumber = Iter->index() * ElementSize;
361  NextSetBitNumber = Iter->find_first();
362  BitNumber += NextSetBitNumber;
363  WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
364  Bits = Iter->word(WordNumber);
365  Bits >>= NextSetBitNumber % BITWORD_SIZE;
366  } else {
367  WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
368  Bits = Iter->word(WordNumber);
369  Bits >>= NextSetBitNumber % BITWORD_SIZE;
370  BitNumber = Iter->index() * ElementSize;
371  BitNumber += NextSetBitNumber;
372  }
373  }
374  }
375 
376  public:
377  SparseBitVectorIterator() = default;
378 
379  SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
380  bool end = false):BitVector(RHS) {
381  Iter = BitVector->Elements.begin();
382  BitNumber = 0;
383  Bits = 0;
384  WordNumber = ~0;
385  AtEnd = end;
386  AdvanceToFirstNonZero();
387  }
388 
389  // Preincrement.
390  inline SparseBitVectorIterator& operator++() {
391  ++BitNumber;
392  Bits >>= 1;
393  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  if (AtEnd && RHS.AtEnd)
412  return true;
413  // Otherwise they are the same if they have the same bit number and
414  // bitmap.
415  return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
416  }
417 
418  bool operator!=(const SparseBitVectorIterator &RHS) const {
419  return !(*this == RHS);
420  }
421  };
422 
423 public:
424  using iterator = SparseBitVectorIterator;
425 
427  CurrElementIter = Elements.begin();
428  }
429 
430  // SparseBitVector copy ctor.
432  ElementListConstIter ElementIter = RHS.Elements.begin();
433  while (ElementIter != RHS.Elements.end()) {
434  Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
435  ++ElementIter;
436  }
437 
438  CurrElementIter = Elements.begin ();
439  }
440 
441  ~SparseBitVector() = default;
442 
443  // Clear.
444  void clear() {
445  Elements.clear();
446  }
447 
448  // Assignment
450  if (this == &RHS)
451  return *this;
452 
453  Elements.clear();
454 
455  ElementListConstIter ElementIter = RHS.Elements.begin();
456  while (ElementIter != RHS.Elements.end()) {
457  Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
458  ++ElementIter;
459  }
460 
461  CurrElementIter = Elements.begin ();
462 
463  return *this;
464  }
465 
466  // Test, Reset, and Set a bit in the bitmap.
467  bool test(unsigned Idx) {
468  if (Elements.empty())
469  return false;
470 
471  unsigned ElementIndex = Idx / ElementSize;
472  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  if (ElementIter == Elements.end() ||
477  ElementIter->index() != ElementIndex)
478  return false;
479  return ElementIter->test(Idx % ElementSize);
480  }
481 
482  void reset(unsigned Idx) {
483  if (Elements.empty())
484  return;
485 
486  unsigned ElementIndex = Idx / ElementSize;
487  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  if (ElementIter == Elements.end() ||
492  ElementIter->index() != ElementIndex)
493  return;
494  ElementIter->reset(Idx % ElementSize);
495 
496  // When the element is zeroed out, delete it.
497  if (ElementIter->empty()) {
498  ++CurrElementIter;
499  Elements.erase(ElementIter);
500  }
501  }
502 
503  void set(unsigned Idx) {
504  unsigned ElementIndex = Idx / ElementSize;
505  ElementListIter ElementIter;
506  if (Elements.empty()) {
507  ElementIter = Elements.emplace(Elements.end(), ElementIndex);
508  } else {
509  ElementIter = FindLowerBound(ElementIndex);
510 
511  if (ElementIter == Elements.end() ||
512  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  if (ElementIter != Elements.end() &&
517  ElementIter->index() < ElementIndex)
518  ++ElementIter;
519  ElementIter = Elements.emplace(ElementIter, ElementIndex);
520  }
521  }
522  CurrElementIter = ElementIter;
523 
524  ElementIter->set(Idx % ElementSize);
525  }
526 
527  bool test_and_set(unsigned Idx) {
528  bool old = test(Idx);
529  if (!old) {
530  set(Idx);
531  return true;
532  }
533  return false;
534  }
535 
536  bool operator!=(const SparseBitVector &RHS) const {
537  return !(*this == RHS);
538  }
539 
540  bool operator==(const SparseBitVector &RHS) const {
541  ElementListConstIter Iter1 = Elements.begin();
542  ElementListConstIter Iter2 = RHS.Elements.begin();
543 
544  for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
545  ++Iter1, ++Iter2) {
546  if (*Iter1 != *Iter2)
547  return false;
548  }
549  return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
550  }
551 
552  // Union our bitmap with the RHS and return true if we changed.
553  bool operator|=(const SparseBitVector &RHS) {
554  if (this == &RHS)
555  return false;
556 
557  bool changed = false;
558  ElementListIter Iter1 = Elements.begin();
559  ElementListConstIter Iter2 = RHS.Elements.begin();
560 
561  // If RHS is empty, we are done
562  if (RHS.Elements.empty())
563  return false;
564 
565  while (Iter2 != RHS.Elements.end()) {
566  if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
567  Elements.insert(Iter1, *Iter2);
568  ++Iter2;
569  changed = true;
570  } else if (Iter1->index() == Iter2->index()) {
571  changed |= Iter1->unionWith(*Iter2);
572  ++Iter1;
573  ++Iter2;
574  } else {
575  ++Iter1;
576  }
577  }
578  CurrElementIter = Elements.begin();
579  return changed;
580  }
581 
582  // Intersect our bitmap with the RHS and return true if ours changed.
583  bool operator&=(const SparseBitVector &RHS) {
584  if (this == &RHS)
585  return false;
586 
587  bool changed = false;
588  ElementListIter Iter1 = Elements.begin();
589  ElementListConstIter Iter2 = RHS.Elements.begin();
590 
591  // Check if both bitmaps are empty.
592  if (Elements.empty() && RHS.Elements.empty())
593  return false;
594 
595  // Loop through, intersecting as we go, erasing elements when necessary.
596  while (Iter2 != RHS.Elements.end()) {
597  if (Iter1 == Elements.end()) {
598  CurrElementIter = Elements.begin();
599  return changed;
600  }
601 
602  if (Iter1->index() > Iter2->index()) {
603  ++Iter2;
604  } else if (Iter1->index() == Iter2->index()) {
605  bool BecameZero;
606  changed |= Iter1->intersectWith(*Iter2, BecameZero);
607  if (BecameZero) {
608  ElementListIter IterTmp = Iter1;
609  ++Iter1;
610  Elements.erase(IterTmp);
611  } else {
612  ++Iter1;
613  }
614  ++Iter2;
615  } else {
616  ElementListIter IterTmp = Iter1;
617  ++Iter1;
618  Elements.erase(IterTmp);
619  changed = true;
620  }
621  }
622  if (Iter1 != Elements.end()) {
623  Elements.erase(Iter1, Elements.end());
624  changed = true;
625  }
626  CurrElementIter = Elements.begin();
627  return changed;
628  }
629 
630  // Intersect our bitmap with the complement of the RHS and return true
631  // if ours changed.
633  if (this == &RHS) {
634  if (!empty()) {
635  clear();
636  return true;
637  }
638  return false;
639  }
640 
641  bool changed = false;
642  ElementListIter Iter1 = Elements.begin();
643  ElementListConstIter Iter2 = RHS.Elements.begin();
644 
645  // If either our bitmap or RHS is empty, we are done
646  if (Elements.empty() || RHS.Elements.empty())
647  return false;
648 
649  // Loop through, intersecting as we go, erasing elements when necessary.
650  while (Iter2 != RHS.Elements.end()) {
651  if (Iter1 == Elements.end()) {
652  CurrElementIter = Elements.begin();
653  return changed;
654  }
655 
656  if (Iter1->index() > Iter2->index()) {
657  ++Iter2;
658  } else if (Iter1->index() == Iter2->index()) {
659  bool BecameZero;
660  changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
661  if (BecameZero) {
662  ElementListIter IterTmp = Iter1;
663  ++Iter1;
664  Elements.erase(IterTmp);
665  } else {
666  ++Iter1;
667  }
668  ++Iter2;
669  } else {
670  ++Iter1;
671  }
672  }
673  CurrElementIter = Elements.begin();
674  return changed;
675  }
676 
678  return intersectWithComplement(*RHS);
679  }
680 
681  // Three argument version of intersectWithComplement.
682  // Result of RHS1 & ~RHS2 is stored into this bitmap.
684  const SparseBitVector<ElementSize> &RHS2)
685  {
686  if (this == &RHS1) {
688  return;
689  } else if (this == &RHS2) {
690  SparseBitVector RHS2Copy(RHS2);
691  intersectWithComplement(RHS1, RHS2Copy);
692  return;
693  }
694 
695  Elements.clear();
696  CurrElementIter = Elements.begin();
697  ElementListConstIter Iter1 = RHS1.Elements.begin();
698  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  if (RHS1.Elements.empty())
703  return;
704 
705  // Loop through, intersecting as we go, erasing elements when necessary.
706  while (Iter2 != RHS2.Elements.end()) {
707  if (Iter1 == RHS1.Elements.end())
708  return;
709 
710  if (Iter1->index() > Iter2->index()) {
711  ++Iter2;
712  } else if (Iter1->index() == Iter2->index()) {
713  bool BecameZero = false;
714  Elements.emplace_back(Iter1->index());
715  Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
716  if (BecameZero)
717  Elements.pop_back();
718  ++Iter1;
719  ++Iter2;
720  } else {
721  Elements.push_back(*Iter1++);
722  }
723  }
724 
725  // copy the remaining elements
726  std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));
727  }
728 
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  bool intersects(const SparseBitVector<ElementSize> &RHS) const {
740  ElementListConstIter Iter1 = Elements.begin();
741  ElementListConstIter Iter2 = RHS.Elements.begin();
742 
743  // Check if both bitmaps are empty.
744  if (Elements.empty() && RHS.Elements.empty())
745  return false;
746 
747  // Loop through, intersecting stopping when we hit bits in common.
748  while (Iter2 != RHS.Elements.end()) {
749  if (Iter1 == Elements.end())
750  return false;
751 
752  if (Iter1->index() > Iter2->index()) {
753  ++Iter2;
754  } else if (Iter1->index() == Iter2->index()) {
755  if (Iter1->intersects(*Iter2))
756  return true;
757  ++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  if (Elements.empty())
777  return -1;
778  const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
779  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  int find_last() const {
784  if (Elements.empty())
785  return -1;
786  const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
787  return (Last.index() * ElementSize) + Last.find_last();
788  }
789 
790  // Return true if the SparseBitVector is empty
791  bool empty() const {
792  return Elements.empty();
793  }
794 
795  unsigned count() const {
796  unsigned BitCount = 0;
797  for (ElementListConstIter Iter = Elements.begin();
798  Iter != Elements.end();
799  ++Iter)
800  BitCount += Iter->count();
801 
802  return BitCount;
803  }
804 
805  iterator begin() const {
806  return iterator(this);
807  }
808 
809  iterator end() const {
810  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>
819  const SparseBitVector<ElementSize> *RHS) {
820  return LHS |= *RHS;
821 }
822 
823 template <unsigned ElementSize>
825  const SparseBitVector<ElementSize> &RHS) {
826  return LHS->operator|=(RHS);
827 }
828 
829 template <unsigned ElementSize>
831  const SparseBitVector<ElementSize> &RHS) {
832  return LHS->operator&=(RHS);
833 }
834 
835 template <unsigned ElementSize>
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>
846  const SparseBitVector<ElementSize> &RHS) {
847  SparseBitVector<ElementSize> Result(LHS);
848  Result |= RHS;
849  return Result;
850 }
851 
852 template <unsigned ElementSize>
855  const SparseBitVector<ElementSize> &RHS) {
856  SparseBitVector<ElementSize> Result(LHS);
857  Result &= RHS;
858  return Result;
859 }
860 
861 template <unsigned ElementSize>
864  const SparseBitVector<ElementSize> &RHS) {
866  Result.intersectWithComplement(LHS, RHS);
867  return Result;
868 }
869 
870 // Dump a SparseBitVector to a stream
871 template <unsigned ElementSize>
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
iterator end() const
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:243
bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:1958
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:181
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 intersectWithComplement(const SparseBitVectorElement &RHS, bool &BecameZero)
bool test(unsigned Idx)
void intersectWithComplement(const SparseBitVector< ElementSize > *RHS1, const SparseBitVector< ElementSize > *RHS2)
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2070
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:112
bool test_and_set(unsigned Idx)
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:512
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:210
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:2023
bool contains(const SparseBitVector< ElementSize > &RHS) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
E & operator &=(E &LHS, E RHS)
Definition: BitmaskEnum.h:134
SparseBitVectorIterator iterator
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:1978
bool intersects(const SparseBitVector< ElementSize > *RHS) const
bool test(unsigned Idx) const