libstdc++-v3/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 http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23
 638    *  for a description of extensions.
 639    *
 640    *  Most of the actual code isn't contained in %bitset<> itself, but in the
 641    *  base class _Base_bitset.  The base class works with whole words, not with
 642    *  individual bits.  This allows us to specialize _Base_bitset for the
 643    *  important special case where the %bitset is only a single word.
 644    *
 645    *  Extra confusion can result due to the fact that the storage for
 646    *  _Base_bitset @e is a regular array, and is indexed as such.  This is
 647    *  carefully encapsulated.
 648   */
 649   template<size_t _Nb>
 650     class bitset
 651     : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
 652     {
 653     private:
 654       typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
 655       typedef unsigned long _WordT;
 656
 657       void
 658         _M_do_sanitize()
 659         {
 660           _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>::
 661             _S_do_sanitize(this->_M_hiword());
 662         }
 663
 664     public:
 665       /**
 666        *  This encapsulates the concept of a single bit.  An instance of this
 667        *  class is a proxy for an actual bit; this way the individual bit
 668        *  operations are done as faster word-size bitwise instructions.
 669        *
 670        *  Most users will never need to use this class directly; conversions
 671        *  to and from bool are automatic and should be transparent.  Overloaded
 672        *  operators help to preserve the illusion.
 673        *
 674        *  (On a typical system, this "bit %reference" is 64 times the size of
 675        *  an actual bit.  Ha.)
 676        */
 677       class reference
 678       {
 679         friend class bitset;
 680
 681         _WordT *_M_wp;
 682         size_t _M_bpos;
 683
 684         // left undefined
 685         reference();
 686
 687       public:
 688         reference(bitset& __b, size_t __pos)
 689         {
 690           _M_wp = &__b._M_getword(__pos);
 691           _M_bpos = _Base::_S_whichbit(__pos);
 692         }
 693
 694         ~reference()
 695         { }
 696
 697         // For b[i] = __x;
 698         reference&
 699         operator=(bool __x)
 700         {
 701           if (__x)
 702             *_M_wp |= _Base::_S_maskbit(_M_bpos);
 703           else
 704             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
 705           return *this;
 706         }
 707
 708         // For b[i] = b[__j];
 709         reference&
 710         operator=(const reference& __j)
 711         {
 712           if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
 713             *_M_wp |= _Base::_S_maskbit(_M_bpos);
 714           else
 715             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
 716           return *this;
 717         }
 718
 719         // Flips the bit
 720         bool
 721         operator~() const
 722         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
 723
 724         // For __x = b[i];
 725         operator bool() const
 726         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
 727
 728         // For b[i].flip();
 729         reference&
 730         flip()
 731         {
 732           *_M_wp ^= _Base::_S_maskbit(_M_bpos);
 733           return *this;
 734         }
 735       };
 736       friend class reference;
 737
 738       // 23.3.5.1 constructors:
 739       /// All bits set to zero.
 740       bitset()
 741       { }
 742
 743       /// Initial bits bitwise-copied from a single word (others set to zero).
 744       bitset(unsigned long __val)
 745       : _Base(__val)
 746       { _M_do_sanitize(); }
 747
 748       /**
 749        *  @brief  Use a subset of a string.
 750        *  @param  s  A string of '0' and '1' characters.
 751        *  @param  position  Index of the first character in @a s to use;
 752        *                    defaults to zero.
 753        *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
 754        *  @throw  std::invalid_argument  If a character appears in the string
 755        *                                 which is neither '0' nor '1'.
 756        */
 757       template<class _CharT, class _Traits, class _Alloc>
 758         explicit
 759         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 760                size_t __position = 0)
 761         : _Base()
 762         {
 763           if (__position > __s.size())
 764             __throw_out_of_range(__N("bitset::bitset initial position "
 765                                      "not valid"));
 766           _M_copy_from_string(__s, __position,
 767                               std::basic_string<_CharT, _Traits, _Alloc>::npos);
 768         }
 769
 770       /**
 771        *  @brief  Use a subset of a string.
 772        *  @param  s  A string of '0' and '1' characters.
 773        *  @param  position  Index of the first character in @a s to use.
 774        *  @param  n    The number of characters to copy.
 775        *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
 776        *  @throw  std::invalid_argument  If a character appears in the string
 777        *                                 which is neither '0' nor '1'.
 778        */
 779       template<class _CharT, class _Traits, class _Alloc>
 780         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 781                size_t __position, size_t __n)
 782         : _Base()
 783         {
 784           if (__position > __s.size())
 785             __throw_out_of_range(__N("bitset::bitset initial position "
 786                                      "not valid"));
 787           _M_copy_from_string(__s, __position, __n);
 788         }
 789
 790       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 791       // 778. std::bitset does not have any constructor taking a string literal
 792       explicit
 793       bitset(const char* __s)
 794       : _Base()
 795       { _M_copy_from_ptr(__s, char_traits<char>::length(__s), 0, size_t(-1)); }
 796
 797       // 23.3.5.2 bitset operations:
 798       //@{
 799       /**
 800        *  @brief  Operations on bitsets.
 801        *  @param  rhs  A same-sized bitset.
 802        *
 803        *  These should be self-explanatory.
 804        */
 805       bitset<_Nb>&
 806       operator&=(const bitset<_Nb>& __rhs)
 807       {
 808         this->_M_do_and(__rhs);
 809         return *this;
 810       }
 811
 812       bitset<_Nb>&
 813       operator|=(const bitset<_Nb>& __rhs)
 814       {
 815         this->_M_do_or(__rhs);
 816         return *this;
 817       }
 818
 819       bitset<_Nb>&
 820       operator^=(const bitset<_Nb>& __rhs)
 821       {
 822         this->_M_do_xor(__rhs);
 823         return *this;
 824       }
 825       //@}
 826
 827       //@{
 828       /**
 829        *  @brief  Operations on bitsets.
 830        *  @param  position  The number of places to shift.
 831        *
 832        *  These should be self-explanatory.
 833        */
 834       bitset<_Nb>&
 835       operator<<=(size_t __position)
 836       {
 837         if (__builtin_expect(__position < _Nb, 1))
 838           {
 839             this->_M_do_left_shift(__position);
 840             this->_M_do_sanitize();
 841           }
 842         else
 843           this->_M_do_reset();
 844         return *this;
 845       }
 846
 847       bitset<_Nb>&
 848       operator>>=(size_t __position)
 849       {
 850         if (__builtin_expect(__position < _Nb, 1))
 851           {
 852             this->_M_do_right_shift(__position);
 853             this->_M_do_sanitize();
 854           }
 855         else
 856           this->_M_do_reset();
 857         return *this;
 858       }
 859       //@}
 860
 861       //@{
 862       /**
 863        *  These versions of single-bit set, reset, flip, and test are
 864        *  extensions from the SGI version.  They do no range checking.
 865        *  @ingroup SGIextensions
 866        */
 867       bitset<_Nb>&
 868       _Unchecked_set(size_t __pos)
 869       {
 870         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 871         return *this;
 872       }
 873
 874       bitset<_Nb>&
 875       _Unchecked_set(size_t __pos, int __val)
 876       {
 877         if (__val)
 878           this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 879         else
 880           this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 881         return *this;
 882       }
 883
 884       bitset<_Nb>&
 885       _Unchecked_reset(size_t __pos)
 886       {
 887         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 888         return *this;
 889       }
 890
 891       bitset<_Nb>&
 892       _Unchecked_flip(size_t __pos)
 893       {
 894         this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
 895         return *this;
 896       }
 897
 898       bool
 899       _Unchecked_test(size_t __pos) const
 900       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
 901                 != static_cast<_WordT>(0)); }
 902       //@}
 903
 904       // Set, reset, and flip.
 905       /**
 906        *  @brief Sets every bit to true.
 907        */
 908       bitset<_Nb>&
 909       set()
 910       {
 911         this->_M_do_set();
 912         this->_M_do_sanitize();
 913         return *this;
 914       }
 915
 916       /**
 917        *  @brief Sets a given bit to a particular value.
 918        *  @param  position  The index of the bit.
 919        *  @param  val  Either true or false, defaults to true.
 920        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
 921        */
 922       bitset<_Nb>&
 923       set(size_t __position, bool __val = true)
 924       {
 925         if (__position >= _Nb)
 926           __throw_out_of_range(__N("bitset::set"));
 927         return _Unchecked_set(__position, __val);
 928       }
 929
 930       /**
 931        *  @brief Sets every bit to false.
 932        */
 933       bitset<_Nb>&
 934       reset()
 935       {
 936         this->_M_do_reset();
 937         return *this;
 938       }
 939
 940       /**
 941        *  @brief Sets a given bit to false.
 942        *  @param  position  The index of the bit.
 943        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
 944        *
 945        *  Same as writing @c set(pos,false).
 946        */
 947       bitset<_Nb>&
 948       reset(size_t __position)
 949       {
 950         if (__position >= _Nb)
 951           __throw_out_of_range(__N("bitset::reset"));
 952         return _Unchecked_reset(__position);
 953       }
 954
 955       /**
 956        *  @brief Toggles every bit to its opposite value.
 957        */
 958       bitset<_Nb>&
 959       flip()
 960       {
 961         this->_M_do_flip();
 962         this->_M_do_sanitize();
 963         return *this;
 964       }
 965
 966       /**
 967        *  @brief Toggles a given bit to its opposite value.
 968        *  @param  position  The index of the bit.
 969        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
 970        */
 971       bitset<_Nb>&
 972       flip(size_t __position)
 973       {
 974         if (__position >= _Nb)
 975           __throw_out_of_range(__N("bitset::flip"));
 976         return _Unchecked_flip(__position);
 977       }
 978
 979       /// See the no-argument flip().
 980       bitset<_Nb>
 981       operator~() const
 982       { return bitset<_Nb>(*this).flip(); }
 983
 984       //@{
 985       /**
 986        *  @brief  Array-indexing support.
 987        *  @param  position  Index into the %bitset.
 988        *  @return  A bool for a 'const %bitset'.  For non-const bitsets, an
 989        *           instance of the reference proxy class.
 990        *  @note  These operators do no range checking and throw no exceptions,
 991        *         as required by DR 11 to the standard.
 992        *
 993        *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
 994        *  resolves DR 11 (items 1 and 2), but does not do the range-checking
 995        *  required by that DR's resolution.  -pme
 996        *  The DR has since been changed:  range-checking is a precondition
 997        *  (users' responsibility), and these functions must not throw.  -pme
 998        */
 999       reference
