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