Google OR-Tools: ortools/util/bitset.h Source File

16#ifndef ORTOOLS_UTIL_BITSET_H_

17#define ORTOOLS_UTIL_BITSET_H_

19#include <string.h>

21#include <algorithm>

22#include <cstddef>

23#include <cstdint>

24#include <iterator>

25#include <string>

26#include <tuple>

27#include <vector>

29#include "absl/log/check.h"

36static const uint64_t kAllBits64 = uint64_t{0xFFFFFFFFFFFFFFFF};

38static const uint32_t kAllBits32 = 0xFFFFFFFFU;

41inline uint64_t OneBit64(int pos) { return uint64_t{1} << pos; }

42inline uint32_t OneBit32(int pos) { return 1U << pos; }

46 const uint64_t m1 = uint64_t{0x5555555555555555};

47 const uint64_t m2 = uint64_t{0x3333333333333333};

48 const uint64_t m4 = uint64_t{0x0F0F0F0F0F0F0F0F};

49 const uint64_t h01 = uint64_t{0x0101010101010101};

50 n -= (n >> 1) & m1;

51 n = (n & m2) + ((n >> 2) & m2);

52 n = (n + (n >> 4)) & m4;

53 n = (n * h01) >> 56;

54 return n;

55}

57 n -= (n >> 1) & 0x55555555UL;

58 n = (n & 0x33333333) + ((n >> 2) & 0x33333333UL);

59 n = (n + (n >> 4)) & 0x0F0F0F0FUL;

60 n = n + (n >> 8);

61 n = n + (n >> 16);

62 return n & 0x0000003FUL;

63}

73#define USE_DEBRUIJN true

74#if defined(__GNUC__) || defined(__llvm__)

75#define USE_FAST_LEAST_SIGNIFICANT_BIT true

76#endif

78#if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)

79inline int LeastSignificantBitPosition64Fast(uint64_t n) {

80 return __builtin_ctzll(n);

81}

82#endif

85 static const uint64_t kSeq = uint64_t{0x0218a392dd5fb34f};

86 static const int kTab[64] = {

88 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 52, 20, 58,

89 5, 17, 26, 56, 15, 38, 29, 40, 10, 49, 53, 31, 21, 34, 59, 42,

90 63, 6, 12, 18, 24, 27, 51, 57, 16, 55, 37, 39, 48, 30, 33, 41,

91 62, 11, 23, 50, 54, 36, 47, 32, 61, 22, 35, 46, 60, 45, 44, 43,

92 };

93 return kTab[((n & (~n + 1)) * kSeq) >> 58];

94}

97 DCHECK_NE(n, 0);

98 int pos = 63;

99 if (n & 0x00000000FFFFFFFFLL) {

100 pos -= 32;

101 } else {

102 n >>= 32;

103 }

104 if (n & 0x000000000000FFFFLL) {

105 pos -= 16;

106 } else {

107 n >>= 16;

108 }

109 if (n & 0x00000000000000FFLL) {

110 pos -= 8;

111 } else {

112 n >>= 8;

113 }

114 if (n & 0x000000000000000FLL) {

115 pos -= 4;

116 } else {

117 n >>= 4;

118 }

119 if (n & 0x0000000000000003LL) {

120 pos -= 2;

121 } else {

122 n >>= 2;

123 }

124 if (n & 0x0000000000000001LL) {

125 pos -= 1;

126 }

127 return pos;

128}

129

131 DCHECK_NE(n, 0);

132#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT

133 return LeastSignificantBitPosition64Fast(n);

134#elif defined(USE_DEBRUIJN)

136#else

138#endif

139}

140

141#if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)

142inline int LeastSignificantBitPosition32Fast(uint32_t n) {

143 return __builtin_ctzl(n);

144}

145#endif

146

148 static const uint32_t kSeq = 0x077CB531U;

149 static const int kTab[32] = {

150 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20,

151 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,

152 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};

153 return kTab[((n & (~n + 1)) * kSeq) >> 27];

154}

155

157 DCHECK_NE(n, 0);

158 int pos = 31;

159 if (n & 0x0000FFFFL) {

160 pos -= 16;

161 } else {

162 n >>= 16;

163 }

164 if (n & 0x000000FFL) {

165 pos -= 8;

166 } else {

167 n >>= 8;

168 }

