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