From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x62d.google.com (mail-ej1-x62d.google.com [IPv6:2a00:1450:4864:20::62d]) by sourceware.org (Postfix) with ESMTPS id C6D783858D20 for ; Thu, 29 Dec 2022 07:29:30 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C6D783858D20 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-ej1-x62d.google.com with SMTP id gh17so43286742ejb.6 for ; Wed, 28 Dec 2022 23:29:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:in-reply-to:cc:references:message-id:date:subject:mime-version :from:content-transfer-encoding:from:to:cc:subject:date:message-id :reply-to; bh=Kpi/ClMz2KlUupsyrm1Jygk2jtxKBv92TsEdFQK7i6I=; b=O5aYfJyAage5ZKKAnxpS66z3mH8FQcNyuL5/nIJmlJo8BjTDDT65hslO0DGsAjjO/H JYhaCipysds+Iv5W/uZxid0BRtuGpphIAf1QYPUXuj24XbKkjCC8m90mXLA+Eg70xyEd ufKMyReI4P9dU/WVwFet+9kPgONNryS8qFL2fv/PW4wTPnwKaI+pGoRYbZ3eXzhkU6BQ Kg2iV/w7s31eLVInrkPlaPB+iBPH14Z7esJAN65U6sOddC77aH04KVBtlO0zr/F0JPET m0QOBR/7I/XACRUHgZ0QDNuL8bEwxmpVNb8CYXvu9B+J+qGTAQA/ntoLJtSjNK3OhuWP IMvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:in-reply-to:cc:references:message-id:date:subject:mime-version :from:content-transfer-encoding:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Kpi/ClMz2KlUupsyrm1Jygk2jtxKBv92TsEdFQK7i6I=; b=cXO+d4dygolPIDKFXake/LDb7GGXzL+9+UgzetODQloEZ+d3nGkfu1XOLNGwsX3FqM Fm11clUNDPZ/yR/XyIfOC4utZs568ly02r+AtGBMzt/tzOoHsjfCVlqJrgVnrg1Ow6B5 PXkxAVIqO5j31pSjLvhcG4LkMxTmAt6DF0T9QRqnH12DBlPz601w3knDYI7CK2J57J79 Sx3ExigvfOjb5nbK6LMpYmPxDM+HGIfqmyCBQoANr5yx9ekkBkaOm9uU2OuRAgBbOQ2+ pTqNn/RCInSsKQMMsVTPy+C5tFbsjdLafr3Atx/J2eInx0EiEDwVdoUOHxA0SMjDDhPR UbjA== X-Gm-Message-State: AFqh2kqVxM3l9B93yXDJ0nLlE50nz10esUQVIA/Thwv+ctr/HzjuydFP ZibGFm8J1iA6QccsN08vCVeJo+cGlKI= X-Google-Smtp-Source: AMrXdXtJ2tRepxAi08IqjllGCAn7Cq+OeIojHNK6zcSRt37Leaz1nZX+9uZ0vc1bNBoNid4RjNhZbg== X-Received: by 2002:a17:906:a2d6:b0:7c0:bf7c:19f4 with SMTP id by22-20020a170906a2d600b007c0bf7c19f4mr22431669ejb.74.1672298968677; Wed, 28 Dec 2022 23:29:28 -0800 (PST) Received: from smtpclient.apple (dynamic-077-004-048-215.77.4.pool.telefonica.de. [77.4.48.215]) by smtp.gmail.com with ESMTPSA id s18-20020a170906bc5200b007c0b4387d2asm8249288ejv.8.2022.12.28.23.29.27 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 28 Dec 2022 23:29:27 -0800 (PST) Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable From: Richard Biener Mime-Version: 1.0 (1.0) Subject: Re: [17/17] check hash table insertions Date: Thu, 29 Dec 2022 08:29:17 +0100 Message-Id: References: Cc: gcc-patches@gcc.gnu.org In-Reply-To: To: Alexandre Oliva X-Mailer: iPhone Mail (20C65) X-Spam-Status: No, score=-3.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,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: > Am 29.12.2022 um 00:06 schrieb Alexandre Oliva : >=20 > =EF=BB=BFOn Dec 28, 2022, Richard Biener wrot= e: >=20 >> I wonder if on INSERT, pushing a DELETED marker would fix the dangling >> insert and search during delete problem be whether that would be >> better from a design point of view? (It of course requires a DELETED >> representation) >=20 > I'm undecided whether a design that rules out the possibility of not > having DELETED would qualify as unequivocally better. >=20 > Unless DELETED takes over the NULL representation, and something else is > used for EMPTY, every INSERT point would have to be adjusted to look for > the non-NULL DELETED representation. Not sure what you mean - I think turning EMPTY (or DELETED) into DELETED at i= nsert time would make the slot occupied for lookups and thus fix lookup duri= ng insert. Of course insert during insert would still fail and possibly ret= urn the same slot again. So the most foolproof design would be a new INSERT= ING representation. > That alone was enough for me to > rule out going down that path. >=20 > If we were to change the INSERT callers, it would make sense to > e.g. return a smart pointer that enforced the completion of the > insertion. But that wouldn't fix lookups during insertion without > requiring a separate DELETED representation. >=20 > The one-pending-insertion strategy I implemented was the only one I > could find that addressed all of the pitfalls without significant > overhead. It caught even one case that the mere element-counting had > failed to catch. Yes, it=E2=80=99s true that this addresses all issues with just imposing con= straints on API use. But the I wondered how you catched the completion of t= he insertion? (I=E2=80=99ll have to Dig into the patch to see) Richard=20 >=20 > --=20 > Alexandre Oliva, happy hacker https://FSFLA.org/blogs/lxo/ > Free Software Activist GNU Toolchain Engineer > Disinformation flourishes because many people care deeply about injustice > but very few check the facts. Ask me about