169 if (n & 0x0000000FL) {

170 pos -= 4;

171 } else {

172 n >>= 4;

173 }

174 if (n & 0x00000003L) {

175 pos -= 2;

176 } else {

177 n >>= 2;

178 }

179 if (n & 0x00000001L) {

180 pos -= 1;

181 }

182 return pos;

183}

184

186 DCHECK_NE(n, 0);

187#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT

188 return LeastSignificantBitPosition32Fast(n);

189#elif defined(USE_DEBRUIJN)

191#else

193#endif

194}

195

196

197#if USE_FAST_LEAST_SIGNIFICANT_BIT

198inline int MostSignificantBitPosition64Fast(uint64_t n) {

199

200

201 const int offset = __builtin_clzll(1);

202 return n == 0 ? 0 : (offset - __builtin_clzll(n));

203}

204#endif

205

207 int b = 0;

208 if (0 != (n & (kAllBits64 << (1 << 5)))) {

209 b |= (1 << 5);

210 n >>= (1 << 5);

211 }

212 if (0 != (n & (kAllBits64 << (1 << 4)))) {

213 b |= (1 << 4);

214 n >>= (1 << 4);

215 }

216 if (0 != (n & (kAllBits64 << (1 << 3)))) {

217 b |= (1 << 3);

218 n >>= (1 << 3);

219 }

220 if (0 != (n & (kAllBits64 << (1 << 2)))) {

221 b |= (1 << 2);

222 n >>= (1 << 2);

223 }

224 if (0 != (n & (kAllBits64 << (1 << 1)))) {

225 b |= (1 << 1);

226 n >>= (1 << 1);

227 }

228 if (0 != (n & (kAllBits64 << (1 << 0)))) {

229 b |= (1 << 0);

230 }

231 return b;

232}

233

235#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT

236 return MostSignificantBitPosition64Fast(n);

237#else

239#endif

240}

241

242#if USE_FAST_LEAST_SIGNIFICANT_BIT

243inline int MostSignificantBitPosition32Fast(uint32_t n) {

244

245

246

247 const int offset = __builtin_clzl(1);

248 return n == 0 ? 0 : (offset - __builtin_clzl(n));

249}

250#endif

251

253 int b = 0;

254 if (0 != (n & (kAllBits32 << (1 << 4)))) {

255 b |= (1 << 4);

256 n >>= (1 << 4);

257 }

258 if (0 != (n & (kAllBits32 << (1 << 3)))) {

259 b |= (1 << 3);

260 n >>= (1 << 3);

261 }

262 if (0 != (n & (kAllBits32 << (1 << 2)))) {

263 b |= (1 << 2);

264 n >>= (1 << 2);

265 }

266 if (0 != (n & (kAllBits32 << (1 << 1)))) {

267 b |= (1 << 1);

268 n >>= (1 << 1);

269 }

270 if (0 != (n & (kAllBits32 << (1 << 0)))) {

271 b |= (1 << 0);

272 }

273 return b;

274}

275

277#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT

278 return MostSignificantBitPosition32Fast(n);

279#else

281#endif

282}

283

284#undef USE_DEBRUIJN

285#undef USE_FAST_LEAST_SIGNIFICANT_BIT

286

287

288inline uint64_t OneRange64(uint64_t s, uint64_t e) {

289 DCHECK_LE(s, 63);

290 DCHECK_LE(e, 63);

291 DCHECK_LE(s, e);

293}

294

295inline uint32_t OneRange32(uint32_t s, uint32_t e) {

296 DCHECK_LE(s, 31);

297 DCHECK_LE(e, 31);

298 DCHECK_LE(s, e);

300}

301

302

304 DCHECK_LE(s, 63);

306}

307

309 DCHECK_LE(s, 31);

311}

312

313

315 DCHECK_LE(s, 63);

317}

318

320 DCHECK_LE(s, 31);

322}

323

324

325

326

327

328

329

330

331

332

333inline uint32_t BitPos64(uint64_t pos) { return (pos & 63); }

334inline uint32_t BitPos32(uint32_t pos) { return (pos & 31); }

335

336

337inline uint64_t BitOffset64(uint64_t pos) { return (pos >> 6); }

338inline uint32_t BitOffset32(uint32_t pos) { return (pos >> 5); }

339

340

