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