From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x533.google.com (mail-ed1-x533.google.com [IPv6:2a00:1450:4864:20::533]) by sourceware.org (Postfix) with ESMTPS id A7F8A3858C83; Wed, 22 Feb 2023 06:08:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A7F8A3858C83 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-ed1-x533.google.com with SMTP id cy6so20568837edb.5; Tue, 21 Feb 2023 22:08:28 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=in-reply-to:references:cc:to:from:content-language:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=e89P5hm3EbIEkjNkq6x8+DRMaPxX0c9LcoD/KirdGj0=; b=WUIJACzPLtGrgiUq03xumOYsscttSNfsDQTVDGLxbwKLT6qMgBZSHvQjR7TOhYiGnA WBKUN5bMjsjILE/PA5KnKwDa2Y5nT642R5UiODBtbZlhwJ0Q1HcT4C8CDEKpeCEwPx3i ugUq1GducY6Bhl2fL9yUsKTr84YNjtX+oGL9kAu3W1lvZGr7SVx/rYGVdSndxq6A/zsU umsfc7nnrNj8LTkqNu0YeqFmIiBl0KuHiq4usNUBjNsUhn2790jdrpz0IEh279RX/aEt etVD4bMSj0K5Jrh6XMTYbataG0lLUaeunQ/wMIyxDLuXahi6bGPGat/YPcDo+S4CC02/ MlXQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=in-reply-to:references:cc:to:from:content-language:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=e89P5hm3EbIEkjNkq6x8+DRMaPxX0c9LcoD/KirdGj0=; b=BfGcNA8mwqlmFRIW1Bjz7bU/2bJGVhVXnMq5qk2VZolK4GcLp8HcIWS9tYf5P3ui95 X4I2njsT0I5MtMKFiPUp73Ftty21tJ1tsaKBujlQplXR3jYLx8TqxtGlCXA1etT/iU2A 6dJ4ux3LxO4zZegxRfSc2wmGG4sw2OsGexutQhnKEV2CgZVFwUdMIgZZZTOvO4+t68sq TulL+ifBJl+ejRQwLL+JHUZzCZRpiBo0rFOR5qVtAYwCQT15bf3iW0TSkL8bQr0mh7nx ED5L0bg7tBkqNn+ld7wA8a8LtaeXmaLzPE5g1+lkBA2U9EatNdI7mJdYGY1KugyBFCmC Dr2A== X-Gm-Message-State: AO0yUKWiW6/gvOWR+8FM0Zjic3SWjiCRMf3e4luqjnvL9ELe7uEyFb2x a6wdfWdfGrSx5GkiZF1Un2GbBdcxrOY= X-Google-Smtp-Source: AK7set+lkFOTe6fGwK4zNbH43wc3l9ishzrWEPEyUXmwlh1K/mrlm0AU0Bmy4MpmZO2lh6UPx1fRUg== X-Received: by 2002:a05:6402:25c2:b0:49e:4786:a0e2 with SMTP id x2-20020a05640225c200b0049e4786a0e2mr6468588edb.14.1677046105938; Tue, 21 Feb 2023 22:08:25 -0800 (PST) Received: from [10.22.3.31] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id b2-20020a50b402000000b004aef4f32edesm2356080edh.88.2023.02.21.22.08.25 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 21 Feb 2023 22:08:25 -0800 (PST) Content-Type: multipart/mixed; boundary="------------0KAqPBTUo5sJIg5s01cXcWZq" Message-ID: <98823f83-ae62-f3e4-4091-01841b08fbb7@gmail.com> Date: Wed, 22 Feb 2023 07:08:24 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.7.1 Subject: [PATCH] libstdc++: Limit allocations in _Rb_tree 2/2 Content-Language: fr From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= To: "libstdc++@gcc.gnu.org" Cc: gcc-patches References: <43172ea5-6729-02c5-d374-9537fff7eb4c@gmail.com> <7313d189-ae56-4582-6f23-9263dbf57dd3@gmail.com> In-Reply-To: <7313d189-ae56-4582-6f23-9263dbf57dd3@gmail.com> X-Spam-Status: No, score=-6.1 required=5.0 tests=BAYES_00,BODY_8BITS,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,KAM_NUMSUBJECT,RCVD_IN_ABUSEAT,RCVD_IN_BARRACUDACENTRAL,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: This is a multi-part message in MIME format. --------------0KAqPBTUo5sJIg5s01cXcWZq Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit This one is a refinement for multimap/multiset. It allows to have share the same key if managed with ref counting like the cow string.     libstdc++: [_Rb_tree] Limit allocations on equal insertions [PR 96088]     When inserting the same key several times prefer to insert the new entry using the     current stored key_type instance if this copy is noexcept. Otherwise create a new     key instance from input argument.     libstdc++-v3/ChangeLog:             PR libstdc++/96088             * include/bits/cow_string.h (basic_string<>::basic_string(const basic_string&)):             Add noexcept qualification when allocator is always equal.             * include/bits/stl_tree.h (_Rb_tree<>::_M_get_insert_equal_pos_tr): New.             (_Rb_tree<>::_M_emplace_equal_tr): New, use latter.             (_Rb_tree<>::_M_emplace_equal_aux): New, use latter. (_Rb_tree<>::_M_emplace_equal<_Arg>(_Arg&&)): New, use latter.             * testsuite/23_containers/multimap/96088.cc (test01): Add check on redundant             insertion.             (test02): Likewise.             * testsuite/23_containers/multiset/96088.cc (test01, test02): Likewise. François --------------0KAqPBTUo5sJIg5s01cXcWZq Content-Type: text/x-patch; charset=UTF-8; name="pr96088_multimap.patch" Content-Disposition: attachment; filename="pr96088_multimap.patch" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL2xpYnN0ZGMrKy12My9pbmNsdWRlL2JpdHMvY293X3N0cmluZy5oIGIv bGlic3RkYysrLXYzL2luY2x1ZGUvYml0cy9jb3dfc3RyaW5nLmgKaW5kZXggYWQ5OTI5YzRh ZDMuLmNkZmJlNWUxOTBiIDEwMDY0NAotLS0gYS9saWJzdGRjKystdjMvaW5jbHVkZS9iaXRz L2Nvd19zdHJpbmcuaAorKysgYi9saWJzdGRjKystdjMvaW5jbHVkZS9iaXRzL2Nvd19zdHJp bmcuaApAQCAtNTQxLDYgKzU0MSw3IEBAIF9HTElCQ1hYX0JFR0lOX05BTUVTUEFDRV9WRVJT SU9OCiAgICAgICAgKiAgQHBhcmFtICBfX3N0ciAgU291cmNlIHN0cmluZy4KICAgICAgICAq LwogICAgICAgYmFzaWNfc3RyaW5nKGNvbnN0IGJhc2ljX3N0cmluZyYgX19zdHIpCisJX0dM SUJDWFhfTk9FWENFUFRfSUYoX0NoYXJUX2FsbG9jX3RyYWl0czo6X1NfYWx3YXlzX2VxdWFs KCkpCiAgICAgICA6IF9NX2RhdGFwbHVzKF9fc3RyLl9NX3JlcCgpLT5fTV9ncmFiKF9BbGxv YyhfX3N0ci5nZXRfYWxsb2NhdG9yKCkpLAogCQkJCQkgICAgX19zdHIuZ2V0X2FsbG9jYXRv cigpKSwKIAkJICAgIF9fc3RyLmdldF9hbGxvY2F0b3IoKSkKZGlmZiAtLWdpdCBhL2xpYnN0 ZGMrKy12My9pbmNsdWRlL2JpdHMvc3RsX3RyZWUuaCBiL2xpYnN0ZGMrKy12My9pbmNsdWRl L2JpdHMvc3RsX3RyZWUuaAppbmRleCAyMWU5NTg2YjBhMy4uYzNhNGE5N2NmY2YgMTAwNjQ0 Ci0tLSBhL2xpYnN0ZGMrKy12My9pbmNsdWRlL2JpdHMvc3RsX3RyZWUuaAorKysgYi9saWJz dGRjKystdjMvaW5jbHVkZS9iaXRzL3N0bF90cmVlLmgKQEAgLTk2OCw2ICs5NjgsMTAgQEAg X0dMSUJDWFhfQkVHSU5fTkFNRVNQQUNFX1ZFUlNJT04KICAgICAgIHRlbXBsYXRlPHR5cGVu YW1lIF9LdD4KIAlwYWlyPF9CYXNlX3B0ciwgX0Jhc2VfcHRyPgogCV9NX2dldF9pbnNlcnRf dW5pcXVlX3Bvc190cihjb25zdCBfS3QmIF9fayk7CisKKyAgICAgIHRlbXBsYXRlPHR5cGVu YW1lIF9LdD4KKwlwYWlyPF9CYXNlX3B0ciwgX0Jhc2VfcHRyPgorCV9NX2dldF9pbnNlcnRf ZXF1YWxfcG9zX3RyKGNvbnN0IF9LdCYgX19rKTsKICNlbmRpZgogCiAgICAgICBwYWlyPF9C YXNlX3B0ciwgX0Jhc2VfcHRyPgpAQCAtMTIyNSw2ICsxMjI5LDE5IEBAIF9HTElCQ1hYX0JF R0lOX05BTUVTUEFDRV9WRVJTSU9OCiAJICAgIHN0ZDo6Zm9yd2FyZDxfQXJnPihfX2FyZykp OwogCX0KIAorICAgICAgdGVtcGxhdGU8dHlwZW5hbWUgX0t0LCB0eXBlbmFtZSBfQXJnPgor CWl0ZXJhdG9yCisJX01fZW1wbGFjZV9lcXVhbF9rdihfS3QmJiwgX0FyZyYmKTsKKworICAg ICAgdGVtcGxhdGU8dHlwZW5hbWUgX0FyZz4KKwlpdGVyYXRvcgorCV9NX2VtcGxhY2VfZXF1 YWxfYXV4KF9BcmcmJiBfX2FyZykKKwl7CisJICByZXR1cm4gX01fZW1wbGFjZV9lcXVhbF9r digKKwkgICAgX1NfZm9yd2FyZF9rZXkoX0tleU9mVmFsdWV7fShzdGQ6OmZvcndhcmQ8X0Fy Zz4oX19hcmcpKSksCisJICAgIHN0ZDo6Zm9yd2FyZDxfQXJnPihfX2FyZykpOworCX0KKwog ICAgICAgdGVtcGxhdGU8dHlwZW5hbWUgX0FyZz4KIAlwYWlyPGl0ZXJhdG9yLCBib29sPgog CV9NX2VtcGxhY2VfdW5pcXVlKF9BcmcmJiBfX2FyZykKQEAgLTEyMzcsNiArMTI1NCwxNCBA QCBfR0xJQkNYWF9CRUdJTl9OQU1FU1BBQ0VfVkVSU0lPTgogCXBhaXI8aXRlcmF0b3IsIGJv b2w+CiAJX01fZW1wbGFjZV91bmlxdWUoX0FyZ3MmJi4uLiBfX2FyZ3MpOwogCisgICAgICB0 ZW1wbGF0ZTx0eXBlbmFtZSBfQXJnPgorCWl0ZXJhdG9yCisJX01fZW1wbGFjZV9lcXVhbChf QXJnJiYgX19hcmcpCisJeworCSAgdXNpbmcgX190b192YWx1ZSA9IF9Db252ZXJ0VG9WYWx1 ZVR5cGU8X0tleU9mVmFsdWUsIHZhbHVlX3R5cGU+OworCSAgcmV0dXJuIF9NX2VtcGxhY2Vf ZXF1YWxfYXV4KF9fdG9fdmFsdWV7fShzdGQ6OmZvcndhcmQ8X0FyZz4oX19hcmcpKSk7CisJ fQorCiAgICAgICB0ZW1wbGF0ZTx0eXBlbmFtZS4uLiBfQXJncz4KIAlpdGVyYXRvcgogCV9N X2VtcGxhY2VfZXF1YWwoX0FyZ3MmJi4uLiBfX2FyZ3MpOwpAQCAtMjM1NSw2ICsyMzgwLDI2 IEBAIF9HTElCQ1hYX0JFR0lOX05BTUVTUEFDRV9WRVJTSU9OCiAJICByZXR1cm4gX1Jlcyhf X3gsIF9feSk7CiAJcmV0dXJuIF9SZXMoX19qLl9NX25vZGUsIDApOwogICAgICAgfQorCisg IHRlbXBsYXRlPHR5cGVuYW1lIF9LZXksIHR5cGVuYW1lIF9WYWwsIHR5cGVuYW1lIF9LZXlP ZlZhbHVlLAorCSAgIHR5cGVuYW1lIF9Db21wYXJlLCB0eXBlbmFtZSBfQWxsb2M+CisgICAg dGVtcGxhdGU8dHlwZW5hbWUgX0t0PgorICAgICAgYXV0bworICAgICAgX1JiX3RyZWU8X0tl eSwgX1ZhbCwgX0tleU9mVmFsdWUsIF9Db21wYXJlLCBfQWxsb2M+OjoKKyAgICAgIF9NX2dl dF9pbnNlcnRfZXF1YWxfcG9zX3RyKGNvbnN0IF9LdCYgX19rKQorICAgICAgLT4gcGFpcjxf QmFzZV9wdHIsIF9CYXNlX3B0cj4KKyAgICAgIHsKKwl0eXBlZGVmIHBhaXI8X0Jhc2VfcHRy LCBfQmFzZV9wdHI+IF9SZXM7CisJX0xpbmtfdHlwZSBfX3ggPSBfTV9iZWdpbigpOworCV9C YXNlX3B0ciBfX3kgPSBfTV9lbmQoKTsKKwl3aGlsZSAoX194ICE9IDApCisJICB7CisJICAg IF9feSA9IF9feDsKKwkgICAgX194ID0gX01faW1wbC5fTV9rZXlfY29tcGFyZShfX2ssIF9T X2tleShfX3gpKSA/CisJICAgICAgX1NfbGVmdChfX3gpIDogX1NfcmlnaHQoX194KTsKKwkg IH0KKwlyZXR1cm4gX1JlcyhfX3gsIF9feSk7CisgICAgICB9CiAjZW5kaWYKIAogICB0ZW1w bGF0ZTx0eXBlbmFtZSBfS2V5LCB0eXBlbmFtZSBfVmFsLCB0eXBlbmFtZSBfS2V5T2ZWYWx1 ZSwKQEAgLTI2NjEsNiArMjcwNiwyNiBAQCBfR0xJQkNYWF9CRUdJTl9OQU1FU1BBQ0VfVkVS U0lPTgogCXJldHVybiB7IGl0ZXJhdG9yKF9fcmVzLmZpcnN0KSwgZmFsc2UgfTsKICAgICAg IH0KIAorICB0ZW1wbGF0ZTx0eXBlbmFtZSBfS2V5LCB0eXBlbmFtZSBfVmFsLCB0eXBlbmFt ZSBfS2V5T2ZWYWx1ZSwKKwkgICB0eXBlbmFtZSBfQ29tcGFyZSwgdHlwZW5hbWUgX0FsbG9j PgorICAgIHRlbXBsYXRlPHR5cGVuYW1lIF9LdCwgdHlwZW5hbWUgX0FyZz4KKyAgICAgIGF1 dG8KKyAgICAgIF9SYl90cmVlPF9LZXksIF9WYWwsIF9LZXlPZlZhbHVlLCBfQ29tcGFyZSwg X0FsbG9jPjo6CisgICAgICBfTV9lbXBsYWNlX2VxdWFsX2t2KF9LdCYmIF9faywgX0FyZyYm IF9fYXJnKQorICAgICAgLT4gaXRlcmF0b3IKKyAgICAgIHsKKwlhdXRvIF9fcmVzID0gX01f Z2V0X2luc2VydF9lcXVhbF9wb3NfdHIoX19rKTsKKwlfQXV0b19ub2RlIF9feiA9CisJICAo IWlzX25vdGhyb3dfY29weV9jb25zdHJ1Y3RpYmxlPGtleV90eXBlPjo6dmFsdWUKKwkgICB8 fCBfX3Jlcy5zZWNvbmQgPT0gX01fZW5kKCkKKwkgICB8fCBfTV9pbXBsLl9NX2tleV9jb21w YXJlKF9faywgX1Nfa2V5KF9fcmVzLnNlY29uZCkpKQorCSAgPyBfU19idWlsZF9ub2RlKCp0 aGlzLCBzdGQ6OmZvcndhcmQ8X0t0PihfX2spLAorCQkJICBzdGQ6OmZvcndhcmQ8X0FyZz4o X19hcmcpLCBfS2V5T2ZWYWx1ZXt9KQorCSAgOiBfU19idWlsZF9ub2RlKCp0aGlzLCBfU19r ZXkoX19yZXMuc2Vjb25kKSwKKwkJCSAgc3RkOjpmb3J3YXJkPF9Bcmc+KF9fYXJnKSwgX0tl eU9mVmFsdWV7fSk7CisJcmV0dXJuIF9fei5fTV9pbnNlcnQoX19yZXMpOworICAgICAgfQor CiAgIHRlbXBsYXRlPHR5cGVuYW1lIF9LZXksIHR5cGVuYW1lIF9WYWwsIHR5cGVuYW1lIF9L ZXlPZlZhbHVlLAogCSAgIHR5cGVuYW1lIF9Db21wYXJlLCB0eXBlbmFtZSBfQWxsb2M+CiAg ICAgdGVtcGxhdGU8dHlwZW5hbWUuLi4gX0FyZ3M+CmRpZmYgLS1naXQgYS9saWJzdGRjKyst djMvdGVzdHN1aXRlLzIzX2NvbnRhaW5lcnMvbXVsdGltYXAvOTYwODguY2MgYi9saWJzdGRj KystdjMvdGVzdHN1aXRlLzIzX2NvbnRhaW5lcnMvbXVsdGltYXAvOTYwODguY2MKaW5kZXgg OTE5YzVlNTljNzEuLjFhNzc4YTA3ODVkIDEwMDY0NAotLS0gYS9saWJzdGRjKystdjMvdGVz dHN1aXRlLzIzX2NvbnRhaW5lcnMvbXVsdGltYXAvOTYwODguY2MKKysrIGIvbGlic3RkYysr LXYzL3Rlc3RzdWl0ZS8yM19jb250YWluZXJzL211bHRpbWFwLzk2MDg4LmNjCkBAIC0xLDQg KzEsNSBAQAogLy8geyBkZy1kbyBydW4geyB0YXJnZXQgYysrMTcgfSB9CisvLyB7IGRnLWFk ZC1vcHRpb25zIG5vX3BjaCB9CiAvLyB7IGRnLXJlcXVpcmUtZWZmZWN0aXZlLXRhcmdldCBz dGRfYWxsb2NhdG9yX25ldyB9CiAKIC8vIENvcHlyaWdodCAoQykgMjAyMyBGcmVlIFNvZnR3 YXJlIEZvdW5kYXRpb24sIEluYy4KQEAgLTIwLDYgKzIxLDkgQEAKIAogLy8gbGlic3RkYysr Lzk2MDg4CiAKKyN1bmRlZiBfR0xJQkNYWF9VU0VfQ1hYMTFfQUJJCisjZGVmaW5lIF9HTElC Q1hYX1VTRV9DWFgxMV9BQkkgMAorCiAjaW5jbHVkZSA8c3RyaW5nX3ZpZXc+CiAjaW5jbHVk ZSA8c3RyaW5nPgogI2luY2x1ZGUgPG1hcD4KQEAgLTQyLDYgKzQ2LDE1IEBAIHRlc3QwMSgp CiAKICAgVkVSSUZZKCBfX2dudV90ZXN0Ojpjb3VudGVyOjpjb3VudCgpID09IDIgKTsKICAg VkVSSUZZKCBfX2dudV90ZXN0Ojpjb3VudGVyOjpnZXQoKS5fTV9pbmNyZW1lbnRzID09IDIg KTsKKworICAvLyBBbGxvY2F0ZSBhIG5vZGUgYW5kIHRoZSBzdGQ6OnN0cmluZyAodW5sZXNz IENPVykuCisgIGNvbnN0ZXhwciBzdGQ6OnNpemVfdCBpbmNyZW1lbnRzID0gX0dMSUJDWFhf VVNFX0NYWDExX0FCSSA/IDIgOiAxOworCisgIGZvby5pbnNlcnQobHN0LmJlZ2luKCksIGxz dC5lbmQoKSk7CisgIFZFUklGWSggZm9vLnNpemUoKSA9PSAyICk7CisKKyAgVkVSSUZZKCBf X2dudV90ZXN0Ojpjb3VudGVyOjpjb3VudCgpID09IDIgKyBpbmNyZW1lbnRzICk7CisgIFZF UklGWSggX19nbnVfdGVzdDo6Y291bnRlcjo6Z2V0KCkuX01faW5jcmVtZW50cyA9PSAyICsg aW5jcmVtZW50cyApOwogfQogCiB2b2lkCkBAIC01NCw2ICs2NywxNSBAQCB0ZXN0MDIoKQog CiAgIFZFUklGWSggX19nbnVfdGVzdDo6Y291bnRlcjo6Y291bnQoKSA9PSAyICk7CiAgIFZF UklGWSggX19nbnVfdGVzdDo6Y291bnRlcjo6Z2V0KCkuX01faW5jcmVtZW50cyA9PSAyICk7 CisKKyAgLy8gQWxsb2NhdGUgYSBub2RlIGFuZCB0aGUgc3RkOjpzdHJpbmcgKHVubGVzcyBD T1cpLgorICBjb25zdGV4cHIgc3RkOjpzaXplX3QgaW5jcmVtZW50cyA9IF9HTElCQ1hYX1VT RV9DWFgxMV9BQkkgPyAyIDogMTsKKworICBmb28uaW5zZXJ0KGxzdC5iZWdpbigpLCBsc3Qu ZW5kKCkpOworICBWRVJJRlkoIGZvby5zaXplKCkgPT0gMiApOworCisgIFZFUklGWSggX19n bnVfdGVzdDo6Y291bnRlcjo6Y291bnQoKSA9PSAyICsgaW5jcmVtZW50cyApOworICBWRVJJ RlkoIF9fZ251X3Rlc3Q6OmNvdW50ZXI6OmdldCgpLl9NX2luY3JlbWVudHMgPT0gMiArIDIg KTsKIH0KIAogaW50Cg== --------------0KAqPBTUo5sJIg5s01cXcWZq--