SmallBitVector.h Source File (original) (raw)

14#ifndef LLVM_ADT_SMALLBITVECTOR_H

15#define LLVM_ADT_SMALLBITVECTOR_H

20#include

21#include

22#include

23#include

24#include

25#include

26#include

28namespace llvm {

39 uintptr_t X = 1;

41 enum {

43 NumBaseBits = sizeof(uintptr_t) * CHAR_BIT,

47 SmallNumRawBits = NumBaseBits - 1,

52 SmallNumSizeBits = (NumBaseBits == 32 ? 5 :

53 NumBaseBits == 64 ? 6 :

54 SmallNumRawBits),

57 SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits

58 };

60 static_assert(NumBaseBits == 64 || NumBaseBits == 32,

61 "Unsupported word size");

63public:

69 unsigned BitPos;

71 public:

77 *this = bool(t);

78 return *this;

79 }

82 if (t)

83 TheVector.set(BitPos);

84 else

85 TheVector.reset(BitPos);

86 return *this;

87 }

89 operator bool() const {

90 return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);

91 }

92 };

94private:

97 return reinterpret_cast<BitVector *>(X);

98 }

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

112

113 uintptr_t getSmallRawBits() const {

115 return X >> 1;

116 }

117

118 void setSmallRawBits(uintptr_t NewRawBits) {

120 X = (NewRawBits << 1) | uintptr_t(1);

121 }

122

123

125 return getSmallRawBits() >> SmallNumDataBits;

126 }

127

129 setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));

130 }

131

132

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

145

146

147

149 if (s <= SmallNumDataBits)

150 switchToSmall(t ? ~uintptr_t(0) : 0, s);

151 else

152 switchToLarge(new BitVector(s, t));

153 }

154

155

157 if (RHS.isSmall())

158 X = RHS.X;

159 else

160 switchToLarge(new BitVector(*RHS.getPointer()));

161 }

162

166

169 delete getPointer();

170 }

171

174

178

182

186

187 bool isSmall() const { return X & uintptr_t(1); }

188

189

191 return isSmall() ? getSmallSize() == 0 : getPointer()->empty();

192 }

193

194

196 return isSmall() ? getSmallSize() : getPointer()->size();

197 }

198

199

202 uintptr_t Bits = getSmallBits();

204 }

205 return getPointer()->count();

206 }

207

208

211 return getSmallBits() != 0;

212 return getPointer()->any();

213 }

214

215

218 return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;

219 return getPointer()->all();

220 }

221

222

225 return getSmallBits() == 0;

226 return getPointer()->none();

227 }

228

229

232 uintptr_t Bits = getSmallBits();

233 if (Bits == 0)

234 return -1;

236 }

237 return getPointer()->find_first();

238 }

239

242 uintptr_t Bits = getSmallBits();

243 if (Bits == 0)

244 return -1;

246 }

247 return getPointer()->find_last();

248 }

249

250

253 if (count() == getSmallSize())

254 return -1;

255

256 uintptr_t Bits = getSmallBits();

258 }

259 return getPointer()->find_first_unset();

260 }

261

264 if (count() == getSmallSize())

265 return -1;

266

267 uintptr_t Bits = getSmallBits();

268

269 Bits |= ~uintptr_t(0) << getSmallSize();

271 }

272 return getPointer()->find_last_unset();

273 }

274

275

276

279 uintptr_t Bits = getSmallBits();

280

281 Bits &= ~uintptr_t(0) << (Prev + 1);

282 if (Bits == 0 || Prev + 1 >= getSmallSize())

283 return -1;

285 }

286 return getPointer()->find_next(Prev);

287 }

288

289

290

293 uintptr_t Bits = getSmallBits();

294

295 Bits |= (uintptr_t(1) << (Prev + 1)) - 1;

296

297 Bits |= ~uintptr_t(0) << getSmallSize();

298

299 if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())

300 return -1;

302 }

303 return getPointer()->find_next_unset(Prev);

304 }

305

306

307

310 if (PriorTo == 0)

311 return -1;

312

313 --PriorTo;

314 uintptr_t Bits = getSmallBits();

316 if (Bits == 0)

317 return -1;

318

320 }

321 return getPointer()->find_prev(PriorTo);

322 }

323

324

327 delete getPointer();

328 switchToSmall(0, 0);

329 }

330

331

332 void resize(unsigned N, bool t = false) {

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 {

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

350 if (N > SmallNumDataBits) {

351 uintptr_t OldBits = getSmallRawBits();

352 size_type SmallSize = getSmallSize();

355 if ((OldBits >> I) & 1)

358 switchToLarge(BV);

359 }

360 } else {

361 getPointer()->reserve(N);

362 }

363 }

364

365

368 setSmallBits(~uintptr_t(0));

369 else

370 getPointer()->set();