341inline uint64_t BitLength64(uint64_t size) { return ((size + 63) >> 6); }

342inline uint32_t BitLength32(uint32_t size) { return ((size + 31) >> 5); }

343

344

345inline uint64_t BitShift64(uint64_t v) { return v << 6; }

346inline uint32_t BitShift32(uint32_t v) { return v << 5; }

347

348

349inline bool IsBitSet64(const uint64_t* const bitset, uint64_t pos) {

351}

352inline bool IsBitSet32(const uint32_t* const bitset, uint32_t pos) {

354}

355

356

357inline void SetBit64(uint64_t* const bitset, uint64_t pos) {

359}

360inline void SetBit32(uint32_t* const bitset, uint32_t pos) {

362}

363

364

365inline void ClearBit64(uint64_t* const bitset, uint64_t pos) {

367}

368inline void ClearBit32(uint32_t* const bitset, uint32_t pos) {

370}

371

372

375

376

379

380

382 uint64_t end);

384 uint32_t end);

385

386

388 uint64_t end);

390 uint32_t end);

391

392

393

395 uint64_t start, uint64_t end);

397 uint32_t start, uint32_t end);

398

400 uint64_t start, uint64_t end);

402 uint32_t start, uint32_t end);

403

404

406 return uint64_t{3} << (pos & 62);

407}

408

409

410

411

412

413

414template <typename IndexType = int64_t>

416 public:

418

419

421 public:

423

427

428 const uint64_t* data() const { return data_; }

429

430 private:

431 const uint64_t* const data_;

432 };

433

435 public:

436 explicit View(Bitset64* bitset) : data_(bitset->data_.data()) {}

437

441

445

446 void Set(IndexType i) {

448 }

449

450 private:

451 uint64_t* const data_;

452 };

453

456 : size_(Value(size) > 0 ? size : IndexType(0)),

458

459 ConstView const_view() const { return ConstView(this); }

460 View view() { return View(this); }

461

462

463 IndexType size() const { return size_; }

464

465

467 ++size_;

468 data_.resize(BitLength64(Value(size_)), 0);

469 Set(size_ - 1, value);

470 }

471

472

475 DCHECK_GE(Value(size), 0);

476 IndexType new_size = Value(size) > 0 ? size : IndexType(0);

477 if (new_size < size_ && Value(new_size) > 0) {

478 const int64_t new_data_size = BitLength64(Value(new_size));

480 << BitPos64(Value(new_size) - 1);

481 data_[new_data_size - 1] &= ~bitmask;

482 }

483 size_ = new_size;

484 data_.resize(BitLength64(Value(size_)), 0);

485 }

486

487

489 DCHECK_GE(Value(size), 0);

490 size_ = Value(size) > 0 ? size : IndexType(0);

491

492

493

494

495 const size_t bit_length = static_cast<size_t>(BitLength64(Value(size_)));

496 const size_t to_clear = std::min(data_.size(), bit_length);

497 data_.resize(bit_length, 0);

498 memset(data_.data(), 0, to_clear * sizeof(int64_t));

499 }

500

501

502 void ClearAll() { memset(data_.data(), 0, data_.size() * sizeof(int64_t)); }

503

504

506 DCHECK_GE(Value(i), 0);

507 DCHECK_LT(Value(i), Value(size_));

509 }

510

511

513 DCHECK_GE(Value(i), 0);

514 DCHECK_LT(Value(i), Value(size_));

516 }

517

518

520 DCHECK_GE(Value(i), 0);

521 DCHECK_LT(Value(i), Value(size_));

523 }

524

525

527 DCHECK_GE(Value(i), 0);

528 DCHECK_LT(Value(i), Value(size_));

530 }

531

532

533 bool IsSet(IndexType i) const {

534 DCHECK_GE(Value(i), 0);

535 DCHECK_LT(Value(i), Value(size_));

537 }

538

539

541

542

543 void Set(IndexType i) {

544 DCHECK_GE(Value(i), 0);

545 DCHECK_LT(Value(i), size_);

546

548 }

549

550

551 void Set(IndexType i, bool value) {

552 if (value) {

554 } else {

556 }

557 }

558

559

561 const uint64_t offset = BitOffset64(Value(i));

562 data_[offset] = other.data_[offset];

563 }

564

565

566

567

568 template <typename OtherIndexType>

