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 #if defined(__clang__)
44 friend typename _Cp::__self;
46 friend class _Cp::__self;
48 friend class __bit_const_reference<_Cp>;
49 friend class __bit_iterator<_Cp, false>;
51 _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT
52 {return static_cast<bool>(*__seg_ & __mask_);}
53 _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT
54 {return !static_cast<bool>(*this);}
56 _LIBCPP_INLINE_VISIBILITY
57 __bit_reference& operator=(bool __x) _NOEXCEPT
66 _LIBCPP_INLINE_VISIBILITY
67 __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT
68 {return operator=(static_cast<bool>(__x));}
70 _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;}
71 _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT
72 {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));}
74 _LIBCPP_INLINE_VISIBILITY
75 __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
76 : __seg_(__s), __mask_(__m) {}
80 class __bit_reference<_Cp, false>
85 _LIBCPP_INLINE_VISIBILITY inline
87 swap(__bit_reference<_Cp> __x, __bit_reference<_Cp> __y) _NOEXCEPT
94 template <class _Cp, class _Dp>
95 _LIBCPP_INLINE_VISIBILITY inline
97 swap(__bit_reference<_Cp> __x, __bit_reference<_Dp> __y) _NOEXCEPT
105 _LIBCPP_INLINE_VISIBILITY inline
107 swap(__bit_reference<_Cp> __x, bool& __y) _NOEXCEPT
115 _LIBCPP_INLINE_VISIBILITY inline
117 swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT
125 class __bit_const_reference
127 typedef typename _Cp::__storage_type __storage_type;
128 typedef typename _Cp::__const_storage_pointer __storage_pointer;
130 __storage_pointer __seg_;
131 __storage_type __mask_;
133 #if defined(__clang__)
134 friend typename _Cp::__self;
136 friend class _Cp::__self;
138 friend class __bit_iterator<_Cp, true>;
140 _LIBCPP_INLINE_VISIBILITY
141 __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT
142 : __seg_(__x.__seg_), __mask_(__x.__mask_) {}
144 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT
145 {return static_cast<bool>(*__seg_ & __mask_);}
147 _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT
148 {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));}
150 _LIBCPP_INLINE_VISIBILITY
152 __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
153 : __seg_(__s), __mask_(__m) {}
155 __bit_const_reference& operator=(const __bit_const_reference& __x);
160 template <class _Cp, bool _IsConst>
161 __bit_iterator<_Cp, _IsConst>
162 __find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
164 typedef __bit_iterator<_Cp, _IsConst> _It;
165 typedef typename _It::__storage_type __storage_type;
166 static const unsigned __bits_per_word = _It::__bits_per_word;
167 // do first partial word
168 if (__first.__ctz_ != 0)
170 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
171 __storage_type __dn = _VSTD::min(__clz_f, __n);
172 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
173 __storage_type __b = *__first.__seg_ & __m;
175 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
179 // do middle whole words
180 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
182 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_)));
183 // do last partial word
186 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
187 __storage_type __b = *__first.__seg_ & __m;
189 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
191 return _It(__first.__seg_, static_cast<unsigned>(__n));
194 template <class _Cp, bool _IsConst>
195 __bit_iterator<_Cp, _IsConst>
196 __find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
198 typedef __bit_iterator<_Cp, _IsConst> _It;
199 typedef typename _It::__storage_type __storage_type;
200 static const unsigned __bits_per_word = _It::__bits_per_word;
201 // do first partial word
202 if (__first.__ctz_ != 0)
204 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
205 __storage_type __dn = _VSTD::min(__clz_f, __n);
206 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
207 __storage_type __b = ~*__first.__seg_ & __m;
209 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
213 // do middle whole words
214 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
216 __storage_type __b = ~*__first.__seg_;
218 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
220 // do last partial word
223 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
224 __storage_type __b = ~*__first.__seg_ & __m;
226 return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
228 return _It(__first.__seg_, static_cast<unsigned>(__n));
231 template <class _Cp, bool _IsConst, class _Tp>
232 inline _LIBCPP_INLINE_VISIBILITY
233 __bit_iterator<_Cp, _IsConst>
234 find(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
236 if (static_cast<bool>(__value_))
237 return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
238 return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
243 template <class _Cp, bool _IsConst>
244 typename __bit_iterator<_Cp, _IsConst>::difference_type
245 __count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
247 typedef __bit_iterator<_Cp, _IsConst> _It;
248 typedef typename _It::__storage_type __storage_type;
249 typedef typename _It::difference_type difference_type;
250 static const unsigned __bits_per_word = _It::__bits_per_word;
251 difference_type __r = 0;
252 // do first partial word
253 if (__first.__ctz_ != 0)
255 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
256 __storage_type __dn = _VSTD::min(__clz_f, __n);
257 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
258 __r = _VSTD::__pop_count(*__first.__seg_ & __m);
262 // do middle whole words
263 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
264 __r += _VSTD::__pop_count(*__first.__seg_);
265 // do last partial word
268 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
269 __r += _VSTD::__pop_count(*__first.__seg_ & __m);
274 template <class _Cp, bool _IsConst>
275 typename __bit_iterator<_Cp, _IsConst>::difference_type
276 __count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
278 typedef __bit_iterator<_Cp, _IsConst> _It;
279 typedef typename _It::__storage_type __storage_type;
280 typedef typename _It::difference_type difference_type;
281 static const unsigned __bits_per_word = _It::__bits_per_word;
282 difference_type __r = 0;
283 // do first partial word
284 if (__first.__ctz_ != 0)
286 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
287 __storage_type __dn = _VSTD::min(__clz_f, __n);
288 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
289 __r = _VSTD::__pop_count(~*__first.__seg_ & __m);
293 // do middle whole words
294 for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
295 __r += _VSTD::__pop_count(~*__first.__seg_);
296 // do last partial word
299 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
300 __r += _VSTD::__pop_count(~*__first.__seg_ & __m);
305 template <class _Cp, bool _IsConst, class _Tp>
306 inline _LIBCPP_INLINE_VISIBILITY
307 typename __bit_iterator<_Cp, _IsConst>::difference_type
308 count(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
310 if (static_cast<bool>(__value_))
311 return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
312 return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
319 __fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
321 typedef __bit_iterator<_Cp, false> _It;
322 typedef typename _It::__storage_type __storage_type;
323 static const unsigned __bits_per_word = _It::__bits_per_word;
324 // do first partial word
325 if (__first.__ctz_ != 0)
327 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
328 __storage_type __dn = _VSTD::min(__clz_f, __n);
329 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
330 *__first.__seg_ &= ~__m;
334 // do middle whole words
335 __storage_type __nw = __n / __bits_per_word;
336 _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), 0, __nw * sizeof(__storage_type));
337 __n -= __nw * __bits_per_word;
338 // do last partial word
341 __first.__seg_ += __nw;
342 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
343 *__first.__seg_ &= ~__m;
349 __fill_n_true(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
351 typedef __bit_iterator<_Cp, false> _It;
352 typedef typename _It::__storage_type __storage_type;
353 static const unsigned __bits_per_word = _It::__bits_per_word;
354 // do first partial word
355 if (__first.__ctz_ != 0)
357 __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
358 __storage_type __dn = _VSTD::min(__clz_f, __n);
359 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
360 *__first.__seg_ |= __m;
364 // do middle whole words
365 __storage_type __nw = __n / __bits_per_word;
366 _VSTD::memset(_VSTD::__to_raw_pointer(__first.__seg_), -1, __nw * sizeof(__storage_type));
367 __n -= __nw * __bits_per_word;
368 // do last partial word
371 __first.__seg_ += __nw;
372 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
373 *__first.__seg_ |= __m;
378 _LIBCPP_INLINE_VISIBILITY inline
380 fill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_)
385 __fill_n_true(__first, __n);
387 __fill_n_false(__first, __n);
394 inline _LIBCPP_INLINE_VISIBILITY
396 fill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_)
398 _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_);
403 template <class _Cp, bool _IsConst>
404 __bit_iterator<_Cp, false>
405 __copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
406 __bit_iterator<_Cp, false> __result)
408 typedef __bit_iterator<_Cp, _IsConst> _In;
409 typedef typename _In::difference_type difference_type;
410 typedef typename _In::__storage_type __storage_type;
411 static const unsigned __bits_per_word = _In::__bits_per_word;
412 difference_type __n = __last - __first;
416 if (__first.__ctz_ != 0)
418 unsigned __clz = __bits_per_word - __first.__ctz_;
419 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
421 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
422 __storage_type __b = *__first.__seg_ & __m;
423 *__result.__seg_ &= ~__m;
424 *__result.__seg_ |= __b;
425 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
426 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
428 // __first.__ctz_ = 0;
430 // __first.__ctz_ == 0;
432 __storage_type __nw = __n / __bits_per_word;
433 _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_),
434 _VSTD::__to_raw_pointer(__first.__seg_),
435 __nw * sizeof(__storage_type));
436 __n -= __nw * __bits_per_word;
437 __result.__seg_ += __nw;
441 __first.__seg_ += __nw;
442 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
443 __storage_type __b = *__first.__seg_ & __m;
444 *__result.__seg_ &= ~__m;
445 *__result.__seg_ |= __b;
446 __result.__ctz_ = static_cast<unsigned>(__n);
452 template <class _Cp, bool _IsConst>
453 __bit_iterator<_Cp, false>
454 __copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
455 __bit_iterator<_Cp, false> __result)
457 typedef __bit_iterator<_Cp, _IsConst> _In;
458 typedef typename _In::difference_type difference_type;
459 typedef typename _In::__storage_type __storage_type;
460 static const unsigned __bits_per_word = _In::__bits_per_word;
461 difference_type __n = __last - __first;
465 if (__first.__ctz_ != 0)
467 unsigned __clz_f = __bits_per_word - __first.__ctz_;
468 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
470 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
471 __storage_type __b = *__first.__seg_ & __m;
472 unsigned __clz_r = __bits_per_word - __result.__ctz_;
473 __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
474 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
475 *__result.__seg_ &= ~__m;
476 if (__result.__ctz_ > __first.__ctz_)
477 *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
479 *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
480 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
481 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
485 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
486 *__result.__seg_ &= ~__m;
487 *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
488 __result.__ctz_ = static_cast<unsigned>(__dn);
491 // __first.__ctz_ = 0;
493 // __first.__ctz_ == 0;
495 unsigned __clz_r = __bits_per_word - __result.__ctz_;
496 __storage_type __m = ~__storage_type(0) << __result.__ctz_;
497 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
499 __storage_type __b = *__first.__seg_;
500 *__result.__seg_ &= ~__m;
501 *__result.__seg_ |= __b << __result.__ctz_;
503 *__result.__seg_ &= __m;
504 *__result.__seg_ |= __b >> __clz_r;
509 __m = ~__storage_type(0) >> (__bits_per_word - __n);
510 __storage_type __b = *__first.__seg_ & __m;
511 __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
512 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
513 *__result.__seg_ &= ~__m;
514 *__result.__seg_ |= __b << __result.__ctz_;
515 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
516 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
520 __m = ~__storage_type(0) >> (__bits_per_word - __n);
521 *__result.__seg_ &= ~__m;
522 *__result.__seg_ |= __b >> __dn;
523 __result.__ctz_ = static_cast<unsigned>(__n);
530 template <class _Cp, bool _IsConst>
531 inline _LIBCPP_INLINE_VISIBILITY
532 __bit_iterator<_Cp, false>
533 copy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
535 if (__first.__ctz_ == __result.__ctz_)
536 return __copy_aligned(__first, __last, __result);
537 return __copy_unaligned(__first, __last, __result);
542 template <class _Cp, bool _IsConst>
543 __bit_iterator<_Cp, false>
544 __copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
545 __bit_iterator<_Cp, false> __result)
547 typedef __bit_iterator<_Cp, _IsConst> _In;
548 typedef typename _In::difference_type difference_type;
549 typedef typename _In::__storage_type __storage_type;
550 static const unsigned __bits_per_word = _In::__bits_per_word;
551 difference_type __n = __last - __first;
555 if (__last.__ctz_ != 0)
557 difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
559 unsigned __clz = __bits_per_word - __last.__ctz_;
560 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);
561 __storage_type __b = *__last.__seg_ & __m;
562 *__result.__seg_ &= ~__m;
563 *__result.__seg_ |= __b;
564 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
565 __result.__ctz_) % __bits_per_word);
568 // __last.__ctz_ == 0 || __n == 0
569 // __result.__ctz_ == 0 || __n == 0
571 __storage_type __nw = __n / __bits_per_word;
572 __result.__seg_ -= __nw;
573 __last.__seg_ -= __nw;
574 _VSTD::memmove(_VSTD::__to_raw_pointer(__result.__seg_),
575 _VSTD::__to_raw_pointer(__last.__seg_),
576 __nw * sizeof(__storage_type));
577 __n -= __nw * __bits_per_word;
581 __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);
582 __storage_type __b = *--__last.__seg_ & __m;
583 *--__result.__seg_ &= ~__m;
584 *__result.__seg_ |= __b;
585 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
591 template <class _Cp, bool _IsConst>
592 __bit_iterator<_Cp, false>
593 __copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
594 __bit_iterator<_Cp, false> __result)
596 typedef __bit_iterator<_Cp, _IsConst> _In;
597 typedef typename _In::difference_type difference_type;
598 typedef typename _In::__storage_type __storage_type;
599 static const unsigned __bits_per_word = _In::__bits_per_word;
600 difference_type __n = __last - __first;
604 if (__last.__ctz_ != 0)
606 difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
608 unsigned __clz_l = __bits_per_word - __last.__ctz_;
609 __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);
610 __storage_type __b = *__last.__seg_ & __m;
611 unsigned __clz_r = __bits_per_word - __result.__ctz_;
612 __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_));
615 __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);
616 *__result.__seg_ &= ~__m;
617 if (__result.__ctz_ > __last.__ctz_)
618 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
620 *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
621 __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) +
622 __result.__ctz_) % __bits_per_word);
627 // __result.__ctz_ == 0
629 __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
630 __m = ~__storage_type(0) << __result.__ctz_;
631 *__result.__seg_ &= ~__m;
632 __last.__ctz_ -= __dn + __ddn;
633 *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
637 // __last.__ctz_ == 0 || __n == 0
638 // __result.__ctz_ != 0 || __n == 0
640 unsigned __clz_r = __bits_per_word - __result.__ctz_;
641 __storage_type __m = ~__storage_type(0) >> __clz_r;
642 for (; __n >= __bits_per_word; __n -= __bits_per_word)
644 __storage_type __b = *--__last.__seg_;
645 *__result.__seg_ &= ~__m;
646 *__result.__seg_ |= __b >> __clz_r;
647 *--__result.__seg_ &= __m;
648 *__result.__seg_ |= __b << __result.__ctz_;
653 __m = ~__storage_type(0) << (__bits_per_word - __n);
654 __storage_type __b = *--__last.__seg_ & __m;
655 __clz_r = __bits_per_word - __result.__ctz_;
656 __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_));
657 __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);
658 *__result.__seg_ &= ~__m;
659 *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
660 __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
661 __result.__ctz_) % __bits_per_word);
665 // __result.__ctz_ == 0
667 __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
668 __m = ~__storage_type(0) << __result.__ctz_;
669 *__result.__seg_ &= ~__m;
670 *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
677 template <class _Cp, bool _IsConst>
678 inline _LIBCPP_INLINE_VISIBILITY
679 __bit_iterator<_Cp, false>
680 copy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
682 if (__last.__ctz_ == __result.__ctz_)
683 return __copy_backward_aligned(__first, __last, __result);
684 return __copy_backward_unaligned(__first, __last, __result);
689 template <class _Cp, bool _IsConst>
690 inline _LIBCPP_INLINE_VISIBILITY
691 __bit_iterator<_Cp, false>
692 move(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
694 return _VSTD::copy(__first, __last, __result);
699 template <class _Cp, bool _IsConst>
700 inline _LIBCPP_INLINE_VISIBILITY
701 __bit_iterator<_Cp, false>
702 move_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
704 return _VSTD::copy(__first, __last, __result);
709 template <class __C1, class __C2>
710 __bit_iterator<__C2, false>
711 __swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
712 __bit_iterator<__C2, false> __result)
714 typedef __bit_iterator<__C1, false> _I1;
715 typedef typename _I1::difference_type difference_type;
716 typedef typename _I1::__storage_type __storage_type;
717 static const unsigned __bits_per_word = _I1::__bits_per_word;
718 difference_type __n = __last - __first;
722 if (__first.__ctz_ != 0)
724 unsigned __clz = __bits_per_word - __first.__ctz_;
725 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
727 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
728 __storage_type __b1 = *__first.__seg_ & __m;
729 *__first.__seg_ &= ~__m;
730 __storage_type __b2 = *__result.__seg_ & __m;
731 *__result.__seg_ &= ~__m;
732 *__result.__seg_ |= __b1;
733 *__first.__seg_ |= __b2;
734 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
735 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
737 // __first.__ctz_ = 0;
739 // __first.__ctz_ == 0;
741 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)
742 swap(*__first.__seg_, *__result.__seg_);
746 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
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.__ctz_ = static_cast<unsigned>(__n);
759 template <class __C1, class __C2>
760 __bit_iterator<__C2, false>
761 __swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
762 __bit_iterator<__C2, false> __result)
764 typedef __bit_iterator<__C1, false> _I1;
765 typedef typename _I1::difference_type difference_type;
766 typedef typename _I1::__storage_type __storage_type;
767 static const unsigned __bits_per_word = _I1::__bits_per_word;
768 difference_type __n = __last - __first;
772 if (__first.__ctz_ != 0)
774 unsigned __clz_f = __bits_per_word - __first.__ctz_;
775 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
777 __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
778 __storage_type __b1 = *__first.__seg_ & __m;
779 *__first.__seg_ &= ~__m;
780 unsigned __clz_r = __bits_per_word - __result.__ctz_;
781 __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
782 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
783 __storage_type __b2 = *__result.__seg_ & __m;
784 *__result.__seg_ &= ~__m;
785 if (__result.__ctz_ > __first.__ctz_)
787 unsigned __s = __result.__ctz_ - __first.__ctz_;
788 *__result.__seg_ |= __b1 << __s;
789 *__first.__seg_ |= __b2 >> __s;
793 unsigned __s = __first.__ctz_ - __result.__ctz_;
794 *__result.__seg_ |= __b1 >> __s;
795 *__first.__seg_ |= __b2 << __s;
797 __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
798 __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
802 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
803 __b2 = *__result.__seg_ & __m;
804 *__result.__seg_ &= ~__m;
805 unsigned __s = __first.__ctz_ + __ddn;
806 *__result.__seg_ |= __b1 >> __s;
807 *__first.__seg_ |= __b2 << __s;
808 __result.__ctz_ = static_cast<unsigned>(__dn);
811 // __first.__ctz_ = 0;
813 // __first.__ctz_ == 0;
815 __storage_type __m = ~__storage_type(0) << __result.__ctz_;
816 unsigned __clz_r = __bits_per_word - __result.__ctz_;
817 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
819 __storage_type __b1 = *__first.__seg_;
820 __storage_type __b2 = *__result.__seg_ & __m;
821 *__result.__seg_ &= ~__m;
822 *__result.__seg_ |= __b1 << __result.__ctz_;
823 *__first.__seg_ = __b2 >> __result.__ctz_;
825 __b2 = *__result.__seg_ & ~__m;
826 *__result.__seg_ &= __m;
827 *__result.__seg_ |= __b1 >> __clz_r;
828 *__first.__seg_ |= __b2 << __clz_r;
833 __m = ~__storage_type(0) >> (__bits_per_word - __n);
834 __storage_type __b1 = *__first.__seg_ & __m;
835 *__first.__seg_ &= ~__m;
836 __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r);
837 __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
838 __storage_type __b2 = *__result.__seg_ & __m;
839 *__result.__seg_ &= ~__m;
840 *__result.__seg_ |= __b1 << __result.__ctz_;
841 *__first.__seg_ |= __b2 >> __result.__ctz_;
842 __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
843 __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
847 __m = ~__storage_type(0) >> (__bits_per_word - __n);
848 __b2 = *__result.__seg_ & __m;
849 *__result.__seg_ &= ~__m;
850 *__result.__seg_ |= __b1 >> __dn;
851 *__first.__seg_ |= __b2 << __dn;
852 __result.__ctz_ = static_cast<unsigned>(__n);
859 template <class __C1, class __C2>
860 inline _LIBCPP_INLINE_VISIBILITY
861 __bit_iterator<__C2, false>
862 swap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1,
863 __bit_iterator<__C2, false> __first2)
865 if (__first1.__ctz_ == __first2.__ctz_)
866 return __swap_ranges_aligned(__first1, __last1, __first2);
867 return __swap_ranges_unaligned(__first1, __last1, __first2);
875 typedef typename _Cp::difference_type difference_type;
876 typedef typename _Cp::__storage_type __storage_type;
877 typedef typename _Cp::__storage_pointer __storage_pointer;
878 typedef typename _Cp::iterator iterator;
879 static const unsigned __bits_per_word = _Cp::__bits_per_word;
880 static const unsigned _Np = 4;
882 difference_type __size_;
883 __storage_type __word_[_Np];
885 _LIBCPP_INLINE_VISIBILITY static difference_type capacity()
886 {return static_cast<difference_type>(_Np * __bits_per_word);}
887 _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {}
888 _LIBCPP_INLINE_VISIBILITY iterator begin()
890 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]), 0);
892 _LIBCPP_INLINE_VISIBILITY iterator end()
894 return iterator(pointer_traits<__storage_pointer>::pointer_to(__word_[0]) + __size_ / __bits_per_word,
895 static_cast<unsigned>(__size_ % __bits_per_word));
900 __bit_iterator<_Cp, false>
901 rotate(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __middle, __bit_iterator<_Cp, false> __last)
903 typedef __bit_iterator<_Cp, false> _I1;
904 typedef typename _I1::difference_type difference_type;
905 typedef typename _I1::__storage_type __storage_type;
906 difference_type __d1 = __middle - __first;
907 difference_type __d2 = __last - __middle;
908 _I1 __r = __first + __d2;
909 while (__d1 != 0 && __d2 != 0)
913 if (__d1 <= __bit_array<_Cp>::capacity())
915 __bit_array<_Cp> __b(__d1);
916 _VSTD::copy(__first, __middle, __b.begin());
917 _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first));
922 __bit_iterator<_Cp, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle);
930 if (__d2 <= __bit_array<_Cp>::capacity())
932 __bit_array<_Cp> __b(__d2);
933 _VSTD::copy(__middle, __last, __b.begin());
934 _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last));
939 __bit_iterator<_Cp, false> __mp = __first + __d2;
940 _VSTD::swap_ranges(__first, __mp, __middle);
951 template <class _Cp, bool _IC1, bool _IC2>
953 __equal_unaligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
954 __bit_iterator<_Cp, _IC2> __first2)
956 typedef __bit_iterator<_Cp, _IC1> _It;
957 typedef typename _It::difference_type difference_type;
958 typedef typename _It::__storage_type __storage_type;
959 static const unsigned __bits_per_word = _It::__bits_per_word;
960 difference_type __n = __last1 - __first1;
964 if (__first1.__ctz_ != 0)
966 unsigned __clz_f = __bits_per_word - __first1.__ctz_;
967 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
969 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
970 __storage_type __b = *__first1.__seg_ & __m;
971 unsigned __clz_r = __bits_per_word - __first2.__ctz_;
972 __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
973 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
974 if (__first2.__ctz_ > __first1.__ctz_)
976 if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
981 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
984 __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
985 __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word);
989 __m = ~__storage_type(0) >> (__bits_per_word - __dn);
990 if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
992 __first2.__ctz_ = static_cast<unsigned>(__dn);
995 // __first1.__ctz_ = 0;
997 // __first1.__ctz_ == 0;
999 unsigned __clz_r = __bits_per_word - __first2.__ctz_;
1000 __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
1001 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_)
1003 __storage_type __b = *__first1.__seg_;
1004 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
1007 if ((*__first2.__seg_ & ~__m) != (__b >> __clz_r))
1013 __m = ~__storage_type(0) >> (__bits_per_word - __n);
1014 __storage_type __b = *__first1.__seg_ & __m;
1015 __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
1016 __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
1017 if ((*__first2.__seg_ & __m) != (__b << __first2.__ctz_))
1019 __first2.__seg_ += (__dn + __first2.__ctz_) / __bits_per_word;
1020 __first2.__ctz_ = static_cast<unsigned>((__dn + __first2.__ctz_) % __bits_per_word);
1024 __m = ~__storage_type(0) >> (__bits_per_word - __n);
1025 if ((*__first2.__seg_ & __m) != (__b >> __dn))
1033 template <class _Cp, bool _IC1, bool _IC2>
1035 __equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
1036 __bit_iterator<_Cp, _IC2> __first2)
1038 typedef __bit_iterator<_Cp, _IC1> _It;
1039 typedef typename _It::difference_type difference_type;
1040 typedef typename _It::__storage_type __storage_type;
1041 static const unsigned __bits_per_word = _It::__bits_per_word;
1042 difference_type __n = __last1 - __first1;
1046 if (__first1.__ctz_ != 0)
1048 unsigned __clz = __bits_per_word - __first1.__ctz_;
1049 difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
1051 __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
1052 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
1056 // __first1.__ctz_ = 0;
1057 // __first2.__ctz_ = 0;
1059 // __first1.__ctz_ == 0;
1060 // __first2.__ctz_ == 0;
1062 for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_, ++__first2.__seg_)
1063 if (*__first2.__seg_ != *__first1.__seg_)
1068 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
1069 if ((*__first2.__seg_ & __m) != (*__first1.__seg_ & __m))
1076 template <class _Cp, bool _IC1, bool _IC2>
1077 inline _LIBCPP_INLINE_VISIBILITY
1079 equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2)
1081 if (__first1.__ctz_ == __first2.__ctz_)
1082 return __equal_aligned(__first1, __last1, __first2);
1083 return __equal_unaligned(__first1, __last1, __first2);
1086 template <class _Cp, bool _IsConst,
1087 typename _Cp::__storage_type>
1088 class __bit_iterator
1091 typedef typename _Cp::difference_type difference_type;
1092 typedef bool value_type;
1093 typedef __bit_iterator pointer;
1094 typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference;
1095 typedef random_access_iterator_tag iterator_category;
1098 typedef typename _Cp::__storage_type __storage_type;
1099 typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer,
1100 typename _Cp::__storage_pointer>::type __storage_pointer;
1101 static const unsigned __bits_per_word = _Cp::__bits_per_word;
1103 __storage_pointer __seg_;
1107 _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT {}
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 #if defined(__clang__)
1218 friend typename _Cp::__self;
1220 friend class _Cp::__self;
1222 friend class __bit_reference<_Cp>;
1223 friend class __bit_const_reference<_Cp>;
1224 friend class __bit_iterator<_Cp, true>;
1225 template <class _Dp> friend struct __bit_array;
1226 template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1227 template <class _Dp> friend void __fill_n_true(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
1228 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> __copy_aligned(__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_unaligned(__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(__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_aligned(__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_unaligned(__bit_iterator<_Dp, _IC> __first,
1241 __bit_iterator<_Dp, _IC> __last,
1242 __bit_iterator<_Dp, false> __result);
1243 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, false> copy_backward(__bit_iterator<_Dp, _IC> __first,
1244 __bit_iterator<_Dp, _IC> __last,
1245 __bit_iterator<_Dp, false> __result);
1246 template <class __C1, class __C2>friend __bit_iterator<__C2, false> __swap_ranges_aligned(__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_unaligned(__bit_iterator<__C1, false>,
1250 __bit_iterator<__C1, false>,
1251 __bit_iterator<__C2, false>);
1252 template <class __C1, class __C2>friend __bit_iterator<__C2, false> swap_ranges(__bit_iterator<__C1, false>,
1253 __bit_iterator<__C1, false>,
1254 __bit_iterator<__C2, false>);
1255 template <class _Dp> friend __bit_iterator<_Dp, false> rotate(__bit_iterator<_Dp, false>,
1256 __bit_iterator<_Dp, false>,
1257 __bit_iterator<_Dp, false>);
1258 template <class _Dp, bool _IC1, bool _IC2> friend bool __equal_aligned(__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_unaligned(__bit_iterator<_Dp, _IC1>,
1262 __bit_iterator<_Dp, _IC1>,
1263 __bit_iterator<_Dp, _IC2>);
1264 template <class _Dp, bool _IC1, bool _IC2> friend bool equal(__bit_iterator<_Dp, _IC1>,
1265 __bit_iterator<_Dp, _IC1>,
1266 __bit_iterator<_Dp, _IC2>);
1267 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>,
1268 typename _Dp::size_type);
1269 template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>,
1270 typename _Dp::size_type);
1271 template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1272 __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1273 template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
1274 __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
1277 _LIBCPP_END_NAMESPACE_STD
1279 #endif // _LIBCPP___BIT_REFERENCE