371 return *this;

372 }

373

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

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;

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 }

399 return *this;

400 }

401

404 setSmallBits(0);

405 else

406 getPointer()->reset();

407 return *this;

408 }

409

412 setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));

413 else

414 getPointer()->reset(Idx);

415 return *this;

416 }

417

418

420 assert(I <= E && "Attempted to reset backwards range!");

421 assert(E <= size() && "Attempted to reset out-of-bounds range!");

422 if (I == E) return *this;

424 uintptr_t EMask = ((uintptr_t)1) << E;

425 uintptr_t IMask = ((uintptr_t)1) << I;

426 uintptr_t Mask = EMask - IMask;

427 setSmallBits(getSmallBits() & ~Mask);

428 } else {

429 getPointer()->reset(I, E);

430 }

431 return *this;

432 }

433

436 setSmallBits(~getSmallBits());

437 else

438 getPointer()->flip();

439 return *this;

440 }

441

444 setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));

445 else

446 getPointer()->flip(Idx);

447 return *this;

448 }

449

450

454

455

457 assert(Idx < size() && "Out-of-bounds Bit access.");

459 }

460

462 assert(Idx < size() && "Out-of-bounds Bit access.");

464 return ((getSmallBits() >> Idx) & 1) != 0;

465 return getPointer()->operator[](Idx);

466 }

467

468

470 assert( empty () && "Getting last element of empty vector.");

471 return (*this)[size() - 1];

472 }

473

474 bool test(unsigned Idx) const {

475 return (*this)[Idx];

476 }

477

478

482

483

485 assert( empty () && "Empty vector has no element to pop.");

487 }

488

489

492 return (getSmallBits() & RHS.getSmallBits()) != 0;

494 return getPointer()->anyCommon(*RHS.getPointer());

495

496 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)

497 if (test(i) && RHS.test(i))

498 return true;

499 return false;

500 }

501

502

504 if (size() != RHS.size())

505 return false;

507 return getSmallBits() == RHS.getSmallBits();

508 else if ( isSmall () && RHS .isSmall())

509 return *getPointer() == *RHS.getPointer();

510 else {

512 if ((*this)[I] != RHS[I])

513 return false;

514 }

515 return true;

516 }

517 }

518

520 return !(*this == RHS);

521 }

522

523

524

528 setSmallBits(getSmallBits() & RHS.getSmallBits());

529 else if ( isSmall () && RHS .isSmall())

530 getPointer()->operator&=(*RHS.getPointer());

531 else {

533 for (I = 0, E = std::min(size(), RHS.size()); I != E; ++I)

535 for (E = size(); I != E; ++I)

537 }

538 return *this;

539 }

540

541

544 setSmallBits(getSmallBits() & ~RHS.getSmallBits());

545 else if ( isSmall () && RHS .isSmall())

546 getPointer()->reset(*RHS.getPointer());

547 else

548 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)

549 if (RHS.test(i))

551

552 return *this;

553 }

554

555

558 return (getSmallBits() & ~RHS.getSmallBits()) != 0;

560 return getPointer()->test(*RHS.getPointer());

561

562 unsigned i, e;

563 for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)

564 if (test(i) && RHS .test(i))

565 return true;

566

567 for (e = size(); i != e; ++i)

569 return true;

570

571 return false;

572 }

573

577 setSmallBits(getSmallBits() | RHS.getSmallBits());

578 else if ( isSmall () && RHS .isSmall())

579 getPointer()->operator|=(*RHS.getPointer());

580 else {

583 }

584 return *this;

585 }

586

590 setSmallBits(getSmallBits() ^ RHS.getSmallBits());

591 else if ( isSmall () && RHS .isSmall())

592 getPointer()->operator^=(*RHS.getPointer());

593 else {

596 }

597 return *this;

598 }

599

602 setSmallBits(getSmallBits() << N);

603 else

604 getPointer()->operator<<=(N);

605 return *this;

606 }

607

610 setSmallBits(getSmallBits() >> N);

611 else

612 getPointer()->operator>>=(N);

613 return *this;

614 }

615

616

619 if (RHS.isSmall())

620 X = RHS.X;

621 else

622 switchToLarge(new BitVector(*RHS.getPointer()));

623 } else {

624 if ( RHS .isSmall())

625 *getPointer() = *RHS.getPointer();

626 else {

627 delete getPointer();

628 X = RHS.X;

629 }

630 }

631 return *this;

632 }

633

635 if (this != &RHS) {

638 }

639 return *this;

640 }

641

645

646

647

650 applyMask<true, false>(Mask, MaskWords);

651 else

652 getPointer()->setBitsInMask(Mask, MaskWords);

653 }

654

655

656

659 applyMask<false, false>(Mask, MaskWords);

660 else

661 getPointer()->clearBitsInMask(Mask, MaskWords);

