l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/std/bitset

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