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