/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/ADT/SparseBitVector.h
Line | Count | Source (jump to first uncovered line) |
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 | 2.71M | explicit SparseBitVectorElement(unsigned Idx) { |
64 | 2.71M | ElementIndex = Idx; |
65 | 2.71M | memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); |
66 | 2.71M | } |
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 | 508k | BitWord word(unsigned Idx) const { |
84 | 508k | assert(Idx < BITWORDS_PER_ELEMENT); |
85 | 508k | return Bits[Idx]; |
86 | 508k | } |
87 | | |
88 | 199M | unsigned index() const { |
89 | 199M | return ElementIndex; |
90 | 199M | } |
91 | | |
92 | 490k | bool empty() const { |
93 | 896k | for (unsigned i = 0; i < BITWORDS_PER_ELEMENT896k ; ++i405k ) |
94 | 705k | if (705k Bits[i]705k ) |
95 | 299k | return false; |
96 | 191k | return true; |
97 | 490k | } |
98 | | |
99 | 33.3M | void set(unsigned Idx) { |
100 | 33.3M | Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE); |
101 | 33.3M | } |
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 | 490k | void reset(unsigned Idx) { |
113 | 490k | Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE)); |
114 | 490k | } |
115 | | |
116 | 54.0M | bool test(unsigned Idx) const { |
117 | 54.0M | return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE)); |
118 | 54.0M | } |
119 | | |
120 | 64.6k | size_type count() const { |
121 | 64.6k | unsigned NumBits = 0; |
122 | 194k | for (unsigned i = 0; i < BITWORDS_PER_ELEMENT194k ; ++i129k ) |
123 | 129k | NumBits += countPopulation(Bits[i]); |
124 | 64.6k | return NumBits; |
125 | 64.6k | } |
126 | | |
127 | | /// find_first - Returns the index of the first set bit. |
128 | 454k | int find_first() const { |
129 | 534k | for (unsigned i = 0; i < BITWORDS_PER_ELEMENT534k ; ++i79.9k ) |
130 | 534k | if (534k Bits[i] != 0534k ) |
131 | 454k | return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); |
132 | 0 | llvm_unreachable0 ("Illegal empty element"); |
133 | 454k | } |
134 | | |
135 | | /// find_last - Returns the index of the last set bit. |
136 | 128 | int find_last() const { |
137 | 255 | for (unsigned I = 0; I < BITWORDS_PER_ELEMENT255 ; ++I127 ) { |
138 | 255 | unsigned Idx = BITWORDS_PER_ELEMENT - I - 1; |
139 | 255 | if (Bits[Idx] != 0) |
140 | 128 | return Idx * BITWORD_SIZE + BITWORD_SIZE - |
141 | 128 | countLeadingZeros(Bits[Idx]) - 1; |
142 | 255 | } |
143 | 0 | llvm_unreachable0 ("Illegal empty element"); |
144 | 128 | } |
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 | 485k | int find_next(unsigned Curr) const { |
149 | 485k | if (Curr >= BITS_PER_ELEMENT) |
150 | 0 | return -1; |
151 | 485k | |
152 | 485k | unsigned WordPos = Curr / BITWORD_SIZE; |
153 | 485k | unsigned BitPos = Curr % BITWORD_SIZE; |
154 | 485k | BitWord Copy = Bits[WordPos]; |
155 | 485k | assert(WordPos <= BITWORDS_PER_ELEMENT |
156 | 485k | && "Word Position outside of element"); |
157 | 485k | |
158 | 485k | // Mask off previous bits. |
159 | 485k | Copy &= ~0UL << BitPos; |
160 | 485k | |
161 | 485k | if (Copy != 0) |
162 | 10.5k | return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); |
163 | 485k | |
164 | 485k | // Check subsequent words. |
165 | 778k | for (unsigned i = WordPos+1; 474k i < BITWORDS_PER_ELEMENT778k ; ++i304k ) |
166 | 352k | if (352k Bits[i] != 0352k ) |
167 | 47.9k | return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); |
168 | 426k | return -1; |
169 | 485k | } |
170 | | |
171 | | // Union this element with RHS and return true if this one changed. |
172 | 311k | bool unionWith(const SparseBitVectorElement &RHS) { |
173 | 311k | bool changed = false; |
174 | 935k | for (unsigned i = 0; i < BITWORDS_PER_ELEMENT935k ; ++i623k ) { |
175 | 623k | BitWord old = changed ? 039.7k : Bits[i]583k ; |
176 | 623k | |
177 | 623k | Bits[i] |= RHS.Bits[i]; |
178 | 623k | if (!changed && 623k old != Bits[i]583k ) |
179 | 67.4k | changed = true; |
180 | 623k | } |
181 | 311k | return changed; |
182 | 311k | } |
183 | | |
184 | | // Return true if we have any bits in common with RHS |
185 | 0 | bool intersects(const SparseBitVectorElement &RHS) const { |
186 | 0 | for (unsigned i = 0; i < BITWORDS_PER_ELEMENT0 ; ++i0 ) { |
187 | 0 | if (RHS.Bits[i] & Bits[i]) |
188 | 0 | return true; |
189 | 0 | } |
190 | 0 | return false; |
191 | 0 | } |
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 | 244 | bool &BecameZero) { |
197 | 244 | bool changed = false; |
198 | 244 | bool allzero = true; |
199 | 244 | |
200 | 244 | BecameZero = false; |
201 | 732 | for (unsigned i = 0; i < BITWORDS_PER_ELEMENT732 ; ++i488 ) { |
202 | 488 | BitWord old = changed ? 056 : Bits[i]432 ; |
203 | 488 | |
204 | 488 | Bits[i] &= RHS.Bits[i]; |
205 | 488 | if (Bits[i] != 0) |
206 | 231 | allzero = false; |
207 | 488 | |
208 | 488 | if (!changed && 488 old != Bits[i]432 ) |
209 | 56 | changed = true; |
210 | 488 | } |
211 | 244 | BecameZero = allzero; |
212 | 244 | return changed; |
213 | 244 | } |
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 | 581 | bool &BecameZero) { |
220 | 581 | bool changed = false; |
221 | 581 | bool allzero = true; |
222 | 581 | |
223 | 581 | BecameZero = false; |
224 | 1.74k | for (unsigned i = 0; i < BITWORDS_PER_ELEMENT1.74k ; ++i1.16k ) { |
225 | 1.16k | BitWord old = changed ? 0580 : Bits[i]582 ; |
226 | 1.16k | |
227 | 1.16k | Bits[i] &= ~RHS.Bits[i]; |
228 | 1.16k | if (Bits[i] != 0) |
229 | 144 | allzero = false; |
230 | 1.16k | |
231 | 1.16k | if (!changed && 1.16k old != Bits[i]582 ) |
232 | 580 | changed = true; |
233 | 1.16k | } |
234 | 581 | BecameZero = allzero; |
235 | 581 | return changed; |
236 | 581 | } |
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 | | // 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 | 90.3M | ElementListIter FindLowerBound(unsigned ElementIndex) { |
271 | 90.3M | |
272 | 90.3M | if (Elements.empty()90.3M ) { |
273 | 0 | CurrElementIter = Elements.begin(); |
274 | 0 | return Elements.begin(); |
275 | 0 | } |
276 | 90.3M | |
277 | 90.3M | // Make sure our current iterator is valid. |
278 | 90.3M | if (90.3M CurrElementIter == Elements.end()90.3M ) |
279 | 1.84M | --CurrElementIter; |
280 | 90.3M | |
281 | 90.3M | // Search from our current iterator, either backwards or forwards, |
282 | 90.3M | // depending on what element we are looking for. |
283 | 90.3M | ElementListIter ElementIter = CurrElementIter; |
284 | 90.3M | if (CurrElementIter->index() == ElementIndex90.3M ) { |
285 | 82.4M | return ElementIter; |
286 | 90.3M | } else if (7.89M CurrElementIter->index() > ElementIndex7.89M ) { |
287 | 7.74M | while (ElementIter != Elements.begin() |
288 | 4.02M | && ElementIter->index() > ElementIndex) |
289 | 3.52M | --ElementIter; |
290 | 7.89M | } else { |
291 | 9.22M | while (ElementIter != Elements.end() && |
292 | 7.13M | ElementIter->index() < ElementIndex) |
293 | 5.55M | ++ElementIter; |
294 | 7.89M | } |
295 | 7.89M | CurrElementIter = ElementIter; |
296 | 7.89M | return ElementIter; |
297 | 90.3M | } |
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 | 5.81M | void AdvanceToFirstNonZero() { |
321 | 5.81M | if (AtEnd) |
322 | 2.89M | return; |
323 | 2.92M | if (2.92M BitVector->Elements.empty()2.92M ) { |
324 | 2.57M | AtEnd = true; |
325 | 2.57M | return; |
326 | 2.57M | } |
327 | 341k | Iter = BitVector->Elements.begin(); |
328 | 341k | BitNumber = Iter->index() * ElementSize; |
329 | 341k | unsigned BitPos = Iter->find_first(); |
330 | 341k | BitNumber += BitPos; |
331 | 341k | WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; |
332 | 341k | Bits = Iter->word(WordNumber); |
333 | 341k | Bits >>= BitPos % BITWORD_SIZE; |
334 | 341k | } |
335 | | |
336 | | // Move our iterator to the next non-zero bit. |
337 | 1.43M | void AdvanceToNextNonZero() { |
338 | 1.43M | if (AtEnd) |
339 | 0 | return; |
340 | 1.43M | |
341 | 4.96M | while (1.43M Bits && 4.96M !(Bits & 1)4.47M ) { |
342 | 3.53M | Bits >>= 1; |
343 | 3.53M | BitNumber += 1; |
344 | 3.53M | } |
345 | 1.43M | |
346 | 1.43M | // See if we ran out of Bits in this word. |
347 | 1.43M | if (!Bits1.43M ) { |
348 | 485k | int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ; |
349 | 485k | // If we ran out of set bits in this element, move to next element. |
350 | 485k | if (NextSetBitNumber == -1 || 485k (BitNumber % ElementSize == 0)58.4k ) { |
351 | 430k | ++Iter; |
352 | 430k | WordNumber = 0; |
353 | 430k | |
354 | 430k | // We may run out of elements in the bitmap. |
355 | 430k | if (Iter == BitVector->Elements.end()430k ) { |
356 | 318k | AtEnd = true; |
357 | 318k | return; |
358 | 318k | } |
359 | 430k | // Set up for next non-zero word in bitmap. |
360 | 112k | BitNumber = Iter->index() * ElementSize; |
361 | 112k | NextSetBitNumber = Iter->find_first(); |
362 | 112k | BitNumber += NextSetBitNumber; |
363 | 112k | WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE; |
364 | 112k | Bits = Iter->word(WordNumber); |
365 | 112k | Bits >>= NextSetBitNumber % BITWORD_SIZE; |
366 | 485k | } else { |
367 | 54.5k | WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE; |
368 | 54.5k | Bits = Iter->word(WordNumber); |
369 | 54.5k | Bits >>= NextSetBitNumber % BITWORD_SIZE; |
370 | 54.5k | BitNumber = Iter->index() * ElementSize; |
371 | 54.5k | BitNumber += NextSetBitNumber; |
372 | 54.5k | } |
373 | 485k | } |
374 | 1.43M | } |
375 | | |
376 | | public: |
377 | | SparseBitVectorIterator() = default; |
378 | | |
379 | | SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS, |
380 | 5.81M | bool end = false):BitVector(RHS) { |
381 | 5.81M | Iter = BitVector->Elements.begin(); |
382 | 5.81M | BitNumber = 0; |
383 | 5.81M | Bits = 0; |
384 | 5.81M | WordNumber = ~0; |
385 | 5.81M | AtEnd = end; |
386 | 5.81M | AdvanceToFirstNonZero(); |
387 | 5.81M | } |
388 | | |
389 | | // Preincrement. |
390 | 1.43M | inline SparseBitVectorIterator& operator++() { |
391 | 1.43M | ++BitNumber; |
392 | 1.43M | Bits >>= 1; |
393 | 1.43M | AdvanceToNextNonZero(); |
394 | 1.43M | return *this; |
395 | 1.43M | } |
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 | 1.45M | unsigned operator*() const { |
406 | 1.45M | return BitNumber; |
407 | 1.45M | } |
408 | | |
409 | 4.45M | bool operator==(const SparseBitVectorIterator &RHS) const { |
410 | 4.45M | // If they are both at the end, ignore the rest of the fields. |
411 | 4.45M | if (AtEnd && 4.45M RHS.AtEnd2.90M ) |
412 | 2.90M | return true; |
413 | 4.45M | // Otherwise they are the same if they have the same bit number and |
414 | 4.45M | // bitmap. |
415 | 1.55M | return AtEnd == RHS.AtEnd && 1.55M RHS.BitNumber == BitNumber0 ; |
416 | 4.45M | } |
417 | | |
418 | 4.27M | bool operator!=(const SparseBitVectorIterator &RHS) const { |
419 | 4.27M | return !(*this == RHS); |
420 | 4.27M | } |
421 | | }; |
422 | | |
423 | | public: |
424 | | using iterator = SparseBitVectorIterator; |
425 | | |
426 | 755k | SparseBitVector() { |
427 | 755k | CurrElementIter = Elements.begin(); |
428 | 755k | } |
429 | | |
430 | | // SparseBitVector copy ctor. |
431 | 28.5M | SparseBitVector(const SparseBitVector &RHS) { |
432 | 28.5M | ElementListConstIter ElementIter = RHS.Elements.begin(); |
433 | 28.9M | while (ElementIter != RHS.Elements.end()28.9M ) { |
434 | 434k | Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); |
435 | 434k | ++ElementIter; |
436 | 434k | } |
437 | 28.5M | |
438 | 28.5M | CurrElementIter = Elements.begin (); |
439 | 28.5M | } |
440 | | |
441 | 29.2M | ~SparseBitVector() = default; |
442 | | |
443 | | // Clear. |
444 | 1.18M | void clear() { |
445 | 1.18M | Elements.clear(); |
446 | 1.18M | } |
447 | | |
448 | | // Assignment |
449 | 39.3k | SparseBitVector& operator=(const SparseBitVector& RHS) { |
450 | 39.3k | if (this == &RHS) |
451 | 1 | return *this; |
452 | 39.3k | |
453 | 39.3k | Elements.clear(); |
454 | 39.3k | |
455 | 39.3k | ElementListConstIter ElementIter = RHS.Elements.begin(); |
456 | 82.7k | while (ElementIter != RHS.Elements.end()82.7k ) { |
457 | 43.3k | Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter)); |
458 | 43.3k | ++ElementIter; |
459 | 43.3k | } |
460 | 39.3k | |
461 | 39.3k | CurrElementIter = Elements.begin (); |
462 | 39.3k | |
463 | 39.3k | return *this; |
464 | 39.3k | } |
465 | | |
466 | | // Test, Reset, and Set a bit in the bitmap. |
467 | 158M | bool test(unsigned Idx) { |
468 | 158M | if (Elements.empty()) |
469 | 99.3M | return false; |
470 | 158M | |
471 | 58.9M | unsigned ElementIndex = Idx / ElementSize; |
472 | 58.9M | ElementListIter ElementIter = FindLowerBound(ElementIndex); |
473 | 58.9M | |
474 | 58.9M | // If we can't find an element that is supposed to contain this bit, there |
475 | 58.9M | // is nothing more to do. |
476 | 58.9M | if (ElementIter == Elements.end() || |
477 | 57.0M | ElementIter->index() != ElementIndex) |
478 | 4.84M | return false; |
479 | 54.0M | return ElementIter->test(Idx % ElementSize); |
480 | 158M | } |
481 | | |
482 | 2.12M | void reset(unsigned Idx) { |
483 | 2.12M | if (Elements.empty()) |
484 | 1.62M | return; |
485 | 2.12M | |
486 | 490k | unsigned ElementIndex = Idx / ElementSize; |
487 | 490k | ElementListIter ElementIter = FindLowerBound(ElementIndex); |
488 | 490k | |
489 | 490k | // If we can't find an element that is supposed to contain this bit, there |
490 | 490k | // is nothing more to do. |
491 | 490k | if (ElementIter == Elements.end() || |
492 | 490k | ElementIter->index() != ElementIndex) |
493 | 0 | return; |
494 | 490k | ElementIter->reset(Idx % ElementSize); |
495 | 490k | |
496 | 490k | // When the element is zeroed out, delete it. |
497 | 490k | if (ElementIter->empty()490k ) { |
498 | 191k | ++CurrElementIter; |
499 | 191k | Elements.erase(ElementIter); |
500 | 191k | } |
501 | 2.12M | } |
502 | | |
503 | 33.3M | void set(unsigned Idx) { |
504 | 33.3M | unsigned ElementIndex = Idx / ElementSize; |
505 | 33.3M | ElementListIter ElementIter; |
506 | 33.3M | if (Elements.empty()33.3M ) { |
507 | 2.41M | ElementIter = Elements.emplace(Elements.end(), ElementIndex); |
508 | 33.3M | } else { |
509 | 30.9M | ElementIter = FindLowerBound(ElementIndex); |
510 | 30.9M | |
511 | 30.9M | if (ElementIter == Elements.end() || |
512 | 30.9M | ElementIter->index() != ElementIndex30.7M ) { |
513 | 302k | // We may have hit the beginning of our SparseBitVector, in which case, |
514 | 302k | // we may need to insert right after this element, which requires moving |
515 | 302k | // the current iterator forward one, because insert does insert before. |
516 | 302k | if (ElementIter != Elements.end() && |
517 | 101k | ElementIter->index() < ElementIndex) |
518 | 5.39k | ++ElementIter; |
519 | 302k | ElementIter = Elements.emplace(ElementIter, ElementIndex); |
520 | 302k | } |
521 | 30.9M | } |
522 | 33.3M | CurrElementIter = ElementIter; |
523 | 33.3M | |
524 | 33.3M | ElementIter->set(Idx % ElementSize); |
525 | 33.3M | } |
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 | 341k | bool operator|=(const SparseBitVector &RHS) { |
554 | 341k | if (this == &RHS) |
555 | 1 | return false; |
556 | 341k | |
557 | 341k | bool changed = false; |
558 | 341k | ElementListIter Iter1 = Elements.begin(); |
559 | 341k | ElementListConstIter Iter2 = RHS.Elements.begin(); |
560 | 341k | |
561 | 341k | // If RHS is empty, we are done |
562 | 341k | if (RHS.Elements.empty()) |
563 | 0 | return false; |
564 | 341k | |
565 | 703k | while (341k Iter2 != RHS.Elements.end()703k ) { |
566 | 361k | if (Iter1 == Elements.end() || 361k Iter1->index() > Iter2->index()330k ) { |
567 | 32.5k | Elements.insert(Iter1, *Iter2); |
568 | 32.5k | ++Iter2; |
569 | 32.5k | changed = true; |
570 | 361k | } else if (328k Iter1->index() == Iter2->index()328k ) { |
571 | 311k | changed |= Iter1->unionWith(*Iter2); |
572 | 311k | ++Iter1; |
573 | 311k | ++Iter2; |
574 | 328k | } else { |
575 | 17.1k | ++Iter1; |
576 | 17.1k | } |
577 | 361k | } |
578 | 341k | CurrElementIter = Elements.begin(); |
579 | 341k | return changed; |
580 | 341k | } |
581 | | |
582 | | // Intersect our bitmap with the RHS and return true if ours changed. |
583 | 247 | bool operator&=(const SparseBitVector &RHS) { |
584 | 247 | if (this == &RHS) |
585 | 1 | return false; |
586 | 247 | |
587 | 246 | bool changed = false; |
588 | 246 | ElementListIter Iter1 = Elements.begin(); |
589 | 246 | ElementListConstIter Iter2 = RHS.Elements.begin(); |
590 | 246 | |
591 | 246 | // Check if both bitmaps are empty. |
592 | 246 | if (Elements.empty() && 246 RHS.Elements.empty()0 ) |
593 | 0 | return false; |
594 | 246 | |
595 | 246 | // Loop through, intersecting as we go, erasing elements when necessary. |
596 | 507 | while (246 Iter2 != RHS.Elements.end()507 ) { |
597 | 262 | if (Iter1 == Elements.end()262 ) { |
598 | 1 | CurrElementIter = Elements.begin(); |
599 | 1 | return changed; |
600 | 1 | } |
601 | 262 | |
602 | 261 | if (261 Iter1->index() > Iter2->index()261 ) { |
603 | 1 | ++Iter2; |
604 | 261 | } else if (260 Iter1->index() == Iter2->index()260 ) { |
605 | 244 | bool BecameZero; |
606 | 244 | changed |= Iter1->intersectWith(*Iter2, BecameZero); |
607 | 244 | if (BecameZero244 ) { |
608 | 13 | ElementListIter IterTmp = Iter1; |
609 | 13 | ++Iter1; |
610 | 13 | Elements.erase(IterTmp); |
611 | 244 | } else { |
612 | 231 | ++Iter1; |
613 | 231 | } |
614 | 244 | ++Iter2; |
615 | 260 | } else { |
616 | 16 | ElementListIter IterTmp = Iter1; |
617 | 16 | ++Iter1; |
618 | 16 | Elements.erase(IterTmp); |
619 | 16 | changed = true; |
620 | 16 | } |
621 | 262 | } |
622 | 245 | if (245 Iter1 != Elements.end()245 ) { |
623 | 1 | Elements.erase(Iter1, Elements.end()); |
624 | 1 | changed = true; |
625 | 1 | } |
626 | 245 | CurrElementIter = Elements.begin(); |
627 | 245 | return changed; |
628 | 247 | } |
629 | | |
630 | | // Intersect our bitmap with the complement of the RHS and return true |
631 | | // if ours changed. |
632 | 489k | bool intersectWithComplement(const SparseBitVector &RHS) { |
633 | 489k | if (this == &RHS489k ) { |
634 | 3 | if (!empty()3 ) { |
635 | 2 | clear(); |
636 | 2 | return true; |
637 | 2 | } |
638 | 1 | return false; |
639 | 3 | } |
640 | 489k | |
641 | 489k | bool changed = false; |
642 | 489k | ElementListIter Iter1 = Elements.begin(); |
643 | 489k | ElementListConstIter Iter2 = RHS.Elements.begin(); |
644 | 489k | |
645 | 489k | // If either our bitmap or RHS is empty, we are done |
646 | 489k | if (Elements.empty() || 489k RHS.Elements.empty()6.11k ) |
647 | 488k | return false; |
648 | 489k | |
649 | 489k | // Loop through, intersecting as we go, erasing elements when necessary. |
650 | 1.16k | while (580 Iter2 != RHS.Elements.end()1.16k ) { |
651 | 581 | if (Iter1 == Elements.end()581 ) { |
652 | 0 | CurrElementIter = Elements.begin(); |
653 | 0 | return changed; |
654 | 0 | } |
655 | 581 | |
656 | 581 | if (581 Iter1->index() > Iter2->index()581 ) { |
657 | 0 | ++Iter2; |
658 | 581 | } else if (581 Iter1->index() == Iter2->index()581 ) { |
659 | 581 | bool BecameZero; |
660 | 581 | changed |= Iter1->intersectWithComplement(*Iter2, BecameZero); |
661 | 581 | if (BecameZero581 ) { |
662 | 437 | ElementListIter IterTmp = Iter1; |
663 | 437 | ++Iter1; |
664 | 437 | Elements.erase(IterTmp); |
665 | 581 | } else { |
666 | 144 | ++Iter1; |
667 | 144 | } |
668 | 581 | ++Iter2; |
669 | 0 | } else { |
670 | 0 | ++Iter1; |
671 | 0 | } |
672 | 581 | } |
673 | 580 | CurrElementIter = Elements.begin(); |
674 | 580 | return changed; |
675 | 489k | } |
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 | | void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1, |
684 | | const SparseBitVector<ElementSize> &RHS2) |
685 | | { |
686 | | if (this == &RHS1) { |
687 | | intersectWithComplement(RHS2); |
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 | | |
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 | 69 | bool intersects(const SparseBitVector<ElementSize> &RHS) const { |
740 | 69 | ElementListConstIter Iter1 = Elements.begin(); |
741 | 69 | ElementListConstIter Iter2 = RHS.Elements.begin(); |
742 | 69 | |
743 | 69 | // Check if both bitmaps are empty. |
744 | 69 | if (Elements.empty() && 69 RHS.Elements.empty()0 ) |
745 | 0 | return false; |
746 | 69 | |
747 | 69 | // Loop through, intersecting stopping when we hit bits in common. |
748 | 69 | while (69 Iter2 != RHS.Elements.end()69 ) { |
749 | 0 | if (Iter1 == Elements.end()) |
750 | 0 | return false; |
751 | 0 |
|
752 | 0 | if (0 Iter1->index() > Iter2->index()0 ) { |
753 | 0 | ++Iter2; |
754 | 0 | } else if (0 Iter1->index() == Iter2->index()0 ) { |
755 | 0 | if (Iter1->intersects(*Iter2)) |
756 | 0 | return true; |
757 | 0 | ++Iter1; |
758 | 0 | ++Iter2; |
759 | 0 | } else { |
760 | 0 | ++Iter1; |
761 | 0 | } |
762 | 0 | } |
763 | 69 | return false; |
764 | 69 | } |
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 | 139 | int find_first() const { |
776 | 139 | if (Elements.empty()) |
777 | 4 | return -1; |
778 | 135 | const SparseBitVectorElement<ElementSize> &First = *(Elements.begin()); |
779 | 135 | return (First.index() * ElementSize) + First.find_first(); |
780 | 139 | } |
781 | | |
782 | | // Return the last set bit in the bitmap. Return -1 if no bits are set. |
783 | 250 | int find_last() const { |
784 | 250 | if (Elements.empty()) |
785 | 122 | return -1; |
786 | 128 | const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin()); |
787 | 128 | return (Last.index() * ElementSize) + Last.find_last(); |
788 | 250 | } |
789 | | |
790 | | // Return true if the SparseBitVector is empty |
791 | 16.2M | bool empty() const { |
792 | 16.2M | return Elements.empty(); |
793 | 16.2M | } |
794 | | |
795 | 59.6k | unsigned count() const { |
796 | 59.6k | unsigned BitCount = 0; |
797 | 59.6k | for (ElementListConstIter Iter = Elements.begin(); |
798 | 124k | Iter != Elements.end(); |
799 | 64.6k | ++Iter) |
800 | 64.6k | BitCount += Iter->count(); |
801 | 59.6k | |
802 | 59.6k | return BitCount; |
803 | 59.6k | } |
804 | | |
805 | 2.92M | iterator begin() const { |
806 | 2.92M | return iterator(this); |
807 | 2.92M | } |
808 | | |
809 | 2.89M | iterator end() const { |
810 | 2.89M | return iterator(this, true); |
811 | 2.89M | } |
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 |