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