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
28namespace 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.
35class 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
63public:
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
94private:
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
142public:
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
693private:
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
709inline SmallBitVector
710operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
711 SmallBitVector Result(LHS);
712 Result &= RHS;
713 return Result;
714}
715
716inline SmallBitVector
717operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
718 SmallBitVector Result(LHS);
719 Result |= RHS;
720 return Result;
721}
722
723inline SmallBitVector
724operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
725 SmallBitVector Result(LHS);
726 Result ^= RHS;
727 return Result;
728}
729
730template <> 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
751namespace std {
752
753/// Implement std::swap in terms of BitVector swap.
754inline void
755swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
756 LHS.swap(RHS);
757}
758
759} // end namespace std
760
761#endif // LLVM_ADT_SMALLBITVECTOR_H
762

source code of include/llvm-17/llvm/ADT/SmallBitVector.h