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 character %array.
 874        *  @param  str  An %array of characters @a zero and @a one.
 875        *  @param  n    The number of characters to use.
 876        *  @param  zero The character corresponding to the value 0.
 877        *  @param  one  The character corresponding to the value 1.
 878        *  @throw  std::invalid_argument  If a character appears in the string
 879        *                                 which is neither @a zero nor @a one.
 880        */
 881       template<typename _CharT>
 882         explicit
 883         bitset(const _CharT* __str,
 884                typename std::basic_string<_CharT>::size_type __n
 885                = std::basic_string<_CharT>::npos,
 886                _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'))
 887         : _Base()
 888         {
 889           if (!__str)
 890             __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)"));
 891
 892           if (__n == std::basic_string<_CharT>::npos)
 893             __n = std::char_traits<_CharT>::length(__str);
 894           _M_copy_from_ptr<_CharT, std::char_traits<_CharT>>(__str, __n, 0,
 895                                                              __n, __zero,
 896                                                              __one);
 897         }
 898 #endif
 899
 900       // 23.3.5.2 bitset operations:
 901       //@{
 902       /**
 903        *  @brief  Operations on bitsets.
 904        *  @param  rhs  A same-sized bitset.
 905        *
 906        *  These should be self-explanatory.
 907        */
 908       bitset<_Nb>&
 909       operator&=(const bitset<_Nb>& __rhs)
 910       {
 911         this->_M_do_and(__rhs);
 912         return *this;
 913       }
 914
 915       bitset<_Nb>&
 916       operator|=(const bitset<_Nb>& __rhs)
 917       {
 918         this->_M_do_or(__rhs);
 919         return *this;
 920       }
 921
 922       bitset<_Nb>&
 923       operator^=(const bitset<_Nb>& __rhs)
 924       {
 925         this->_M_do_xor(__rhs);
 926         return *this;
 927       }
 928       //@}
 929
 930       //@{
 931       /**
 932        *  @brief  Operations on bitsets.
 933        *  @param  position  The number of places to shift.
 934        *
 935        *  These should be self-explanatory.
 936        */
 937       bitset<_Nb>&
 938       operator<<=(size_t __position)
 939       {
 940         if (__builtin_expect(__position < _Nb, 1))
 941           {
 942             this->_M_do_left_shift(__position);
 943             this->_M_do_sanitize();
 944           }
 945         else
 946           this->_M_do_reset();
 947         return *this;
 948       }
 949
 950       bitset<_Nb>&
 951       operator>>=(size_t __position)
 952       {
 953         if (__builtin_expect(__position < _Nb, 1))
 954           {
 955             this->_M_do_right_shift(__position);
 956             this->_M_do_sanitize();
 957           }
 958         else
 959           this->_M_do_reset();
 960         return *this;
 961       }
 962       //@}
 963
 964       //@{
 965       /**
 966        *  These versions of single-bit set, reset, flip, and test are
 967        *  extensions from the SGI version.  They do no range checking.
 968        *  @ingroup SGIextensions
 969        */
 970       bitset<_Nb>&
 971       _Unchecked_set(size_t __pos)
 972       {
 973         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 974         return *this;
 975       }
 976
 977       bitset<_Nb>&
 978       _Unchecked_set(size_t __pos, int __val)
 979       {
 980         if (__val)
 981           this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 982         else
 983           this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 984         return *this;
 985       }
 986
 987       bitset<_Nb>&
 988       _Unchecked_reset(size_t __pos)
 989       {
 990         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 991         return *this;
 992       }
 993
 994       bitset<_Nb>&
 995       _Unchecked_flip(size_t __pos)
 996       {
 997         this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
 998         return *this;
 999       }
