libstdc++-v3/include/std/bitset

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