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