From patchwork Wed Aug 2 09:55:25 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrzej Turko X-Patchwork-Id: 129735 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:9f41:0:b0:3e4:2afc:c1 with SMTP id v1csp341050vqx; Wed, 2 Aug 2023 03:02:35 -0700 (PDT) X-Google-Smtp-Source: APBJJlHPl7Xqh6Hcj0q8Fkf8MJlTcEF5TFkC6UpTcalz5MjObv9xuQ/jxybjEtV36DoYMmOZ/eKD X-Received: by 2002:aa7:c795:0:b0:522:2c44:a915 with SMTP id n21-20020aa7c795000000b005222c44a915mr4830940eds.24.1690970555009; Wed, 02 Aug 2023 03:02:35 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1690970554; cv=none; d=google.com; s=arc-20160816; b=pxAbDFj2ktWR8IWSX1Uahb7G5WbBZTBJWaaEQsfeSvIhuvQT9OfrFCkdAZjtrxHh4j XeSndOI4kVuWyO7Q8JiURAFi/TFU3rjymk9PUPgjQmjHDz5srNWyH0aLFiLXbHMk8RCZ REtO/ILfBxVhY4CFTxvLcmhYqOELOgpCgJsF7NG3IC8kJSTJdk0CEyccqTyWzaTDmSAC x8Y+Sn0AYb2dPvoF4m4v6vGVXhp6NcWprcPAeuEBVtDbglqGRHHKZ1CzYlzBGRvlRmmj QU6hg5jL2RSMZ9Wqx7PKrCof2UwKpydpRadWMZdNP8PbdQMZnVACvwA2QZak9QGCfN6H hUKw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=jx50U3YNwZqJZ5RNjN+doWjBr6mTI5xkGFSIOlXQQ00=; fh=k/nQU4IX+jAQueq710KA8dCAcoPPe4cl6LpGj9WeH7w=; b=PTDTfOY7aojpzo0IO+Q0qp7c8gudrcNYd/nNs9bCuy4e0vCYD/QIKrhFJKHyrGQqgD 8/ztslEVmJsHEGcagtQKHDXy9f3ICE2nck41GcMk4wkB8gjGF8Ug/EZOrAsWs0lDMN0L 2Jq9dTJX1HNpss+G89lX3RnlfJS2a2Q8PzudgB0EshFZfuDTgkn6oo2b7weApDRZd9hi qNi/cvdRVTMKlptIKo7J61+KF16FtguCJ9MAmjodZUsSj/gExzXpzLxurHlXfjHvSj6z hZeGRRyMX5bn3qmi+uKclEVTSgEkKLTTKh5tVJnRqNqoRRdPvaaXs6SplE/0VU6wpt/j 50Dw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=ZBxNd0a8; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id j14-20020aa7c0ce000000b00521ab8e67dbsi9662689edp.226.2023.08.02.03.02.34 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 02 Aug 2023 03:02:34 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=ZBxNd0a8; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id F0FFB3857C41 for ; Wed, 2 Aug 2023 10:01:32 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org F0FFB3857C41 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1690970493; 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=ZBxNd0a8lUzG8s7Wl7KC4ZjuTbjS2Si1nrYatavUr0WfNOq1qcG5SjulWvkucgCBd wGVuN4XOg+HQ0c7kUPY25Qd8LIiqbg+ZPt0lz5sNTKTT7oIkx44NzeqDPnii0T1bbm iKu5JxtLpXq2CA/ZTobtLSWuHNnLXWSVIPcR/7l0= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wr1-x435.google.com (mail-wr1-x435.google.com [IPv6:2a00:1450:4864:20::435]) by sourceware.org (Postfix) with ESMTPS id B703C3858D37 for ; Wed, 2 Aug 2023 10:00:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org B703C3858D37 Received: by mail-wr1-x435.google.com with SMTP id ffacd0b85a97d-31759e6a4a1so5890985f8f.3 for ; Wed, 02 Aug 2023 03:00:47 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690970446; x=1691575246; 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=NUwiMkkK1NRfuDKL4It2d3Onw1LeNPv9y97rnYttqgjffMHhnWrS4EIn+9DcTlU8Hr ao/vXGTLqk6lI8IG/Zud26SqfIKo6ReeK+ubHClKhQ0weDGbaNzTkwTgkdv7DJvd18Nf cFcbXP69B0Ev+0E847EHD+RzHKYmGi0/+nct2Mz0Cok30l15rWnF4fp7Eu1C3o+yKosd UqcoeircnozC9HnmVr96zpVwBxIrP1tlzk1SBTE4NjxZLNTp2tfWc6drDTVjDJDYZvVh K/HnQVCr2NBeY/ncWTjbvJTKLuR61m3eszAu8g/uWBLH2h6yqs+2G6dmAEkJ+K8JSEyi mcpA== X-Gm-Message-State: ABy/qLbQhxGFx7Qq1EmV+CfwUONxuHXk/hdqYMULU9GgoGcTrsaBd9mb XDK4vgeR3SqkvgyQvcaTi07v4gg7CYk0nOri X-Received: by 2002:a05:6000:1205:b0:313:e953:65cf with SMTP id e5-20020a056000120500b00313e95365cfmr4343937wrx.17.1690970446093; Wed, 02 Aug 2023 03:00:46 -0700 (PDT) Received: from amwld-aturko1.us.drwholdings.com ([149.14.21.6]) by smtp.gmail.com with ESMTPSA id s1-20020a5d4ec1000000b003063db8f45bsm18544560wrv.23.2023.08.02.03.00.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 02 Aug 2023 03:00:45 -0700 (PDT) To: gcc-patches@gcc.gnu.org Cc: Andrzej Turko Subject: [PATCH 1/3 v2] Support get_or_insert in ordered_hash_map Date: Wed, 2 Aug 2023 11:55:25 +0200 Message-Id: <20230802095527.100830-2-andrzej.turko@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230802095527.100830-1-andrzej.turko@gmail.com> References: <20230802095527.100830-1-andrzej.turko@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.7 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, 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: 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1773111141021916026 X-GMAIL-MSGID: 1773111141021916026 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. */