{"id":2226713,"url":"http://patchwork.ozlabs.org/api/patches/2226713/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.3@forge-stage.sourceware.org/","project":{"id":17,"url":"http://patchwork.ozlabs.org/api/projects/17/?format=json","name":"GNU Compiler Collection","link_name":"gcc","list_id":"gcc-patches.gcc.gnu.org","list_email":"gcc-patches@gcc.gnu.org","web_url":null,"scm_url":null,"webscm_url":null,"list_archive_url":"","list_archive_url_format":"","commit_url_format":""},"msgid":"","list_archive_url":null,"date":"2026-04-22T18:27:27","name":"[v1,3/8] libstdc++: Directly implement ranges::inplace_merge [PR100795]","commit_ref":null,"pull_url":null,"state":"new","archived":false,"hash":"d5914a80b47a77520eb1d51e020ceb8876c0e55b","submitter":{"id":93215,"url":"http://patchwork.ozlabs.org/api/people/93215/?format=json","name":"ppalka via Sourceware Forge","email":"forge-bot+ppalka@forge-stage.sourceware.org"},"delegate":null,"mbox":"http://patchwork.ozlabs.org/project/gcc/patch/bmm.hhuoj2uk6c.gcc.gcc-TEST.ppalka.57.1.3@forge-stage.sourceware.org/mbox/","series":[{"id":501079,"url":"http://patchwork.ozlabs.org/api/series/501079/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=501079","date":"2026-04-22T18:27:24","name":"libstdc++: C++20 iterator awareness fixes for various Ranges algorithms [PR100795]","version":1,"mbox":"http://patchwork.ozlabs.org/series/501079/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/patches/2226713/comments/","check":"pending","checks":"http://patchwork.ozlabs.org/api/patches/2226713/checks/","tags":{},"related":[],"headers":{"Return-Path":"","X-Original-To":["incoming@patchwork.ozlabs.org","gcc-patches@gcc.gnu.org"],"Delivered-To":["patchwork-incoming@legolas.ozlabs.org","gcc-patches@gcc.gnu.org"],"Authentication-Results":["legolas.ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org\n (client-ip=38.145.34.32; helo=vm01.sourceware.org;\n envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org;\n receiver=patchwork.ozlabs.org)","sourceware.org; dmarc=none (p=none dis=none)\n header.from=forge-stage.sourceware.org","sourceware.org;\n spf=pass smtp.mailfrom=forge-stage.sourceware.org","server2.sourceware.org;\n arc=none smtp.remote-ip=38.145.34.39"],"Received":["from vm01.sourceware.org (vm01.sourceware.org [38.145.34.32])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange x25519 server-signature ECDSA (secp384r1) server-digest SHA384)\n\t(No client certificate requested)\n\tby legolas.ozlabs.org (Postfix) with ESMTPS id 4g17Wh6cVwz1yHB\n\tfor ; Thu, 23 Apr 2026 04:47:43 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id DDE8848EACF8\n\tfor ; Wed, 22 Apr 2026 18:47:41 +0000 (GMT)","from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id 35DF249002D2\n for ; Wed, 22 Apr 2026 18:28:35 +0000 (GMT)","from forge-stage.sourceware.org (localhost [IPv6:::1])\n (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n key-exchange x25519 server-signature ECDSA (prime256v1) server-digest SHA256)\n (No client certificate requested)\n by forge-stage.sourceware.org (Postfix) with ESMTPS id 12CC94349D\n for ; Wed, 22 Apr 2026 18:28:35 +0000 (UTC)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org DDE8848EACF8","OpenDKIM Filter v2.11.0 sourceware.org 35DF249002D2"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org 35DF249002D2","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org 35DF249002D2","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776882515; cv=none;\n b=sP+kEFfIWLAx77ECMZE+OG8vkwZFRcQFFFzkQVpdV6zutscwp9Knl9iHU7iJzxrH1W/BryuQZ9CKE+oS1e5lHlGYc7BsDwLYSNhanQl7HMfcVRRd3IdBUgsPFu6OLed8s7ri2uCITDGZSzcMiSBaGaYzZZ1c7I2Dc/Z1y+kXCc0=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776882515; c=relaxed/simple;\n bh=MCRkm2npXBh6Ui5YQu3Y3IJoLgrBMwLTsaMXaoWi8V8=;\n h=From:Date:Subject:To:Message-ID;\n b=MTaqJd+rR6hXrALXLEuEulP7jGp/qqIyYs1doX4q3K8LDSSWUk8birLRuBfOX2CWWQuFa42ePmY/2FjAtyKaAJyMgNYyuGJLFghG6qKRreym/HoBnY+82WIpbn3M0jdy9Vn6CJ20VL4Db9A01YOeUN44axSYPLDU7RduhWbllVs=","ARC-Authentication-Results":"i=1; server2.sourceware.org","From":"ppalka via Sourceware Forge\n ","Date":"Wed, 22 Apr 2026 18:27:27 +0000","Subject":"[PATCH v1 3/8] libstdc++: Directly implement ranges::inplace_merge\n [PR100795]","To":"gcc-patches mailing list ","Message-ID":"\n ","X-Mailer":"batrachomyomachia","X-Pull-Request-Organization":"gcc","X-Pull-Request-Repository":"gcc-TEST","X-Pull-Request":"https://forge.sourceware.org/gcc/gcc-TEST/pulls/57","References":"\n ","In-Reply-To":"\n ","X-Patch-URL":"\n https://forge.sourceware.org/gcc/gcc-TEST/commit/152d1d0171dd3b50d9d4299ee691f37d1525836d","X-BeenThere":"gcc-patches@gcc.gnu.org","X-Mailman-Version":"2.1.30","Precedence":"list","List-Id":"Gcc-patches mailing list ","List-Unsubscribe":",\n ","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n ","Reply-To":"gcc-patches mailing list ,\n ppalka@gcc.gnu.org","Errors-To":"gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org"},"content":"From: Patrick Palka \n\nAs with the previous patch, this patch reimplements ranges::inplace_merge\ndirectly instead of incorrectly forwarding to std::inplace_merge. In\naddition to the compatibility changes listed in the previous patch we\nalso:\n\n - explicitly cast the difference type (which can be an integer class) to\n ptrdiff_t when constructing a _Temporary_buffer\n\n\tPR libstdc++/100795\n\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/ranges_algo.h (__detail::__move_merge_adaptive):\n\tNew, based on the stl_algo.h implementation.\n\t(__detail::__move_merge_adaptive_backward): Likewise.\n\t(__detail::__rotate_adaptive): Likewise.\n\t(__detail::__merge_adaptive): Likewise.\n\t(__detail::__merge_adaptive_resize): Likewise.\n\t(__detail::__merge_without_buffer): Likewise.\n\t(__inplace_merge_fn::operator()): Reimplement in terms of the\n\tabove.\n\t* testsuite/25_algorithms/inplace_merge/constrained.cc (test03):\n\tNew test.\n---\n libstdc++-v3/include/bits/ranges_algo.h | 257 +++++++++++++++++-\n .../inplace_merge/constrained.cc | 36 +++\n 2 files changed, 289 insertions(+), 4 deletions(-)","diff":"diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h\nindex de935dde4f70..b0357600adbc 100644\n--- a/libstdc++-v3/include/bits/ranges_algo.h\n+++ b/libstdc++-v3/include/bits/ranges_algo.h\n@@ -3145,6 +3145,215 @@ namespace ranges\n \n inline constexpr __merge_fn merge{};\n \n+ namespace __detail\n+ {\n+ template\n+ void\n+ __move_merge_adaptive(_Iter1 __first1, _Iter1 __last1,\n+\t\t\t _Iter2 __first2, _Iter2 __last2,\n+\t\t\t _Out __result, _Comp __comp)\n+ {\n+\twhile (__first1 != __last1 && __first2 != __last2)\n+\t {\n+\t if (__comp(*__first2, *__first1))\n+\t {\n+\t\t*__result = ranges::iter_move(__first2);\n+\t\t++__first2;\n+\t }\n+\t else\n+\t {\n+\t\t*__result = ranges::iter_move(__first1);\n+\t\t++__first1;\n+\t }\n+\t ++__result;\n+\t }\n+\tif (__first1 != __last1)\n+\t ranges::move(__first1, __last1, __result);\n+ }\n+\n+ template\n+ void\n+ __move_merge_adaptive_backward(_Iter1 __first1, _Iter1 __last1,\n+\t\t\t\t _Iter2 __first2, _Iter2 __last2,\n+\t\t\t\t _Iter3 __result, _Comp __comp)\n+ {\n+\tif (__first1 == __last1)\n+\t {\n+\t ranges::move_backward(__first2, __last2, __result);\n+\t return;\n+\t }\n+\telse if (__first2 == __last2)\n+\t return;\n+\n+\t--__last1;\n+\t--__last2;\n+\twhile (true)\n+\t {\n+\t if (__comp(*__last2, *__last1))\n+\t {\n+\t\t*--__result = ranges::iter_move(__last1);\n+\t\tif (__first1 == __last1)\n+\t\t {\n+\t\t ranges::move_backward(__first2, ++__last2, __result);\n+\t\t return;\n+\t\t }\n+\t\t--__last1;\n+\t }\n+\t else\n+\t {\n+\t\t*--__result = ranges::iter_move(__last2);\n+\t\tif (__first2 == __last2)\n+\t\t return;\n+\t\t--__last2;\n+\t }\n+\t }\n+ }\n+\n+ template\n+ _Iter1\n+ __rotate_adaptive(_Iter1 __first, _Iter1 __middle, _Iter1 __last,\n+\t\t\titer_difference_t<_Iter1> __len1,\n+\t\t\titer_difference_t<_Iter1> __len2,\n+\t\t\t_Iter2 __buffer,\n+\t\t\titer_difference_t<_Iter1> __buffer_size)\n+ {\n+\t_Iter2 __buffer_end;\n+\tif (__len1 > __len2 && __len2 <= __buffer_size)\n+\t {\n+\t if (__len2)\n+\t {\n+\t\t__buffer_end = ranges::move(__middle, __last, __buffer).out;\n+\t\tranges::move_backward(__first, __middle, __last);\n+\t\treturn ranges::move(__buffer, __buffer_end, __first).out;\n+\t }\n+\t else\n+\t return __first;\n+\t }\n+\telse if (__len1 <= __buffer_size)\n+\t {\n+\t if (__len1)\n+\t {\n+\t\t__buffer_end = ranges::move(__first, __middle, __buffer).out;\n+\t\tranges::move(__middle, __last, __first);\n+\t\treturn ranges::move_backward(__buffer, __buffer_end, __last).out;\n+\t }\n+\t else\n+\t return __last;\n+\t }\n+\telse\n+\t return ranges::rotate(__first, __middle, __last).begin();\n+ }\n+\n+ template\n+ void\n+ __merge_adaptive(_Iter __first, _Iter __middle, _Iter __last,\n+\t\t iter_difference_t<_Iter> __len1,\n+\t\t iter_difference_t<_Iter> __len2,\n+\t\t _Pointer __buffer, _Comp __comp)\n+ {\n+\tif (__len1 <= __len2)\n+\t {\n+\t _Pointer __buffer_end = ranges::move(__first, __middle, __buffer).out;\n+\t __detail::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,\n+\t\t\t\t\t __first, __comp);\n+\t }\n+\telse\n+\t {\n+\t _Pointer __buffer_end = ranges::move(__middle, __last, __buffer).out;\n+\t __detail::__move_merge_adaptive_backward(__first, __middle, __buffer,\n+\t\t\t\t\t\t __buffer_end, __last, __comp);\n+\t }\n+ }\n+\n+ template\n+ void\n+ __merge_adaptive_resize(_Iter __first, _Iter __middle, _Iter __last,\n+\t\t\t _Distance __len1, _Distance __len2,\n+\t\t\t _Pointer __buffer, _Distance __buffer_size,\n+\t\t\t _Comp __comp)\n+ {\n+\tif (__len1 <= __buffer_size || __len2 <= __buffer_size)\n+\t __detail::__merge_adaptive(__first, __middle, __last,\n+\t\t\t\t __len1, __len2, __buffer, __comp);\n+\telse\n+\t {\n+\t _Iter __first_cut = __first;\n+\t _Iter __second_cut = __middle;\n+\t _Distance __len11 = 0;\n+\t _Distance __len22 = 0;\n+\t if (__len1 > __len2)\n+\t {\n+\t\t__len11 = __len1 / 2;\n+\t\tranges::advance(__first_cut, __len11);\n+\t\t__second_cut = ranges::lower_bound(__middle, __last, *__first_cut,\n+\t\t\t\t\t\t __comp);\n+\t\t__len22 = ranges::distance(__middle, __second_cut);\n+\t }\n+\t else\n+\t {\n+\t\t__len22 = __len2 / 2;\n+\t\tranges::advance(__second_cut, __len22);\n+\t\t__first_cut = ranges::upper_bound(__first, __middle, *__second_cut,\n+\t\t\t\t\t\t __comp);\n+\t\t__len11 = ranges::distance(__first, __first_cut);\n+\t }\n+\n+\t _Iter __new_middle\n+\t = __detail::__rotate_adaptive(__first_cut, __middle, __second_cut,\n+\t\t\t\t\t _Distance(__len1 - __len11), __len22,\n+\t\t\t\t\t __buffer, __buffer_size);\n+\t __detail::__merge_adaptive_resize(__first, __first_cut, __new_middle,\n+\t\t\t\t\t __len11, __len22,\n+\t\t\t\t\t __buffer, __buffer_size, __comp);\n+\t __detail::__merge_adaptive_resize(__new_middle, __second_cut, __last,\n+\t\t\t\t\t _Distance(__len1 - __len11),\n+\t\t\t\t\t _Distance(__len2 - __len22),\n+\t\t\t\t\t __buffer, __buffer_size, __comp);\n+\t }\n+ }\n+\n+ template\n+ constexpr void\n+ __merge_without_buffer(_Iter __first, _Iter __middle, _Iter __last,\n+\t\t\t _Distance __len1, _Distance __len2, _Comp __comp)\n+ {\n+\tif (__len1 == 0 || __len2 == 0)\n+\t return;\n+\n+\tif (__len1 + __len2 == 2)\n+\t {\n+\t if (__comp(*__middle, *__first))\n+\t ranges::iter_swap(__first, __middle);\n+\t return;\n+\t }\n+\n+\t_Iter __first_cut = __first;\n+\t_Iter __second_cut = __middle;\n+\t_Distance __len11 = 0;\n+\t_Distance __len22 = 0;\n+\tif (__len1 > __len2)\n+\t {\n+\t __len11 = __len1 / 2;\n+\t ranges::advance(__first_cut, __len11);\n+\t __second_cut = ranges::lower_bound(__middle, __last, *__first_cut, __comp);\n+\t __len22 = ranges::distance(__middle, __second_cut);\n+\t }\n+\telse\n+\t {\n+\t __len22 = __len2 / 2;\n+\t ranges::advance(__second_cut, __len22);\n+\t __first_cut = ranges::upper_bound(__first, __middle, *__second_cut, __comp);\n+\t __len11 = ranges::distance(__first, __first_cut);\n+\t }\n+\n+\t_Iter __new_middle = ranges::rotate(__first_cut, __middle, __second_cut).begin();\n+\t__detail::__merge_without_buffer(__first, __first_cut, __new_middle,\n+\t\t\t\t\t __len11, __len22, __comp);\n+\t__detail::__merge_without_buffer(__new_middle, __second_cut, __last,\n+\t\t\t\t\t __len1 - __len11, __len2 - __len22, __comp);\n+ }\n+ } // namespace __detail\n+\n struct __inplace_merge_fn\n {\n template _Sent,\n@@ -3156,10 +3365,50 @@ namespace ranges\n operator()(_Iter __first, _Iter __middle, _Sent __last,\n \t\t _Comp __comp = {}, _Proj __proj = {}) const\n {\n-\tauto __lasti = ranges::next(__first, __last);\n-\tstd::inplace_merge(std::move(__first), std::move(__middle), __lasti,\n-\t\t\t __detail::__make_comp_proj(__comp, __proj));\n-\treturn __lasti;\n+\tif constexpr (!same_as<_Iter, _Sent>)\n+\t return (*this)(__first, __middle, ranges::next(__middle, __last),\n+\t\t\t std::move(__comp), std::move(__proj));\n+\telse\n+\t {\n+\t using _DistanceType = iter_difference_t<_Iter>;\n+\n+\t if (__first == __middle || __middle == __last)\n+\t return __last;\n+\n+\t const _DistanceType __len1 = ranges::distance(__first, __middle);\n+\t const _DistanceType __len2 = ranges::distance(__middle, __last);\n+\n+\t auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);\n+\n+#if _GLIBCXX_HOSTED\n+# if __glibcxx_constexpr_algorithms >= 202306L // >= C++26\n+\t if consteval {\n+\t __detail::__merge_without_buffer(__first, __middle, __last,\n+\t\t\t\t\t __len1, __len2, __comp_proj);\n+\t return __last;\n+\t }\n+# endif\n+\t using _TmpBuf = _Temporary_buffer<_Iter, iter_value_t<_Iter>>;\n+\t // __merge_adaptive will use a buffer for the smaller of\n+\t // [first,middle) and [middle,last).\n+\t _TmpBuf __buf(__first, ptrdiff_t(ranges::min(__len1, __len2)));\n+\n+\t if (__buf.size() == __buf._M_requested_size()) [[likely]]\n+\t __detail::__merge_adaptive\n+\t\t(__first, __middle, __last, __len1, __len2, __buf.begin(), __comp_proj);\n+\t else if (__buf.begin() == 0) [[unlikely]]\n+\t __detail::__merge_without_buffer\n+\t\t(__first, __middle, __last, __len1, __len2, __comp_proj);\n+\t else\n+\t __detail::__merge_adaptive_resize\n+\t\t(__first, __middle, __last, __len1, __len2, __buf.begin(),\n+\t\t _DistanceType(__buf.size()), __comp_proj);\n+#else\n+\t __detail::__merge_without_buffer\n+\t (__first, __middle, __last, __len1, __len2, __comp_proj);\n+#endif\n+\t return __last;\n+\t }\n }\n \n template\n+#include \n #include \n #include \n #include \n@@ -60,9 +61,44 @@ test02()\n }\n \n \n+void\n+test03()\n+{\n+ // PR libstdc++/100795 - ranges::inplace_merge should not use\n+ // std::inplace_merge directly\n+#if __SIZEOF_INT128__\n+ auto v = std::views::iota(__int128(0), __int128(20));\n+#else\n+ auto v = std::views::iota(0ll, 20ll);\n+#endif\n+\n+ int storage[20] = {2,5,4,3,1,6,7,9,10,8,11,14,12,13,15,16,18,0,19,17};\n+ auto w = v | std::views::transform([&](auto i) -> int& { return storage[i]; });\n+ using type = decltype(w);\n+ using cat = std::iterator_traits>::iterator_category;\n+ static_assert( std::same_as );\n+ static_assert( std::ranges::random_access_range );\n+\n+ ranges::sort(w | std::views::take(10));\n+ ranges::sort(w | std::views::drop(10));\n+ ranges::inplace_merge(w, w.begin() + 10);\n+ VERIFY( ranges::equal(w, v) );\n+\n+ ranges::sort(w | std::views::take(10), std::ranges::greater{});\n+ ranges::sort(w | std::views::drop(10), std::ranges::greater{});\n+ ranges::inplace_merge(w, w.begin() + 10, std::ranges::greater{});\n+ VERIFY( ranges::equal(w, v | std::views::reverse) );\n+\n+ ranges::sort(w | std::views::take(10), std::ranges::greater{}, std::negate{});\n+ ranges::sort(w | std::views::drop(10), std::ranges::greater{}, std::negate{});\n+ ranges::inplace_merge(w, w.begin() + 10, std::ranges::greater{}, std::negate{});\n+ VERIFY( ranges::equal(w, v) );\n+}\n+\n int\n main()\n {\n test01();\n test02();\n+ test03();\n }\n","prefixes":["v1","3/8"]}