1000       operator[](size_t __position)
1001       { return reference(*this,__position); }
1002
1003       bool
1004       operator[](size_t __position) const
1005       { return _Unchecked_test(__position); }
1006       //@}
1007
1008       /**
1009        *  @brief Returns a numerical interpretation of the %bitset.
1010        *  @return  The integral equivalent of the bits.
1011        *  @throw  std::overflow_error  If there are too many bits to be
1012        *                               represented in an @c unsigned @c long.
1013        */
1014       unsigned long
1015       to_ulong() const
1016       { return this->_M_do_to_ulong(); }
1017
1018       /**
1019        *  @brief Returns a character interpretation of the %bitset.
1020        *  @return  The string equivalent of the bits.
1021        *
1022        *  Note the ordering of the bits:  decreasing character positions
1023        *  correspond to increasing bit positions (see the main class notes for
1024        *  an example).
1025        */
1026       template<class _CharT, class _Traits, class _Alloc>
1027         std::basic_string<_CharT, _Traits, _Alloc>
1028         to_string() const
1029         {
1030           std::basic_string<_CharT, _Traits, _Alloc> __result;
1031           _M_copy_to_string(__result);
1032           return __result;
1033         }
1034
1035       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1036       // 434. bitset::to_string() hard to use.
1037       template<class _CharT, class _Traits>
1038         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1039         to_string() const
1040         { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
1041
1042       template<class _CharT>
1043         std::basic_string<_CharT, std::char_traits<_CharT>,
1044                           std::allocator<_CharT> >
1045         to_string() const
1046         {
1047           return to_string<_CharT, std::char_traits<_CharT>,
1048                            std::allocator<_CharT> >();
1049         }
1050
1051       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1052       to_string() const
1053       {
1054         return to_string<char, std::char_traits<char>,
1055                          std::allocator<char> >();
1056       }
1057
1058       // Helper functions for string operations.
1059       template<class _CharT>
1060         void
1061         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t);
1062
1063       template<class _CharT, class _Traits, class _Alloc>
1064         void
1065         _M_copy_from_string(const std::basic_string<_CharT,
1066                             _Traits, _Alloc>& __s, size_t __pos, size_t __n)
1067         { _M_copy_from_ptr(__s.data(), __s.size(), __pos, __n); }
1068
1069       template<class _CharT, class _Traits, class _Alloc>
1070         void
1071         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&) const;
1072
1073       /// Returns the number of bits which are set.
1074       size_t
1075       count() const
1076       { return this->_M_do_count(); }
1077
1078       /// Returns the total number of bits.
1079       size_t
1080       size() const
1081       { return _Nb; }
1082
1083       //@{
1084       /// These comparisons for equality/inequality are, well, @e bitwise.
1085       bool
1086       operator==(const bitset<_Nb>& __rhs) const
1087       { return this->_M_is_equal(__rhs); }
1088
1089       bool
1090       operator!=(const bitset<_Nb>& __rhs) const
1091       { return !this->_M_is_equal(__rhs); }
1092       //@}
1093
1094       /**
1095        *  @brief Tests the value of a bit.
1096        *  @param  position  The index of a bit.
1097        *  @return  The value at @a pos.
1098        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1099        */
1100       bool
1101       test(size_t __position) const
1102       {
1103         if (__position >= _Nb)
1104           __throw_out_of_range(__N("bitset::test"));
1105         return _Unchecked_test(__position);
1106       }
1107
1108       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1109       // DR 693. std::bitset::all() missing.
1110       /**
1111        *  @brief Tests whether all the bits are on.
1112        *  @return  True if all the bits are set.
1113        */
1114       bool
1115       all() const
1116       { return this->_M_are_all_aux() == _Nb; }
1117
1118       /**
1119        *  @brief Tests whether any of the bits are on.
1120        *  @return  True if at least one bit is set.
1121        */
1122       bool
1123       any() const
1124       { return this->_M_is_any(); }
1125
1126       /**
1127        *  @brief Tests whether any of the bits are on.
1128        *  @return  True if none of the bits are set.
1129        */
1130       bool
1131       none() const
1132       { return !this->_M_is_any(); }
1133
1134       //@{
1135       /// Self-explanatory.
1136       bitset<_Nb>
1137       operator<<(size_t __position) const
1138       { return bitset<_Nb>(*this) <<= __position; }
1139
1140       bitset<_Nb>
1141       operator>>(size_t __position) const
1142       { return bitset<_Nb>(*this) >>= __position; }
1143       //@}
1144
1145       /**
1146        *  @brief  Finds the index of the first "on" bit.
1147        *  @return  The index of the first bit set, or size() if not found.
1148        *  @ingroup SGIextensions
1149        *  @sa  _Find_next
1150        */
1151       size_t
1152       _Find_first() const
1153       { return this->_M_do_find_first(_Nb); }
1154
1155       /**
1156        *  @brief  Finds the index of the next "on" bit after prev.
1157        *  @return  The index of the next bit set, or size() if not found.
1158        *  @param  prev  Where to start searching.
1159        *  @ingroup SGIextensions
1160        *  @sa  _Find_first
1161        */
1162       size_t
1163       _Find_next(size_t __prev ) const
1164       { return this->_M_do_find_next(__prev, _Nb); }
1165     };
1166
1167   // Definitions of non-inline member functions.
1168   template<size_t _Nb>
1169     template<class _CharT>
1170       void
1171       bitset<_Nb>::
1172       _M_copy_from_ptr(const _CharT* __s, size_t __len,
1173                        size_t __pos, size_t __n)
1174       {
1175         reset();
1176         const size_t __nbits = std::min(_Nb, std::min(__n, __len - __pos));
1177         for (size_t __i = __nbits; __i > 0; --__i)
1178           {
1179             switch(__s[__pos + __nbits - __i])
1180               {
1181               case '0':
1182                 break;
1183               case '1':
1184                 _Unchecked_set(__i - 1);
1185                 break;
1186               default:
1187                 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
1188               }
1189           }
1190       }
1191
1192   template<size_t _Nb>
1193     template<class _CharT, class _Traits, class _Alloc>
1194       void
1195       bitset<_Nb>::
1196       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s) const
1197       {
1198         __s.assign(_Nb, '0');
1199         for (size_t __i = _Nb; __i > 0; --__i)
1200           if (_Unchecked_test(__i - 1))
1201             __s[_Nb - __i] = '1';
1202       }
1203
1204   // 23.3.5.3 bitset operations:
1205   //@{
1206   /**
1207    *  @brief  Global bitwise operations on bitsets.
1208    *  @param  x  A bitset.
1209    *  @param  y  A bitset of the same size as @a x.
1210    *  @return  A new bitset.
1211    *
1212    *  These should be self-explanatory.
1213   */
1214   template<size_t _Nb>
1215     inline bitset<_Nb>
1216     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1217     {
1218       bitset<_Nb> __result(__x);
1219       __result &= __y;
1220       return __result;
1221     }
1222
1223   template<size_t _Nb>
1224     inline bitset<_Nb>
1225     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1226     {
1227       bitset<_Nb> __result(__x);
1228       __result |= __y;
1229       return __result;
1230     }
1231
1232   template <size_t _Nb>
1233     inline bitset<_Nb>
1234     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1235     {
1236       bitset<_Nb> __result(__x);
1237       __result ^= __y;
1238       return __result;
1239     }
1240   //@}
1241
1242   //@{
1243   /**
1244    *  @brief Global I/O operators for bitsets.
1245    *
1246    *  Direct I/O between streams and bitsets is supported.  Output is
1247    *  straightforward.  Input will skip whitespace, only accept '0' and '1'
1248    *  characters, and will only extract as many digits as the %bitset will
1249    *  hold.
1250   */
1251   template<class _CharT, class _Traits, size_t _Nb>
1252     std::basic_istream<_CharT, _Traits>&
1253     operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
1254     {
1255       typedef typename _Traits::char_type          char_type;
1256       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
1257       typedef typename __istream_type::ios_base    __ios_base;
1258
1259       std::basic_string<_CharT, _Traits> __tmp;
1260       __tmp.reserve(_Nb);
1261
1262       typename __ios_base::iostate __state = __ios_base::goodbit;
1263       typename __istream_type::sentry __sentry(__is);
1264       if (__sentry)
1265         {
1266           try
1267             {
1268               // _GLIBCXX_RESOLVE_LIB_DEFECTS
1269               // 303. Bitset input operator underspecified
1270               const char_type __zero = __is.widen('0');
1271               const char_type __one = __is.widen('1');
1272               for (size_t __i = _Nb; __i > 0; --__i)
1273                 {
1274                   static typename _Traits::int_type __eof = _Traits::eof();
1275
1276                   typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
1277                   if (_Traits::eq_int_type(__c1, __eof))
1278                     {
1279                       __state |= __ios_base::eofbit;
1280                       break;
1281                     }
1282                   else
1283                     {
1284                       const char_type __c2 = _Traits::to_char_type(__c1);
1285                       if (__c2 == __zero)
1286                         __tmp.push_back('0');
1287                       else if (__c2 == __one)
1288                         __tmp.push_back('1');
1289                       else if (_Traits::
1290                                eq_int_type(__is.rdbuf()->sputbackc(__c2),
1291                                            __eof))
1292                         {
1293                           __state |= __ios_base::failbit;
1294                           break;
1295                         }
1296                     }
1297                 }
1298             }
1299           catch(__cxxabiv1::__forced_unwind&)
1300             {
1301               __is._M_setstate(__ios_base::badbit);
1302               __throw_exception_again;
1303             }
1304           catch(...)
1305             { __is._M_setstate(__ios_base::badbit); }
1306         }
1307
1308       if (__tmp.empty() && _Nb)
1309         __state |= __ios_base::failbit;
1310       else
1311         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb);
1312       if (__state)
1313         __is.setstate(__state);
1314       return __is;
1315     }
1316
1317   template <class _CharT, class _Traits, size_t _Nb>
1318     std::basic_ostream<_CharT, _Traits>&
1319     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1320                const bitset<_Nb>& __x)
1321     {
1322       std::basic_string<_CharT, _Traits> __tmp;
1323       __x._M_copy_to_string(__tmp);
1324       return __os << __tmp;
1325     }
1326   //@}
1327
1328 _GLIBCXX_END_NESTED_NAMESPACE
1329
1330 #undef _GLIBCXX_BITSET_WORDS
1331 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1332
1333 #ifdef _GLIBCXX_DEBUG
1334 # include <debug/bitset>
1335 #endif
1336
1337 #endif /* _GLIBCXX_BITSET */