OSDN Git Service

2011-12-10 Benjamin Kosnik <bkoz@redhat.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / std / bitset
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
62 namespace 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, __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
1547 namespace 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 */