libstdc++
dynamic_bitset.tcc
Go to the documentation of this file.
00001 // TR2 <dynamic_bitset> -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2014 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file tr2/dynamic_bitset.tcc
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly. @headername{tr2/dynamic_bitset}
00028  */
00029 
00030 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET_TCC
00031 #define _GLIBCXX_TR2_DYNAMIC_BITSET_TCC 1
00032 
00033 #pragma GCC system_header
00034 
00035 namespace std _GLIBCXX_VISIBILITY(default)
00036 {
00037 namespace tr2
00038 {
00039 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00040 
00041   // Definitions of non-inline functions from __dynamic_bitset_base.
00042   template<typename _WordT, typename _Alloc>
00043     void
00044     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
00045     {
00046       if (__builtin_expect(__shift != 0, 1))
00047     {
00048       const size_t __wshift = __shift / _S_bits_per_block;
00049       const size_t __offset = __shift % _S_bits_per_block;
00050 
00051       if (__offset == 0)
00052         for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
00053           this->_M_w[__n] = this->_M_w[__n - __wshift];
00054       else
00055         {
00056           const size_t __sub_offset = _S_bits_per_block - __offset;
00057           for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
00058         this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
00059                  | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
00060           this->_M_w[__wshift] = this->_M_w[0] << __offset;
00061         }
00062 
00063       //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift,
00064       ////          static_cast<_WordT>(0));
00065     }
00066     }
00067 
00068   template<typename _WordT, typename _Alloc>
00069     void
00070     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
00071     {
00072       if (__builtin_expect(__shift != 0, 1))
00073     {
00074       const size_t __wshift = __shift / _S_bits_per_block;
00075       const size_t __offset = __shift % _S_bits_per_block;
00076       const size_t __limit = this->_M_w.size() - __wshift - 1;
00077 
00078       if (__offset == 0)
00079         for (size_t __n = 0; __n <= __limit; ++__n)
00080           this->_M_w[__n] = this->_M_w[__n + __wshift];
00081       else
00082         {
00083           const size_t __sub_offset = (_S_bits_per_block
00084                        - __offset);
00085           for (size_t __n = 0; __n < __limit; ++__n)
00086         this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
00087                  | (this->_M_w[__n + __wshift + 1] << __sub_offset));
00088           this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
00089         }
00090 
00091       ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(),
00092       ////          static_cast<_WordT>(0));
00093     }
00094     }
00095 
00096   template<typename _WordT, typename _Alloc>
00097     unsigned long
00098     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
00099     {
00100       size_t __n = sizeof(unsigned long) / sizeof(block_type);
00101       for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
00102     if (this->_M_w[__i])
00103       __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
00104       unsigned long __res = 0UL;
00105       for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
00106     __res += this->_M_w[__i] << (__i * _S_bits_per_block);
00107       return __res;
00108     }
00109 
00110   template<typename _WordT, typename _Alloc>
00111     unsigned long long
00112     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
00113     {
00114       size_t __n = sizeof(unsigned long long) / sizeof(block_type);
00115       for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
00116     if (this->_M_w[__i])
00117       __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
00118       unsigned long long __res = 0ULL;
00119       for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
00120     __res += this->_M_w[__i] << (__i * _S_bits_per_block);
00121       return __res;
00122     }
00123 
00124   template<typename _WordT, typename _Alloc>
00125     size_t
00126     __dynamic_bitset_base<_WordT, _Alloc>
00127     ::_M_do_find_first(size_t __not_found) const
00128     {
00129       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00130     {
00131       _WordT __thisword = this->_M_w[__i];
00132       if (__thisword != static_cast<_WordT>(0))
00133         return (__i * _S_bits_per_block
00134             + __builtin_ctzll(__thisword));
00135     }
00136       // not found, so return an indication of failure.
00137       return __not_found;
00138     }
00139 
00140   template<typename _WordT, typename _Alloc>
00141     size_t
00142     __dynamic_bitset_base<_WordT, _Alloc>
00143     ::_M_do_find_next(size_t __prev, size_t __not_found) const
00144     {
00145       // make bound inclusive
00146       ++__prev;
00147 
00148       // check out of bounds
00149       if (__prev >= this->_M_w.size() * _S_bits_per_block)
00150     return __not_found;
00151 
00152       // search first word
00153       size_t __i = _S_whichword(__prev);
00154       _WordT __thisword = this->_M_w[__i];
00155 
00156       // mask off bits below bound
00157       __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
00158 
00159       if (__thisword != static_cast<_WordT>(0))
00160     return (__i * _S_bits_per_block
00161         + __builtin_ctzll(__thisword));
00162 
00163       // check subsequent words
00164       for (++__i; __i < this->_M_w.size(); ++__i)
00165     {
00166       __thisword = this->_M_w[__i];
00167       if (__thisword != static_cast<_WordT>(0))
00168         return (__i * _S_bits_per_block
00169             + __builtin_ctzll(__thisword));
00170     }
00171       // not found, so return an indication of failure.
00172       return __not_found;
00173     } // end _M_do_find_next
00174 
00175   // Definitions of non-inline member functions.
00176   template<typename _WordT, typename _Alloc>
00177     template<typename _CharT, typename _Traits>
00178       void
00179       dynamic_bitset<_WordT, _Alloc>::
00180       _M_copy_from_ptr(const _CharT* __str, size_t __len,
00181                size_t __pos, size_t __n, _CharT __zero, _CharT __one)
00182       {
00183     reset();
00184     const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos));
00185     for (size_t __i = __nbits; __i > 0; --__i)
00186       {
00187         const _CharT __c = __str[__pos + __nbits - __i];
00188         if (_Traits::eq(__c, __zero))
00189           ;
00190         else if (_Traits::eq(__c, __one))
00191           _M_unchecked_set(__i - 1);
00192         else
00193           __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr"));
00194       }
00195       }
00196 
00197   /**
00198    *  @defgroup Global I/O operators for bitsets.
00199    *  @{
00200    *  @brief Global I/O operators for bitsets.
00201    *
00202    *  Direct I/O between streams and bitsets is supported.  Output is
00203    *  straightforward.  Input will skip whitespace and only accept '0'
00204    *  and '1' characters.  The %dynamic_bitset will grow as necessary
00205    *  to hold the string of bits.
00206    */
00207   template<typename _CharT, typename _Traits,
00208        typename _WordT, typename _Alloc>
00209     std::basic_istream<_CharT, _Traits>&
00210     operator>>(std::basic_istream<_CharT, _Traits>& __is,
00211            dynamic_bitset<_WordT, _Alloc>& __x)
00212     {
00213       typedef typename _Traits::char_type          char_type;
00214       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
00215       typedef typename __istream_type::ios_base    __ios_base;
00216 
00217       std::basic_string<_CharT, _Traits> __tmp;
00218       __tmp.reserve(__x.size());
00219 
00220       const char_type __zero = __is.widen('0');
00221       const char_type __one = __is.widen('1');
00222 
00223       typename __ios_base::iostate __state = __ios_base::goodbit;
00224       typename __istream_type::sentry __sentry(__is);
00225       if (__sentry)
00226     {
00227       __try
00228         {
00229           while (1)
00230         {
00231           static typename _Traits::int_type __eof = _Traits::eof();
00232 
00233           typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
00234           if (_Traits::eq_int_type(__c1, __eof))
00235             {
00236               __state |= __ios_base::eofbit;
00237               break;
00238             }
00239           else
00240             {
00241               const char_type __c2 = _Traits::to_char_type(__c1);
00242               if (_Traits::eq(__c2, __zero))
00243             __tmp.push_back(__zero);
00244               else if (_Traits::eq(__c2, __one))
00245             __tmp.push_back(__one);
00246               else if (_Traits::
00247                    eq_int_type(__is.rdbuf()->sputbackc(__c2),
00248                        __eof))
00249             {
00250               __state |= __ios_base::failbit;
00251               break;
00252             }
00253               else
00254             break;
00255             }
00256         }
00257         }
00258       __catch(__cxxabiv1::__forced_unwind&)
00259         {
00260           __is._M_setstate(__ios_base::badbit);
00261           __throw_exception_again;
00262         }
00263       __catch(...)
00264         { __is._M_setstate(__ios_base::badbit); }
00265     }
00266 
00267       __x.resize(__tmp.size());
00268 
00269       if (__tmp.empty() && __x.size())
00270     __state |= __ios_base::failbit;
00271       else
00272     __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),
00273                 __zero, __one);
00274       if (__state)
00275     __is.setstate(__state);
00276       return __is;
00277     }
00278   /**
00279    *  @}
00280    */
00281 
00282 _GLIBCXX_END_NAMESPACE_VERSION
00283 } // tr2
00284 } // std
00285 
00286 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */