/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/ADT/SmallBitVector.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- 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 implements the SmallBitVector class. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #ifndef LLVM_ADT_SMALLBITVECTOR_H |
15 | | #define LLVM_ADT_SMALLBITVECTOR_H |
16 | | |
17 | | #include "llvm/ADT/BitVector.h" |
18 | | #include "llvm/ADT/iterator_range.h" |
19 | | #include "llvm/Support/MathExtras.h" |
20 | | #include <algorithm> |
21 | | #include <cassert> |
22 | | #include <climits> |
23 | | #include <cstddef> |
24 | | #include <cstdint> |
25 | | #include <limits> |
26 | | #include <utility> |
27 | | |
28 | | namespace llvm { |
29 | | |
30 | | /// This is a 'bitvector' (really, a variable-sized bit array), optimized for |
31 | | /// the case when the array is small. It contains one pointer-sized field, which |
32 | | /// is directly used as a plain collection of bits when possible, or as a |
33 | | /// pointer to a larger heap-allocated array when necessary. This allows normal |
34 | | /// "small" cases to be fast without losing generality for large inputs. |
35 | | class SmallBitVector { |
36 | | // TODO: In "large" mode, a pointer to a BitVector is used, leading to an |
37 | | // unnecessary level of indirection. It would be more efficient to use a |
38 | | // pointer to memory containing size, allocation size, and the array of bits. |
39 | | uintptr_t X = 1; |
40 | | |
41 | | enum { |
42 | | // The number of bits in this class. |
43 | | NumBaseBits = sizeof(uintptr_t) * CHAR_BIT, |
44 | | |
45 | | // One bit is used to discriminate between small and large mode. The |
46 | | // remaining bits are used for the small-mode representation. |
47 | | SmallNumRawBits = NumBaseBits - 1, |
48 | | |
49 | | // A few more bits are used to store the size of the bit set in small mode. |
50 | | // Theoretically this is a ceil-log2. These bits are encoded in the most |
51 | | // significant bits of the raw bits. |
52 | | SmallNumSizeBits = (NumBaseBits == 32 ? 5 : |
53 | | NumBaseBits == 64 ? 6 : |
54 | | SmallNumRawBits), |
55 | | |
56 | | // The remaining bits are used to store the actual set in small mode. |
57 | | SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits |
58 | | }; |
59 | | |
60 | | static_assert(NumBaseBits == 64 || NumBaseBits == 32, |
61 | | "Unsupported word size"); |
62 | | |
63 | | public: |
64 | | using size_type = unsigned; |
65 | | |
66 | | // Encapsulation of a single bit. |
67 | | class reference { |
68 | | SmallBitVector &TheVector; |
69 | | unsigned BitPos; |
70 | | |
71 | | public: |
72 | 148M | reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} |
73 | | |
74 | | reference(const reference&) = default; |
75 | | |
76 | 0 | reference& operator=(reference t) { |
77 | 0 | *this = bool(t); |
78 | 0 | return *this; |
79 | 0 | } |
80 | | |
81 | 89.8M | reference& operator=(bool t) { |
82 | 89.8M | if (t) |
83 | 2.80M | TheVector.set(BitPos); |
84 | 89.8M | else |
85 | 87.0M | TheVector.reset(BitPos); |
86 | 89.8M | return *this; |
87 | 89.8M | } |
88 | | |
89 | 58.1M | operator bool() const { |
90 | 58.1M | return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); |
91 | 58.1M | } |
92 | | }; |
93 | | |
94 | | private: |
95 | 654M | bool isSmall() const { |
96 | 654M | return X & uintptr_t(1); |
97 | 654M | } |
98 | | |
99 | 294M | BitVector *getPointer() const { |
100 | 294M | assert(!isSmall()); |
101 | 294M | return reinterpret_cast<BitVector *>(X); |
102 | 294M | } |
103 | | |
104 | 11.7M | void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { |
105 | 11.7M | X = 1; |
106 | 11.7M | setSmallSize(NewSize); |
107 | 11.7M | setSmallBits(NewSmallBits); |
108 | 11.7M | } |
109 | | |
110 | 587k | void switchToLarge(BitVector *BV) { |
111 | 587k | X = reinterpret_cast<uintptr_t>(BV); |
112 | 587k | assert(!isSmall() && "Tried to use an unaligned pointer"); |
113 | 587k | } |
114 | | |
115 | | // Return all the bits used for the "small" representation; this includes |
116 | | // bits for the size as well as the element bits. |
117 | 891M | uintptr_t getSmallRawBits() const { |
118 | 891M | assert(isSmall()); |
119 | 891M | return X >> 1; |
120 | 891M | } |
121 | | |
122 | 199M | void setSmallRawBits(uintptr_t NewRawBits) { |
123 | 199M | assert(isSmall()); |
124 | 199M | X = (NewRawBits << 1) | uintptr_t(1); |
125 | 199M | } |
126 | | |
127 | | // Return the size. |
128 | 651M | size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; } |
129 | | |
130 | 66.7M | void setSmallSize(size_t Size) { |
131 | 66.7M | setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); |
132 | 66.7M | } |
133 | | |
134 | | // Return the element bits. |
135 | 239M | uintptr_t getSmallBits() const { |
136 | 239M | return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); |
137 | 239M | } |
138 | | |
139 | 132M | void setSmallBits(uintptr_t NewBits) { |
140 | 132M | setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | |
141 | 132M | (getSmallSize() << SmallNumDataBits)); |
142 | 132M | } |
143 | | |
144 | | public: |
145 | | /// Creates an empty bitvector. |
146 | 18.0M | SmallBitVector() = default; |
147 | | |
148 | | /// Creates a bitvector of specified number of bits. All bits are initialized |
149 | | /// to the specified value. |
150 | 8.28M | explicit SmallBitVector(unsigned s, bool t = false) { |
151 | 8.28M | if (s <= SmallNumDataBits) |
152 | 8.28M | switchToSmall(t ? 8.28M ~uintptr_t(0)146k : 08.14M , s); |
153 | 8.28M | else |
154 | 923 | switchToLarge(new BitVector(s, t)); |
155 | 8.28M | } |
156 | | |
157 | | /// SmallBitVector copy ctor. |
158 | 191k | SmallBitVector(const SmallBitVector &RHS) { |
159 | 191k | if (RHS.isSmall()) |
160 | 191k | X = RHS.X; |
161 | 191k | else |
162 | 5 | switchToLarge(new BitVector(*RHS.getPointer())); |
163 | 191k | } |
164 | | |
165 | 16.3M | SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { |
166 | 16.3M | RHS.X = 1; |
167 | 16.3M | } |
168 | | |
169 | 42.8M | ~SmallBitVector() { |
170 | 42.8M | if (!isSmall()) |
171 | 587k | delete getPointer(); |
172 | 42.8M | } |
173 | | |
174 | | using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>; |
175 | | using set_iterator = const_set_bits_iterator; |
176 | | |
177 | 4.40M | const_set_bits_iterator set_bits_begin() const { |
178 | 4.40M | return const_set_bits_iterator(*this); |
179 | 4.40M | } |
180 | | |
181 | 4.40M | const_set_bits_iterator set_bits_end() const { |
182 | 4.40M | return const_set_bits_iterator(*this, -1); |
183 | 4.40M | } |
184 | | |
185 | 4.40M | iterator_range<const_set_bits_iterator> set_bits() const { |
186 | 4.40M | return make_range(set_bits_begin(), set_bits_end()); |
187 | 4.40M | } |
188 | | |
189 | | /// Tests whether there are no bits in this bitvector. |
190 | 161k | bool empty() const { |
191 | 161k | return isSmall() ? getSmallSize() == 0161k : getPointer()->empty()4 ; |
192 | 161k | } |
193 | | |
194 | | /// Returns the number of bits in this bitvector. |
195 | 290M | size_t size() const { |
196 | 290M | return isSmall() ? getSmallSize()141M : getPointer()->size()148M ; |
197 | 290M | } |
198 | | |
199 | | /// Returns the number of bits which are set. |
200 | 2.63M | size_type count() const { |
201 | 2.63M | if (isSmall()2.63M ) { |
202 | 2.00M | uintptr_t Bits = getSmallBits(); |
203 | 2.00M | return countPopulation(Bits); |
204 | 2.00M | } |
205 | 626k | return getPointer()->count(); |
206 | 2.63M | } |
207 | | |
208 | | /// Returns true if any bit is set. |
209 | 65.7k | bool any() const { |
210 | 65.7k | if (isSmall()) |
211 | 65.6k | return getSmallBits() != 0; |
212 | 4 | return getPointer()->any(); |
213 | 65.7k | } |
214 | | |
215 | | /// Returns true if all bits are set. |
216 | 4.22k | bool all() const { |
217 | 4.22k | if (isSmall()) |
218 | 4.22k | return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; |
219 | 4 | return getPointer()->all(); |
220 | 4.22k | } |
221 | | |
222 | | /// Returns true if none of the bits are set. |
223 | | bool none() const { |
224 | | if (isSmall()) |
225 | | return getSmallBits() == 0; |
226 | | return getPointer()->none(); |
227 | | } |
228 | | |
229 | | /// Returns the index of the first set bit, -1 if none of the bits are set. |
230 | 15.4M | int find_first() const { |
231 | 15.4M | if (isSmall()15.4M ) { |
232 | 11.8M | uintptr_t Bits = getSmallBits(); |
233 | 11.8M | if (Bits == 0) |
234 | 78.1k | return -1; |
235 | 11.8M | return countTrailingZeros(Bits); |
236 | 11.8M | } |
237 | 3.61M | return getPointer()->find_first(); |
238 | 15.4M | } |
239 | | |
240 | | int find_last() const { |
241 | | if (isSmall()) { |
242 | | uintptr_t Bits = getSmallBits(); |
243 | | if (Bits == 0) |
244 | | return -1; |
245 | | return NumBaseBits - countLeadingZeros(Bits); |
246 | | } |
247 | | return getPointer()->find_last(); |
248 | | } |
249 | | |
250 | | /// Returns the index of the first unset bit, -1 if all of the bits are set. |
251 | | int find_first_unset() const { |
252 | | if (isSmall()) { |
253 | | if (count() == getSmallSize()) |
254 | | return -1; |
255 | | |
256 | | uintptr_t Bits = getSmallBits(); |
257 | | return countTrailingOnes(Bits); |
258 | | } |
259 | | return getPointer()->find_first_unset(); |
260 | | } |
261 | | |
262 | | int find_last_unset() const { |
263 | | if (isSmall()) { |
264 | | if (count() == getSmallSize()) |
265 | | return -1; |
266 | | |
267 | | uintptr_t Bits = getSmallBits(); |
268 | | return NumBaseBits - countLeadingOnes(Bits); |
269 | | } |
270 | | return getPointer()->find_last_unset(); |
271 | | } |
272 | | |
273 | | /// Returns the index of the next set bit following the "Prev" bit. |
274 | | /// Returns -1 if the next set bit is not found. |
275 | 12.8M | int find_next(unsigned Prev) const { |
276 | 12.8M | if (isSmall()12.8M ) { |
277 | 10.1M | uintptr_t Bits = getSmallBits(); |
278 | 10.1M | // Mask off previous bits. |
279 | 10.1M | Bits &= ~uintptr_t(0) << (Prev + 1); |
280 | 10.1M | if (Bits == 0 || 10.1M Prev + 1 >= getSmallSize()3.20M ) |
281 | 6.99M | return -1; |
282 | 3.20M | return countTrailingZeros(Bits); |
283 | 10.1M | } |
284 | 2.70M | return getPointer()->find_next(Prev); |
285 | 12.8M | } |
286 | | |
287 | | /// Returns the index of the next unset bit following the "Prev" bit. |
288 | | /// Returns -1 if the next unset bit is not found. |
289 | | int find_next_unset(unsigned Prev) const { |
290 | | if (isSmall()) { |
291 | | ++Prev; |
292 | | uintptr_t Bits = getSmallBits(); |
293 | | // Mask in previous bits. |
294 | | uintptr_t Mask = (1 << Prev) - 1; |
295 | | Bits |= Mask; |
296 | | |
297 | | if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize()) |
298 | | return -1; |
299 | | return countTrailingOnes(Bits); |
300 | | } |
301 | | return getPointer()->find_next_unset(Prev); |
302 | | } |
303 | | |
304 | | /// find_prev - Returns the index of the first set bit that precedes the |
305 | | /// the bit at \p PriorTo. Returns -1 if all previous bits are unset. |
306 | | int find_prev(unsigned PriorTo) const { |
307 | | if (isSmall()) { |
308 | | if (PriorTo == 0) |
309 | | return -1; |
310 | | |
311 | | --PriorTo; |
312 | | uintptr_t Bits = getSmallBits(); |
313 | | Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1); |
314 | | if (Bits == 0) |
315 | | return -1; |
316 | | |
317 | | return NumBaseBits - countLeadingZeros(Bits) - 1; |
318 | | } |
319 | | return getPointer()->find_prev(PriorTo); |
320 | | } |
321 | | |
322 | | /// Clear all bits. |
323 | 3.42M | void clear() { |
324 | 3.42M | if (!isSmall()) |
325 | 2 | delete getPointer(); |
326 | 3.42M | switchToSmall(0, 0); |
327 | 3.42M | } |
328 | | |
329 | | /// Grow or shrink the bitvector. |
330 | 106M | void resize(unsigned N, bool t = false) { |
331 | 106M | if (!isSmall()106M ) { |
332 | 50.9M | getPointer()->resize(N, t); |
333 | 106M | } else if (55.5M SmallNumDataBits >= N55.5M ) { |
334 | 54.9M | uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize()54 : 054.9M ; |
335 | 54.9M | setSmallSize(N); |
336 | 54.9M | setSmallBits(NewBits | getSmallBits()); |
337 | 55.5M | } else { |
338 | 586k | BitVector *BV = new BitVector(N, t); |
339 | 586k | uintptr_t OldBits = getSmallBits(); |
340 | 6.44M | for (size_t i = 0, e = getSmallSize(); i != e6.44M ; ++i5.85M ) |
341 | 5.85M | (*BV)[i] = (OldBits >> i) & 1; |
342 | 55.5M | switchToLarge(BV); |
343 | 55.5M | } |
344 | 106M | } |
345 | | |
346 | 0 | void reserve(unsigned N) { |
347 | 0 | if (isSmall()) { |
348 | 0 | if (N > SmallNumDataBits) { |
349 | 0 | uintptr_t OldBits = getSmallRawBits(); |
350 | 0 | size_t SmallSize = getSmallSize(); |
351 | 0 | BitVector *BV = new BitVector(SmallSize); |
352 | 0 | for (size_t i = 0; i < SmallSize; ++i) |
353 | 0 | if ((OldBits >> i) & 1) |
354 | 0 | BV->set(i); |
355 | 0 | BV->reserve(N); |
356 | 0 | switchToLarge(BV); |
357 | 0 | } |
358 | 0 | } else { |
359 | 0 | getPointer()->reserve(N); |
360 | 0 | } |
361 | 0 | } |
362 | | |
363 | | // Set, reset, flip |
364 | | SmallBitVector &set() { |
365 | | if (isSmall()) |
366 | | setSmallBits(~uintptr_t(0)); |
367 | | else |
368 | | getPointer()->set(); |
369 | | return *this; |
370 | | } |
371 | | |
372 | 25.2M | SmallBitVector &set(unsigned Idx) { |
373 | 25.2M | if (isSmall()25.2M ) { |
374 | 21.9M | assert(Idx <= static_cast<unsigned>( |
375 | 21.9M | std::numeric_limits<uintptr_t>::digits) && |
376 | 21.9M | "undefined behavior"); |
377 | 21.9M | setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); |
378 | 21.9M | } |
379 | 25.2M | else |
380 | 3.36M | getPointer()->set(Idx); |
381 | 25.2M | return *this; |
382 | 25.2M | } |
383 | | |
384 | | /// Efficiently set a range of bits in [I, E) |
385 | 160k | SmallBitVector &set(unsigned I, unsigned E) { |
386 | 160k | assert(I <= E && "Attempted to set backwards range!"); |
387 | 160k | assert(E <= size() && "Attempted to set out-of-bounds range!"); |
388 | 160k | if (I == E160k ) return *this0 ; |
389 | 160k | if (160k isSmall()160k ) { |
390 | 160k | uintptr_t EMask = ((uintptr_t)1) << E; |
391 | 160k | uintptr_t IMask = ((uintptr_t)1) << I; |
392 | 160k | uintptr_t Mask = EMask - IMask; |
393 | 160k | setSmallBits(getSmallBits() | Mask); |
394 | 160k | } else |
395 | 99 | getPointer()->set(I, E); |
396 | 160k | return *this; |
397 | 160k | } |
398 | | |
399 | 324k | SmallBitVector &reset() { |
400 | 324k | if (isSmall()) |
401 | 322k | setSmallBits(0); |
402 | 324k | else |
403 | 1.85k | getPointer()->reset(); |
404 | 324k | return *this; |
405 | 324k | } |
406 | | |
407 | 88.0M | SmallBitVector &reset(unsigned Idx) { |
408 | 88.0M | if (isSmall()) |
409 | 40.5M | setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); |
410 | 88.0M | else |
411 | 47.4M | getPointer()->reset(Idx); |
412 | 88.0M | return *this; |
413 | 88.0M | } |
414 | | |
415 | | /// Efficiently reset a range of bits in [I, E) |
416 | 219k | SmallBitVector &reset(unsigned I, unsigned E) { |
417 | 219k | assert(I <= E && "Attempted to reset backwards range!"); |
418 | 219k | assert(E <= size() && "Attempted to reset out-of-bounds range!"); |
419 | 219k | if (I == E219k ) return *this0 ; |
420 | 219k | if (219k isSmall()219k ) { |
421 | 219k | uintptr_t EMask = ((uintptr_t)1) << E; |
422 | 219k | uintptr_t IMask = ((uintptr_t)1) << I; |
423 | 219k | uintptr_t Mask = EMask - IMask; |
424 | 219k | setSmallBits(getSmallBits() & ~Mask); |
425 | 219k | } else |
426 | 3 | getPointer()->reset(I, E); |
427 | 219k | return *this; |
428 | 219k | } |
429 | | |
430 | 77.7k | SmallBitVector &flip() { |
431 | 77.7k | if (isSmall()) |
432 | 77.7k | setSmallBits(~getSmallBits()); |
433 | 77.7k | else |
434 | 3 | getPointer()->flip(); |
435 | 77.7k | return *this; |
436 | 77.7k | } |
437 | | |
438 | | SmallBitVector &flip(unsigned Idx) { |
439 | | if (isSmall()) |
440 | | setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); |
441 | | else |
442 | | getPointer()->flip(Idx); |
443 | | return *this; |
444 | | } |
445 | | |
446 | | // No argument flip. |
447 | 0 | SmallBitVector operator~() const { |
448 | 0 | return SmallBitVector(*this).flip(); |
449 | 0 | } |
450 | | |
451 | | // Indexing. |
452 | 148M | reference operator[](unsigned Idx) { |
453 | 148M | assert(Idx < size() && "Out-of-bounds Bit access."); |
454 | 148M | return reference(*this, Idx); |
455 | 148M | } |
456 | | |
457 | 59.9M | bool operator[](unsigned Idx) const { |
458 | 59.9M | assert(Idx < size() && "Out-of-bounds Bit access."); |
459 | 59.9M | if (isSmall()) |
460 | 24.7M | return ((getSmallBits() >> Idx) & 1) != 0; |
461 | 35.1M | return getPointer()->operator[](Idx); |
462 | 59.9M | } |
463 | | |
464 | 1.17k | bool test(unsigned Idx) const { |
465 | 1.17k | return (*this)[Idx]; |
466 | 1.17k | } |
467 | | |
468 | | /// Test if any common bits are set. |
469 | | bool anyCommon(const SmallBitVector &RHS) const { |
470 | | if (isSmall() && RHS.isSmall()) |
471 | | return (getSmallBits() & RHS.getSmallBits()) != 0; |
472 | | if (!isSmall() && !RHS.isSmall()) |
473 | | return getPointer()->anyCommon(*RHS.getPointer()); |
474 | | |
475 | | for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) |
476 | | if (test(i) && RHS.test(i)) |
477 | | return true; |
478 | | return false; |
479 | | } |
480 | | |
481 | | // Comparison operators. |
482 | 233k | bool operator==(const SmallBitVector &RHS) const { |
483 | 233k | if (size() != RHS.size()) |
484 | 0 | return false; |
485 | 233k | if (233k isSmall()233k ) |
486 | 231k | return getSmallBits() == RHS.getSmallBits(); |
487 | 233k | else |
488 | 1.80k | return *getPointer() == *RHS.getPointer(); |
489 | 233k | } |
490 | | |
491 | 233k | bool operator!=(const SmallBitVector &RHS) const { |
492 | 233k | return !(*this == RHS); |
493 | 233k | } |
494 | | |
495 | | // Intersection, union, disjoint union. |
496 | 349 | SmallBitVector &operator&=(const SmallBitVector &RHS) { |
497 | 349 | resize(std::max(size(), RHS.size())); |
498 | 349 | if (isSmall()) |
499 | 349 | setSmallBits(getSmallBits() & RHS.getSmallBits()); |
500 | 0 | else if (0 !RHS.isSmall()0 ) |
501 | 0 | getPointer()->operator&=(*RHS.getPointer()); |
502 | 0 | else { |
503 | 0 | SmallBitVector Copy = RHS; |
504 | 0 | Copy.resize(size()); |
505 | 0 | getPointer()->operator&=(*Copy.getPointer()); |
506 | 0 | } |
507 | 349 | return *this; |
508 | 349 | } |
509 | | |
510 | | /// Reset bits that are set in RHS. Same as *this &= ~RHS. |
511 | | SmallBitVector &reset(const SmallBitVector &RHS) { |
512 | | if (isSmall() && RHS.isSmall()) |
513 | | setSmallBits(getSmallBits() & ~RHS.getSmallBits()); |
514 | | else if (!isSmall() && !RHS.isSmall()) |
515 | | getPointer()->reset(*RHS.getPointer()); |
516 | | else |
517 | | for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) |
518 | | if (RHS.test(i)) |
519 | | reset(i); |
520 | | |
521 | | return *this; |
522 | | } |
523 | | |
524 | | /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any(). |
525 | 40 | bool test(const SmallBitVector &RHS) const { |
526 | 40 | if (isSmall() && 40 RHS.isSmall()8 ) |
527 | 4 | return (getSmallBits() & ~RHS.getSmallBits()) != 0; |
528 | 36 | if (36 !isSmall() && 36 !RHS.isSmall()32 ) |
529 | 30 | return getPointer()->test(*RHS.getPointer()); |
530 | 36 | |
531 | 6 | unsigned i, e; |
532 | 206 | for (i = 0, e = std::min(size(), RHS.size()); i != e206 ; ++i200 ) |
533 | 202 | if (202 test(i) && 202 !RHS.test(i)102 ) |
534 | 2 | return true; |
535 | 6 | |
536 | 4 | for (e = size(); 4 i != e4 ; ++i0 ) |
537 | 1 | if (1 test(i)1 ) |
538 | 1 | return true; |
539 | 4 | |
540 | 3 | return false; |
541 | 40 | } |
542 | | |
543 | 3.25M | SmallBitVector &operator|=(const SmallBitVector &RHS) { |
544 | 3.25M | resize(std::max(size(), RHS.size())); |
545 | 3.25M | if (isSmall()) |
546 | 2.68M | setSmallBits(getSmallBits() | RHS.getSmallBits()); |
547 | 571k | else if (571k !RHS.isSmall()571k ) |
548 | 386k | getPointer()->operator|=(*RHS.getPointer()); |
549 | 184k | else { |
550 | 184k | SmallBitVector Copy = RHS; |
551 | 184k | Copy.resize(size()); |
552 | 184k | getPointer()->operator|=(*Copy.getPointer()); |
553 | 184k | } |
554 | 3.25M | return *this; |
555 | 3.25M | } |
556 | | |
557 | | SmallBitVector &operator^=(const SmallBitVector &RHS) { |
558 | | resize(std::max(size(), RHS.size())); |
559 | | if (isSmall()) |
560 | | setSmallBits(getSmallBits() ^ RHS.getSmallBits()); |
561 | | else if (!RHS.isSmall()) |
562 | | getPointer()->operator^=(*RHS.getPointer()); |
563 | | else { |
564 | | SmallBitVector Copy = RHS; |
565 | | Copy.resize(size()); |
566 | | getPointer()->operator^=(*Copy.getPointer()); |
567 | | } |
568 | | return *this; |
569 | | } |
570 | | |
571 | | SmallBitVector &operator<<=(unsigned N) { |
572 | | if (isSmall()) |
573 | | setSmallBits(getSmallBits() << N); |
574 | | else |
575 | | getPointer()->operator<<=(N); |
576 | | return *this; |
577 | | } |
578 | | |
579 | | SmallBitVector &operator>>=(unsigned N) { |
580 | | if (isSmall()) |
581 | | setSmallBits(getSmallBits() >> N); |
582 | | else |
583 | | getPointer()->operator>>=(N); |
584 | | return *this; |
585 | | } |
586 | | |
587 | | // Assignment operator. |
588 | 457k | const SmallBitVector &operator=(const SmallBitVector &RHS) { |
589 | 457k | if (isSmall()457k ) { |
590 | 453k | if (RHS.isSmall()) |
591 | 453k | X = RHS.X; |
592 | 453k | else |
593 | 0 | switchToLarge(new BitVector(*RHS.getPointer())); |
594 | 457k | } else { |
595 | 3.56k | if (!RHS.isSmall()) |
596 | 3.56k | *getPointer() = *RHS.getPointer(); |
597 | 0 | else { |
598 | 0 | delete getPointer(); |
599 | 0 | X = RHS.X; |
600 | 0 | } |
601 | 3.56k | } |
602 | 457k | return *this; |
603 | 457k | } |
604 | | |
605 | | const SmallBitVector &operator=(SmallBitVector &&RHS) { |
606 | | if (this != &RHS) { |
607 | | clear(); |
608 | | swap(RHS); |
609 | | } |
610 | | return *this; |
611 | | } |
612 | | |
613 | 0 | void swap(SmallBitVector &RHS) { |
614 | 0 | std::swap(X, RHS.X); |
615 | 0 | } |
616 | | |
617 | | /// Add '1' bits from Mask to this vector. Don't resize. |
618 | | /// This computes "*this |= Mask". |
619 | | void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
620 | | if (isSmall()) |
621 | | applyMask<true, false>(Mask, MaskWords); |
622 | | else |
623 | | getPointer()->setBitsInMask(Mask, MaskWords); |
624 | | } |
625 | | |
626 | | /// Clear any bits in this vector that are set in Mask. Don't resize. |
627 | | /// This computes "*this &= ~Mask". |
628 | 0 | void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
629 | 0 | if (isSmall()) |
630 | 0 | applyMask<false, false>(Mask, MaskWords); |
631 | 0 | else |
632 | 0 | getPointer()->clearBitsInMask(Mask, MaskWords); |
633 | 0 | } |
634 | | |
635 | | /// Add a bit to this vector for every '0' bit in Mask. Don't resize. |
636 | | /// This computes "*this |= ~Mask". |
637 | | void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
638 | | if (isSmall()) |
639 | | applyMask<true, true>(Mask, MaskWords); |
640 | | else |
641 | | getPointer()->setBitsNotInMask(Mask, MaskWords); |
642 | | } |
643 | | |
644 | | /// Clear a bit in this vector for every '0' bit in Mask. Don't resize. |
645 | | /// This computes "*this &= Mask". |
646 | | void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
647 | | if (isSmall()) |
648 | | applyMask<false, true>(Mask, MaskWords); |
649 | | else |
650 | | getPointer()->clearBitsNotInMask(Mask, MaskWords); |
651 | | } |
652 | | |
653 | | private: |
654 | | template <bool AddBits, bool InvertMask> |
655 | 0 | void applyMask(const uint32_t *Mask, unsigned MaskWords) { |
656 | 0 | assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!"); |
657 | 0 | uintptr_t M = Mask[0]; |
658 | 0 | if (NumBaseBits == 64) |
659 | 0 | M |= uint64_t(Mask[1]) << 32; |
660 | 0 | if (InvertMask) |
661 | 0 | M = ~M; |
662 | 0 | if (AddBits) |
663 | 0 | setSmallBits(getSmallBits() | M); |
664 | 0 | else |
665 | 0 | setSmallBits(getSmallBits() & ~M); |
666 | 0 | } Unexecuted instantiation: void llvm::SmallBitVector::applyMask<true, true>(unsigned int const*, unsigned int) Unexecuted instantiation: void llvm::SmallBitVector::applyMask<false, true>(unsigned int const*, unsigned int) Unexecuted instantiation: void llvm::SmallBitVector::applyMask<false, false>(unsigned int const*, unsigned int) |
667 | | }; |
668 | | |
669 | | inline SmallBitVector |
670 | 0 | operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { |
671 | 0 | SmallBitVector Result(LHS); |
672 | 0 | Result &= RHS; |
673 | 0 | return Result; |
674 | 0 | } |
675 | | |
676 | | inline SmallBitVector |
677 | 2.53k | operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { |
678 | 2.53k | SmallBitVector Result(LHS); |
679 | 2.53k | Result |= RHS; |
680 | 2.53k | return Result; |
681 | 2.53k | } |
682 | | |
683 | | inline SmallBitVector |
684 | 0 | operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { |
685 | 0 | SmallBitVector Result(LHS); |
686 | 0 | Result ^= RHS; |
687 | 0 | return Result; |
688 | 0 | } |
689 | | |
690 | | } // end namespace llvm |
691 | | |
692 | | namespace std { |
693 | | |
694 | | /// Implement std::swap in terms of BitVector swap. |
695 | | inline void |
696 | 0 | swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { |
697 | 0 | LHS.swap(RHS); |
698 | 0 | } |
699 | | |
700 | | } // end namespace std |
701 | | |
702 | | #endif // LLVM_ADT_SMALLBITVECTOR_H |