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