662 }

663

664

665

668 applyMask<true, true>(Mask, MaskWords);

669 else

670 getPointer()->setBitsNotInMask(Mask, MaskWords);

671 }

672

673

674

677 applyMask<false, true>(Mask, MaskWords);

678 else

679 getPointer()->clearBitsNotInMask(Mask, MaskWords);

680 }

681

684 X = (uintptr_t)-1;

685 }

686 bool isInvalid() const { return X == (uintptr_t)-1; }

687

690 return getPointer()->getData();

691 Store = getSmallBits();

692 return Store;

693 }

694

695private:

696 template <bool AddBits, bool InvertMask>

697 void applyMask(const uint32_t *Mask, unsigned MaskWords) {

698 assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");

699 uintptr_t M = Mask[0];

700 if (NumBaseBits == 64)

701 M |= uint64_t(Mask[1]) << 32;

702 if (InvertMask)

703 M = ~M;

704 if (AddBits)

705 setSmallBits(getSmallBits() | M);

706 else

707 setSmallBits(getSmallBits() & ~M);

708 }

709};

710

714 Result &= RHS;

715 return Result;

716}

717

718inline SmallBitVector

721 Result |= RHS;

722 return Result;

723}

724

725inline SmallBitVector

728 Result ^= RHS;

729 return Result;

730}

731

740 uintptr_t Store;

742 std::pair<SmallBitVector::size_type, ArrayRef<uintptr_t>>>::

743 getHashValue(std::make_pair(V.size(), V.getData(Store)));

744 }

746 if (LHS.isInvalid() || RHS.isInvalid())

747 return LHS.isInvalid() == RHS.isInvalid();

749 }

750};

751}

752

753namespace std {

754

755

756inline void

760

761}

762

763#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file implements the BitVector class.

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

Value * getPointer(Value *Ptr)

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Definition SmallBitVector.h:67

reference(SmallBitVector &b, unsigned Idx)

Definition SmallBitVector.h:72

reference & operator=(bool t)

Definition SmallBitVector.h:81

reference & operator=(reference t)

Definition SmallBitVector.h:76

reference(const reference &)=default

This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...

Definition SmallBitVector.h:35

SmallBitVector & flip()

Definition SmallBitVector.h:434

reference operator[](unsigned Idx)

Definition SmallBitVector.h:456

int find_last_unset() const

Definition SmallBitVector.h:262

bool operator[](unsigned Idx) const

Definition SmallBitVector.h:461

int find_first() const

Returns the index of the first set bit, -1 if none of the bits are set.

Definition SmallBitVector.h:230

void push_back(bool Val)

Definition SmallBitVector.h:479

SmallBitVector & set()

Definition SmallBitVector.h:366

int find_last() const

Definition SmallBitVector.h:240

void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)

Clear any bits in this vector that are set in Mask.

Definition SmallBitVector.h:657

bool test(const SmallBitVector &RHS) const

Check if (This - RHS) is zero. This is the same as reset(RHS) and any().

Definition SmallBitVector.h:556

SmallBitVector & reset(unsigned I, unsigned E)

Efficiently reset a range of bits in [I, E)

Definition SmallBitVector.h:419

void invalid()

Definition SmallBitVector.h:682

void swap(SmallBitVector &RHS)

Definition SmallBitVector.h:642

void reserve(unsigned N)

Definition SmallBitVector.h:348

int find_prev(unsigned PriorTo) const

find_prev - Returns the index of the first set bit that precedes the the bit at PriorTo.

Definition SmallBitVector.h:308

SmallBitVector & set(unsigned I, unsigned E)

Efficiently set a range of bits in [I, E)

Definition SmallBitVector.h:387

SmallBitVector(SmallBitVector &&RHS)

Definition SmallBitVector.h:163

const_set_bits_iterator set_iterator

Definition SmallBitVector.h:173

bool test(unsigned Idx) const

Definition SmallBitVector.h:474

SmallBitVector()=default

Creates an empty bitvector.

SmallBitVector & operator&=(const SmallBitVector &RHS)

Definition SmallBitVector.h:525

void setBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)

Add '1' bits from Mask to this vector.

Definition SmallBitVector.h:648

bool back() const

Return the last element in the vector.

Definition SmallBitVector.h:469

const SmallBitVector & operator=(SmallBitVector &&RHS)

Definition SmallBitVector.h:634

SmallBitVector(unsigned s, bool t=false)

Creates a bitvector of specified number of bits.

Definition SmallBitVector.h:148

iterator_range< const_set_bits_iterator > set_bits() const

Definition SmallBitVector.h:183

SmallBitVector(const SmallBitVector &RHS)

SmallBitVector copy ctor.

Definition SmallBitVector.h:156

void clear()

Clear all bits.

