197403Sobrien// <bitset> -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 597403Sobrien// 697403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 797403Sobrien// software; you can redistribute it and/or modify it under the 897403Sobrien// terms of the GNU General Public License as published by the 997403Sobrien// Free Software Foundation; either version 2, or (at your option) 1097403Sobrien// any later version. 1197403Sobrien 1297403Sobrien// This library is distributed in the hope that it will be useful, 1397403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1497403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1597403Sobrien// GNU General Public License for more details. 1697403Sobrien 1797403Sobrien// You should have received a copy of the GNU General Public License along 1897403Sobrien// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2097403Sobrien// USA. 2197403Sobrien 2297403Sobrien// As a special exception, you may use this file as part of a free software 2397403Sobrien// library without restriction. Specifically, if other files instantiate 2497403Sobrien// templates or use macros or inline functions from this file, or you compile 2597403Sobrien// this file and link it with other files to produce an executable, this 2697403Sobrien// file does not by itself cause the resulting executable to be covered by 2797403Sobrien// the GNU General Public License. This exception does not however 2897403Sobrien// invalidate any other reasons why the executable file might be covered by 2997403Sobrien// the GNU General Public License. 3097403Sobrien 3197403Sobrien/* 3297403Sobrien * Copyright (c) 1998 3397403Sobrien * Silicon Graphics Computer Systems, Inc. 3497403Sobrien * 3597403Sobrien * Permission to use, copy, modify, distribute and sell this software 3697403Sobrien * and its documentation for any purpose is hereby granted without fee, 3797403Sobrien * provided that the above copyright notice appear in all copies and 3897403Sobrien * that both that copyright notice and this permission notice appear 3997403Sobrien * in supporting documentation. Silicon Graphics makes no 4097403Sobrien * representations about the suitability of this software for any 4197403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4297403Sobrien */ 4397403Sobrien 44169691Skan/** @file include/bitset 45169691Skan * This is a Standard C++ Library header. 4697403Sobrien */ 4797403Sobrien 48132720Skan#ifndef _GLIBCXX_BITSET 49132720Skan#define _GLIBCXX_BITSET 1 5097403Sobrien 5197403Sobrien#pragma GCC system_header 5297403Sobrien 53132720Skan#include <cstddef> // For size_t 54132720Skan#include <cstring> // For memset 55132720Skan#include <limits> // For numeric_limits 5697403Sobrien#include <string> 57132720Skan#include <bits/functexcept.h> // For invalid_argument, out_of_range, 5897403Sobrien // overflow_error 59132720Skan#include <ostream> // For ostream (operator<<) 60132720Skan#include <istream> // For istream (operator>>) 6197403Sobrien 62132720Skan#define _GLIBCXX_BITSET_BITS_PER_WORD numeric_limits<unsigned long>::digits 63132720Skan#define _GLIBCXX_BITSET_WORDS(__n) \ 64169691Skan ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \ 65169691Skan / _GLIBCXX_BITSET_BITS_PER_WORD) 6697403Sobrien 67169691Skan_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) 68169691Skan 6997403Sobrien /** 7097403Sobrien * @if maint 7197403Sobrien * Base class, general case. It is a class inveriant that _Nw will be 7297403Sobrien * nonnegative. 7397403Sobrien * 7497403Sobrien * See documentation for bitset. 7597403Sobrien * @endif 7697403Sobrien */ 7797403Sobrien template<size_t _Nw> 7897403Sobrien struct _Base_bitset 7997403Sobrien { 8097403Sobrien typedef unsigned long _WordT; 8197403Sobrien 8297403Sobrien /// 0 is the least significant word. 8397403Sobrien _WordT _M_w[_Nw]; 8497403Sobrien 85169691Skan _Base_bitset() 86169691Skan { _M_do_reset(); } 87169691Skan 8897403Sobrien _Base_bitset(unsigned long __val) 8997403Sobrien { 9097403Sobrien _M_do_reset(); 9197403Sobrien _M_w[0] = __val; 9297403Sobrien } 9397403Sobrien 9497403Sobrien static size_t 9597403Sobrien _S_whichword(size_t __pos ) 96132720Skan { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 9797403Sobrien 9897403Sobrien static size_t 9997403Sobrien _S_whichbyte(size_t __pos ) 100132720Skan { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 10197403Sobrien 10297403Sobrien static size_t 10397403Sobrien _S_whichbit(size_t __pos ) 104132720Skan { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 10597403Sobrien 10697403Sobrien static _WordT 10797403Sobrien _S_maskbit(size_t __pos ) 10897403Sobrien { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 10997403Sobrien 11097403Sobrien _WordT& 11197403Sobrien _M_getword(size_t __pos) 11297403Sobrien { return _M_w[_S_whichword(__pos)]; } 11397403Sobrien 11497403Sobrien _WordT 11597403Sobrien _M_getword(size_t __pos) const 11697403Sobrien { return _M_w[_S_whichword(__pos)]; } 11797403Sobrien 11897403Sobrien _WordT& 119169691Skan _M_hiword() 120169691Skan { return _M_w[_Nw - 1]; } 12197403Sobrien 12297403Sobrien _WordT 123169691Skan _M_hiword() const 124169691Skan { return _M_w[_Nw - 1]; } 12597403Sobrien 12697403Sobrien void 12797403Sobrien _M_do_and(const _Base_bitset<_Nw>& __x) 12897403Sobrien { 12997403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 13097403Sobrien _M_w[__i] &= __x._M_w[__i]; 13197403Sobrien } 13297403Sobrien 13397403Sobrien void 13497403Sobrien _M_do_or(const _Base_bitset<_Nw>& __x) 13597403Sobrien { 13697403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 13797403Sobrien _M_w[__i] |= __x._M_w[__i]; 13897403Sobrien } 13997403Sobrien 14097403Sobrien void 14197403Sobrien _M_do_xor(const _Base_bitset<_Nw>& __x) 14297403Sobrien { 14397403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 14497403Sobrien _M_w[__i] ^= __x._M_w[__i]; 14597403Sobrien } 14697403Sobrien 14797403Sobrien void 14897403Sobrien _M_do_left_shift(size_t __shift); 14997403Sobrien 15097403Sobrien void 15197403Sobrien _M_do_right_shift(size_t __shift); 15297403Sobrien 15397403Sobrien void 15497403Sobrien _M_do_flip() 15597403Sobrien { 15697403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 15797403Sobrien _M_w[__i] = ~_M_w[__i]; 15897403Sobrien } 15997403Sobrien 16097403Sobrien void 16197403Sobrien _M_do_set() 16297403Sobrien { 16397403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 16497403Sobrien _M_w[__i] = ~static_cast<_WordT>(0); 16597403Sobrien } 16697403Sobrien 16797403Sobrien void 168169691Skan _M_do_reset() 169169691Skan { std::memset(_M_w, 0, _Nw * sizeof(_WordT)); } 17097403Sobrien 17197403Sobrien bool 17297403Sobrien _M_is_equal(const _Base_bitset<_Nw>& __x) const 17397403Sobrien { 17497403Sobrien for (size_t __i = 0; __i < _Nw; ++__i) 17597403Sobrien { 17697403Sobrien if (_M_w[__i] != __x._M_w[__i]) 17797403Sobrien return false; 17897403Sobrien } 17997403Sobrien return true; 18097403Sobrien } 18197403Sobrien 18297403Sobrien bool 18397403Sobrien _M_is_any() const 18497403Sobrien { 18597403Sobrien for (size_t __i = 0; __i < _Nw; __i++) 18697403Sobrien { 18797403Sobrien if (_M_w[__i] != static_cast<_WordT>(0)) 18897403Sobrien return true; 18997403Sobrien } 19097403Sobrien return false; 19197403Sobrien } 19297403Sobrien 19397403Sobrien size_t 19497403Sobrien _M_do_count() const 19597403Sobrien { 19697403Sobrien size_t __result = 0; 197132720Skan for (size_t __i = 0; __i < _Nw; __i++) 198132720Skan __result += __builtin_popcountl(_M_w[__i]); 19997403Sobrien return __result; 20097403Sobrien } 20197403Sobrien 20297403Sobrien unsigned long 20397403Sobrien _M_do_to_ulong() const; 20497403Sobrien 20597403Sobrien // find first "on" bit 20697403Sobrien size_t 20797403Sobrien _M_do_find_first(size_t __not_found) const; 20897403Sobrien 20997403Sobrien // find the next "on" bit that follows "prev" 21097403Sobrien size_t 21197403Sobrien _M_do_find_next(size_t __prev, size_t __not_found) const; 21297403Sobrien }; 21397403Sobrien 21497403Sobrien // Definitions of non-inline functions from _Base_bitset. 21597403Sobrien template<size_t _Nw> 21697403Sobrien void 21797403Sobrien _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) 21897403Sobrien { 219117397Skan if (__builtin_expect(__shift != 0, 1)) 22097403Sobrien { 221132720Skan const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 222132720Skan const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 22397403Sobrien 22497403Sobrien if (__offset == 0) 22597403Sobrien for (size_t __n = _Nw - 1; __n >= __wshift; --__n) 22697403Sobrien _M_w[__n] = _M_w[__n - __wshift]; 22797403Sobrien else 22897403Sobrien { 229169691Skan const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 230169691Skan - __offset); 23197403Sobrien for (size_t __n = _Nw - 1; __n > __wshift; --__n) 232169691Skan _M_w[__n] = ((_M_w[__n - __wshift] << __offset) 233169691Skan | (_M_w[__n - __wshift - 1] >> __sub_offset)); 23497403Sobrien _M_w[__wshift] = _M_w[0] << __offset; 23597403Sobrien } 23697403Sobrien 237132720Skan std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); 23897403Sobrien } 23997403Sobrien } 24097403Sobrien 24197403Sobrien template<size_t _Nw> 24297403Sobrien void 24397403Sobrien _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) 24497403Sobrien { 245117397Skan if (__builtin_expect(__shift != 0, 1)) 24697403Sobrien { 247132720Skan const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 248132720Skan const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 24997403Sobrien const size_t __limit = _Nw - __wshift - 1; 25097403Sobrien 25197403Sobrien if (__offset == 0) 25297403Sobrien for (size_t __n = 0; __n <= __limit; ++__n) 25397403Sobrien _M_w[__n] = _M_w[__n + __wshift]; 25497403Sobrien else 25597403Sobrien { 256169691Skan const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 257169691Skan - __offset); 25897403Sobrien for (size_t __n = 0; __n < __limit; ++__n) 259169691Skan _M_w[__n] = ((_M_w[__n + __wshift] >> __offset) 260169691Skan | (_M_w[__n + __wshift + 1] << __sub_offset)); 26197403Sobrien _M_w[__limit] = _M_w[_Nw-1] >> __offset; 26297403Sobrien } 263132720Skan 264132720Skan std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); 26597403Sobrien } 26697403Sobrien } 26797403Sobrien 26897403Sobrien template<size_t _Nw> 26997403Sobrien unsigned long 27097403Sobrien _Base_bitset<_Nw>::_M_do_to_ulong() const 27197403Sobrien { 27297403Sobrien for (size_t __i = 1; __i < _Nw; ++__i) 27397403Sobrien if (_M_w[__i]) 274132720Skan __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong")); 27597403Sobrien return _M_w[0]; 27697403Sobrien } 27797403Sobrien 27897403Sobrien template<size_t _Nw> 27997403Sobrien size_t 28097403Sobrien _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const 28197403Sobrien { 282132720Skan for (size_t __i = 0; __i < _Nw; __i++) 28397403Sobrien { 28497403Sobrien _WordT __thisword = _M_w[__i]; 285132720Skan if (__thisword != static_cast<_WordT>(0)) 286169691Skan return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 287169691Skan + __builtin_ctzl(__thisword)); 28897403Sobrien } 28997403Sobrien // not found, so return an indication of failure. 29097403Sobrien return __not_found; 29197403Sobrien } 29297403Sobrien 29397403Sobrien template<size_t _Nw> 29497403Sobrien size_t 29597403Sobrien _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const 29697403Sobrien { 29797403Sobrien // make bound inclusive 29897403Sobrien ++__prev; 29997403Sobrien 30097403Sobrien // check out of bounds 301132720Skan if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD) 30297403Sobrien return __not_found; 30397403Sobrien 30497403Sobrien // search first word 30597403Sobrien size_t __i = _S_whichword(__prev); 30697403Sobrien _WordT __thisword = _M_w[__i]; 30797403Sobrien 30897403Sobrien // mask off bits below bound 30997403Sobrien __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 31097403Sobrien 311132720Skan if (__thisword != static_cast<_WordT>(0)) 312169691Skan return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 313169691Skan + __builtin_ctzl(__thisword)); 31497403Sobrien 31597403Sobrien // check subsequent words 31697403Sobrien __i++; 317169691Skan for (; __i < _Nw; __i++) 31897403Sobrien { 31997403Sobrien __thisword = _M_w[__i]; 320132720Skan if (__thisword != static_cast<_WordT>(0)) 321169691Skan return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 322169691Skan + __builtin_ctzl(__thisword)); 32397403Sobrien } 32497403Sobrien // not found, so return an indication of failure. 32597403Sobrien return __not_found; 32697403Sobrien } // end _M_do_find_next 32797403Sobrien 32897403Sobrien /** 32997403Sobrien * @if maint 33097403Sobrien * Base class, specialization for a single word. 33197403Sobrien * 33297403Sobrien * See documentation for bitset. 33397403Sobrien * @endif 33497403Sobrien */ 33597403Sobrien template<> 33697403Sobrien struct _Base_bitset<1> 33797403Sobrien { 33897403Sobrien typedef unsigned long _WordT; 33997403Sobrien _WordT _M_w; 34097403Sobrien 341169691Skan _Base_bitset(void) 342169691Skan : _M_w(0) 343169691Skan { } 34497403Sobrien 345169691Skan _Base_bitset(unsigned long __val) 346169691Skan : _M_w(__val) 347169691Skan { } 348169691Skan 34997403Sobrien static size_t 35097403Sobrien _S_whichword(size_t __pos ) 351132720Skan { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 35297403Sobrien 35397403Sobrien static size_t 35497403Sobrien _S_whichbyte(size_t __pos ) 355132720Skan { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 35697403Sobrien 35797403Sobrien static size_t 35897403Sobrien _S_whichbit(size_t __pos ) 359132720Skan { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 36097403Sobrien 36197403Sobrien static _WordT 36297403Sobrien _S_maskbit(size_t __pos ) 36397403Sobrien { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 36497403Sobrien 36597403Sobrien _WordT& 366169691Skan _M_getword(size_t) 367169691Skan { return _M_w; } 36897403Sobrien 36997403Sobrien _WordT 370169691Skan _M_getword(size_t) const 371169691Skan { return _M_w; } 37297403Sobrien 37397403Sobrien _WordT& 374169691Skan _M_hiword() 375169691Skan { return _M_w; } 37697403Sobrien 37797403Sobrien _WordT 378169691Skan _M_hiword() const 379169691Skan { return _M_w; } 38097403Sobrien 38197403Sobrien void 382169691Skan _M_do_and(const _Base_bitset<1>& __x) 383169691Skan { _M_w &= __x._M_w; } 38497403Sobrien 38597403Sobrien void 386169691Skan _M_do_or(const _Base_bitset<1>& __x) 387169691Skan { _M_w |= __x._M_w; } 38897403Sobrien 38997403Sobrien void 390169691Skan _M_do_xor(const _Base_bitset<1>& __x) 391169691Skan { _M_w ^= __x._M_w; } 39297403Sobrien 39397403Sobrien void 394169691Skan _M_do_left_shift(size_t __shift) 395169691Skan { _M_w <<= __shift; } 39697403Sobrien 39797403Sobrien void 398169691Skan _M_do_right_shift(size_t __shift) 399169691Skan { _M_w >>= __shift; } 40097403Sobrien 40197403Sobrien void 402169691Skan _M_do_flip() 403169691Skan { _M_w = ~_M_w; } 40497403Sobrien 40597403Sobrien void 406169691Skan _M_do_set() 407169691Skan { _M_w = ~static_cast<_WordT>(0); } 40897403Sobrien 40997403Sobrien void 410169691Skan _M_do_reset() 411169691Skan { _M_w = 0; } 41297403Sobrien 41397403Sobrien bool 41497403Sobrien _M_is_equal(const _Base_bitset<1>& __x) const 41597403Sobrien { return _M_w == __x._M_w; } 41697403Sobrien 41797403Sobrien bool 418169691Skan _M_is_any() const 419169691Skan { return _M_w != 0; } 42097403Sobrien 42197403Sobrien size_t 422169691Skan _M_do_count() const 423169691Skan { return __builtin_popcountl(_M_w); } 42497403Sobrien 42597403Sobrien unsigned long 426169691Skan _M_do_to_ulong() const 427169691Skan { return _M_w; } 42897403Sobrien 42997403Sobrien size_t 430132720Skan _M_do_find_first(size_t __not_found) const 431132720Skan { 432132720Skan if (_M_w != 0) 433132720Skan return __builtin_ctzl(_M_w); 434132720Skan else 435132720Skan return __not_found; 436132720Skan } 43797403Sobrien 43897403Sobrien // find the next "on" bit that follows "prev" 43997403Sobrien size_t 440132720Skan _M_do_find_next(size_t __prev, size_t __not_found) const 441132720Skan { 442132720Skan ++__prev; 443132720Skan if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD)) 444132720Skan return __not_found; 445132720Skan 446132720Skan _WordT __x = _M_w >> __prev; 447132720Skan if (__x != 0) 448132720Skan return __builtin_ctzl(__x) + __prev; 449132720Skan else 450132720Skan return __not_found; 451132720Skan } 45297403Sobrien }; 45397403Sobrien 454102782Skan /** 455102782Skan * @if maint 456102782Skan * Base class, specialization for no storage (zero-length %bitset). 457102782Skan * 458102782Skan * See documentation for bitset. 459102782Skan * @endif 460102782Skan */ 461102782Skan template<> 462102782Skan struct _Base_bitset<0> 463102782Skan { 464102782Skan typedef unsigned long _WordT; 465102782Skan 466169691Skan _Base_bitset() 467169691Skan { } 468102782Skan 469169691Skan _Base_bitset(unsigned long) 470169691Skan { } 471169691Skan 472102782Skan static size_t 473102782Skan _S_whichword(size_t __pos ) 474132720Skan { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 475102782Skan 476102782Skan static size_t 477102782Skan _S_whichbyte(size_t __pos ) 478132720Skan { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 479102782Skan 480102782Skan static size_t 481102782Skan _S_whichbit(size_t __pos ) 482132720Skan { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 483102782Skan 484102782Skan static _WordT 485102782Skan _S_maskbit(size_t __pos ) 486102782Skan { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 487102782Skan 488102782Skan // This would normally give access to the data. The bounds-checking 489102782Skan // in the bitset class will prevent the user from getting this far, 490102782Skan // but (1) it must still return an lvalue to compile, and (2) the 491102782Skan // user might call _Unchecked_set directly, in which case this /needs/ 492102782Skan // to fail. Let's not penalize zero-length users unless they actually 493102782Skan // make an unchecked call; all the memory ugliness is therefore 494102782Skan // localized to this single should-never-get-this-far function. 495102782Skan _WordT& 496102782Skan _M_getword(size_t) const 497132720Skan { 498132720Skan __throw_out_of_range(__N("_Base_bitset::_M_getword")); 499132720Skan return *new _WordT; 500132720Skan } 501102782Skan 502102782Skan _WordT 503169691Skan _M_hiword() const 504169691Skan { return 0; } 505102782Skan 506102782Skan void 507169691Skan _M_do_and(const _Base_bitset<0>&) 508169691Skan { } 509102782Skan 510102782Skan void 511169691Skan _M_do_or(const _Base_bitset<0>&) 512169691Skan { } 513102782Skan 514102782Skan void 515169691Skan _M_do_xor(const _Base_bitset<0>&) 516169691Skan { } 517102782Skan 518102782Skan void 519169691Skan _M_do_left_shift(size_t) 520169691Skan { } 521102782Skan 522102782Skan void 523169691Skan _M_do_right_shift(size_t) 524169691Skan { } 525102782Skan 526102782Skan void 527169691Skan _M_do_flip() 528169691Skan { } 529102782Skan 530102782Skan void 531169691Skan _M_do_set() 532169691Skan { } 533102782Skan 534102782Skan void 535169691Skan _M_do_reset() 536169691Skan { } 537102782Skan 538102782Skan // Are all empty bitsets equal to each other? Are they equal to 539102782Skan // themselves? How to compare a thing which has no state? What is 540102782Skan // the sound of one zero-length bitset clapping? 541102782Skan bool 542169691Skan _M_is_equal(const _Base_bitset<0>&) const 543169691Skan { return true; } 544102782Skan 545102782Skan bool 546169691Skan _M_is_any() const 547169691Skan { return false; } 548102782Skan 549102782Skan size_t 550169691Skan _M_do_count() const 551169691Skan { return 0; } 552102782Skan 553102782Skan unsigned long 554169691Skan _M_do_to_ulong() const 555169691Skan { return 0; } 556102782Skan 557102782Skan // Normally "not found" is the size, but that could also be 558102782Skan // misinterpreted as an index in this corner case. Oh well. 559102782Skan size_t 560169691Skan _M_do_find_first(size_t) const 561169691Skan { return 0; } 562102782Skan 563102782Skan size_t 564169691Skan _M_do_find_next(size_t, size_t) const 565169691Skan { return 0; } 566102782Skan }; 567102782Skan 568102782Skan 56997403Sobrien // Helper class to zero out the unused high-order bits in the highest word. 57097403Sobrien template<size_t _Extrabits> 57197403Sobrien struct _Sanitize 57297403Sobrien { 57397403Sobrien static void _S_do_sanitize(unsigned long& __val) 57497403Sobrien { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } 57597403Sobrien }; 57697403Sobrien 57797403Sobrien template<> 57897403Sobrien struct _Sanitize<0> 579169691Skan { static void _S_do_sanitize(unsigned long) {} }; 58097403Sobrien 58197403Sobrien /** 58297403Sobrien * @brief The %bitset class represents a @e fixed-size sequence of bits. 58397403Sobrien * 58497403Sobrien * @ingroup Containers 58597403Sobrien * 58697403Sobrien * (Note that %bitset does @e not meet the formal requirements of a 58797403Sobrien * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 58897403Sobrien * 589117397Skan * The template argument, @a Nb, may be any non-negative number, 590117397Skan * specifying the number of bits (e.g., "0", "12", "1024*1024"). 59197403Sobrien * 592117397Skan * In the general unoptimized case, storage is allocated in word-sized 593117397Skan * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B 594117397Skan * words will be used for storage. B - Nb%B bits are unused. (They are 595117397Skan * the high-order bits in the highest word.) It is a class invariant 596117397Skan * that those unused bits are always zero. 59797403Sobrien * 59897403Sobrien * If you think of %bitset as "a simple array of bits," be aware that 59997403Sobrien * your mental picture is reversed: a %bitset behaves the same way as 60097403Sobrien * bits in integers do, with the bit at index 0 in the "least significant 601117397Skan * / right-hand" position, and the bit at index Nb-1 in the "most 60297403Sobrien * significant / left-hand" position. Thus, unlike other containers, a 60397403Sobrien * %bitset's index "counts from right to left," to put it very loosely. 60497403Sobrien * 60597403Sobrien * This behavior is preserved when translating to and from strings. For 60697403Sobrien * example, the first line of the following program probably prints 60797403Sobrien * "b('a') is 0001100001" on a modern ASCII system. 60897403Sobrien * 60997403Sobrien * @code 61097403Sobrien * #include <bitset> 61197403Sobrien * #include <iostream> 61297403Sobrien * #include <sstream> 61397403Sobrien * 61497403Sobrien * using namespace std; 61597403Sobrien * 61697403Sobrien * int main() 61797403Sobrien * { 61897403Sobrien * long a = 'a'; 61997403Sobrien * bitset<10> b(a); 62097403Sobrien * 62197403Sobrien * cout << "b('a') is " << b << endl; 62297403Sobrien * 62397403Sobrien * ostringstream s; 62497403Sobrien * s << b; 62597403Sobrien * string str = s.str(); 62697403Sobrien * cout << "index 3 in the string is " << str[3] << " but\n" 62797403Sobrien * << "index 3 in the bitset is " << b[3] << endl; 62897403Sobrien * } 62997403Sobrien * @endcode 63097403Sobrien * 63197403Sobrien * Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23 632117397Skan * for a description of extensions. 63397403Sobrien * 63497403Sobrien * @if maint 63597403Sobrien * Most of the actual code isn't contained in %bitset<> itself, but in the 63697403Sobrien * base class _Base_bitset. The base class works with whole words, not with 63797403Sobrien * individual bits. This allows us to specialize _Base_bitset for the 63897403Sobrien * important special case where the %bitset is only a single word. 63997403Sobrien * 64097403Sobrien * Extra confusion can result due to the fact that the storage for 64197403Sobrien * _Base_bitset @e is a regular array, and is indexed as such. This is 64297403Sobrien * carefully encapsulated. 64397403Sobrien * @endif 64497403Sobrien */ 64597403Sobrien template<size_t _Nb> 646169691Skan class bitset 647169691Skan : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> 64897403Sobrien { 649169691Skan private: 650169691Skan typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base; 651169691Skan typedef unsigned long _WordT; 65297403Sobrien 653169691Skan void 654169691Skan _M_do_sanitize() 655169691Skan { 656169691Skan _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>:: 657169691Skan _S_do_sanitize(this->_M_hiword()); 658169691Skan } 65997403Sobrien 660169691Skan public: 661169691Skan /** 662169691Skan * This encapsulates the concept of a single bit. An instance of this 663169691Skan * class is a proxy for an actual bit; this way the individual bit 664169691Skan * operations are done as faster word-size bitwise instructions. 665169691Skan * 666169691Skan * Most users will never need to use this class directly; conversions 667169691Skan * to and from bool are automatic and should be transparent. Overloaded 668169691Skan * operators help to preserve the illusion. 669169691Skan * 670169691Skan * (On a typical system, this "bit %reference" is 64 times the size of 671169691Skan * an actual bit. Ha.) 672169691Skan */ 673169691Skan class reference 674169691Skan { 675169691Skan friend class bitset; 67697403Sobrien 677169691Skan _WordT *_M_wp; 678169691Skan size_t _M_bpos; 679169691Skan 680169691Skan // left undefined 681169691Skan reference(); 682169691Skan 683169691Skan public: 684169691Skan reference(bitset& __b, size_t __pos) 685169691Skan { 686169691Skan _M_wp = &__b._M_getword(__pos); 687169691Skan _M_bpos = _Base::_S_whichbit(__pos); 688169691Skan } 68997403Sobrien 690169691Skan ~reference() 691169691Skan { } 692169691Skan 693169691Skan // For b[i] = __x; 694169691Skan reference& 695169691Skan operator=(bool __x) 696169691Skan { 697169691Skan if (__x) 698169691Skan *_M_wp |= _Base::_S_maskbit(_M_bpos); 699169691Skan else 700169691Skan *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 701169691Skan return *this; 702169691Skan } 703169691Skan 704169691Skan // For b[i] = b[__j]; 705169691Skan reference& 706169691Skan operator=(const reference& __j) 707169691Skan { 708169691Skan if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 709169691Skan *_M_wp |= _Base::_S_maskbit(_M_bpos); 710169691Skan else 711169691Skan *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 712169691Skan return *this; 713169691Skan } 714169691Skan 715169691Skan // Flips the bit 716169691Skan bool 717169691Skan operator~() const 718169691Skan { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 719169691Skan 720169691Skan // For __x = b[i]; 721169691Skan operator bool() const 722169691Skan { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 723169691Skan 724169691Skan // For b[i].flip(); 725169691Skan reference& 726169691Skan flip() 727169691Skan { 728169691Skan *_M_wp ^= _Base::_S_maskbit(_M_bpos); 729169691Skan return *this; 730169691Skan } 731169691Skan }; 732169691Skan friend class reference; 733169691Skan 734169691Skan // 23.3.5.1 constructors: 735169691Skan /// All bits set to zero. 736169691Skan bitset() 737169691Skan { } 738169691Skan 739169691Skan /// Initial bits bitwise-copied from a single word (others set to zero). 740169691Skan bitset(unsigned long __val) 741169691Skan : _Base(__val) 742169691Skan { _M_do_sanitize(); } 743169691Skan 744169691Skan /** 745169691Skan * @brief Use a subset of a string. 746169691Skan * @param s A string of '0' and '1' characters. 747169691Skan * @param position Index of the first character in @a s to use; 748169691Skan * defaults to zero. 749169691Skan * @throw std::out_of_range If @a pos is bigger the size of @a s. 750169691Skan * @throw std::invalid_argument If a character appears in the string 751169691Skan * which is neither '0' nor '1'. 752169691Skan */ 753169691Skan template<class _CharT, class _Traits, class _Alloc> 754169691Skan explicit 755169691Skan bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 756169691Skan size_t __position = 0) 757169691Skan : _Base() 758169691Skan { 759169691Skan if (__position > __s.size()) 760169691Skan __throw_out_of_range(__N("bitset::bitset initial position " 761169691Skan "not valid")); 762169691Skan _M_copy_from_string(__s, __position, 763169691Skan std::basic_string<_CharT, _Traits, _Alloc>::npos); 764169691Skan } 765169691Skan 766169691Skan /** 767169691Skan * @brief Use a subset of a string. 768169691Skan * @param s A string of '0' and '1' characters. 769169691Skan * @param position Index of the first character in @a s to use. 770169691Skan * @param n The number of characters to copy. 771169691Skan * @throw std::out_of_range If @a pos is bigger the size of @a s. 772169691Skan * @throw std::invalid_argument If a character appears in the string 773169691Skan * which is neither '0' nor '1'. 774169691Skan */ 775169691Skan template<class _CharT, class _Traits, class _Alloc> 776169691Skan bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 777169691Skan size_t __position, size_t __n) 778169691Skan : _Base() 779169691Skan { 780169691Skan if (__position > __s.size()) 781169691Skan __throw_out_of_range(__N("bitset::bitset initial position " 782169691Skan "not valid")); 783169691Skan _M_copy_from_string(__s, __position, __n); 784169691Skan } 785169691Skan 786169691Skan // 23.3.5.2 bitset operations: 787169691Skan //@{ 788169691Skan /** 789169691Skan * @brief Operations on bitsets. 790169691Skan * @param rhs A same-sized bitset. 791169691Skan * 792169691Skan * These should be self-explanatory. 793169691Skan */ 794169691Skan bitset<_Nb>& 795169691Skan operator&=(const bitset<_Nb>& __rhs) 79697403Sobrien { 797169691Skan this->_M_do_and(__rhs); 798169691Skan return *this; 79997403Sobrien } 80097403Sobrien 801169691Skan bitset<_Nb>& 802169691Skan operator|=(const bitset<_Nb>& __rhs) 803169691Skan { 804169691Skan this->_M_do_or(__rhs); 805169691Skan return *this; 806169691Skan } 80797403Sobrien 808169691Skan bitset<_Nb>& 809169691Skan operator^=(const bitset<_Nb>& __rhs) 81097403Sobrien { 811169691Skan this->_M_do_xor(__rhs); 812169691Skan return *this; 813169691Skan } 814169691Skan //@} 815169691Skan 816169691Skan //@{ 817169691Skan /** 818169691Skan * @brief Operations on bitsets. 819169691Skan * @param position The number of places to shift. 820169691Skan * 821169691Skan * These should be self-explanatory. 822169691Skan */ 823169691Skan bitset<_Nb>& 824169691Skan operator<<=(size_t __position) 825169691Skan { 826169691Skan if (__builtin_expect(__position < _Nb, 1)) 827169691Skan { 828169691Skan this->_M_do_left_shift(__position); 829169691Skan this->_M_do_sanitize(); 830169691Skan } 83197403Sobrien else 832169691Skan this->_M_do_reset(); 83397403Sobrien return *this; 83497403Sobrien } 83597403Sobrien 836169691Skan bitset<_Nb>& 837169691Skan operator>>=(size_t __position) 83897403Sobrien { 839169691Skan if (__builtin_expect(__position < _Nb, 1)) 840169691Skan { 841169691Skan this->_M_do_right_shift(__position); 842169691Skan this->_M_do_sanitize(); 843169691Skan } 84497403Sobrien else 845169691Skan this->_M_do_reset(); 84697403Sobrien return *this; 84797403Sobrien } 848169691Skan //@} 849169691Skan 850169691Skan //@{ 851169691Skan /** 852169691Skan * These versions of single-bit set, reset, flip, and test are 853169691Skan * extensions from the SGI version. They do no range checking. 854169691Skan * @ingroup SGIextensions 855169691Skan */ 856169691Skan bitset<_Nb>& 857169691Skan _Unchecked_set(size_t __pos) 858169691Skan { 859169691Skan this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 860169691Skan return *this; 861169691Skan } 86297403Sobrien 863169691Skan bitset<_Nb>& 864169691Skan _Unchecked_set(size_t __pos, int __val) 865169691Skan { 866169691Skan if (__val) 867169691Skan this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 868169691Skan else 869169691Skan this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 870169691Skan return *this; 871169691Skan } 87297403Sobrien 873169691Skan bitset<_Nb>& 874169691Skan _Unchecked_reset(size_t __pos) 875169691Skan { 876169691Skan this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 877169691Skan return *this; 878169691Skan } 87997403Sobrien 880169691Skan bitset<_Nb>& 881169691Skan _Unchecked_flip(size_t __pos) 88297403Sobrien { 883169691Skan this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 88497403Sobrien return *this; 88597403Sobrien } 88697403Sobrien 887169691Skan bool 888169691Skan _Unchecked_test(size_t __pos) const 889169691Skan { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 890169691Skan != static_cast<_WordT>(0)); } 891169691Skan //@} 892169691Skan 893169691Skan // Set, reset, and flip. 894169691Skan /** 895169691Skan * @brief Sets every bit to true. 896169691Skan */ 897169691Skan bitset<_Nb>& 898169691Skan set() 89997403Sobrien { 900169691Skan this->_M_do_set(); 901169691Skan this->_M_do_sanitize(); 902169691Skan return *this; 90397403Sobrien } 90497403Sobrien 905169691Skan /** 906169691Skan * @brief Sets a given bit to a particular value. 907169691Skan * @param position The index of the bit. 908169691Skan * @param val Either true or false, defaults to true. 909169691Skan * @throw std::out_of_range If @a pos is bigger the size of the %set. 910169691Skan */ 911169691Skan bitset<_Nb>& 912169691Skan set(size_t __position, bool __val = true) 91397403Sobrien { 914169691Skan if (__position >= _Nb) 915169691Skan __throw_out_of_range(__N("bitset::set")); 916169691Skan return _Unchecked_set(__position, __val); 91797403Sobrien } 91897403Sobrien 919169691Skan /** 920169691Skan * @brief Sets every bit to false. 921169691Skan */ 922169691Skan bitset<_Nb>& 923169691Skan reset() 924169691Skan { 925117397Skan this->_M_do_reset(); 926169691Skan return *this; 927169691Skan } 92897403Sobrien 929169691Skan /** 930169691Skan * @brief Sets a given bit to false. 931169691Skan * @param position The index of the bit. 932169691Skan * @throw std::out_of_range If @a pos is bigger the size of the %set. 933169691Skan * 934169691Skan * Same as writing @c set(pos,false). 935169691Skan */ 936169691Skan bitset<_Nb>& 937169691Skan reset(size_t __position) 938169691Skan { 939169691Skan if (__position >= _Nb) 940169691Skan __throw_out_of_range(__N("bitset::reset")); 941169691Skan return _Unchecked_reset(__position); 942169691Skan } 943169691Skan 944169691Skan /** 945169691Skan * @brief Toggles every bit to its opposite value. 946169691Skan */ 947169691Skan bitset<_Nb>& 948169691Skan flip() 949169691Skan { 950169691Skan this->_M_do_flip(); 951169691Skan this->_M_do_sanitize(); 952169691Skan return *this; 953169691Skan } 95497403Sobrien 955169691Skan /** 956169691Skan * @brief Toggles a given bit to its opposite value. 957169691Skan * @param position The index of the bit. 958169691Skan * @throw std::out_of_range If @a pos is bigger the size of the %set. 959169691Skan */ 960169691Skan bitset<_Nb>& 961169691Skan flip(size_t __position) 962169691Skan { 963169691Skan if (__position >= _Nb) 964169691Skan __throw_out_of_range(__N("bitset::flip")); 965169691Skan return _Unchecked_flip(__position); 966169691Skan } 967169691Skan 968169691Skan /// See the no-argument flip(). 969169691Skan bitset<_Nb> 970169691Skan operator~() const 971169691Skan { return bitset<_Nb>(*this).flip(); } 97297403Sobrien 973169691Skan //@{ 974169691Skan /** 975169691Skan * @brief Array-indexing support. 976169691Skan * @param position Index into the %bitset. 977169691Skan * @return A bool for a 'const %bitset'. For non-const bitsets, an 978169691Skan * instance of the reference proxy class. 979169691Skan * @note These operators do no range checking and throw no exceptions, 980169691Skan * as required by DR 11 to the standard. 981169691Skan * 982169691Skan * @if maint 983169691Skan * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already 984169691Skan * resolves DR 11 (items 1 and 2), but does not do the range-checking 985169691Skan * required by that DR's resolution. -pme 986169691Skan * The DR has since been changed: range-checking is a precondition 987169691Skan * (users' responsibility), and these functions must not throw. -pme 988169691Skan * @endif 989169691Skan */ 990169691Skan reference 991169691Skan operator[](size_t __position) 992169691Skan { return reference(*this,__position); } 99397403Sobrien 994169691Skan bool 995169691Skan operator[](size_t __position) const 996169691Skan { return _Unchecked_test(__position); } 997169691Skan //@} 998169691Skan 999169691Skan /** 1000169691Skan * @brief Retuns a numerical interpretation of the %bitset. 1001169691Skan * @return The integral equivalent of the bits. 1002169691Skan * @throw std::overflow_error If there are too many bits to be 1003169691Skan * represented in an @c unsigned @c long. 1004169691Skan */ 1005169691Skan unsigned long 1006169691Skan to_ulong() const 1007169691Skan { return this->_M_do_to_ulong(); } 100897403Sobrien 1009169691Skan /** 1010169691Skan * @brief Retuns a character interpretation of the %bitset. 1011169691Skan * @return The string equivalent of the bits. 1012169691Skan * 1013169691Skan * Note the ordering of the bits: decreasing character positions 1014169691Skan * correspond to increasing bit positions (see the main class notes for 1015169691Skan * an example). 1016169691Skan */ 1017169691Skan template<class _CharT, class _Traits, class _Alloc> 1018169691Skan std::basic_string<_CharT, _Traits, _Alloc> 1019169691Skan to_string() const 1020169691Skan { 1021169691Skan std::basic_string<_CharT, _Traits, _Alloc> __result; 1022169691Skan _M_copy_to_string(__result); 1023169691Skan return __result; 1024169691Skan } 102597403Sobrien 1026169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 1027169691Skan // 434. bitset::to_string() hard to use. 1028169691Skan template<class _CharT, class _Traits> 1029169691Skan std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 1030169691Skan to_string() const 1031169691Skan { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); } 103297403Sobrien 1033169691Skan template<class _CharT> 1034169691Skan std::basic_string<_CharT, std::char_traits<_CharT>, 1035169691Skan std::allocator<_CharT> > 1036169691Skan to_string() const 1037169691Skan { 1038169691Skan return to_string<_CharT, std::char_traits<_CharT>, 1039169691Skan std::allocator<_CharT> >(); 1040169691Skan } 104197403Sobrien 1042169691Skan std::basic_string<char, std::char_traits<char>, std::allocator<char> > 104397403Sobrien to_string() const 104497403Sobrien { 1045169691Skan return to_string<char, std::char_traits<char>, 1046169691Skan std::allocator<char> >(); 104797403Sobrien } 104897403Sobrien 1049169691Skan // Helper functions for string operations. 1050169691Skan template<class _CharT, class _Traits, class _Alloc> 1051169691Skan void 1052169691Skan _M_copy_from_string(const std::basic_string<_CharT, 1053169691Skan _Traits, _Alloc>& __s, 1054169691Skan size_t, size_t); 105597403Sobrien 1056169691Skan template<class _CharT, class _Traits, class _Alloc> 1057169691Skan void 1058169691Skan _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&) const; 105997403Sobrien 1060169691Skan /// Returns the number of bits which are set. 1061169691Skan size_t 1062169691Skan count() const 1063169691Skan { return this->_M_do_count(); } 106497403Sobrien 1065169691Skan /// Returns the total number of bits. 1066169691Skan size_t 1067169691Skan size() const 1068169691Skan { return _Nb; } 106997403Sobrien 1070169691Skan //@{ 1071169691Skan /// These comparisons for equality/inequality are, well, @e bitwise. 1072169691Skan bool 1073169691Skan operator==(const bitset<_Nb>& __rhs) const 1074169691Skan { return this->_M_is_equal(__rhs); } 107597403Sobrien 1076169691Skan bool 1077169691Skan operator!=(const bitset<_Nb>& __rhs) const 1078169691Skan { return !this->_M_is_equal(__rhs); } 1079169691Skan //@} 1080169691Skan 1081169691Skan /** 1082169691Skan * @brief Tests the value of a bit. 1083169691Skan * @param position The index of a bit. 1084169691Skan * @return The value at @a pos. 1085169691Skan * @throw std::out_of_range If @a pos is bigger the size of the %set. 1086169691Skan */ 1087169691Skan bool 1088169691Skan test(size_t __position) const 1089169691Skan { 1090169691Skan if (__position >= _Nb) 1091169691Skan __throw_out_of_range(__N("bitset::test")); 1092169691Skan return _Unchecked_test(__position); 1093169691Skan } 1094169691Skan 1095169691Skan /** 1096169691Skan * @brief Tests whether any of the bits are on. 1097169691Skan * @return True if at least one bit is set. 1098169691Skan */ 1099169691Skan bool 1100169691Skan any() const 1101169691Skan { return this->_M_is_any(); } 110297403Sobrien 1103169691Skan /** 1104169691Skan * @brief Tests whether any of the bits are on. 1105169691Skan * @return True if none of the bits are set. 1106169691Skan */ 1107169691Skan bool 1108169691Skan none() const 1109169691Skan { return !this->_M_is_any(); } 111097403Sobrien 1111169691Skan //@{ 1112169691Skan /// Self-explanatory. 1113169691Skan bitset<_Nb> 1114169691Skan operator<<(size_t __position) const 1115169691Skan { return bitset<_Nb>(*this) <<= __position; } 111697403Sobrien 1117169691Skan bitset<_Nb> 1118169691Skan operator>>(size_t __position) const 1119169691Skan { return bitset<_Nb>(*this) >>= __position; } 1120169691Skan //@} 1121169691Skan 1122169691Skan /** 1123169691Skan * @brief Finds the index of the first "on" bit. 1124169691Skan * @return The index of the first bit set, or size() if not found. 1125169691Skan * @ingroup SGIextensions 1126169691Skan * @sa _Find_next 1127169691Skan */ 1128169691Skan size_t 1129169691Skan _Find_first() const 1130169691Skan { return this->_M_do_find_first(_Nb); } 113197403Sobrien 1132169691Skan /** 1133169691Skan * @brief Finds the index of the next "on" bit after prev. 1134169691Skan * @return The index of the next bit set, or size() if not found. 1135169691Skan * @param prev Where to start searching. 1136169691Skan * @ingroup SGIextensions 1137169691Skan * @sa _Find_first 1138169691Skan */ 1139169691Skan size_t 1140169691Skan _Find_next(size_t __prev ) const 1141169691Skan { return this->_M_do_find_next(__prev, _Nb); } 1142169691Skan }; 114397403Sobrien 114497403Sobrien // Definitions of non-inline member functions. 114597403Sobrien template<size_t _Nb> 114697403Sobrien template<class _CharT, class _Traits, class _Alloc> 1147169691Skan void 1148169691Skan bitset<_Nb>:: 1149169691Skan _M_copy_from_string(const std::basic_string<_CharT, _Traits, 1150169691Skan _Alloc>& __s, size_t __pos, size_t __n) 1151169691Skan { 1152169691Skan reset(); 1153169691Skan const size_t __nbits = std::min(_Nb, std::min(__n, __s.size() - __pos)); 1154169691Skan for (size_t __i = __nbits; __i > 0; --__i) 1155169691Skan { 1156169691Skan switch(__s[__pos + __nbits - __i]) 1157169691Skan { 1158169691Skan case '0': 1159169691Skan break; 1160169691Skan case '1': 1161169691Skan _Unchecked_set(__i - 1); 1162169691Skan break; 1163169691Skan default: 1164169691Skan __throw_invalid_argument(__N("bitset::_M_copy_from_string")); 1165169691Skan } 1166169691Skan } 1167169691Skan } 116897403Sobrien 116997403Sobrien template<size_t _Nb> 117097403Sobrien template<class _CharT, class _Traits, class _Alloc> 1171169691Skan void 1172169691Skan bitset<_Nb>:: 1173169691Skan _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s) const 1174169691Skan { 1175169691Skan __s.assign(_Nb, '0'); 1176169691Skan for (size_t __i = _Nb; __i > 0; --__i) 1177169691Skan if (_Unchecked_test(__i - 1)) 1178169691Skan __s[_Nb - __i] = '1'; 1179169691Skan } 118097403Sobrien 118197403Sobrien // 23.3.5.3 bitset operations: 118297403Sobrien //@{ 118397403Sobrien /** 118497403Sobrien * @brief Global bitwise operations on bitsets. 118597403Sobrien * @param x A bitset. 118697403Sobrien * @param y A bitset of the same size as @a x. 118797403Sobrien * @return A new bitset. 118897403Sobrien * 118997403Sobrien * These should be self-explanatory. 119097403Sobrien */ 119197403Sobrien template<size_t _Nb> 119297403Sobrien inline bitset<_Nb> 119397403Sobrien operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 119497403Sobrien { 119597403Sobrien bitset<_Nb> __result(__x); 119697403Sobrien __result &= __y; 119797403Sobrien return __result; 119897403Sobrien } 119997403Sobrien 120097403Sobrien template<size_t _Nb> 120197403Sobrien inline bitset<_Nb> 120297403Sobrien operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 120397403Sobrien { 120497403Sobrien bitset<_Nb> __result(__x); 120597403Sobrien __result |= __y; 120697403Sobrien return __result; 120797403Sobrien } 120897403Sobrien 120997403Sobrien template <size_t _Nb> 121097403Sobrien inline bitset<_Nb> 121197403Sobrien operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 121297403Sobrien { 121397403Sobrien bitset<_Nb> __result(__x); 121497403Sobrien __result ^= __y; 121597403Sobrien return __result; 121697403Sobrien } 121797403Sobrien //@} 121897403Sobrien 121997403Sobrien //@{ 122097403Sobrien /** 122197403Sobrien * @brief Global I/O operators for bitsets. 122297403Sobrien * 122397403Sobrien * Direct I/O between streams and bitsets is supported. Output is 122497403Sobrien * straightforward. Input will skip whitespace, only accept '0' and '1' 122597403Sobrien * characters, and will only extract as many digits as the %bitset will 122697403Sobrien * hold. 122797403Sobrien */ 122897403Sobrien template<class _CharT, class _Traits, size_t _Nb> 1229169691Skan std::basic_istream<_CharT, _Traits>& 1230169691Skan operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 123197403Sobrien { 123297403Sobrien typedef typename _Traits::char_type char_type; 1233169691Skan std::basic_string<_CharT, _Traits> __tmp; 123497403Sobrien __tmp.reserve(_Nb); 123597403Sobrien 1236169691Skan std::ios_base::iostate __state = std::ios_base::goodbit; 1237169691Skan typename std::basic_istream<_CharT, _Traits>::sentry __sentry(__is); 123897403Sobrien if (__sentry) 123997403Sobrien { 1240132720Skan try 124197403Sobrien { 1242132720Skan basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf(); 1243132720Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 1244132720Skan // 303. Bitset input operator underspecified 1245132720Skan const char_type __zero = __is.widen('0'); 1246132720Skan const char_type __one = __is.widen('1'); 1247169691Skan for (size_t __i = _Nb; __i > 0; --__i) 124897403Sobrien { 1249132720Skan static typename _Traits::int_type __eof = _Traits::eof(); 1250132720Skan 1251132720Skan typename _Traits::int_type __c1 = __buf->sbumpc(); 1252132720Skan if (_Traits::eq_int_type(__c1, __eof)) 125397403Sobrien { 1254169691Skan __state |= std::ios_base::eofbit; 125597403Sobrien break; 125697403Sobrien } 1257132720Skan else 1258132720Skan { 1259169691Skan const char_type __c2 = _Traits::to_char_type(__c1); 1260132720Skan if (__c2 == __zero) 1261132720Skan __tmp.push_back('0'); 1262132720Skan else if (__c2 == __one) 1263132720Skan __tmp.push_back('1'); 1264132720Skan else if (_Traits::eq_int_type(__buf->sputbackc(__c2), 1265132720Skan __eof)) 1266132720Skan { 1267169691Skan __state |= std::ios_base::failbit; 1268132720Skan break; 1269132720Skan } 1270132720Skan } 127197403Sobrien } 127297403Sobrien } 1273132720Skan catch(...) 1274169691Skan { __is._M_setstate(std::ios_base::badbit); } 127597403Sobrien } 127697403Sobrien 1277132720Skan if (__tmp.empty() && _Nb) 1278169691Skan __state |= std::ios_base::failbit; 1279132720Skan else 1280132720Skan __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); 1281132720Skan if (__state) 1282132720Skan __is.setstate(__state); 128397403Sobrien return __is; 128497403Sobrien } 128597403Sobrien 128697403Sobrien template <class _CharT, class _Traits, size_t _Nb> 1287169691Skan std::basic_ostream<_CharT, _Traits>& 1288169691Skan operator<<(std::basic_ostream<_CharT, _Traits>& __os, 1289169691Skan const bitset<_Nb>& __x) 129097403Sobrien { 1291169691Skan std::basic_string<_CharT, _Traits> __tmp; 129297403Sobrien __x._M_copy_to_string(__tmp); 129397403Sobrien return __os << __tmp; 129497403Sobrien } 1295169691Skan 1296169691Skan // Specializations for zero-sized bitsets, to avoid "unsigned comparison 1297169691Skan // with zero" warnings. 1298169691Skan template<> 1299169691Skan inline bitset<0>& 1300169691Skan bitset<0>:: 1301169691Skan set(size_t, bool) 1302169691Skan { 1303169691Skan __throw_out_of_range(__N("bitset::set")); 1304169691Skan return *this; 1305169691Skan } 1306169691Skan 1307169691Skan template<> 1308169691Skan inline bitset<0>& 1309169691Skan bitset<0>:: 1310169691Skan reset(size_t) 1311169691Skan { 1312169691Skan __throw_out_of_range(__N("bitset::reset")); 1313169691Skan return *this; 1314169691Skan } 1315169691Skan 1316169691Skan template<> 1317169691Skan inline bitset<0>& 1318169691Skan bitset<0>:: 1319169691Skan flip(size_t) 1320169691Skan { 1321169691Skan __throw_out_of_range(__N("bitset::flip")); 1322169691Skan return *this; 1323169691Skan } 1324169691Skan 1325169691Skan template<> 1326169691Skan inline bool 1327169691Skan bitset<0>:: 1328169691Skan test(size_t) const 1329169691Skan { 1330169691Skan __throw_out_of_range(__N("bitset::test")); 1331169691Skan return false; 1332169691Skan } 133397403Sobrien //@} 133497403Sobrien 1335169691Skan_GLIBCXX_END_NESTED_NAMESPACE 1336169691Skan 1337132720Skan#undef _GLIBCXX_BITSET_WORDS 1338132720Skan#undef _GLIBCXX_BITSET_BITS_PER_WORD 133997403Sobrien 1340132720Skan#ifdef _GLIBCXX_DEBUG 1341132720Skan# include <debug/bitset> 1342132720Skan#endif 1343132720Skan 1344132720Skan#endif /* _GLIBCXX_BITSET */ 1345