Line data Source code
1 : //===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector --*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file defines the SparseBitVector class. See the doxygen comment for
11 : // SparseBitVector for more details on the algorithm used.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_ADT_SPARSEBITVECTOR_H
16 : #define LLVM_ADT_SPARSEBITVECTOR_H
17 :
18 : #include "llvm/Support/ErrorHandling.h"
19 : #include "llvm/Support/MathExtras.h"
20 : #include "llvm/Support/raw_ostream.h"
21 : #include <cassert>
22 : #include <climits>
23 : #include <cstring>
24 : #include <iterator>
25 : #include <list>
26 :
27 : namespace llvm {
28 :
29 : /// SparseBitVector is an implementation of a bitvector that is sparse by only
30 : /// storing the elements that have non-zero bits set. In order to make this
31 : /// fast for the most common cases, SparseBitVector is implemented as a linked
32 : /// list of SparseBitVectorElements. We maintain a pointer to the last
33 : /// SparseBitVectorElement accessed (in the form of a list iterator), in order
34 : /// to make multiple in-order test/set constant time after the first one is
35 : /// executed. Note that using vectors to store SparseBitVectorElement's does
36 : /// not work out very well because it causes insertion in the middle to take
37 : /// enormous amounts of time with a large amount of bits. Other structures that
38 : /// have better worst cases for insertion in the middle (various balanced trees,
39 : /// etc) do not perform as well in practice as a linked list with this iterator
40 : /// kept up to date. They are also significantly more memory intensive.
41 :
42 : template <unsigned ElementSize = 128> struct SparseBitVectorElement {
43 : public:
44 : using BitWord = unsigned long;
45 : using size_type = unsigned;
46 : enum {
47 : BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
48 : BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
49 : BITS_PER_ELEMENT = ElementSize
50 : };
51 :
52 : private:
53 : // Index of Element in terms of where first bit starts.
54 : unsigned ElementIndex;
55 : BitWord Bits[BITWORDS_PER_ELEMENT];
56 :
57 : SparseBitVectorElement() {
58 : ElementIndex = ~0U;
59 : memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
60 : }
61 :
62 : public:
63 0 : explicit SparseBitVectorElement(unsigned Idx) {
64 0 : ElementIndex = Idx;
65 0 : memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
66 : }
67 :
68 : // Comparison.
69 : bool operator==(const SparseBitVectorElement &RHS) const {
70 1 : if (ElementIndex != RHS.ElementIndex)
71 : return false;
72 3 : for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
73 2 : if (Bits[i] != RHS.Bits[i])
74 : return false;
75 : return true;
76 : }
77 :
78 : bool operator!=(const SparseBitVectorElement &RHS) const {
79 : 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 2160193 : return Bits[Idx];
86 : }
87 :
88 0 : unsigned index() const {
89 0 : return ElementIndex;
90 : }
91 :
92 : bool empty() const {
93 94711 : for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
94 78893 : if (Bits[i])
95 : return false;
96 : return true;
97 : }
98 :
99 : void set(unsigned Idx) {
100 2228105 : 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 60065 : Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
114 : }
115 :
116 : bool test(unsigned Idx) const {
117 2532645 : return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
118 : }
119 :
120 : size_type count() const {
121 : unsigned NumBits = 0;
122 411837 : for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
123 549116 : 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 2219427 : for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
130 2219427 : if (Bits[i] != 0)
131 1927132 : return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
132 0 : llvm_unreachable("Illegal empty element");
133 : }
134 :
135 : /// find_last - Returns the index of the last set bit.
136 : int find_last() const {
137 685 : for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; ++I) {
138 685 : unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
139 685 : if (Bits[Idx] != 0)
140 343 : return Idx * BITWORD_SIZE + BITWORD_SIZE -
141 343 : countLeadingZeros(Bits[Idx]) - 1;
142 : }
143 0 : llvm_unreachable("Illegal empty element");
144 : }
145 :
146 : /// find_next - Returns the index of the next set bit starting from the
147 : /// "Curr" bit. Returns -1 if the next set bit is not found.
148 2134293 : int find_next(unsigned Curr) const {
149 2134293 : if (Curr >= BITS_PER_ELEMENT)
150 : return -1;
151 :
152 2134293 : unsigned WordPos = Curr / BITWORD_SIZE;
153 2134293 : unsigned BitPos = Curr % BITWORD_SIZE;
154 2134293 : BitWord Copy = Bits[WordPos];
155 : assert(WordPos <= BITWORDS_PER_ELEMENT
156 : && "Word Position outside of element");
157 :
158 : // Mask off previous bits.
159 2134293 : Copy &= ~0UL << BitPos;
160 :
161 2134293 : if (Copy != 0)
162 92776 : return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
163 :
164 : // Check subsequent words.
165 3465250 : for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
166 1574898 : if (Bits[i] != 0)
167 395106 : 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 1090413 : for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
175 726942 : BitWord old = changed ? 0 : Bits[i];
176 :
177 726942 : Bits[i] |= RHS.Bits[i];
178 726942 : 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 0 : for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
187 0 : if (RHS.Bits[i] & Bits[i])
188 : return true;
189 : }
190 : return false;
191 : }
192 :
193 : // Intersect this Element with RHS and return true if this one changed.
194 : // BecameZero is set to true if this element became all-zero bits.
195 : bool intersectWith(const SparseBitVectorElement &RHS,
196 : bool &BecameZero) {
197 : bool changed = false;
198 : bool allzero = true;
199 :
200 : BecameZero = false;
201 119055 : for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
202 79370 : BitWord old = changed ? 0 : Bits[i];
203 :
204 79370 : Bits[i] &= RHS.Bits[i];
205 79370 : if (Bits[i] != 0)
206 : allzero = false;
207 :
208 79370 : 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 226785 : for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
225 151190 : BitWord old = changed ? 0 : Bits[i];
226 :
227 151190 : Bits[i] &= ~RHS.Bits[i];
228 151190 : if (Bits[i] != 0)
229 : allzero = false;
230 :
231 151190 : 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 6 : for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
247 4 : Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
248 4 : if (Bits[i] != 0)
249 : 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 : // 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 4591216 : ElementListIter FindLowerBound(unsigned ElementIndex) {
271 :
272 4591216 : if (Elements.empty()) {
273 0 : CurrElementIter = Elements.begin();
274 : return Elements.begin();
275 : }
276 :
277 : // Make sure our current iterator is valid.
278 4591216 : 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 4591216 : ElementListIter ElementIter = CurrElementIter;
284 4591216 : if (CurrElementIter->index() == ElementIndex) {
285 4418697 : return ElementIter;
286 172519 : } else if (CurrElementIter->index() > ElementIndex) {
287 : while (ElementIter != Elements.begin()
288 141116 : && ElementIter->index() > ElementIndex)
289 : --ElementIter;
290 : } else {
291 198582 : while (ElementIter != Elements.end() &&
292 158885 : ElementIter->index() < ElementIndex)
293 : ++ElementIter;
294 : }
295 172519 : CurrElementIter = ElementIter;
296 172519 : return ElementIter;
297 : }
298 :
299 : // Iterator to walk set bits in the bitmap. This iterator is a lot uglier
300 : // than it would be, in order to be efficient.
301 : class SparseBitVectorIterator {
302 : private:
303 : bool AtEnd;
304 :
305 : const SparseBitVector<ElementSize> *BitVector = nullptr;
306 :
307 : // Current element inside of bitmap.
308 : ElementListConstIter Iter;
309 :
310 : // Current bit number inside of our bitmap.
311 : unsigned BitNumber;
312 :
313 : // Current word number inside of our element.
314 : unsigned WordNumber;
315 :
316 : // Current bits from the element.
317 : typename SparseBitVectorElement<ElementSize>::BitWord Bits;
318 :
319 : // Move our iterator to the first non-zero bit in the bitmap.
320 21375190 : void AdvanceToFirstNonZero() {
321 21375190 : if (AtEnd)
322 : return;
323 21400358 : if (BitVector->Elements.empty()) {
324 8909414 : AtEnd = true;
325 8909414 : return;
326 : }
327 1790765 : Iter = BitVector->Elements.begin();
328 1790765 : BitNumber = Iter->index() * ElementSize;
329 : unsigned BitPos = Iter->find_first();
330 1790765 : BitNumber += BitPos;
331 1790765 : WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
332 : Bits = Iter->word(WordNumber);
333 1790765 : Bits >>= BitPos % BITWORD_SIZE;
334 : }
335 :
336 : // Move our iterator to the next non-zero bit.
337 8753124 : void AdvanceToNextNonZero() {
338 8753124 : if (AtEnd)
339 : return;
340 :
341 21361603 : while (Bits && !(Bits & 1)) {
342 12608479 : Bits >>= 1;
343 12608479 : BitNumber += 1;
344 : }
345 :
346 : // See if we ran out of Bits in this word.
347 8753124 : if (!Bits) {
348 2134293 : int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
349 : // If we ran out of set bits in this element, move to next element.
350 2134293 : if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
351 : ++Iter;
352 1901104 : WordNumber = 0;
353 :
354 : // We may run out of elements in the bitmap.
355 3802208 : if (Iter == BitVector->Elements.end()) {
356 1764865 : AtEnd = true;
357 1764865 : return;
358 : }
359 : // Set up for next non-zero word in bitmap.
360 136239 : BitNumber = Iter->index() * ElementSize;
361 : NextSetBitNumber = Iter->find_first();
362 136239 : BitNumber += NextSetBitNumber;
363 136239 : WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
364 : Bits = Iter->word(WordNumber);
365 136239 : Bits >>= NextSetBitNumber % BITWORD_SIZE;
366 : } else {
367 233189 : WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
368 : Bits = Iter->word(WordNumber);
369 233189 : Bits >>= NextSetBitNumber % BITWORD_SIZE;
370 233189 : BitNumber = Iter->index() * ElementSize;
371 233189 : BitNumber += NextSetBitNumber;
372 : }
373 : }
374 : }
375 :
376 : public:
377 4760 : SparseBitVectorIterator() = default;
378 :
379 5191432 : SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
380 2602020 : bool end = false):BitVector(RHS) {
381 5191432 : Iter = BitVector->Elements.begin();
382 5191432 : BitNumber = 0;
383 5191432 : Bits = 0;
384 5191432 : WordNumber = ~0;
385 5191432 : AtEnd = end;
386 2602020 : AdvanceToFirstNonZero();
387 : }
388 :
389 : // Preincrement.
390 : inline SparseBitVectorIterator& operator++() {
391 524686 : ++BitNumber;
392 524686 : Bits >>= 1;
393 524686 : 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 0 : unsigned operator*() const {
406 0 : return BitNumber;
407 : }
408 :
409 0 : bool operator==(const SparseBitVectorIterator &RHS) const {
410 : // If they are both at the end, ignore the rest of the fields.
411 2718434 : if (AtEnd && RHS.AtEnd)
412 0 : return true;
413 : // Otherwise they are the same if they have the same bit number and
414 : // bitmap.
415 659071 : return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
416 : }
417 :
418 : bool operator!=(const SparseBitVectorIterator &RHS) const {
419 3056330 : return !(*this == RHS);
420 : }
421 : };
422 :
423 : public:
424 : using iterator = SparseBitVectorIterator;
425 :
426 1501990 : SparseBitVector() {
427 1551818 : CurrElementIter = Elements.begin();
428 : }
429 :
430 : // SparseBitVector copy ctor.
431 10047590 : SparseBitVector(const SparseBitVector &RHS) {
432 5023795 : ElementListConstIter ElementIter = RHS.Elements.begin();
433 5228849 : while (ElementIter != RHS.Elements.end()) {
434 205054 : Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
435 : ++ElementIter;
436 : }
437 :
438 5023795 : CurrElementIter = Elements.begin ();
439 5023795 : }
440 :
441 2761510 : ~SparseBitVector() = default;
442 :
443 : // Clear.
444 : void clear() {
445 : Elements.clear();
446 : }
447 :
448 : // Assignment
449 1491190 : SparseBitVector& operator=(const SparseBitVector& RHS) {
450 1491190 : if (this == &RHS)
451 : return *this;
452 :
453 1491189 : Elements.clear();
454 :
455 1491189 : ElementListConstIter ElementIter = RHS.Elements.begin();
456 1651185 : while (ElementIter != RHS.Elements.end()) {
457 159996 : Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
458 : ++ElementIter;
459 : }
460 :
461 1491189 : CurrElementIter = Elements.begin ();
462 :
463 1491189 : return *this;
464 : }
465 :
466 : // Test, Reset, and Set a bit in the bitmap.
467 3844270 : bool test(unsigned Idx) {
468 3844270 : if (Elements.empty())
469 : return false;
470 :
471 2576735 : unsigned ElementIndex = Idx / ElementSize;
472 2576735 : 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 2576735 : if (ElementIter == Elements.end() ||
477 2551061 : ElementIter->index() != ElementIndex)
478 : return false;
479 2532645 : return ElementIter->test(Idx % ElementSize);
480 : }
481 :
482 283729 : void reset(unsigned Idx) {
483 283729 : if (Elements.empty())
484 : return;
485 :
486 60065 : unsigned ElementIndex = Idx / ElementSize;
487 60065 : 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 60065 : if (ElementIter == Elements.end() ||
492 60065 : ElementIter->index() != ElementIndex)
493 : return;
494 60065 : ElementIter->reset(Idx % ElementSize);
495 :
496 : // When the element is zeroed out, delete it.
497 60065 : if (ElementIter->empty()) {
498 : ++CurrElementIter;
499 : Elements.erase(ElementIter);
500 : }
501 : }
502 :
503 2228105 : void set(unsigned Idx) {
504 2228105 : unsigned ElementIndex = Idx / ElementSize;
505 : ElementListIter ElementIter;
506 2228105 : if (Elements.empty()) {
507 : ElementIter = Elements.emplace(Elements.end(), ElementIndex);
508 : } else {
509 1954416 : ElementIter = FindLowerBound(ElementIndex);
510 :
511 1954416 : if (ElementIter == Elements.end() ||
512 1940393 : 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 24336 : if (ElementIter != Elements.end() &&
517 10313 : ElementIter->index() < ElementIndex)
518 : ++ElementIter;
519 : ElementIter = Elements.emplace(ElementIter, ElementIndex);
520 : }
521 : }
522 2228105 : CurrElementIter = ElementIter;
523 :
524 2228105 : ElementIter->set(Idx % ElementSize);
525 2228105 : }
526 :
527 2 : bool test_and_set(unsigned Idx) {
528 2 : bool old = test(Idx);
529 2 : if (!old) {
530 1 : set(Idx);
531 1 : return true;
532 : }
533 : return false;
534 : }
535 :
536 : bool operator!=(const SparseBitVector &RHS) const {
537 : return !(*this == RHS);
538 : }
539 :
540 2 : bool operator==(const SparseBitVector &RHS) const {
541 2 : ElementListConstIter Iter1 = Elements.begin();
542 2 : ElementListConstIter Iter2 = RHS.Elements.begin();
543 :
544 3 : for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
545 : ++Iter1, ++Iter2) {
546 1 : if (*Iter1 != *Iter2)
547 : return false;
548 : }
549 2 : return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
550 : }
551 :
552 : // Union our bitmap with the RHS and return true if we changed.
553 435539 : bool operator|=(const SparseBitVector &RHS) {
554 435539 : if (this == &RHS)
555 : return false;
556 :
557 : bool changed = false;
558 435538 : ElementListIter Iter1 = Elements.begin();
559 435538 : ElementListConstIter Iter2 = RHS.Elements.begin();
560 :
561 : // If RHS is empty, we are done
562 435538 : if (RHS.Elements.empty())
563 : return false;
564 :
565 894115 : while (Iter2 != RHS.Elements.end()) {
566 458577 : if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
567 158792 : Elements.insert(Iter1, *Iter2);
568 : ++Iter2;
569 : changed = true;
570 379181 : } else if (Iter1->index() == Iter2->index()) {
571 363471 : changed |= Iter1->unionWith(*Iter2);
572 : ++Iter1;
573 : ++Iter2;
574 : } else {
575 : ++Iter1;
576 : }
577 : }
578 435538 : CurrElementIter = Elements.begin();
579 435538 : return changed;
580 : }
581 :
582 : // Intersect our bitmap with the RHS and return true if ours changed.
583 37528 : bool operator&=(const SparseBitVector &RHS) {
584 37528 : if (this == &RHS)
585 : return false;
586 :
587 : bool changed = false;
588 37527 : ElementListIter Iter1 = Elements.begin();
589 37527 : ElementListConstIter Iter2 = RHS.Elements.begin();
590 :
591 : // Check if both bitmaps are empty.
592 37527 : if (Elements.empty() && RHS.Elements.empty())
593 : return false;
594 :
595 : // Loop through, intersecting as we go, erasing elements when necessary.
596 77469 : while (Iter2 != RHS.Elements.end()) {
597 42462 : if (Iter1 == Elements.end()) {
598 2520 : CurrElementIter = Elements.begin();
599 2520 : return changed;
600 : }
601 :
602 39942 : if (Iter1->index() > Iter2->index()) {
603 : ++Iter2;
604 39808 : } else if (Iter1->index() == Iter2->index()) {
605 : bool BecameZero;
606 39685 : changed |= Iter1->intersectWith(*Iter2, BecameZero);
607 39685 : 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 35007 : if (Iter1 != Elements.end()) {
623 1602 : Elements.erase(Iter1, Elements.end());
624 : changed = true;
625 : }
626 35007 : CurrElementIter = Elements.begin();
627 35007 : return changed;
628 : }
629 :
630 : // Intersect our bitmap with the complement of the RHS and return true
631 : // if ours changed.
632 2377462 : bool intersectWithComplement(const SparseBitVector &RHS) {
633 2377462 : if (this == &RHS) {
634 3 : if (!empty()) {
635 : clear();
636 2 : return true;
637 : }
638 : return false;
639 : }
640 :
641 : bool changed = false;
642 2377459 : ElementListIter Iter1 = Elements.begin();
643 2377459 : ElementListConstIter Iter2 = RHS.Elements.begin();
644 :
645 : // If either our bitmap or RHS is empty, we are done
646 2377459 : if (Elements.empty() || RHS.Elements.empty())
647 : return false;
648 :
649 : // Loop through, intersecting as we go, erasing elements when necessary.
650 149598 : while (Iter2 != RHS.Elements.end()) {
651 78410 : if (Iter1 == Elements.end()) {
652 37 : CurrElementIter = Elements.begin();
653 37 : return changed;
654 : }
655 :
656 78373 : if (Iter1->index() > Iter2->index()) {
657 : ++Iter2;
658 78368 : } else if (Iter1->index() == Iter2->index()) {
659 : bool BecameZero;
660 75595 : changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
661 75595 : 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 71188 : CurrElementIter = Elements.begin();
674 71188 : return changed;
675 : }
676 :
677 : bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
678 : return intersectWithComplement(*RHS);
679 : }
680 :
681 : // Three argument version of intersectWithComplement.
682 : // Result of RHS1 & ~RHS2 is stored into this bitmap.
683 5 : void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
684 : const SparseBitVector<ElementSize> &RHS2)
685 : {
686 5 : if (this == &RHS1) {
687 2 : intersectWithComplement(RHS2);
688 2 : return;
689 3 : } else if (this == &RHS2) {
690 1 : SparseBitVector RHS2Copy(RHS2);
691 1 : intersectWithComplement(RHS1, RHS2Copy);
692 : return;
693 : }
694 :
695 2 : Elements.clear();
696 2 : CurrElementIter = Elements.begin();
697 2 : ElementListConstIter Iter1 = RHS1.Elements.begin();
698 2 : 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 2 : if (RHS1.Elements.empty())
703 : return;
704 :
705 : // Loop through, intersecting as we go, erasing elements when necessary.
706 4 : while (Iter2 != RHS2.Elements.end()) {
707 2 : if (Iter1 == RHS1.Elements.end())
708 : return;
709 :
710 2 : if (Iter1->index() > Iter2->index()) {
711 : ++Iter2;
712 2 : } else if (Iter1->index() == Iter2->index()) {
713 : bool BecameZero = false;
714 2 : Elements.emplace_back(Iter1->index());
715 : Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
716 2 : if (BecameZero)
717 1 : 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 :
729 : void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
730 : const SparseBitVector<ElementSize> *RHS2) {
731 : intersectWithComplement(*RHS1, *RHS2);
732 : }
733 :
734 : bool intersects(const SparseBitVector<ElementSize> *RHS) const {
735 : return intersects(*RHS);
736 : }
737 :
738 : // Return true if we share any bits in common with RHS
739 88 : bool intersects(const SparseBitVector<ElementSize> &RHS) const {
740 88 : ElementListConstIter Iter1 = Elements.begin();
741 88 : ElementListConstIter Iter2 = RHS.Elements.begin();
742 :
743 : // Check if both bitmaps are empty.
744 88 : if (Elements.empty() && RHS.Elements.empty())
745 : return false;
746 :
747 : // Loop through, intersecting stopping when we hit bits in common.
748 88 : while (Iter2 != RHS.Elements.end()) {
749 0 : if (Iter1 == Elements.end())
750 : return false;
751 :
752 0 : if (Iter1->index() > Iter2->index()) {
753 : ++Iter2;
754 0 : } else if (Iter1->index() == Iter2->index()) {
755 0 : if (Iter1->intersects(*Iter2))
756 : return true;
757 : ++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 132 : if (Elements.empty())
777 : return -1;
778 : const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
779 256 : 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 680 : int find_last() const {
784 680 : if (Elements.empty())
785 : return -1;
786 : const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
787 686 : 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 132350 : for (ElementListConstIter Iter = Elements.begin();
798 269629 : Iter != Elements.end();
799 : ++Iter)
800 137279 : 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>
818 : inline bool operator |=(SparseBitVector<ElementSize> &LHS,
819 : const SparseBitVector<ElementSize> *RHS) {
820 : return LHS |= *RHS;
821 : }
822 :
823 : template <unsigned ElementSize>
824 : inline bool operator |=(SparseBitVector<ElementSize> *LHS,
825 : const SparseBitVector<ElementSize> &RHS) {
826 : return LHS->operator|=(RHS);
827 : }
828 :
829 : template <unsigned ElementSize>
830 : inline bool operator &=(SparseBitVector<ElementSize> *LHS,
831 : const SparseBitVector<ElementSize> &RHS) {
832 : return LHS->operator&=(RHS);
833 : }
834 :
835 : template <unsigned ElementSize>
836 : inline bool operator &=(SparseBitVector<ElementSize> &LHS,
837 : const SparseBitVector<ElementSize> *RHS) {
838 : return LHS &= *RHS;
839 : }
840 :
841 : // Convenience functions for infix union, intersection, difference operators.
842 :
843 : template <unsigned ElementSize>
844 : inline SparseBitVector<ElementSize>
845 : operator|(const SparseBitVector<ElementSize> &LHS,
846 : const SparseBitVector<ElementSize> &RHS) {
847 : SparseBitVector<ElementSize> Result(LHS);
848 : Result |= RHS;
849 : return Result;
850 : }
851 :
852 : template <unsigned ElementSize>
853 : inline SparseBitVector<ElementSize>
854 : operator&(const SparseBitVector<ElementSize> &LHS,
855 : const SparseBitVector<ElementSize> &RHS) {
856 : SparseBitVector<ElementSize> Result(LHS);
857 : Result &= RHS;
858 : return Result;
859 : }
860 :
861 : template <unsigned ElementSize>
862 : inline SparseBitVector<ElementSize>
863 : operator-(const SparseBitVector<ElementSize> &LHS,
864 : const SparseBitVector<ElementSize> &RHS) {
865 : SparseBitVector<ElementSize> Result;
866 : Result.intersectWithComplement(LHS, RHS);
867 : return Result;
868 : }
869 :
870 : // Dump a SparseBitVector to a stream
871 : template <unsigned ElementSize>
872 : void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
873 : out << "[";
874 :
875 : typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
876 : be = LHS.end();
877 : if (bi != be) {
878 : out << *bi;
879 : for (++bi; bi != be; ++bi) {
880 : out << " " << *bi;
881 : }
882 : }
883 : out << "]\n";
884 : }
885 :
886 : } // end namespace llvm
887 :
888 : #endif // LLVM_ADT_SPARSEBITVECTOR_H
|