1000
1001       bool
1002       _Unchecked_test(size_t __pos) const
1003       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
1004                 != static_cast<_WordT>(0)); }
1005       //@}
1006
1007       // Set, reset, and flip.
1008       /**
1009        *  @brief Sets every bit to true.
1010        */
1011       bitset<_Nb>&
1012       set()
1013       {
1014         this->_M_do_set();
1015         this->_M_do_sanitize();
1016         return *this;
1017       }
1018
1019       /**
1020        *  @brief Sets a given bit to a particular value.
1021        *  @param  position  The index of the bit.
1022        *  @param  val  Either true or false, defaults to true.
1023        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1024        */
1025       bitset<_Nb>&
1026       set(size_t __position, bool __val = true)
1027       {
1028         if (__position >= _Nb)
1029           __throw_out_of_range(__N("bitset::set"));
1030         return _Unchecked_set(__position, __val);
1031       }
1032
1033       /**
1034        *  @brief Sets every bit to false.
1035        */
1036       bitset<_Nb>&
1037       reset()
1038       {
1039         this->_M_do_reset();
1040         return *this;
1041       }
1042
1043       /**
1044        *  @brief Sets a given bit to false.
1045        *  @param  position  The index of the bit.
1046        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1047        *
1048        *  Same as writing @c set(pos,false).
1049        */
1050       bitset<_Nb>&
1051       reset(size_t __position)
1052       {
1053         if (__position >= _Nb)
1054           __throw_out_of_range(__N("bitset::reset"));
1055         return _Unchecked_reset(__position);
1056       }
1057
1058       /**
1059        *  @brief Toggles every bit to its opposite value.
1060        */
1061       bitset<_Nb>&
1062       flip()
1063       {
1064         this->_M_do_flip();
1065         this->_M_do_sanitize();
1066         return *this;
1067       }
1068
1069       /**
1070        *  @brief Toggles a given bit to its opposite value.
1071        *  @param  position  The index of the bit.
1072        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1073        */
1074       bitset<_Nb>&
1075       flip(size_t __position)
1076       {
1077         if (__position >= _Nb)
1078           __throw_out_of_range(__N("bitset::flip"));
1079         return _Unchecked_flip(__position);
1080       }
1081
1082       /// See the no-argument flip().
1083       bitset<_Nb>
1084       operator~() const
1085       { return bitset<_Nb>(*this).flip(); }
1086
1087       //@{
1088       /**
1089        *  @brief  Array-indexing support.
1090        *  @param  position  Index into the %bitset.
1091        *  @return  A bool for a <em>const %bitset</em>.  For non-const bitsets, an
1092        *           instance of the reference proxy class.
1093        *  @note  These operators do no range checking and throw no exceptions,
1094        *         as required by DR 11 to the standard.
1095        *
1096        *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
1097        *  resolves DR 11 (items 1 and 2), but does not do the range-checking
1098        *  required by that DR's resolution.  -pme
1099        *  The DR has since been changed:  range-checking is a precondition
1100        *  (users' responsibility), and these functions must not throw.  -pme
1101        */
1102       reference
1103       operator[](size_t __position)
1104       { return reference(*this,__position); }
1105
1106       bool
1107       operator[](size_t __position) const
1108       { return _Unchecked_test(__position); }
1109       //@}
1110
1111       /**
1112        *  @brief Returns a numerical interpretation of the %bitset.
1113        *  @return  The integral equivalent of the bits.
1114        *  @throw  std::overflow_error  If there are too many bits to be
1115        *                               represented in an @c unsigned @c long.
1116        */
1117       unsigned long
1118       to_ulong() const
1119       { return this->_M_do_to_ulong(); }
1120
1121 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1122       unsigned long long
1123       to_ullong() const
1124       { return this->_M_do_to_ullong(); }
1125 #endif
1126
1127       /**
1128        *  @brief Returns a character interpretation of the %bitset.
1129        *  @return  The string equivalent of the bits.
1130        *
1131        *  Note the ordering of the bits:  decreasing character positions
1132        *  correspond to increasing bit positions (see the main class notes for
1133        *  an example).
1134        */
1135       template<class _CharT, class _Traits, class _Alloc>
1136         std::basic_string<_CharT, _Traits, _Alloc>
1137         to_string() const
1138         {
1139           std::basic_string<_CharT, _Traits, _Alloc> __result;
1140           _M_copy_to_string(__result, _CharT('0'), _CharT('1'));
1141           return __result;
1142         }
1143
1144       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1145       // 396. what are characters zero and one.
1146       template<class _CharT, class _Traits, class _Alloc>
1147         std::basic_string<_CharT, _Traits, _Alloc>
1148         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1149         {
1150           std::basic_string<_CharT, _Traits, _Alloc> __result;
1151           _M_copy_to_string(__result, __zero, __one);
1152           return __result;
1153         }
1154
1155       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1156       // 434. bitset::to_string() hard to use.
1157       template<class _CharT, class _Traits>
1158         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1159         to_string() const
1160         { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
1161
1162       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1163       // 853. to_string needs updating with zero and one.
1164       template<class _CharT, class _Traits>
1165         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1166         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1167         { return to_string<_CharT, _Traits,
1168                            std::allocator<_CharT> >(__zero, __one); }
1169
1170       template<class _CharT>
1171         std::basic_string<_CharT, std::char_traits<_CharT>,
1172                           std::allocator<_CharT> >
1173         to_string() const
1174         {
1175           return to_string<_CharT, std::char_traits<_CharT>,
1176                            std::allocator<_CharT> >();
1177         }
1178
1179       template<class _CharT>
1180         std::basic_string<_CharT, std::char_traits<_CharT>,
1181                           std::allocator<_CharT> >
1182         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1183         {
1184           return to_string<_CharT, std::char_traits<_CharT>,
1185                            std::allocator<_CharT> >(__zero, __one);
1186         }
1187
1188       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1189       to_string() const
1190       {
1191         return to_string<char, std::char_traits<char>,
1192                          std::allocator<char> >();
1193       }
1194
1195       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1196       to_string(char __zero, char __one = '1') const
1197       {
1198         return to_string<char, std::char_traits<char>,
1199                          std::allocator<char> >(__zero, __one);
1200       }
1201
1202       // Helper functions for string operations.
1203       template<class _CharT, class _Traits>
1204         void
1205         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
1206                          _CharT, _CharT);
1207
1208       template<class _CharT, class _Traits, class _Alloc>
1209         void
1210         _M_copy_from_string(const std::basic_string<_CharT,
1211                             _Traits, _Alloc>& __s, size_t __pos, size_t __n,
1212                             _CharT __zero, _CharT __one)
1213         { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n,
1214                                             __zero, __one); }
1215
1216       template<class _CharT, class _Traits, class _Alloc>
1217         void
1218         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&,
1219                           _CharT, _CharT) const;
1220
1221       // NB: Backward compat.
1222       template<class _CharT, class _Traits, class _Alloc>
1223         void
1224         _M_copy_from_string(const std::basic_string<_CharT,
1225                             _Traits, _Alloc>& __s, size_t __pos, size_t __n)
1226         { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); }
1227
1228       template<class _CharT, class _Traits, class _Alloc>
1229         void
1230         _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const
1231         { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); }
1232
1233       /// Returns the number of bits which are set.
1234       size_t
1235       count() const
1236       { return this->_M_do_count(); }
1237
1238       /// Returns the total number of bits.
1239       size_t
1240       size() const
1241       { return _Nb; }
1242
1243       //@{
1244       /// These comparisons for equality/inequality are, well, @e bitwise.
1245       bool
1246       operator==(const bitset<_Nb>& __rhs) const
1247       { return this->_M_is_equal(__rhs); }
1248
1249       bool
1250       operator!=(const bitset<_Nb>& __rhs) const
1251       { return !this->_M_is_equal(__rhs); }
1252       //@}
1253
1254       /**
1255        *  @brief Tests the value of a bit.
1256        *  @param  position  The index of a bit.
1257        *  @return  The value at @a pos.
1258        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1259        */
1260       bool
1261       test(size_t __position) const
1262       {
1263         if (__position >= _Nb)
1264           __throw_out_of_range(__N("bitset::test"));
1265         return _Unchecked_test(__position);
1266       }
1267
1268       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1269       // DR 693. std::bitset::all() missing.
1270       /**
1271        *  @brief Tests whether all the bits are on.
1272        *  @return  True if all the bits are set.
1273        */
1274       bool
1275       all() const
1276       { return this->_M_are_all_aux() == _Nb; }
1277
1278       /**
1279        *  @brief Tests whether any of the bits are on.
1280        *  @return  True if at least one bit is set.
1281        */
1282       bool
1283       any() const
1284       { return this->_M_is_any(); }
1285
1286       /**
1287        *  @brief Tests whether any of the bits are on.
1288        *  @return  True if none of the bits are set.
1289        */
1290       bool
1291       none() const
1292       { return !this->_M_is_any(); }
1293
1294       //@{
1295       /// Self-explanatory.
1296       bitset<_Nb>
1297       operator<<(size_t __position) const
1298       { return bitset<_Nb>(*this) <<= __position; }
1299
1300       bitset<_Nb>
1301       operator>>(size_t __position) const
1302       { return bitset<_Nb>(*this) >>= __position; }
1303       //@}
1304
1305       /**
1306        *  @brief  Finds the index of the first "on" bit.
1307        *  @return  The index of the first bit set, or size() if not found.
1308        *  @ingroup SGIextensions
1309        *  @sa  _Find_next
1310        */
1311       size_t
1312       _Find_first() const
1313       { return this->_M_do_find_first(_Nb); }
1314
1315       /**
1316        *  @brief  Finds the index of the next "on" bit after prev.
1317        *  @return  The index of the next bit set, or size() if not found.
1318        *  @param  prev  Where to start searching.
1319        *  @ingroup SGIextensions
1320        *  @sa  _Find_first
1321        */
1322       size_t
1323       _Find_next(size_t __prev ) const
1324       { return this->_M_do_find_next(__prev, _Nb); }
1325     };
1326
1327   // Definitions of non-inline member functions.
1328   template<size_t _Nb>
1329     template<class _CharT, class _Traits>
1330       void
1331       bitset<_Nb>::
1332       _M_copy_from_ptr(const _CharT* __s, size_t __len,
1333                        size_t __pos, size_t __n, _CharT __zero, _CharT __one)
1334       {
1335         reset();
1336         const size_t __nbits = std::min(_Nb, std::min(__n, __len - __pos));
1337         for (size_t __i = __nbits; __i > 0; --__i)
1338           {
1339             const _CharT __c = __s[__pos + __nbits - __i];
1340             if (_Traits::eq(__c, __zero))
1341               ;
1342             else if (_Traits::eq(__c, __one))
1343               _Unchecked_set(__i - 1);
1344             else
1345               __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
1346           }
1347       }
1348
1349   template<size_t _Nb>
1350     template<class _CharT, class _Traits, class _Alloc>
1351       void
1352       bitset<_Nb>::
1353       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s,
1354                         _CharT __zero, _CharT __one) const
1355       {
1356         __s.assign(_Nb, __zero);
1357         for (size_t __i = _Nb; __i > 0; --__i)
1358           if (_Unchecked_test(__i - 1))
1359             _Traits::assign(__s[_Nb - __i], __one);
1360       }
1361
1362   // 23.3.5.3 bitset operations:
1363   //@{
1364   /**
1365    *  @brief  Global bitwise operations on bitsets.
1366    *  @param  x  A bitset.
1367    *  @param  y  A bitset of the same size as @a x.
1368    *  @return  A new bitset.
1369    *
1370    *  These should be self-explanatory.
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   template <size_t _Nb>
1391     inline bitset<_Nb>
1392     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1393     {
1394       bitset<_Nb> __result(__x);
1395       __result ^= __y;
1396       return __result;
1397     }
1398   //@}
1399
1400   //@{
1401   /**
1402    *  @brief Global I/O operators for bitsets.
1403    *
1404    *  Direct I/O between streams and bitsets is supported.  Output is
1405    *  straightforward.  Input will skip whitespace, only accept @a 0 and @a 1
1406    *  characters, and will only extract as many digits as the %bitset will
1407    *  hold.
1408   */
1409   template<class _CharT, class _Traits, size_t _Nb>
1410     std::basic_istream<_CharT, _Traits>&
1411     operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
1412     {
1413       typedef typename _Traits::char_type          char_type;
1414       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
1415       typedef typename __istream_type::ios_base    __ios_base;
1416
1417       std::basic_string<_CharT, _Traits> __tmp;
1418       __tmp.reserve(_Nb);
1419
1420       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1421       // 303. Bitset input operator underspecified
1422       const char_type __zero = __is.widen('0');
1423       const char_type __one = __is.widen('1');
1424
1425       typename __ios_base::iostate __state = __ios_base::goodbit;
1426       typename __istream_type::sentry __sentry(__is);
1427       if (__sentry)
1428         {
1429           __try
1430             {
1431               for (size_t __i = _Nb; __i > 0; --__i)
1432                 {
1433                   static typename _Traits::int_type __eof = _Traits::eof();
1434
1435                   typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
1436                   if (_Traits::eq_int_type(__c1, __eof))
1437                     {
1438                       __state |= __ios_base::eofbit;
1439                       break;
1440                     }
1441                   else
1442                     {
1443                       const char_type __c2 = _Traits::to_char_type(__c1);
1444                       if (_Traits::eq(__c2, __zero))
1445                         __tmp.push_back(__zero);
1446                       else if (_Traits::eq(__c2, __one))
1447                         __tmp.push_back(__one);
1448                       else if (_Traits::
1449                                eq_int_type(__is.rdbuf()->sputbackc(__c2),
1450                                            __eof))
1451                         {
1452                           __state |= __ios_base::failbit;
1453                           break;
1454                         }
1455                     }
1456                 }
1457             }
1458           __catch(__cxxabiv1::__forced_unwind&)
1459             {
1460               __is._M_setstate(__ios_base::badbit);
1461               __throw_exception_again;
1462             }
1463           __catch(...)
1464             { __is._M_setstate(__ios_base::badbit); }
1465         }
1466
1467       if (__tmp.empty() && _Nb)
1468         __state |= __ios_base::failbit;
1469       else
1470         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb,
1471                                 __zero, __one);
1472       if (__state)
1473         __is.setstate(__state);
1474       return __is;
1475     }
1476
1477   template <class _CharT, class _Traits, size_t _Nb>
1478     std::basic_ostream<_CharT, _Traits>&
1479     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1480                const bitset<_Nb>& __x)
1481     {
1482       std::basic_string<_CharT, _Traits> __tmp;
1483
1484       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1485       // 396. what are characters zero and one.
1486       const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
1487       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1488       return __os << __tmp;
1489     }
1490   //@}
1491
1492 _GLIBCXX_END_NESTED_NAMESPACE
1493
1494 #undef _GLIBCXX_BITSET_WORDS
1495 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1496
1497 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1498
1499 #include <bits/functional_hash.h>
1500
1501 _GLIBCXX_BEGIN_NAMESPACE(std)
1502
1503   // DR 1182.
1504   /// std::hash specialization for bitset.
1505   template<size_t _Nb>
1506     struct hash<_GLIBCXX_STD_D::bitset<_Nb>>
1507     : public __hash_base<size_t, _GLIBCXX_STD_D::bitset<_Nb>>
1508     {
1509       size_t
1510       operator()(const _GLIBCXX_STD_D::bitset<_Nb>& __b) const
1511       {
1512         const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__;
1513         return std::_Hash_impl::hash(__b._M_getdata(), __clength);
1514       }
1515     };
1516
1517   template<>
1518     struct hash<_GLIBCXX_STD_D::bitset<0>>
1519     : public __hash_base<size_t, _GLIBCXX_STD_D::bitset<0>>
1520     {
1521       size_t
1522       operator()(const _GLIBCXX_STD_D::bitset<0>&) const
1523       { return 0; }
1524     };
1525
1526 _GLIBCXX_END_NAMESPACE
1527
1528 #endif // __GXX_EXPERIMENTAL_CXX0X__
1529
1530 #ifdef _GLIBCXX_DEBUG
1531 # include <debug/bitset>
1532 #endif
1533
1534 #ifdef _GLIBCXX_PROFILE
1535 # include <profile/bitset>
1536 #endif
1537
1538 #endif /* _GLIBCXX_BITSET */