{"id":2226254,"url":"http://patchwork.ozlabs.org/api/covers/2226254/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/cover/bmm.hhubaw7tx4.gcc.gcc-TEST.redi.18.1.0@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-22T10:27:38","name":"[v1,0/1] libstdc++: Simplify _Hashtable merge functions","submitter":{"id":93210,"url":"http://patchwork.ozlabs.org/api/people/93210/?format=json","name":"Jonathan Wakely via Sourceware Forge","email":"forge-bot+redi@forge-stage.sourceware.org"},"mbox":"http://patchwork.ozlabs.org/project/gcc/cover/bmm.hhubaw7tx4.gcc.gcc-TEST.redi.18.1.0@forge-stage.sourceware.org/mbox/","series":[{"id":500977,"url":"http://patchwork.ozlabs.org/api/series/500977/?format=json","web_url":"http://patchwork.ozlabs.org/project/gcc/list/?series=500977","date":"2026-04-22T10:27:38","name":"libstdc++: Simplify _Hashtable merge functions","version":1,"mbox":"http://patchwork.ozlabs.org/series/500977/mbox/"}],"comments":"http://patchwork.ozlabs.org/api/covers/2226254/comments/","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=2620:52:6:3111::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\n [IPv6:2620:52:6:3111::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 4g0wtg2JdQz1y2d\n\tfor ; Wed, 22 Apr 2026 20:48:27 +1000 (AEST)","from vm01.sourceware.org (localhost [127.0.0.1])\n\tby sourceware.org (Postfix) with ESMTP id 340F74332F1A\n\tfor ; Wed, 22 Apr 2026 10:48:25 +0000 (GMT)","from forge-stage.sourceware.org (vm08.sourceware.org [38.145.34.39])\n by sourceware.org (Postfix) with ESMTPS id ACE014BC897C\n for ; Wed, 22 Apr 2026 10:28:29 +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 817F9405B3\n for ; Wed, 22 Apr 2026 10:28:29 +0000 (UTC)"],"DKIM-Filter":["OpenDKIM Filter v2.11.0 sourceware.org 340F74332F1A","OpenDKIM Filter v2.11.0 sourceware.org ACE014BC897C"],"DMARC-Filter":"OpenDMARC Filter v1.4.2 sourceware.org ACE014BC897C","ARC-Filter":"OpenARC Filter v1.0.0 sourceware.org ACE014BC897C","ARC-Seal":"i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1776853709; cv=none;\n b=TZP/ht1py8IsusNkfFrqSS/uc5dzhzUYceWHK2mXMU7nYqCAGfnOsnGXpFGpcUuB5haOTGVTQXlY1ipISq7HaOwRCp8g4JKU9jLjvwCwzYYzCzDcozG7eIJg3pWIB4f8A1jAbD6wAluJjZdZpJqnOEIfDX6Qf1yOrY4muX0wi84=","ARC-Message-Signature":"i=1; a=rsa-sha256; d=sourceware.org; s=key;\n t=1776853709; c=relaxed/simple;\n bh=VABVcHR9pznKoY25wWx9tNutR22S3rssMM8I/jhMOuQ=;\n h=From:Date:Subject:To:Message-ID;\n b=tpFptrzrWItBclEvTK/YTAfM1iJnOq3SRkCPbxVNPvMVFj2klYfHHMIgMOi/Sfmo3sVkbj16pJYMbD3MI2mztLJ0R6h6YoUnGQ9LisNwMlKFI5oEPECPqw0lzO/AicRqZAA8zD4c1wAu7B8VzSKN1BmhwqESv7y2D8m9PtFuQfM=","ARC-Authentication-Results":"i=1; server2.sourceware.org","From":"Jonathan Wakely via Sourceware Forge\n ","Date":"Wed, 22 Apr 2026 10:27:38 +0000","Subject":"[PATCH v1 0/1] libstdc++: Simplify _Hashtable merge functions","To":"gcc-patches mailing list ","Message-ID":"\n ","X-Mailer":"batrachomyomachia","X-Requested-Reviewer":"fdumont","X-Pull-Request-Organization":"gcc","X-Pull-Request-Repository":"gcc-TEST","X-Pull-Request":"https://forge.sourceware.org/gcc/gcc-TEST/pulls/18","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 , redi@gcc.gnu.org","Errors-To":"gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org"},"content":"Hi gcc-patches mailing list,\nJonathan Wakely via Sourceware Forge has requested that the following forgejo pull request\nbe published on the mailing list.\n\nCreated on: 2024-11-07 22:17:42+00:00\nLatest update: 2025-08-13 07:25:54+00:00\nChanges: 0 changed files, 0 additions, 0 deletions\nHead revision: redi/gcc ref refs/pull/18/head commit 55b7bcc7b8e4b5c08218e0474de4b61addb8faa0\nBase revision: gcc/gcc-TEST ref trunk commit e97179bacd067ccd3ee765632e0c034df152ccb6 r15-5033-ge97179bacd067c\nMerge base: e97179bacd067ccd3ee765632e0c034df152ccb6\nFull diff url: https://forge.sourceware.org/gcc/gcc-TEST/pulls/18.diff\nDiscussion: https://forge.sourceware.org/gcc/gcc-TEST/pulls/18\nRequested Reviewers: fdumont\n\nI realised that _M_merge_unique and _M_merge_multi call extract(iter)\nwhich then has to call _M_get_previous_node to iterate through the\nbucket to find the node before the one iter points to. Since the merge\nfunction is already iterating over the entire container, we had the\nprevious node a moment ago. Walking the whole bucket to find it again is\nwasteful. We could just rewrite the loop in terms of node pointers\ninstead of iterators, and then call _M_extract_node directly. However,\nthis is only possible when the source container is the same type as the\ndestination, because otherwise we can't access the source's private\nmembers (_M_before_begin, _M_begin, _M_extract_node etc.)\n\nAdd overloads of _M_merge_unique and _M_merge_multi that work with\nsource containers of the same type, to enable this optimization.\n\nFor both overloads of _M_merge_unique we can also remove the conditional\nmodifications to __n_elt and just consistently decrement it for every\nelement processed. Use a multiplier of one or zero that dictates whether\n__n_elt is passed to _M_insert_unique_node or not. We can also remove\nthe repeated calls to size() and just keep track of the size in a local\nvariable.\n\nAlthough _M_merge_unique and _M_merge_multi should be safe for\n\"self-merge\", i.e. when doing c.merge(c), it's wasteful to search/insert\nevery element when we don't need to do anything. Add 'this == &source'\nchecks to the overloads taking an lvalue of the container's own type.\nBecause those checks aren't needed for the rvalue overloads, change\nthose to call the underlying _M_merge_xxx function directly instead of\ngoing through the lvalue overload that checks the address.\n\nI've also added more extensive tests for better coverage of the new\noverloads added in this commit.\n\n```\nlibstdc++-v3/ChangeLog:\n\n\t* include/bits/hashtable.h (_M_merge_unique): Add overload for\n\tmerging from same type.\n\t(_M_merge_unique): Simplify size tracking. Add\n\tcomment.\n\t(_M_merge_multi): Add overload for merging from same type.\n\t(_M_merge_multi): Add comment.\n\t* include/bits/unordered_map.h (unordered_map::merge): Check for\n\tself-merge in the lvalue overload. Call _M_merge_unique directly\n\tfor the rvalue overload.\n\t(unordered_multimap::merge): Likewise.\n\t* include/bits/unordered_set.h (unordered_set::merge): Likewise.\n\t(unordered_multiset::merge): Likewise.\n\t* testsuite/23_containers/unordered_map/modifiers/merge.cc:\n\tAdd more tests.\n\t* testsuite/23_containers/unordered_multimap/modifiers/merge.cc:\n\tLikewise.\n\t* testsuite/23_containers/unordered_multiset/modifiers/merge.cc:\n\tLikewise.\n\t* testsuite/23_containers/unordered_set/modifiers/merge.cc:\n\tLikewise.\n```\n\n\nChanged files:\n- M: libstdc++-v3/include/bits/hashtable.h\n- M: libstdc++-v3/include/bits/unordered_map.h\n- M: libstdc++-v3/include/bits/unordered_set.h\n- M: libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/merge.cc\n- M: libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/merge.cc\n- M: libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc\n- M: libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc\n\n\nJonathan Wakely (1):\n libstdc++: Simplify _Hashtable merge functions\n\n libstdc++-v3/include/bits/hashtable.h | 118 ++++++++++++----\n libstdc++-v3/include/bits/unordered_map.h | 19 ++-\n libstdc++-v3/include/bits/unordered_set.h | 19 ++-\n .../unordered_map/modifiers/merge.cc | 130 ++++++++++++++++++\n .../unordered_multimap/modifiers/merge.cc | 119 ++++++++++++++++\n .../unordered_multiset/modifiers/merge.cc | 121 ++++++++++++++++\n .../unordered_set/modifiers/merge.cc | 128 +++++++++++++++++\n 7 files changed, 626 insertions(+), 28 deletions(-)"}