LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
18 #include "llvm/ADT/ilist.h"
19 #include "llvm/ADT/ilist_node.h"
20 #include "llvm/Support/DataTypes.h"
24 #include <cassert>
25 #include <climits>
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 
43 template <unsigned ElementSize = 128>
45  : public ilist_node<SparseBitVectorElement<ElementSize> > {
46 public:
47  typedef unsigned long BitWord;
48  enum {
49  BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
51  BITS_PER_ELEMENT = ElementSize
52  };
53 
54 private:
55  // Index of Element in terms of where first bit starts.
56  unsigned ElementIndex;
58  // Needed for sentinels
61  ElementIndex = ~0U;
62  memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
63  }
64 
65 public:
66  explicit SparseBitVectorElement(unsigned Idx) {
67  ElementIndex = Idx;
68  memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
69  }
70 
71  // Comparison.
72  bool operator==(const SparseBitVectorElement &RHS) const {
73  if (ElementIndex != RHS.ElementIndex)
74  return false;
75  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
76  if (Bits[i] != RHS.Bits[i])
77  return false;
78  return true;
79  }
80 
81  bool operator!=(const SparseBitVectorElement &RHS) const {
82  return !(*this == RHS);
83  }
84 
85  // Return the bits that make up word Idx in our element.
86  BitWord word(unsigned Idx) const {
87  assert (Idx < BITWORDS_PER_ELEMENT);
88  return Bits[Idx];
89  }
90 
91  unsigned index() const {
92  return ElementIndex;
93  }
94 
95  bool empty() const {
96  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
97  if (Bits[i])
98  return false;
99  return true;
100  }
101 
102  void set(unsigned Idx) {
103  Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
104  }
105 
106  bool test_and_set (unsigned Idx) {
107  bool old = test(Idx);
108  if (!old) {
109  set(Idx);
110  return true;
111  }
112  return false;
113  }
114 
115  void reset(unsigned Idx) {
116  Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
117  }
118 
119  bool test(unsigned Idx) const {
120  return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
121  }
122 
123  unsigned count() const {
124  unsigned NumBits = 0;
125  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
126  if (sizeof(BitWord) == 4)
127  NumBits += CountPopulation_32(Bits[i]);
128  else if (sizeof(BitWord) == 8)
129  NumBits += CountPopulation_64(Bits[i]);
130  else
131  llvm_unreachable("Unsupported!");
132  return NumBits;
133  }
134 
135  /// find_first - Returns the index of the first set bit.
136  int find_first() const {
137  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
138  if (Bits[i] != 0) {
139  if (sizeof(BitWord) == 4)
140  return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
141  if (sizeof(BitWord) == 8)
142  return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
143  llvm_unreachable("Unsupported!");
144  }
145  llvm_unreachable("Illegal empty element");
146  }
147 
148  /// find_next - Returns the index of the next set bit starting from the
149  /// "Curr" bit. Returns -1 if the next set bit is not found.
150  int find_next(unsigned Curr) const {
151  if (Curr >= BITS_PER_ELEMENT)
152  return -1;
153 
154  unsigned WordPos = Curr / BITWORD_SIZE;
155  unsigned BitPos = Curr % BITWORD_SIZE;
156  BitWord Copy = Bits[WordPos];
157  assert (WordPos <= BITWORDS_PER_ELEMENT
158  && "Word Position outside of element");
159 
160  // Mask off previous bits.
161  Copy &= ~0UL << BitPos;
162 
163  if (Copy != 0) {
164  if (sizeof(BitWord) == 4)
165  return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
166  if (sizeof(BitWord) == 8)
167  return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
168  llvm_unreachable("Unsupported!");
169  }
170 
171  // Check subsequent words.
172  for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
173  if (Bits[i] != 0) {
174  if (sizeof(BitWord) == 4)
175  return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
176  if (sizeof(BitWord) == 8)
177  return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
178  llvm_unreachable("Unsupported!");
179  }
180  return -1;
181  }
182 
183  // Union this element with RHS and return true if this one changed.
185  bool changed = false;
186  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
187  BitWord old = changed ? 0 : Bits[i];
188 
189  Bits[i] |= RHS.Bits[i];
190  if (!changed && old != Bits[i])
191  changed = true;
192  }
193  return changed;
194  }
195 
196  // Return true if we have any bits in common with RHS
197  bool intersects(const SparseBitVectorElement &RHS) const {
198  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
199  if (RHS.Bits[i] & Bits[i])
200  return true;
201  }
202  return false;
203  }
204 
205  // Intersect this Element with RHS and return true if this one changed.
206  // BecameZero is set to true if this element became all-zero bits.
208  bool &BecameZero) {
209  bool changed = false;
210  bool allzero = true;
211 
212  BecameZero = false;
213  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
214  BitWord old = changed ? 0 : Bits[i];
215 
216  Bits[i] &= RHS.Bits[i];
217  if (Bits[i] != 0)
218  allzero = false;
219 
220  if (!changed && old != Bits[i])
221  changed = true;
222  }
223  BecameZero = allzero;
224  return changed;
225  }
226  // Intersect this Element with the complement of RHS and return true if this
227  // one changed. BecameZero is set to true if this element became all-zero
228  // bits.
230  bool &BecameZero) {
231  bool changed = false;
232  bool allzero = true;
233 
234  BecameZero = false;
235  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
236  BitWord old = changed ? 0 : Bits[i];
237 
238  Bits[i] &= ~RHS.Bits[i];
239  if (Bits[i] != 0)
240  allzero = false;
241 
242  if (!changed && old != Bits[i])
243  changed = true;
244  }
245  BecameZero = allzero;
246  return changed;
247  }
248  // Three argument version of intersectWithComplement that intersects
249  // RHS1 & ~RHS2 into this element
251  const SparseBitVectorElement &RHS2,
252  bool &BecameZero) {
253  bool allzero = true;
254 
255  BecameZero = false;
256  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
257  Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
258  if (Bits[i] != 0)
259  allzero = false;
260  }
261  BecameZero = allzero;
262  }
263 };
264 
265 template <unsigned ElementSize>
267  : public ilist_default_traits<SparseBitVectorElement<ElementSize> > {
269 
270  Element *createSentinel() const { return static_cast<Element *>(&Sentinel); }
271  static void destroySentinel(Element *) {}
272 
274  Element *ensureHead(Element *) const { return createSentinel(); }
275  static void noteHead(Element *, Element *) {}
276 
277 private:
278  mutable ilist_half_node<Element> Sentinel;
279 };
280 
281 template <unsigned ElementSize = 128>
284  typedef typename ElementList::iterator ElementListIter;
286  enum {
288  };
289 
290  // Pointer to our current Element.
291  ElementListIter CurrElementIter;
292  ElementList Elements;
293 
294  // This is like std::lower_bound, except we do linear searching from the
295  // current position.
296  ElementListIter FindLowerBound(unsigned ElementIndex) {
297 
298  if (Elements.empty()) {
299  CurrElementIter = Elements.begin();
300  return Elements.begin();
301  }
302 
303  // Make sure our current iterator is valid.
304  if (CurrElementIter == Elements.end())
305  --CurrElementIter;
306 
307  // Search from our current iterator, either backwards or forwards,
308  // depending on what element we are looking for.
309  ElementListIter ElementIter = CurrElementIter;
310  if (CurrElementIter->index() == ElementIndex) {
311  return ElementIter;
312  } else if (CurrElementIter->index() > ElementIndex) {
313  while (ElementIter != Elements.begin()
314  && ElementIter->index() > ElementIndex)
315  --ElementIter;
316  } else {
317  while (ElementIter != Elements.end() &&
318  ElementIter->index() < ElementIndex)
319  ++ElementIter;
320  }
321  CurrElementIter = ElementIter;
322  return ElementIter;
323  }
324 
325  // Iterator to walk set bits in the bitmap. This iterator is a lot uglier
326  // than it would be, in order to be efficient.
327  class SparseBitVectorIterator {
328  private:
329  bool AtEnd;
330 
332 
333  // Current element inside of bitmap.
335 
336  // Current bit number inside of our bitmap.
337  unsigned BitNumber;
338 
339  // Current word number inside of our element.
340  unsigned WordNumber;
341 
342  // Current bits from the element.
344 
345  // Move our iterator to the first non-zero bit in the bitmap.
346  void AdvanceToFirstNonZero() {
347  if (AtEnd)
348  return;
349  if (BitVector->Elements.empty()) {
350  AtEnd = true;
351  return;
352  }
353  Iter = BitVector->Elements.begin();
354  BitNumber = Iter->index() * ElementSize;
355  unsigned BitPos = Iter->find_first();
356  BitNumber += BitPos;
357  WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
358  Bits = Iter->word(WordNumber);
359  Bits >>= BitPos % BITWORD_SIZE;
360  }
361 
362  // Move our iterator to the next non-zero bit.
363  void AdvanceToNextNonZero() {
364  if (AtEnd)
365  return;
366 
367  while (Bits && !(Bits & 1)) {
368  Bits >>= 1;
369  BitNumber += 1;
370  }
371 
372  // See if we ran out of Bits in this word.
373  if (!Bits) {
374  int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
375  // If we ran out of set bits in this element, move to next element.
376  if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
377  ++Iter;
378  WordNumber = 0;
379 
380  // We may run out of elements in the bitmap.
381  if (Iter == BitVector->Elements.end()) {
382  AtEnd = true;
383  return;
384  }
385  // Set up for next non zero word in bitmap.
386  BitNumber = Iter->index() * ElementSize;
387  NextSetBitNumber = Iter->find_first();
388  BitNumber += NextSetBitNumber;
389  WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
390  Bits = Iter->word(WordNumber);
391  Bits >>= NextSetBitNumber % BITWORD_SIZE;
392  } else {
393  WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
394  Bits = Iter->word(WordNumber);
395  Bits >>= NextSetBitNumber % BITWORD_SIZE;
396  BitNumber = Iter->index() * ElementSize;
397  BitNumber += NextSetBitNumber;
398  }
399  }
400  }
401  public:
402  // Preincrement.
403  inline SparseBitVectorIterator& operator++() {
404  ++BitNumber;
405  Bits >>= 1;
406  AdvanceToNextNonZero();
407  return *this;
408  }
409 
410  // Postincrement.
411  inline SparseBitVectorIterator operator++(int) {
412  SparseBitVectorIterator tmp = *this;
413  ++*this;
414  return tmp;
415  }
416 
417  // Return the current set bit number.
418  unsigned operator*() const {
419  return BitNumber;
420  }
421 
422  bool operator==(const SparseBitVectorIterator &RHS) const {
423  // If they are both at the end, ignore the rest of the fields.
424  if (AtEnd && RHS.AtEnd)
425  return true;
426  // Otherwise they are the same if they have the same bit number and
427  // bitmap.
428  return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
429  }
430  bool operator!=(const SparseBitVectorIterator &RHS) const {
431  return !(*this == RHS);
432  }
433  SparseBitVectorIterator(): BitVector(NULL) {
434  }
435 
436 
437  SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
438  bool end = false):BitVector(RHS) {
439  Iter = BitVector->Elements.begin();
440  BitNumber = 0;
441  Bits = 0;
442  WordNumber = ~0;
443  AtEnd = end;
444  AdvanceToFirstNonZero();
445  }
446  };
447 public:
448  typedef SparseBitVectorIterator iterator;
449 
451  CurrElementIter = Elements.begin ();
452  }
453 
455  }
456 
457  // SparseBitVector copy ctor.
459  ElementListConstIter ElementIter = RHS.Elements.begin();
460  while (ElementIter != RHS.Elements.end()) {
461  Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
462  ++ElementIter;
463  }
464 
465  CurrElementIter = Elements.begin ();
466  }
467 
468  // Clear.
469  void clear() {
470  Elements.clear();
471  }
472 
473  // Assignment
475  Elements.clear();
476 
477  ElementListConstIter ElementIter = RHS.Elements.begin();
478  while (ElementIter != RHS.Elements.end()) {
479  Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
480  ++ElementIter;
481  }
482 
483  CurrElementIter = Elements.begin ();
484 
485  return *this;
486  }
487 
488  // Test, Reset, and Set a bit in the bitmap.
489  bool test(unsigned Idx) {
490  if (Elements.empty())
491  return false;
492 
493  unsigned ElementIndex = Idx / ElementSize;
494  ElementListIter ElementIter = FindLowerBound(ElementIndex);
495 
496  // If we can't find an element that is supposed to contain this bit, there
497  // is nothing more to do.
498  if (ElementIter == Elements.end() ||
499  ElementIter->index() != ElementIndex)
500  return false;
501  return ElementIter->test(Idx % ElementSize);
502  }
503 
504  void reset(unsigned Idx) {
505  if (Elements.empty())
506  return;
507 
508  unsigned ElementIndex = Idx / ElementSize;
509  ElementListIter ElementIter = FindLowerBound(ElementIndex);
510 
511  // If we can't find an element that is supposed to contain this bit, there
512  // is nothing more to do.
513  if (ElementIter == Elements.end() ||
514  ElementIter->index() != ElementIndex)
515  return;
516  ElementIter->reset(Idx % ElementSize);
517 
518  // When the element is zeroed out, delete it.
519  if (ElementIter->empty()) {
520  ++CurrElementIter;
521  Elements.erase(ElementIter);
522  }
523  }
524 
525  void set(unsigned Idx) {
526  unsigned ElementIndex = Idx / ElementSize;
528  ElementListIter ElementIter;
529  if (Elements.empty()) {
530  Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
531  ElementIter = Elements.insert(Elements.end(), Element);
532 
533  } else {
534  ElementIter = FindLowerBound(ElementIndex);
535 
536  if (ElementIter == Elements.end() ||
537  ElementIter->index() != ElementIndex) {
538  Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
539  // We may have hit the beginning of our SparseBitVector, in which case,
540  // we may need to insert right after this element, which requires moving
541  // the current iterator forward one, because insert does insert before.
542  if (ElementIter != Elements.end() &&
543  ElementIter->index() < ElementIndex)
544  ElementIter = Elements.insert(++ElementIter, Element);
545  else
546  ElementIter = Elements.insert(ElementIter, Element);
547  }
548  }
549  CurrElementIter = ElementIter;
550 
551  ElementIter->set(Idx % ElementSize);
552  }
553 
554  bool test_and_set (unsigned Idx) {
555  bool old = test(Idx);
556  if (!old) {
557  set(Idx);
558  return true;
559  }
560  return false;
561  }
562 
563  bool operator!=(const SparseBitVector &RHS) const {
564  return !(*this == RHS);
565  }
566 
567  bool operator==(const SparseBitVector &RHS) const {
568  ElementListConstIter Iter1 = Elements.begin();
569  ElementListConstIter Iter2 = RHS.Elements.begin();
570 
571  for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
572  ++Iter1, ++Iter2) {
573  if (*Iter1 != *Iter2)
574  return false;
575  }
576  return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
577  }
578 
579  // Union our bitmap with the RHS and return true if we changed.
580  bool operator|=(const SparseBitVector &RHS) {
581  bool changed = false;
582  ElementListIter Iter1 = Elements.begin();
583  ElementListConstIter Iter2 = RHS.Elements.begin();
584 
585  // If RHS is empty, we are done
586  if (RHS.Elements.empty())
587  return false;
588 
589  while (Iter2 != RHS.Elements.end()) {
590  if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
591  Elements.insert(Iter1,
593  ++Iter2;
594  changed = true;
595  } else if (Iter1->index() == Iter2->index()) {
596  changed |= Iter1->unionWith(*Iter2);
597  ++Iter1;
598  ++Iter2;
599  } else {
600  ++Iter1;
601  }
602  }
603  CurrElementIter = Elements.begin();
604  return changed;
605  }
606 
607  // Intersect our bitmap with the RHS and return true if ours changed.
608  bool operator&=(const SparseBitVector &RHS) {
609  bool changed = false;
610  ElementListIter Iter1 = Elements.begin();
611  ElementListConstIter Iter2 = RHS.Elements.begin();
612 
613  // Check if both bitmaps are empty.
614  if (Elements.empty() && RHS.Elements.empty())
615  return false;
616 
617  // Loop through, intersecting as we go, erasing elements when necessary.
618  while (Iter2 != RHS.Elements.end()) {
619  if (Iter1 == Elements.end()) {
620  CurrElementIter = Elements.begin();
621  return changed;
622  }
623 
624  if (Iter1->index() > Iter2->index()) {
625  ++Iter2;
626  } else if (Iter1->index() == Iter2->index()) {
627  bool BecameZero;
628  changed |= Iter1->intersectWith(*Iter2, BecameZero);
629  if (BecameZero) {
630  ElementListIter IterTmp = Iter1;
631  ++Iter1;
632  Elements.erase(IterTmp);
633  } else {
634  ++Iter1;
635  }
636  ++Iter2;
637  } else {
638  ElementListIter IterTmp = Iter1;
639  ++Iter1;
640  Elements.erase(IterTmp);
641  }
642  }
643  Elements.erase(Iter1, Elements.end());
644  CurrElementIter = Elements.begin();
645  return changed;
646  }
647 
648  // Intersect our bitmap with the complement of the RHS and return true
649  // if ours changed.
651  bool changed = false;
652  ElementListIter Iter1 = Elements.begin();
653  ElementListConstIter Iter2 = RHS.Elements.begin();
654 
655  // If either our bitmap or RHS is empty, we are done
656  if (Elements.empty() || RHS.Elements.empty())
657  return false;
658 
659  // Loop through, intersecting as we go, erasing elements when necessary.
660  while (Iter2 != RHS.Elements.end()) {
661  if (Iter1 == Elements.end()) {
662  CurrElementIter = Elements.begin();
663  return changed;
664  }
665 
666  if (Iter1->index() > Iter2->index()) {
667  ++Iter2;
668  } else if (Iter1->index() == Iter2->index()) {
669  bool BecameZero;
670  changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
671  if (BecameZero) {
672  ElementListIter IterTmp = Iter1;
673  ++Iter1;
674  Elements.erase(IterTmp);
675  } else {
676  ++Iter1;
677  }
678  ++Iter2;
679  } else {
680  ++Iter1;
681  }
682  }
683  CurrElementIter = Elements.begin();
684  return changed;
685  }
686 
688  return intersectWithComplement(*RHS);
689  }
690 
691 
692  // Three argument version of intersectWithComplement.
693  // Result of RHS1 & ~RHS2 is stored into this bitmap.
695  const SparseBitVector<ElementSize> &RHS2)
696  {
697  Elements.clear();
698  CurrElementIter = Elements.begin();
699  ElementListConstIter Iter1 = RHS1.Elements.begin();
700  ElementListConstIter Iter2 = RHS2.Elements.begin();
701 
702  // If RHS1 is empty, we are done
703  // If RHS2 is empty, we still have to copy RHS1
704  if (RHS1.Elements.empty())
705  return;
706 
707  // Loop through, intersecting as we go, erasing elements when necessary.
708  while (Iter2 != RHS2.Elements.end()) {
709  if (Iter1 == RHS1.Elements.end())
710  return;
711 
712  if (Iter1->index() > Iter2->index()) {
713  ++Iter2;
714  } else if (Iter1->index() == Iter2->index()) {
715  bool BecameZero = false;
717  new SparseBitVectorElement<ElementSize>(Iter1->index());
718  NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero);
719  if (!BecameZero) {
720  Elements.push_back(NewElement);
721  }
722  else
723  delete NewElement;
724  ++Iter1;
725  ++Iter2;
726  } else {
729  Elements.push_back(NewElement);
730  ++Iter1;
731  }
732  }
733 
734  // copy the remaining elements
735  while (Iter1 != RHS1.Elements.end()) {
738  Elements.push_back(NewElement);
739  ++Iter1;
740  }
741 
742  return;
743  }
744 
746  const SparseBitVector<ElementSize> *RHS2) {
747  intersectWithComplement(*RHS1, *RHS2);
748  }
749 
750  bool intersects(const SparseBitVector<ElementSize> *RHS) const {
751  return intersects(*RHS);
752  }
753 
754  // Return true if we share any bits in common with RHS
755  bool intersects(const SparseBitVector<ElementSize> &RHS) const {
756  ElementListConstIter Iter1 = Elements.begin();
757  ElementListConstIter Iter2 = RHS.Elements.begin();
758 
759  // Check if both bitmaps are empty.
760  if (Elements.empty() && RHS.Elements.empty())
761  return false;
762 
763  // Loop through, intersecting stopping when we hit bits in common.
764  while (Iter2 != RHS.Elements.end()) {
765  if (Iter1 == Elements.end())
766  return false;
767 
768  if (Iter1->index() > Iter2->index()) {
769  ++Iter2;
770  } else if (Iter1->index() == Iter2->index()) {
771  if (Iter1->intersects(*Iter2))
772  return true;
773  ++Iter1;
774  ++Iter2;
775  } else {
776  ++Iter1;
777  }
778  }
779  return false;
780  }
781 
782  // Return true iff all bits set in this SparseBitVector are
783  // also set in RHS.
784  bool contains(const SparseBitVector<ElementSize> &RHS) const {
785  SparseBitVector<ElementSize> Result(*this);
786  Result &= RHS;
787  return (Result == RHS);
788  }
789 
790  // Return the first set bit in the bitmap. Return -1 if no bits are set.
791  int find_first() const {
792  if (Elements.empty())
793  return -1;
794  const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
795  return (First.index() * ElementSize) + First.find_first();
796  }
797 
798  // Return true if the SparseBitVector is empty
799  bool empty() const {
800  return Elements.empty();
801  }
802 
803  unsigned count() const {
804  unsigned BitCount = 0;
805  for (ElementListConstIter Iter = Elements.begin();
806  Iter != Elements.end();
807  ++Iter)
808  BitCount += Iter->count();
809 
810  return BitCount;
811  }
812  iterator begin() const {
813  return iterator(this);
814  }
815 
816  iterator end() const {
817  return iterator(this, true);
818  }
819 };
820 
821 // Convenience functions to allow Or and And without dereferencing in the user
822 // code.
823 
824 template <unsigned ElementSize>
826  const SparseBitVector<ElementSize> *RHS) {
827  return LHS |= *RHS;
828 }
829 
830 template <unsigned ElementSize>
832  const SparseBitVector<ElementSize> &RHS) {
833  return LHS->operator|=(RHS);
834 }
835 
836 template <unsigned ElementSize>
838  const SparseBitVector<ElementSize> &RHS) {
839  return LHS->operator&=(RHS);
840 }
841 
842 template <unsigned ElementSize>
844  const SparseBitVector<ElementSize> *RHS) {
845  return LHS &= *RHS;
846 }
847 
848 // Convenience functions for infix union, intersection, difference operators.
849 
850 template <unsigned ElementSize>
851 inline SparseBitVector<ElementSize>
853  const SparseBitVector<ElementSize> &RHS) {
854  SparseBitVector<ElementSize> Result(LHS);
855  Result |= RHS;
856  return Result;
857 }
858 
859 template <unsigned ElementSize>
860 inline SparseBitVector<ElementSize>
862  const SparseBitVector<ElementSize> &RHS) {
863  SparseBitVector<ElementSize> Result(LHS);
864  Result &= RHS;
865  return Result;
866 }
867 
868 template <unsigned ElementSize>
869 inline SparseBitVector<ElementSize>
871  const SparseBitVector<ElementSize> &RHS) {
873  Result.intersectWithComplement(LHS, RHS);
874  return Result;
875 }
876 
877 
878 
879 
880 // Dump a SparseBitVector to a stream
881 template <unsigned ElementSize>
883  out << "[";
884 
885  typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
886  be = LHS.end();
887  if (bi != be) {
888  out << *bi;
889  for (++bi; bi != be; ++bi) {
890  out << " " << *bi;
891  }
892  }
893  out << "]\n";
894 }
895 } // end namespace llvm
896 
897 #endif
void operator-(int, ilist_iterator< T >) LLVM_DELETED_FUNCTION
int find_first() const
Definition: BitVector.h:159
iplist< SparseBitVectorElement< ElementSize > >::iterator iterator
Definition: ilist.h:642
SparseBitVector & operator=(const SparseBitVector &RHS)
void set(unsigned Idx)
void intersectWithComplement(const SparseBitVector< ElementSize > &RHS1, const SparseBitVector< ElementSize > &RHS2)
SmallBitVector operator&(const SmallBitVector &LHS, const SmallBitVector &RHS)
bool intersects(const SparseBitVector< ElementSize > &RHS) const
bool intersectWithComplement(const SparseBitVector< ElementSize > *RHS) const
iterator begin()
Definition: ilist.h:359
bool test(unsigned Idx) const
bool operator!=(const SparseBitVector &RHS) const
SparseBitVectorElement(unsigned Idx)
bool unionWith(const SparseBitVectorElement &RHS)
bool operator|=(const SparseBitVector &RHS)
bool operator!=(const SparseBitVectorElement &RHS) const
bool intersectWithComplement(const SparseBitVectorElement &RHS, bool &BecameZero)
bool test(unsigned Idx)
int find_first() const
find_first - Returns the index of the first set bit.
#define llvm_unreachable(msg)
void intersectWithComplement(const SparseBitVector< ElementSize > *RHS1, const SparseBitVector< ElementSize > *RHS2)
SmallBitVector operator|(const SmallBitVector &LHS, const SmallBitVector &RHS)
void clear()
Definition: ilist.h:550
unsigned count() const
enable_if_c< std::numeric_limits< T >::is_integer &&!std::numeric_limits< T >::is_signed, std::size_t >::type countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the least significant bit to the most stopping at the first 1...
Definition: MathExtras.h:49
bool operator|=(SparseBitVector< ElementSize > &LHS, const SparseBitVector< ElementSize > *RHS)
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool test_and_set(unsigned Idx)
iterator begin() const
bool operator&=(const SparseBitVector &RHS)
bool empty() const
empty - Tests whether there are no bits in this bitvector.
Definition: BitVector.h:113
iterator insert(iterator where, const NodeTy &val)
Definition: ilist.h:664
bool operator==(const SparseBitVector &RHS) const
unsigned CountPopulation_64(uint64_t Value)
Definition: MathExtras.h:429
void reset(unsigned Idx)
iterator erase(iterator where)
Definition: ilist.h:465
bool operator==(const SparseBitVectorElement &RHS) const
bool intersectWith(const SparseBitVectorElement &RHS, bool &BecameZero)
unsigned CountPopulation_32(uint32_t Value)
Definition: MathExtras.h:417
void intersectWithComplement(const SparseBitVectorElement &RHS1, const SparseBitVectorElement &RHS2, bool &BecameZero)
BitWord word(unsigned Idx) const
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
Definition: ilist.h:385
bool intersectWithComplement(const SparseBitVector &RHS)
bool test_and_set(unsigned Idx)
bool intersects(const SparseBitVector< ElementSize > *RHS) const
int find_next(unsigned Curr) const
SparseBitVector(const SparseBitVector &RHS)
static NodeTy * createSentinel()
createSentinel - create the dynamic sentinel
Definition: ilist.h:78
iterator end()
Definition: ilist.h:367
SparseBitVectorIterator iterator
bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)
iterator end() const
bool intersects(const SparseBitVectorElement &RHS) const
void push_back(const NodeTy &val)
Definition: ilist.h:671
bool contains(const SparseBitVector< ElementSize > &RHS) const