[committed 2/3] libstdc++: Fix some algos for 16-bit size_t [PR108221]

[Jonathan Wakely <jwakely@redhat.com>]

Tested x86_64-linux. Pushed to trunk.

-- >8 --

Some standard algorithms fail to compile when size_t or ptrdiff_t is
narrower than int. The __lg helper function is ambiguous if ptrdiff_t is
short or __int20, so replace it with a function template that works for
those types as well as signed/unsigned int/long/long long. The helpers
for stable_sort perform arithmetic on size values and assume the types
won't change, which isn't true if the type promotes to int.

libstdc++-v3/ChangeLog:

	PR libstdc++/108221
	* include/bits/stl_algobase.h (__lg): Replace six overloads with
	a single function template for all integer types.
	* include/bits/stl_algo.h (__merge_adaptive_resize): Cast
	arithmetic results back to _Distance.
---
 libstdc++-v3/include/bits/stl_algo.h     |  5 ++-
 libstdc++-v3/include/bits/stl_algobase.h | 47 ++++++++++++------------
 2 files changed, 26 insertions(+), 26 deletions(-)

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 6386918fc8b..eed04b3c1b8 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -2458,13 +2458,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
 
 	  _BidirectionalIterator __new_middle
 	    = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
-				     __len1 - __len11, __len22,
+				     _Distance(__len1 - __len11), __len22,
 				     __buffer, __buffer_size);
 	  std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
 				       __len11, __len22,
 				       __buffer, __buffer_size, __comp);
 	  std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
-				       __len1 - __len11, __len2 - __len22,
+				       _Distance(__len1 - __len11),
+				       _Distance(__len2 - __len22),
 				       __buffer, __buffer_size, __comp);
 	}
     }
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index ae898ed3706..566b6d9c4bc 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -72,7 +72,10 @@
 #if __cplusplus >= 201103L
 # include <type_traits>
 #endif
-#if __cplusplus > 201703L
+#if __cplusplus >= 201402L
+# include <bit> // std::__bit_width
+#endif
+#if __cplusplus >= 202002L
 # include <compare>
 #endif
 
@@ -1505,29 +1508,25 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
 
   /// This is a helper function for the sort routines and for random.tcc.
   //  Precondition: __n > 0.
-  inline _GLIBCXX_CONSTEXPR int
-  __lg(int __n)
-  { return (int)sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
-
-  inline _GLIBCXX_CONSTEXPR unsigned
-  __lg(unsigned __n)
-  { return (int)sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
-
-  inline _GLIBCXX_CONSTEXPR long
-  __lg(long __n)
-  { return (int)sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
-
-  inline _GLIBCXX_CONSTEXPR unsigned long
-  __lg(unsigned long __n)
-  { return (int)sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
-
-  inline _GLIBCXX_CONSTEXPR long long
-  __lg(long long __n)
-  { return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
-
-  inline _GLIBCXX_CONSTEXPR unsigned long long
-  __lg(unsigned long long __n)
-  { return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
+  template<typename _Tp>
+    inline _GLIBCXX_CONSTEXPR _Tp
+    __lg(_Tp __n)
+    {
+#if __cplusplus >= 201402L
+      return std::__bit_width(make_unsigned_t<_Tp>(__n)) - 1;
+#else
+      // Use +__n so it promotes to at least int.
+      const int __sz = sizeof(+__n);
+      int __w = __sz * __CHAR_BIT__ - 1;
+      if (__sz == sizeof(long long))
+	__w -= __builtin_clzll(+__n);
+      else if (__sz == sizeof(long))
+	__w -= __builtin_clzl(+__n);
+      else if (__sz == sizeof(int))
+	__w -= __builtin_clz(+__n);
+      return __w;
+#endif
+    }
 
 _GLIBCXX_BEGIN_NAMESPACE_ALGO
 
-- 
2.39.0