From patchwork Mon Aug 7 09:58:59 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrzej Turko X-Patchwork-Id: 1817736 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=tkgImahg; dkim-atps=neutral Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4RKBkY0Wxzz1ybZ for ; Mon, 7 Aug 2023 20:04:36 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A6A443857700 for ; Mon, 7 Aug 2023 10:04:34 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A6A443857700 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1691402674; bh=jx50U3YNwZqJZ5RNjN+doWjBr6mTI5xkGFSIOlXQQ00=; h=To:Cc:Subject:Date:In-Reply-To:References:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=tkgImahgz7y22b/MkFqbqCw7MxG2XjObDRhrjrbZY+aHE3XpUpnSr/THJTxYXiFs2 b7sZKaOBpA8of/HSUWRjlrTicMkU2BZMzT0VTC5CCmbh7wPZGq1lwHfcpUAGV2rZDl StyCfGT8QH7ChiGPF6exlG4NboqY+8aeDJf72PS0= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-lj1-x22c.google.com (mail-lj1-x22c.google.com [IPv6:2a00:1450:4864:20::22c]) by sourceware.org (Postfix) with ESMTPS id AD2103858C39 for ; Mon, 7 Aug 2023 10:04:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org AD2103858C39 Received: by mail-lj1-x22c.google.com with SMTP id 38308e7fff4ca-2b9db1de50cso65429011fa.3 for ; Mon, 07 Aug 2023 03:04:05 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1691402644; x=1692007444; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=jx50U3YNwZqJZ5RNjN+doWjBr6mTI5xkGFSIOlXQQ00=; b=Q4H5s6iu9Y1rfk0yeEvR8DZFgxSVNPDqi8wy3Bxi7QdE4k0F5x2NigjqdMeDiZA4Nc XynnszZf8X5E4Yxuj3e6SWAuTsckuAWfNuFSBp2yDSyKGpshhz7Zl21xQMZ2QfW5S+wG 3zKIqXHdz7MHNL3lxgM65EYMRDanGTZf3yx4Vm8YcrWobF9zFmdqX/DgiQTKfM2291Q1 hk6UUZs9ZPc2FfAHrxUvo1T859f4qujVkwP2hZ4sJpHD3etNUtgksWKvOmIMhtauM1uu q4gMamWC7/eQ989TCOzzjYf8NjuVHmNVKdpqq+xM2e5cAt6FjQWC41rJmWBJXNUGJyIU Mecw== X-Gm-Message-State: AOJu0YzO8uEEfioXcBV4XCCcnBnqB/5mR+CzEd4BEuY8JYT/BXFiJGdZ mXI8Aip67CGd3XefQO9VOHH2B07j0/FNU/IfoPg= X-Google-Smtp-Source: AGHT+IGgcAZQhtPFo2Gbq+KCAKu6fpG7kAIPOEzfuiw0xN0dD06LLEewLbV1Z4I4gfys31AWEj800Q== X-Received: by 2002:a2e:88d6:0:b0:2b4:75f0:b9e9 with SMTP id a22-20020a2e88d6000000b002b475f0b9e9mr5792503ljk.10.1691402643502; Mon, 07 Aug 2023 03:04:03 -0700 (PDT) Received: from amwld-aturko1.us.drwholdings.com ([149.14.21.6]) by smtp.gmail.com with ESMTPSA id la4-20020a170906ad8400b0099bd682f317sm4881305ejb.206.2023.08.07.03.04.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Aug 2023 03:04:03 -0700 (PDT) To: gcc-patches@gcc.gnu.org, Richard Biener Cc: Andrzej Turko Subject: [PATCH 1/3 v4] Support get_or_insert in ordered_hash_map Date: Mon, 7 Aug 2023 11:58:59 +0200 Message-Id: <20230807095901.267099-2-andrzej.turko@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230807095901.267099-1-andrzej.turko@gmail.com> References: <20230807095901.267099-1-andrzej.turko@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, 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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Andrzej Turko via Gcc-patches From: Andrzej Turko Reply-To: Andrzej Turko Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Get_or_insert method is already supported by the unordered hash map. Adding it to the ordered map enables us to replace the unordered map with the ordered one in cases where ordering may be useful. Signed-off-by: Andrzej Turko gcc/ChangeLog: * ordered-hash-map.h: Add get_or_insert. * ordered-hash-map-tests.cc: Use get_or_insert in tests. --- gcc/ordered-hash-map-tests.cc | 19 +++++++++++++++---- gcc/ordered-hash-map.h | 26 ++++++++++++++++++++++++++ 2 files changed, 41 insertions(+), 4 deletions(-) diff --git a/gcc/ordered-hash-map-tests.cc b/gcc/ordered-hash-map-tests.cc index 1c26bbfa979..55894c25fa0 100644 --- a/gcc/ordered-hash-map-tests.cc +++ b/gcc/ordered-hash-map-tests.cc @@ -58,6 +58,7 @@ static void test_map_of_strings_to_int () { ordered_hash_map m; + bool existed; const char *ostrich = "ostrich"; const char *elephant = "elephant"; @@ -74,17 +75,23 @@ test_map_of_strings_to_int () ASSERT_EQ (false, m.put (ostrich, 2)); ASSERT_EQ (false, m.put (elephant, 4)); ASSERT_EQ (false, m.put (ant, 6)); - ASSERT_EQ (false, m.put (spider, 8)); + existed = true; + int &value = m.get_or_insert (spider, &existed); + value = 8; + ASSERT_EQ (false, existed); ASSERT_EQ (false, m.put (millipede, 750)); ASSERT_EQ (false, m.put (eric, 3)); + /* Verify that we can recover the stored values. */ ASSERT_EQ (6, m.elements ()); ASSERT_EQ (2, *m.get (ostrich)); ASSERT_EQ (4, *m.get (elephant)); ASSERT_EQ (6, *m.get (ant)); ASSERT_EQ (8, *m.get (spider)); - ASSERT_EQ (750, *m.get (millipede)); + existed = false; + ASSERT_EQ (750, m.get_or_insert (millipede, &existed)); + ASSERT_EQ (true, existed); ASSERT_EQ (3, *m.get (eric)); /* Verify that the order of insertion is preserved. */ @@ -113,6 +120,7 @@ test_map_of_int_to_strings () { const int EMPTY = -1; const int DELETED = -2; + bool existed; typedef int_hash int_hash_t; ordered_hash_map m; @@ -131,7 +139,9 @@ test_map_of_int_to_strings () ASSERT_EQ (false, m.put (2, ostrich)); ASSERT_EQ (false, m.put (4, elephant)); ASSERT_EQ (false, m.put (6, ant)); - ASSERT_EQ (false, m.put (8, spider)); + const char* &value = m.get_or_insert (8, &existed); + value = spider; + ASSERT_EQ (false, existed); ASSERT_EQ (false, m.put (750, millipede)); ASSERT_EQ (false, m.put (3, eric)); @@ -141,7 +151,8 @@ test_map_of_int_to_strings () ASSERT_EQ (*m.get (4), elephant); ASSERT_EQ (*m.get (6), ant); ASSERT_EQ (*m.get (8), spider); - ASSERT_EQ (*m.get (750), millipede); + ASSERT_EQ (m.get_or_insert (750, &existed), millipede); + ASSERT_EQ (existed, TRUE); ASSERT_EQ (*m.get (3), eric); /* Verify that the order of insertion is preserved. */ diff --git a/gcc/ordered-hash-map.h b/gcc/ordered-hash-map.h index 6b68cc96305..9fc875182e1 100644 --- a/gcc/ordered-hash-map.h +++ b/gcc/ordered-hash-map.h @@ -76,6 +76,32 @@ public: return m_map.get (k); } + /* Return a reference to the value for the passed in key, creating the entry + if it doesn't already exist. If existed is not NULL then it is set to + false if the key was not previously in the map, and true otherwise. */ + + Value &get_or_insert (const Key &k, bool *existed = NULL) + { + bool _existed; + Value &ret = m_map.get_or_insert (k, &_existed); + + if (!_existed) + { + bool key_present; + int &slot = m_key_index.get_or_insert (k, &key_present); + if (!key_present) + { + slot = m_keys.length (); + m_keys.safe_push (k); + } + } + + if (existed) + *existed = _existed; + + return ret; + } + /* Removing a key removes it from the map, but retains the insertion order. */