libstdc++: dynamic_bitset.tcc Source File (original) (raw)

30#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET_TCC

31#define _GLIBCXX_TR2_DYNAMIC_BITSET_TCC 1

33#pragma GCC system_header

35namespace std _GLIBCXX_VISIBILITY(default)

36{

37_GLIBCXX_BEGIN_NAMESPACE_VERSION

39namespace tr2

40{

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;

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 }

63 std::fill_n(this->_M_w.begin(), __wshift, _WordT(0));

64 }

65 }

67 template<typename _WordT, typename _Alloc>

68 void

69 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)

70 {

71 if (__builtin_expect(__shift != 0, 1))

72 {

73 const size_t __wshift = __shift / _S_bits_per_block;

74 const size_t __offset = __shift % _S_bits_per_block;

75 const size_t __limit = this->_M_w.size() - __wshift - 1;

77 if (__offset == 0)

78 for (size_t __n = 0; __n <= __limit; ++__n)

79 this->_M_w[__n] = this->_M_w[__n + __wshift];

80 else

81 {

82 const size_t __sub_offset = (_S_bits_per_block

83 - __offset);

84 for (size_t __n = 0; __n < __limit; ++__n)

85 this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)

86 | (this->_M_w[__n + __wshift + 1] << __sub_offset));

87 this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;

88 }

90 std::fill_n(this->_M_w.end() - __wshift, __wshift, _WordT(0));

91 }

92 }

94 template<typename _WordT, typename _Alloc>

95 unsigned long

96 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const

97 {

98 size_t __n = sizeof(unsigned long) / sizeof(block_type);

99 for (size_t __i = __n; __i < this->_M_w.size(); ++__i)

100 if (this->_M_w[__i])

101 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));

102 unsigned long __res = 0UL;

103 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)

104 __res += this->_M_w[__i] << (__i * _S_bits_per_block);

105 return __res;

106 }

107

108 template<typename _WordT, typename _Alloc>

109 unsigned long long

110 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const

111 {

112 size_t __n = sizeof(unsigned long long) / sizeof(block_type);

113 for (size_t __i = __n; __i < this->_M_w.size(); ++__i)

114 if (this->_M_w[__i])

115 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));

116 unsigned long long __res = 0ULL;

117 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)

118 __res += this->_M_w[__i] << (__i * _S_bits_per_block);

119 return __res;

120 }

121

122 template<typename _WordT, typename _Alloc>

123 size_t

124 __dynamic_bitset_base<_WordT, _Alloc>

125 ::_M_do_find_first(size_t __not_found) const

126 {

127 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)

128 {

129 _WordT __thisword = this->_M_w[__i];

130 if (__thisword != static_cast<_WordT>(0))

131 return (__i * _S_bits_per_block

132 + __builtin_ctzll(__thisword));

133 }

134

135 return __not_found;

136 }

137

138 template<typename _WordT, typename _Alloc>

139 size_t

140 __dynamic_bitset_base<_WordT, _Alloc>

141 ::_M_do_find_next(size_t __prev, size_t __not_found) const

142 {

143

144 ++__prev;

145

146

147 if (__prev >= this->_M_w.size() * _S_bits_per_block)

148 return __not_found;

149

150

151 size_t __i = _S_whichword(__prev);

152 _WordT __thisword = this->_M_w[__i];

153

154

155 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);

156

157 if (__thisword != static_cast<_WordT>(0))

158 return (__i * _S_bits_per_block

159 + __builtin_ctzll(__thisword));

160

161

162 for (++__i; __i < this->_M_w.size(); ++__i)

163 {

164 __thisword = this->_M_w[__i];

165 if (__thisword != static_cast<_WordT>(0))

166 return (__i * _S_bits_per_block

167 + __builtin_ctzll(__thisword));

168 }

169

170 return __not_found;

171 }

172

173

174 template<typename _WordT, typename _Alloc>

175 template<typename _Traits, typename _CharT>

176 void

177 dynamic_bitset<_WordT, _Alloc>::

178 _M_copy_from_ptr(const _CharT* __str, size_t __len,

179 size_t __pos, size_t __n, _CharT __zero, _CharT __one)

180 {

181 reset();

182 const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos));

183 for (size_t __i = __nbits; __i > 0; --__i)

184 {

185 const _CharT __c = __str[__pos + __nbits - __i];

186 if (_Traits::eq(__c, __zero))

187 ;

188 else if (_Traits::eq(__c, __one))

189 _M_unchecked_set(__i - 1);

190 else

191 __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr"));

192 }

193 }

194

195

196

197

198

199

200

201

202 template<typename _CharT, typename _Traits,

203 typename _WordT, typename _Alloc>

207 {

208 typedef typename _Traits::char_type char_type;

210 typedef typename __istream_type::ios_base __ios_base;

211

214

215 const char_type __zero = __is.widen('0');

216 const char_type __one = __is.widen('1');

217

218 typename __ios_base::iostate __state = __ios_base::goodbit;

219 typename __istream_type::sentry __sentry(__is);

220 if (__sentry)

221 {

222 __try

223 {

224 while (1)

225 {

226 static typename _Traits::int_type __eof = _Traits::eof();

227

228 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();

229 if (_Traits::eq_int_type(__c1, __eof))

230 {

231 __state |= __ios_base::eofbit;

232 break;

233 }

234 else

235 {

236 const char_type __c2 = _Traits::to_char_type(__c1);

237 if (_Traits::eq(__c2, __zero))

239 else if (_Traits::eq(__c2, __one))

241 else if (_Traits::

242 eq_int_type(__is.rdbuf()->sputbackc(__c2),

243 __eof))

244 {

245 __state |= __ios_base::failbit;

246 break;

247 }

248 else

249 break;

250 }

251 }

252 }

254 {

255 __is._M_setstate(__ios_base::badbit);

256 __throw_exception_again;

257 }

258 __catch(...)

259 { __is._M_setstate(__ios_base::badbit); }

260 }

261

263

265 __state |= __ios_base::failbit;

266 else

267 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),

268 __zero, __one);

269 if (__state)

271 return __is;

272 }

273}

274

275_GLIBCXX_END_NAMESPACE_VERSION

276}

277

278#endif

constexpr const _Tp & min(const _Tp &, const _Tp &)

This does what you think it does.

std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, dynamic_bitset< _WordT, _Alloc > &__x)

Stream input operator for dynamic_bitset.

ISO C++ entities toplevel namespace is std.

void setstate(iostate __state)

Sets additional flags in the error state.

char_type widen(char __c) const

Widens characters.

basic_streambuf< _CharT, _Traits > * rdbuf() const

Accessing the underlying buffer.

Template class basic_istream.

Managing sequences of characters and character-like objects.

void push_back(_CharT __c)

Append a single character.

void reserve(size_type __res_arg)

Attempt to preallocate enough memory for specified number of characters.

size_type size() const noexcept

Returns the number of characters in the string, not including any null-termination.

bool empty() const noexcept

Thrown as part of forced unwinding.

The dynamic_bitset class represents a sequence of bits.

void resize(size_type __nbits, bool __value=false)

Resize the bitset.

size_type size() const noexcept

Returns the total number of bits.