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