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