43 #ifndef _GLIBCXX_BITSET
44 #define _GLIBCXX_BITSET 1
46 #pragma GCC system_header
53 #include <cxxabi-forced.h>
55 #define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * sizeof(unsigned long))
56 #define _GLIBCXX_BITSET_WORDS(__n) \
57 ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \
58 / _GLIBCXX_BITSET_BITS_PER_WORD)
60 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
71 typedef unsigned long _WordT;
79 _Base_bitset(
unsigned long __val)
86 _S_whichword(
size_t __pos )
87 {
return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
90 _S_whichbyte(
size_t __pos )
91 {
return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
94 _S_whichbit(
size_t __pos )
95 {
return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
98 _S_maskbit(
size_t __pos )
99 {
return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
102 _M_getword(
size_t __pos)
103 {
return _M_w[_S_whichword(__pos)]; }
106 _M_getword(
size_t __pos)
const
107 {
return _M_w[_S_whichword(__pos)]; }
111 {
return _M_w[_Nw - 1]; }
115 {
return _M_w[_Nw - 1]; }
118 _M_do_and(
const _Base_bitset<_Nw>& __x)
120 for (
size_t __i = 0; __i < _Nw; __i++)
121 _M_w[__i] &= __x._M_w[__i];
125 _M_do_or(
const _Base_bitset<_Nw>& __x)
127 for (
size_t __i = 0; __i < _Nw; __i++)
128 _M_w[__i] |= __x._M_w[__i];
132 _M_do_xor(
const _Base_bitset<_Nw>& __x)
134 for (
size_t __i = 0; __i < _Nw; __i++)
135 _M_w[__i] ^= __x._M_w[__i];
139 _M_do_left_shift(
size_t __shift);
142 _M_do_right_shift(
size_t __shift);
147 for (
size_t __i = 0; __i < _Nw; __i++)
148 _M_w[__i] = ~_M_w[__i];
154 for (
size_t __i = 0; __i < _Nw; __i++)
155 _M_w[__i] = ~static_cast<_WordT>(0);
160 { __builtin_memset(_M_w, 0, _Nw *
sizeof(_WordT)); }
163 _M_is_equal(
const _Base_bitset<_Nw>& __x)
const
165 for (
size_t __i = 0; __i < _Nw; ++__i)
166 if (_M_w[__i] != __x._M_w[__i])
172 _M_are_all_aux()
const
174 for (
size_t __i = 0; __i < _Nw - 1; __i++)
175 if (_M_w[__i] != ~static_cast<_WordT>(0))
177 return ((_Nw - 1) * _GLIBCXX_BITSET_BITS_PER_WORD
178 + __builtin_popcountl(_M_hiword()));
184 for (
size_t __i = 0; __i < _Nw; __i++)
185 if (_M_w[__i] != static_cast<_WordT>(0))
194 for (
size_t __i = 0; __i < _Nw; __i++)
195 __result += __builtin_popcountl(_M_w[__i]);
200 _M_do_to_ulong()
const;
204 _M_do_find_first(
size_t __not_found)
const;
208 _M_do_find_next(
size_t __prev,
size_t __not_found)
const;
214 _Base_bitset<_Nw>::_M_do_left_shift(
size_t __shift)
216 if (__builtin_expect(__shift != 0, 1))
218 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
219 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
222 for (
size_t __n = _Nw - 1; __n >= __wshift; --__n)
223 _M_w[__n] = _M_w[__n - __wshift];
226 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
228 for (
size_t __n = _Nw - 1; __n > __wshift; --__n)
229 _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
230 | (_M_w[__n - __wshift - 1] >> __sub_offset));
231 _M_w[__wshift] = _M_w[0] << __offset;
234 std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
240 _Base_bitset<_Nw>::_M_do_right_shift(
size_t __shift)
242 if (__builtin_expect(__shift != 0, 1))
244 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
245 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
246 const size_t __limit = _Nw - __wshift - 1;
249 for (
size_t __n = 0; __n <= __limit; ++__n)
250 _M_w[__n] = _M_w[__n + __wshift];
253 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
255 for (
size_t __n = 0; __n < __limit; ++__n)
256 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
257 | (_M_w[__n + __wshift + 1] << __sub_offset));
258 _M_w[__limit] = _M_w[_Nw-1] >> __offset;
261 std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
267 _Base_bitset<_Nw>::_M_do_to_ulong()
const
269 for (
size_t __i = 1; __i < _Nw; ++__i)
271 __throw_overflow_error(__N(
"_Base_bitset::_M_do_to_ulong"));
277 _Base_bitset<_Nw>::_M_do_find_first(
size_t __not_found)
const
279 for (
size_t __i = 0; __i < _Nw; __i++)
281 _WordT __thisword = _M_w[__i];
282 if (__thisword != static_cast<_WordT>(0))
283 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
284 + __builtin_ctzl(__thisword));
292 _Base_bitset<_Nw>::_M_do_find_next(
size_t __prev,
size_t __not_found)
const
298 if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
302 size_t __i = _S_whichword(__prev);
303 _WordT __thisword = _M_w[__i];
306 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
308 if (__thisword != static_cast<_WordT>(0))
309 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
310 + __builtin_ctzl(__thisword));
314 for (; __i < _Nw; __i++)
316 __thisword = _M_w[__i];
317 if (__thisword != static_cast<_WordT>(0))
318 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
319 + __builtin_ctzl(__thisword));
331 struct _Base_bitset<1>
333 typedef unsigned long _WordT;
340 _Base_bitset(
unsigned long __val)
345 _S_whichword(
size_t __pos )
346 {
return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
349 _S_whichbyte(
size_t __pos )
350 {
return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
353 _S_whichbit(
size_t __pos )
354 {
return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
357 _S_maskbit(
size_t __pos )
358 {
return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
365 _M_getword(
size_t)
const
378 { _M_w &= __x._M_w; }
382 { _M_w |= __x._M_w; }
386 { _M_w ^= __x._M_w; }
389 _M_do_left_shift(
size_t __shift)
390 { _M_w <<= __shift; }
393 _M_do_right_shift(
size_t __shift)
394 { _M_w >>= __shift; }
402 { _M_w = ~static_cast<_WordT>(0); }
410 {
return _M_w == __x._M_w; }
413 _M_are_all_aux()
const
414 {
return __builtin_popcountl(_M_w); }
418 {
return _M_w != 0; }
422 {
return __builtin_popcountl(_M_w); }
425 _M_do_to_ulong()
const
429 _M_do_find_first(
size_t __not_found)
const
432 return __builtin_ctzl(_M_w);
439 _M_do_find_next(
size_t __prev,
size_t __not_found)
const
442 if (__prev >= ((
size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
445 _WordT __x = _M_w >> __prev;
447 return __builtin_ctzl(__x) + __prev;
459 struct _Base_bitset<0>
461 typedef unsigned long _WordT;
466 _Base_bitset(
unsigned long)
470 _S_whichword(
size_t __pos )
471 {
return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
474 _S_whichbyte(
size_t __pos )
475 {
return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
478 _S_whichbit(
size_t __pos )
479 {
return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
482 _S_maskbit(
size_t __pos )
483 {
return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
493 _M_getword(
size_t)
const
495 __throw_out_of_range(__N(
"_Base_bitset::_M_getword"));
516 _M_do_left_shift(
size_t)
520 _M_do_right_shift(
size_t)
543 _M_are_all_aux()
const
555 _M_do_to_ulong()
const
561 _M_do_find_first(
size_t)
const
565 _M_do_find_next(
size_t,
size_t)
const
571 template<
size_t _Extrabits>
574 static void _S_do_sanitize(
unsigned long& __val)
575 { __val &= ~((~static_cast<
unsigned long>(0)) << _Extrabits); }
580 {
static void _S_do_sanitize(
unsigned long) {} };
647 :
private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
651 typedef unsigned long _WordT;
656 _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>::
657 _S_do_sanitize(this->_M_hiword());
686 _M_wp = &__b._M_getword(__pos);
687 _M_bpos = _Base::_S_whichbit(__pos);
698 *_M_wp |= _Base::_S_maskbit(_M_bpos);
700 *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
708 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
709 *_M_wp |= _Base::_S_maskbit(_M_bpos);
711 *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
718 {
return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
721 operator bool()
const
722 {
return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
728 *_M_wp ^= _Base::_S_maskbit(_M_bpos);
742 { _M_do_sanitize(); }
753 template<
class _CharT,
class _Traits,
class _Alloc>
756 size_t __position = 0)
759 if (__position > __s.
size())
760 __throw_out_of_range(__N(
"bitset::bitset initial position "
762 _M_copy_from_string(__s, __position,
764 _CharT(
'0'), _CharT(
'1'));
776 template<
class _CharT,
class _Traits,
class _Alloc>
778 size_t __position,
size_t __n)
781 if (__position > __s.
size())
782 __throw_out_of_range(__N(
"bitset::bitset initial position "
784 _M_copy_from_string(__s, __position, __n, _CharT(
'0'), _CharT(
'1'));
789 template<
class _CharT,
class _Traits,
class _Alloc>
791 size_t __position,
size_t __n,
792 _CharT __zero, _CharT __one = _CharT(
'1'))
795 if (__position > __s.
size())
796 __throw_out_of_range(__N(
"bitset::bitset initial position "
798 _M_copy_from_string(__s, __position, __n, __zero, __one);
812 this->_M_do_and(__rhs);
819 this->_M_do_or(__rhs);
826 this->_M_do_xor(__rhs);
839 operator<<=(
size_t __position)
841 if (__builtin_expect(__position < _Nb, 1))
843 this->_M_do_left_shift(__position);
844 this->_M_do_sanitize();
852 operator>>=(
size_t __position)
854 if (__builtin_expect(__position < _Nb, 1))
856 this->_M_do_right_shift(__position);
857 this->_M_do_sanitize();
872 _Unchecked_set(
size_t __pos)
874 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
879 _Unchecked_set(
size_t __pos,
int __val)
882 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
884 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
889 _Unchecked_reset(
size_t __pos)
891 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
896 _Unchecked_flip(
size_t __pos)
898 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
903 _Unchecked_test(
size_t __pos)
const
904 {
return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
905 != static_cast<_WordT>(0)); }
916 this->_M_do_sanitize();
927 set(
size_t __position,
bool __val =
true)
929 if (__position >= _Nb)
930 __throw_out_of_range(__N(
"bitset::set"));
931 return _Unchecked_set(__position, __val);
952 reset(
size_t __position)
954 if (__position >= _Nb)
955 __throw_out_of_range(__N(
"bitset::reset"));
956 return _Unchecked_reset(__position);
966 this->_M_do_sanitize();
976 flip(
size_t __position)
978 if (__position >= _Nb)
979 __throw_out_of_range(__N(
"bitset::flip"));
980 return _Unchecked_flip(__position);
1004 operator[](
size_t __position)
1005 {
return reference(*
this,__position); }
1008 operator[](
size_t __position)
const
1009 {
return _Unchecked_test(__position); }
1020 {
return this->_M_do_to_ulong(); }
1030 template<
class _CharT,
class _Traits,
class _Alloc>
1035 _M_copy_to_string(__result, _CharT(
'0'), _CharT(
'1'));
1041 template<
class _CharT,
class _Traits,
class _Alloc>
1043 to_string(_CharT __zero, _CharT __one = _CharT(
'1'))
const
1046 _M_copy_to_string(__result, __zero, __one);
1052 template<
class _CharT,
class _Traits>
1055 {
return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
1059 template<
class _CharT,
class _Traits>
1061 to_string(_CharT __zero, _CharT __one = _CharT(
'1'))
const
1062 {
return to_string<_CharT, _Traits,
1065 template<
class _CharT>
1070 return to_string<_CharT, std::char_traits<_CharT>,
1074 template<
class _CharT>
1077 to_string(_CharT __zero, _CharT __one = _CharT(
'1'))
const
1079 return to_string<_CharT, std::char_traits<_CharT>,
1086 return to_string<char, std::char_traits<char>,
1091 to_string(
char __zero,
char __one =
'1')
const
1093 return to_string<char, std::char_traits<char>,
1098 template<
class _CharT,
class _Traits>
1100 _M_copy_from_ptr(
const _CharT*,
size_t,
size_t,
size_t,
1103 template<
class _CharT,
class _Traits,
class _Alloc>
1106 _Traits, _Alloc>& __s,
size_t __pos,
size_t __n,
1107 _CharT __zero, _CharT __one)
1108 { _M_copy_from_ptr<_CharT, _Traits>(__s.
data(), __s.
size(), __pos, __n,
1111 template<
class _CharT,
class _Traits,
class _Alloc>
1114 _CharT, _CharT)
const;
1117 template<
class _CharT,
class _Traits,
class _Alloc>
1120 _Traits, _Alloc>& __s,
size_t __pos,
size_t __n)
1121 { _M_copy_from_string(__s, __pos, __n, _CharT(
'0'), _CharT(
'1')); }
1123 template<
class _CharT,
class _Traits,
class _Alloc>
1126 { _M_copy_to_string(__s, _CharT(
'0'), _CharT(
'1')); }
1131 {
return this->_M_do_count(); }
1142 {
return this->_M_is_equal(__rhs); }
1146 {
return !this->_M_is_equal(__rhs); }
1156 test(
size_t __position)
const
1158 if (__position >= _Nb)
1159 __throw_out_of_range(__N(
"bitset::test"));
1160 return _Unchecked_test(__position);
1171 {
return this->_M_are_all_aux() == _Nb; }
1179 {
return this->_M_is_any(); }
1187 {
return !this->_M_is_any(); }
1208 {
return this->_M_do_find_first(_Nb); }
1218 _Find_next(
size_t __prev )
const
1219 {
return this->_M_do_find_next(__prev, _Nb); }
1223 template<
size_t _Nb>
1224 template<
class _CharT,
class _Traits>
1227 _M_copy_from_ptr(
const _CharT* __s,
size_t __len,
1228 size_t __pos,
size_t __n, _CharT __zero, _CharT __one)
1232 for (
size_t __i = __nbits; __i > 0; --__i)
1234 const _CharT __c = __s[__pos + __nbits - __i];
1235 if (_Traits::eq(__c, __zero))
1237 else if (_Traits::eq(__c, __one))
1238 _Unchecked_set(__i - 1);
1240 __throw_invalid_argument(__N(
"bitset::_M_copy_from_ptr"));
1244 template<
size_t _Nb>
1245 template<
class _CharT,
class _Traits,
class _Alloc>
1249 _CharT __zero, _CharT __one)
const
1252 for (
size_t __i = _Nb; __i > 0; --__i)
1253 if (_Unchecked_test(__i - 1))
1254 _Traits::assign(__s[_Nb - __i], __one);
1267 template<
size_t _Nb>
1276 template<
size_t _Nb>
1285 template <
size_t _Nb>
1304 template<
class _CharT,
class _Traits,
size_t _Nb>
1308 typedef typename _Traits::char_type char_type;
1310 typedef typename __istream_type::ios_base __ios_base;
1317 const char_type __zero = __is.
widen(
'0');
1318 const char_type __one = __is.
widen(
'1');
1320 typename __ios_base::iostate __state = __ios_base::goodbit;
1321 typename __istream_type::sentry __sentry(__is);
1326 for (
size_t __i = _Nb; __i > 0; --__i)
1328 static typename _Traits::int_type __eof = _Traits::eof();
1330 typename _Traits::int_type __c1 = __is.
rdbuf()->sbumpc();
1331 if (_Traits::eq_int_type(__c1, __eof))
1333 __state |= __ios_base::eofbit;
1338 const char_type __c2 = _Traits::to_char_type(__c1);
1339 if (_Traits::eq(__c2, __zero))
1341 else if (_Traits::eq(__c2, __one))
1344 eq_int_type(__is.
rdbuf()->sputbackc(__c2),
1347 __state |= __ios_base::failbit;
1355 __is._M_setstate(__ios_base::badbit);
1356 __throw_exception_again;
1359 { __is._M_setstate(__ios_base::badbit); }
1362 if (__tmp.
empty() && _Nb)
1363 __state |= __ios_base::failbit;
1365 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb,
1372 template <
class _CharT,
class _Traits,
size_t _Nb>
1374 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1381 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
1382 __x._M_copy_to_string(__tmp, __ct.
widen(
'0'), __ct.
widen(
'1'));
1383 return __os << __tmp;
1387 _GLIBCXX_END_NESTED_NAMESPACE
1389 #undef _GLIBCXX_BITSET_WORDS
1390 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1392 #ifdef _GLIBCXX_DEBUG