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