570 const int64_t min_size = std::min(data_.size(), other.data_.size());

571 if (min_size == 0) return;

572 const uint64_t last_common_bucket = data_[min_size - 1];

573 memcpy(data_.data(), other.data_.data(), min_size * sizeof(uint64_t));

574 if (data_.size() >= other.data_.size()) {

577 data_[min_size - 1] &= ~bitmask;

578 data_[min_size - 1] |= (bitmask & last_common_bucket);

579 }

580 }

581

582

583 template <typename OtherIndexType>

585 DCHECK_EQ(Value(size()), other.Value(other.size()));

586 memcpy(data_.data(), other.data_.data(), data_.size() * sizeof(uint64_t));

587 }

588

589

590

591

593 const int min_size = std::min(data_.size(), other.data_.size());

594 uint64_t* const d = data_.data();

595 const uint64_t* const o = other.data_.data();

596 for (int i = 0; i < min_size; ++i) {

597 d[i] &= o[i];

598 }

599 for (int i = min_size; i < data_.size(); ++i) {

600 d[i] = 0;

601 }

602 }

603

604

607 DCHECK_EQ(a.size(), b.size());

609

610

611 const int num_buckets = a.data_.size();

612 for (int i = 0; i < num_buckets; ++i) {

613 data_[i] = a.data_[i] & b.data_[i];

614 }

615 }

616

617

618

619

621 const int min_size = std::min(data_.size(), other.data_.size());

622 for (int i = 0; i < min_size; ++i) {

623 data_[i] |= other.data_[i];

624 }

625 }

626

627

628

629

630

632 public:

633

634

645

647 : data_(bitset.data_.data()), size_(bitset.data_.size()) {

648 if (!bitset.data_.empty()) {

649 current_ = data_[0];

650 this->operator++();

651 }

652 }

653

655 return Iterator(bitset.data_.data());

656 }

657

660 if (other.size_ == 0) {

661 return size_ != 0;

662 }

663 return std::tie(index_, current_) !=

664 std::tie(other.index_, other.current_);

665 }

666

667 IndexType operator*() const { return IndexType(index_); }

668

671 ++(*this);

672 return other;

673 }

674

677 while (current_ == 0) {

678 bucket++;

679 if (bucket == size_) {

680 size_ = 0;

681 return *this;

682 }

683 current_ = data_[bucket];

684 }

685

686

688 current_ &= current_ - 1;

689 return *this;

690 }

691

692 private:

693 explicit Iterator(const uint64_t* data) : data_(data), size_(0) {}

694

695 const uint64_t* data_;

696 int size_;

697 int index_ = 0;

698 uint64_t current_ = 0;

699 };

700

701

702

703 Iterator begin() const { return Iterator(*this); }

705

706

707

710 uint64_t use2,

712 DCHECK(use1 == 0 || use1 == 1);

713 DCHECK(use2 == 0 || use2 == 1);

714 const int bucket = BitOffset64(Value(i));

715 const int pos = BitPos64(Value(i));

716 return ((use1 << pos) & set1.data()[bucket]) ^

717 ((use2 << pos) & set2.data()[bucket]);

718 }

719

720

722 std::string output;

723 for (IndexType i(0); i < size(); ++i) {

724 output += IsSet(i) ? "1" : "0";

725 }

726 return output;

727 }

728

730 return std::all_of(data_.begin(), data_.end(),

731 [](uint64_t v) { return v == 0; });

732 }

733

734 private:

735

736

737 static int Value(IndexType input);

738

739 IndexType size_;

740 std::vector<uint64_t> data_;

741

742 template <class OtherIndexType>

744};

745

746

747

749 public:

752 : size_(size), top_(-1), data_(BitLength64(size), 0) {}

753

754

757

759 CHECK_GE(size, size_);

760 size_ = size;

762 }

763

765 top_ = -1;

766 size_ = size;

768 }

769

771 DCHECK_GE(i, 0);

772 DCHECK_LT(i, size_);

773 top_ = std::max(top_, i);

775 }

776

777

779 DCHECK_GE(i, 0);

780 DCHECK_LT(i, size_);

781 top_ = std::max(top_, i - 1);

782 int bucket_index = static_cast<int>(BitOffset64(i));

784 for (--bucket_index; bucket_index >= 0; --bucket_index) {

786 }

787 }

788

789

