1// <bitset> -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 3, or (at your option) 10// any later version. 11 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16 17// Under Section 7 of GPL version 3, you are granted additional 18// permissions described in the GCC Runtime Library Exception, version 19// 3.1, as published by the Free Software Foundation. 20 21// You should have received a copy of the GNU General Public License and 22// a copy of the GCC Runtime Library Exception along with this program; 23// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24// <http://www.gnu.org/licenses/>. 25 26/* 27 * Copyright (c) 1998 28 * Silicon Graphics Computer Systems, Inc. 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Silicon Graphics makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 */ 38 39/** @file include/bitset 40 * This is a Standard C++ Library header. 41 */ 42 43#ifndef _GLIBCXX_BITSET 44#define _GLIBCXX_BITSET 1 45 46#pragma GCC system_header 47 48#include <cstddef> // For size_t 49#include <string> 50#include <bits/functexcept.h> // For invalid_argument, out_of_range, 51 // overflow_error 52#include <iosfwd> 53#include <cxxabi-forced.h> 54 55#define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * sizeof(unsigned long)) 56#define _GLIBCXX_BITSET_WORDS(__n) \ 57 ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \ 58 / _GLIBCXX_BITSET_BITS_PER_WORD) 59 60_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 61 62 /** 63 * Base class, general case. It is a class invariant that _Nw will be 64 * nonnegative. 65 * 66 * See documentation for bitset. 67 */ 68 template<size_t _Nw> 69 struct _Base_bitset 70 { 71 typedef unsigned long _WordT; 72 73 /// 0 is the least significant word. 74 _WordT _M_w[_Nw]; 75 76 _Base_bitset() 77 { _M_do_reset(); } 78 79#ifdef __GXX_EXPERIMENTAL_CXX0X__ 80 _Base_bitset(unsigned long long __val) 81#else 82 _Base_bitset(unsigned long __val) 83#endif 84 { 85 _M_do_reset(); 86 _M_w[0] = __val; 87#ifdef __GXX_EXPERIMENTAL_CXX0X__ 88 if (sizeof(unsigned long long) > sizeof(unsigned long)) 89 _M_w[1] = __val >> _GLIBCXX_BITSET_BITS_PER_WORD; 90#endif 91 } 92 93 static size_t 94 _S_whichword(size_t __pos ) 95 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 96 97 static size_t 98 _S_whichbyte(size_t __pos ) 99 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 100 101 static size_t 102 _S_whichbit(size_t __pos ) 103 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 104 105 static _WordT 106 _S_maskbit(size_t __pos ) 107 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 108 109 _WordT& 110 _M_getword(size_t __pos) 111 { return _M_w[_S_whichword(__pos)]; } 112 113 _WordT 114 _M_getword(size_t __pos) const 115 { return _M_w[_S_whichword(__pos)]; } 116 117#ifdef __GXX_EXPERIMENTAL_CXX0X__ 118 const _WordT* 119 _M_getdata() const 120 { return _M_w; } 121#endif 122 123 _WordT& 124 _M_hiword() 125 { return _M_w[_Nw - 1]; } 126 127 _WordT 128 _M_hiword() const 129 { return _M_w[_Nw - 1]; } 130 131 void 132 _M_do_and(const _Base_bitset<_Nw>& __x) 133 { 134 for (size_t __i = 0; __i < _Nw; __i++) 135 _M_w[__i] &= __x._M_w[__i]; 136 } 137 138 void 139 _M_do_or(const _Base_bitset<_Nw>& __x) 140 { 141 for (size_t __i = 0; __i < _Nw; __i++) 142 _M_w[__i] |= __x._M_w[__i]; 143 } 144 145 void 146 _M_do_xor(const _Base_bitset<_Nw>& __x) 147 { 148 for (size_t __i = 0; __i < _Nw; __i++) 149 _M_w[__i] ^= __x._M_w[__i]; 150 } 151 152 void 153 _M_do_left_shift(size_t __shift); 154 155 void 156 _M_do_right_shift(size_t __shift); 157 158 void 159 _M_do_flip() 160 { 161 for (size_t __i = 0; __i < _Nw; __i++) 162 _M_w[__i] = ~_M_w[__i]; 163 } 164 165 void 166 _M_do_set() 167 { 168 for (size_t __i = 0; __i < _Nw; __i++) 169 _M_w[__i] = ~static_cast<_WordT>(0); 170 } 171 172 void 173 _M_do_reset() 174 { __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT)); } 175 176 bool 177 _M_is_equal(const _Base_bitset<_Nw>& __x) const 178 { 179 for (size_t __i = 0; __i < _Nw; ++__i) 180 if (_M_w[__i] != __x._M_w[__i]) 181 return false; 182 return true; 183 } 184 185 size_t 186 _M_are_all_aux() const 187 { 188 for (size_t __i = 0; __i < _Nw - 1; __i++) 189 if (_M_w[__i] != ~static_cast<_WordT>(0)) 190 return 0; 191 return ((_Nw - 1) * _GLIBCXX_BITSET_BITS_PER_WORD 192 + __builtin_popcountl(_M_hiword())); 193 } 194 195 bool 196 _M_is_any() const 197 { 198 for (size_t __i = 0; __i < _Nw; __i++) 199 if (_M_w[__i] != static_cast<_WordT>(0)) 200 return true; 201 return false; 202 } 203 204 size_t 205 _M_do_count() const 206 { 207 size_t __result = 0; 208 for (size_t __i = 0; __i < _Nw; __i++) 209 __result += __builtin_popcountl(_M_w[__i]); 210 return __result; 211 } 212 213 unsigned long 214 _M_do_to_ulong() const; 215 216#ifdef __GXX_EXPERIMENTAL_CXX0X__ 217 unsigned long long 218 _M_do_to_ullong() const; 219#endif 220 221 // find first "on" bit 222 size_t 223 _M_do_find_first(size_t __not_found) const; 224 225 // find the next "on" bit that follows "prev" 226 size_t 227 _M_do_find_next(size_t __prev, size_t __not_found) const; 228 }; 229 230 // Definitions of non-inline functions from _Base_bitset. 231 template<size_t _Nw> 232 void 233 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) 234 { 235 if (__builtin_expect(__shift != 0, 1)) 236 { 237 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 238 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 239 240 if (__offset == 0) 241 for (size_t __n = _Nw - 1; __n >= __wshift; --__n) 242 _M_w[__n] = _M_w[__n - __wshift]; 243 else 244 { 245 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 246 - __offset); 247 for (size_t __n = _Nw - 1; __n > __wshift; --__n) 248 _M_w[__n] = ((_M_w[__n - __wshift] << __offset) 249 | (_M_w[__n - __wshift - 1] >> __sub_offset)); 250 _M_w[__wshift] = _M_w[0] << __offset; 251 } 252 253 std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); 254 } 255 } 256 257 template<size_t _Nw> 258 void 259 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) 260 { 261 if (__builtin_expect(__shift != 0, 1)) 262 { 263 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 264 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 265 const size_t __limit = _Nw - __wshift - 1; 266 267 if (__offset == 0) 268 for (size_t __n = 0; __n <= __limit; ++__n) 269 _M_w[__n] = _M_w[__n + __wshift]; 270 else 271 { 272 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 273 - __offset); 274 for (size_t __n = 0; __n < __limit; ++__n) 275 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset) 276 | (_M_w[__n + __wshift + 1] << __sub_offset)); 277 _M_w[__limit] = _M_w[_Nw-1] >> __offset; 278 } 279 280 std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); 281 } 282 } 283 284 template<size_t _Nw> 285 unsigned long 286 _Base_bitset<_Nw>::_M_do_to_ulong() const 287 { 288 for (size_t __i = 1; __i < _Nw; ++__i) 289 if (_M_w[__i]) 290 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong")); 291 return _M_w[0]; 292 } 293 294#ifdef __GXX_EXPERIMENTAL_CXX0X__ 295 template<size_t _Nw> 296 unsigned long long 297 _Base_bitset<_Nw>::_M_do_to_ullong() const 298 { 299 const bool __dw = sizeof(unsigned long long) > sizeof(unsigned long); 300 for (size_t __i = 1 + __dw; __i < _Nw; ++__i) 301 if (_M_w[__i]) 302 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong")); 303 304 if (__dw) 305 return _M_w[0] + (static_cast<unsigned long long>(_M_w[1]) 306 << _GLIBCXX_BITSET_BITS_PER_WORD); 307 return _M_w[0]; 308 } 309#endif 310 311 template<size_t _Nw> 312 size_t 313 _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const 314 { 315 for (size_t __i = 0; __i < _Nw; __i++) 316 { 317 _WordT __thisword = _M_w[__i]; 318 if (__thisword != static_cast<_WordT>(0)) 319 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 320 + __builtin_ctzl(__thisword)); 321 } 322 // not found, so return an indication of failure. 323 return __not_found; 324 } 325 326 template<size_t _Nw> 327 size_t 328 _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const 329 { 330 // make bound inclusive 331 ++__prev; 332 333 // check out of bounds 334 if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD) 335 return __not_found; 336 337 // search first word 338 size_t __i = _S_whichword(__prev); 339 _WordT __thisword = _M_w[__i]; 340 341 // mask off bits below bound 342 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 343 344 if (__thisword != static_cast<_WordT>(0)) 345 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 346 + __builtin_ctzl(__thisword)); 347 348 // check subsequent words 349 __i++; 350 for (; __i < _Nw; __i++) 351 { 352 __thisword = _M_w[__i]; 353 if (__thisword != static_cast<_WordT>(0)) 354 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 355 + __builtin_ctzl(__thisword)); 356 } 357 // not found, so return an indication of failure. 358 return __not_found; 359 } // end _M_do_find_next 360 361 /** 362 * Base class, specialization for a single word. 363 * 364 * See documentation for bitset. 365 */ 366 template<> 367 struct _Base_bitset<1> 368 { 369 typedef unsigned long _WordT; 370 _WordT _M_w; 371 372 _Base_bitset(void) 373 : _M_w(0) 374 { } 375 376#ifdef __GXX_EXPERIMENTAL_CXX0X__ 377 _Base_bitset(unsigned long long __val) 378#else 379 _Base_bitset(unsigned long __val) 380#endif 381 : _M_w(__val) 382 { } 383 384 static size_t 385 _S_whichword(size_t __pos ) 386 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 387 388 static size_t 389 _S_whichbyte(size_t __pos ) 390 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 391 392 static size_t 393 _S_whichbit(size_t __pos ) 394 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 395 396 static _WordT 397 _S_maskbit(size_t __pos ) 398 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 399 400 _WordT& 401 _M_getword(size_t) 402 { return _M_w; } 403 404 _WordT 405 _M_getword(size_t) const 406 { return _M_w; } 407 408#ifdef __GXX_EXPERIMENTAL_CXX0X__ 409 const _WordT* 410 _M_getdata() const 411 { return &_M_w; } 412#endif 413 414 _WordT& 415 _M_hiword() 416 { return _M_w; } 417 418 _WordT 419 _M_hiword() const 420 { return _M_w; } 421 422 void 423 _M_do_and(const _Base_bitset<1>& __x) 424 { _M_w &= __x._M_w; } 425 426 void 427 _M_do_or(const _Base_bitset<1>& __x) 428 { _M_w |= __x._M_w; } 429 430 void 431 _M_do_xor(const _Base_bitset<1>& __x) 432 { _M_w ^= __x._M_w; } 433 434 void 435 _M_do_left_shift(size_t __shift) 436 { _M_w <<= __shift; } 437 438 void 439 _M_do_right_shift(size_t __shift) 440 { _M_w >>= __shift; } 441 442 void 443 _M_do_flip() 444 { _M_w = ~_M_w; } 445 446 void 447 _M_do_set() 448 { _M_w = ~static_cast<_WordT>(0); } 449 450 void 451 _M_do_reset() 452 { _M_w = 0; } 453 454 bool 455 _M_is_equal(const _Base_bitset<1>& __x) const 456 { return _M_w == __x._M_w; } 457 458 size_t 459 _M_are_all_aux() const 460 { return __builtin_popcountl(_M_w); } 461 462 bool 463 _M_is_any() const 464 { return _M_w != 0; } 465 466 size_t 467 _M_do_count() const 468 { return __builtin_popcountl(_M_w); } 469 470 unsigned long 471 _M_do_to_ulong() const 472 { return _M_w; } 473 474#ifdef __GXX_EXPERIMENTAL_CXX0X__ 475 unsigned long long 476 _M_do_to_ullong() const 477 { return _M_w; } 478#endif 479 480 size_t 481 _M_do_find_first(size_t __not_found) const 482 { 483 if (_M_w != 0) 484 return __builtin_ctzl(_M_w); 485 else 486 return __not_found; 487 } 488 489 // find the next "on" bit that follows "prev" 490 size_t 491 _M_do_find_next(size_t __prev, size_t __not_found) const 492 { 493 ++__prev; 494 if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD)) 495 return __not_found; 496 497 _WordT __x = _M_w >> __prev; 498 if (__x != 0) 499 return __builtin_ctzl(__x) + __prev; 500 else 501 return __not_found; 502 } 503 }; 504 505 /** 506 * Base class, specialization for no storage (zero-length %bitset). 507 * 508 * See documentation for bitset. 509 */ 510 template<> 511 struct _Base_bitset<0> 512 { 513 typedef unsigned long _WordT; 514 515 _Base_bitset() 516 { } 517 518#ifdef __GXX_EXPERIMENTAL_CXX0X__ 519 _Base_bitset(unsigned long long) 520#else 521 _Base_bitset(unsigned long) 522#endif 523 { } 524 525 static size_t 526 _S_whichword(size_t __pos ) 527 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 528 529 static size_t 530 _S_whichbyte(size_t __pos ) 531 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 532 533 static size_t 534 _S_whichbit(size_t __pos ) 535 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 536 537 static _WordT 538 _S_maskbit(size_t __pos ) 539 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 540 541 // This would normally give access to the data. The bounds-checking 542 // in the bitset class will prevent the user from getting this far, 543 // but (1) it must still return an lvalue to compile, and (2) the 544 // user might call _Unchecked_set directly, in which case this /needs/ 545 // to fail. Let's not penalize zero-length users unless they actually 546 // make an unchecked call; all the memory ugliness is therefore 547 // localized to this single should-never-get-this-far function. 548 _WordT& 549 _M_getword(size_t) const 550 { 551 __throw_out_of_range(__N("_Base_bitset::_M_getword")); 552 return *new _WordT; 553 } 554 555 _WordT 556 _M_hiword() const 557 { return 0; } 558 559 void 560 _M_do_and(const _Base_bitset<0>&) 561 { } 562 563 void 564 _M_do_or(const _Base_bitset<0>&) 565 { } 566 567 void 568 _M_do_xor(const _Base_bitset<0>&) 569 { } 570 571 void 572 _M_do_left_shift(size_t) 573 { } 574 575 void 576 _M_do_right_shift(size_t) 577 { } 578 579 void 580 _M_do_flip() 581 { } 582 583 void 584 _M_do_set() 585 { } 586 587 void 588 _M_do_reset() 589 { } 590 591 // Are all empty bitsets equal to each other? Are they equal to 592 // themselves? How to compare a thing which has no state? What is 593 // the sound of one zero-length bitset clapping? 594 bool 595 _M_is_equal(const _Base_bitset<0>&) const 596 { return true; } 597 598 size_t 599 _M_are_all_aux() const 600 { return 0; } 601 602 bool 603 _M_is_any() const 604 { return false; } 605 606 size_t 607 _M_do_count() const 608 { return 0; } 609 610 unsigned long 611 _M_do_to_ulong() const 612 { return 0; } 613 614#ifdef __GXX_EXPERIMENTAL_CXX0X__ 615 unsigned long long 616 _M_do_to_ullong() const 617 { return 0; } 618#endif 619 620 // Normally "not found" is the size, but that could also be 621 // misinterpreted as an index in this corner case. Oh well. 622 size_t 623 _M_do_find_first(size_t) const 624 { return 0; } 625 626 size_t 627 _M_do_find_next(size_t, size_t) const 628 { return 0; } 629 }; 630 631 632 // Helper class to zero out the unused high-order bits in the highest word. 633 template<size_t _Extrabits> 634 struct _Sanitize 635 { 636 static void _S_do_sanitize(unsigned long& __val) 637 { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } 638 }; 639 640 template<> 641 struct _Sanitize<0> 642 { static void _S_do_sanitize(unsigned long) {} }; 643 644 /** 645 * @brief The %bitset class represents a @e fixed-size sequence of bits. 646 * 647 * @ingroup containers 648 * 649 * (Note that %bitset does @e not meet the formal requirements of a 650 * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 651 * 652 * The template argument, @a Nb, may be any non-negative number, 653 * specifying the number of bits (e.g., "0", "12", "1024*1024"). 654 * 655 * In the general unoptimized case, storage is allocated in word-sized 656 * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B 657 * words will be used for storage. B - Nb%B bits are unused. (They are 658 * the high-order bits in the highest word.) It is a class invariant 659 * that those unused bits are always zero. 660 * 661 * If you think of %bitset as <em>a simple array of bits</em>, be 662 * aware that your mental picture is reversed: a %bitset behaves 663 * the same way as bits in integers do, with the bit at index 0 in 664 * the <em>least significant / right-hand</em> position, and the bit at 665 * index Nb-1 in the <em>most significant / left-hand</em> position. 666 * Thus, unlike other containers, a %bitset's index <em>counts from 667 * right to left</em>, to put it very loosely. 668 * 669 * This behavior is preserved when translating to and from strings. For 670 * example, the first line of the following program probably prints 671 * <em>b('a') is 0001100001</em> on a modern ASCII system. 672 * 673 * @code 674 * #include <bitset> 675 * #include <iostream> 676 * #include <sstream> 677 * 678 * using namespace std; 679 * 680 * int main() 681 * { 682 * long a = 'a'; 683 * bitset<10> b(a); 684 * 685 * cout << "b('a') is " << b << endl; 686 * 687 * ostringstream s; 688 * s << b; 689 * string str = s.str(); 690 * cout << "index 3 in the string is " << str[3] << " but\n" 691 * << "index 3 in the bitset is " << b[3] << endl; 692 * } 693 * @endcode 694 * 695 * Also see: 696 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html 697 * for a description of extensions. 698 * 699 * Most of the actual code isn't contained in %bitset<> itself, but in the 700 * base class _Base_bitset. The base class works with whole words, not with 701 * individual bits. This allows us to specialize _Base_bitset for the 702 * important special case where the %bitset is only a single word. 703 * 704 * Extra confusion can result due to the fact that the storage for 705 * _Base_bitset @e is a regular array, and is indexed as such. This is 706 * carefully encapsulated. 707 */ 708 template<size_t _Nb> 709 class bitset 710 : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> 711 { 712 private: 713 typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base; 714 typedef unsigned long _WordT; 715 716 void 717 _M_do_sanitize() 718 { 719 _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>:: 720 _S_do_sanitize(this->_M_hiword()); 721 } 722 723#ifdef __GXX_EXPERIMENTAL_CXX0X__ 724 template<typename> friend class hash; 725#endif 726 727 public: 728 /** 729 * This encapsulates the concept of a single bit. An instance of this 730 * class is a proxy for an actual bit; this way the individual bit 731 * operations are done as faster word-size bitwise instructions. 732 * 733 * Most users will never need to use this class directly; conversions 734 * to and from bool are automatic and should be transparent. Overloaded 735 * operators help to preserve the illusion. 736 * 737 * (On a typical system, this <em>bit %reference</em> is 64 738 * times the size of an actual bit. Ha.) 739 */ 740 class reference 741 { 742 friend class bitset; 743 744 _WordT *_M_wp; 745 size_t _M_bpos; 746 747 // left undefined 748 reference(); 749 750 public: 751 reference(bitset& __b, size_t __pos) 752 { 753 _M_wp = &__b._M_getword(__pos); 754 _M_bpos = _Base::_S_whichbit(__pos); 755 } 756 757 ~reference() 758 { } 759 760 // For b[i] = __x; 761 reference& 762 operator=(bool __x) 763 { 764 if (__x) 765 *_M_wp |= _Base::_S_maskbit(_M_bpos); 766 else 767 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 768 return *this; 769 } 770 771 // For b[i] = b[__j]; 772 reference& 773 operator=(const reference& __j) 774 { 775 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 776 *_M_wp |= _Base::_S_maskbit(_M_bpos); 777 else 778 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 779 return *this; 780 } 781 782 // Flips the bit 783 bool 784 operator~() const 785 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 786 787 // For __x = b[i]; 788 operator bool() const 789 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 790 791 // For b[i].flip(); 792 reference& 793 flip() 794 { 795 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 796 return *this; 797 } 798 }; 799 friend class reference; 800 801 // 23.3.5.1 constructors: 802 /// All bits set to zero. 803 bitset() 804 { } 805 806 /// Initial bits bitwise-copied from a single word (others set to zero). 807#ifdef __GXX_EXPERIMENTAL_CXX0X__ 808 bitset(unsigned long long __val) 809#else 810 bitset(unsigned long __val) 811#endif 812 : _Base(__val) 813 { _M_do_sanitize(); } 814 815 /** 816 * @brief Use a subset of a string. 817 * @param s A string of @a 0 and @a 1 characters. 818 * @param position Index of the first character in @a s to use; 819 * defaults to zero. 820 * @throw std::out_of_range If @a pos is bigger the size of @a s. 821 * @throw std::invalid_argument If a character appears in the string 822 * which is neither @a 0 nor @a 1. 823 */ 824 template<class _CharT, class _Traits, class _Alloc> 825 explicit 826 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 827 size_t __position = 0) 828 : _Base() 829 { 830 if (__position > __s.size()) 831 __throw_out_of_range(__N("bitset::bitset initial position " 832 "not valid")); 833 _M_copy_from_string(__s, __position, 834 std::basic_string<_CharT, _Traits, _Alloc>::npos, 835 _CharT('0'), _CharT('1')); 836 } 837 838 /** 839 * @brief Use a subset of a string. 840 * @param s A string of @a 0 and @a 1 characters. 841 * @param position Index of the first character in @a s to use. 842 * @param n The number of characters to copy. 843 * @throw std::out_of_range If @a pos is bigger the size of @a s. 844 * @throw std::invalid_argument If a character appears in the string 845 * which is neither @a 0 nor @a 1. 846 */ 847 template<class _CharT, class _Traits, class _Alloc> 848 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 849 size_t __position, size_t __n) 850 : _Base() 851 { 852 if (__position > __s.size()) 853 __throw_out_of_range(__N("bitset::bitset initial position " 854 "not valid")); 855 _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1')); 856 } 857 858 // _GLIBCXX_RESOLVE_LIB_DEFECTS 859 // 396. what are characters zero and one. 860 template<class _CharT, class _Traits, class _Alloc> 861 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 862 size_t __position, size_t __n, 863 _CharT __zero, _CharT __one = _CharT('1')) 864 : _Base() 865 { 866 if (__position > __s.size()) 867 __throw_out_of_range(__N("bitset::bitset initial position " 868 "not valid")); 869 _M_copy_from_string(__s, __position, __n, __zero, __one); 870 } 871 872#ifdef __GXX_EXPERIMENTAL_CXX0X__ 873 /** 874 * @brief Construct from a string. 875 * @param str A string of @a 0 and @a 1 characters. 876 * @throw std::invalid_argument If a character appears in the string 877 * which is neither @a 0 nor @a 1. 878 */ 879 explicit 880 bitset(const char* __str) 881 : _Base() 882 { 883 if (!__str) 884 __throw_logic_error(__N("bitset::bitset(const char*)")); 885 886 const size_t __len = __builtin_strlen(__str); 887 _M_copy_from_ptr<char, std::char_traits<char>>(__str, __len, 0, 888 __len, '0', '1'); 889 } 890#endif 891 892 // 23.3.5.2 bitset operations: 893 //@{ 894 /** 895 * @brief Operations on bitsets. 896 * @param rhs A same-sized bitset. 897 * 898 * These should be self-explanatory. 899 */ 900 bitset<_Nb>& 901 operator&=(const bitset<_Nb>& __rhs) 902 { 903 this->_M_do_and(__rhs); 904 return *this; 905 } 906 907 bitset<_Nb>& 908 operator|=(const bitset<_Nb>& __rhs) 909 { 910 this->_M_do_or(__rhs); 911 return *this; 912 } 913 914 bitset<_Nb>& 915 operator^=(const bitset<_Nb>& __rhs) 916 { 917 this->_M_do_xor(__rhs); 918 return *this; 919 } 920 //@} 921 922 //@{ 923 /** 924 * @brief Operations on bitsets. 925 * @param position The number of places to shift. 926 * 927 * These should be self-explanatory. 928 */ 929 bitset<_Nb>& 930 operator<<=(size_t __position) 931 { 932 if (__builtin_expect(__position < _Nb, 1)) 933 { 934 this->_M_do_left_shift(__position); 935 this->_M_do_sanitize(); 936 } 937 else 938 this->_M_do_reset(); 939 return *this; 940 } 941 942 bitset<_Nb>& 943 operator>>=(size_t __position) 944 { 945 if (__builtin_expect(__position < _Nb, 1)) 946 { 947 this->_M_do_right_shift(__position); 948 this->_M_do_sanitize(); 949 } 950 else 951 this->_M_do_reset(); 952 return *this; 953 } 954 //@} 955 956 //@{ 957 /** 958 * These versions of single-bit set, reset, flip, and test are 959 * extensions from the SGI version. They do no range checking. 960 * @ingroup SGIextensions 961 */ 962 bitset<_Nb>& 963 _Unchecked_set(size_t __pos) 964 { 965 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 966 return *this; 967 } 968 969 bitset<_Nb>& 970 _Unchecked_set(size_t __pos, int __val) 971 { 972 if (__val) 973 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 974 else 975 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 976 return *this; 977 } 978 979 bitset<_Nb>& 980 _Unchecked_reset(size_t __pos) 981 { 982 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 983 return *this; 984 } 985 986 bitset<_Nb>& 987 _Unchecked_flip(size_t __pos) 988 { 989 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 990 return *this; 991 } 992 993 bool 994 _Unchecked_test(size_t __pos) const 995 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 996 != static_cast<_WordT>(0)); } 997 //@} 998 999 // Set, reset, and flip. 1000 /** 1001 * @brief Sets every bit to true. 1002 */ 1003 bitset<_Nb>& 1004 set() 1005 { 1006 this->_M_do_set(); 1007 this->_M_do_sanitize(); 1008 return *this; 1009 } 1010 1011 /** 1012 * @brief Sets a given bit to a particular value. 1013 * @param position The index of the bit. 1014 * @param val Either true or false, defaults to true. 1015 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1016 */ 1017 bitset<_Nb>& 1018 set(size_t __position, bool __val = true) 1019 { 1020 if (__position >= _Nb) 1021 __throw_out_of_range(__N("bitset::set")); 1022 return _Unchecked_set(__position, __val); 1023 } 1024 1025 /** 1026 * @brief Sets every bit to false. 1027 */ 1028 bitset<_Nb>& 1029 reset() 1030 { 1031 this->_M_do_reset(); 1032 return *this; 1033 } 1034 1035 /** 1036 * @brief Sets a given bit to false. 1037 * @param position The index of the bit. 1038 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1039 * 1040 * Same as writing @c set(pos,false). 1041 */ 1042 bitset<_Nb>& 1043 reset(size_t __position) 1044 { 1045 if (__position >= _Nb) 1046 __throw_out_of_range(__N("bitset::reset")); 1047 return _Unchecked_reset(__position); 1048 } 1049 1050 /** 1051 * @brief Toggles every bit to its opposite value. 1052 */ 1053 bitset<_Nb>& 1054 flip() 1055 { 1056 this->_M_do_flip(); 1057 this->_M_do_sanitize(); 1058 return *this; 1059 } 1060 1061 /** 1062 * @brief Toggles a given bit to its opposite value. 1063 * @param position The index of the bit. 1064 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1065 */ 1066 bitset<_Nb>& 1067 flip(size_t __position) 1068 { 1069 if (__position >= _Nb) 1070 __throw_out_of_range(__N("bitset::flip")); 1071 return _Unchecked_flip(__position); 1072 } 1073 1074 /// See the no-argument flip(). 1075 bitset<_Nb> 1076 operator~() const 1077 { return bitset<_Nb>(*this).flip(); } 1078 1079 //@{ 1080 /** 1081 * @brief Array-indexing support. 1082 * @param position Index into the %bitset. 1083 * @return A bool for a <em>const %bitset</em>. For non-const bitsets, an 1084 * instance of the reference proxy class. 1085 * @note These operators do no range checking and throw no exceptions, 1086 * as required by DR 11 to the standard. 1087 * 1088 * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already 1089 * resolves DR 11 (items 1 and 2), but does not do the range-checking 1090 * required by that DR's resolution. -pme 1091 * The DR has since been changed: range-checking is a precondition 1092 * (users' responsibility), and these functions must not throw. -pme 1093 */ 1094 reference 1095 operator[](size_t __position) 1096 { return reference(*this,__position); } 1097 1098 bool 1099 operator[](size_t __position) const 1100 { return _Unchecked_test(__position); } 1101 //@} 1102 1103 /** 1104 * @brief Returns a numerical interpretation of the %bitset. 1105 * @return The integral equivalent of the bits. 1106 * @throw std::overflow_error If there are too many bits to be 1107 * represented in an @c unsigned @c long. 1108 */ 1109 unsigned long 1110 to_ulong() const 1111 { return this->_M_do_to_ulong(); } 1112 1113#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1114 unsigned long long 1115 to_ullong() const 1116 { return this->_M_do_to_ullong(); } 1117#endif 1118 1119 /** 1120 * @brief Returns a character interpretation of the %bitset. 1121 * @return The string equivalent of the bits. 1122 * 1123 * Note the ordering of the bits: decreasing character positions 1124 * correspond to increasing bit positions (see the main class notes for 1125 * an example). 1126 */ 1127 template<class _CharT, class _Traits, class _Alloc> 1128 std::basic_string<_CharT, _Traits, _Alloc> 1129 to_string() const 1130 { 1131 std::basic_string<_CharT, _Traits, _Alloc> __result; 1132 _M_copy_to_string(__result, _CharT('0'), _CharT('1')); 1133 return __result; 1134 } 1135 1136 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1137 // 396. what are characters zero and one. 1138 template<class _CharT, class _Traits, class _Alloc> 1139 std::basic_string<_CharT, _Traits, _Alloc> 1140 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1141 { 1142 std::basic_string<_CharT, _Traits, _Alloc> __result; 1143 _M_copy_to_string(__result, __zero, __one); 1144 return __result; 1145 } 1146 1147 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1148 // 434. bitset::to_string() hard to use. 1149 template<class _CharT, class _Traits> 1150 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 1151 to_string() const 1152 { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); } 1153 1154 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1155 // 853. to_string needs updating with zero and one. 1156 template<class _CharT, class _Traits> 1157 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 1158 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1159 { return to_string<_CharT, _Traits, 1160 std::allocator<_CharT> >(__zero, __one); } 1161 1162 template<class _CharT> 1163 std::basic_string<_CharT, std::char_traits<_CharT>, 1164 std::allocator<_CharT> > 1165 to_string() const 1166 { 1167 return to_string<_CharT, std::char_traits<_CharT>, 1168 std::allocator<_CharT> >(); 1169 } 1170 1171 template<class _CharT> 1172 std::basic_string<_CharT, std::char_traits<_CharT>, 1173 std::allocator<_CharT> > 1174 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1175 { 1176 return to_string<_CharT, std::char_traits<_CharT>, 1177 std::allocator<_CharT> >(__zero, __one); 1178 } 1179 1180 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 1181 to_string() const 1182 { 1183 return to_string<char, std::char_traits<char>, 1184 std::allocator<char> >(); 1185 } 1186 1187 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 1188 to_string(char __zero, char __one = '1') const 1189 { 1190 return to_string<char, std::char_traits<char>, 1191 std::allocator<char> >(__zero, __one); 1192 } 1193 1194 // Helper functions for string operations. 1195 template<class _CharT, class _Traits> 1196 void 1197 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 1198 _CharT, _CharT); 1199 1200 template<class _CharT, class _Traits, class _Alloc> 1201 void 1202 _M_copy_from_string(const std::basic_string<_CharT, 1203 _Traits, _Alloc>& __s, size_t __pos, size_t __n, 1204 _CharT __zero, _CharT __one) 1205 { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n, 1206 __zero, __one); } 1207 1208 template<class _CharT, class _Traits, class _Alloc> 1209 void 1210 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&, 1211 _CharT, _CharT) const; 1212 1213 // NB: Backward compat. 1214 template<class _CharT, class _Traits, class _Alloc> 1215 void 1216 _M_copy_from_string(const std::basic_string<_CharT, 1217 _Traits, _Alloc>& __s, size_t __pos, size_t __n) 1218 { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); } 1219 1220 template<class _CharT, class _Traits, class _Alloc> 1221 void 1222 _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const 1223 { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); } 1224 1225 /// Returns the number of bits which are set. 1226 size_t 1227 count() const 1228 { return this->_M_do_count(); } 1229 1230 /// Returns the total number of bits. 1231 size_t 1232 size() const 1233 { return _Nb; } 1234 1235 //@{ 1236 /// These comparisons for equality/inequality are, well, @e bitwise. 1237 bool 1238 operator==(const bitset<_Nb>& __rhs) const 1239 { return this->_M_is_equal(__rhs); } 1240 1241 bool 1242 operator!=(const bitset<_Nb>& __rhs) const 1243 { return !this->_M_is_equal(__rhs); } 1244 //@} 1245 1246 /** 1247 * @brief Tests the value of a bit. 1248 * @param position The index of a bit. 1249 * @return The value at @a pos. 1250 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1251 */ 1252 bool 1253 test(size_t __position) const 1254 { 1255 if (__position >= _Nb) 1256 __throw_out_of_range(__N("bitset::test")); 1257 return _Unchecked_test(__position); 1258 } 1259 1260 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1261 // DR 693. std::bitset::all() missing. 1262 /** 1263 * @brief Tests whether all the bits are on. 1264 * @return True if all the bits are set. 1265 */ 1266 bool 1267 all() const 1268 { return this->_M_are_all_aux() == _Nb; } 1269 1270 /** 1271 * @brief Tests whether any of the bits are on. 1272 * @return True if at least one bit is set. 1273 */ 1274 bool 1275 any() const 1276 { return this->_M_is_any(); } 1277 1278 /** 1279 * @brief Tests whether any of the bits are on. 1280 * @return True if none of the bits are set. 1281 */ 1282 bool 1283 none() const 1284 { return !this->_M_is_any(); } 1285 1286 //@{ 1287 /// Self-explanatory. 1288 bitset<_Nb> 1289 operator<<(size_t __position) const 1290 { return bitset<_Nb>(*this) <<= __position; } 1291 1292 bitset<_Nb> 1293 operator>>(size_t __position) const 1294 { return bitset<_Nb>(*this) >>= __position; } 1295 //@} 1296 1297 /** 1298 * @brief Finds the index of the first "on" bit. 1299 * @return The index of the first bit set, or size() if not found. 1300 * @ingroup SGIextensions 1301 * @sa _Find_next 1302 */ 1303 size_t 1304 _Find_first() const 1305 { return this->_M_do_find_first(_Nb); } 1306 1307 /** 1308 * @brief Finds the index of the next "on" bit after prev. 1309 * @return The index of the next bit set, or size() if not found. 1310 * @param prev Where to start searching. 1311 * @ingroup SGIextensions 1312 * @sa _Find_first 1313 */ 1314 size_t 1315 _Find_next(size_t __prev ) const 1316 { return this->_M_do_find_next(__prev, _Nb); } 1317 }; 1318 1319 // Definitions of non-inline member functions. 1320 template<size_t _Nb> 1321 template<class _CharT, class _Traits> 1322 void 1323 bitset<_Nb>:: 1324 _M_copy_from_ptr(const _CharT* __s, size_t __len, 1325 size_t __pos, size_t __n, _CharT __zero, _CharT __one) 1326 { 1327 reset(); 1328 const size_t __nbits = std::min(_Nb, std::min(__n, __len - __pos)); 1329 for (size_t __i = __nbits; __i > 0; --__i) 1330 { 1331 const _CharT __c = __s[__pos + __nbits - __i]; 1332 if (_Traits::eq(__c, __zero)) 1333 ; 1334 else if (_Traits::eq(__c, __one)) 1335 _Unchecked_set(__i - 1); 1336 else 1337 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr")); 1338 } 1339 } 1340 1341 template<size_t _Nb> 1342 template<class _CharT, class _Traits, class _Alloc> 1343 void 1344 bitset<_Nb>:: 1345 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s, 1346 _CharT __zero, _CharT __one) const 1347 { 1348 __s.assign(_Nb, __zero); 1349 for (size_t __i = _Nb; __i > 0; --__i) 1350 if (_Unchecked_test(__i - 1)) 1351 _Traits::assign(__s[_Nb - __i], __one); 1352 } 1353 1354 // 23.3.5.3 bitset operations: 1355 //@{ 1356 /** 1357 * @brief Global bitwise operations on bitsets. 1358 * @param x A bitset. 1359 * @param y A bitset of the same size as @a x. 1360 * @return A new bitset. 1361 * 1362 * These should be self-explanatory. 1363 */ 1364 template<size_t _Nb> 1365 inline bitset<_Nb> 1366 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 1367 { 1368 bitset<_Nb> __result(__x); 1369 __result &= __y; 1370 return __result; 1371 } 1372 1373 template<size_t _Nb> 1374 inline bitset<_Nb> 1375 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 1376 { 1377 bitset<_Nb> __result(__x); 1378 __result |= __y; 1379 return __result; 1380 } 1381 1382 template <size_t _Nb> 1383 inline bitset<_Nb> 1384 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 1385 { 1386 bitset<_Nb> __result(__x); 1387 __result ^= __y; 1388 return __result; 1389 } 1390 //@} 1391 1392 //@{ 1393 /** 1394 * @brief Global I/O operators for bitsets. 1395 * 1396 * Direct I/O between streams and bitsets is supported. Output is 1397 * straightforward. Input will skip whitespace, only accept @a 0 and @a 1 1398 * characters, and will only extract as many digits as the %bitset will 1399 * hold. 1400 */ 1401 template<class _CharT, class _Traits, size_t _Nb> 1402 std::basic_istream<_CharT, _Traits>& 1403 operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 1404 { 1405 typedef typename _Traits::char_type char_type; 1406 typedef std::basic_istream<_CharT, _Traits> __istream_type; 1407 typedef typename __istream_type::ios_base __ios_base; 1408 1409 std::basic_string<_CharT, _Traits> __tmp; 1410 __tmp.reserve(_Nb); 1411 1412 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1413 // 303. Bitset input operator underspecified 1414 const char_type __zero = __is.widen('0'); 1415 const char_type __one = __is.widen('1'); 1416 1417 typename __ios_base::iostate __state = __ios_base::goodbit; 1418 typename __istream_type::sentry __sentry(__is); 1419 if (__sentry) 1420 { 1421 __try 1422 { 1423 for (size_t __i = _Nb; __i > 0; --__i) 1424 { 1425 static typename _Traits::int_type __eof = _Traits::eof(); 1426 1427 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 1428 if (_Traits::eq_int_type(__c1, __eof)) 1429 { 1430 __state |= __ios_base::eofbit; 1431 break; 1432 } 1433 else 1434 { 1435 const char_type __c2 = _Traits::to_char_type(__c1); 1436 if (_Traits::eq(__c2, __zero)) 1437 __tmp.push_back(__zero); 1438 else if (_Traits::eq(__c2, __one)) 1439 __tmp.push_back(__one); 1440 else if (_Traits:: 1441 eq_int_type(__is.rdbuf()->sputbackc(__c2), 1442 __eof)) 1443 { 1444 __state |= __ios_base::failbit; 1445 break; 1446 } 1447 } 1448 } 1449 } 1450 __catch(__cxxabiv1::__forced_unwind&) 1451 { 1452 __is._M_setstate(__ios_base::badbit); 1453 __throw_exception_again; 1454 } 1455 __catch(...) 1456 { __is._M_setstate(__ios_base::badbit); } 1457 } 1458 1459 if (__tmp.empty() && _Nb) 1460 __state |= __ios_base::failbit; 1461 else 1462 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb, 1463 __zero, __one); 1464 if (__state) 1465 __is.setstate(__state); 1466 return __is; 1467 } 1468 1469 template <class _CharT, class _Traits, size_t _Nb> 1470 std::basic_ostream<_CharT, _Traits>& 1471 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 1472 const bitset<_Nb>& __x) 1473 { 1474 std::basic_string<_CharT, _Traits> __tmp; 1475 1476 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1477 // 396. what are characters zero and one. 1478 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc()); 1479 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 1480 return __os << __tmp; 1481 } 1482 //@} 1483 1484_GLIBCXX_END_NESTED_NAMESPACE 1485 1486#undef _GLIBCXX_BITSET_WORDS 1487#undef _GLIBCXX_BITSET_BITS_PER_WORD 1488 1489#ifdef __GXX_EXPERIMENTAL_CXX0X__ 1490 1491#include <bits/functional_hash.h> 1492 1493_GLIBCXX_BEGIN_NAMESPACE(std) 1494 1495 // DR 1182. 1496 /// std::hash specialization for bitset. 1497 template<size_t _Nb> 1498 struct hash<_GLIBCXX_STD_D::bitset<_Nb>> 1499 : public std::unary_function<_GLIBCXX_STD_D::bitset<_Nb>, size_t> 1500 { 1501 size_t 1502 operator()(const _GLIBCXX_STD_D::bitset<_Nb>& __b) const 1503 { 1504 const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__; 1505 return std::_Fnv_hash::hash(__b._M_getdata(), __clength); 1506 } 1507 }; 1508 1509 template<> 1510 struct hash<_GLIBCXX_STD_D::bitset<0>> 1511 : public std::unary_function<_GLIBCXX_STD_D::bitset<0>, size_t> 1512 { 1513 size_t 1514 operator()(const _GLIBCXX_STD_D::bitset<0>&) const 1515 { return 0; } 1516 }; 1517 1518_GLIBCXX_END_NAMESPACE 1519 1520#endif // __GXX_EXPERIMENTAL_CXX0X__ 1521 1522#ifdef _GLIBCXX_DEBUG 1523# include <debug/bitset> 1524#endif 1525 1526#ifdef _GLIBCXX_PROFILE 1527# include <profile/bitset> 1528#endif 1529 1530#endif /* _GLIBCXX_BITSET */ 1531