Definition SmallBitVector.h:325

SmallBitVector & operator<<=(unsigned N)

Definition SmallBitVector.h:600

int find_next(unsigned Prev) const

Returns the index of the next set bit following the "Prev" bit.

Definition SmallBitVector.h:277

SmallBitVector & reset(const SmallBitVector &RHS)

Reset bits that are set in RHS. Same as *this &= ~RHS.

Definition SmallBitVector.h:542

SmallBitVector & reset(unsigned Idx)

Definition SmallBitVector.h:410

uintptr_t size_type

Definition SmallBitVector.h:64

const SmallBitVector & operator=(const SmallBitVector &RHS)

Definition SmallBitVector.h:617

const_set_bits_iterator_impl< SmallBitVector > const_set_bits_iterator

Definition SmallBitVector.h:172

bool all() const

Returns true if all bits are set.

Definition SmallBitVector.h:216

bool operator==(const SmallBitVector &RHS) const

Definition SmallBitVector.h:503

ArrayRef< uintptr_t > getData(uintptr_t &Store) const

Definition SmallBitVector.h:688

SmallBitVector & operator>>=(unsigned N)

Definition SmallBitVector.h:608

int find_first_unset() const

Returns the index of the first unset bit, -1 if all of the bits are set.

Definition SmallBitVector.h:251

size_type size() const

Returns the number of bits in this bitvector.

Definition SmallBitVector.h:195

void resize(unsigned N, bool t=false)

Grow or shrink the bitvector.

Definition SmallBitVector.h:332

bool any() const

Returns true if any bit is set.

Definition SmallBitVector.h:209

void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)

Add a bit to this vector for every '0' bit in Mask.

Definition SmallBitVector.h:666

bool empty() const

Tests whether there are no bits in this bitvector.

Definition SmallBitVector.h:190

~SmallBitVector()

Definition SmallBitVector.h:167

bool isInvalid() const

Definition SmallBitVector.h:686

const_set_bits_iterator set_bits_end() const

Definition SmallBitVector.h:179

bool isSmall() const

Definition SmallBitVector.h:187

SmallBitVector & flip(unsigned Idx)

Definition SmallBitVector.h:442

void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)

Clear a bit in this vector for every '0' bit in Mask.

Definition SmallBitVector.h:675

SmallBitVector & operator|=(const SmallBitVector &RHS)

Definition SmallBitVector.h:574

size_type count() const

Returns the number of bits which are set.

Definition SmallBitVector.h:200

bool anyCommon(const SmallBitVector &RHS) const

Test if any common bits are set.

Definition SmallBitVector.h:490

int find_next_unset(unsigned Prev) const

Returns the index of the next unset bit following the "Prev" bit.

Definition SmallBitVector.h:291

const_set_bits_iterator set_bits_begin() const

Definition SmallBitVector.h:175

void pop_back()

Pop one bit from the end of the vector.

Definition SmallBitVector.h:484

SmallBitVector & set(unsigned Idx)

Definition SmallBitVector.h:374

SmallBitVector & reset()

Definition SmallBitVector.h:402

SmallBitVector operator~() const

Definition SmallBitVector.h:451

bool none() const

Returns true if none of the bits are set.

Definition SmallBitVector.h:223

SmallBitVector & operator^=(const SmallBitVector &RHS)

Definition SmallBitVector.h:587

bool operator!=(const SmallBitVector &RHS) const

Definition SmallBitVector.h:519

ForwardIterator for the bits that are set.

A range adaptor for a pair of iterators.

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

This is an optimization pass for GlobalISel generic memory operations.

APInt operator&(APInt a, const APInt &b)

int countr_one(T Value)

Count the number of ones from the least significant bit to the first zero bit.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

constexpr int popcount(T Value) noexcept

Count the number of set bits in a value.

int countr_zero(T Val)

Count number of 0's from the least significant bit to the most stopping at the first 1.

int countl_zero(T Val)

Count number of 0's from the most significant bit to the least stopping at the first 1.

APInt operator^(APInt a, const APInt &b)

int countl_one(T Value)

Count the number of ones from the most significant bit to the first zero bit.

APInt operator|(APInt a, const APInt &b)

constexpr T maskTrailingOnes(unsigned N)

Create a bitmask with the N right-most bits set to 1, and all other bits set to 0.

Implement std::hash so that hash_code can be used in STL containers.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

static SmallBitVector getTombstoneKey()

Definition SmallBitVector.h:734

static SmallBitVector getEmptyKey()

Definition SmallBitVector.h:733

static unsigned getHashValue(const SmallBitVector &V)

Definition SmallBitVector.h:739

static bool isEqual(const SmallBitVector &LHS, const SmallBitVector &RHS)

Definition SmallBitVector.h:745

An information struct used to provide DenseMap with the various necessary components for a given valu...