790 int Top() const { return top_; }

791

792

794 DCHECK_NE(top_, -1);

795 int bucket_index = static_cast<int>(BitOffset64(top_));

796 uint64_t bucket = data_[bucket_index] &= ~OneBit64(BitPos64(top_));

797 while (!bucket) {

798 if (bucket_index == 0) {

799 top_ = -1;

800 return;

801 }

802 bucket = data_[--bucket_index];

803 }

804

805

806

807

808 top_ = static_cast<int>(BitShift64(bucket_index) +

810 }

811

812 private:

813 int size_;

814 int top_;

815 std::vector<uint64_t> data_;

816};

817

818

819template <typename IntType>

820inline int Bitset64<IntType>::Value(IntType input) {

821 DCHECK_GE(input.value(), 0);

822 return input.value();

823}

824template <>

825inline int Bitset64<int>::Value(int input) {

826 DCHECK_GE(input, 0);

828}

829template <>

830inline int Bitset64<int64_t>::Value(int64_t input) {

831 DCHECK_GE(input, 0);

833}

834template <>

835inline int Bitset64<size_t>::Value(size_t input) {

837}

838

839

840

841template <typename IntegerType = int64_t>

843 public:

846

847

850 IntegerType size() const { return bitset_.size(); }

853

854 const int kSparseThreshold = 300;

855 if (to_clear_.size() * kSparseThreshold < size) {

856 for (const IntegerType i : to_clear_) bitset_.ClearBucket(i);

857 to_clear_.clear();

858 bitset_.Resize(size);

859 } else {

860 bitset_.ClearAndResize(size);

861 to_clear_.clear();

862 }

863 }

865 if (size < bitset_.size()) {

866 int new_index = 0;

867 for (IntegerType index : to_clear_) {

868 if (index < size) {

869 to_clear_[new_index] = index;

870 ++new_index;

871 }

872 }

873 to_clear_.resize(new_index);

874 }

875 bitset_.Resize(size);

876 }

877 bool operator[](IntegerType index) const { return bitset_[index]; }

878 void Set(IntegerType index) {

879 if (!bitset_[index]) {

880 bitset_.Set(index);

881 to_clear_.push_back(index);

882 }

883 }

884

886 bitset_.ClearAndResize(other.size());

887 bitset_.SetContentFromBitsetOfSameSize(other.bitset_);

888 to_clear_.assign(other.to_clear_.begin(), other.to_clear_.end());

889 }

890

891

894 return bitset_.const_view();

895 }

897 view.Set(index);

898 to_clear_.push_back(index);

899 }

900

901 void Clear(IntegerType index) { bitset_.Clear(index); }

903 return to_clear_.size();

904 }

906 return to_clear_;

907 }

908

909

910

911

912

913

914

916#if !defined(NDEBUG)

917 for (IntegerType index : to_clear_) CHECK(!bitset_[index]);

918#endif

919 to_clear_.clear();

920 }

921

923 return bitset_.const_view();

924 }

925

926 private:

928 std::vector<IntegerType> to_clear_;

929};

930

931}

932

933#endif

BitQueue64(int size)

Definition bitset.h:751

int Top() const

Definition bitset.h:790

void Set(int i)

Definition bitset.h:770

void ClearAndResize(int size)

Definition bitset.h:764

void ClearTop()

Definition bitset.h:793

BitQueue64(const BitQueue64 &)=delete

void IncreaseSize(int size)

Definition bitset.h:758

BitQueue64 & operator=(const BitQueue64 &)=delete

void SetAllBefore(int i)

Definition bitset.h:778

BitQueue64()

Definition bitset.h:750

const uint64_t * data() const

Definition bitset.h:428

bool operator[](IndexType i) const

Definition bitset.h:424

ConstView(const Bitset64 *bitset)

Definition bitset.h:422

Iterator & operator++()

Definition bitset.h:675

Iterator(const Iterator &other)=default

value_type * pointer

Definition bitset.h:644

bool operator==(const Iterator &other) const

Definition bitset.h:658

bool operator!=(const Iterator &other) const

Definition bitset.h:659

std::forward_iterator_tag iterator_category

Definition bitset.h:640

Iterator(Iterator &&other)=default

std::size_t size_type

Definition bitset.h:642

Iterator & operator=(const Iterator &other)=default

std::ptrdiff_t difference_type

