From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x634.google.com (mail-ej1-x634.google.com [IPv6:2a00:1450:4864:20::634]) by sourceware.org (Postfix) with ESMTPS id 8E8913851AB4; Mon, 20 Jun 2022 16:57:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8E8913851AB4 Received: by mail-ej1-x634.google.com with SMTP id g26so954813ejb.5; Mon, 20 Jun 2022 09:57:56 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:from :subject:to:cc:content-language; bh=v2NGbGFf0TG4X5idb5HnR6fbdw4j0Xvgcg+nCMZN07c=; b=FtfvSe3z/PYzrtCwZa+t6I/7Ni1DnteDuumL+kkDY7du+egdq66yZI7WE5UR0V6gf6 /4AMCuyKr09c5M4UnNtNElXo3vmevJEn0GDujZ2864Tg6JvFoUkGSPDpkRFb8XirjPgt U8PF/P98roKCaljfDI/MnHN6p8GRwljc7Olz4kBvcRufX00aJgXjIpyKTcDlHqvTu44j AN1nzspLR+y2SDrcpkdJap4X+9m3HUCwNn4ASZTOnqG47MhKPCCfx5RUOGvTNHdRIUSC YfzaDndc+B1gMz988f/T3rpxCfDnlKXksix1wk1SZ6iY0vA+1g7/RsZG8fqOX9Rg5rZa kCeQ== X-Gm-Message-State: AJIora/r+zZOz98wjU0VpcGIXdaQkRWJKc8knAAR6Piq2mPNJR90nxK0 JSsLCIdVlX1mt8+a2wbLDKQnewLU8mo= X-Google-Smtp-Source: AGRyM1sbpEZ27SNRwiLXCcasaQBnmgkDmoQ/TBsmbi76ibShQTGK5OWkaw23cgCA6K9u8Liia5yhqQ== X-Received: by 2002:a17:907:da7:b0:722:dac3:13e0 with SMTP id go39-20020a1709070da700b00722dac313e0mr1556349ejc.337.1655744275175; Mon, 20 Jun 2022 09:57:55 -0700 (PDT) Received: from [10.126.3.254] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id ff10-20020a1709069c0a00b006fec69696a0sm6197972ejc.220.2022.06.20.09.57.53 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 20 Jun 2022 09:57:54 -0700 (PDT) Content-Type: multipart/mixed; boundary="------------cBcsc2vy4qOENGiN4wNMG7ou" Message-ID: <82bd8c6e-760f-a6c8-2e4a-fad412a0ce2c@gmail.com> Date: Mon, 20 Jun 2022 18:57:51 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.9.1 From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: [PATCH 2/5][_Hashtable] New method to check current bucket To: "libstdc++@gcc.gnu.org" Cc: gcc-patches Content-Language: fr X-Spam-Status: No, score=-9.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_BARRACUDACENTRAL, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 20 Jun 2022 16:57:58 -0000 This is a multi-part message in MIME format. --------------cBcsc2vy4qOENGiN4wNMG7ou Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit libstdc++: [_Hashtable] Use next bucket node and equal_to to check if same bucket To find out if we are still in the same bucket we can first check that current node is not the next bucket's before-begin and then that hash code are equals when cached. If not we can also use the equal_to functor in a multi-container context. As a last resort, compute node bucket index. libstdc++-v3/ChangeLog:     * include/bits/hashtable_policy.h (_Hashtable_base<>::_S_hash_code_equals): New.     * include/bits/hashtable.h (_Hashtable<>::_M_is_in_bucket): New, use latter.     (_Hashtable<>::_M_find_before_node): Use latter.     (_Hashtable<>::_M_find_before_node_tr): Likewise. Tested under Linux x86_64. François --------------cBcsc2vy4qOENGiN4wNMG7ou Content-Type: text/x-patch; charset=UTF-8; name="2_hashtable_is_in_bucket.patch" Content-Disposition: attachment; filename="2_hashtable_is_in_bucket.patch" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL2xpYnN0ZGMrKy12My9pbmNsdWRlL2JpdHMvaGFzaHRhYmxlLmggYi9s aWJzdGRjKystdjMvaW5jbHVkZS9iaXRzL2hhc2h0YWJsZS5oCmluZGV4IDgzMThkYTE2OGUz Li5lNTNjYmFmMDY0NCAxMDA2NDQKLS0tIGEvbGlic3RkYysrLXYzL2luY2x1ZGUvYml0cy9o YXNodGFibGUuaAorKysgYi9saWJzdGRjKystdjMvaW5jbHVkZS9iaXRzL2hhc2h0YWJsZS5o CkBAIC04MDEsNiArODAxLDMzIEBAIF9HTElCQ1hYX0JFR0lOX05BTUVTUEFDRV9WRVJTSU9O CiAgICAgICBfX25vZGVfYmFzZV9wdHIKICAgICAgIF9NX2ZpbmRfYmVmb3JlX25vZGUoY29u c3Qga2V5X3R5cGUmKTsKIAorICAgICAgYm9vbAorICAgICAgX01faXNfaW5fYnVja2V0KHNp emVfdHlwZSBfX2JrdCwgX19ub2RlX3B0ciwgX19ub2RlX3B0ciBfX24sCisJCSAgICAgIHRy dWVfdHlwZSAvKiBfX3VrcyAqLykgY29uc3QKKyAgICAgIHsgcmV0dXJuIF9NX2J1Y2tldF9p bmRleCgqX19uKSA9PSBfX2JrdDsgfQorCisgICAgICBib29sCisgICAgICBfTV9pc19pbl9i dWNrZXQoc2l6ZV90eXBlIF9fYmt0LCBfX25vZGVfcHRyIF9fcHJldl9uLCBfX25vZGVfcHRy IF9fbiwKKwkJICAgICAgZmFsc2VfdHlwZSAvKiBfX3VrcyAqLykgY29uc3QKKyAgICAgIHsK KwlyZXR1cm4gdGhpcy0+X01fa2V5X2VxdWFscyhfRXh0cmFjdEtleXt9KF9fcHJldl9uLT5f TV92KCkpLCAqX19uKQorCSAgfHwgX01fYnVja2V0X2luZGV4KCpfX24pID09IF9fYmt0Owor ICAgICAgfQorCisgICAgICBib29sCisgICAgICBfTV9pc19ueHRfaW5fYnVja2V0KHNpemVf dHlwZSBfX2JrdCwgX19ub2RlX3B0ciBfX3ByZXZfbiwKKwkJCSAgX19ub2RlX2Jhc2VfcHRy IF9fbnh0X2JrdF9uKSBjb25zdAorICAgICAgeworCWlmIChfX3ByZXZfbiA9PSBfX254dF9i a3RfbikKKwkgIHJldHVybiBmYWxzZTsKKworCV9fbm9kZV9wdHIgX19uID0gX19wcmV2X24t Pl9NX25leHQoKTsKKwlpZiAodGhpcy0+X1NfaGFzaF9jb2RlX2VxdWFscygqX19wcmV2X24s ICpfX24pKQorCSAgcmV0dXJuIHRydWU7CisKKwlyZXR1cm4gX01faXNfaW5fYnVja2V0KF9f Ymt0LCBfX3ByZXZfbiwgX19uLCBfX3VuaXF1ZV9rZXlze30pOworICAgICAgfQorCiAgICAg ICAvLyBGaW5kIGFuZCBpbnNlcnQgaGVscGVyIGZ1bmN0aW9ucyBhbmQgdHlwZXMKICAgICAg IC8vIEZpbmQgdGhlIG5vZGUgYmVmb3JlIHRoZSBvbmUgbWF0Y2hpbmcgdGhlIGNyaXRlcmlh LgogICAgICAgX19ub2RlX2Jhc2VfcHRyCkBAIC0xOTk5LDEzICsyMDI2LDE1IEBAIF9HTElC Q1hYX0JFR0lOX05BTUVTUEFDRV9WRVJTSU9OCiAgICAgICBpZiAoIV9fcHJldl9wKQogCXJl dHVybiBudWxscHRyOwogCisgICAgICBfX25vZGVfYmFzZV9wdHIgX19ueHRfYmt0X24KKwk9 IF9fYmt0IDwgX01fYnVja2V0X2NvdW50IC0gMSA/IF9NX2J1Y2tldHNbX19ia3QgKyAxXSA6 IG51bGxwdHI7CiAgICAgICBmb3IgKF9fbm9kZV9wdHIgX19wID0gc3RhdGljX2Nhc3Q8X19u b2RlX3B0cj4oX19wcmV2X3AtPl9NX254dCk7OwogCSAgIF9fcCA9IF9fcC0+X01fbmV4dCgp KQogCXsKIAkgIGlmICh0aGlzLT5fTV9lcXVhbHMoX19rLCBfX2NvZGUsICpfX3ApKQogCSAg ICByZXR1cm4gX19wcmV2X3A7CiAKLQkgIGlmICghX19wLT5fTV9ueHQgfHwgX01fYnVja2V0 X2luZGV4KCpfX3AtPl9NX25leHQoKSkgIT0gX19ia3QpCisJICBpZiAoIV9fcC0+X01fbnh0 IHx8ICFfTV9pc19ueHRfaW5fYnVja2V0KF9fYmt0LCBfX3AsIF9fbnh0X2JrdF9uKSkKIAkg ICAgYnJlYWs7CiAJICBfX3ByZXZfcCA9IF9fcDsKIAl9CkBAIC0yMDI5LDEzICsyMDU4LDE1 IEBAIF9HTElCQ1hYX0JFR0lOX05BTUVTUEFDRV9WRVJTSU9OCiAJaWYgKCFfX3ByZXZfcCkK IAkgIHJldHVybiBudWxscHRyOwogCisJX19ub2RlX2Jhc2VfcHRyIF9fbnh0X2JrdF9uCisJ ICA9IF9fYmt0IDwgX01fYnVja2V0X2NvdW50IC0gMSA/IF9NX2J1Y2tldHNbX19ia3QgKyAx XSA6IG51bGxwdHI7CiAJZm9yIChfX25vZGVfcHRyIF9fcCA9IHN0YXRpY19jYXN0PF9fbm9k ZV9wdHI+KF9fcHJldl9wLT5fTV9ueHQpOzsKIAkgICAgIF9fcCA9IF9fcC0+X01fbmV4dCgp KQogCSAgewogCSAgICBpZiAodGhpcy0+X01fZXF1YWxzX3RyKF9faywgX19jb2RlLCAqX19w KSkKIAkgICAgICByZXR1cm4gX19wcmV2X3A7CiAKLQkgICAgaWYgKCFfX3AtPl9NX254dCB8 fCBfTV9idWNrZXRfaW5kZXgoKl9fcC0+X01fbmV4dCgpKSAhPSBfX2JrdCkKKwkgICAgaWYg KCFfX3AtPl9NX254dCB8fCAhX01faXNfbnh0X2luX2J1Y2tldChfX2JrdCwgX19wLCBfX254 dF9ia3RfbikpCiAJICAgICAgYnJlYWs7CiAJICAgIF9fcHJldl9wID0gX19wOwogCSAgfQpk aWZmIC0tZ2l0IGEvbGlic3RkYysrLXYzL2luY2x1ZGUvYml0cy9oYXNodGFibGVfcG9saWN5 LmggYi9saWJzdGRjKystdjMvaW5jbHVkZS9iaXRzL2hhc2h0YWJsZV9wb2xpY3kuaAppbmRl eCA4M2E5ZmYyYmIzZC4uZTg0OGJhMWQzZjcgMTAwNjQ0Ci0tLSBhL2xpYnN0ZGMrKy12My9p bmNsdWRlL2JpdHMvaGFzaHRhYmxlX3BvbGljeS5oCisrKyBiL2xpYnN0ZGMrKy12My9pbmNs dWRlL2JpdHMvaGFzaHRhYmxlX3BvbGljeS5oCkBAIC0xNzIxLDYgKzE3MjEsMTYgQEAgbmFt ZXNwYWNlIF9fZGV0YWlsCiAgICAgICA6IF9faGFzaF9jb2RlX2Jhc2UoX19oYXNoKSwgX0Vx dWFsRUJPKF9fZXEpCiAgICAgICB7IH0KIAorICAgICAgc3RhdGljIGJvb2wKKyAgICAgIF9T X2hhc2hfY29kZV9lcXVhbHMoY29uc3QgX0hhc2hfbm9kZV9jb2RlX2NhY2hlPGZhbHNlPiYs CisJCQkgIGNvbnN0IF9IYXNoX25vZGVfY29kZV9jYWNoZTxmYWxzZT4mKQorICAgICAgeyBy ZXR1cm4gZmFsc2U7IH0KKworICAgICAgc3RhdGljIGJvb2wKKyAgICAgIF9TX2hhc2hfY29k ZV9lcXVhbHMoY29uc3QgX0hhc2hfbm9kZV9jb2RlX2NhY2hlPHRydWU+JiBfX2xobiwKKwkJ CSAgY29uc3QgX0hhc2hfbm9kZV9jb2RlX2NhY2hlPHRydWU+JiBfX3JobikKKyAgICAgIHsg cmV0dXJuIF9fbGhuLl9NX2hhc2hfY29kZSA9PSBfX3Jobi5fTV9oYXNoX2NvZGU7IH0KKwog ICAgICAgYm9vbAogICAgICAgX01fa2V5X2VxdWFscyhjb25zdCBfS2V5JiBfX2ssCiAJCSAg ICBjb25zdCBfSGFzaF9ub2RlX3ZhbHVlPF9WYWx1ZSwK --------------cBcsc2vy4qOENGiN4wNMG7ou--