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