From 691b5f0119cb5958797ad6e47357e68d22c91fb1 Mon Sep 17 00:00:00 2001
From: Jonathan Wakely <jwakely@redhat.com>
Date: Wed, 17 May 2017 18:18:07 +0100
Subject: [PATCH] PR libstdc++/66059 optimise _Build_index_tuple

Backport from mainline
2015-11-17  Jonathan Wakely  <jwakely@redhat.com>

	PR libstdc++/66059
	* include/std/utility (_Build_index_tuple): Optimise.

From-SVN: r248163
---
 libstdc++-v3/ChangeLog           |  8 ++++++++
 libstdc++-v3/include/std/utility | 19 +++++++++++++++----
 2 files changed, 23 insertions(+), 4 deletions(-)

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 537100e59f97..42588eb1488c 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,11 @@
+2017-05-17  Jonathan Wakely  <jwakely@redhat.com>
+
+	Backport from mainline
+	2015-11-17  Jonathan Wakely  <jwakely@redhat.com>
+
+	PR libstdc++/66059
+	* include/std/utility (_Build_index_tuple): Optimise.
+
 2017-03-17  Jonathan Wakely  <jwakely@redhat.com>
 
 	Backport from mainline
diff --git a/libstdc++-v3/include/std/utility b/libstdc++-v3/include/std/utility
index 1aac77c10cb4..0ca85dfbb4b8 100644
--- a/libstdc++-v3/include/std/utility
+++ b/libstdc++-v3/include/std/utility
@@ -202,17 +202,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   // Stores a tuple of indices.  Used by tuple and pair, and by bind() to
   // extract the elements in a tuple.
-  template<size_t... _Indexes>
-    struct _Index_tuple
+  template<size_t... _Indexes> struct _Index_tuple { };
+
+  // Concatenates two _Index_tuples.
+  template<typename _Itup1, typename _Itup2> struct _Itup_cat;
+
+  template<size_t... _Ind1, size_t... _Ind2>
+    struct _Itup_cat<_Index_tuple<_Ind1...>, _Index_tuple<_Ind2...>>
     {
-      typedef _Index_tuple<_Indexes..., sizeof...(_Indexes)> __next;
+      using __type = _Index_tuple<_Ind1..., (_Ind2 + sizeof...(_Ind1))...>;
     };
 
   // Builds an _Index_tuple<0, 1, 2, ..., _Num-1>.
   template<size_t _Num>
     struct _Build_index_tuple
+    : _Itup_cat<typename _Build_index_tuple<_Num / 2>::__type,
+		typename _Build_index_tuple<_Num - _Num / 2>::__type>
+    { };
+
+  template<>
+    struct _Build_index_tuple<1>
     {
-      typedef typename _Build_index_tuple<_Num - 1>::__type::__next __type;
+      typedef _Index_tuple<0> __type;
     };
 
   template<>
-- 
2.47.2