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