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: 131778 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:c44e:0:b0:3f2:4152:657d with SMTP id w14csp1341985vqr; Mon, 7 Aug 2023 03:05:26 -0700 (PDT) X-Google-Smtp-Source: AGHT+IGGbvsXv7yr8+Mpi/zNPqeBNMLQMUUSfnjQNpZS0atVbqQl4aSAssh08XDBsr28TG1aCwRo X-Received: by 2002:a17:906:519c:b0:99c:a23b:b4f4 with SMTP id y28-20020a170906519c00b0099ca23bb4f4mr8507492ejk.2.1691402726195; Mon, 07 Aug 2023 03:05:26 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1691402726; cv=none; d=google.com; s=arc-20160816; b=W0speoOACxV3C9RLjFK6NN5Pq1nIjCpaiVVs/kJrRvUJcjd7Dh4Xc7Ugp3feneB86j UT4gTh2G/nwZj7tiaGLi3ptOZ78uA4SGVQogYmGMnAHMGLr6v6eg/eDeOHVZ1BVTliRo vaOFONDucVJJ39UCRXM124Iqa1XGo2yyNxVxipuawYcH3Cz4QKmx1drFmmbIhQLRQwVA 10YEpYSxGLlF26cm4TeWDw1XyOQgcpQaKq+wDkc8wC6t9vcxk4upn02LhQhNSNZnpZYl Is3yNUQWgX15+Rx2nvHxZMOX37sW2tlfAlmBkuJgL5Khn/BCr9FC6I4e1XTOUfGkTCnJ zaZw== 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=Yo2ByyRkNEaDu9X7hI9WCxKxqBIoNDutgIrFEk/DvWs=; b=ksE5xPKGwAoKTSRc0lYr8YZ2CaxWWOH6IEDiFWpbvRMkFuxV3BmDURY+x1gLkifoTY j3YqJS6Vn6UJPZV4Hihp9Q/s00L+Cz/Prz5yQgf3Z/qiDCgIWrv3GsUfxv5UgzFJTW3A tqY9/IqQaKONj7Cb5bK5AYmsTqChvUgba0D4Z12XvQ/zs/IT1drUfXUu+L/LPBNzdJwF C16ZyKyorGLf7CJURef4ajk9vHyhLnFgoqaACx1MUuWwyxsN9oXQxBlDMFSuApAo28mf ZTvQuXJVeUbdY+FLLNPfH1o4wRteJj8k34yWP6WPdRDHD7anf97fVpZDZtlTw/Xkw64r O0Bw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=Hz9Hfdp3; 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 o24-20020a1709064f9800b009930ef7f05dsi5021151eju.908.2023.08.07.03.05.25 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Aug 2023 03:05:26 -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=Hz9Hfdp3; 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 BB6E43855583 for ; Mon, 7 Aug 2023 10:04:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BB6E43855583 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1691402699; 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=Hz9Hfdp3NZDSmYRx8OPDxTWuAsHprDLKYKbNoqk6vTPpA10tebzpsBWFnc5TGpMwP a2FKBGzv89XFGmHnI+Jr6d/xPfaGI11zIylrJTkmy+0erySwCDtClWm/jyq8B3IgT+ zjuVwCfW1kWCL9w8P+BKjpmBMe+aCMb5jW4OsNNc= 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-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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1773564304882215908 X-GMAIL-MSGID: 1773564304882215908 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. */