From patchwork Thu Aug 3 14:21:29 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrzej Turko X-Patchwork-Id: 130661 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:9f41:0:b0:3e4:2afc:c1 with SMTP id v1csp1184986vqx; Thu, 3 Aug 2023 07:24:55 -0700 (PDT) X-Google-Smtp-Source: APBJJlHnwm2TM5zphWD5eg7M6WiKJ64NvtsCi+9hyDl9mY+7MMbvcQnFYW9I9gBoJGV9D4pR4ZKX X-Received: by 2002:a17:907:77cf:b0:982:26c5:6525 with SMTP id kz15-20020a17090777cf00b0098226c56525mr7777645ejc.60.1691072694934; Thu, 03 Aug 2023 07:24:54 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1691072694; cv=none; d=google.com; s=arc-20160816; b=bTSfMIRKXRR5kZ6U/ClvEbTTKDBV/PfqaK3kGcyAnVWyeQHBCtnuTOuS/i6lKfcHoP /llCaNWdYocXGtyJ6/nXjCbZ1TOVAV4TPFTyS5KlcCxkjzIHa1t80mKBt2HYymnSUekJ bhNwq8gmwJUMYt4O7xSlf1tR7/PJyxxwwiN/bnyzKqRrFaKRJiKk6+jiQUhr6LISG6DW xuOZTfWuA3HpjoA3pVOK/Ra+EHW889bN4WskPnB7mtEVtR54BjXvK8XPLS2XASpDFrHh PislZ1EE+5Y3O3WRlVPDD3CQfrZFuyc2oN6+eXMwSu3b1sPcFgLmGIcsbbr876vv3LKm bg0w== 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=iK0cXAX0WIKgeX1/eUGGaXIoaF0/R0ECoYm9M+roBheXNRDS5pBLzDgJwrbk0YjbGq MeCq/IUY/P1tj40LYp4BT2+pqmnQmEtl0ZQ+vV39yLx/KWGpOAJcAfpnjRSWCfdlZBX9 Dz4dFwgPBJD4eAcGVn+OWGEyd+B+sJHovG/3CVyVEzLK5uEffJiNUhgOGayCOke3SLR0 WlXJkxzlI4FXL7PrE0V6bzoK96vtpXajjZOv+ZqnA0fNIL4GNWCAa26KoF5xzdcWE/n9 r3GQcW7eYfD59gVTTECf4stpcQDRkIOTZ46kYb1jevhF6fmkD32owBEvFCYjM1Yp4Fxq txeA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=PzVbaYsr; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id dv22-20020a170906b81600b00992bd86ece6si11905118ejb.725.2023.08.03.07.24.54 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 03 Aug 2023 07:24:54 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=PzVbaYsr; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 F310B38555B9 for ; Thu, 3 Aug 2023 14:23:52 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org F310B38555B9 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1691072633; 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=PzVbaYsrVth40ZpOlZ6nuGPnm1mSCv+DExR/BO8DGbpZnS5TSSuRKm+fY/Nu/evpd MQTTloSX3F3YuH2scC/Y7tnVEyu5YIWVGa8lyM4pHMQS9iN1gwBCYxXSYkcCRLA10s r0oTFdCfv8sP65tpTqwXaw96IGikCmNB8FDDPra8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x334.google.com (mail-wm1-x334.google.com [IPv6:2a00:1450:4864:20::334]) by sourceware.org (Postfix) with ESMTPS id 7A4223858D35 for ; Thu, 3 Aug 2023 14:23:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 7A4223858D35 Received: by mail-wm1-x334.google.com with SMTP id 5b1f17b1804b1-3fbea14706eso10251675e9.2 for ; Thu, 03 Aug 2023 07:23:03 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1691072582; x=1691677382; 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=PpGI1tRcqg3RuDXvgTVqtF3l7/ePuUT4LF+AUksgEA4xnspSx34hbcRY2ch4rz+hPv mTvOu4t7ZBF2pZIm3Y0KkpgVKR+FQUMo5Wb1978aHCzQfPS3UQavV4P8Od5Nzph1ddFJ FfEbXjetlpIgBJ8UJ0kR8oC8FljMNKuhnhU4vGAjguk7+E5ykahqs5w/QjcbdqpAwzDG fd+Qy6B5xl/1eIib+ok+tlYC0A4CbwnGY/xMCM3EWx9p5LNIKVkES2UHgmRR60fLXpOw AqYRfP2PxlDN3Hil1P1eihHdLclCTkZm5mCBwVmwXwvpRxwBGhh8xRPT3AR2/UJzIYna TUvA== X-Gm-Message-State: ABy/qLaTOfD2YmSTrG8zv8eFhQ6CPBhPnGQjk3V+xYqOF0jl4DsMQBwU lEhhfgDQc+WkUeWvbwo0fmijsQ/5zApUNZV8 X-Received: by 2002:a05:600c:3644:b0:3fb:b1af:a455 with SMTP id y4-20020a05600c364400b003fbb1afa455mr7023923wmq.5.1691072581686; Thu, 03 Aug 2023 07:23:01 -0700 (PDT) Received: from amwld-aturko1.us.drwholdings.com ([149.14.21.6]) by smtp.gmail.com with ESMTPSA id f9-20020a7bc8c9000000b003fba92fad35sm4371349wml.26.2023.08.03.07.23.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 03 Aug 2023 07:23:01 -0700 (PDT) To: gcc-patches@gcc.gnu.org Cc: Andrzej Turko Subject: [PATCH 1/3 v3] Support get_or_insert in ordered_hash_map Date: Thu, 3 Aug 2023 16:21:29 +0200 Message-Id: <20230803142131.250087-2-andrzej.turko@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230803142131.250087-1-andrzej.turko@gmail.com> References: <20230803142131.250087-1-andrzej.turko@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-11.6 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: 1773218242538924711 X-GMAIL-MSGID: 1773218242538924711 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. */