1 // TR2 <dynamic_bitset> -*- C++ -*- 2 3 // Copyright (C) 2009-2022 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file tr2/dynamic_bitset 26 * This is a TR2 C++ Library header. 27 */ 28 29 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET 30 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1 31 32 #pragma GCC system_header 33 34 #include <limits> 35 #include <vector> 36 #include <string> 37 #include <istream> 38 #include <bits/functexcept.h> 39 #include <bits/stl_algo.h> // For fill 40 #include <bits/cxxabi_forced.h> 41 42 namespace std _GLIBCXX_VISIBILITY(default) 43 { 44 _GLIBCXX_BEGIN_NAMESPACE_VERSION 45 46 namespace tr2 47 { 48 /** 49 * @defgroup dynamic_bitset Dynamic Bitset. 50 * @ingroup extensions 51 * 52 * @{ 53 */ 54 55 /** 56 * Base class, general case. 57 * 58 * See documentation for dynamic_bitset. 59 */ 60 template<typename _WordT = unsigned long long, 61 typename _Alloc = std::allocator<_WordT>> 62 struct __dynamic_bitset_base 63 { 64 static_assert(std::is_unsigned<_WordT>::value, "template argument " 65 "_WordT not an unsigned integral type"); 66 67 typedef _WordT block_type; 68 typedef _Alloc allocator_type; 69 typedef size_t size_type; 70 71 static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type); 72 static const size_type npos = static_cast<size_type>(-1); 73 74 /// 0 is the least significant word. 75 std::vector<block_type, allocator_type> _M_w; 76 77 explicit 78 __dynamic_bitset_base(const allocator_type& __alloc) 79 : _M_w(__alloc) 80 { } 81 82 __dynamic_bitset_base() = default; 83 __dynamic_bitset_base(const __dynamic_bitset_base&) = default; 84 __dynamic_bitset_base(__dynamic_bitset_base&& __b) = default; 85 __dynamic_bitset_base& operator=(const __dynamic_bitset_base&) = default; 86 __dynamic_bitset_base& operator=(__dynamic_bitset_base&&) = default; 87 ~__dynamic_bitset_base() = default; 88 89 explicit 90 __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL, 91 const allocator_type& __alloc = allocator_type()) 92 : _M_w(__nbits / _S_bits_per_block + (__nbits % _S_bits_per_block > 0), 93 block_type(0), __alloc) 94 { 95 if (__nbits < std::numeric_limits<decltype(__val)>::digits) 96 __val &= ~(-1ULL << __nbits); 97 if (__val == 0) 98 return; 99 100 if _GLIBCXX17_CONSTEXPR (sizeof(__val) == sizeof(block_type)) 101 _M_w[0] = __val; 102 else 103 { 104 const size_t __n 105 = std::min(_M_w.size(), sizeof(__val) / sizeof(block_type)); 106 for (size_t __i = 0; __val && __i < __n; ++__i) 107 { 108 _M_w[__i] = static_cast<block_type>(__val); 109 __val >>= _S_bits_per_block; 110 } 111 } 112 } 113 114 void 115 _M_swap(__dynamic_bitset_base& __b) noexcept 116 { this->_M_w.swap(__b._M_w); } 117 118 void 119 _M_clear() noexcept 120 { this->_M_w.clear(); } 121 122 void 123 _M_resize(size_t __nbits, bool __value) 124 { 125 size_t __sz = __nbits / _S_bits_per_block; 126 if (__nbits % _S_bits_per_block > 0) 127 ++__sz; 128 if (__sz != this->_M_w.size()) 129 { 130 block_type __val = 0; 131 if (__value) 132 __val = std::numeric_limits<block_type>::max(); 133 this->_M_w.resize(__sz, __val); 134 } 135 } 136 137 allocator_type 138 _M_get_allocator() const noexcept 139 { return this->_M_w.get_allocator(); } 140 141 static size_type 142 _S_whichword(size_type __pos) noexcept 143 { return __pos / _S_bits_per_block; } 144 145 static size_type 146 _S_whichbyte(size_type __pos) noexcept 147 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; } 148 149 static size_type 150 _S_whichbit(size_type __pos) noexcept 151 { return __pos % _S_bits_per_block; } 152 153 static block_type 154 _S_maskbit(size_type __pos) noexcept 155 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); } 156 157 block_type& 158 _M_getword(size_type __pos) noexcept 159 { return this->_M_w[_S_whichword(__pos)]; } 160 161 block_type 162 _M_getword(size_type __pos) const noexcept 163 { return this->_M_w[_S_whichword(__pos)]; } 164 165 block_type& 166 _M_hiword() noexcept 167 { return this->_M_w[_M_w.size() - 1]; } 168 169 block_type 170 _M_hiword() const noexcept 171 { return this->_M_w[_M_w.size() - 1]; } 172 173 void 174 _M_do_and(const __dynamic_bitset_base& __x) noexcept 175 { 176 if (__x._M_w.size() == this->_M_w.size()) 177 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 178 this->_M_w[__i] &= __x._M_w[__i]; 179 else 180 return; 181 } 182 183 void 184 _M_do_or(const __dynamic_bitset_base& __x) noexcept 185 { 186 if (__x._M_w.size() == this->_M_w.size()) 187 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 188 this->_M_w[__i] |= __x._M_w[__i]; 189 else 190 return; 191 } 192 193 void 194 _M_do_xor(const __dynamic_bitset_base& __x) noexcept 195 { 196 if (__x._M_w.size() == this->_M_w.size()) 197 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 198 this->_M_w[__i] ^= __x._M_w[__i]; 199 else 200 return; 201 } 202 203 void 204 _M_do_dif(const __dynamic_bitset_base& __x) noexcept 205 { 206 if (__x._M_w.size() == this->_M_w.size()) 207 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 208 this->_M_w[__i] &= ~__x._M_w[__i]; 209 else 210 return; 211 } 212 213 void 214 _M_do_left_shift(size_t __shift); 215 216 void 217 _M_do_right_shift(size_t __shift); 218 219 void 220 _M_do_flip() noexcept 221 { 222 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 223 this->_M_w[__i] = ~this->_M_w[__i]; 224 } 225 226 void 227 _M_do_set() noexcept 228 { 229 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 230 this->_M_w[__i] = static_cast<block_type>(-1); 231 } 232 233 void 234 _M_do_reset() noexcept 235 { 236 std::fill(_M_w.begin(), _M_w.end(), static_cast<block_type>(0)); 237 } 238 239 bool 240 _M_is_equal(const __dynamic_bitset_base& __x) const noexcept 241 { 242 if (__x._M_w.size() == this->_M_w.size()) 243 { 244 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 245 if (this->_M_w[__i] != __x._M_w[__i]) 246 return false; 247 return true; 248 } 249 else 250 return false; 251 } 252 253 bool 254 _M_is_less(const __dynamic_bitset_base& __x) const noexcept 255 { 256 if (__x._M_w.size() == this->_M_w.size()) 257 { 258 for (size_t __i = this->_M_w.size(); __i > 0; --__i) 259 { 260 if (this->_M_w[__i-1] < __x._M_w[__i-1]) 261 return true; 262 else if (this->_M_w[__i-1] > __x._M_w[__i-1]) 263 return false; 264 } 265 return false; 266 } 267 else 268 return false; 269 } 270 271 size_t 272 _M_are_all_aux() const noexcept 273 { 274 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i) 275 if (_M_w[__i] != static_cast<block_type>(-1)) 276 return 0; 277 return ((this->_M_w.size() - 1) * _S_bits_per_block 278 + __builtin_popcountll(this->_M_hiword())); 279 } 280 281 bool 282 _M_is_any() const noexcept 283 { 284 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 285 if (this->_M_w[__i] != static_cast<block_type>(0)) 286 return true; 287 return false; 288 } 289 290 bool 291 _M_is_subset_of(const __dynamic_bitset_base& __b) noexcept 292 { 293 if (__b._M_w.size() == this->_M_w.size()) 294 { 295 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 296 if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i])) 297 return false; 298 return true; 299 } 300 else 301 return false; 302 } 303 304 bool 305 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const noexcept 306 { 307 if (this->is_subset_of(__b)) 308 { 309 if (*this == __b) 310 return false; 311 else 312 return true; 313 } 314 else 315 return false; 316 } 317 318 size_t 319 _M_do_count() const noexcept 320 { 321 size_t __result = 0; 322 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 323 __result += __builtin_popcountll(this->_M_w[__i]); 324 return __result; 325 } 326 327 size_type 328 _M_size() const noexcept 329 { return this->_M_w.size(); } 330 331 unsigned long 332 _M_do_to_ulong() const; 333 334 unsigned long long 335 _M_do_to_ullong() const; 336 337 // find first "on" bit 338 size_type 339 _M_do_find_first(size_t __not_found) const; 340 341 // find the next "on" bit that follows "prev" 342 size_type 343 _M_do_find_next(size_t __prev, size_t __not_found) const; 344 345 // do append of block 346 void 347 _M_do_append_block(block_type __block, size_type __pos) 348 { 349 size_t __offset = __pos % _S_bits_per_block; 350 if (__offset == 0) 351 this->_M_w.push_back(__block); 352 else 353 { 354 this->_M_hiword() |= (__block << __offset); 355 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset)); 356 } 357 } 358 }; 359 360 /** 361 * @brief The %dynamic_bitset class represents a sequence of bits. 362 * 363 * See N2050, 364 * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library. 365 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2050.pdf 366 * 367 * In the general unoptimized case, storage is allocated in 368 * word-sized blocks. Let B be the number of bits in a word, then 369 * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are 370 * unused. (They are the high-order bits in the highest word.) It 371 * is a class invariant that those unused bits are always zero. 372 * 373 * If you think of %dynamic_bitset as "a simple array of bits," be 374 * aware that your mental picture is reversed: a %dynamic_bitset 375 * behaves the same way as bits in integers do, with the bit at 376 * index 0 in the "least significant / right-hand" position, and 377 * the bit at index Nb-1 in the "most significant / left-hand" 378 * position. Thus, unlike other containers, a %dynamic_bitset's 379 * index "counts from right to left," to put it very loosely. 380 * 381 * This behavior is preserved when translating to and from strings. 382 * For example, the first line of the following program probably 383 * prints "b('a') is 0001100001" on a modern ASCII system. 384 * 385 * @code 386 * #include <dynamic_bitset> 387 * #include <iostream> 388 * #include <sstream> 389 * 390 * using namespace std; 391 * 392 * int main() 393 * { 394 * long a = 'a'; 395 * dynamic_bitset<> b(a); 396 * 397 * cout << "b('a') is " << b << endl; 398 * 399 * ostringstream s; 400 * s << b; 401 * string str = s.str(); 402 * cout << "index 3 in the string is " << str[3] << " but\n" 403 * << "index 3 in the bitset is " << b[3] << endl; 404 * } 405 * @endcode 406 * 407 * Most of the actual code isn't contained in %dynamic_bitset<> 408 * itself, but in the base class __dynamic_bitset_base. The base 409 * class works with whole words, not with individual bits. This 410 * allows us to specialize __dynamic_bitset_base for the important 411 * special case where the %dynamic_bitset is only a single word. 412 * 413 * Extra confusion can result due to the fact that the storage for 414 * __dynamic_bitset_base @e is a vector, and is indexed as such. This is 415 * carefully encapsulated. 416 */ 417 template<typename _WordT = unsigned long long, 418 typename _Alloc = std::allocator<_WordT>> 419 class dynamic_bitset 420 : private __dynamic_bitset_base<_WordT, _Alloc> 421 { 422 static_assert(std::is_unsigned<_WordT>::value, "template argument " 423 "_WordT not an unsigned integral type"); 424 425 public: 426 427 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base; 428 typedef _WordT block_type; 429 typedef _Alloc allocator_type; 430 typedef size_t size_type; 431 432 static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type); 433 // Use this: constexpr size_type std::numeric_limits<size_type>::max(). 434 static const size_type npos = static_cast<size_type>(-1); 435 436 private: 437 438 // Clear the unused bits in the uppermost word. 439 void 440 _M_do_sanitize() 441 { 442 size_type __shift = this->_M_Nb % bits_per_block; 443 if (__shift > 0) 444 this->_M_hiword() &= block_type(~(block_type(-1) << __shift)); 445 } 446 447 // Set the unused bits in the uppermost word. 448 void 449 _M_do_fill() 450 { 451 size_type __shift = this->_M_Nb % bits_per_block; 452 if (__shift > 0) 453 this->_M_hiword() |= block_type(block_type(-1) << __shift); 454 } 455 456 /** 457 * These versions of single-bit set, reset, flip, and test 458 * do no range checking. 459 */ 460 dynamic_bitset& 461 _M_unchecked_set(size_type __pos) noexcept 462 { 463 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 464 return *this; 465 } 466 467 dynamic_bitset& 468 _M_unchecked_set(size_type __pos, int __val) noexcept 469 { 470 if (__val) 471 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 472 else 473 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 474 return *this; 475 } 476 477 dynamic_bitset& 478 _M_unchecked_reset(size_type __pos) noexcept 479 { 480 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 481 return *this; 482 } 483 484 dynamic_bitset& 485 _M_unchecked_flip(size_type __pos) noexcept 486 { 487 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 488 return *this; 489 } 490 491 bool 492 _M_unchecked_test(size_type __pos) const noexcept 493 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 494 != static_cast<_WordT>(0)); } 495 496 size_type _M_Nb = 0; 497 498 public: 499 /** 500 * This encapsulates the concept of a single bit. An instance 501 * of this class is a proxy for an actual bit; this way the 502 * individual bit operations are done as faster word-size 503 * bitwise instructions. 504 * 505 * Most users will never need to use this class directly; 506 * conversions to and from bool are automatic and should be 507 * transparent. Overloaded operators help to preserve the 508 * illusion. 509 * 510 * (On a typical system, this "bit %reference" is 64 times the 511 * size of an actual bit. Ha.) 512 */ 513 class reference 514 { 515 friend class dynamic_bitset; 516 517 block_type *_M_wp; 518 size_type _M_bpos; 519 520 public: 521 reference(dynamic_bitset& __b, size_type __pos) noexcept 522 { 523 this->_M_wp = &__b._M_getword(__pos); 524 this->_M_bpos = _Base::_S_whichbit(__pos); 525 } 526 527 // For b[i] = __x; 528 reference& 529 operator=(bool __x) noexcept 530 { 531 if (__x) 532 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 533 else 534 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 535 return *this; 536 } 537 538 // For b[i] = b[__j]; 539 reference& 540 operator=(const reference& __j) noexcept 541 { 542 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 543 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 544 else 545 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 546 return *this; 547 } 548 549 // Flips the bit 550 bool 551 operator~() const noexcept 552 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; } 553 554 // For __x = b[i]; 555 operator bool() const noexcept 556 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; } 557 558 // For b[i].flip(); 559 reference& 560 flip() noexcept 561 { 562 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos); 563 return *this; 564 } 565 }; 566 567 friend class reference; 568 569 typedef bool const_reference; 570 571 // 23.3.5.1 constructors: 572 573 /// All bits set to zero. 574 dynamic_bitset() = default; 575 576 /// All bits set to zero. 577 explicit 578 dynamic_bitset(const allocator_type& __alloc) 579 : _Base(__alloc) 580 { } 581 582 /// Initial bits bitwise-copied from a single word (others set to zero). 583 explicit 584 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL, 585 const allocator_type& __alloc = allocator_type()) 586 : _Base(__nbits, __val, __alloc), 587 _M_Nb(__nbits) 588 { } 589 590 dynamic_bitset(initializer_list<block_type> __il, 591 const allocator_type& __alloc = allocator_type()) 592 : _Base(__alloc) 593 { this->append(__il); } 594 595 /** 596 * @brief Use a subset of a string. 597 * @param __str A string of '0' and '1' characters. 598 * @param __pos Index of the first character in @p __str to use. 599 * @param __n The number of characters to copy. 600 * @param __zero The character to use for unset bits. 601 * @param __one The character to use for set bits. 602 * @param __alloc An allocator. 603 * @throw std::out_of_range If @p __pos is bigger the size of @p __str. 604 * @throw std::invalid_argument If a character appears in the string 605 * which is neither '0' nor '1'. 606 */ 607 template<typename _CharT, typename _Traits, typename _Alloc1> 608 explicit 609 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str, 610 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 611 __pos = 0, 612 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 613 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos, 614 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'), 615 const allocator_type& __alloc = allocator_type()) 616 : _Base(__alloc) 617 { 618 if (__pos > __str.size()) 619 __throw_out_of_range(__N("dynamic_bitset::bitset initial position " 620 "not valid")); 621 622 // Watch for npos. 623 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n); 624 this->resize(this->_M_Nb); 625 this->_M_copy_from_string(__str, __pos, __n, __zero, __one); 626 } 627 628 /** 629 * @brief Construct from a string. 630 * @param __str A string of '0' and '1' characters. 631 * @param __alloc An allocator. 632 * @throw std::invalid_argument If a character appears in the string 633 * which is neither '0' nor '1'. 634 */ 635 explicit 636 dynamic_bitset(const char* __str, 637 const allocator_type& __alloc = allocator_type()) 638 : _Base(__builtin_strlen(__str), 0ULL, __alloc), 639 _M_Nb(__builtin_strlen(__str)) 640 { 641 this->_M_copy_from_ptr(__str, _M_Nb, 0, _M_Nb); 642 } 643 644 /// Copy constructor. 645 dynamic_bitset(const dynamic_bitset&) = default; 646 647 /// Move constructor. 648 dynamic_bitset(dynamic_bitset&& __b) noexcept 649 : _Base(std::move(__b)), _M_Nb(__b._M_Nb) 650 { __b.clear(); } 651 652 /// Swap with another bitset. 653 void 654 swap(dynamic_bitset& __b) noexcept 655 { 656 this->_M_swap(__b); 657 std::swap(this->_M_Nb, __b._M_Nb); 658 } 659 660 /// Copy assignment operator. 661 dynamic_bitset& operator=(const dynamic_bitset&) = default; 662 663 /// Move assignment operator. 664 dynamic_bitset& 665 operator=(dynamic_bitset&& __b) 666 noexcept(std::is_nothrow_move_assignable<_Base>::value) 667 { 668 static_cast<_Base&>(*this) = static_cast<_Base&&>(__b); 669 _M_Nb = __b._M_Nb; 670 if _GLIBCXX17_CONSTEXPR (std::is_nothrow_move_assignable<_Base>::value) 671 __b._M_Nb = 0; 672 else if (get_allocator() == __b.get_allocator()) 673 __b._M_Nb = 0; 674 return *this; 675 } 676 677 /** 678 * @brief Return the allocator for the bitset. 679 */ 680 allocator_type 681 get_allocator() const noexcept 682 { return this->_M_get_allocator(); } 683 684 /** 685 * @brief Resize the bitset. 686 */ 687 void 688 resize(size_type __nbits, bool __value = false) 689 { 690 if (__value) 691 this->_M_do_fill(); 692 this->_M_resize(__nbits, __value); 693 this->_M_Nb = __nbits; 694 this->_M_do_sanitize(); 695 } 696 697 /** 698 * @brief Clear the bitset. 699 */ 700 void 701 clear() 702 { 703 this->_M_clear(); 704 this->_M_Nb = 0; 705 } 706 707 /** 708 * @brief Push a bit onto the high end of the bitset. 709 */ 710 void 711 push_back(bool __bit) 712 { 713 if (this->size() % bits_per_block == 0) 714 this->_M_do_append_block(block_type(__bit), this->_M_Nb); 715 else 716 this->_M_unchecked_set(this->_M_Nb, __bit); 717 ++this->_M_Nb; 718 } 719 720 // XXX why is there no pop_back() member in the proposal? 721 722 /** 723 * @brief Append a block. 724 */ 725 void 726 append(block_type __block) 727 { 728 this->_M_do_append_block(__block, this->_M_Nb); 729 this->_M_Nb += bits_per_block; 730 } 731 732 /** 733 * @brief 734 */ 735 void 736 append(initializer_list<block_type> __il) 737 { this->append(__il.begin(), __il.end()); } 738 739 /** 740 * @brief Append an iterator range of blocks. 741 */ 742 template <typename _BlockInputIterator> 743 void 744 append(_BlockInputIterator __first, _BlockInputIterator __last) 745 { 746 for (; __first != __last; ++__first) 747 this->append(*__first); 748 } 749 750 // 23.3.5.2 dynamic_bitset operations: 751 ///@{ 752 /** 753 * @brief Operations on dynamic_bitsets. 754 * @param __rhs A same-sized dynamic_bitset. 755 * 756 * These should be self-explanatory. 757 */ 758 dynamic_bitset& 759 operator&=(const dynamic_bitset& __rhs) 760 { 761 this->_M_do_and(__rhs); 762 return *this; 763 } 764 765 dynamic_bitset& 766 operator&=(dynamic_bitset&& __rhs) 767 { 768 this->_M_do_and(std::move(__rhs)); 769 return *this; 770 } 771 772 dynamic_bitset& 773 operator|=(const dynamic_bitset& __rhs) 774 { 775 this->_M_do_or(__rhs); 776 return *this; 777 } 778 779 dynamic_bitset& 780 operator^=(const dynamic_bitset& __rhs) 781 { 782 this->_M_do_xor(__rhs); 783 return *this; 784 } 785 786 dynamic_bitset& 787 operator-=(const dynamic_bitset& __rhs) 788 { 789 this->_M_do_dif(__rhs); 790 return *this; 791 } 792 ///@} 793 794 ///@{ 795 /** 796 * @brief Operations on dynamic_bitsets. 797 * @param __pos The number of places to shift. 798 * 799 * These should be self-explanatory. 800 */ 801 dynamic_bitset& 802 operator<<=(size_type __pos) 803 { 804 if (__builtin_expect(__pos < this->_M_Nb, 1)) 805 { 806 this->_M_do_left_shift(__pos); 807 this->_M_do_sanitize(); 808 } 809 else 810 this->_M_do_reset(); 811 return *this; 812 } 813 814 dynamic_bitset& 815 operator>>=(size_type __pos) 816 { 817 if (__builtin_expect(__pos < this->_M_Nb, 1)) 818 this->_M_do_right_shift(__pos); 819 else 820 this->_M_do_reset(); 821 return *this; 822 } 823 ///@} 824 825 // Set, reset, and flip. 826 /** 827 * @brief Sets every bit to true. 828 */ 829 dynamic_bitset& 830 set() 831 { 832 this->_M_do_set(); 833 this->_M_do_sanitize(); 834 return *this; 835 } 836 837 /** 838 * @brief Sets a given bit to a particular value. 839 * @param __pos The index of the bit. 840 * @param __val Either true or false, defaults to true. 841 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 842 */ 843 dynamic_bitset& 844 set(size_type __pos, bool __val = true) 845 { 846 if (__pos >= _M_Nb) 847 __throw_out_of_range(__N("dynamic_bitset::set")); 848 return this->_M_unchecked_set(__pos, __val); 849 } 850 851 /** 852 * @brief Sets every bit to false. 853 */ 854 dynamic_bitset& 855 reset() 856 { 857 this->_M_do_reset(); 858 return *this; 859 } 860 861 /** 862 * @brief Sets a given bit to false. 863 * @param __pos The index of the bit. 864 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 865 * 866 * Same as writing @c set(__pos, false). 867 */ 868 dynamic_bitset& 869 reset(size_type __pos) 870 { 871 if (__pos >= _M_Nb) 872 __throw_out_of_range(__N("dynamic_bitset::reset")); 873 return this->_M_unchecked_reset(__pos); 874 } 875 876 /** 877 * @brief Toggles every bit to its opposite value. 878 */ 879 dynamic_bitset& 880 flip() 881 { 882 this->_M_do_flip(); 883 this->_M_do_sanitize(); 884 return *this; 885 } 886 887 /** 888 * @brief Toggles a given bit to its opposite value. 889 * @param __pos The index of the bit. 890 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 891 */ 892 dynamic_bitset& 893 flip(size_type __pos) 894 { 895 if (__pos >= _M_Nb) 896 __throw_out_of_range(__N("dynamic_bitset::flip")); 897 return this->_M_unchecked_flip(__pos); 898 } 899 900 /// See the no-argument flip(). 901 dynamic_bitset 902 operator~() const 903 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); } 904 905 ///@{ 906 /** 907 * @brief Array-indexing support. 908 * @param __pos Index into the %dynamic_bitset. 909 * @return A bool for a 'const %dynamic_bitset'. For non-const 910 * bitsets, an instance of the reference proxy class. 911 * @note These operators do no range checking and throw no 912 * exceptions, as required by DR 11 to the standard. 913 */ 914 reference 915 operator[](size_type __pos) 916 { return reference(*this,__pos); } 917 918 const_reference 919 operator[](size_type __pos) const 920 { return _M_unchecked_test(__pos); } 921 ///@} 922 923 /** 924 * @brief Returns a numerical interpretation of the %dynamic_bitset. 925 * @return The integral equivalent of the bits. 926 * @throw std::overflow_error If there are too many bits to be 927 * represented in an @c unsigned @c long. 928 */ 929 unsigned long 930 to_ulong() const 931 { return this->_M_do_to_ulong(); } 932 933 /** 934 * @brief Returns a numerical interpretation of the %dynamic_bitset. 935 * @return The integral equivalent of the bits. 936 * @throw std::overflow_error If there are too many bits to be 937 * represented in an @c unsigned @c long. 938 */ 939 unsigned long long 940 to_ullong() const 941 { return this->_M_do_to_ullong(); } 942 943 /** 944 * @brief Returns a character interpretation of the %dynamic_bitset. 945 * @return The string equivalent of the bits. 946 * 947 * Note the ordering of the bits: decreasing character positions 948 * correspond to increasing bit positions (see the main class notes for 949 * an example). 950 */ 951 template<typename _CharT = char, 952 typename _Traits = std::char_traits<_CharT>, 953 typename _Alloc1 = std::allocator<_CharT>> 954 std::basic_string<_CharT, _Traits, _Alloc1> 955 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const 956 { 957 std::basic_string<_CharT, _Traits, _Alloc1> __result; 958 _M_copy_to_string(__result, __zero, __one); 959 return __result; 960 } 961 962 // Helper functions for string operations. 963 template<typename _Traits = std::char_traits<char>, 964 typename _CharT = typename _Traits::char_type> 965 void 966 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 967 _CharT __zero = _CharT('0'), 968 _CharT __one = _CharT('1')); 969 970 template<typename _CharT, typename _Traits, typename _Alloc1> 971 void 972 _M_copy_from_string(const basic_string<_CharT, _Traits, _Alloc1>& __str, 973 size_t __pos, size_t __n, 974 _CharT __zero = _CharT('0'), 975 _CharT __one = _CharT('1')) 976 { 977 _M_copy_from_ptr<_Traits>(__str.data(), __str.size(), __pos, __n, 978 __zero, __one); 979 } 980 981 template<typename _CharT, typename _Traits, typename _Alloc1> 982 void 983 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 984 _CharT __zero = _CharT('0'), 985 _CharT __one = _CharT('1')) const; 986 987 /// Returns the number of bits which are set. 988 size_type 989 count() const noexcept 990 { return this->_M_do_count(); } 991 992 /// Returns the total number of bits. 993 size_type 994 size() const noexcept 995 { return this->_M_Nb; } 996 997 /// Returns the total number of blocks. 998 size_type 999 num_blocks() const noexcept 1000 { return this->_M_size(); } 1001 1002 /// Returns true if the dynamic_bitset is empty. 1003 _GLIBCXX_NODISCARD bool 1004 empty() const noexcept 1005 { return (this->_M_Nb == 0); } 1006 1007 /// Returns the maximum size of a dynamic_bitset object having the same 1008 /// type as *this. 1009 /// The real answer is max() * bits_per_block but is likely to overflow. 1010 constexpr size_type 1011 max_size() noexcept 1012 { return std::numeric_limits<block_type>::max(); } 1013 1014 /** 1015 * @brief Tests the value of a bit. 1016 * @param __pos The index of a bit. 1017 * @return The value at @a __pos. 1018 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 1019 */ 1020 bool 1021 test(size_type __pos) const 1022 { 1023 if (__pos >= _M_Nb) 1024 __throw_out_of_range(__N("dynamic_bitset::test")); 1025 return _M_unchecked_test(__pos); 1026 } 1027 1028 /** 1029 * @brief Tests whether all the bits are on. 1030 * @return True if all the bits are set. 1031 */ 1032 bool 1033 all() const 1034 { return this->_M_are_all_aux() == _M_Nb; } 1035 1036 /** 1037 * @brief Tests whether any of the bits are on. 1038 * @return True if at least one bit is set. 1039 */ 1040 bool 1041 any() const 1042 { return this->_M_is_any(); } 1043 1044 /** 1045 * @brief Tests whether any of the bits are on. 1046 * @return True if none of the bits are set. 1047 */ 1048 bool 1049 none() const 1050 { return !this->_M_is_any(); } 1051 1052 ///@{ 1053 /// Self-explanatory. 1054 dynamic_bitset 1055 operator<<(size_type __pos) const 1056 { return dynamic_bitset(*this) <<= __pos; } 1057 1058 dynamic_bitset 1059 operator>>(size_type __pos) const 1060 { return dynamic_bitset(*this) >>= __pos; } 1061 ///@} 1062 1063 /** 1064 * @brief Finds the index of the first "on" bit. 1065 * @return The index of the first bit set, or size() if not found. 1066 * @sa find_next 1067 */ 1068 size_type 1069 find_first() const 1070 { return this->_M_do_find_first(this->_M_Nb); } 1071 1072 /** 1073 * @brief Finds the index of the next "on" bit after prev. 1074 * @return The index of the next bit set, or size() if not found. 1075 * @param __prev Where to start searching. 1076 * @sa find_first 1077 */ 1078 size_type 1079 find_next(size_t __prev) const 1080 { return this->_M_do_find_next(__prev, this->_M_Nb); } 1081 1082 bool 1083 is_subset_of(const dynamic_bitset& __b) const 1084 { return this->_M_is_subset_of(__b); } 1085 1086 bool 1087 is_proper_subset_of(const dynamic_bitset& __b) const 1088 { return this->_M_is_proper_subset_of(__b); } 1089 1090 friend bool 1091 operator==(const dynamic_bitset& __lhs, 1092 const dynamic_bitset& __rhs) noexcept 1093 { return __lhs._M_Nb == __rhs._M_Nb && __lhs._M_is_equal(__rhs); } 1094 1095 friend bool 1096 operator<(const dynamic_bitset& __lhs, 1097 const dynamic_bitset& __rhs) noexcept 1098 { return __lhs._M_is_less(__rhs) || __lhs._M_Nb < __rhs._M_Nb; } 1099 }; 1100 1101 template<typename _WordT, typename _Alloc> 1102 template<typename _CharT, typename _Traits, typename _Alloc1> 1103 inline void 1104 dynamic_bitset<_WordT, _Alloc>:: 1105 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 1106 _CharT __zero, _CharT __one) const 1107 { 1108 __str.assign(_M_Nb, __zero); 1109 for (size_t __i = _M_Nb; __i > 0; --__i) 1110 if (_M_unchecked_test(__i - 1)) 1111 _Traits::assign(__str[_M_Nb - __i], __one); 1112 } 1113 1114 1115 ///@{ 1116 /// These comparisons for equality/inequality are, well, @e bitwise. 1117 1118 template<typename _WordT, typename _Alloc> 1119 inline bool 1120 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1121 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1122 { return !(__lhs == __rhs); } 1123 1124 template<typename _WordT, typename _Alloc> 1125 inline bool 1126 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1127 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1128 { return !(__lhs > __rhs); } 1129 1130 template<typename _WordT, typename _Alloc> 1131 inline bool 1132 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1133 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1134 { return __rhs < __lhs; } 1135 1136 template<typename _WordT, typename _Alloc> 1137 inline bool 1138 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1139 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1140 { return !(__lhs < __rhs); } 1141 ///@} 1142 1143 // 23.3.5.3 bitset operations: 1144 ///@{ 1145 /** 1146 * @brief Global bitwise operations on bitsets. 1147 * @param __x A bitset. 1148 * @param __y A bitset of the same size as @a __x. 1149 * @return A new bitset. 1150 * 1151 * These should be self-explanatory. 1152 */ 1153 template<typename _WordT, typename _Alloc> 1154 inline dynamic_bitset<_WordT, _Alloc> 1155 operator&(const dynamic_bitset<_WordT, _Alloc>& __x, 1156 const dynamic_bitset<_WordT, _Alloc>& __y) 1157 { 1158 dynamic_bitset<_WordT, _Alloc> __result(__x); 1159 __result &= __y; 1160 return __result; 1161 } 1162 1163 template<typename _WordT, typename _Alloc> 1164 inline dynamic_bitset<_WordT, _Alloc> 1165 operator|(const dynamic_bitset<_WordT, _Alloc>& __x, 1166 const dynamic_bitset<_WordT, _Alloc>& __y) 1167 { 1168 dynamic_bitset<_WordT, _Alloc> __result(__x); 1169 __result |= __y; 1170 return __result; 1171 } 1172 1173 template <typename _WordT, typename _Alloc> 1174 inline dynamic_bitset<_WordT, _Alloc> 1175 operator^(const dynamic_bitset<_WordT, _Alloc>& __x, 1176 const dynamic_bitset<_WordT, _Alloc>& __y) 1177 { 1178 dynamic_bitset<_WordT, _Alloc> __result(__x); 1179 __result ^= __y; 1180 return __result; 1181 } 1182 1183 template <typename _WordT, typename _Alloc> 1184 inline dynamic_bitset<_WordT, _Alloc> 1185 operator-(const dynamic_bitset<_WordT, _Alloc>& __x, 1186 const dynamic_bitset<_WordT, _Alloc>& __y) 1187 { 1188 dynamic_bitset<_WordT, _Alloc> __result(__x); 1189 __result -= __y; 1190 return __result; 1191 } 1192 ///@} 1193 1194 /// Stream output operator for dynamic_bitset. 1195 template <typename _CharT, typename _Traits, 1196 typename _WordT, typename _Alloc> 1197 inline std::basic_ostream<_CharT, _Traits>& 1198 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 1199 const dynamic_bitset<_WordT, _Alloc>& __x) 1200 { 1201 std::basic_string<_CharT, _Traits> __tmp; 1202 1203 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc()); 1204 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 1205 return __os << __tmp; 1206 } 1207 /** 1208 * @} 1209 */ 1210 } // tr2 1211 1212 _GLIBCXX_END_NAMESPACE_VERSION 1213 } // std 1214 1215 #include <tr2/dynamic_bitset.tcc> 1216 1217 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */ 1218
Indexes created Sun Mar 01 05:31:48 UTC 2026