libstdc++
|
00001 // <bitset> -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 00004 // 2011 00005 // Free Software Foundation, Inc. 00006 // 00007 // This file is part of the GNU ISO C++ Library. This library is free 00008 // software; you can redistribute it and/or modify it under the 00009 // terms of the GNU General Public License as published by the 00010 // Free Software Foundation; either version 3, or (at your option) 00011 // any later version. 00012 00013 // This library is distributed in the hope that it will be useful, 00014 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00016 // GNU General Public License for more details. 00017 00018 // Under Section 7 of GPL version 3, you are granted additional 00019 // permissions described in the GCC Runtime Library Exception, version 00020 // 3.1, as published by the Free Software Foundation. 00021 00022 // You should have received a copy of the GNU General Public License and 00023 // a copy of the GCC Runtime Library Exception along with this program; 00024 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00025 // <http://www.gnu.org/licenses/>. 00026 00027 /* 00028 * Copyright (c) 1998 00029 * Silicon Graphics Computer Systems, Inc. 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Silicon Graphics makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 */ 00039 00040 /** @file include/bitset 00041 * This is a Standard C++ Library header. 00042 */ 00043 00044 #ifndef _GLIBCXX_BITSET 00045 #define _GLIBCXX_BITSET 1 00046 00047 #pragma GCC system_header 00048 00049 #include <string> 00050 #include <bits/functexcept.h> // For invalid_argument, out_of_range, 00051 // overflow_error 00052 #include <iosfwd> 00053 #include <bits/cxxabi_forced.h> 00054 00055 #define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * __SIZEOF_LONG__) 00056 #define _GLIBCXX_BITSET_WORDS(__n) \ 00057 ((__n) / _GLIBCXX_BITSET_BITS_PER_WORD + \ 00058 ((__n) % _GLIBCXX_BITSET_BITS_PER_WORD == 0 ? 0 : 1)) 00059 00060 #define _GLIBCXX_BITSET_BITS_PER_ULL (__CHAR_BIT__ * __SIZEOF_LONG_LONG__) 00061 00062 namespace std _GLIBCXX_VISIBILITY(default) 00063 { 00064 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00065 00066 /** 00067 * Base class, general case. It is a class invariant that _Nw will be 00068 * nonnegative. 00069 * 00070 * See documentation for bitset. 00071 */ 00072 template<size_t _Nw> 00073 struct _Base_bitset 00074 { 00075 typedef unsigned long _WordT; 00076 00077 /// 0 is the least significant word. 00078 _WordT _M_w[_Nw]; 00079 00080 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT 00081 : _M_w() { } 00082 00083 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00084 constexpr _Base_bitset(unsigned long long __val) noexcept 00085 : _M_w{ _WordT(__val) 00086 #if __SIZEOF_LONG_LONG__ > __SIZEOF_LONG__ 00087 , _WordT(__val >> _GLIBCXX_BITSET_BITS_PER_WORD) 00088 #endif 00089 } { } 00090 #else 00091 _Base_bitset(unsigned long __val) 00092 : _M_w() 00093 { _M_w[0] = __val; } 00094 #endif 00095 00096 static _GLIBCXX_CONSTEXPR size_t 00097 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT 00098 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 00099 00100 static _GLIBCXX_CONSTEXPR size_t 00101 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT 00102 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 00103 00104 static _GLIBCXX_CONSTEXPR size_t 00105 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT 00106 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 00107 00108 static _GLIBCXX_CONSTEXPR _WordT 00109 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT 00110 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00111 00112 _WordT& 00113 _M_getword(size_t __pos) _GLIBCXX_NOEXCEPT 00114 { return _M_w[_S_whichword(__pos)]; } 00115 00116 _GLIBCXX_CONSTEXPR _WordT 00117 _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT 00118 { return _M_w[_S_whichword(__pos)]; } 00119 00120 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00121 const _WordT* 00122 _M_getdata() const noexcept 00123 { return _M_w; } 00124 #endif 00125 00126 _WordT& 00127 _M_hiword() _GLIBCXX_NOEXCEPT 00128 { return _M_w[_Nw - 1]; } 00129 00130 _GLIBCXX_CONSTEXPR _WordT 00131 _M_hiword() const _GLIBCXX_NOEXCEPT 00132 { return _M_w[_Nw - 1]; } 00133 00134 void 00135 _M_do_and(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT 00136 { 00137 for (size_t __i = 0; __i < _Nw; __i++) 00138 _M_w[__i] &= __x._M_w[__i]; 00139 } 00140 00141 void 00142 _M_do_or(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT 00143 { 00144 for (size_t __i = 0; __i < _Nw; __i++) 00145 _M_w[__i] |= __x._M_w[__i]; 00146 } 00147 00148 void 00149 _M_do_xor(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT 00150 { 00151 for (size_t __i = 0; __i < _Nw; __i++) 00152 _M_w[__i] ^= __x._M_w[__i]; 00153 } 00154 00155 void 00156 _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT; 00157 00158 void 00159 _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT; 00160 00161 void 00162 _M_do_flip() _GLIBCXX_NOEXCEPT 00163 { 00164 for (size_t __i = 0; __i < _Nw; __i++) 00165 _M_w[__i] = ~_M_w[__i]; 00166 } 00167 00168 void 00169 _M_do_set() _GLIBCXX_NOEXCEPT 00170 { 00171 for (size_t __i = 0; __i < _Nw; __i++) 00172 _M_w[__i] = ~static_cast<_WordT>(0); 00173 } 00174 00175 void 00176 _M_do_reset() _GLIBCXX_NOEXCEPT 00177 { __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT)); } 00178 00179 bool 00180 _M_is_equal(const _Base_bitset<_Nw>& __x) const _GLIBCXX_NOEXCEPT 00181 { 00182 for (size_t __i = 0; __i < _Nw; ++__i) 00183 if (_M_w[__i] != __x._M_w[__i]) 00184 return false; 00185 return true; 00186 } 00187 00188 template<size_t _Nb> 00189 bool 00190 _M_are_all() const _GLIBCXX_NOEXCEPT 00191 { 00192 for (size_t __i = 0; __i < _Nw - 1; __i++) 00193 if (_M_w[__i] != ~static_cast<_WordT>(0)) 00194 return false; 00195 return _M_hiword() == (~static_cast<_WordT>(0) 00196 >> (_Nw * _GLIBCXX_BITSET_BITS_PER_WORD 00197 - _Nb)); 00198 } 00199 00200 bool 00201 _M_is_any() const _GLIBCXX_NOEXCEPT 00202 { 00203 for (size_t __i = 0; __i < _Nw; __i++) 00204 if (_M_w[__i] != static_cast<_WordT>(0)) 00205 return true; 00206 return false; 00207 } 00208 00209 size_t 00210 _M_do_count() const _GLIBCXX_NOEXCEPT 00211 { 00212 size_t __result = 0; 00213 for (size_t __i = 0; __i < _Nw; __i++) 00214 __result += __builtin_popcountl(_M_w[__i]); 00215 return __result; 00216 } 00217 00218 unsigned long 00219 _M_do_to_ulong() const; 00220 00221 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00222 unsigned long long 00223 _M_do_to_ullong() const; 00224 #endif 00225 00226 // find first "on" bit 00227 size_t 00228 _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT; 00229 00230 // find the next "on" bit that follows "prev" 00231 size_t 00232 _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT; 00233 }; 00234 00235 // Definitions of non-inline functions from _Base_bitset. 00236 template<size_t _Nw> 00237 void 00238 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT 00239 { 00240 if (__builtin_expect(__shift != 0, 1)) 00241 { 00242 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 00243 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 00244 00245 if (__offset == 0) 00246 for (size_t __n = _Nw - 1; __n >= __wshift; --__n) 00247 _M_w[__n] = _M_w[__n - __wshift]; 00248 else 00249 { 00250 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 00251 - __offset); 00252 for (size_t __n = _Nw - 1; __n > __wshift; --__n) 00253 _M_w[__n] = ((_M_w[__n - __wshift] << __offset) 00254 | (_M_w[__n - __wshift - 1] >> __sub_offset)); 00255 _M_w[__wshift] = _M_w[0] << __offset; 00256 } 00257 00258 std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); 00259 } 00260 } 00261 00262 template<size_t _Nw> 00263 void 00264 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT 00265 { 00266 if (__builtin_expect(__shift != 0, 1)) 00267 { 00268 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 00269 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 00270 const size_t __limit = _Nw - __wshift - 1; 00271 00272 if (__offset == 0) 00273 for (size_t __n = 0; __n <= __limit; ++__n) 00274 _M_w[__n] = _M_w[__n + __wshift]; 00275 else 00276 { 00277 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 00278 - __offset); 00279 for (size_t __n = 0; __n < __limit; ++__n) 00280 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset) 00281 | (_M_w[__n + __wshift + 1] << __sub_offset)); 00282 _M_w[__limit] = _M_w[_Nw-1] >> __offset; 00283 } 00284 00285 std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); 00286 } 00287 } 00288 00289 template<size_t _Nw> 00290 unsigned long 00291 _Base_bitset<_Nw>::_M_do_to_ulong() const 00292 { 00293 for (size_t __i = 1; __i < _Nw; ++__i) 00294 if (_M_w[__i]) 00295 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong")); 00296 return _M_w[0]; 00297 } 00298 00299 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00300 template<size_t _Nw> 00301 unsigned long long 00302 _Base_bitset<_Nw>::_M_do_to_ullong() const 00303 { 00304 const bool __dw = sizeof(unsigned long long) > sizeof(unsigned long); 00305 for (size_t __i = 1 + __dw; __i < _Nw; ++__i) 00306 if (_M_w[__i]) 00307 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong")); 00308 00309 if (__dw) 00310 return _M_w[0] + (static_cast<unsigned long long>(_M_w[1]) 00311 << _GLIBCXX_BITSET_BITS_PER_WORD); 00312 return _M_w[0]; 00313 } 00314 #endif 00315 00316 template<size_t _Nw> 00317 size_t 00318 _Base_bitset<_Nw>:: 00319 _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT 00320 { 00321 for (size_t __i = 0; __i < _Nw; __i++) 00322 { 00323 _WordT __thisword = _M_w[__i]; 00324 if (__thisword != static_cast<_WordT>(0)) 00325 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 00326 + __builtin_ctzl(__thisword)); 00327 } 00328 // not found, so return an indication of failure. 00329 return __not_found; 00330 } 00331 00332 template<size_t _Nw> 00333 size_t 00334 _Base_bitset<_Nw>:: 00335 _M_do_find_next(size_t __prev, size_t __not_found) const _GLIBCXX_NOEXCEPT 00336 { 00337 // make bound inclusive 00338 ++__prev; 00339 00340 // check out of bounds 00341 if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD) 00342 return __not_found; 00343 00344 // search first word 00345 size_t __i = _S_whichword(__prev); 00346 _WordT __thisword = _M_w[__i]; 00347 00348 // mask off bits below bound 00349 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 00350 00351 if (__thisword != static_cast<_WordT>(0)) 00352 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 00353 + __builtin_ctzl(__thisword)); 00354 00355 // check subsequent words 00356 __i++; 00357 for (; __i < _Nw; __i++) 00358 { 00359 __thisword = _M_w[__i]; 00360 if (__thisword != static_cast<_WordT>(0)) 00361 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 00362 + __builtin_ctzl(__thisword)); 00363 } 00364 // not found, so return an indication of failure. 00365 return __not_found; 00366 } // end _M_do_find_next 00367 00368 /** 00369 * Base class, specialization for a single word. 00370 * 00371 * See documentation for bitset. 00372 */ 00373 template<> 00374 struct _Base_bitset<1> 00375 { 00376 typedef unsigned long _WordT; 00377 _WordT _M_w; 00378 00379 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT 00380 : _M_w(0) 00381 { } 00382 00383 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00384 constexpr _Base_bitset(unsigned long long __val) noexcept 00385 #else 00386 _Base_bitset(unsigned long __val) 00387 #endif 00388 : _M_w(__val) 00389 { } 00390 00391 static _GLIBCXX_CONSTEXPR size_t 00392 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT 00393 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 00394 00395 static _GLIBCXX_CONSTEXPR size_t 00396 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT 00397 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 00398 00399 static _GLIBCXX_CONSTEXPR size_t 00400 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT 00401 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 00402 00403 static _GLIBCXX_CONSTEXPR _WordT 00404 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT 00405 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00406 00407 _WordT& 00408 _M_getword(size_t) _GLIBCXX_NOEXCEPT 00409 { return _M_w; } 00410 00411 _GLIBCXX_CONSTEXPR _WordT 00412 _M_getword(size_t) const _GLIBCXX_NOEXCEPT 00413 { return _M_w; } 00414 00415 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00416 const _WordT* 00417 _M_getdata() const noexcept 00418 { return &_M_w; } 00419 #endif 00420 00421 _WordT& 00422 _M_hiword() _GLIBCXX_NOEXCEPT 00423 { return _M_w; } 00424 00425 _GLIBCXX_CONSTEXPR _WordT 00426 _M_hiword() const _GLIBCXX_NOEXCEPT 00427 { return _M_w; } 00428 00429 void 00430 _M_do_and(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT 00431 { _M_w &= __x._M_w; } 00432 00433 void 00434 _M_do_or(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT 00435 { _M_w |= __x._M_w; } 00436 00437 void 00438 _M_do_xor(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT 00439 { _M_w ^= __x._M_w; } 00440 00441 void 00442 _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT 00443 { _M_w <<= __shift; } 00444 00445 void 00446 _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT 00447 { _M_w >>= __shift; } 00448 00449 void 00450 _M_do_flip() _GLIBCXX_NOEXCEPT 00451 { _M_w = ~_M_w; } 00452 00453 void 00454 _M_do_set() _GLIBCXX_NOEXCEPT 00455 { _M_w = ~static_cast<_WordT>(0); } 00456 00457 void 00458 _M_do_reset() _GLIBCXX_NOEXCEPT 00459 { _M_w = 0; } 00460 00461 bool 00462 _M_is_equal(const _Base_bitset<1>& __x) const _GLIBCXX_NOEXCEPT 00463 { return _M_w == __x._M_w; } 00464 00465 template<size_t _Nb> 00466 bool 00467 _M_are_all() const _GLIBCXX_NOEXCEPT 00468 { return _M_w == (~static_cast<_WordT>(0) 00469 >> (_GLIBCXX_BITSET_BITS_PER_WORD - _Nb)); } 00470 00471 bool 00472 _M_is_any() const _GLIBCXX_NOEXCEPT 00473 { return _M_w != 0; } 00474 00475 size_t 00476 _M_do_count() const _GLIBCXX_NOEXCEPT 00477 { return __builtin_popcountl(_M_w); } 00478 00479 unsigned long 00480 _M_do_to_ulong() const _GLIBCXX_NOEXCEPT 00481 { return _M_w; } 00482 00483 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00484 unsigned long long 00485 _M_do_to_ullong() const noexcept 00486 { return _M_w; } 00487 #endif 00488 00489 size_t 00490 _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT 00491 { 00492 if (_M_w != 0) 00493 return __builtin_ctzl(_M_w); 00494 else 00495 return __not_found; 00496 } 00497 00498 // find the next "on" bit that follows "prev" 00499 size_t 00500 _M_do_find_next(size_t __prev, size_t __not_found) const 00501 _GLIBCXX_NOEXCEPT 00502 { 00503 ++__prev; 00504 if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD)) 00505 return __not_found; 00506 00507 _WordT __x = _M_w >> __prev; 00508 if (__x != 0) 00509 return __builtin_ctzl(__x) + __prev; 00510 else 00511 return __not_found; 00512 } 00513 }; 00514 00515 /** 00516 * Base class, specialization for no storage (zero-length %bitset). 00517 * 00518 * See documentation for bitset. 00519 */ 00520 template<> 00521 struct _Base_bitset<0> 00522 { 00523 typedef unsigned long _WordT; 00524 00525 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT 00526 { } 00527 00528 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00529 constexpr _Base_bitset(unsigned long long) noexcept 00530 #else 00531 _Base_bitset(unsigned long) 00532 #endif 00533 { } 00534 00535 static _GLIBCXX_CONSTEXPR size_t 00536 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT 00537 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 00538 00539 static _GLIBCXX_CONSTEXPR size_t 00540 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT 00541 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 00542 00543 static _GLIBCXX_CONSTEXPR size_t 00544 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT 00545 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 00546 00547 static _GLIBCXX_CONSTEXPR _WordT 00548 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT 00549 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00550 00551 // This would normally give access to the data. The bounds-checking 00552 // in the bitset class will prevent the user from getting this far, 00553 // but (1) it must still return an lvalue to compile, and (2) the 00554 // user might call _Unchecked_set directly, in which case this /needs/ 00555 // to fail. Let's not penalize zero-length users unless they actually 00556 // make an unchecked call; all the memory ugliness is therefore 00557 // localized to this single should-never-get-this-far function. 00558 _WordT& 00559 _M_getword(size_t) _GLIBCXX_NOEXCEPT 00560 { 00561 __throw_out_of_range(__N("_Base_bitset::_M_getword")); 00562 return *new _WordT; 00563 } 00564 00565 _GLIBCXX_CONSTEXPR _WordT 00566 _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT 00567 { return 0; } 00568 00569 _GLIBCXX_CONSTEXPR _WordT 00570 _M_hiword() const _GLIBCXX_NOEXCEPT 00571 { return 0; } 00572 00573 void 00574 _M_do_and(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT 00575 { } 00576 00577 void 00578 _M_do_or(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT 00579 { } 00580 00581 void 00582 _M_do_xor(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT 00583 { } 00584 00585 void 00586 _M_do_left_shift(size_t) _GLIBCXX_NOEXCEPT 00587 { } 00588 00589 void 00590 _M_do_right_shift(size_t) _GLIBCXX_NOEXCEPT 00591 { } 00592 00593 void 00594 _M_do_flip() _GLIBCXX_NOEXCEPT 00595 { } 00596 00597 void 00598 _M_do_set() _GLIBCXX_NOEXCEPT 00599 { } 00600 00601 void 00602 _M_do_reset() _GLIBCXX_NOEXCEPT 00603 { } 00604 00605 // Are all empty bitsets equal to each other? Are they equal to 00606 // themselves? How to compare a thing which has no state? What is 00607 // the sound of one zero-length bitset clapping? 00608 bool 00609 _M_is_equal(const _Base_bitset<0>&) const _GLIBCXX_NOEXCEPT 00610 { return true; } 00611 00612 template<size_t _Nb> 00613 bool 00614 _M_are_all() const _GLIBCXX_NOEXCEPT 00615 { return true; } 00616 00617 bool 00618 _M_is_any() const _GLIBCXX_NOEXCEPT 00619 { return false; } 00620 00621 size_t 00622 _M_do_count() const _GLIBCXX_NOEXCEPT 00623 { return 0; } 00624 00625 unsigned long 00626 _M_do_to_ulong() const _GLIBCXX_NOEXCEPT 00627 { return 0; } 00628 00629 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00630 unsigned long long 00631 _M_do_to_ullong() const noexcept 00632 { return 0; } 00633 #endif 00634 00635 // Normally "not found" is the size, but that could also be 00636 // misinterpreted as an index in this corner case. Oh well. 00637 size_t 00638 _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT 00639 { return 0; } 00640 00641 size_t 00642 _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT 00643 { return 0; } 00644 }; 00645 00646 00647 // Helper class to zero out the unused high-order bits in the highest word. 00648 template<size_t _Extrabits> 00649 struct _Sanitize 00650 { 00651 typedef unsigned long _WordT; 00652 00653 static void 00654 _S_do_sanitize(_WordT& __val) _GLIBCXX_NOEXCEPT 00655 { __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); } 00656 }; 00657 00658 template<> 00659 struct _Sanitize<0> 00660 { 00661 typedef unsigned long _WordT; 00662 00663 static void 00664 _S_do_sanitize(_WordT) _GLIBCXX_NOEXCEPT { } 00665 }; 00666 00667 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00668 template<size_t _Nb, bool = _Nb < _GLIBCXX_BITSET_BITS_PER_ULL> 00669 struct _Sanitize_val 00670 { 00671 static constexpr unsigned long long 00672 _S_do_sanitize_val(unsigned long long __val) 00673 { return __val; } 00674 }; 00675 00676 template<size_t _Nb> 00677 struct _Sanitize_val<_Nb, true> 00678 { 00679 static constexpr unsigned long long 00680 _S_do_sanitize_val(unsigned long long __val) 00681 { return __val & ~((~static_cast<unsigned long long>(0)) << _Nb); } 00682 }; 00683 #endif 00684 00685 /** 00686 * The %bitset class represents a @e fixed-size sequence of bits. 00687 * 00688 * @ingroup containers 00689 * 00690 * (Note that %bitset does @e not meet the formal requirements of a 00691 * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 00692 * 00693 * The template argument, @a Nb, may be any non-negative number, 00694 * specifying the number of bits (e.g., "0", "12", "1024*1024"). 00695 * 00696 * In the general unoptimized case, storage is allocated in word-sized 00697 * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B 00698 * words will be used for storage. B - Nb%B bits are unused. (They are 00699 * the high-order bits in the highest word.) It is a class invariant 00700 * that those unused bits are always zero. 00701 * 00702 * If you think of %bitset as <em>a simple array of bits</em>, be 00703 * aware that your mental picture is reversed: a %bitset behaves 00704 * the same way as bits in integers do, with the bit at index 0 in 00705 * the <em>least significant / right-hand</em> position, and the bit at 00706 * index Nb-1 in the <em>most significant / left-hand</em> position. 00707 * Thus, unlike other containers, a %bitset's index <em>counts from 00708 * right to left</em>, to put it very loosely. 00709 * 00710 * This behavior is preserved when translating to and from strings. For 00711 * example, the first line of the following program probably prints 00712 * <em>b('a') is 0001100001</em> on a modern ASCII system. 00713 * 00714 * @code 00715 * #include <bitset> 00716 * #include <iostream> 00717 * #include <sstream> 00718 * 00719 * using namespace std; 00720 * 00721 * int main() 00722 * { 00723 * long a = 'a'; 00724 * bitset<10> b(a); 00725 * 00726 * cout << "b('a') is " << b << endl; 00727 * 00728 * ostringstream s; 00729 * s << b; 00730 * string str = s.str(); 00731 * cout << "index 3 in the string is " << str[3] << " but\n" 00732 * << "index 3 in the bitset is " << b[3] << endl; 00733 * } 00734 * @endcode 00735 * 00736 * Also see: 00737 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html 00738 * for a description of extensions. 00739 * 00740 * Most of the actual code isn't contained in %bitset<> itself, but in the 00741 * base class _Base_bitset. The base class works with whole words, not with 00742 * individual bits. This allows us to specialize _Base_bitset for the 00743 * important special case where the %bitset is only a single word. 00744 * 00745 * Extra confusion can result due to the fact that the storage for 00746 * _Base_bitset @e is a regular array, and is indexed as such. This is 00747 * carefully encapsulated. 00748 */ 00749 template<size_t _Nb> 00750 class bitset 00751 : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> 00752 { 00753 private: 00754 typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base; 00755 typedef unsigned long _WordT; 00756 00757 void 00758 _M_do_sanitize() _GLIBCXX_NOEXCEPT 00759 { 00760 typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type; 00761 __sanitize_type::_S_do_sanitize(this->_M_hiword()); 00762 } 00763 00764 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00765 template<typename> friend class hash; 00766 #endif 00767 00768 public: 00769 /** 00770 * This encapsulates the concept of a single bit. An instance of this 00771 * class is a proxy for an actual bit; this way the individual bit 00772 * operations are done as faster word-size bitwise instructions. 00773 * 00774 * Most users will never need to use this class directly; conversions 00775 * to and from bool are automatic and should be transparent. Overloaded 00776 * operators help to preserve the illusion. 00777 * 00778 * (On a typical system, this <em>bit %reference</em> is 64 00779 * times the size of an actual bit. Ha.) 00780 */ 00781 class reference 00782 { 00783 friend class bitset; 00784 00785 _WordT* _M_wp; 00786 size_t _M_bpos; 00787 00788 // left undefined 00789 reference(); 00790 00791 public: 00792 reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT 00793 { 00794 _M_wp = &__b._M_getword(__pos); 00795 _M_bpos = _Base::_S_whichbit(__pos); 00796 } 00797 00798 ~reference() _GLIBCXX_NOEXCEPT 00799 { } 00800 00801 // For b[i] = __x; 00802 reference& 00803 operator=(bool __x) _GLIBCXX_NOEXCEPT 00804 { 00805 if (__x) 00806 *_M_wp |= _Base::_S_maskbit(_M_bpos); 00807 else 00808 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 00809 return *this; 00810 } 00811 00812 // For b[i] = b[__j]; 00813 reference& 00814 operator=(const reference& __j) _GLIBCXX_NOEXCEPT 00815 { 00816 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 00817 *_M_wp |= _Base::_S_maskbit(_M_bpos); 00818 else 00819 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 00820 return *this; 00821 } 00822 00823 // Flips the bit 00824 bool 00825 operator~() const _GLIBCXX_NOEXCEPT 00826 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 00827 00828 // For __x = b[i]; 00829 operator bool() const _GLIBCXX_NOEXCEPT 00830 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 00831 00832 // For b[i].flip(); 00833 reference& 00834 flip() _GLIBCXX_NOEXCEPT 00835 { 00836 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 00837 return *this; 00838 } 00839 }; 00840 friend class reference; 00841 00842 // 23.3.5.1 constructors: 00843 /// All bits set to zero. 00844 _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT 00845 { } 00846 00847 /// Initial bits bitwise-copied from a single word (others set to zero). 00848 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00849 constexpr bitset(unsigned long long __val) noexcept 00850 : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { } 00851 #else 00852 bitset(unsigned long __val) 00853 : _Base(__val) 00854 { _M_do_sanitize(); } 00855 #endif 00856 00857 /** 00858 * Use a subset of a string. 00859 * @param __s A string of @a 0 and @a 1 characters. 00860 * @param __position Index of the first character in @a __s to use; 00861 * defaults to zero. 00862 * @throw std::out_of_range If @a pos is bigger the size of @a __s. 00863 * @throw std::invalid_argument If a character appears in the string 00864 * which is neither @a 0 nor @a 1. 00865 */ 00866 template<class _CharT, class _Traits, class _Alloc> 00867 explicit 00868 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 00869 size_t __position = 0) 00870 : _Base() 00871 { 00872 if (__position > __s.size()) 00873 __throw_out_of_range(__N("bitset::bitset initial position " 00874 "not valid")); 00875 _M_copy_from_string(__s, __position, 00876 std::basic_string<_CharT, _Traits, _Alloc>::npos, 00877 _CharT('0'), _CharT('1')); 00878 } 00879 00880 /** 00881 * Use a subset of a string. 00882 * @param __s A string of @a 0 and @a 1 characters. 00883 * @param __position Index of the first character in @a __s to use. 00884 * @param __n The number of characters to copy. 00885 * @throw std::out_of_range If @a __position is bigger the size 00886 * of @a __s. 00887 * @throw std::invalid_argument If a character appears in the string 00888 * which is neither @a 0 nor @a 1. 00889 */ 00890 template<class _CharT, class _Traits, class _Alloc> 00891 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 00892 size_t __position, size_t __n) 00893 : _Base() 00894 { 00895 if (__position > __s.size()) 00896 __throw_out_of_range(__N("bitset::bitset initial position " 00897 "not valid")); 00898 _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1')); 00899 } 00900 00901 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00902 // 396. what are characters zero and one. 00903 template<class _CharT, class _Traits, class _Alloc> 00904 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 00905 size_t __position, size_t __n, 00906 _CharT __zero, _CharT __one = _CharT('1')) 00907 : _Base() 00908 { 00909 if (__position > __s.size()) 00910 __throw_out_of_range(__N("bitset::bitset initial position " 00911 "not valid")); 00912 _M_copy_from_string(__s, __position, __n, __zero, __one); 00913 } 00914 00915 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00916 /** 00917 * Construct from a character %array. 00918 * @param __str An %array of characters @a zero and @a one. 00919 * @param __n The number of characters to use. 00920 * @param __zero The character corresponding to the value 0. 00921 * @param __one The character corresponding to the value 1. 00922 * @throw std::invalid_argument If a character appears in the string 00923 * which is neither @a __zero nor @a __one. 00924 */ 00925 template<typename _CharT> 00926 explicit 00927 bitset(const _CharT* __str, 00928 typename std::basic_string<_CharT>::size_type __n 00929 = std::basic_string<_CharT>::npos, 00930 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) 00931 : _Base() 00932 { 00933 if (!__str) 00934 __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)")); 00935 00936 if (__n == std::basic_string<_CharT>::npos) 00937 __n = std::char_traits<_CharT>::length(__str); 00938 _M_copy_from_ptr<_CharT, std::char_traits<_CharT>>(__str, __n, 0, 00939 __n, __zero, 00940 __one); 00941 } 00942 #endif 00943 00944 // 23.3.5.2 bitset operations: 00945 //@{ 00946 /** 00947 * Operations on bitsets. 00948 * @param __rhs A same-sized bitset. 00949 * 00950 * These should be self-explanatory. 00951 */ 00952 bitset<_Nb>& 00953 operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 00954 { 00955 this->_M_do_and(__rhs); 00956 return *this; 00957 } 00958 00959 bitset<_Nb>& 00960 operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 00961 { 00962 this->_M_do_or(__rhs); 00963 return *this; 00964 } 00965 00966 bitset<_Nb>& 00967 operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 00968 { 00969 this->_M_do_xor(__rhs); 00970 return *this; 00971 } 00972 //@} 00973 00974 //@{ 00975 /** 00976 * Operations on bitsets. 00977 * @param __position The number of places to shift. 00978 * 00979 * These should be self-explanatory. 00980 */ 00981 bitset<_Nb>& 00982 operator<<=(size_t __position) _GLIBCXX_NOEXCEPT 00983 { 00984 if (__builtin_expect(__position < _Nb, 1)) 00985 { 00986 this->_M_do_left_shift(__position); 00987 this->_M_do_sanitize(); 00988 } 00989 else 00990 this->_M_do_reset(); 00991 return *this; 00992 } 00993 00994 bitset<_Nb>& 00995 operator>>=(size_t __position) _GLIBCXX_NOEXCEPT 00996 { 00997 if (__builtin_expect(__position < _Nb, 1)) 00998 { 00999 this->_M_do_right_shift(__position); 01000 this->_M_do_sanitize(); 01001 } 01002 else 01003 this->_M_do_reset(); 01004 return *this; 01005 } 01006 //@} 01007 01008 //@{ 01009 /** 01010 * These versions of single-bit set, reset, flip, and test are 01011 * extensions from the SGI version. They do no range checking. 01012 * @ingroup SGIextensions 01013 */ 01014 bitset<_Nb>& 01015 _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT 01016 { 01017 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 01018 return *this; 01019 } 01020 01021 bitset<_Nb>& 01022 _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT 01023 { 01024 if (__val) 01025 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 01026 else 01027 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 01028 return *this; 01029 } 01030 01031 bitset<_Nb>& 01032 _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT 01033 { 01034 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 01035 return *this; 01036 } 01037 01038 bitset<_Nb>& 01039 _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT 01040 { 01041 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 01042 return *this; 01043 } 01044 01045 _GLIBCXX_CONSTEXPR bool 01046 _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT 01047 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 01048 != static_cast<_WordT>(0)); } 01049 //@} 01050 01051 // Set, reset, and flip. 01052 /** 01053 * @brief Sets every bit to true. 01054 */ 01055 bitset<_Nb>& 01056 set() _GLIBCXX_NOEXCEPT 01057 { 01058 this->_M_do_set(); 01059 this->_M_do_sanitize(); 01060 return *this; 01061 } 01062 01063 /** 01064 * @brief Sets a given bit to a particular value. 01065 * @param __position The index of the bit. 01066 * @param __val Either true or false, defaults to true. 01067 * @throw std::out_of_range If @a pos is bigger the size of the %set. 01068 */ 01069 bitset<_Nb>& 01070 set(size_t __position, bool __val = true) 01071 { 01072 if (__position >= _Nb) 01073 __throw_out_of_range(__N("bitset::set")); 01074 return _Unchecked_set(__position, __val); 01075 } 01076 01077 /** 01078 * @brief Sets every bit to false. 01079 */ 01080 bitset<_Nb>& 01081 reset() _GLIBCXX_NOEXCEPT 01082 { 01083 this->_M_do_reset(); 01084 return *this; 01085 } 01086 01087 /** 01088 * @brief Sets a given bit to false. 01089 * @param __position The index of the bit. 01090 * @throw std::out_of_range If @a pos is bigger the size of the %set. 01091 * 01092 * Same as writing @c set(pos,false). 01093 */ 01094 bitset<_Nb>& 01095 reset(size_t __position) 01096 { 01097 if (__position >= _Nb) 01098 __throw_out_of_range(__N("bitset::reset")); 01099 return _Unchecked_reset(__position); 01100 } 01101 01102 /** 01103 * @brief Toggles every bit to its opposite value. 01104 */ 01105 bitset<_Nb>& 01106 flip() _GLIBCXX_NOEXCEPT 01107 { 01108 this->_M_do_flip(); 01109 this->_M_do_sanitize(); 01110 return *this; 01111 } 01112 01113 /** 01114 * @brief Toggles a given bit to its opposite value. 01115 * @param __position The index of the bit. 01116 * @throw std::out_of_range If @a pos is bigger the size of the %set. 01117 */ 01118 bitset<_Nb>& 01119 flip(size_t __position) 01120 { 01121 if (__position >= _Nb) 01122 __throw_out_of_range(__N("bitset::flip")); 01123 return _Unchecked_flip(__position); 01124 } 01125 01126 /// See the no-argument flip(). 01127 bitset<_Nb> 01128 operator~() const _GLIBCXX_NOEXCEPT 01129 { return bitset<_Nb>(*this).flip(); } 01130 01131 //@{ 01132 /** 01133 * @brief Array-indexing support. 01134 * @param __position Index into the %bitset. 01135 * @return A bool for a <em>const %bitset</em>. For non-const 01136 * bitsets, an instance of the reference proxy class. 01137 * @note These operators do no range checking and throw no exceptions, 01138 * as required by DR 11 to the standard. 01139 * 01140 * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already 01141 * resolves DR 11 (items 1 and 2), but does not do the range-checking 01142 * required by that DR's resolution. -pme 01143 * The DR has since been changed: range-checking is a precondition 01144 * (users' responsibility), and these functions must not throw. -pme 01145 */ 01146 reference 01147 operator[](size_t __position) 01148 { return reference(*this, __position); } 01149 01150 _GLIBCXX_CONSTEXPR bool 01151 operator[](size_t __position) const 01152 { return _Unchecked_test(__position); } 01153 //@} 01154 01155 /** 01156 * @brief Returns a numerical interpretation of the %bitset. 01157 * @return The integral equivalent of the bits. 01158 * @throw std::overflow_error If there are too many bits to be 01159 * represented in an @c unsigned @c long. 01160 */ 01161 unsigned long 01162 to_ulong() const 01163 { return this->_M_do_to_ulong(); } 01164 01165 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01166 unsigned long long 01167 to_ullong() const 01168 { return this->_M_do_to_ullong(); } 01169 #endif 01170 01171 /** 01172 * @brief Returns a character interpretation of the %bitset. 01173 * @return The string equivalent of the bits. 01174 * 01175 * Note the ordering of the bits: decreasing character positions 01176 * correspond to increasing bit positions (see the main class notes for 01177 * an example). 01178 */ 01179 template<class _CharT, class _Traits, class _Alloc> 01180 std::basic_string<_CharT, _Traits, _Alloc> 01181 to_string() const 01182 { 01183 std::basic_string<_CharT, _Traits, _Alloc> __result; 01184 _M_copy_to_string(__result, _CharT('0'), _CharT('1')); 01185 return __result; 01186 } 01187 01188 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01189 // 396. what are characters zero and one. 01190 template<class _CharT, class _Traits, class _Alloc> 01191 std::basic_string<_CharT, _Traits, _Alloc> 01192 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 01193 { 01194 std::basic_string<_CharT, _Traits, _Alloc> __result; 01195 _M_copy_to_string(__result, __zero, __one); 01196 return __result; 01197 } 01198 01199 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01200 // 434. bitset::to_string() hard to use. 01201 template<class _CharT, class _Traits> 01202 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 01203 to_string() const 01204 { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); } 01205 01206 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01207 // 853. to_string needs updating with zero and one. 01208 template<class _CharT, class _Traits> 01209 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 01210 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 01211 { return to_string<_CharT, _Traits, 01212 std::allocator<_CharT> >(__zero, __one); } 01213 01214 template<class _CharT> 01215 std::basic_string<_CharT, std::char_traits<_CharT>, 01216 std::allocator<_CharT> > 01217 to_string() const 01218 { 01219 return to_string<_CharT, std::char_traits<_CharT>, 01220 std::allocator<_CharT> >(); 01221 } 01222 01223 template<class _CharT> 01224 std::basic_string<_CharT, std::char_traits<_CharT>, 01225 std::allocator<_CharT> > 01226 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 01227 { 01228 return to_string<_CharT, std::char_traits<_CharT>, 01229 std::allocator<_CharT> >(__zero, __one); 01230 } 01231 01232 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 01233 to_string() const 01234 { 01235 return to_string<char, std::char_traits<char>, 01236 std::allocator<char> >(); 01237 } 01238 01239 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 01240 to_string(char __zero, char __one = '1') const 01241 { 01242 return to_string<char, std::char_traits<char>, 01243 std::allocator<char> >(__zero, __one); 01244 } 01245 01246 // Helper functions for string operations. 01247 template<class _CharT, class _Traits> 01248 void 01249 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 01250 _CharT, _CharT); 01251 01252 template<class _CharT, class _Traits, class _Alloc> 01253 void 01254 _M_copy_from_string(const std::basic_string<_CharT, 01255 _Traits, _Alloc>& __s, size_t __pos, size_t __n, 01256 _CharT __zero, _CharT __one) 01257 { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n, 01258 __zero, __one); } 01259 01260 template<class _CharT, class _Traits, class _Alloc> 01261 void 01262 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&, 01263 _CharT, _CharT) const; 01264 01265 // NB: Backward compat. 01266 template<class _CharT, class _Traits, class _Alloc> 01267 void 01268 _M_copy_from_string(const std::basic_string<_CharT, 01269 _Traits, _Alloc>& __s, size_t __pos, size_t __n) 01270 { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); } 01271 01272 template<class _CharT, class _Traits, class _Alloc> 01273 void 01274 _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const 01275 { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); } 01276 01277 /// Returns the number of bits which are set. 01278 size_t 01279 count() const _GLIBCXX_NOEXCEPT 01280 { return this->_M_do_count(); } 01281 01282 /// Returns the total number of bits. 01283 _GLIBCXX_CONSTEXPR size_t 01284 size() const _GLIBCXX_NOEXCEPT 01285 { return _Nb; } 01286 01287 //@{ 01288 /// These comparisons for equality/inequality are, well, @e bitwise. 01289 bool 01290 operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT 01291 { return this->_M_is_equal(__rhs); } 01292 01293 bool 01294 operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT 01295 { return !this->_M_is_equal(__rhs); } 01296 //@} 01297 01298 /** 01299 * @brief Tests the value of a bit. 01300 * @param __position The index of a bit. 01301 * @return The value at @a pos. 01302 * @throw std::out_of_range If @a pos is bigger the size of the %set. 01303 */ 01304 bool 01305 test(size_t __position) const 01306 { 01307 if (__position >= _Nb) 01308 __throw_out_of_range(__N("bitset::test")); 01309 return _Unchecked_test(__position); 01310 } 01311 01312 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01313 // DR 693. std::bitset::all() missing. 01314 /** 01315 * @brief Tests whether all the bits are on. 01316 * @return True if all the bits are set. 01317 */ 01318 bool 01319 all() const _GLIBCXX_NOEXCEPT 01320 { return this->template _M_are_all<_Nb>(); } 01321 01322 /** 01323 * @brief Tests whether any of the bits are on. 01324 * @return True if at least one bit is set. 01325 */ 01326 bool 01327 any() const _GLIBCXX_NOEXCEPT 01328 { return this->_M_is_any(); } 01329 01330 /** 01331 * @brief Tests whether any of the bits are on. 01332 * @return True if none of the bits are set. 01333 */ 01334 bool 01335 none() const _GLIBCXX_NOEXCEPT 01336 { return !this->_M_is_any(); } 01337 01338 //@{ 01339 /// Self-explanatory. 01340 bitset<_Nb> 01341 operator<<(size_t __position) const _GLIBCXX_NOEXCEPT 01342 { return bitset<_Nb>(*this) <<= __position; } 01343 01344 bitset<_Nb> 01345 operator>>(size_t __position) const _GLIBCXX_NOEXCEPT 01346 { return bitset<_Nb>(*this) >>= __position; } 01347 //@} 01348 01349 /** 01350 * @brief Finds the index of the first "on" bit. 01351 * @return The index of the first bit set, or size() if not found. 01352 * @ingroup SGIextensions 01353 * @sa _Find_next 01354 */ 01355 size_t 01356 _Find_first() const _GLIBCXX_NOEXCEPT 01357 { return this->_M_do_find_first(_Nb); } 01358 01359 /** 01360 * @brief Finds the index of the next "on" bit after prev. 01361 * @return The index of the next bit set, or size() if not found. 01362 * @param __prev Where to start searching. 01363 * @ingroup SGIextensions 01364 * @sa _Find_first 01365 */ 01366 size_t 01367 _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT 01368 { return this->_M_do_find_next(__prev, _Nb); } 01369 }; 01370 01371 // Definitions of non-inline member functions. 01372 template<size_t _Nb> 01373 template<class _CharT, class _Traits> 01374 void 01375 bitset<_Nb>:: 01376 _M_copy_from_ptr(const _CharT* __s, size_t __len, 01377 size_t __pos, size_t __n, _CharT __zero, _CharT __one) 01378 { 01379 reset(); 01380 const size_t __nbits = std::min(_Nb, std::min(__n, __len - __pos)); 01381 for (size_t __i = __nbits; __i > 0; --__i) 01382 { 01383 const _CharT __c = __s[__pos + __nbits - __i]; 01384 if (_Traits::eq(__c, __zero)) 01385 ; 01386 else if (_Traits::eq(__c, __one)) 01387 _Unchecked_set(__i - 1); 01388 else 01389 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr")); 01390 } 01391 } 01392 01393 template<size_t _Nb> 01394 template<class _CharT, class _Traits, class _Alloc> 01395 void 01396 bitset<_Nb>:: 01397 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s, 01398 _CharT __zero, _CharT __one) const 01399 { 01400 __s.assign(_Nb, __zero); 01401 for (size_t __i = _Nb; __i > 0; --__i) 01402 if (_Unchecked_test(__i - 1)) 01403 _Traits::assign(__s[_Nb - __i], __one); 01404 } 01405 01406 // 23.3.5.3 bitset operations: 01407 //@{ 01408 /** 01409 * @brief Global bitwise operations on bitsets. 01410 * @param __x A bitset. 01411 * @param __y A bitset of the same size as @a __x. 01412 * @return A new bitset. 01413 * 01414 * These should be self-explanatory. 01415 */ 01416 template<size_t _Nb> 01417 inline bitset<_Nb> 01418 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 01419 { 01420 bitset<_Nb> __result(__x); 01421 __result &= __y; 01422 return __result; 01423 } 01424 01425 template<size_t _Nb> 01426 inline bitset<_Nb> 01427 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 01428 { 01429 bitset<_Nb> __result(__x); 01430 __result |= __y; 01431 return __result; 01432 } 01433 01434 template <size_t _Nb> 01435 inline bitset<_Nb> 01436 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 01437 { 01438 bitset<_Nb> __result(__x); 01439 __result ^= __y; 01440 return __result; 01441 } 01442 //@} 01443 01444 //@{ 01445 /** 01446 * @brief Global I/O operators for bitsets. 01447 * 01448 * Direct I/O between streams and bitsets is supported. Output is 01449 * straightforward. Input will skip whitespace, only accept @a 0 and @a 1 01450 * characters, and will only extract as many digits as the %bitset will 01451 * hold. 01452 */ 01453 template<class _CharT, class _Traits, size_t _Nb> 01454 std::basic_istream<_CharT, _Traits>& 01455 operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 01456 { 01457 typedef typename _Traits::char_type char_type; 01458 typedef std::basic_istream<_CharT, _Traits> __istream_type; 01459 typedef typename __istream_type::ios_base __ios_base; 01460 01461 std::basic_string<_CharT, _Traits> __tmp; 01462 __tmp.reserve(_Nb); 01463 01464 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01465 // 303. Bitset input operator underspecified 01466 const char_type __zero = __is.widen('0'); 01467 const char_type __one = __is.widen('1'); 01468 01469 typename __ios_base::iostate __state = __ios_base::goodbit; 01470 typename __istream_type::sentry __sentry(__is); 01471 if (__sentry) 01472 { 01473 __try 01474 { 01475 for (size_t __i = _Nb; __i > 0; --__i) 01476 { 01477 static typename _Traits::int_type __eof = _Traits::eof(); 01478 01479 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 01480 if (_Traits::eq_int_type(__c1, __eof)) 01481 { 01482 __state |= __ios_base::eofbit; 01483 break; 01484 } 01485 else 01486 { 01487 const char_type __c2 = _Traits::to_char_type(__c1); 01488 if (_Traits::eq(__c2, __zero)) 01489 __tmp.push_back(__zero); 01490 else if (_Traits::eq(__c2, __one)) 01491 __tmp.push_back(__one); 01492 else if (_Traits:: 01493 eq_int_type(__is.rdbuf()->sputbackc(__c2), 01494 __eof)) 01495 { 01496 __state |= __ios_base::failbit; 01497 break; 01498 } 01499 } 01500 } 01501 } 01502 __catch(__cxxabiv1::__forced_unwind&) 01503 { 01504 __is._M_setstate(__ios_base::badbit); 01505 __throw_exception_again; 01506 } 01507 __catch(...) 01508 { __is._M_setstate(__ios_base::badbit); } 01509 } 01510 01511 if (__tmp.empty() && _Nb) 01512 __state |= __ios_base::failbit; 01513 else 01514 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb, 01515 __zero, __one); 01516 if (__state) 01517 __is.setstate(__state); 01518 return __is; 01519 } 01520 01521 template <class _CharT, class _Traits, size_t _Nb> 01522 std::basic_ostream<_CharT, _Traits>& 01523 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 01524 const bitset<_Nb>& __x) 01525 { 01526 std::basic_string<_CharT, _Traits> __tmp; 01527 01528 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01529 // 396. what are characters zero and one. 01530 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc()); 01531 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 01532 return __os << __tmp; 01533 } 01534 //@} 01535 01536 _GLIBCXX_END_NAMESPACE_CONTAINER 01537 } // namespace std 01538 01539 #undef _GLIBCXX_BITSET_WORDS 01540 #undef _GLIBCXX_BITSET_BITS_PER_WORD 01541 #undef _GLIBCXX_BITSET_BITS_PER_ULL 01542 01543 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01544 01545 #include <bits/functional_hash.h> 01546 01547 namespace std _GLIBCXX_VISIBILITY(default) 01548 { 01549 _GLIBCXX_BEGIN_NAMESPACE_VERSION 01550 01551 // DR 1182. 01552 /// std::hash specialization for bitset. 01553 template<size_t _Nb> 01554 struct hash<_GLIBCXX_STD_C::bitset<_Nb>> 01555 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>> 01556 { 01557 size_t 01558 operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept 01559 { 01560 const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__; 01561 return std::_Hash_impl::hash(__b._M_getdata(), __clength); 01562 } 01563 }; 01564 01565 template<> 01566 struct hash<_GLIBCXX_STD_C::bitset<0>> 01567 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>> 01568 { 01569 size_t 01570 operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept 01571 { return 0; } 01572 }; 01573 01574 _GLIBCXX_END_NAMESPACE_VERSION 01575 } // namespace 01576 01577 #endif // __GXX_EXPERIMENTAL_CXX0X__ 01578 01579 #ifdef _GLIBCXX_DEBUG 01580 # include <debug/bitset> 01581 #endif 01582 01583 #ifdef _GLIBCXX_PROFILE 01584 # include <profile/bitset> 01585 #endif 01586 01587 #endif /* _GLIBCXX_BITSET */