libstdc++-v3/include/tr2/dynamic_bitset.tcc

   1 // TR2 <dynamic_bitset> -*- C++ -*-
   2
   3 // Copyright (C) 2009-2013 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file tr2/dynamic_bitset.tcc
  26  *  This is an internal header file, included by other library headers.
  27  *  Do not attempt to use it directly. @headername{tr2/dynamic_bitset}
  28  */
  29
  30 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET_TCC
  31 #define _GLIBCXX_TR2_DYNAMIC_BITSET_TCC 1
  32
  33 #pragma GCC system_header
  34
  35 namespace std _GLIBCXX_VISIBILITY(default)
  36 {
  37 namespace tr2
  38 {
  39 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  40
  41   // Definitions of non-inline functions from __dynamic_bitset_base.
  42   template<typename _WordT, typename _Alloc>
  43     void
  44     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
  45     {
  46       if (__builtin_expect(__shift != 0, 1))
  47         {
  48           const size_t __wshift = __shift / _S_bits_per_block;
  49           const size_t __offset = __shift % _S_bits_per_block;
  50
  51           if (__offset == 0)
  52             for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
  53               this->_M_w[__n] = this->_M_w[__n - __wshift];
  54           else
  55             {
  56               const size_t __sub_offset = _S_bits_per_block - __offset;
  57               for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
  58                 this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
  59                              | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
  60               this->_M_w[__wshift] = this->_M_w[0] << __offset;
  61             }
  62
  63           //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift,
  64           ////          static_cast<_WordT>(0));
  65         }
  66     }
  67
  68   template<typename _WordT, typename _Alloc>
  69     void
  70     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
  71     {
  72       if (__builtin_expect(__shift != 0, 1))
  73         {
  74           const size_t __wshift = __shift / _S_bits_per_block;
  75           const size_t __offset = __shift % _S_bits_per_block;
  76           const size_t __limit = this->_M_w.size() - __wshift - 1;
  77
  78           if (__offset == 0)
  79             for (size_t __n = 0; __n <= __limit; ++__n)
  80               this->_M_w[__n] = this->_M_w[__n + __wshift];
  81           else
  82             {
  83               const size_t __sub_offset = (_S_bits_per_block
  84                                            - __offset);
  85               for (size_t __n = 0; __n < __limit; ++__n)
  86                 this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
  87                              | (this->_M_w[__n + __wshift + 1] << __sub_offset));
  88               this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
  89             }
  90
  91           ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(),
  92           ////          static_cast<_WordT>(0));
  93         }
  94     }
  95
  96   template<typename _WordT, typename _Alloc>
  97     unsigned long
  98     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
  99     {
 100       size_t __n = sizeof(unsigned long) / sizeof(block_type);
 101       for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
 102         if (this->_M_w[__i])
 103           __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
 104       unsigned long __res = 0UL;
 105       for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
 106         __res += this->_M_w[__i] << (__i * _S_bits_per_block);
 107       return __res;
 108     }
 109
 110   template<typename _WordT, typename _Alloc>
 111     unsigned long long
 112     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
 113     {
 114       size_t __n = sizeof(unsigned long long) / sizeof(block_type);
 115       for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
 116         if (this->_M_w[__i])
 117           __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
 118       unsigned long long __res = 0ULL;
 119       for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
 120         __res += this->_M_w[__i] << (__i * _S_bits_per_block);
 121       return __res;
 122     }
 123
 124   template<typename _WordT, typename _Alloc>
 125     size_t
 126     __dynamic_bitset_base<_WordT, _Alloc>
 127     ::_M_do_find_first(size_t __not_found) const
 128     {
 129       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
 130         {
 131           _WordT __thisword = this->_M_w[__i];
 132           if (__thisword != static_cast<_WordT>(0))
 133             return (__i * _S_bits_per_block
 134                     + __builtin_ctzll(__thisword));
 135         }
 136       // not found, so return an indication of failure.
 137       return __not_found;
 138     }
 139
 140   template<typename _WordT, typename _Alloc>
 141     size_t
 142     __dynamic_bitset_base<_WordT, _Alloc>
 143     ::_M_do_find_next(size_t __prev, size_t __not_found) const
 144     {
 145       // make bound inclusive
 146       ++__prev;
 147
 148       // check out of bounds
 149       if (__prev >= this->_M_w.size() * _S_bits_per_block)
 150         return __not_found;
 151
 152       // search first word
 153       size_t __i = _S_whichword(__prev);
 154       _WordT __thisword = this->_M_w[__i];
 155
 156       // mask off bits below bound
 157       __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
 158
 159       if (__thisword != static_cast<_WordT>(0))
 160         return (__i * _S_bits_per_block
 161                 + __builtin_ctzll(__thisword));
 162
 163       // check subsequent words
 164       for (++__i; __i < this->_M_w.size(); ++__i)
 165         {
 166           __thisword = this->_M_w[__i];
 167           if (__thisword != static_cast<_WordT>(0))
 168             return (__i * _S_bits_per_block
 169                     + __builtin_ctzll(__thisword));
 170         }
 171       // not found, so return an indication of failure.
 172       return __not_found;
 173     } // end _M_do_find_next
 174
 175   // Definitions of non-inline member functions.
 176   template<typename _WordT, typename _Alloc>
 177     template<typename _CharT, typename _Traits>
 178       void
 179       dynamic_bitset<_WordT, _Alloc>::
 180       _M_copy_from_ptr(const _CharT* __str, size_t __len,
 181                        size_t __pos, size_t __n, _CharT __zero, _CharT __one)
 182       {
 183         reset();
 184         const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos));
 185         for (size_t __i = __nbits; __i > 0; --__i)
 186           {
 187             const _CharT __c = __str[__pos + __nbits - __i];
 188             if (_Traits::eq(__c, __zero))
 189               ;
 190             else if (_Traits::eq(__c, __one))
 191               _M_unchecked_set(__i - 1);
 192             else
 193               __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr"));
 194           }
 195       }
 196
 197   /**
 198    *  @defgroup Global I/O operators for bitsets.
 199    *  @{
 200    *  @brief Global I/O operators for bitsets.
 201    *
 202    *  Direct I/O between streams and bitsets is supported.  Output is
 203    *  straightforward.  Input will skip whitespace and only accept '0'
 204    *  and '1' characters.  The %dynamic_bitset will grow as necessary
 205    *  to hold the string of bits.
 206    */
 207   template<typename _CharT, typename _Traits,
 208            typename _WordT, typename _Alloc>
 209     std::basic_istream<_CharT, _Traits>&
 210     operator>>(std::basic_istream<_CharT, _Traits>& __is,
 211                dynamic_bitset<_WordT, _Alloc>& __x)
 212     {
 213       typedef typename _Traits::char_type          char_type;
 214       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
 215       typedef typename __istream_type::ios_base    __ios_base;
 216
 217       std::basic_string<_CharT, _Traits> __tmp;
 218       __tmp.reserve(__x.size());
 219
 220       const char_type __zero = __is.widen('0');
 221       const char_type __one = __is.widen('1');
 222
 223       typename __ios_base::iostate __state = __ios_base::goodbit;
 224       typename __istream_type::sentry __sentry(__is);
 225       if (__sentry)
 226         {
 227           __try
 228             {
 229               while (1)
 230                 {
 231                   static typename _Traits::int_type __eof = _Traits::eof();
 232
 233                   typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
 234                   if (_Traits::eq_int_type(__c1, __eof))
 235                     {
 236                       __state |= __ios_base::eofbit;
 237                       break;
 238                     }
 239                   else
 240                     {
 241                       const char_type __c2 = _Traits::to_char_type(__c1);
 242                       if (_Traits::eq(__c2, __zero))
 243                         __tmp.push_back(__zero);
 244                       else if (_Traits::eq(__c2, __one))
 245                         __tmp.push_back(__one);
 246                       else if (_Traits::
 247                                eq_int_type(__is.rdbuf()->sputbackc(__c2),
 248                                            __eof))
 249                         {
 250                           __state |= __ios_base::failbit;
 251                           break;
 252                         }
 253                       else
 254                         break;
 255                     }
 256                 }
 257             }
 258           __catch(__cxxabiv1::__forced_unwind&)
 259             {
 260               __is._M_setstate(__ios_base::badbit);
 261               __throw_exception_again;
 262             }
 263           __catch(...)
 264             { __is._M_setstate(__ios_base::badbit); }
 265         }
 266
 267       __x.resize(__tmp.size());
 268
 269       if (__tmp.empty() && __x.size())
 270         __state |= __ios_base::failbit;
 271       else
 272         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),
 273                                 __zero, __one);
 274       if (__state)
 275         __is.setstate(__state);
 276       return __is;
 277     }
 278   /**
 279    *  @}
 280    */
 281
 282 _GLIBCXX_END_NAMESPACE_VERSION
 283 } // tr2
 284 } // std
 285
 286 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */