Replace __make_tuple_indices implementation with superior implementation.
The previous __make_tuple_indices implementation caused O(N) instantiations
and was pretty inefficient. The C++14 __make_integer_sequence implementation
is much better, since it either uses a builtin to generate the sequence or
a very nice Log8(N) implementation provided by richard smith.
This patch moves the __make_integer_sequence implementation into __tuple
and uses it to implement __make_tuple_indices.
Since libc++ can't expose the name 'integer_sequence' in C++11 this patch
also introduces a dummy type '__integer_sequence' which is used when generating
the sequence. One the sequence is generated '__integer_sequence' can be
converted into the required type; either '__tuple_indices' or 'integer_sequence'.
llvm-svn: 274286
diff --git a/libcxx/include/__tuple b/libcxx/include/__tuple
index 09c6839..53afb18 100644
--- a/libcxx/include/__tuple
+++ b/libcxx/include/__tuple
@@ -68,6 +68,80 @@
// tuple specializations
#if !defined(_LIBCPP_HAS_NO_VARIADICS)
+
+template <size_t...> struct __tuple_indices {};
+
+template <class _IdxType, _IdxType... _Values>
+struct __integer_sequence {
+ template <template <class _OIdxType, _OIdxType...> class _ToIndexSeq, class _ToIndexType>
+ using __convert = _ToIndexSeq<_ToIndexType, _Values...>;
+
+ template <size_t _Sp>
+ using __to_tuple_indices = __tuple_indices<(_Values + _Sp)...>;
+};
+
+#if !__has_builtin(__make_integer_seq) || defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE)
+namespace __detail {
+
+template<typename _Tp, size_t ..._Extra> struct __repeat;
+template<typename _Tp, _Tp ..._Np, size_t ..._Extra> struct __repeat<__integer_sequence<_Tp, _Np...>, _Extra...> {
+ typedef __integer_sequence<_Tp,
+ _Np...,
+ sizeof...(_Np) + _Np...,
+ 2 * sizeof...(_Np) + _Np...,
+ 3 * sizeof...(_Np) + _Np...,
+ 4 * sizeof...(_Np) + _Np...,
+ 5 * sizeof...(_Np) + _Np...,
+ 6 * sizeof...(_Np) + _Np...,
+ 7 * sizeof...(_Np) + _Np...,
+ _Extra...> type;
+};
+
+template<size_t _Np> struct __parity;
+template<size_t _Np> struct __make : __parity<_Np % 8>::template __pmake<_Np> {};
+
+template<> struct __make<0> { typedef __integer_sequence<size_t> type; };
+template<> struct __make<1> { typedef __integer_sequence<size_t, 0> type; };
+template<> struct __make<2> { typedef __integer_sequence<size_t, 0, 1> type; };
+template<> struct __make<3> { typedef __integer_sequence<size_t, 0, 1, 2> type; };
+template<> struct __make<4> { typedef __integer_sequence<size_t, 0, 1, 2, 3> type; };
+template<> struct __make<5> { typedef __integer_sequence<size_t, 0, 1, 2, 3, 4> type; };
+template<> struct __make<6> { typedef __integer_sequence<size_t, 0, 1, 2, 3, 4, 5> type; };
+template<> struct __make<7> { typedef __integer_sequence<size_t, 0, 1, 2, 3, 4, 5, 6> type; };
+
+template<> struct __parity<0> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type> {}; };
+template<> struct __parity<1> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 1> {}; };
+template<> struct __parity<2> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 2, _Np - 1> {}; };
+template<> struct __parity<3> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 3, _Np - 2, _Np - 1> {}; };
+template<> struct __parity<4> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
+template<> struct __parity<5> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 5, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
+template<> struct __parity<6> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 6, _Np - 5, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
+template<> struct __parity<7> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 7, _Np - 6, _Np - 5, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
+
+} // namespace detail
+
+#endif // !__has_builtin(__make_integer_seq) || defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE)
+
+#if __has_builtin(__make_integer_seq)
+template <size_t _Ep, size_t _Sp>
+using __make_indices_imp =
+ typename __make_integer_seq<__integer_sequence, size_t, _Ep - _Sp>::template
+ __to_tuple_indices<_Sp>;
+#else
+template <size_t _Ep, size_t _Sp>
+using __make_indices_imp =
+ typename __detail::__make<_Ep - _Sp>::type::template __to_tuple_indices<_Sp>;
+
+#endif
+
+template <size_t _Ep, size_t _Sp = 0>
+struct __make_tuple_indices
+{
+ static_assert(_Sp <= _Ep, "__make_tuple_indices input error");
+ typedef __make_indices_imp<_Ep, _Sp> type;
+};
+
+
template <class ..._Tp> class _LIBCPP_TYPE_VIS_ONLY tuple;
template <class... _Tp> struct __tuple_like<tuple<_Tp...> > : true_type {};
@@ -149,31 +223,6 @@
#if !defined(_LIBCPP_HAS_NO_VARIADICS)
-// __make_tuple_indices
-
-template <size_t...> struct __tuple_indices {};
-
-template <size_t _Sp, class _IntTuple, size_t _Ep>
-struct __make_indices_imp;
-
-template <size_t _Sp, size_t ..._Indices, size_t _Ep>
-struct __make_indices_imp<_Sp, __tuple_indices<_Indices...>, _Ep>
-{
- typedef typename __make_indices_imp<_Sp+1, __tuple_indices<_Indices..., _Sp>, _Ep>::type type;
-};
-
-template <size_t _Ep, size_t ..._Indices>
-struct __make_indices_imp<_Ep, __tuple_indices<_Indices...>, _Ep>
-{
- typedef __tuple_indices<_Indices...> type;
-};
-
-template <size_t _Ep, size_t _Sp = 0>
-struct __make_tuple_indices
-{
- static_assert(_Sp <= _Ep, "__make_tuple_indices input error");
- typedef typename __make_indices_imp<_Sp, __tuple_indices<>, _Ep>::type type;
-};
// __tuple_types