Definition bitset.h:639

IndexType operator*() const

Definition bitset.h:667

Iterator operator++(int)

Definition bitset.h:669

static Iterator EndIterator(const Bitset64 &bitset)

Definition bitset.h:654

IndexType value_type

Definition bitset.h:641

value_type & reference

Definition bitset.h:643

Iterator()

Definition bitset.h:635

Iterator(const Bitset64 &bitset)

Definition bitset.h:646

bool operator[](IndexType i) const

Definition bitset.h:438

void Set(IndexType i)

Definition bitset.h:446

void Clear(IndexType i)

Definition bitset.h:442

View(Bitset64 *bitset)

Definition bitset.h:436

void CopyBucket(const Bitset64< IndexType > &other, IndexType i)

Definition bitset.h:560

View view()

Definition bitset.h:460

void ClearAll()

Definition bitset.h:502

void ClearBucket(IndexType i)

Definition bitset.h:512

void SetContentFromBitset(const Bitset64< OtherIndexType > &other)

Definition bitset.h:569

bool IsSet(IndexType i) const

Definition bitset.h:533

ColIndex size() const

Definition bitset.h:463

void Clear(IndexType i)

Definition bitset.h:505

void Set(IndexType i, bool value)

Definition bitset.h:551

void Union(const Bitset64< IndexType > &other)

Definition bitset.h:620

void Intersection(const Bitset64< IndexType > &other)

Definition bitset.h:592

Iterator end() const

Definition bitset.h:704

ColIndex value_type

Definition bitset.h:417

Iterator begin() const

Definition bitset.h:703

void resize(int size)

Definition bitset.h:473

std::string DebugString() const

Definition bitset.h:721

static uint64_t ConditionalXorOfTwoBits(IndexType i, uint64_t use1, Bitset64< IndexType >::ConstView set1, uint64_t use2, Bitset64< IndexType >::ConstView set2)

Definition bitset.h:708

void ClearTwoBits(IndexType i)

Definition bitset.h:519

Bitset64(IndexType size)

Definition bitset.h:455

void Resize(IndexType size)

Definition bitset.h:474

bool AreOneOfTwoBitsSet(IndexType i) const

Definition bitset.h:526

Bitset64()

Definition bitset.h:454

friend class Bitset64

Definition bitset.h:743

void SetToIntersectionOf(const Bitset64< IndexType > &a, const Bitset64< IndexType > &b)

Definition bitset.h:605

void ClearAndResize(IndexType size)

Definition bitset.h:488

void PushBack(bool value)

Definition bitset.h:466

bool operator[](IndexType i) const

Definition bitset.h:540

void SetContentFromBitsetOfSameSize(const Bitset64< OtherIndexType > &other)

Definition bitset.h:584

ConstView const_view() const

Definition bitset.h:459

bool IsAllFalse() const

Definition bitset.h:729

void Set(IndexType i)

Definition bitset.h:543

Bitset64< IntegerType >::ConstView BitsetConstView()

Definition bitset.h:893

void ClearAndResize(IntegerType size)

Definition bitset.h:852

void CopyFrom(const SparseBitset &other)

Definition bitset.h:885

const std::vector< IntegerType > & PositionsSetAtLeastOnce() const

Definition bitset.h:905

void Clear(IntegerType index)

Definition bitset.h:901

bool operator[](IntegerType index) const

Definition bitset.h:877

SparseBitset & operator=(const SparseBitset &)=delete

Bitset64< IntegerType >::ConstView const_view() const

Definition bitset.h:922

SparseBitset(IntegerType size)

Definition bitset.h:845

void Set(IntegerType index)

Definition bitset.h:878

Bitset64< IntegerType >::View BitsetView()

Definition bitset.h:892

void NotifyAllClear()

Definition bitset.h:915

SparseBitset()

Definition bitset.h:844

int NumberOfSetCallsWithDifferentArguments() const

Definition bitset.h:902

void ResetAllToFalse()

Definition bitset.h:851

SparseBitset(const SparseBitset &)=delete

IntegerType size() const

Definition bitset.h:850

void Resize(IntegerType size)

Definition bitset.h:864

void SetUnsafe(typename Bitset64< IntegerType >::View view, IntegerType index)

Definition bitset.h:896

uint32_t IntervalDown32(uint32_t s)

