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