root / lab4 / .minix-src / include / c++ / __bit_reference
History | View | Annotate | Download (51.3 KB)
1 | 13 | up20180614 | // -*- C++ -*- |
---|---|---|---|
2 | //===----------------------------------------------------------------------===// |
||
3 | // |
||
4 | // The LLVM Compiler Infrastructure |
||
5 | // |
||
6 | // This file is dual licensed under the MIT and the University of Illinois Open |
||
7 | // Source Licenses. See LICENSE.TXT for details. |
||
8 | // |
||
9 | //===----------------------------------------------------------------------===// |
||
10 | |||
11 | #ifndef _LIBCPP___BIT_REFERENCE |
||
12 | #define _LIBCPP___BIT_REFERENCE |
||
13 | |||
14 | #include <__config> |
||
15 | #include <algorithm> |
||
16 | |||
17 | #include <__undef_min_max> |
||
18 | |||
19 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
||
20 | #pragma GCC system_header |
||
21 | #endif |
||
22 | |||
23 | _LIBCPP_BEGIN_NAMESPACE_STD |
||
24 | |||
25 | template <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator; |
||
26 | template <class _Cp> class __bit_const_reference; |
||
27 | |||
28 | template <class _Tp> |
||
29 | struct __has_storage_type |
||
30 | { |
||
31 | static const bool value = false; |
||
32 | }; |
||
33 | |||
34 | template <class _Cp, bool = __has_storage_type<_Cp>::value> |
||
35 | class __bit_reference |
||
36 | { |
||
37 | typedef typename _Cp::__storage_type __storage_type; |
||
38 | typedef typename _Cp::__storage_pointer __storage_pointer; |
||
39 | |||
40 | __storage_pointer __seg_; |
||
41 | __storage_type __mask_; |
||
42 | |||
43 | #if defined(__clang__) || defined(__IBMCPP__) || defined(_LIBCPP_MSVC) |
||
44 | friend typename _Cp::__self; |
||
45 | #else |
||
46 | friend class _Cp::__self; |
||
47 | #endif |
||
48 | friend class __bit_const_reference<_Cp>; |
||
49 | friend class __bit_iterator<_Cp, false>; |
||
50 | public: |
||
51 | _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT |
||
52 | {return static_cast<bool>(*__seg_ & __mask_);} |
||
53 | _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT |
||
54 | {return !static_cast<bool>(*this);} |
||
55 | |||
56 | _LIBCPP_INLINE_VISIBILITY |
||
57 | __bit_reference& operator=(bool __x) _NOEXCEPT |
||
58 | { |
||
59 | if (__x) |
||
60 | *__seg_ |= __mask_; |
||
61 | else |
||
62 | *__seg_ &= ~__mask_; |
||
63 | return *this; |
||
64 | } |
||
65 | |||
66 | _LIBCPP_INLINE_VISIBILITY |
||
67 | __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT |
||
68 | {return operator=(static_cast<bool>(__x));} |
||
69 | |||
70 | _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;} |
||
71 | _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT |
||
72 | {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} |
||
73 | private: |
||
74 | _LIBCPP_INLINE_VISIBILITY |
||
75 | __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT |
||
76 | : __seg_(__s), __mask_(__m) {} |
||
77 | }; |
||
78 | |||
79 | template <class _Cp> |
||
80 | class __bit_reference<_Cp, false> |
||
81 | { |
||
82 | }; |
||
83 | |||
84 | template <class _Cp> |
||
85 | inline _LIBCPP_INLINE_VISIBILITY |
||
86 | void |
||
87 | swap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT |
||
88 | { |
||
89 | bool __t = __x; |
||
90 | __x = __y; |
||
91 | __y = __t; |
||
92 | } |
||
93 | |||
94 | template <class _Cp, class _Dp> |
||
95 | inline _LIBCPP_INLINE_VISIBILITY |
||
96 | void |
||
97 | swap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT |
||
98 | { |
||
99 | bool __t = __x; |
||
100 | __x = __y; |
||
101 | __y = __t; |
||
102 | } |
||
103 | |||
104 | template <class _Cp> |
||
105 | inline _LIBCPP_INLINE_VISIBILITY |
||
106 | void |
||
107 | swap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT |
||
108 | { |
||
109 | bool __t = __x; |
||
110 | __x = __y; |
||
111 | __y = __t; |
||
112 | } |
||
113 | |||
114 | template <class _Cp> |
||
115 | inline _LIBCPP_INLINE_VISIBILITY |
||
116 | void |
||
117 | swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT |
||
118 | { |
||
119 | bool __t = __x; |
||
120 | __x = __y; |
||
121 | __y = __t; |
||
122 | } |
||
123 | |||
124 | template <class _Cp> |
||
125 | class __bit_const_reference |
||
126 | { |
||
127 | typedef typename _Cp::__storage_type __storage_type; |
||
128 | typedef typename _Cp::__const_storage_pointer __storage_pointer; |
||
129 | |||
130 | __storage_pointer __seg_; |
||
131 | __storage_type __mask_; |
||
132 | |||
133 | #if defined(__clang__) || defined(__IBMCPP__) || defined(_LIBCPP_MSVC) |
||
134 | friend typename _Cp::__self; |
||
135 | #else |
||
136 | friend class _Cp::__self; |
||
137 | #endif |
||
138 | friend class __bit_iterator<_Cp, true>; |
||
139 | public: |
||
140 | _LIBCPP_INLINE_VISIBILITY |
||
141 | __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT |
||
142 | : __seg_(__x.__seg_), __mask_(__x.__mask_) {} |
||
143 | |||
144 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT |
||
145 | {return static_cast<bool>(*__seg_ & __mask_);} |
||
146 | |||
147 | _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT |
||
148 | {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));} |
||
149 | private: |
||
150 | _LIBCPP_INLINE_VISIBILITY |
||
151 | _LIBCPP_CONSTEXPR |
||
152 | __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT |
||
153 | : __seg_(__s), __mask_(__m) {} |
||
154 | |||
155 | __bit_const_reference& operator=(const __bit_const_reference& __x); |
||
156 | }; |
||
157 | |||
158 | // find |
||
159 | |||
160 | template <class _Cp, bool _IsConst> |
||
161 | __bit_iterator<_Cp, _IsConst> |
||
162 | __find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) |
||
163 | { |
||
164 | typedef __bit_iterator<_Cp, _IsConst> _It; |
||
165 | typedef typename _It::__storage_type __storage_type; |
||
166 | static const unsigned __bits_per_word = _It::__bits_per_word; |
||
167 | // do first partial word |
||
168 | if (__first.__ctz_ != 0) |
||
169 | { |
||
170 | __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); |
||
171 | __storage_type __dn = _VSTD::min(__clz_f, __n); |
||
172 | __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); |
||
173 | __storage_type __b = *__first.__seg_ & __m; |
||
174 | if (__b) |
||
175 | return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); |
||
176 | if (__n == __dn) |
||
177 | return __first + __n; |
||
178 | __n -= __dn; |
||
179 | ++__first.__seg_; |
||
180 | } |
||
181 | // do middle whole words |
||
182 | for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) |
||
183 | if (*__first.__seg_) |
||
184 | return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_))); |
||
185 | // do last partial word |
||
186 | if (__n > 0) |
||
187 | { |
||
188 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
189 | __storage_type __b = *__first.__seg_ & __m; |
||
190 | if (__b) |
||
191 | return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); |
||
192 | } |
||
193 | return _It(__first.__seg_, static_cast<unsigned>(__n)); |
||
194 | } |
||
195 | |||
196 | template <class _Cp, bool _IsConst> |
||
197 | __bit_iterator<_Cp, _IsConst> |
||
198 | __find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) |
||
199 | { |
||
200 | typedef __bit_iterator<_Cp, _IsConst> _It; |
||
201 | typedef typename _It::__storage_type __storage_type; |
||
202 | static const unsigned __bits_per_word = _It::__bits_per_word; |
||
203 | // do first partial word |
||
204 | if (__first.__ctz_ != 0) |
||
205 | { |
||
206 | __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); |
||
207 | __storage_type __dn = _VSTD::min(__clz_f, __n); |
||
208 | __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); |
||
209 | __storage_type __b = ~*__first.__seg_ & __m; |
||
210 | if (__b) |
||
211 | return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); |
||
212 | if (__n == __dn) |
||
213 | return __first + __n; |
||
214 | __n -= __dn; |
||
215 | ++__first.__seg_; |
||
216 | } |
||
217 | // do middle whole words |
||
218 | for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) |
||
219 | { |
||
220 | __storage_type __b = ~*__first.__seg_; |
||
221 | if (__b) |
||
222 | return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); |
||
223 | } |
||
224 | // do last partial word |
||
225 | if (__n > 0) |
||
226 | { |
||
227 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
228 | __storage_type __b = ~*__first.__seg_ & __m; |
||
229 | if (__b) |
||
230 | return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b))); |
||
231 | } |
||
232 | return _It(__first.__seg_, static_cast<unsigned>(__n)); |
||
233 | } |
||
234 | |||
235 | template <class _Cp, bool _IsConst, class _Tp> |
||
236 | inline _LIBCPP_INLINE_VISIBILITY |
||
237 | __bit_iterator<_Cp, _IsConst> |
||
238 | find(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) |
||
239 | { |
||
240 | if (static_cast<bool>(__value_)) |
||
241 | return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); |
||
242 | return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); |
||
243 | } |
||
244 | |||
245 | // count |
||
246 | |||
247 | template <class _Cp, bool _IsConst> |
||
248 | typename __bit_iterator<_Cp, _IsConst>::difference_type |
||
249 | __count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) |
||
250 | { |
||
251 | typedef __bit_iterator<_Cp, _IsConst> _It; |
||
252 | typedef typename _It::__storage_type __storage_type; |
||
253 | typedef typename _It::difference_type difference_type; |
||
254 | static const unsigned __bits_per_word = _It::__bits_per_word; |
||
255 | difference_type __r = 0; |
||
256 | // do first partial word |
||
257 | if (__first.__ctz_ != 0) |
||
258 | { |
||
259 | __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); |
||
260 | __storage_type __dn = _VSTD::min(__clz_f, __n); |
||
261 | __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); |
||
262 | __r = _VSTD::__pop_count(*__first.__seg_ & __m); |
||
263 | __n -= __dn; |
||
264 | ++__first.__seg_; |
||
265 | } |
||
266 | // do middle whole words |
||
267 | for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) |
||
268 | __r += _VSTD::__pop_count(*__first.__seg_); |
||
269 | // do last partial word |
||
270 | if (__n > 0) |
||
271 | { |
||
272 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
273 | __r += _VSTD::__pop_count(*__first.__seg_ & __m); |
||
274 | } |
||
275 | return __r; |
||
276 | } |
||
277 | |||
278 | template <class _Cp, bool _IsConst> |
||
279 | typename __bit_iterator<_Cp, _IsConst>::difference_type |
||
280 | __count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) |
||
281 | { |
||
282 | typedef __bit_iterator<_Cp, _IsConst> _It; |
||
283 | typedef typename _It::__storage_type __storage_type; |
||
284 | typedef typename _It::difference_type difference_type; |
||
285 | static const unsigned __bits_per_word = _It::__bits_per_word; |
||
286 | difference_type __r = 0; |
||
287 | // do first partial word |
||
288 | if (__first.__ctz_ != 0) |
||
289 | { |
||
290 | __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); |
||
291 | __storage_type __dn = _VSTD::min(__clz_f, __n); |
||
292 | __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); |
||
293 | __r = _VSTD::__pop_count(~*__first.__seg_ & __m); |
||
294 | __n -= __dn; |
||
295 | ++__first.__seg_; |
||
296 | } |
||
297 | // do middle whole words |
||
298 | for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) |
||
299 | __r += _VSTD::__pop_count(~*__first.__seg_); |
||
300 | // do last partial word |
||
301 | if (__n > 0) |
||
302 | { |
||
303 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
304 | __r += _VSTD::__pop_count(~*__first.__seg_ & __m); |
||
305 | } |
||
306 | return __r; |
||
307 | } |
||
308 | |||
309 | template <class _Cp, bool _IsConst, class _Tp> |
||
310 | inline _LIBCPP_INLINE_VISIBILITY |
||
311 | typename __bit_iterator<_Cp, _IsConst>::difference_type |
||
312 | count(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_) |
||
313 | { |
||
314 | if (static_cast<bool>(__value_)) |
||
315 | return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first)); |
||
316 | return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first)); |
||
317 | } |
||
318 | |||
319 | // fill_n |
||
320 | |||
321 | template <class _Cp> |
||
322 | void |
||
323 | __fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) |
||
324 | { |
||
325 | typedef __bit_iterator<_Cp, false> _It; |
||
326 | typedef typename _It::__storage_type __storage_type; |
||
327 | static const unsigned __bits_per_word = _It::__bits_per_word; |
||
328 | // do first partial word |
||
329 | if (__first.__ctz_ != 0) |
||
330 | { |
||
331 | __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); |
||
332 | __storage_type __dn = _VSTD::min(__clz_f, __n); |
||
333 | __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); |
||
334 | *__first.__seg_ &= ~__m; |
||
335 | __n -= __dn; |
||
336 | ++__first.__seg_; |
||
337 | } |
||
338 | // do middle whole words |
||
339 | __storage_type __nw = __n / __bits_per_word; |
||
340 | _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), 0, __nw * sizeof(__storage_type)); |
||
341 | __n -= __nw * __bits_per_word; |
||
342 | // do last partial word |
||
343 | if (__n > 0) |
||
344 | { |
||
345 | __first.__seg_ += __nw; |
||
346 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
347 | *__first.__seg_ &= ~__m; |
||
348 | } |
||
349 | } |
||
350 | |||
351 | template <class _Cp> |
||
352 | void |
||
353 | __fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n) |
||
354 | { |
||
355 | typedef __bit_iterator<_Cp, false> _It; |
||
356 | typedef typename _It::__storage_type __storage_type; |
||
357 | static const unsigned __bits_per_word = _It::__bits_per_word; |
||
358 | // do first partial word |
||
359 | if (__first.__ctz_ != 0) |
||
360 | { |
||
361 | __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); |
||
362 | __storage_type __dn = _VSTD::min(__clz_f, __n); |
||
363 | __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); |
||
364 | *__first.__seg_ |= __m; |
||
365 | __n -= __dn; |
||
366 | ++__first.__seg_; |
||
367 | } |
||
368 | // do middle whole words |
||
369 | __storage_type __nw = __n / __bits_per_word; |
||
370 | _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), -1, __nw * sizeof(__storage_type)); |
||
371 | __n -= __nw * __bits_per_word; |
||
372 | // do last partial word |
||
373 | if (__n > 0) |
||
374 | { |
||
375 | __first.__seg_ += __nw; |
||
376 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
377 | *__first.__seg_ |= __m; |
||
378 | } |
||
379 | } |
||
380 | |||
381 | template <class _Cp> |
||
382 | inline _LIBCPP_INLINE_VISIBILITY |
||
383 | void |
||
384 | fill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_) |
||
385 | { |
||
386 | if (__n > 0) |
||
387 | { |
||
388 | if (__value_) |
||
389 | __fill_n_true(__first, __n); |
||
390 | else |
||
391 | __fill_n_false(__first, __n); |
||
392 | } |
||
393 | } |
||
394 | |||
395 | // fill |
||
396 | |||
397 | template <class _Cp> |
||
398 | inline _LIBCPP_INLINE_VISIBILITY |
||
399 | void |
||
400 | fill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_) |
||
401 | { |
||
402 | _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_); |
||
403 | } |
||
404 | |||
405 | // copy |
||
406 | |||
407 | template <class _Cp, bool _IsConst> |
||
408 | __bit_iterator<_Cp, false> |
||
409 | __copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, |
||
410 | __bit_iterator<_Cp, false> __result) |
||
411 | { |
||
412 | typedef __bit_iterator<_Cp, _IsConst> _In; |
||
413 | typedef typename _In::difference_type difference_type; |
||
414 | typedef typename _In::__storage_type __storage_type; |
||
415 | static const unsigned __bits_per_word = _In::__bits_per_word; |
||
416 | difference_type __n = __last - __first; |
||
417 | if (__n > 0) |
||
418 | { |
||
419 | // do first word |
||
420 | if (__first.__ctz_ != 0) |
||
421 | { |
||
422 | unsigned __clz = __bits_per_word - __first.__ctz_; |
||
423 | difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); |
||
424 | __n -= __dn; |
||
425 | __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); |
||
426 | __storage_type __b = *__first.__seg_ & __m; |
||
427 | *__result.__seg_ &= ~__m; |
||
428 | *__result.__seg_ |= __b; |
||
429 | __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; |
||
430 | __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); |
||
431 | ++__first.__seg_; |
||
432 | // __first.__ctz_ = 0; |
||
433 | } |
||
434 | // __first.__ctz_ == 0; |
||
435 | // do middle words |
||
436 | __storage_type __nw = __n / __bits_per_word; |
||
437 | _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_), |
||
438 | _VSTD::__to_raw_pointer(__first.__seg_), |
||
439 | __nw * sizeof(__storage_type)); |
||
440 | __n -= __nw * __bits_per_word; |
||
441 | __result.__seg_ += __nw; |
||
442 | // do last word |
||
443 | if (__n > 0) |
||
444 | { |
||
445 | __first.__seg_ += __nw; |
||
446 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
447 | __storage_type __b = *__first.__seg_ & __m; |
||
448 | *__result.__seg_ &= ~__m; |
||
449 | *__result.__seg_ |= __b; |
||
450 | __result.__ctz_ = static_cast<unsigned>(__n); |
||
451 | } |
||
452 | } |
||
453 | return __result; |
||
454 | } |
||
455 | |||
456 | template <class _Cp, bool _IsConst> |
||
457 | __bit_iterator<_Cp, false> |
||
458 | __copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, |
||
459 | __bit_iterator<_Cp, false> __result) |
||
460 | { |
||
461 | typedef __bit_iterator<_Cp, _IsConst> _In; |
||
462 | typedef typename _In::difference_type difference_type; |
||
463 | typedef typename _In::__storage_type __storage_type; |
||
464 | static const unsigned __bits_per_word = _In::__bits_per_word; |
||
465 | difference_type __n = __last - __first; |
||
466 | if (__n > 0) |
||
467 | { |
||
468 | // do first word |
||
469 | if (__first.__ctz_ != 0) |
||
470 | { |
||
471 | unsigned __clz_f = __bits_per_word - __first.__ctz_; |
||
472 | difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); |
||
473 | __n -= __dn; |
||
474 | __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); |
||
475 | __storage_type __b = *__first.__seg_ & __m; |
||
476 | unsigned __clz_r = __bits_per_word - __result.__ctz_; |
||
477 | __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); |
||
478 | __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); |
||
479 | *__result.__seg_ &= ~__m; |
||
480 | if (__result.__ctz_ > __first.__ctz_) |
||
481 | *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_); |
||
482 | else |
||
483 | *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_); |
||
484 | __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; |
||
485 | __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); |
||
486 | __dn -= __ddn; |
||
487 | if (__dn > 0) |
||
488 | { |
||
489 | __m = ~__storage_type(0) >> (__bits_per_word - __dn); |
||
490 | *__result.__seg_ &= ~__m; |
||
491 | *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn); |
||
492 | __result.__ctz_ = static_cast<unsigned>(__dn); |
||
493 | } |
||
494 | ++__first.__seg_; |
||
495 | // __first.__ctz_ = 0; |
||
496 | } |
||
497 | // __first.__ctz_ == 0; |
||
498 | // do middle words |
||
499 | unsigned __clz_r = __bits_per_word - __result.__ctz_; |
||
500 | __storage_type __m = ~__storage_type(0) << __result.__ctz_; |
||
501 | for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) |
||
502 | { |
||
503 | __storage_type __b = *__first.__seg_; |
||
504 | *__result.__seg_ &= ~__m; |
||
505 | *__result.__seg_ |= __b << __result.__ctz_; |
||
506 | ++__result.__seg_; |
||
507 | *__result.__seg_ &= __m; |
||
508 | *__result.__seg_ |= __b >> __clz_r; |
||
509 | } |
||
510 | // do last word |
||
511 | if (__n > 0) |
||
512 | { |
||
513 | __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
514 | __storage_type __b = *__first.__seg_ & __m; |
||
515 | __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); |
||
516 | __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); |
||
517 | *__result.__seg_ &= ~__m; |
||
518 | *__result.__seg_ |= __b << __result.__ctz_; |
||
519 | __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; |
||
520 | __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); |
||
521 | __n -= __dn; |
||
522 | if (__n > 0) |
||
523 | { |
||
524 | __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
525 | *__result.__seg_ &= ~__m; |
||
526 | *__result.__seg_ |= __b >> __dn; |
||
527 | __result.__ctz_ = static_cast<unsigned>(__n); |
||
528 | } |
||
529 | } |
||
530 | } |
||
531 | return __result; |
||
532 | } |
||
533 | |||
534 | template <class _Cp, bool _IsConst> |
||
535 | inline _LIBCPP_INLINE_VISIBILITY |
||
536 | __bit_iterator<_Cp, false> |
||
537 | copy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) |
||
538 | { |
||
539 | if (__first.__ctz_ == __result.__ctz_) |
||
540 | return __copy_aligned(__first, __last, __result); |
||
541 | return __copy_unaligned(__first, __last, __result); |
||
542 | } |
||
543 | |||
544 | // copy_backward |
||
545 | |||
546 | template <class _Cp, bool _IsConst> |
||
547 | __bit_iterator<_Cp, false> |
||
548 | __copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, |
||
549 | __bit_iterator<_Cp, false> __result) |
||
550 | { |
||
551 | typedef __bit_iterator<_Cp, _IsConst> _In; |
||
552 | typedef typename _In::difference_type difference_type; |
||
553 | typedef typename _In::__storage_type __storage_type; |
||
554 | static const unsigned __bits_per_word = _In::__bits_per_word; |
||
555 | difference_type __n = __last - __first; |
||
556 | if (__n > 0) |
||
557 | { |
||
558 | // do first word |
||
559 | if (__last.__ctz_ != 0) |
||
560 | { |
||
561 | difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); |
||
562 | __n -= __dn; |
||
563 | unsigned __clz = __bits_per_word - __last.__ctz_; |
||
564 | __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz); |
||
565 | __storage_type __b = *__last.__seg_ & __m; |
||
566 | *__result.__seg_ &= ~__m; |
||
567 | *__result.__seg_ |= __b; |
||
568 | __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + |
||
569 | __result.__ctz_) % __bits_per_word); |
||
570 | // __last.__ctz_ = 0 |
||
571 | } |
||
572 | // __last.__ctz_ == 0 || __n == 0 |
||
573 | // __result.__ctz_ == 0 || __n == 0 |
||
574 | // do middle words |
||
575 | __storage_type __nw = __n / __bits_per_word; |
||
576 | __result.__seg_ -= __nw; |
||
577 | __last.__seg_ -= __nw; |
||
578 | _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_), |
||
579 | _VSTD::__to_raw_pointer(__last.__seg_), |
||
580 | __nw * sizeof(__storage_type)); |
||
581 | __n -= __nw * __bits_per_word; |
||
582 | // do last word |
||
583 | if (__n > 0) |
||
584 | { |
||
585 | __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n); |
||
586 | __storage_type __b = *--__last.__seg_ & __m; |
||
587 | *--__result.__seg_ &= ~__m; |
||
588 | *__result.__seg_ |= __b; |
||
589 | __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); |
||
590 | } |
||
591 | } |
||
592 | return __result; |
||
593 | } |
||
594 | |||
595 | template <class _Cp, bool _IsConst> |
||
596 | __bit_iterator<_Cp, false> |
||
597 | __copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, |
||
598 | __bit_iterator<_Cp, false> __result) |
||
599 | { |
||
600 | typedef __bit_iterator<_Cp, _IsConst> _In; |
||
601 | typedef typename _In::difference_type difference_type; |
||
602 | typedef typename _In::__storage_type __storage_type; |
||
603 | static const unsigned __bits_per_word = _In::__bits_per_word; |
||
604 | difference_type __n = __last - __first; |
||
605 | if (__n > 0) |
||
606 | { |
||
607 | // do first word |
||
608 | if (__last.__ctz_ != 0) |
||
609 | { |
||
610 | difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n); |
||
611 | __n -= __dn; |
||
612 | unsigned __clz_l = __bits_per_word - __last.__ctz_; |
||
613 | __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l); |
||
614 | __storage_type __b = *__last.__seg_ & __m; |
||
615 | unsigned __clz_r = __bits_per_word - __result.__ctz_; |
||
616 | __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_)); |
||
617 | if (__ddn > 0) |
||
618 | { |
||
619 | __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r); |
||
620 | *__result.__seg_ &= ~__m; |
||
621 | if (__result.__ctz_ > __last.__ctz_) |
||
622 | *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); |
||
623 | else |
||
624 | *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_); |
||
625 | __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) + |
||
626 | __result.__ctz_) % __bits_per_word); |
||
627 | __dn -= __ddn; |
||
628 | } |
||
629 | if (__dn > 0) |
||
630 | { |
||
631 | // __result.__ctz_ == 0 |
||
632 | --__result.__seg_; |
||
633 | __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1)); |
||
634 | __m = ~__storage_type(0) << __result.__ctz_; |
||
635 | *__result.__seg_ &= ~__m; |
||
636 | __last.__ctz_ -= __dn + __ddn; |
||
637 | *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_); |
||
638 | } |
||
639 | // __last.__ctz_ = 0 |
||
640 | } |
||
641 | // __last.__ctz_ == 0 || __n == 0 |
||
642 | // __result.__ctz_ != 0 || __n == 0 |
||
643 | // do middle words |
||
644 | unsigned __clz_r = __bits_per_word - __result.__ctz_; |
||
645 | __storage_type __m = ~__storage_type(0) >> __clz_r; |
||
646 | for (; __n >= __bits_per_word; __n -= __bits_per_word) |
||
647 | { |
||
648 | __storage_type __b = *--__last.__seg_; |
||
649 | *__result.__seg_ &= ~__m; |
||
650 | *__result.__seg_ |= __b >> __clz_r; |
||
651 | *--__result.__seg_ &= __m; |
||
652 | *__result.__seg_ |= __b << __result.__ctz_; |
||
653 | } |
||
654 | // do last word |
||
655 | if (__n > 0) |
||
656 | { |
||
657 | __m = ~__storage_type(0) << (__bits_per_word - __n); |
||
658 | __storage_type __b = *--__last.__seg_ & __m; |
||
659 | __clz_r = __bits_per_word - __result.__ctz_; |
||
660 | __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_)); |
||
661 | __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r); |
||
662 | *__result.__seg_ &= ~__m; |
||
663 | *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_); |
||
664 | __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) + |
||
665 | __result.__ctz_) % __bits_per_word); |
||
666 | __n -= __dn; |
||
667 | if (__n > 0) |
||
668 | { |
||
669 | // __result.__ctz_ == 0 |
||
670 | --__result.__seg_; |
||
671 | __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1)); |
||
672 | __m = ~__storage_type(0) << __result.__ctz_; |
||
673 | *__result.__seg_ &= ~__m; |
||
674 | *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn)); |
||
675 | } |
||
676 | } |
||
677 | } |
||
678 | return __result; |
||
679 | } |
||
680 | |||
681 | template <class _Cp, bool _IsConst> |
||
682 | inline _LIBCPP_INLINE_VISIBILITY |
||
683 | __bit_iterator<_Cp, false> |
||
684 | copy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) |
||
685 | { |
||
686 | if (__last.__ctz_ == __result.__ctz_) |
||
687 | return __copy_backward_aligned(__first, __last, __result); |
||
688 | return __copy_backward_unaligned(__first, __last, __result); |
||
689 | } |
||
690 | |||
691 | // move |
||
692 | |||
693 | template <class _Cp, bool _IsConst> |
||
694 | inline _LIBCPP_INLINE_VISIBILITY |
||
695 | __bit_iterator<_Cp, false> |
||
696 | move(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) |
||
697 | { |
||
698 | return _VSTD::copy(__first, __last, __result); |
||
699 | } |
||
700 | |||
701 | // move_backward |
||
702 | |||
703 | template <class _Cp, bool _IsConst> |
||
704 | inline _LIBCPP_INLINE_VISIBILITY |
||
705 | __bit_iterator<_Cp, false> |
||
706 | move_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result) |
||
707 | { |
||
708 | return _VSTD::copy_backward(__first, __last, __result); |
||
709 | } |
||
710 | |||
711 | // swap_ranges |
||
712 | |||
713 | template <class __C1, class __C2> |
||
714 | __bit_iterator<__C2, false> |
||
715 | __swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, |
||
716 | __bit_iterator<__C2, false> __result) |
||
717 | { |
||
718 | typedef __bit_iterator<__C1, false> _I1; |
||
719 | typedef typename _I1::difference_type difference_type; |
||
720 | typedef typename _I1::__storage_type __storage_type; |
||
721 | static const unsigned __bits_per_word = _I1::__bits_per_word; |
||
722 | difference_type __n = __last - __first; |
||
723 | if (__n > 0) |
||
724 | { |
||
725 | // do first word |
||
726 | if (__first.__ctz_ != 0) |
||
727 | { |
||
728 | unsigned __clz = __bits_per_word - __first.__ctz_; |
||
729 | difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); |
||
730 | __n -= __dn; |
||
731 | __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); |
||
732 | __storage_type __b1 = *__first.__seg_ & __m; |
||
733 | *__first.__seg_ &= ~__m; |
||
734 | __storage_type __b2 = *__result.__seg_ & __m; |
||
735 | *__result.__seg_ &= ~__m; |
||
736 | *__result.__seg_ |= __b1; |
||
737 | *__first.__seg_ |= __b2; |
||
738 | __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; |
||
739 | __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); |
||
740 | ++__first.__seg_; |
||
741 | // __first.__ctz_ = 0; |
||
742 | } |
||
743 | // __first.__ctz_ == 0; |
||
744 | // do middle words |
||
745 | for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_) |
||
746 | swap(*__first.__seg_, *__result.__seg_); |
||
747 | // do last word |
||
748 | if (__n > 0) |
||
749 | { |
||
750 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
751 | __storage_type __b1 = *__first.__seg_ & __m; |
||
752 | *__first.__seg_ &= ~__m; |
||
753 | __storage_type __b2 = *__result.__seg_ & __m; |
||
754 | *__result.__seg_ &= ~__m; |
||
755 | *__result.__seg_ |= __b1; |
||
756 | *__first.__seg_ |= __b2; |
||
757 | __result.__ctz_ = static_cast<unsigned>(__n); |
||
758 | } |
||
759 | } |
||
760 | return __result; |
||
761 | } |
||
762 | |||
763 | template <class __C1, class __C2> |
||
764 | __bit_iterator<__C2, false> |
||
765 | __swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last, |
||
766 | __bit_iterator<__C2, false> __result) |
||
767 | { |
||
768 | typedef __bit_iterator<__C1, false> _I1; |
||
769 | typedef typename _I1::difference_type difference_type; |
||
770 | typedef typename _I1::__storage_type __storage_type; |
||
771 | static const unsigned __bits_per_word = _I1::__bits_per_word; |
||
772 | difference_type __n = __last - __first; |
||
773 | if (__n > 0) |
||
774 | { |
||
775 | // do first word |
||
776 | if (__first.__ctz_ != 0) |
||
777 | { |
||
778 | unsigned __clz_f = __bits_per_word - __first.__ctz_; |
||
779 | difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); |
||
780 | __n -= __dn; |
||
781 | __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); |
||
782 | __storage_type __b1 = *__first.__seg_ & __m; |
||
783 | *__first.__seg_ &= ~__m; |
||
784 | unsigned __clz_r = __bits_per_word - __result.__ctz_; |
||
785 | __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); |
||
786 | __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); |
||
787 | __storage_type __b2 = *__result.__seg_ & __m; |
||
788 | *__result.__seg_ &= ~__m; |
||
789 | if (__result.__ctz_ > __first.__ctz_) |
||
790 | { |
||
791 | unsigned __s = __result.__ctz_ - __first.__ctz_; |
||
792 | *__result.__seg_ |= __b1 << __s; |
||
793 | *__first.__seg_ |= __b2 >> __s; |
||
794 | } |
||
795 | else |
||
796 | { |
||
797 | unsigned __s = __first.__ctz_ - __result.__ctz_; |
||
798 | *__result.__seg_ |= __b1 >> __s; |
||
799 | *__first.__seg_ |= __b2 << __s; |
||
800 | } |
||
801 | __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word; |
||
802 | __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word); |
||
803 | __dn -= __ddn; |
||
804 | if (__dn > 0) |
||
805 | { |
||
806 | __m = ~__storage_type(0) >> (__bits_per_word - __dn); |
||
807 | __b2 = *__result.__seg_ & __m; |
||
808 | *__result.__seg_ &= ~__m; |
||
809 | unsigned __s = __first.__ctz_ + __ddn; |
||
810 | *__result.__seg_ |= __b1 >> __s; |
||
811 | *__first.__seg_ |= __b2 << __s; |
||
812 | __result.__ctz_ = static_cast<unsigned>(__dn); |
||
813 | } |
||
814 | ++__first.__seg_; |
||
815 | // __first.__ctz_ = 0; |
||
816 | } |
||
817 | // __first.__ctz_ == 0; |
||
818 | // do middle words |
||
819 | __storage_type __m = ~__storage_type(0) << __result.__ctz_; |
||
820 | unsigned __clz_r = __bits_per_word - __result.__ctz_; |
||
821 | for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_) |
||
822 | { |
||
823 | __storage_type __b1 = *__first.__seg_; |
||
824 | __storage_type __b2 = *__result.__seg_ & __m; |
||
825 | *__result.__seg_ &= ~__m; |
||
826 | *__result.__seg_ |= __b1 << __result.__ctz_; |
||
827 | *__first.__seg_ = __b2 >> __result.__ctz_; |
||
828 | ++__result.__seg_; |
||
829 | __b2 = *__result.__seg_ & ~__m; |
||
830 | *__result.__seg_ &= __m; |
||
831 | *__result.__seg_ |= __b1 >> __clz_r; |
||
832 | *__first.__seg_ |= __b2 << __clz_r; |
||
833 | } |
||
834 | // do last word |
||
835 | if (__n > 0) |
||
836 | { |
||
837 | __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
838 | __storage_type __b1 = *__first.__seg_ & __m; |
||
839 | *__first.__seg_ &= ~__m; |
||
840 | __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r); |
||
841 | __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); |
||
842 | __storage_type __b2 = *__result.__seg_ & __m; |
||
843 | *__result.__seg_ &= ~__m; |
||
844 | *__result.__seg_ |= __b1 << __result.__ctz_; |
||
845 | *__first.__seg_ |= __b2 >> __result.__ctz_; |
||
846 | __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word; |
||
847 | __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word); |
||
848 | __n -= __dn; |
||
849 | if (__n > 0) |
||
850 | { |
||
851 | __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
852 | __b2 = *__result.__seg_ & __m; |
||
853 | *__result.__seg_ &= ~__m; |
||
854 | *__result.__seg_ |= __b1 >> __dn; |
||
855 | *__first.__seg_ |= __b2 << __dn; |
||
856 | __result.__ctz_ = static_cast<unsigned>(__n); |
||
857 | } |
||
858 | } |
||
859 | } |
||
860 | return __result; |
||
861 | } |
||
862 | |||
863 | template <class __C1, class __C2> |
||
864 | inline _LIBCPP_INLINE_VISIBILITY |
||
865 | __bit_iterator<__C2, false> |
||
866 | swap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1, |
||
867 | __bit_iterator<__C2, false> __first2) |
||
868 | { |
||
869 | if (__first1.__ctz_ == __first2.__ctz_) |
||
870 | return __swap_ranges_aligned(__first1, __last1, __first2); |
||
871 | return __swap_ranges_unaligned(__first1, __last1, __first2); |
||
872 | } |
||
873 | |||
874 | // rotate |
||
875 | |||
876 | template <class _Cp> |
||
877 | struct __bit_array |
||
878 | { |
||
879 | typedef typename _Cp::difference_type difference_type; |
||
880 | typedef typename _Cp::__storage_type __storage_type; |
||
881 | typedef typename _Cp::__storage_pointer __storage_pointer; |
||
882 | typedef typename _Cp::iterator iterator; |
||
883 | static const unsigned __bits_per_word = _Cp::__bits_per_word; |
||
884 | static const unsigned _Np = 4; |
||
885 | |||
886 | difference_type __size_; |
||
887 | __storage_type __word_[_Np]; |
||
888 | |||
889 | _LIBCPP_INLINE_VISIBILITY static difference_type capacity() |
||
890 | {return static_cast<difference_type>(_Np * __bits_per_word);} |
||
891 | _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {} |
||
892 | _LIBCPP_INLINE_VISIBILITY iterator begin() |
||
893 | { |
||
894 | return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0); |
||
895 | } |
||
896 | _LIBCPP_INLINE_VISIBILITY iterator end() |
||
897 | { |
||
898 | return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word, |
||
899 | static_cast<unsigned>(__size_ % __bits_per_word)); |
||
900 | } |
||
901 | }; |
||
902 | |||
903 | template <class _Cp> |
||
904 | __bit_iterator<_Cp, false> |
||
905 | rotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last) |
||
906 | { |
||
907 | typedef __bit_iterator<_Cp, false> _I1; |
||
908 | typedef typename _I1::difference_type difference_type; |
||
909 | difference_type __d1 = __middle - __first; |
||
910 | difference_type __d2 = __last - __middle; |
||
911 | _I1 __r = __first + __d2; |
||
912 | while (__d1 != 0 && __d2 != 0) |
||
913 | { |
||
914 | if (__d1 <= __d2) |
||
915 | { |
||
916 | if (__d1 <= __bit_array<_Cp>::capacity()) |
||
917 | { |
||
918 | __bit_array<_Cp> __b(__d1); |
||
919 | _VSTD::copy(__first, __middle, __b.begin()); |
||
920 | _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first)); |
||
921 | break; |
||
922 | } |
||
923 | else |
||
924 | { |
||
925 | __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle); |
||
926 | __first = __middle; |
||
927 | __middle = __mp; |
||
928 | __d2 -= __d1; |
||
929 | } |
||
930 | } |
||
931 | else |
||
932 | { |
||
933 | if (__d2 <= __bit_array<_Cp>::capacity()) |
||
934 | { |
||
935 | __bit_array<_Cp> __b(__d2); |
||
936 | _VSTD::copy(__middle, __last, __b.begin()); |
||
937 | _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last)); |
||
938 | break; |
||
939 | } |
||
940 | else |
||
941 | { |
||
942 | __bit_iterator<_Cp, false> __mp = __first + __d2; |
||
943 | _VSTD::swap_ranges(__first, __mp, __middle); |
||
944 | __first = __mp; |
||
945 | __d1 -= __d2; |
||
946 | } |
||
947 | } |
||
948 | } |
||
949 | return __r; |
||
950 | } |
||
951 | |||
952 | // equal |
||
953 | |||
954 | template <class _Cp, bool _IC1, bool _IC2> |
||
955 | bool |
||
956 | __equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, |
||
957 | __bit_iterator<_Cp, _IC2> __first2) |
||
958 | { |
||
959 | typedef __bit_iterator<_Cp, _IC1> _It; |
||
960 | typedef typename _It::difference_type difference_type; |
||
961 | typedef typename _It::__storage_type __storage_type; |
||
962 | static const unsigned __bits_per_word = _It::__bits_per_word; |
||
963 | difference_type __n = __last1 - __first1; |
||
964 | if (__n > 0) |
||
965 | { |
||
966 | // do first word |
||
967 | if (__first1.__ctz_ != 0) |
||
968 | { |
||
969 | unsigned __clz_f = __bits_per_word - __first1.__ctz_; |
||
970 | difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n); |
||
971 | __n -= __dn; |
||
972 | __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); |
||
973 | __storage_type __b = *__first1.__seg_ & __m; |
||
974 | unsigned __clz_r = __bits_per_word - __first2.__ctz_; |
||
975 | __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r); |
||
976 | __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn)); |
||
977 | if (__first2.__ctz_ > __first1.__ctz_) |
||
978 | { |
||
979 | if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_))) |
||
980 | return false; |
||
981 | } |
||
982 | else |
||
983 | { |
||
984 | if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_))) |
||
985 | return false; |
||
986 | } |
||
987 | __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word; |
||
988 | __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word); |
||
989 | __dn -= __ddn; |
||
990 | if (__dn > 0) |
||
991 | { |
||
992 | __m = ~__storage_type(0) >> (__bits_per_word - __dn); |
||
993 | if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn))) |
||
994 | return false; |
||
995 | __first2.__ctz_ = static_cast<unsigned>(__dn); |
||
996 | } |
||
997 | ++__first1.__seg_; |
||
998 | // __first1.__ctz_ = 0; |
||
999 | } |
||
1000 | // __first1.__ctz_ == 0; |
||
1001 | // do middle words |
||
1002 | unsigned __clz_r = __bits_per_word - __first2.__ctz_; |
||
1003 | __storage_type __m = ~__storage_type(0) << __first2.__ctz_; |
||
1004 | for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_) |
||
1005 | { |
||
1006 | __storage_type __b = *__first1.__seg_; |
||
1007 | if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) |
||
1008 | return false; |
||
1009 | ++__first2.__seg_; |
||
1010 | if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r)) |
||
1011 | return false; |
||
1012 | } |
||
1013 | // do last word |
||
1014 | if (__n > 0) |
||
1015 | { |
||
1016 | __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
1017 | __storage_type __b = *__first1.__seg_ & __m; |
||
1018 | __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r)); |
||
1019 | __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn)); |
||
1020 | if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_)) |
||
1021 | return false; |
||
1022 | __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word; |
||
1023 | __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word); |
||
1024 | __n -= __dn; |
||
1025 | if (__n > 0) |
||
1026 | { |
||
1027 | __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
1028 | if ((*__first2.__seg_ & __m) != (__b >> __dn)) |
||
1029 | return false; |
||
1030 | } |
||
1031 | } |
||
1032 | } |
||
1033 | return true; |
||
1034 | } |
||
1035 | |||
1036 | template <class _Cp, bool _IC1, bool _IC2> |
||
1037 | bool |
||
1038 | __equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, |
||
1039 | __bit_iterator<_Cp, _IC2> __first2) |
||
1040 | { |
||
1041 | typedef __bit_iterator<_Cp, _IC1> _It; |
||
1042 | typedef typename _It::difference_type difference_type; |
||
1043 | typedef typename _It::__storage_type __storage_type; |
||
1044 | static const unsigned __bits_per_word = _It::__bits_per_word; |
||
1045 | difference_type __n = __last1 - __first1; |
||
1046 | if (__n > 0) |
||
1047 | { |
||
1048 | // do first word |
||
1049 | if (__first1.__ctz_ != 0) |
||
1050 | { |
||
1051 | unsigned __clz = __bits_per_word - __first1.__ctz_; |
||
1052 | difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n); |
||
1053 | __n -= __dn; |
||
1054 | __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn)); |
||
1055 | if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) |
||
1056 | return false; |
||
1057 | ++__first2.__seg_; |
||
1058 | ++__first1.__seg_; |
||
1059 | // __first1.__ctz_ = 0; |
||
1060 | // __first2.__ctz_ = 0; |
||
1061 | } |
||
1062 | // __first1.__ctz_ == 0; |
||
1063 | // __first2.__ctz_ == 0; |
||
1064 | // do middle words |
||
1065 | for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_) |
||
1066 | if (*__first2.__seg_ != *__first1.__seg_) |
||
1067 | return false; |
||
1068 | // do last word |
||
1069 | if (__n > 0) |
||
1070 | { |
||
1071 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
1072 | if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m)) |
||
1073 | return false; |
||
1074 | } |
||
1075 | } |
||
1076 | return true; |
||
1077 | } |
||
1078 | |||
1079 | template <class _Cp, bool _IC1, bool _IC2> |
||
1080 | inline _LIBCPP_INLINE_VISIBILITY |
||
1081 | bool |
||
1082 | equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2) |
||
1083 | { |
||
1084 | if (__first1.__ctz_ == __first2.__ctz_) |
||
1085 | return __equal_aligned(__first1, __last1, __first2); |
||
1086 | return __equal_unaligned(__first1, __last1, __first2); |
||
1087 | } |
||
1088 | |||
1089 | template <class _Cp, bool _IsConst, |
||
1090 | typename _Cp::__storage_type> |
||
1091 | class __bit_iterator |
||
1092 | { |
||
1093 | public: |
||
1094 | typedef typename _Cp::difference_type difference_type; |
||
1095 | typedef bool value_type; |
||
1096 | typedef __bit_iterator pointer; |
||
1097 | typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference; |
||
1098 | typedef random_access_iterator_tag iterator_category; |
||
1099 | |||
1100 | private: |
||
1101 | typedef typename _Cp::__storage_type __storage_type; |
||
1102 | typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer, |
||
1103 | typename _Cp::__storage_pointer>::type __storage_pointer; |
||
1104 | static const unsigned __bits_per_word = _Cp::__bits_per_word; |
||
1105 | |||
1106 | __storage_pointer __seg_; |
||
1107 | unsigned __ctz_; |
||
1108 | |||
1109 | public: |
||
1110 | _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT |
||
1111 | #if _LIBCPP_STD_VER > 11 |
||
1112 | : __seg_(nullptr), __ctz_(0) |
||
1113 | #endif |
||
1114 | {} |
||
1115 | |||
1116 | _LIBCPP_INLINE_VISIBILITY |
||
1117 | __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT |
||
1118 | : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {} |
||
1119 | |||
1120 | _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT |
||
1121 | {return reference(__seg_, __storage_type(1) << __ctz_);} |
||
1122 | |||
1123 | _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++() |
||
1124 | { |
||
1125 | if (__ctz_ != __bits_per_word-1) |
||
1126 | ++__ctz_; |
||
1127 | else |
||
1128 | { |
||
1129 | __ctz_ = 0; |
||
1130 | ++__seg_; |
||
1131 | } |
||
1132 | return *this; |
||
1133 | } |
||
1134 | |||
1135 | _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int) |
||
1136 | { |
||
1137 | __bit_iterator __tmp = *this; |
||
1138 | ++(*this); |
||
1139 | return __tmp; |
||
1140 | } |
||
1141 | |||
1142 | _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--() |
||
1143 | { |
||
1144 | if (__ctz_ != 0) |
||
1145 | --__ctz_; |
||
1146 | else |
||
1147 | { |
||
1148 | __ctz_ = __bits_per_word - 1; |
||
1149 | --__seg_; |
||
1150 | } |
||
1151 | return *this; |
||
1152 | } |
||
1153 | |||
1154 | _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int) |
||
1155 | { |
||
1156 | __bit_iterator __tmp = *this; |
||
1157 | --(*this); |
||
1158 | return __tmp; |
||
1159 | } |
||
1160 | |||
1161 | _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n) |
||
1162 | { |
||
1163 | if (__n >= 0) |
||
1164 | __seg_ += (__n + __ctz_) / __bits_per_word; |
||
1165 | else |
||
1166 | __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1) |
||
1167 | / static_cast<difference_type>(__bits_per_word); |
||
1168 | __n &= (__bits_per_word - 1); |
||
1169 | __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word); |
||
1170 | return *this; |
||
1171 | } |
||
1172 | |||
1173 | _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n) |
||
1174 | { |
||
1175 | return *this += -__n; |
||
1176 | } |
||
1177 | |||
1178 | _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const |
||
1179 | { |
||
1180 | __bit_iterator __t(*this); |
||
1181 | __t += __n; |
||
1182 | return __t; |
||
1183 | } |
||
1184 | |||
1185 | _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const |
||
1186 | { |
||
1187 | __bit_iterator __t(*this); |
||
1188 | __t -= __n; |
||
1189 | return __t; |
||
1190 | } |
||
1191 | |||
1192 | _LIBCPP_INLINE_VISIBILITY |
||
1193 | friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;} |
||
1194 | |||
1195 | _LIBCPP_INLINE_VISIBILITY |
||
1196 | friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y) |
||
1197 | {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;} |
||
1198 | |||
1199 | _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);} |
||
1200 | |||
1201 | _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y) |
||
1202 | {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;} |
||
1203 | |||
1204 | _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y) |
||
1205 | {return !(__x == __y);} |
||
1206 | |||
1207 | _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y) |
||
1208 | {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);} |
||
1209 | |||
1210 | _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y) |
||
1211 | {return __y < __x;} |
||
1212 | |||
1213 | _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y) |
||
1214 | {return !(__y < __x);} |
||
1215 | |||
1216 | _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y) |
||
1217 | {return !(__x < __y);} |
||
1218 | |||
1219 | private: |
||
1220 | _LIBCPP_INLINE_VISIBILITY |
||
1221 | __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT |
||
1222 | : __seg_(__s), __ctz_(__ctz) {} |
||
1223 | |||
1224 | #if defined(__clang__) || defined(__IBMCPP__) || defined(_LIBCPP_MSVC) |
||
1225 | friend typename _Cp::__self; |
||
1226 | #else |
||
1227 | friend class _Cp::__self; |
||
1228 | #endif |
||
1229 | friend class __bit_reference<_Cp>; |
||
1230 | friend class __bit_const_reference<_Cp>; |
||
1231 | friend class __bit_iterator<_Cp, true>; |
||
1232 | template <class _Dp> friend struct __bit_array; |
||
1233 | template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); |
||
1234 | template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n); |
||
1235 | template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first, |
||
1236 | __bit_iterator<_Dp, _IC> __last, |
||
1237 | __bit_iterator<_Dp, false> __result); |
||
1238 | template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first, |
||
1239 | __bit_iterator<_Dp, _IC> __last, |
||
1240 | __bit_iterator<_Dp, false> __result); |
||
1241 | template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first, |
||
1242 | __bit_iterator<_Dp, _IC> __last, |
||
1243 | __bit_iterator<_Dp, false> __result); |
||
1244 | template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first, |
||
1245 | __bit_iterator<_Dp, _IC> __last, |
||
1246 | __bit_iterator<_Dp, false> __result); |
||
1247 | template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first, |
||
1248 | __bit_iterator<_Dp, _IC> __last, |
||
1249 | __bit_iterator<_Dp, false> __result); |
||
1250 | template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first, |
||
1251 | __bit_iterator<_Dp, _IC> __last, |
||
1252 | __bit_iterator<_Dp, false> __result); |
||
1253 | template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>, |
||
1254 | __bit_iterator<__C1, false>, |
||
1255 | __bit_iterator<__C2, false>); |
||
1256 | template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>, |
||
1257 | __bit_iterator<__C1, false>, |
||
1258 | __bit_iterator<__C2, false>); |
||
1259 | template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>, |
||
1260 | __bit_iterator<__C1, false>, |
||
1261 | __bit_iterator<__C2, false>); |
||
1262 | template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>, |
||
1263 | __bit_iterator<_Dp, false>, |
||
1264 | __bit_iterator<_Dp, false>); |
||
1265 | template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>, |
||
1266 | __bit_iterator<_Dp, _IC1>, |
||
1267 | __bit_iterator<_Dp, _IC2>); |
||
1268 | template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>, |
||
1269 | __bit_iterator<_Dp, _IC1>, |
||
1270 | __bit_iterator<_Dp, _IC2>); |
||
1271 | template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>, |
||
1272 | __bit_iterator<_Dp, _IC1>, |
||
1273 | __bit_iterator<_Dp, _IC2>); |
||
1274 | template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>, |
||
1275 | typename _Dp::size_type); |
||
1276 | template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>, |
||
1277 | typename _Dp::size_type); |
||
1278 | template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type |
||
1279 | __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); |
||
1280 | template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type |
||
1281 | __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type); |
||
1282 | }; |
||
1283 | |||
1284 | _LIBCPP_END_NAMESPACE_STD |
||
1285 | |||
1286 | #endif // _LIBCPP___BIT_REFERENCE |