Definition bitset.h:319

int64_t UnsafeMostSignificantBitPosition64(const uint64_t *bitset, uint64_t start, uint64_t end)

uint32_t BitCountRange32(const uint32_t *bitset, uint32_t start, uint32_t end)

int LeastSignificantBitPosition32Default(uint32_t n)

Definition bitset.h:156

void SetBit32(uint32_t *const bitset, uint32_t pos)

Definition bitset.h:360

int64_t UnsafeLeastSignificantBitPosition64(const uint64_t *bitset, uint64_t start, uint64_t end)

uint32_t BitLength32(uint32_t size)

Definition bitset.h:342

static const uint32_t kAllBits32

Definition bitset.h:38

bool IsEmptyRange32(const uint32_t *bitset, uint32_t start, uint32_t end)

uint32_t BitCount32(uint32_t n)

Definition bitset.h:56

int32_t UnsafeLeastSignificantBitPosition32(const uint32_t *bitset, uint32_t start, uint32_t end)

int LeastSignificantBitPosition64DeBruijn(uint64_t n)

Definition bitset.h:84

int MostSignificantBitPosition32Default(uint32_t n)

Definition bitset.h:252

int LeastSignificantBitPosition64Default(uint64_t n)

Definition bitset.h:96

bool IsBitSet32(const uint32_t *const bitset, uint32_t pos)

Definition bitset.h:352

uint32_t BitPos32(uint32_t pos)

Definition bitset.h:334

ClosedInterval::Iterator end(ClosedInterval interval)

uint64_t BitShift64(uint64_t v)

Definition bitset.h:345

uint32_t BitOffset32(uint32_t pos)

Definition bitset.h:338

uint32_t LeastSignificantBitWord32(uint32_t n)

Definition bitset.h:67

uint64_t IntervalDown64(uint64_t s)

Definition bitset.h:314

uint32_t IntervalUp32(uint32_t s)

Definition bitset.h:308

void ClearBit32(uint32_t *const bitset, uint32_t pos)

Definition bitset.h:368

static const uint64_t kAllBits64

Definition bitset.h:36

int LeastSignificantBitPosition32DeBruijn(uint32_t n)

Definition bitset.h:147

void ClearBit64(uint64_t *const bitset, uint64_t pos)

Definition bitset.h:365

uint32_t OneBit32(int pos)

Definition bitset.h:42

uint64_t OneRange64(uint64_t s, uint64_t e)

Definition bitset.h:288

static const uint64_t kAllBitsButLsb64

Definition bitset.h:37

uint32_t BitShift32(uint32_t v)

Definition bitset.h:346

uint32_t BitPos64(uint64_t pos)

Definition bitset.h:333

uint64_t BitCountRange64(const uint64_t *bitset, uint64_t start, uint64_t end)

uint64_t BitCount64(uint64_t n)

Definition bitset.h:45

int MostSignificantBitPosition32(uint32_t n)

Definition bitset.h:276

bool IsBitSet64(const uint64_t *const bitset, uint64_t pos)

Definition bitset.h:349

uint64_t OneBit64(int pos)

Definition bitset.h:41

uint32_t OneRange32(uint32_t s, uint32_t e)

Definition bitset.h:295

uint64_t BitOffset64(uint64_t pos)

Definition bitset.h:337

bool IsEmptyRange64(const uint64_t *bitset, uint64_t start, uint64_t end)

uint64_t BitLength64(uint64_t size)

Definition bitset.h:341

int LeastSignificantBitPosition64(uint64_t n)

Definition bitset.h:130

int32_t UnsafeMostSignificantBitPosition32(const uint32_t *bitset, uint32_t start, uint32_t end)

int MostSignificantBitPosition64Default(uint64_t n)

Definition bitset.h:206

int LeastSignificantBitPosition32(uint32_t n)

Definition bitset.h:185

void SetBit64(uint64_t *const bitset, uint64_t pos)

Definition bitset.h:357

uint64_t LeastSignificantBitWord64(uint64_t n)

Definition bitset.h:66

uint64_t TwoBitsFromPos64(uint64_t pos)

Definition bitset.h:405

int MostSignificantBitPosition64(uint64_t n)

Definition bitset.h:234

uint64_t IntervalUp64(uint64_t s)

Definition bitset.h:303

static int input(yyscan_t yyscanner)