svn commit: r227983 - in head: . contrib/libc++
contrib/libc++/include contrib/libc++/include/ext
contrib/libc++/src contrib/libc++/src/support
contrib/libcxxrt etc/mtree lib lib/libc++ lib/libcxxr...
David Chisnall
theraven at FreeBSD.org
Fri Nov 25 20:59:05 UTC 2011
Author: theraven
Date: Fri Nov 25 20:59:04 2011
New Revision: 227983
URL: http://svn.freebsd.org/changeset/base/227983
Log:
Import libc++ / libcxxrt into base. Not build by default yet (use
MK_LIBCPLUSPLUS=yes to enable). This is a work-in-progress. It works for
me, but is not guaranteed to work for anyone else and may eat your dog.
To build C++ using libc++, add -stdlib=libc++ to your CXX and LD flags.
Bug reports welcome, bug fixes even more welcome...
Approved by: dim (mentor)
Added:
head/contrib/libc++/
head/contrib/libc++/FREEBSD-upgrade
head/contrib/libc++/include/
head/contrib/libc++/include/__bit_reference
- copied unchanged from r227828, vendor/libc++/dist/include/__bit_reference
head/contrib/libc++/include/__config
- copied unchanged from r227828, vendor/libc++/dist/include/__config
head/contrib/libc++/include/__debug
- copied unchanged from r227828, vendor/libc++/dist/include/__debug
head/contrib/libc++/include/__functional_03
- copied unchanged from r227828, vendor/libc++/dist/include/__functional_03
head/contrib/libc++/include/__functional_base
- copied unchanged from r227828, vendor/libc++/dist/include/__functional_base
head/contrib/libc++/include/__functional_base_03
- copied unchanged from r227828, vendor/libc++/dist/include/__functional_base_03
head/contrib/libc++/include/__hash_table
- copied unchanged from r227828, vendor/libc++/dist/include/__hash_table
head/contrib/libc++/include/__locale
- copied unchanged from r227828, vendor/libc++/dist/include/__locale
head/contrib/libc++/include/__mutex_base
- copied unchanged from r227828, vendor/libc++/dist/include/__mutex_base
head/contrib/libc++/include/__split_buffer
- copied unchanged from r227828, vendor/libc++/dist/include/__split_buffer
head/contrib/libc++/include/__sso_allocator
- copied unchanged from r227828, vendor/libc++/dist/include/__sso_allocator
head/contrib/libc++/include/__std_stream
- copied unchanged from r227828, vendor/libc++/dist/include/__std_stream
head/contrib/libc++/include/__tree
- copied unchanged from r227828, vendor/libc++/dist/include/__tree
head/contrib/libc++/include/__tuple
- copied unchanged from r227828, vendor/libc++/dist/include/__tuple
head/contrib/libc++/include/__tuple_03
- copied unchanged from r227828, vendor/libc++/dist/include/__tuple_03
head/contrib/libc++/include/algorithm
- copied unchanged from r227828, vendor/libc++/dist/include/algorithm
head/contrib/libc++/include/array
- copied unchanged from r227828, vendor/libc++/dist/include/array
head/contrib/libc++/include/atomic
- copied unchanged from r227828, vendor/libc++/dist/include/atomic
head/contrib/libc++/include/bitset
- copied unchanged from r227828, vendor/libc++/dist/include/bitset
head/contrib/libc++/include/cassert
- copied unchanged from r227828, vendor/libc++/dist/include/cassert
head/contrib/libc++/include/ccomplex
- copied unchanged from r227828, vendor/libc++/dist/include/ccomplex
head/contrib/libc++/include/cctype
- copied unchanged from r227828, vendor/libc++/dist/include/cctype
head/contrib/libc++/include/cerrno
- copied unchanged from r227828, vendor/libc++/dist/include/cerrno
head/contrib/libc++/include/cfenv
- copied unchanged from r227828, vendor/libc++/dist/include/cfenv
head/contrib/libc++/include/cfloat
- copied unchanged from r227828, vendor/libc++/dist/include/cfloat
head/contrib/libc++/include/chrono
- copied unchanged from r227828, vendor/libc++/dist/include/chrono
head/contrib/libc++/include/cinttypes
- copied unchanged from r227828, vendor/libc++/dist/include/cinttypes
head/contrib/libc++/include/ciso646
- copied unchanged from r227828, vendor/libc++/dist/include/ciso646
head/contrib/libc++/include/climits
- copied unchanged from r227828, vendor/libc++/dist/include/climits
head/contrib/libc++/include/clocale
- copied unchanged from r227828, vendor/libc++/dist/include/clocale
head/contrib/libc++/include/cmath
- copied unchanged from r227828, vendor/libc++/dist/include/cmath
head/contrib/libc++/include/codecvt
- copied unchanged from r227828, vendor/libc++/dist/include/codecvt
head/contrib/libc++/include/complex
- copied unchanged from r227828, vendor/libc++/dist/include/complex
head/contrib/libc++/include/complex.h
- copied unchanged from r227828, vendor/libc++/dist/include/complex.h
head/contrib/libc++/include/condition_variable
- copied unchanged from r227828, vendor/libc++/dist/include/condition_variable
head/contrib/libc++/include/csetjmp
- copied unchanged from r227828, vendor/libc++/dist/include/csetjmp
head/contrib/libc++/include/csignal
- copied unchanged from r227828, vendor/libc++/dist/include/csignal
head/contrib/libc++/include/cstdarg
- copied unchanged from r227828, vendor/libc++/dist/include/cstdarg
head/contrib/libc++/include/cstdbool
- copied unchanged from r227828, vendor/libc++/dist/include/cstdbool
head/contrib/libc++/include/cstddef
- copied unchanged from r227828, vendor/libc++/dist/include/cstddef
head/contrib/libc++/include/cstdint
- copied unchanged from r227828, vendor/libc++/dist/include/cstdint
head/contrib/libc++/include/cstdio
- copied unchanged from r227828, vendor/libc++/dist/include/cstdio
head/contrib/libc++/include/cstdlib
- copied unchanged from r227828, vendor/libc++/dist/include/cstdlib
head/contrib/libc++/include/cstring
- copied unchanged from r227828, vendor/libc++/dist/include/cstring
head/contrib/libc++/include/ctgmath
- copied unchanged from r227828, vendor/libc++/dist/include/ctgmath
head/contrib/libc++/include/ctime
- copied unchanged from r227828, vendor/libc++/dist/include/ctime
head/contrib/libc++/include/cwchar
- copied unchanged from r227828, vendor/libc++/dist/include/cwchar
head/contrib/libc++/include/cwctype
- copied unchanged from r227828, vendor/libc++/dist/include/cwctype
head/contrib/libc++/include/deque
- copied unchanged from r227828, vendor/libc++/dist/include/deque
head/contrib/libc++/include/exception
- copied unchanged from r227828, vendor/libc++/dist/include/exception
head/contrib/libc++/include/ext/
- copied from r227828, vendor/libc++/dist/include/ext/
head/contrib/libc++/include/forward_list
- copied unchanged from r227828, vendor/libc++/dist/include/forward_list
head/contrib/libc++/include/fstream
- copied unchanged from r227828, vendor/libc++/dist/include/fstream
head/contrib/libc++/include/functional
- copied unchanged from r227828, vendor/libc++/dist/include/functional
head/contrib/libc++/include/future
- copied unchanged from r227828, vendor/libc++/dist/include/future
head/contrib/libc++/include/initializer_list
- copied unchanged from r227828, vendor/libc++/dist/include/initializer_list
head/contrib/libc++/include/iomanip
- copied unchanged from r227828, vendor/libc++/dist/include/iomanip
head/contrib/libc++/include/ios
- copied unchanged from r227828, vendor/libc++/dist/include/ios
head/contrib/libc++/include/iosfwd
- copied unchanged from r227828, vendor/libc++/dist/include/iosfwd
head/contrib/libc++/include/iostream
- copied unchanged from r227828, vendor/libc++/dist/include/iostream
head/contrib/libc++/include/istream
- copied unchanged from r227828, vendor/libc++/dist/include/istream
head/contrib/libc++/include/iterator
- copied unchanged from r227828, vendor/libc++/dist/include/iterator
head/contrib/libc++/include/limits
- copied unchanged from r227828, vendor/libc++/dist/include/limits
head/contrib/libc++/include/list
- copied unchanged from r227828, vendor/libc++/dist/include/list
head/contrib/libc++/include/locale
- copied unchanged from r227828, vendor/libc++/dist/include/locale
head/contrib/libc++/include/map
- copied unchanged from r227828, vendor/libc++/dist/include/map
head/contrib/libc++/include/memory
- copied unchanged from r227828, vendor/libc++/dist/include/memory
head/contrib/libc++/include/mutex
- copied unchanged from r227828, vendor/libc++/dist/include/mutex
head/contrib/libc++/include/new
- copied unchanged from r227828, vendor/libc++/dist/include/new
head/contrib/libc++/include/numeric
- copied unchanged from r227828, vendor/libc++/dist/include/numeric
head/contrib/libc++/include/ostream
- copied unchanged from r227828, vendor/libc++/dist/include/ostream
head/contrib/libc++/include/queue
- copied unchanged from r227828, vendor/libc++/dist/include/queue
head/contrib/libc++/include/random
- copied unchanged from r227828, vendor/libc++/dist/include/random
head/contrib/libc++/include/ratio
- copied unchanged from r227828, vendor/libc++/dist/include/ratio
head/contrib/libc++/include/regex
- copied unchanged from r227828, vendor/libc++/dist/include/regex
head/contrib/libc++/include/scoped_allocator
- copied unchanged from r227828, vendor/libc++/dist/include/scoped_allocator
head/contrib/libc++/include/set
- copied unchanged from r227828, vendor/libc++/dist/include/set
head/contrib/libc++/include/sstream
- copied unchanged from r227828, vendor/libc++/dist/include/sstream
head/contrib/libc++/include/stack
- copied unchanged from r227828, vendor/libc++/dist/include/stack
head/contrib/libc++/include/stdexcept
- copied unchanged from r227828, vendor/libc++/dist/include/stdexcept
head/contrib/libc++/include/streambuf
- copied unchanged from r227828, vendor/libc++/dist/include/streambuf
head/contrib/libc++/include/string
- copied unchanged from r227828, vendor/libc++/dist/include/string
head/contrib/libc++/include/strstream
- copied unchanged from r227828, vendor/libc++/dist/include/strstream
head/contrib/libc++/include/system_error
- copied unchanged from r227828, vendor/libc++/dist/include/system_error
head/contrib/libc++/include/tgmath.h
- copied unchanged from r227828, vendor/libc++/dist/include/tgmath.h
head/contrib/libc++/include/thread
- copied unchanged from r227828, vendor/libc++/dist/include/thread
head/contrib/libc++/include/tuple
- copied unchanged from r227828, vendor/libc++/dist/include/tuple
head/contrib/libc++/include/type_traits
- copied unchanged from r227828, vendor/libc++/dist/include/type_traits
head/contrib/libc++/include/typeindex
- copied unchanged from r227828, vendor/libc++/dist/include/typeindex
head/contrib/libc++/include/typeinfo
- copied unchanged from r227828, vendor/libc++/dist/include/typeinfo
head/contrib/libc++/include/unordered_map
- copied unchanged from r227828, vendor/libc++/dist/include/unordered_map
head/contrib/libc++/include/unordered_set
- copied unchanged from r227828, vendor/libc++/dist/include/unordered_set
head/contrib/libc++/include/utility
- copied unchanged from r227828, vendor/libc++/dist/include/utility
head/contrib/libc++/include/valarray
- copied unchanged from r227828, vendor/libc++/dist/include/valarray
head/contrib/libc++/include/vector
- copied unchanged from r227828, vendor/libc++/dist/include/vector
head/contrib/libc++/src/
head/contrib/libc++/src/algorithm.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/algorithm.cpp
head/contrib/libc++/src/bind.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/bind.cpp
head/contrib/libc++/src/chrono.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/chrono.cpp
head/contrib/libc++/src/condition_variable.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/condition_variable.cpp
head/contrib/libc++/src/debug.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/debug.cpp
head/contrib/libc++/src/exception.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/exception.cpp
head/contrib/libc++/src/future.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/future.cpp
head/contrib/libc++/src/hash.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/hash.cpp
head/contrib/libc++/src/ios.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/ios.cpp
head/contrib/libc++/src/iostream.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/iostream.cpp
head/contrib/libc++/src/locale.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/locale.cpp
head/contrib/libc++/src/memory.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/memory.cpp
head/contrib/libc++/src/mutex.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/mutex.cpp
head/contrib/libc++/src/new.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/new.cpp
head/contrib/libc++/src/random.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/random.cpp
head/contrib/libc++/src/regex.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/regex.cpp
head/contrib/libc++/src/stdexcept.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/stdexcept.cpp
head/contrib/libc++/src/string.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/string.cpp
head/contrib/libc++/src/strstream.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/strstream.cpp
head/contrib/libc++/src/support/
- copied from r227828, vendor/libc++/dist/src/support/
head/contrib/libc++/src/system_error.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/system_error.cpp
head/contrib/libc++/src/thread.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/thread.cpp
head/contrib/libc++/src/typeinfo.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/typeinfo.cpp
head/contrib/libc++/src/utility.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/utility.cpp
head/contrib/libc++/src/valarray.cpp
- copied unchanged from r227828, vendor/libc++/dist/src/valarray.cpp
head/contrib/libcxxrt/
head/contrib/libcxxrt/FREEBSD-upgrade
head/contrib/libcxxrt/abi_namespace.h
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/abi_namespace.h
head/contrib/libcxxrt/auxhelper.cc
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/auxhelper.cc
head/contrib/libcxxrt/cxxabi.h
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/cxxabi.h
head/contrib/libcxxrt/dwarf_eh.h
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/dwarf_eh.h
head/contrib/libcxxrt/dynamic_cast.cc
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/dynamic_cast.cc
head/contrib/libcxxrt/exception.cc
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/exception.cc
head/contrib/libcxxrt/guard.cc
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/guard.cc
head/contrib/libcxxrt/libelftc_dem_gnu3.c
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/libelftc_dem_gnu3.c
head/contrib/libcxxrt/memory.cc
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/memory.cc
head/contrib/libcxxrt/stdexcept.cc
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/stdexcept.cc
head/contrib/libcxxrt/stdexcept.h
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/stdexcept.h
head/contrib/libcxxrt/terminate.cc
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/terminate.cc
head/contrib/libcxxrt/typeinfo
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/typeinfo
head/contrib/libcxxrt/typeinfo.cc
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/typeinfo.cc
head/contrib/libcxxrt/typeinfo.h
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/typeinfo.h
head/contrib/libcxxrt/unwind-arm.h
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/unwind-arm.h
head/contrib/libcxxrt/unwind-itanium.h
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/unwind-itanium.h
head/contrib/libcxxrt/unwind.h
- copied unchanged from r227973, vendor/libcxxrt/1be67aa8295314fb794c4e933d9bb7c7c33e0ca4/unwind.h
head/lib/libc++/
head/lib/libc++/Makefile (contents, props changed)
head/lib/libcxxrt/
head/lib/libcxxrt/Makefile (contents, props changed)
Modified:
head/Makefile.inc1
head/etc/mtree/BSD.include.dist
head/lib/Makefile
head/share/mk/bsd.libnames.mk
head/share/mk/bsd.own.mk
Modified: head/Makefile.inc1
==============================================================================
--- head/Makefile.inc1 Fri Nov 25 19:29:21 2011 (r227982)
+++ head/Makefile.inc1 Fri Nov 25 20:59:04 2011 (r227983)
@@ -1218,6 +1218,9 @@ _startup_libs+= lib/csu/${MACHINE_CPUARC
_startup_libs+= gnu/lib/libgcc
_startup_libs+= lib/libcompiler_rt
_startup_libs+= lib/libc
+.if defined(MK_LIBCPLUSPLUS)
+_startup_libs+= lib/libcxxrt
+.endif
gnu/lib/libgcc__L: lib/libc__L
Added: head/contrib/libc++/FREEBSD-upgrade
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ head/contrib/libc++/FREEBSD-upgrade Fri Nov 25 20:59:04 2011 (r227983)
@@ -0,0 +1,8 @@
+$FreeBSD$
+
+The FreeBSD copy of libc++. This contains everything from the include and
+source directories upstream, with the exception of the support/win32 directory,
+which is only required for building on Windows (FreeBSD is not Windows).
+
+To update, bring in anything new in source or include that is not
+platform-dependent (unless the platform in question is FreeBSD, obviously).
Copied: head/contrib/libc++/include/__bit_reference (from r227828, vendor/libc++/dist/include/__bit_reference)
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ head/contrib/libc++/include/__bit_reference Fri Nov 25 20:59:04 2011 (r227983, copy of r227828, vendor/libc++/dist/include/__bit_reference)
@@ -0,0 +1,1247 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___BIT_REFERENCE
+#define _LIBCPP___BIT_REFERENCE
+
+#include <__config>
+#include <algorithm>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _C, bool _IsConst> class __bit_iterator;
+template <class _C> class __bit_const_reference;
+
+template <class _Tp>
+struct __has_storage_type
+{
+ static const bool value = false;
+};
+
+template <class _C, bool = __has_storage_type<_C>::value>
+class __bit_reference
+{
+ typedef typename _C::__storage_type __storage_type;
+ typedef typename _C::__storage_pointer __storage_pointer;
+
+ __storage_pointer __seg_;
+ __storage_type __mask_;
+
+#if defined(__clang__)
+ friend typename _C::__self;
+#else
+ friend class _C::__self;
+#endif
+ friend class __bit_const_reference<_C>;
+ friend class __bit_iterator<_C, false>;
+public:
+ _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT
+ {return static_cast<bool>(*__seg_ & __mask_);}
+ _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT
+ {return !static_cast<bool>(*this);}
+
+ _LIBCPP_INLINE_VISIBILITY
+ __bit_reference& operator=(bool __x) _NOEXCEPT
+ {
+ if (__x)
+ *__seg_ |= __mask_;
+ else
+ *__seg_ &= ~__mask_;
+ return *this;
+ }
+
+ _LIBCPP_INLINE_VISIBILITY
+ __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT
+ {return operator=(static_cast<bool>(__x));}
+
+ _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;}
+ _LIBCPP_INLINE_VISIBILITY __bit_iterator<_C, false> operator&() const _NOEXCEPT
+ {return __bit_iterator<_C, false>(__seg_, static_cast<unsigned>(__ctz(__mask_)));}
+private:
+ _LIBCPP_INLINE_VISIBILITY
+ __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
+ : __seg_(__s), __mask_(__m) {}
+};
+
+template <class _C>
+class __bit_reference<_C, false>
+{
+};
+
+template <class _C, class _D>
+_LIBCPP_INLINE_VISIBILITY inline
+void
+swap(__bit_reference<_C> __x, __bit_reference<_D> __y) _NOEXCEPT
+{
+ bool __t = __x;
+ __x = __y;
+ __y = __t;
+}
+
+template <class _C>
+_LIBCPP_INLINE_VISIBILITY inline
+void
+swap(__bit_reference<_C> __x, bool& __y) _NOEXCEPT
+{
+ bool __t = __x;
+ __x = __y;
+ __y = __t;
+}
+
+template <class _C>
+_LIBCPP_INLINE_VISIBILITY inline
+void
+swap(bool& __x, __bit_reference<_C> __y) _NOEXCEPT
+{
+ bool __t = __x;
+ __x = __y;
+ __y = __t;
+}
+
+template <class _C>
+class __bit_const_reference
+{
+ typedef typename _C::__storage_type __storage_type;
+ typedef typename _C::__const_storage_pointer __storage_pointer;
+
+ __storage_pointer __seg_;
+ __storage_type __mask_;
+
+#if defined(__clang__)
+ friend typename _C::__self;
+#else
+ friend class _C::__self;
+#endif
+ friend class __bit_iterator<_C, true>;
+public:
+ _LIBCPP_INLINE_VISIBILITY
+ __bit_const_reference(const __bit_reference<_C>& __x) _NOEXCEPT
+ : __seg_(__x.__seg_), __mask_(__x.__mask_) {}
+
+ _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT
+ {return static_cast<bool>(*__seg_ & __mask_);}
+
+ _LIBCPP_INLINE_VISIBILITY __bit_iterator<_C, true> operator&() const _NOEXCEPT
+ {return __bit_iterator<_C, true>(__seg_, static_cast<unsigned>(__ctz(__mask_)));}
+private:
+ _LIBCPP_INLINE_VISIBILITY
+ __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
+ : __seg_(__s), __mask_(__m) {}
+
+ __bit_const_reference& operator=(const __bit_const_reference& __x);
+};
+
+// find
+
+template <class _C>
+__bit_iterator<_C, false>
+__find_bool_true(__bit_iterator<_C, false> __first, typename _C::size_type __n)
+{
+ typedef __bit_iterator<_C, false> _It;
+ typedef typename _It::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _It::__bits_per_word;
+ // do first partial word
+ if (__first.__ctz_ != 0)
+ {
+ __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
+ __storage_type __dn = _VSTD::min(__clz_f, __n);
+ __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
+ __storage_type __b = *__first.__seg_ & __m;
+ if (__b)
+ return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
+ __n -= __dn;
+ ++__first.__seg_;
+ }
+ // do middle whole words
+ for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
+ if (*__first.__seg_)
+ return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(*__first.__seg_)));
+ // do last partial word
+ if (__n > 0)
+ {
+ __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ __storage_type __b = *__first.__seg_ & __m;
+ if (__b)
+ return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
+ }
+ return _It(__first.__seg_, static_cast<unsigned>(__n));
+}
+
+template <class _C>
+__bit_iterator<_C, false>
+__find_bool_false(__bit_iterator<_C, false> __first, typename _C::size_type __n)
+{
+ typedef __bit_iterator<_C, false> _It;
+ typedef typename _It::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _It::__bits_per_word;
+ // do first partial word
+ if (__first.__ctz_ != 0)
+ {
+ __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
+ __storage_type __dn = _VSTD::min(__clz_f, __n);
+ __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
+ __storage_type __b = ~(*__first.__seg_ & __m);
+ if (__b)
+ return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
+ __n -= __dn;
+ ++__first.__seg_;
+ }
+ // do middle whole words
+ for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
+ {
+ __storage_type __b = ~*__first.__seg_;
+ if (__b)
+ return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
+ }
+ // do last partial word
+ if (__n > 0)
+ {
+ __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ __storage_type __b = ~(*__first.__seg_ & __m);
+ if (__b)
+ return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
+ }
+ return _It(__first.__seg_, static_cast<unsigned>(__n));
+}
+
+template <class _C, class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY
+__bit_iterator<_C, false>
+find(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, const _Tp& __value_)
+{
+ if (static_cast<bool>(__value_))
+ return __find_bool_true(__first, static_cast<typename _C::size_type>(__last - __first));
+ return __find_bool_false(__first, static_cast<typename _C::size_type>(__last - __first));
+}
+
+// count
+
+template <class _C>
+typename __bit_iterator<_C, false>::difference_type
+__count_bool_true(__bit_iterator<_C, false> __first, typename _C::size_type __n)
+{
+ typedef __bit_iterator<_C, false> _It;
+ typedef typename _It::__storage_type __storage_type;
+ typedef typename _It::difference_type difference_type;
+ static const unsigned __bits_per_word = _It::__bits_per_word;
+ difference_type __r = 0;
+ // do first partial word
+ if (__first.__ctz_ != 0)
+ {
+ __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
+ __storage_type __dn = _VSTD::min(__clz_f, __n);
+ __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
+ __r = _VSTD::__pop_count(*__first.__seg_ & __m);
+ __n -= __dn;
+ ++__first.__seg_;
+ }
+ // do middle whole words
+ for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
+ __r += _VSTD::__pop_count(*__first.__seg_);
+ // do last partial word
+ if (__n > 0)
+ {
+ __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ __r += _VSTD::__pop_count(*__first.__seg_ & __m);
+ }
+ return __r;
+}
+
+template <class _C>
+typename __bit_iterator<_C, false>::difference_type
+__count_bool_false(__bit_iterator<_C, false> __first, typename _C::size_type __n)
+{
+ typedef __bit_iterator<_C, false> _It;
+ typedef typename _It::__storage_type __storage_type;
+ typedef typename _It::difference_type difference_type;
+ static const unsigned __bits_per_word = _It::__bits_per_word;
+ difference_type __r = 0;
+ // do first partial word
+ if (__first.__ctz_ != 0)
+ {
+ __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
+ __storage_type __dn = _VSTD::min(__clz_f, __n);
+ __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
+ __r = _VSTD::__pop_count(~(*__first.__seg_ & __m));
+ __n -= __dn;
+ ++__first.__seg_;
+ }
+ // do middle whole words
+ for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
+ __r += _VSTD::__pop_count(~*__first.__seg_);
+ // do last partial word
+ if (__n > 0)
+ {
+ __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ __r += _VSTD::__pop_count(~(*__first.__seg_ & __m));
+ }
+ return __r;
+}
+
+template <class _C, class _Tp>
+inline _LIBCPP_INLINE_VISIBILITY
+typename __bit_iterator<_C, false>::difference_type
+count(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, const _Tp& __value_)
+{
+ if (static_cast<bool>(__value_))
+ return __count_bool_true(__first, static_cast<typename _C::size_type>(__last - __first));
+ return __count_bool_false(__first, static_cast<typename _C::size_type>(__last - __first));
+}
+
+// fill_n
+
+template <class _C>
+void
+__fill_n_false(__bit_iterator<_C, false> __first, typename _C::size_type __n)
+{
+ typedef __bit_iterator<_C, false> _It;
+ typedef typename _It::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _It::__bits_per_word;
+ // do first partial word
+ if (__first.__ctz_ != 0)
+ {
+ __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
+ __storage_type __dn = _VSTD::min(__clz_f, __n);
+ __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
+ *__first.__seg_ &= ~__m;
+ __n -= __dn;
+ ++__first.__seg_;
+ }
+ // do middle whole words
+ __storage_type __nw = __n / __bits_per_word;
+ _VSTD::memset(__first.__seg_, 0, __nw * sizeof(__storage_type));
+ __n -= __nw * __bits_per_word;
+ // do last partial word
+ if (__n > 0)
+ {
+ __first.__seg_ += __nw;
+ __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ *__first.__seg_ &= ~__m;
+ }
+}
+
+template <class _C>
+void
+__fill_n_true(__bit_iterator<_C, false> __first, typename _C::size_type __n)
+{
+ typedef __bit_iterator<_C, false> _It;
+ typedef typename _It::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _It::__bits_per_word;
+ // do first partial word
+ if (__first.__ctz_ != 0)
+ {
+ __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
+ __storage_type __dn = _VSTD::min(__clz_f, __n);
+ __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
+ *__first.__seg_ |= __m;
+ __n -= __dn;
+ ++__first.__seg_;
+ }
+ // do middle whole words
+ __storage_type __nw = __n / __bits_per_word;
+ _VSTD::memset(__first.__seg_, -1, __nw * sizeof(__storage_type));
+ __n -= __nw * __bits_per_word;
+ // do last partial word
+ if (__n > 0)
+ {
+ __first.__seg_ += __nw;
+ __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ *__first.__seg_ |= __m;
+ }
+}
+
+template <class _C>
+_LIBCPP_INLINE_VISIBILITY inline
+void
+fill_n(__bit_iterator<_C, false> __first, typename _C::size_type __n, bool __value_)
+{
+ if (__n > 0)
+ {
+ if (__value_)
+ __fill_n_true(__first, __n);
+ else
+ __fill_n_false(__first, __n);
+ }
+}
+
+// fill
+
+template <class _C>
+inline _LIBCPP_INLINE_VISIBILITY
+void
+fill(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __last, bool __value_)
+{
+ _VSTD::fill_n(__first, static_cast<typename _C::size_type>(__last - __first), __value_);
+}
+
+// copy
+
+template <class _C, bool _IsConst>
+__bit_iterator<_C, false>
+__copy_aligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last,
+ __bit_iterator<_C, false> __result)
+{
+ typedef __bit_iterator<_C, _IsConst> _In;
+ typedef typename _In::difference_type difference_type;
+ typedef typename _In::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _In::__bits_per_word;
+ difference_type __n = __last - __first;
+ if (__n > 0)
+ {
+ // do first word
+ if (__first.__ctz_ != 0)
+ {
+ unsigned __clz = __bits_per_word - __first.__ctz_;
+ difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
+ __n -= __dn;
+ __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
+ __storage_type __b = *__first.__seg_ & __m;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b;
+ __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
+ __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
+ ++__first.__seg_;
+ // __first.__ctz_ = 0;
+ }
+ // __first.__ctz_ == 0;
+ // do middle words
+ __storage_type __nw = __n / __bits_per_word;
+ _VSTD::memmove(__result.__seg_, __first.__seg_, __nw * sizeof(__storage_type));
+ __n -= __nw * __bits_per_word;
+ __result.__seg_ += __nw;
+ // do last word
+ if (__n > 0)
+ {
+ __first.__seg_ += __nw;
+ __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ __storage_type __b = *__first.__seg_ & __m;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b;
+ __result.__ctz_ = static_cast<unsigned>(__n);
+ }
+ }
+ return __result;
+}
+
+template <class _C, bool _IsConst>
+__bit_iterator<_C, false>
+__copy_unaligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last,
+ __bit_iterator<_C, false> __result)
+{
+ typedef __bit_iterator<_C, _IsConst> _In;
+ typedef typename _In::difference_type difference_type;
+ typedef typename _In::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _In::__bits_per_word;
+ difference_type __n = __last - __first;
+ if (__n > 0)
+ {
+ // do first word
+ if (__first.__ctz_ != 0)
+ {
+ unsigned __clz_f = __bits_per_word - __first.__ctz_;
+ difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
+ __n -= __dn;
+ __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
+ __storage_type __b = *__first.__seg_ & __m;
+ unsigned __clz_r = __bits_per_word - __result.__ctz_;
+ __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
+ __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
+ *__result.__seg_ &= ~__m;
+ if (__result.__ctz_ > __first.__ctz_)
+ *__result.__seg_ |= __b << (__result.__ctz_ - __first.__ctz_);
+ else
+ *__result.__seg_ |= __b >> (__first.__ctz_ - __result.__ctz_);
+ __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
+ __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
+ __dn -= __ddn;
+ if (__dn > 0)
+ {
+ __m = ~__storage_type(0) >> (__bits_per_word - __dn);
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b >> (__first.__ctz_ + __ddn);
+ __result.__ctz_ = static_cast<unsigned>(__dn);
+ }
+ ++__first.__seg_;
+ // __first.__ctz_ = 0;
+ }
+ // __first.__ctz_ == 0;
+ // do middle words
+ unsigned __clz_r = __bits_per_word - __result.__ctz_;
+ __storage_type __m = ~__storage_type(0) << __result.__ctz_;
+ for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
+ {
+ __storage_type __b = *__first.__seg_;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b << __result.__ctz_;
+ ++__result.__seg_;
+ *__result.__seg_ &= __m;
+ *__result.__seg_ |= __b >> __clz_r;
+ }
+ // do last word
+ if (__n > 0)
+ {
+ __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ __storage_type __b = *__first.__seg_ & __m;
+ __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__clz_r));
+ __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b << __result.__ctz_;
+ __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
+ __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
+ __n -= __dn;
+ if (__n > 0)
+ {
+ __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b >> __dn;
+ __result.__ctz_ = static_cast<unsigned>(__n);
+ }
+ }
+ }
+ return __result;
+}
+
+template <class _C, bool _IsConst>
+inline _LIBCPP_INLINE_VISIBILITY
+__bit_iterator<_C, false>
+copy(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result)
+{
+ if (__first.__ctz_ == __result.__ctz_)
+ return __copy_aligned(__first, __last, __result);
+ return __copy_unaligned(__first, __last, __result);
+}
+
+// copy_backward
+
+template <class _C, bool _IsConst>
+__bit_iterator<_C, false>
+__copy_backward_aligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last,
+ __bit_iterator<_C, false> __result)
+{
+ typedef __bit_iterator<_C, _IsConst> _In;
+ typedef typename _In::difference_type difference_type;
+ typedef typename _In::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _In::__bits_per_word;
+ difference_type __n = __last - __first;
+ if (__n > 0)
+ {
+ // do first word
+ if (__last.__ctz_ != 0)
+ {
+ difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
+ __n -= __dn;
+ unsigned __clz = __bits_per_word - __last.__ctz_;
+ __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz);
+ __storage_type __b = *__last.__seg_ & __m;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b;
+ __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
+ __result.__ctz_) % __bits_per_word);
+ // __last.__ctz_ = 0
+ }
+ // __last.__ctz_ == 0 || __n == 0
+ // __result.__ctz_ == 0 || __n == 0
+ // do middle words
+ __storage_type __nw = __n / __bits_per_word;
+ __result.__seg_ -= __nw;
+ __last.__seg_ -= __nw;
+ _VSTD::memmove(__result.__seg_, __last.__seg_, __nw * sizeof(__storage_type));
+ __n -= __nw * __bits_per_word;
+ // do last word
+ if (__n > 0)
+ {
+ __storage_type __m = ~__storage_type(0) << (__bits_per_word - __n);
+ __storage_type __b = *--__last.__seg_ & __m;
+ *--__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b;
+ __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
+ }
+ }
+ return __result;
+}
+
+template <class _C, bool _IsConst>
+__bit_iterator<_C, false>
+__copy_backward_unaligned(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last,
+ __bit_iterator<_C, false> __result)
+{
+ typedef __bit_iterator<_C, _IsConst> _In;
+ typedef typename _In::difference_type difference_type;
+ typedef typename _In::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _In::__bits_per_word;
+ difference_type __n = __last - __first;
+ if (__n > 0)
+ {
+ // do first word
+ if (__last.__ctz_ != 0)
+ {
+ difference_type __dn = _VSTD::min(static_cast<difference_type>(__last.__ctz_), __n);
+ __n -= __dn;
+ unsigned __clz_l = __bits_per_word - __last.__ctz_;
+ __storage_type __m = (~__storage_type(0) << (__last.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_l);
+ __storage_type __b = *__last.__seg_ & __m;
+ unsigned __clz_r = __bits_per_word - __result.__ctz_;
+ __storage_type __ddn = _VSTD::min(__dn, static_cast<difference_type>(__result.__ctz_));
+ if (__ddn > 0)
+ {
+ __m = (~__storage_type(0) << (__result.__ctz_ - __ddn)) & (~__storage_type(0) >> __clz_r);
+ *__result.__seg_ &= ~__m;
+ if (__result.__ctz_ > __last.__ctz_)
+ *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
+ else
+ *__result.__seg_ |= __b >> (__last.__ctz_ - __result.__ctz_);
+ __result.__ctz_ = static_cast<unsigned>(((-__ddn & (__bits_per_word - 1)) +
+ __result.__ctz_) % __bits_per_word);
+ __dn -= __ddn;
+ }
+ if (__dn > 0)
+ {
+ // __result.__ctz_ == 0
+ --__result.__seg_;
+ __result.__ctz_ = static_cast<unsigned>(-__dn & (__bits_per_word - 1));
+ __m = ~__storage_type(0) << __result.__ctz_;
+ *__result.__seg_ &= ~__m;
+ __last.__ctz_ -= __dn + __ddn;
+ *__result.__seg_ |= __b << (__result.__ctz_ - __last.__ctz_);
+ }
+ // __last.__ctz_ = 0
+ }
+ // __last.__ctz_ == 0 || __n == 0
+ // __result.__ctz_ != 0 || __n == 0
+ // do middle words
+ unsigned __clz_r = __bits_per_word - __result.__ctz_;
+ __storage_type __m = ~__storage_type(0) >> __clz_r;
+ for (; __n >= __bits_per_word; __n -= __bits_per_word)
+ {
+ __storage_type __b = *--__last.__seg_;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b >> __clz_r;
+ *--__result.__seg_ &= __m;
+ *__result.__seg_ |= __b << __result.__ctz_;
+ }
+ // do last word
+ if (__n > 0)
+ {
+ __m = ~__storage_type(0) << (__bits_per_word - __n);
+ __storage_type __b = *--__last.__seg_ & __m;
+ unsigned __clz_r = __bits_per_word - __result.__ctz_;
+ __storage_type __dn = _VSTD::min(__n, static_cast<difference_type>(__result.__ctz_));
+ __m = (~__storage_type(0) << (__result.__ctz_ - __dn)) & (~__storage_type(0) >> __clz_r);
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b >> (__bits_per_word - __result.__ctz_);
+ __result.__ctz_ = static_cast<unsigned>(((-__dn & (__bits_per_word - 1)) +
+ __result.__ctz_) % __bits_per_word);
+ __n -= __dn;
+ if (__n > 0)
+ {
+ // __result.__ctz_ == 0
+ --__result.__seg_;
+ __result.__ctz_ = static_cast<unsigned>(-__n & (__bits_per_word - 1));
+ __m = ~__storage_type(0) << __result.__ctz_;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b << (__result.__ctz_ - (__bits_per_word - __n - __dn));
+ }
+ }
+ }
+ return __result;
+}
+
+template <class _C, bool _IsConst>
+inline _LIBCPP_INLINE_VISIBILITY
+__bit_iterator<_C, false>
+copy_backward(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result)
+{
+ if (__last.__ctz_ == __result.__ctz_)
+ return __copy_backward_aligned(__first, __last, __result);
+ return __copy_backward_unaligned(__first, __last, __result);
+}
+
+// move
+
+template <class _C, bool _IsConst>
+inline _LIBCPP_INLINE_VISIBILITY
+__bit_iterator<_C, false>
+move(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result)
+{
+ return _VSTD::copy(__first, __last, __result);
+}
+
+// move_backward
+
+template <class _C, bool _IsConst>
+inline _LIBCPP_INLINE_VISIBILITY
+__bit_iterator<_C, false>
+move_backward(__bit_iterator<_C, _IsConst> __first, __bit_iterator<_C, _IsConst> __last, __bit_iterator<_C, false> __result)
+{
+ return _VSTD::copy(__first, __last, __result);
+}
+
+// swap_ranges
+
+template <class __C1, class __C2>
+__bit_iterator<__C2, false>
+__swap_ranges_aligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
+ __bit_iterator<__C2, false> __result)
+{
+ typedef __bit_iterator<__C1, false> _I1;
+ typedef typename _I1::difference_type difference_type;
+ typedef typename _I1::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _I1::__bits_per_word;
+ difference_type __n = __last - __first;
+ if (__n > 0)
+ {
+ // do first word
+ if (__first.__ctz_ != 0)
+ {
+ unsigned __clz = __bits_per_word - __first.__ctz_;
+ difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz), __n);
+ __n -= __dn;
+ __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz - __dn));
+ __storage_type __b1 = *__first.__seg_ & __m;
+ *__first.__seg_ &= ~__m;
+ __storage_type __b2 = *__result.__seg_ & __m;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b1;
+ *__first.__seg_ |= __b2;
+ __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
+ __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
+ ++__first.__seg_;
+ // __first.__ctz_ = 0;
+ }
+ // __first.__ctz_ == 0;
+ // do middle words
+ for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_, ++__result.__seg_)
+ swap(*__first.__seg_, *__result.__seg_);
+ // do last word
+ if (__n > 0)
+ {
+ __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ __storage_type __b1 = *__first.__seg_ & __m;
+ *__first.__seg_ &= ~__m;
+ __storage_type __b2 = *__result.__seg_ & __m;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b1;
+ *__first.__seg_ |= __b2;
+ __result.__ctz_ = static_cast<unsigned>(__n);
+ }
+ }
+ return __result;
+}
+
+template <class __C1, class __C2>
+__bit_iterator<__C2, false>
+__swap_ranges_unaligned(__bit_iterator<__C1, false> __first, __bit_iterator<__C1, false> __last,
+ __bit_iterator<__C2, false> __result)
+{
+ typedef __bit_iterator<__C1, false> _I1;
+ typedef typename _I1::difference_type difference_type;
+ typedef typename _I1::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _I1::__bits_per_word;
+ difference_type __n = __last - __first;
+ if (__n > 0)
+ {
+ // do first word
+ if (__first.__ctz_ != 0)
+ {
+ unsigned __clz_f = __bits_per_word - __first.__ctz_;
+ difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
+ __n -= __dn;
+ __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
+ __storage_type __b1 = *__first.__seg_ & __m;
+ *__first.__seg_ &= ~__m;
+ unsigned __clz_r = __bits_per_word - __result.__ctz_;
+ __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
+ __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
+ __storage_type __b2 = *__result.__seg_ & __m;
+ *__result.__seg_ &= ~__m;
+ if (__result.__ctz_ > __first.__ctz_)
+ {
+ unsigned __s = __result.__ctz_ - __first.__ctz_;
+ *__result.__seg_ |= __b1 << __s;
+ *__first.__seg_ |= __b2 >> __s;
+ }
+ else
+ {
+ unsigned __s = __first.__ctz_ - __result.__ctz_;
+ *__result.__seg_ |= __b1 >> __s;
+ *__first.__seg_ |= __b2 << __s;
+ }
+ __result.__seg_ += (__ddn + __result.__ctz_) / __bits_per_word;
+ __result.__ctz_ = static_cast<unsigned>((__ddn + __result.__ctz_) % __bits_per_word);
+ __dn -= __ddn;
+ if (__dn > 0)
+ {
+ __m = ~__storage_type(0) >> (__bits_per_word - __dn);
+ __b2 = *__result.__seg_ & __m;
+ *__result.__seg_ &= ~__m;
+ unsigned __s = __first.__ctz_ + __ddn;
+ *__result.__seg_ |= __b1 >> __s;
+ *__first.__seg_ |= __b2 << __s;
+ __result.__ctz_ = static_cast<unsigned>(__dn);
+ }
+ ++__first.__seg_;
+ // __first.__ctz_ = 0;
+ }
+ // __first.__ctz_ == 0;
+ // do middle words
+ __storage_type __m = ~__storage_type(0) << __result.__ctz_;
+ unsigned __clz_r = __bits_per_word - __result.__ctz_;
+ for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first.__seg_)
+ {
+ __storage_type __b1 = *__first.__seg_;
+ __storage_type __b2 = *__result.__seg_ & __m;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b1 << __result.__ctz_;
+ *__first.__seg_ = __b2 >> __result.__ctz_;
+ ++__result.__seg_;
+ __b2 = *__result.__seg_ & ~__m;
+ *__result.__seg_ &= __m;
+ *__result.__seg_ |= __b1 >> __clz_r;
+ *__first.__seg_ |= __b2 << __clz_r;
+ }
+ // do last word
+ if (__n > 0)
+ {
+ __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ __storage_type __b1 = *__first.__seg_ & __m;
+ *__first.__seg_ &= ~__m;
+ __storage_type __dn = _VSTD::min<__storage_type>(__n, __clz_r);
+ __m = (~__storage_type(0) << __result.__ctz_) & (~__storage_type(0) >> (__clz_r - __dn));
+ __storage_type __b2 = *__result.__seg_ & __m;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b1 << __result.__ctz_;
+ *__first.__seg_ |= __b2 >> __result.__ctz_;
+ __result.__seg_ += (__dn + __result.__ctz_) / __bits_per_word;
+ __result.__ctz_ = static_cast<unsigned>((__dn + __result.__ctz_) % __bits_per_word);
+ __n -= __dn;
+ if (__n > 0)
+ {
+ __m = ~__storage_type(0) >> (__bits_per_word - __n);
+ __b2 = *__result.__seg_ & __m;
+ *__result.__seg_ &= ~__m;
+ *__result.__seg_ |= __b1 >> __dn;
+ *__first.__seg_ |= __b2 << __dn;
+ __result.__ctz_ = static_cast<unsigned>(__n);
+ }
+ }
+ }
+ return __result;
+}
+
+template <class __C1, class __C2>
+inline _LIBCPP_INLINE_VISIBILITY
+__bit_iterator<__C2, false>
+swap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1,
+ __bit_iterator<__C2, false> __first2)
+{
+ if (__first1.__ctz_ == __first2.__ctz_)
+ return __swap_ranges_aligned(__first1, __last1, __first2);
+ return __swap_ranges_unaligned(__first1, __last1, __first2);
+}
+
+// rotate
+
+template <class _C>
+struct __bit_array
+{
+ typedef typename _C::difference_type difference_type;
+ typedef typename _C::__storage_type __storage_type;
+ typedef typename _C::iterator iterator;
+ static const unsigned __bits_per_word = _C::__bits_per_word;
+ static const unsigned _N = 4;
+
+ difference_type __size_;
+ __storage_type __word_[_N];
+
+ _LIBCPP_INLINE_VISIBILITY static difference_type capacity()
+ {return static_cast<difference_type>(_N * __bits_per_word);}
+ _LIBCPP_INLINE_VISIBILITY explicit __bit_array(difference_type __s) : __size_(__s) {}
+ _LIBCPP_INLINE_VISIBILITY iterator begin() {return iterator(__word_, 0);}
+ _LIBCPP_INLINE_VISIBILITY iterator end() {return iterator(__word_ + __size_ / __bits_per_word,
+ static_cast<unsigned>(__size_ % __bits_per_word));}
+};
+
+template <class _C>
+__bit_iterator<_C, false>
+rotate(__bit_iterator<_C, false> __first, __bit_iterator<_C, false> __middle, __bit_iterator<_C, false> __last)
+{
+ typedef __bit_iterator<_C, false> _I1;
+ typedef typename _I1::difference_type difference_type;
+ typedef typename _I1::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _I1::__bits_per_word;
+ difference_type __d1 = __middle - __first;
+ difference_type __d2 = __last - __middle;
+ _I1 __r = __first + __d2;
+ while (__d1 != 0 && __d2 != 0)
+ {
+ if (__d1 <= __d2)
+ {
+ if (__d1 <= __bit_array<_C>::capacity())
+ {
+ __bit_array<_C> __b(__d1);
+ _VSTD::copy(__first, __middle, __b.begin());
+ _VSTD::copy(__b.begin(), __b.end(), _VSTD::copy(__middle, __last, __first));
+ break;
+ }
+ else
+ {
+ __bit_iterator<_C, false> __mp = _VSTD::swap_ranges(__first, __middle, __middle);
+ __first = __middle;
+ __middle = __mp;
+ __d2 -= __d1;
+ }
+ }
+ else
+ {
+ if (__d2 <= __bit_array<_C>::capacity())
+ {
+ __bit_array<_C> __b(__d2);
+ _VSTD::copy(__middle, __last, __b.begin());
+ _VSTD::copy_backward(__b.begin(), __b.end(), _VSTD::copy_backward(__first, __middle, __last));
+ break;
+ }
+ else
+ {
+ __bit_iterator<_C, false> __mp = __first + __d2;
+ _VSTD::swap_ranges(__first, __mp, __middle);
+ __first = __mp;
+ __d1 -= __d2;
+ }
+ }
+ }
+ return __r;
+}
+
+// equal
+
+template <class _C>
+bool
+__equal_unaligned(__bit_iterator<_C, true> __first1, __bit_iterator<_C, true> __last1,
+ __bit_iterator<_C, true> __first2)
+{
+ typedef __bit_iterator<_C, true> _It;
+ typedef typename _It::difference_type difference_type;
+ typedef typename _It::__storage_type __storage_type;
+ static const unsigned __bits_per_word = _It::__bits_per_word;
+ difference_type __n = __last1 - __first1;
+ if (__n > 0)
+ {
+ // do first word
+ if (__first1.__ctz_ != 0)
+ {
+ unsigned __clz_f = __bits_per_word - __first1.__ctz_;
+ difference_type __dn = _VSTD::min(static_cast<difference_type>(__clz_f), __n);
+ __n -= __dn;
+ __storage_type __m = (~__storage_type(0) << __first1.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
+ __storage_type __b = *__first1.__seg_ & __m;
+ unsigned __clz_r = __bits_per_word - __first2.__ctz_;
+ __storage_type __ddn = _VSTD::min<__storage_type>(__dn, __clz_r);
+ __m = (~__storage_type(0) << __first2.__ctz_) & (~__storage_type(0) >> (__clz_r - __ddn));
+ if (__first2.__ctz_ > __first1.__ctz_)
+ if ((*__first2.__seg_ & __m) != (__b << (__first2.__ctz_ - __first1.__ctz_)))
+ return false;
+ else
+ if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ - __first2.__ctz_)))
+ return false;
+ __first2.__seg_ += (__ddn + __first2.__ctz_) / __bits_per_word;
+ __first2.__ctz_ = static_cast<unsigned>((__ddn + __first2.__ctz_) % __bits_per_word);
+ __dn -= __ddn;
+ if (__dn > 0)
+ {
+ __m = ~__storage_type(0) >> (__bits_per_word - __dn);
+ if ((*__first2.__seg_ & __m) != (__b >> (__first1.__ctz_ + __ddn)))
+ return false;
+ __first2.__ctz_ = static_cast<unsigned>(__dn);
+ }
+ ++__first1.__seg_;
+ // __first1.__ctz_ = 0;
+ }
+ // __first1.__ctz_ == 0;
+ // do middle words
+ unsigned __clz_r = __bits_per_word - __first2.__ctz_;
+ __storage_type __m = ~__storage_type(0) << __first2.__ctz_;
+ for (; __n >= __bits_per_word; __n -= __bits_per_word, ++__first1.__seg_)
*** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
More information about the svn-src-head
mailing list