2 //===----------------------------------------------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP___BIT_REFERENCE
12 #define _LIBCPP___BIT_REFERENCE
17 #include <__undef_min_max>
19 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
20 #pragma GCC system_header
23 _LIBCPP_BEGIN_NAMESPACE_STD
25 template <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator;
26 template <class _Cp> class __bit_const_reference;
29 struct __has_storage_type
31 static const bool value = false;
34 template <class _Cp, bool = __has_storage_type<_Cp>::value>
37 typedef typename _Cp::__storage_type __storage_type;
38 typedef typename _Cp::__storage_pointer __storage_pointer;
40 __storage_pointer __seg_;
41 __storage_type __mask_;
43 friend typename _Cp::__self;
45 friend class __bit_const_reference<_Cp>;
46 friend class __bit_iterator<_Cp, false>;
48 _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT
49 {return static_cast<bool>(*__seg_ & __mask_);}
50 _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT
51 {return !static_cast<bool>(*this);}
53 _LIBCPP_INLINE_VISIBILITY
54 __bit_reference& operator=(bool __x) _NOEXCEPT
63 _LIBCPP_INLINE_VISIBILITY
64 __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT
65 {return operator=(static_cast<bool>(__x));}
67 _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;}
68 _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT
69 {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));}
71 _LIBCPP_INLINE_VISIBILITY
72 __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
73 : __seg_(__s), __mask_(__m) {}
77 class __bit_reference<_Cp, false>
82 inline _LIBCPP_INLINE_VISIBILITY
84 swap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT
91 template <class _Cp, class _Dp>
92 inline _LIBCPP_INLINE_VISIBILITY
94 swap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT
102 inline _LIBCPP_INLINE_VISIBILITY
104 swap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT
112 inline _LIBCPP_INLINE_VISIBILITY
114 swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT
122 class __bit_const_reference
124 typedef typename _Cp::__storage_type __storage_type;
125 typedef typename _Cp::__const_storage_pointer __storage_pointer;
127 __storage_pointer __seg_;
128 __storage_type __mask_;
130 friend typename _Cp::__self;
131 friend class __bit_iterator<_Cp, true>;
133 _LIBCPP_INLINE_VISIBILITY
134 __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT
135 : __seg_(__x.__seg_), __mask_(__x.__mask_) {}
137 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT
138 {return static_cast<bool>(*__seg_ & __mask_);}
140 _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT
141 {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));}
143 _LIBCPP_INLINE_VISIBILITY
145 __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
146 : __seg_(__s), __mask_(__m) {}
148 __bit_const_reference& operator=(const __bit_const_reference& __x);
153 template <class _Cp, bool _IsConst>
154 __bit_iterator<_Cp, _IsConst>
155 __find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
157 typedef __bit_iterator<_Cp, _IsConst> _It;
158 typedef typename _It::__storage_type __storage_type;
159 static const int __bits_per_word = _It::__bits_per_word;
160 // do first partial word
161 if (__first.__ctz_ != 0)
163 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
164 __storage_type __dn = _VSTD::min(__clz_f, __n);
165 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
166 __storage_type __b = *__first.__seg_ & __m;
168 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
170 return __first + __n;
174 // do middle whole words
175 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
177 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_)));
178 // do last partial word
181 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
182 __storage_type __b = *__first.__seg_ & __m;
184 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
186 return _It(__first.__seg_, static_cast<unsigned>(__n));
189 template <class _Cp, bool _IsConst>
190 __bit_iterator<_Cp, _IsConst>
191 __find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
193 typedef __bit_iterator<_Cp, _IsConst> _It;
194 typedef typename _It::__storage_type __storage_type;
195 const int __bits_per_word = _It::__bits_per_word;
196 // do first partial word
197 if (__first.__ctz_ != 0)
199 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
200 __storage_type __dn = _VSTD::min(__clz_f, __n);
201 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
202 __storage_type __b = ~*__first.__seg_ & __m;
204 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
206 return __first + __n;
210 // do middle whole words
211 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
213 __storage_type __b = ~*__first.__seg_;
215 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
217 // do last partial word
220 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
221 __storage_type __b = ~*__first.__seg_ & __m;
223 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
225 return _It(__first.__seg_, static_cast<unsigned>(__n));
228 template <class _Cp, bool _IsConst, class _Tp>
229 inline _LIBCPP_INLINE_VISIBILITY
230 __bit_iterator<_Cp, _IsConst>
231 find(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
233 if (static_cast<bool>(__value_))
234 return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
235 return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
240 template <class _Cp, bool _IsConst>
241 typename __bit_iterator<_Cp, _IsConst>::difference_type
242 __count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
244 typedef __bit_iterator<_Cp, _IsConst> _It;
245 typedef typename _It::__storage_type __storage_type;
246 typedef typename _It::difference_type difference_type;
247 const int __bits_per_word = _It::__bits_per_word;
248 difference_type __r = 0;
249 // do first partial word
250 if (__first.__ctz_ != 0)
252 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
253 __storage_type __dn = _VSTD::min(__clz_f, __n);
254 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
255 __r = _VSTD::__pop_count(*__first.__seg_ & __m);
259 // do middle whole words
260 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
261 __r += _VSTD::__pop_count(*__first.__seg_);
262 // do last partial word
265 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
266 __r += _VSTD::__pop_count(*__first.__seg_ & __m);
271 template <class _Cp, bool _IsConst>
272 typename __bit_iterator<_Cp, _IsConst>::difference_type
273 __count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
275 typedef __bit_iterator<_Cp, _IsConst> _It;
276 typedef typename _It::__storage_type __storage_type;
277 typedef typename _It::difference_type difference_type;
278 const int __bits_per_word = _It::__bits_per_word;
279 difference_type __r = 0;
280 // do first partial word
281 if (__first.__ctz_ != 0)
283 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
284 __storage_type __dn = _VSTD::min(__clz_f, __n);
285 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
286 __r = _VSTD::__pop_count(~*__first.__seg_ & __m);
290 // do middle whole words
291 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
292 __r += _VSTD::__pop_count(~*__first.__seg_);
293 // do last partial word
296 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
297 __r += _VSTD::__pop_count(~*__first.__seg_ & __m);
302 template <class _Cp, bool _IsConst, class _Tp>
303 inline _LIBCPP_INLINE_VISIBILITY
304 typename __bit_iterator<_Cp, _IsConst>::difference_type
305 count(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
307 if (static_cast<bool>(__value_))
308 return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
309 return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
316 __fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
318 typedef __bit_iterator<_Cp, false> _It;
319 typedef typename _It::__storage_type __storage_type;
320 const int __bits_per_word = _It::__bits_per_word;
321 // do first partial word
322 if (__first.__ctz_ != 0)
324 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
325 __storage_type __dn = _VSTD::min(__clz_f, __n);
326 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
327 *__first.__seg_ &= ~__m;
331 // do middle whole words
332 __storage_type __nw = __n / __bits_per_word;
333 _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), 0, __nw * sizeof(__storage_type));
334 __n -= __nw * __bits_per_word;
335 // do last partial word
338 __first.__seg_ += __nw;
339 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
340 *__first.__seg_ &= ~__m;
346 __fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
348 typedef __bit_iterator<_Cp, false> _It;
349 typedef typename _It::__storage_type __storage_type;
350 const int __bits_per_word = _It::__bits_per_word;
351 // do first partial word
352 if (__first.__ctz_ != 0)
354 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
355 __storage_type __dn = _VSTD::min(__clz_f, __n);
356 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
357 *__first.__seg_ |= __m;
361 // do middle whole words
362 __storage_type __nw = __n / __bits_per_word;
363 _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), -1, __nw * sizeof(__storage_type));
364 __n -= __nw * __bits_per_word;
365 // do last partial word
368 __first.__seg_ += __nw;
369 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
370 *__first.__seg_ |= __m;
375 inline _LIBCPP_INLINE_VISIBILITY
377 fill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_)
382 __fill_n_true(__first, __n);
384 __fill_n_false(__first, __n);
391 inline _LIBCPP_INLINE_VISIBILITY
393 fill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_)
395 _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_);
400 template <class _Cp, bool _IsConst>
401 __bit_iterator<_Cp, false>
402 __copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
403 __bit_iterator<_Cp, false> __result)
405 typedef __bit_iterator<_Cp, _IsConst> _In;
406 typedef typename _In::difference_type difference_type;
407 typedef typename _In::__storage_type __storage_type;
408 const int __bits_per_word = _In::__bits_per_word;
409 difference_type __n = __last - __first;
413 if (__first.__ctz_ != 0)
415 unsigned __clz = __bits_per_word - __first.__ctz_;
416 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
418 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
419 __storage_type __b = *__first.__seg_ & __m;
420 *__result.__seg_ &= ~__m;
421 *__result.__seg_ |= __b;
422 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
423 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
425 // __first.__ctz_ = 0;
427 // __first.__ctz_ == 0;
429 __storage_type __nw = __n / __bits_per_word;
430 _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_),
431 _VSTD::__to_raw_pointer(__first.__seg_),
432 __nw * sizeof(__storage_type));
433 __n -= __nw * __bits_per_word;
434 __result.__seg_ += __nw;
438 __first.__seg_ += __nw;
439 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
440 __storage_type __b = *__first.__seg_ & __m;
441 *__result.__seg_ &= ~__m;
442 *__result.__seg_ |= __b;
443 __result.__ctz_ = static_cast<unsigned>(__n);
449 template <class _Cp, bool _IsConst>
450 __bit_iterator<_Cp, false>
451 __copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
452 __bit_iterator<_Cp, false> __result)
454 typedef __bit_iterator<_Cp, _IsConst> _In;
455 typedef typename _In::difference_type difference_type;
456 typedef typename _In::__storage_type __storage_type;
457 static const int __bits_per_word = _In::__bits_per_word;
458 difference_type __n = __last - __first;
462 if (__first.__ctz_ != 0)
464 unsigned __clz_f = __bits_per_word - __first.__ctz_;
465 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
467 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
468 __storage_type __b = *__first.__seg_ & __m;
469 unsigned __clz_r = __bits_per_word - __result.__ctz_;
470 __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
471 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
472 *__result.__seg_ &= ~__m;
473 if (__result.__ctz_ > __first.__ctz_)
474 *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
476 *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
477 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
478 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
482 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
483 *__result.__seg_ &= ~__m;
484 *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
485 __result.__ctz_ = static_cast<unsigned>(__dn);
488 // __first.__ctz_ = 0;
490 // __first.__ctz_ == 0;
492 unsigned __clz_r = __bits_per_word - __result.__ctz_;
493 __storage_type __m = ~__storage_type(0) << __result.__ctz_;
494 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
496 __storage_type __b = *__first.__seg_;
497 *__result.__seg_ &= ~__m;
498 *__result.__seg_ |= __b << __result.__ctz_;
500 *__result.__seg_ &= __m;
501 *__result.__seg_ |= __b >> __clz_r;
506 __m = ~__storage_type(0) >> (__bits_per_word - __n);
507 __storage_type __b = *__first.__seg_ & __m;
508 __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
509 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
510 *__result.__seg_ &= ~__m;
511 *__result.__seg_ |= __b << __result.__ctz_;
512 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
513 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
517 __m = ~__storage_type(0) >> (__bits_per_word - __n);
518 *__result.__seg_ &= ~__m;
519 *__result.__seg_ |= __b >> __dn;
520 __result.__ctz_ = static_cast<unsigned>(__n);
527 template <class _Cp, bool _IsConst>
528 inline _LIBCPP_INLINE_VISIBILITY
529 __bit_iterator<_Cp, false>
530 copy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
532 if (__first.__ctz_ == __result.__ctz_)
533 return __copy_aligned(__first, __last, __result);
534 return __copy_unaligned(__first, __last, __result);
539 template <class _Cp, bool _IsConst>
540 __bit_iterator<_Cp, false>
541 __copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
542 __bit_iterator<_Cp, false> __result)
544 typedef __bit_iterator<_Cp, _IsConst> _In;
545 typedef typename _In::difference_type difference_type;
546 typedef typename _In::__storage_type __storage_type;
547 const int __bits_per_word = _In::__bits_per_word;
548 difference_type __n = __last - __first;
552 if (__last.__ctz_ != 0)
554 difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
556 unsigned __clz = __bits_per_word - __last.__ctz_;
557 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);
558 __storage_type __b = *__last.__seg_ & __m;
559 *__result.__seg_ &= ~__m;
560 *__result.__seg_ |= __b;
561 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
562 __result.__ctz_) % __bits_per_word);
565 // __last.__ctz_ == 0 || __n == 0
566 // __result.__ctz_ == 0 || __n == 0
568 __storage_type __nw = __n / __bits_per_word;
569 __result.__seg_ -= __nw;
570 __last.__seg_ -= __nw;
571 _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_),
572 _VSTD::__to_raw_pointer(__last.__seg_),
573 __nw * sizeof(__storage_type));
574 __n -= __nw * __bits_per_word;
578 __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);
579 __storage_type __b = *--__last.__seg_ & __m;
580 *--__result.__seg_ &= ~__m;
581 *__result.__seg_ |= __b;
582 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
588 template <class _Cp, bool _IsConst>
589 __bit_iterator<_Cp, false>
590 __copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
591 __bit_iterator<_Cp, false> __result)
593 typedef __bit_iterator<_Cp, _IsConst> _In;
594 typedef typename _In::difference_type difference_type;
595 typedef typename _In::__storage_type __storage_type;
596 const int __bits_per_word = _In::__bits_per_word;
597 difference_type __n = __last - __first;
601 if (__last.__ctz_ != 0)
603 difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
605 unsigned __clz_l = __bits_per_word - __last.__ctz_;
606 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);
607 __storage_type __b = *__last.__seg_ & __m;
608 unsigned __clz_r = __bits_per_word - __result.__ctz_;
609 __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_));
612 __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);
613 *__result.__seg_ &= ~__m;
614 if (__result.__ctz_ > __last.__ctz_)
615 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
617 *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
618 __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) +
619 __result.__ctz_) % __bits_per_word);
624 // __result.__ctz_ == 0
626 __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
627 __m = ~__storage_type(0) << __result.__ctz_;
628 *__result.__seg_ &= ~__m;
629 __last.__ctz_ -= __dn + __ddn;
630 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
634 // __last.__ctz_ == 0 || __n == 0
635 // __result.__ctz_ != 0 || __n == 0
637 unsigned __clz_r = __bits_per_word - __result.__ctz_;
638 __storage_type __m = ~__storage_type(0) >> __clz_r;
639 for (; __n >= __bits_per_word; __n -= __bits_per_word)
641 __storage_type __b = *--__last.__seg_;
642 *__result.__seg_ &= ~__m;
643 *__result.__seg_ |= __b >> __clz_r;
644 *--__result.__seg_ &= __m;
645 *__result.__seg_ |= __b << __result.__ctz_;
650 __m = ~__storage_type(0) << (__bits_per_word - __n);
651 __storage_type __b = *--__last.__seg_ & __m;
652 __clz_r = __bits_per_word - __result.__ctz_;
653 __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_));
654 __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);
655 *__result.__seg_ &= ~__m;
656 *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
657 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
658 __result.__ctz_) % __bits_per_word);
662 // __result.__ctz_ == 0
664 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
665 __m = ~__storage_type(0) << __result.__ctz_;
666 *__result.__seg_ &= ~__m;
667 *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
674 template <class _Cp, bool _IsConst>
675 inline _LIBCPP_INLINE_VISIBILITY
676 __bit_iterator<_Cp, false>
677 copy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
679 if (__last.__ctz_ == __result.__ctz_)
680 return __copy_backward_aligned(__first, __last, __result);
681 return __copy_backward_unaligned(__first, __last, __result);
686 template <class _Cp, bool _IsConst>
687 inline _LIBCPP_INLINE_VISIBILITY
688 __bit_iterator<_Cp, false>
689 move(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
691 return _VSTD::copy(__first, __last, __result);
696 template <class _Cp, bool _IsConst>
697 inline _LIBCPP_INLINE_VISIBILITY
698 __bit_iterator<_Cp, false>
699 move_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
701 return _VSTD::copy_backward(__first, __last, __result);
706 template <class __C1, class __C2>
707 __bit_iterator<__C2, false>
708 __swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
709 __bit_iterator<__C2, false> __result)
711 typedef __bit_iterator<__C1, false> _I1;
712 typedef typename _I1::difference_type difference_type;
713 typedef typename _I1::__storage_type __storage_type;
714 const int __bits_per_word = _I1::__bits_per_word;
715 difference_type __n = __last - __first;
719 if (__first.__ctz_ != 0)
721 unsigned __clz = __bits_per_word - __first.__ctz_;
722 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
724 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
725 __storage_type __b1 = *__first.__seg_ & __m;
726 *__first.__seg_ &= ~__m;
727 __storage_type __b2 = *__result.__seg_ & __m;
728 *__result.__seg_ &= ~__m;
729 *__result.__seg_ |= __b1;
730 *__first.__seg_ |= __b2;
731 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
732 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
734 // __first.__ctz_ = 0;
736 // __first.__ctz_ == 0;
738 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)
739 swap(*__first.__seg_, *__result.__seg_);
743 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
744 __storage_type __b1 = *__first.__seg_ & __m;
745 *__first.__seg_ &= ~__m;
746 __storage_type __b2 = *__result.__seg_ & __m;
747 *__result.__seg_ &= ~__m;
748 *__result.__seg_ |= __b1;
749 *__first.__seg_ |= __b2;
750 __result.__ctz_ = static_cast<unsigned>(__n);
756 template <class __C1, class __C2>
757 __bit_iterator<__C2, false>
758 __swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
759 __bit_iterator<__C2, false> __result)
761 typedef __bit_iterator<__C1, false> _I1;
762 typedef typename _I1::difference_type difference_type;
763 typedef typename _I1::__storage_type __storage_type;
764 const int __bits_per_word = _I1::__bits_per_word;
765 difference_type __n = __last - __first;
769 if (__first.__ctz_ != 0)
771 unsigned __clz_f = __bits_per_word - __first.__ctz_;
772 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
774 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
775 __storage_type __b1 = *__first.__seg_ & __m;
776 *__first.__seg_ &= ~__m;
777 unsigned __clz_r = __bits_per_word - __result.__ctz_;
778 __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
779 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
780 __storage_type __b2 = *__result.__seg_ & __m;
781 *__result.__seg_ &= ~__m;
782 if (__result.__ctz_ > __first.__ctz_)
784 unsigned __s = __result.__ctz_ - __first.__ctz_;
785 *__result.__seg_ |= __b1 << __s;
786 *__first.__seg_ |= __b2 >> __s;
790 unsigned __s = __first.__ctz_ - __result.__ctz_;
791 *__result.__seg_ |= __b1 >> __s;
792 *__first.__seg_ |= __b2 << __s;
794 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
795 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
799 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
800 __b2 = *__result.__seg_ & __m;
801 *__result.__seg_ &= ~__m;
802 unsigned __s = __first.__ctz_ + __ddn;
803 *__result.__seg_ |= __b1 >> __s;
804 *__first.__seg_ |= __b2 << __s;
805 __result.__ctz_ = static_cast<unsigned>(__dn);
808 // __first.__ctz_ = 0;
810 // __first.__ctz_ == 0;
812 __storage_type __m = ~__storage_type(0) << __result.__ctz_;
813 unsigned __clz_r = __bits_per_word - __result.__ctz_;
814 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
816 __storage_type __b1 = *__first.__seg_;
817 __storage_type __b2 = *__result.__seg_ & __m;
818 *__result.__seg_ &= ~__m;
819 *__result.__seg_ |= __b1 << __result.__ctz_;
820 *__first.__seg_ = __b2 >> __result.__ctz_;
822 __b2 = *__result.__seg_ & ~__m;
823 *__result.__seg_ &= __m;
824 *__result.__seg_ |= __b1 >> __clz_r;
825 *__first.__seg_ |= __b2 << __clz_r;
830 __m = ~__storage_type(0) >> (__bits_per_word - __n);
831 __storage_type __b1 = *__first.__seg_ & __m;
832 *__first.__seg_ &= ~__m;
833 __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r);
834 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
835 __storage_type __b2 = *__result.__seg_ & __m;
836 *__result.__seg_ &= ~__m;
837 *__result.__seg_ |= __b1 << __result.__ctz_;
838 *__first.__seg_ |= __b2 >> __result.__ctz_;
839 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
840 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
844 __m = ~__storage_type(0) >> (__bits_per_word - __n);
845 __b2 = *__result.__seg_ & __m;
846 *__result.__seg_ &= ~__m;
847 *__result.__seg_ |= __b1 >> __dn;
848 *__first.__seg_ |= __b2 << __dn;
849 __result.__ctz_ = static_cast<unsigned>(__n);
856 template <class __C1, class __C2>
857 inline _LIBCPP_INLINE_VISIBILITY
858 __bit_iterator<__C2, false>
859 swap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1,
860 __bit_iterator<__C2, false> __first2)
862 if (__first1.__ctz_ == __first2.__ctz_)
863 return __swap_ranges_aligned(__first1, __last1, __first2);
864 return __swap_ranges_unaligned(__first1, __last1, __first2);
872 typedef typename _Cp::difference_type difference_type;
873 typedef typename _Cp::__storage_type __storage_type;
874 typedef typename _Cp::__storage_pointer __storage_pointer;
875 typedef typename _Cp::iterator iterator;
876 static const unsigned __bits_per_word = _Cp::__bits_per_word;
877 static const unsigned _Np = 4;
879 difference_type __size_;
880 __storage_type __word_[_Np];
882 _LIBCPP_INLINE_VISIBILITY static difference_type capacity()
883 {return static_cast<difference_type>(_Np * __bits_per_word);}
884 _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {}
885 _LIBCPP_INLINE_VISIBILITY iterator begin()
887 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0);
889 _LIBCPP_INLINE_VISIBILITY iterator end()
891 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word,
892 static_cast<unsigned>(__size_ % __bits_per_word));
897 __bit_iterator<_Cp, false>
898 rotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last)
900 typedef __bit_iterator<_Cp, false> _I1;
901 typedef typename _I1::difference_type difference_type;
902 difference_type __d1 = __middle - __first;
903 difference_type __d2 = __last - __middle;
904 _I1 __r = __first + __d2;
905 while (__d1 != 0 && __d2 != 0)
909 if (__d1 <= __bit_array<_Cp>::capacity())
911 __bit_array<_Cp> __b(__d1);
912 _VSTD::copy(__first, __middle, __b.begin());
913 _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first));
918 __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle);
926 if (__d2 <= __bit_array<_Cp>::capacity())
928 __bit_array<_Cp> __b(__d2);
929 _VSTD::copy(__middle, __last, __b.begin());
930 _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last));
935 __bit_iterator<_Cp, false> __mp = __first + __d2;
936 _VSTD::swap_ranges(__first, __mp, __middle);
947 template <class _Cp, bool _IC1, bool _IC2>
949 __equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
950 __bit_iterator<_Cp, _IC2> __first2)
952 typedef __bit_iterator<_Cp, _IC1> _It;
953 typedef typename _It::difference_type difference_type;
954 typedef typename _It::__storage_type __storage_type;
955 static const int __bits_per_word = _It::__bits_per_word;
956 difference_type __n = __last1 - __first1;
960 if (__first1.__ctz_ != 0)
962 unsigned __clz_f = __bits_per_word - __first1.__ctz_;
963 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
965 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
966 __storage_type __b = *__first1.__seg_ & __m;
967 unsigned __clz_r = __bits_per_word - __first2.__ctz_;
968 __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
969 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
970 if (__first2.__ctz_ > __first1.__ctz_)
972 if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
977 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
980 __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
981 __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word);
985 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
986 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
988 __first2.__ctz_ = static_cast<unsigned>(__dn);
991 // __first1.__ctz_ = 0;
993 // __first1.__ctz_ == 0;
995 unsigned __clz_r = __bits_per_word - __first2.__ctz_;
996 __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
997 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_)
999 __storage_type __b = *__first1.__seg_;
1000 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
1003 if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))
1009 __m = ~__storage_type(0) >> (__bits_per_word - __n);
1010 __storage_type __b = *__first1.__seg_ & __m;
1011 __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
1012 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
1013 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
1015 __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
1016 __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word);
1020 __m = ~__storage_type(0) >> (__bits_per_word - __n);
1021 if ((*__first2.__seg_ & __m) != (__b >> __dn))
1029 template <class _Cp, bool _IC1, bool _IC2>
1031 __equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
1032 __bit_iterator<_Cp, _IC2> __first2)
1034 typedef __bit_iterator<_Cp, _IC1> _It;
1035 typedef typename _It::difference_type difference_type;
1036 typedef typename _It::__storage_type __storage_type;
1037 static const int __bits_per_word = _It::__bits_per_word;
1038 difference_type __n = __last1 - __first1;
1042 if (__first1.__ctz_ != 0)
1044 unsigned __clz = __bits_per_word - __first1.__ctz_;
1045 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
1047 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
1048 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
1052 // __first1.__ctz_ = 0;
1053 // __first2.__ctz_ = 0;
1055 // __first1.__ctz_ == 0;
1056 // __first2.__ctz_ == 0;
1058 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
1059 if (*__first2.__seg_ != *__first1.__seg_)
1064 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
1065 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
1072 template <class _Cp, bool _IC1, bool _IC2>
1073 inline _LIBCPP_INLINE_VISIBILITY
1075 equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2)
1077 if (__first1.__ctz_ == __first2.__ctz_)
1078 return __equal_aligned(__first1, __last1, __first2);
1079 return __equal_unaligned(__first1, __last1, __first2);
1082 template <class _Cp, bool _IsConst,
1083 typename _Cp::__storage_type>
1084 class __bit_iterator
1087 typedef typename _Cp::difference_type difference_type;
1088 typedef bool value_type;
1089 typedef __bit_iterator pointer;
1090 typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference;
1091 typedef random_access_iterator_tag iterator_category;
1094 typedef typename _Cp::__storage_type __storage_type;
1095 typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer,
1096 typename _Cp::__storage_pointer>::type __storage_pointer;
1097 static const unsigned __bits_per_word = _Cp::__bits_per_word;
1099 __storage_pointer __seg_;
1103 _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT
1104 #if _LIBCPP_STD_VER > 11
1105 : __seg_(nullptr), __ctz_(0)
1109 _LIBCPP_INLINE_VISIBILITY
1110 __bit_iterator(const __bit_iterator<_Cp, false>& __it) _NOEXCEPT
1111 : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
1113 _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
1114 {return reference(__seg_, __storage_type(1) << __ctz_);}
1116 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++()
1118 if (__ctz_ != __bits_per_word-1)
1128 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int)
1130 __bit_iterator __tmp = *this;
1135 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--()
1141 __ctz_ = __bits_per_word - 1;
1147 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int)
1149 __bit_iterator __tmp = *this;
1154 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n)
1157 __seg_ += (__n + __ctz_) / __bits_per_word;
1159 __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1)
1160 / static_cast<difference_type>(__bits_per_word);
1161 __n &= (__bits_per_word - 1);
1162 __ctz_ = static_cast<unsigned>((__n + __ctz_) % __bits_per_word);
1166 _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n)
1168 return *this += -__n;
1171 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator+(difference_type __n) const
1173 __bit_iterator __t(*this);
1178 _LIBCPP_INLINE_VISIBILITY __bit_iterator operator-(difference_type __n) const
1180 __bit_iterator __t(*this);
1185 _LIBCPP_INLINE_VISIBILITY
1186 friend __bit_iterator operator+(difference_type __n, const __bit_iterator& __it) {return __it + __n;}
1188 _LIBCPP_INLINE_VISIBILITY
1189 friend difference_type operator-(const __bit_iterator& __x, const __bit_iterator& __y)
1190 {return (__x.__seg_ - __y.__seg_) * __bits_per_word + __x.__ctz_ - __y.__ctz_;}
1192 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const {return *(*this + __n);}
1194 _LIBCPP_INLINE_VISIBILITY friend bool operator==(const __bit_iterator& __x, const __bit_iterator& __y)
1195 {return __x.__seg_ == __y.__seg_ && __x.__ctz_ == __y.__ctz_;}
1197 _LIBCPP_INLINE_VISIBILITY friend bool operator!=(const __bit_iterator& __x, const __bit_iterator& __y)
1198 {return !(__x == __y);}
1200 _LIBCPP_INLINE_VISIBILITY friend bool operator<(const __bit_iterator& __x, const __bit_iterator& __y)
1201 {return __x.__seg_ < __y.__seg_ || (__x.__seg_ == __y.__seg_ && __x.__ctz_ < __y.__ctz_);}
1203 _LIBCPP_INLINE_VISIBILITY friend bool operator>(const __bit_iterator& __x, const __bit_iterator& __y)
1206 _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y)
1207 {return !(__y < __x);}
1209 _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y)
1210 {return !(__x < __y);}
1213 _LIBCPP_INLINE_VISIBILITY
1214 __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT
1215 : __seg_(__s), __ctz_(__ctz) {}
1217 friend typename _Cp::__self;
1219 friend class __bit_reference<_Cp>;
1220 friend class __bit_const_reference<_Cp>;
1221 friend class __bit_iterator<_Cp, true>;
1222 template <class _Dp> friend struct __bit_array;
1223 template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1224 template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1225 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__bit_iterator<_Dp, _IC> __first,
1226 __bit_iterator<_Dp, _IC> __last,
1227 __bit_iterator<_Dp, false> __result);
1228 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_unaligned(__bit_iterator<_Dp, _IC> __first,
1229 __bit_iterator<_Dp, _IC> __last,
1230 __bit_iterator<_Dp, false> __result);
1231 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy(__bit_iterator<_Dp, _IC> __first,
1232 __bit_iterator<_Dp, _IC> __last,
1233 __bit_iterator<_Dp, false> __result);
1234 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_aligned(__bit_iterator<_Dp, _IC> __first,
1235 __bit_iterator<_Dp, _IC> __last,
1236 __bit_iterator<_Dp, false> __result);
1237 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_backward_unaligned(__bit_iterator<_Dp, _IC> __first,
1238 __bit_iterator<_Dp, _IC> __last,
1239 __bit_iterator<_Dp, false> __result);
1240 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first,
1241 __bit_iterator<_Dp, _IC> __last,
1242 __bit_iterator<_Dp, false> __result);
1243 template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__bit_iterator<__C1, false>,
1244 __bit_iterator<__C1, false>,
1245 __bit_iterator<__C2, false>);
1246 template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_unaligned(__bit_iterator<__C1, false>,
1247 __bit_iterator<__C1, false>,
1248 __bit_iterator<__C2, false>);
1249 template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>,
1250 __bit_iterator<__C1, false>,
1251 __bit_iterator<__C2, false>);
1252 template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>,
1253 __bit_iterator<_Dp, false>,
1254 __bit_iterator<_Dp, false>);
1255 template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__bit_iterator<_Dp, _IC1>,
1256 __bit_iterator<_Dp, _IC1>,
1257 __bit_iterator<_Dp, _IC2>);
1258 template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_unaligned(__bit_iterator<_Dp, _IC1>,
1259 __bit_iterator<_Dp, _IC1>,
1260 __bit_iterator<_Dp, _IC2>);
1261 template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>,
1262 __bit_iterator<_Dp, _IC1>,
1263 __bit_iterator<_Dp, _IC2>);
1264 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>,
1265 typename _Dp::size_type);
1266 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>,
1267 typename _Dp::size_type);
1268 template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1269 __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1270 template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1271 __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1274 _LIBCPP_END_NAMESPACE_STD
1276 #endif // _LIBCPP___BIT_REFERENCE