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