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