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