From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x134.google.com (mail-lf1-x134.google.com [IPv6:2a00:1450:4864:20::134]) by sourceware.org (Postfix) with ESMTPS id DAD643858000 for ; Mon, 31 Jul 2023 13:39:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org DAD643858000 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-lf1-x134.google.com with SMTP id 2adb3069b0e04-4fe0fe622c3so6900857e87.2 for ; Mon, 31 Jul 2023 06:39:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1690810775; x=1691415575; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=NBZIi4z6gTktag8mFVzMOXO9T+LgHvV3HDYclYG0CM0=; b=GgENEY4tgnOf4FfxOcb+2zQ2DRRppe2dx3SdBdJN1Ip10zLiOO0OxQS3f1Pe/sVzpp NCrkhnwbFMdUOvOenljBk3qNjLIdGzfoWDmMWnqCCiG0pNx4j3xhQf0fy0FZj4+1HEhy I0b2FCUUZeXOnKRpB/6JmkyE2xoE99dSXC9dW8Xc7hb/KPURLLc9FasCA3/2vHoUprZp bWm4F2Ap0uBF/I3C8v8KWAE7zL6t114wJaQNTE81KSPpFIQITdOPQQZVo+p76ebdYm/R prCv6Jq2chuPCB9z5oAABXf7REEUX7uW8MK1L2v5NwbWC2jIArfYWNYpjom0aBZrnzzJ fgCw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690810775; x=1691415575; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=NBZIi4z6gTktag8mFVzMOXO9T+LgHvV3HDYclYG0CM0=; b=ESQSZr0nMkzY5jAGaP/3q3bZOr9AVzqa3nh0XY+lM81d6SIhOnGLtodxBor9Dt0s9H 8BvWK9QpGd8yebiQxlzYXG+xZ3Z+Rza0JJCFOcdtC3xJrYkkbkOgxTdOTYZoBFHn4vQk KusJXWiqh6a6vZPJ5K/PYVC3O25bRFwW5xDIhtyEsO2Ama82GQ4sZVqo2NYjpr54iTSo tkKIdXLOTDRzE1HErC54Uh2npDrPmBIDK3J5lKS+B9j2jnw6o6A4gFvdmS0o3xki5OYf VI4FhjxojCkWJLFqgCVSDjKKZmuyLxKKvLpeqijHoOjejRwd4W1Z1zevrv3063ppt7mX Hx+w== X-Gm-Message-State: ABy/qLZr9l9OFYXsZl0T3XGrmzqorUdI/+cLeU2JTvPLAaMvaDQZgQYA l0wbDUdLuc8hV0I+13DSY8zhsQuogZtxJDdkQK5q3++W X-Google-Smtp-Source: APBJJlFH8wrKM00La+yVpZdS07rsJAnumF2L41zP9hfpyzDkD0B1rqWe8Rfe4XFcPvgMRHuIvg+BxLTaGpG3Z6pnMsw= X-Received: by 2002:a2e:a40c:0:b0:2b9:afd1:b77a with SMTP id p12-20020a2ea40c000000b002b9afd1b77amr17177ljn.0.1690810774589; Mon, 31 Jul 2023 06:39:34 -0700 (PDT) MIME-Version: 1.0 References: <20230731110346.174848-1-andrzej.turko@gmail.com> <20230731110346.174848-2-andrzej.turko@gmail.com> In-Reply-To: <20230731110346.174848-2-andrzej.turko@gmail.com> From: Richard Biener Date: Mon, 31 Jul 2023 15:38:41 +0200 Message-ID: Subject: Re: [PATCH 1/3] Support get_or_insert in ordered_hash_map To: Andrzej Turko Cc: gcc-patches@gcc.gnu.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.2 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 List-Id: On Mon, Jul 31, 2023 at 1:06=E2=80=AFPM Andrzej Turko via Gcc-patches wrote: > > 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. OK. Note the Makefile.in change really belongs to another patch in the series, without this it could be pushed independently. Thanks, Richard. > Signed-off-by: Andrzej Turko > > gcc/ChangeLog: > > * ordered-hash-map.h: Add get_or_insert. > * Makefile.in: Require the ordered map header for genmatch.o. > * ordered-hash-map-tests.cc: Use get_or_insert in tests. > > Signed-off-by: Andrzej Turko > --- > gcc/Makefile.in | 4 ++-- > gcc/ordered-hash-map-tests.cc | 19 +++++++++++++++---- > gcc/ordered-hash-map.h | 26 ++++++++++++++++++++++++++ > 3 files changed, 43 insertions(+), 6 deletions(-) > > diff --git a/gcc/Makefile.in b/gcc/Makefile.in > index e99628cec07..2429128cbf2 100644 > --- a/gcc/Makefile.in > +++ b/gcc/Makefile.in > @@ -3004,8 +3004,8 @@ build/genhooks.o : genhooks.cc $(TARGET_DEF) $(C_TA= RGET_DEF) \ > $(COMMON_TARGET_DEF) $(D_TARGET_DEF) $(BCONFIG_H) $(SYSTEM_H) errors.h > build/genmddump.o : genmddump.cc $(RTL_BASE_H) $(BCONFIG_H) $(SYSTEM_H) = \ > $(CORETYPES_H) $(GTM_H) errors.h $(READ_MD_H) $(GENSUPPORT_H) > -build/genmatch.o : genmatch.cc $(BCONFIG_H) $(SYSTEM_H) \ > - $(CORETYPES_H) errors.h $(HASH_TABLE_H) hash-map.h $(GGC_H) is-a.h \ > +build/genmatch.o : genmatch.cc $(BCONFIG_H) $(SYSTEM_H) $(CORETYPES_H) \ > + errors.h $(HASH_TABLE_H) hash-map.h $(GGC_H) is-a.h ordered-hash-map.h= \ > tree.def builtins.def internal-fn.def case-cfn-macros.h $(CPPLIB_H) > build/gencfn-macros.o : gencfn-macros.cc $(BCONFIG_H) $(SYSTEM_H) \ > $(CORETYPES_H) errors.h $(HASH_TABLE_H) hash-set.h builtins.def \ > diff --git a/gcc/ordered-hash-map-tests.cc b/gcc/ordered-hash-map-tests.c= c > 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 =3D "ostrich"; > const char *elephant =3D "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 =3D true; > + int &value =3D m.get_or_insert (spider, &existed); > + value =3D 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 =3D 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 =3D -1; > const int DELETED =3D -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 =3D m.get_or_insert (8, &existed); > + value =3D 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 =3D NULL) > + { > + bool _existed; > + Value &ret =3D m_map.get_or_insert (k, &_existed); > + > + if (!_existed) > + { > + bool key_present; > + int &slot =3D m_key_index.get_or_insert (k, &key_present); > + if (!key_present) > + { > + slot =3D m_keys.length (); > + m_keys.safe_push (k); > + } > + } > + > + if (existed) > + *existed =3D _existed; > + > + return ret; > + } > + > /* Removing a key removes it from the map, but retains the insertion > order. */ > > -- > 2.34.1 >