1/*
2 * Copyright (c) 1998
3 * Silicon Graphics Computer Systems, Inc.
4 *
5 * Copyright (c) 1999
6 * Boris Fomitchev
7 *
8 * This material is provided "as is", with absolutely no warranty expressed
9 * or implied. Any use is at your own risk.
10 *
11 * Permission to use or copy this software for any purpose is hereby granted
12 * without fee, provided the above notices are retained on all copies.
13 * Permission to modify the code and to distribute modified code is granted,
14 * provided the above notices are retained, and a notice that the code was
15 * modified is included with the above copyright notice.
16 *
17 */
18
19#ifndef _STLP_BITSET_C
20#define _STLP_BITSET_C
21
22#ifndef _STLP_BITSET_H
23#  include <stl/_bitset.h>
24#endif
25
26#define __BITS_PER_WORD (CHAR_BIT * sizeof(unsigned long))
27
28_STLP_BEGIN_NAMESPACE
29
30_STLP_MOVE_TO_PRIV_NAMESPACE
31//
32// Definitions of non-inline functions from _Base_bitset.
33//
34template<size_t _Nw>
35void _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) {
36  if (__shift != 0) {
37    const size_t __wshift = __shift / __BITS_PER_WORD;
38    const size_t __offset = __shift % __BITS_PER_WORD;
39
40    if (__offset == 0)
41      for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
42        _M_w[__n] = _M_w[__n - __wshift];
43
44    else {
45      const size_t __sub_offset = __BITS_PER_WORD - __offset;
46      for (size_t __n = _Nw - 1; __n > __wshift; --__n)
47        _M_w[__n] = (_M_w[__n - __wshift] << __offset) |
48                    (_M_w[__n - __wshift - 1] >> __sub_offset);
49      _M_w[__wshift] = _M_w[0] << __offset;
50    }
51
52    fill(_M_w + 0, _M_w + __wshift, __STATIC_CAST(_WordT,0));
53  }
54}
55
56template<size_t _Nw>
57void _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) {
58  if (__shift != 0) {
59    const size_t __wshift = __shift / __BITS_PER_WORD;
60    const size_t __offset = __shift % __BITS_PER_WORD;
61    const size_t __limit = _Nw - __wshift - 1;
62
63    if (__offset == 0)
64      for (size_t __n = 0; __n <= __limit; ++__n)
65        _M_w[__n] = _M_w[__n + __wshift];
66
67    else {
68      const size_t __sub_offset = __BITS_PER_WORD - __offset;
69      for (size_t __n = 0; __n < __limit; ++__n)
70        _M_w[__n] = (_M_w[__n + __wshift] >> __offset) |
71                    (_M_w[__n + __wshift + 1] << __sub_offset);
72      _M_w[__limit] = _M_w[_Nw-1] >> __offset;
73    }
74
75    fill(_M_w + __limit + 1, _M_w + _Nw, __STATIC_CAST(_WordT,0));
76  }
77}
78
79template<size_t _Nw>
80unsigned long _Base_bitset<_Nw>::_M_do_to_ulong() const {
81  for (size_t __i = 1; __i < _Nw; ++__i)
82    if (_M_w[__i])
83      __stl_throw_overflow_error("bitset");
84  return _M_w[0];
85} // End _M_do_to_ulong
86
87template<size_t _Nw>
88size_t _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const {
89  for ( size_t __i = 0; __i < _Nw; __i++ ) {
90    _WordT __thisword = _M_w[__i];
91    if ( __thisword != __STATIC_CAST(_WordT,0) ) {
92      // find byte within word
93      for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) {
94        unsigned char __this_byte
95          = __STATIC_CAST(unsigned char,(__thisword & (~(unsigned char)0)));
96        if ( __this_byte )
97          return __i*__BITS_PER_WORD + __j*CHAR_BIT +
98            _Bs_G::_S_first_one(__this_byte);
99
100        __thisword >>= CHAR_BIT;
101      }
102    }
103  }
104  // not found, so return an indication of failure.
105  return __not_found;
106}
107
108template<size_t _Nw>
109size_t
110_Base_bitset<_Nw>::_M_do_find_next(size_t __prev,
111                                   size_t __not_found) const {
112  // make bound inclusive
113  ++__prev;
114
115  // check out of bounds
116  if ( __prev >= _Nw * __BITS_PER_WORD )
117    return __not_found;
118
119    // search first word
120  size_t __i = _S_whichword(__prev);
121  _WordT __thisword = _M_w[__i];
122
123    // mask off bits below bound
124  __thisword &= (~__STATIC_CAST(_WordT,0)) << _S_whichbit(__prev);
125
126  if ( __thisword != __STATIC_CAST(_WordT,0) ) {
127    // find byte within word
128    // get first byte into place
129    __thisword >>= _S_whichbyte(__prev) * CHAR_BIT;
130    for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); ++__j ) {
131      unsigned char __this_byte
132        = __STATIC_CAST(unsigned char,(__thisword & (~(unsigned char)0)));
133      if ( __this_byte )
134        return __i*__BITS_PER_WORD + __j*CHAR_BIT +
135          _Bs_G::_S_first_one(__this_byte);
136
137      __thisword >>= CHAR_BIT;
138    }
139  }
140
141  // check subsequent words
142  ++__i;
143  for ( ; __i < _Nw; ++__i ) {
144    /* _WordT */ __thisword = _M_w[__i];
145    if ( __thisword != __STATIC_CAST(_WordT,0) ) {
146      // find byte within word
147      for ( size_t __j = 0; __j < sizeof(_WordT); ++__j ) {
148        unsigned char __this_byte
149          = __STATIC_CAST(unsigned char,(__thisword & (~(unsigned char)0)));
150        if ( __this_byte )
151          return __i*__BITS_PER_WORD + __j*CHAR_BIT +
152            _Bs_G::_S_first_one(__this_byte);
153
154        __thisword >>= CHAR_BIT;
155      }
156    }
157  }
158
159  // not found, so return an indication of failure.
160  return __not_found;
161} // end _M_do_find_next
162
163_STLP_MOVE_TO_STD_NAMESPACE
164
165#if !defined (_STLP_NON_TYPE_TMPL_PARAM_BUG)
166
167#  if !defined (_STLP_USE_NO_IOSTREAMS)
168
169_STLP_END_NAMESPACE
170
171#ifndef _STLP_STRING_IO_H
172#  include <stl/_string_io.h> //includes _istream.h and _ostream.h
173#endif
174
175_STLP_BEGIN_NAMESPACE
176
177template <class _CharT, class _Traits, size_t _Nb>
178basic_istream<_CharT, _Traits>& _STLP_CALL
179operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) {
180  basic_string<_CharT, _Traits> __tmp;
181  __tmp.reserve(_Nb);
182
183  // Skip whitespace
184  typename basic_istream<_CharT, _Traits>::sentry __sentry(__is);
185  if (__sentry) {
186    basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
187    for (size_t __i = 0; __i < _Nb; ++__i) {
188      static typename _Traits::int_type __eof = _Traits::eof();
189
190      typename _Traits::int_type __c1 = __buf->sbumpc();
191      if (_Traits::eq_int_type(__c1, __eof)) {
192        __is.setstate(ios_base::eofbit);
193        break;
194      }
195      else {
196        typename _Traits::char_type __c2 = _Traits::to_char_type(__c1);
197        char __c = __is.narrow(__c2, '*');
198
199        if (__c == '0' || __c == '1')
200          __tmp.push_back(__c);
201        else if (_Traits::eq_int_type(__buf->sputbackc(__c2), __eof)) {
202          __is.setstate(ios_base::failbit);
203          break;
204        }
205      }
206    }
207
208    if (__tmp.empty())
209      __is.setstate(ios_base::failbit);
210    else
211      __x._M_copy_from_string(__tmp, __STATIC_CAST(size_t,0), _Nb);
212  }
213
214  return __is;
215}
216
217template <class _CharT, class _Traits, size_t _Nb>
218basic_ostream<_CharT, _Traits>& _STLP_CALL
219operator<<(basic_ostream<_CharT, _Traits>& __os,
220           const bitset<_Nb>& __x) {
221  basic_string<_CharT, _Traits> __tmp;
222  __x._M_copy_to_string(__tmp);
223  return __os << __tmp;
224}
225
226#  endif /* !_STLP_USE_NO_IOSTREAMS */
227
228#endif /* _STLP_NON_TYPE_TMPL_PARAM_BUG */
229
230_STLP_END_NAMESPACE
231
232#undef __BITS_PER_WORD
233#undef bitset
234
235#endif /*  _STLP_BITSET_C */
236