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