Implement LCM and GCD for C++17. Same code as for Library Fundamentals TS.

llvm-svn: 276751

2 files changed, 64 insertions, 2 deletions

diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index 25e95ac443a..cf03d66d542 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -2431,7 +2431,7 @@ __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIt
 template<typename _Integral>
 inline _LIBCPP_INLINE_VISIBILITY
 _Integral
-__gcd(_Integral __x, _Integral __y)
+__algo_gcd(_Integral __x, _Integral __y)
 {
     do
     {
@@ -2456,7 +2456,7 @@ __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Ran
         _VSTD::swap_ranges(__first, __middle, __middle);
         return __middle;
     }
-    const difference_type __g = _VSTD::__gcd(__m1, __m2);
+    const difference_type __g = _VSTD::__algo_gcd(__m1, __m2);
     for (_RandomAccessIterator __p = __first + __g; __p != __first;)
     {
         value_type __t(_VSTD::move(*--__p));
diff --git a/libcxx/include/numeric b/libcxx/include/numeric
index 21c3781ab6a..1643d6400d1 100644
--- a/libcxx/include/numeric
+++ b/libcxx/include/numeric
@@ -53,6 +53,12 @@ template <class InputIterator, class OutputIterator, class BinaryOperation>
 template <class ForwardIterator, class T>
     void iota(ForwardIterator first, ForwardIterator last, T value);
 
+template <class M, class N>
+    constexpr common_type_t<M,N> gcd(M m, N n);    // C++17
+
+template <class M, class N>
+    constexpr common_type_t<M,N> lcm(M m, N n);    // C++17
+
 }  // std
 
 */
@@ -192,6 +198,62 @@ iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value_)
         *__first = __value_;
 }
 
+
+#if _LIBCPP_STD_VER > 14
+template <typename _Tp, bool _IsSigned = is_signed<_Tp>::value> struct __abs;
+
+template <typename _Tp>
+struct __abs<_Tp, true> {
+    _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
+    _Tp operator()(_Tp __t) const noexcept { return __t >= 0 ? __t : -__t; }
+};
+
+template <typename _Tp>
+struct __abs<_Tp, false> {
+    _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
+    _Tp operator()(_Tp __t) const noexcept { return __t; }
+};
+
+
+template<class _Tp>
+_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
+_Tp __gcd(_Tp __m, _Tp __n)
+{
+    static_assert((!is_signed<_Tp>::value), "" );
+    return __n == 0 ? __m : __gcd<_Tp>(__n, __m % __n);
+}
+
+
+template<class _Tp, class _Up>
+_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
+common_type_t<_Tp,_Up>
+gcd(_Tp __m, _Up __n)
+{
+    static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types");
+    using _Rp = common_type_t<_Tp,_Up>;
+    using _Wp = make_unsigned_t<_Rp>;
+    return static_cast<_Rp>(__gcd(static_cast<_Wp>(__abs<_Tp>()(__m)),
+                                  static_cast<_Wp>(__abs<_Up>()(__n))));
+}
+
+template<class _Tp, class _Up>
+_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
+common_type_t<_Tp,_Up>
+lcm(_Tp __m, _Up __n)
+{
+    static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types");
+    if (__m == 0 || __n == 0)
+        return 0;
+
+    using _Rp = common_type_t<_Tp,_Up>;
+    _Rp __val1 = __abs<_Tp>()(__m) / gcd(__m,__n);
+    _Up __val2 = __abs<_Up>()(__n);
+    _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm");
+    return __val1 * __val2;
+}
+
+#endif /* _LIBCPP_STD_VER > 14 */
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif  // _LIBCPP_NUMERIC