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