[PATCH] Make hashtab/hash-table elt removal not fail on removing non-existent entry
On Wed, Mar 13, 2019 at 10:08:09PM -0400, Jason Merrill wrote:
> > The following testcase ICEs since my recent cxx_eval_loop_expr changes.
> > The problem is that the Forget saved values of SAVE_EXPRs. inside of the
> > loop can remove SAVE_EXPRs from new_ctx.values and if that is the last
> > iteration, we can also do the loop at the end of function (which has been
> > added there mainly to handle cases where the main loop breaks earlier)
> > and new_ctx.values->remove ICEs because *iter is already not in the table.
>
> It shouldn't ICE, remove_elt_with_hash is documented to do nothing if the
> element is not in the table.
>
> Does this untested patch fix the test?
This changed in https://gcc.gnu.org/ml/gcc-patches/2000-02/msg00988.html
Before that change, it has been documented that:
"Naturally the hash table must already exist."
That patch changed it to do
slot = htab_find_slot (htab, element, 0);
if (*slot == EMPTY_ENTRY)
return;
but htab_find_slot actually never returns *slot == EMPTY_ENTRY if called
with insert 0:
+ if (!insert)
+ return NULL;
It can return *slot == EMPTY_ENTRY only if insert is non-zero, and
otherwise it must be (for both cases) a non-deleted non-empty entry equal to
the one we are looking for.
Thus, I believe what is documented since that patch has never worked and we
are wasting cycles (if not optimized out) testing something impossible.
So, I think our options are either to make it work, like below (untested),
or remove those ifs altogether and put back the
"Naturally the hash table must already exist." comment.
2019-03-14 Jason Merrill
Jakub Jelinek
* hash-table.h (remove_elt_with_hash): Return if slot is NULL rather
than if is_empty (*slot).
* hashtab.c (htab_remove_elt_with_hash): Return if slot is NULL rather
than if *slot is HTAB_EMPTY_ENTRY.
--- gcc/hash-table.h.jj 2019-01-01 12:37:17.446970209 +0100
+++ gcc/hash-table.h2019-03-14 08:48:18.861131498 +0100
@@ -940,7 +940,7 @@ hash_table
::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
{
value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
- if (is_empty (*slot))
+ if (slot == NULL)
return;
Descriptor::remove (*slot);
--- libiberty/hashtab.c.jj 2019-01-01 12:38:46.868503025 +0100
+++ libiberty/hashtab.c 2019-03-14 08:47:49.172612001 +0100
@@ -725,7 +725,7 @@ htab_remove_elt_with_hash (htab_t htab,
PTR *slot;
slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
- if (*slot == HTAB_EMPTY_ENTRY)
+ if (slot == NULL)
return;
if (htab->del_f)
Jakub
Re: [PATCH] Make hashtab/hash-table elt removal not fail on removing non-existent entry
On Thu, 14 Mar 2019, Jakub Jelinek wrote:
> On Wed, Mar 13, 2019 at 10:08:09PM -0400, Jason Merrill wrote:
> > > The following testcase ICEs since my recent cxx_eval_loop_expr changes.
> > > The problem is that the Forget saved values of SAVE_EXPRs. inside of the
> > > loop can remove SAVE_EXPRs from new_ctx.values and if that is the last
> > > iteration, we can also do the loop at the end of function (which has been
> > > added there mainly to handle cases where the main loop breaks earlier)
> > > and new_ctx.values->remove ICEs because *iter is already not in the table.
> >
> > It shouldn't ICE, remove_elt_with_hash is documented to do nothing if the
> > element is not in the table.
> >
> > Does this untested patch fix the test?
>
> This changed in https://gcc.gnu.org/ml/gcc-patches/2000-02/msg00988.html
> Before that change, it has been documented that:
> "Naturally the hash table must already exist."
> That patch changed it to do
> slot = htab_find_slot (htab, element, 0);
> if (*slot == EMPTY_ENTRY)
> return;
> but htab_find_slot actually never returns *slot == EMPTY_ENTRY if called
> with insert 0:
> + if (!insert)
> + return NULL;
> It can return *slot == EMPTY_ENTRY only if insert is non-zero, and
> otherwise it must be (for both cases) a non-deleted non-empty entry equal to
> the one we are looking for.
>
> Thus, I believe what is documented since that patch has never worked and we
> are wasting cycles (if not optimized out) testing something impossible.
>
> So, I think our options are either to make it work, like below (untested),
> or remove those ifs altogether and put back the
> "Naturally the hash table must already exist." comment.
I'd say make it work, thus your patch below is OK.
Richard.
> 2019-03-14 Jason Merrill
> Jakub Jelinek
>
> * hash-table.h (remove_elt_with_hash): Return if slot is NULL rather
> than if is_empty (*slot).
>
> * hashtab.c (htab_remove_elt_with_hash): Return if slot is NULL rather
> than if *slot is HTAB_EMPTY_ENTRY.
>
> --- gcc/hash-table.h.jj 2019-01-01 12:37:17.446970209 +0100
> +++ gcc/hash-table.h 2019-03-14 08:48:18.861131498 +0100
> @@ -940,7 +940,7 @@ hash_table
> ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
> {
>value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
> - if (is_empty (*slot))
> + if (slot == NULL)
> return;
>
>Descriptor::remove (*slot);
> --- libiberty/hashtab.c.jj2019-01-01 12:38:46.868503025 +0100
> +++ libiberty/hashtab.c 2019-03-14 08:47:49.172612001 +0100
> @@ -725,7 +725,7 @@ htab_remove_elt_with_hash (htab_t htab,
>PTR *slot;
>
>slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
> - if (*slot == HTAB_EMPTY_ENTRY)
> + if (slot == NULL)
> return;
>
>if (htab->del_f)
>
>
> Jakub
>
--
Richard Biener
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB
21284 (AG Nuernberg)
Re: [PATCH] Make hashtab/hash-table elt removal not fail on removing non-existent entry
On Thu, Mar 14, 2019 at 09:57:27AM +0100, Richard Biener wrote:
> I'd say make it work, thus your patch below is OK.
Ok, here is an updated patch with some self-tests coverage as well that I'll
bootstrap/regtest.
2019-03-14 Jason Merrill
Jakub Jelinek
* hash-table.h (remove_elt_with_hash): Return if slot is NULL rather
than if is_empty (*slot).
* hash-set-tests.c (test_set_of_strings): Add tests for addition of
existing elt and for elt removal.
* hash-map-tests.c (test_map_of_strings_to_int): Add test for removal
of already removed elt.
* hashtab.c (htab_remove_elt_with_hash): Return if slot is NULL rather
than if *slot is HTAB_EMPTY_ENTRY.
--- gcc/hash-table.h.jj 2019-01-01 12:37:17.446970209 +0100
+++ gcc/hash-table.h2019-03-14 08:48:18.861131498 +0100
@@ -940,7 +940,7 @@ hash_table
::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
{
value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
- if (is_empty (*slot))
+ if (slot == NULL)
return;
Descriptor::remove (*slot);
--- gcc/hash-set-tests.c.jj 2019-01-01 12:37:21.648901265 +0100
+++ gcc/hash-set-tests.c2019-03-14 10:06:04.688950764 +0100
@@ -48,11 +48,26 @@ test_set_of_strings ()
ASSERT_EQ (false, s.add (red));
ASSERT_EQ (false, s.add (green));
ASSERT_EQ (false, s.add (blue));
+ ASSERT_EQ (true, s.add (green));
/* Verify that the values are now within the set. */
ASSERT_EQ (true, s.contains (red));
ASSERT_EQ (true, s.contains (green));
ASSERT_EQ (true, s.contains (blue));
+ ASSERT_EQ (3, s.elements ());
+
+ /* Test removal. */
+ s.remove (red);
+ ASSERT_EQ (false, s.contains (red));
+ ASSERT_EQ (true, s.contains (green));
+ ASSERT_EQ (true, s.contains (blue));
+ ASSERT_EQ (2, s.elements ());
+
+ s.remove (red);
+ ASSERT_EQ (false, s.contains (red));
+ ASSERT_EQ (true, s.contains (green));
+ ASSERT_EQ (true, s.contains (blue));
+ ASSERT_EQ (2, s.elements ());
}
/* Run all of the selftests within this file. */
--- gcc/hash-map-tests.c.jj 2019-01-21 20:46:21.963092085 +0100
+++ gcc/hash-map-tests.c2019-03-14 10:06:56.994105872 +0100
@@ -78,6 +78,10 @@ test_map_of_strings_to_int ()
ASSERT_EQ (5, m.elements ());
ASSERT_EQ (NULL, m.get (eric));
+ m.remove (eric);
+ ASSERT_EQ (5, m.elements ());
+ ASSERT_EQ (NULL, m.get (eric));
+
/* A plain char * key is hashed based on its value (address), rather
than the string it points to. */
char *another_ant = static_cast (xcalloc (4, 1));
--- libiberty/hashtab.c.jj 2019-01-01 12:38:46.868503025 +0100
+++ libiberty/hashtab.c 2019-03-14 08:47:49.172612001 +0100
@@ -725,7 +725,7 @@ htab_remove_elt_with_hash (htab_t htab,
PTR *slot;
slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
- if (*slot == HTAB_EMPTY_ENTRY)
+ if (slot == NULL)
return;
if (htab->del_f)
Jakub
Re: [PATCH] Make hashtab/hash-table elt removal not fail on removing non-existent entry
On Thu, 14 Mar 2019 10:19:17 +0100
Jakub Jelinek wrote:
> On Thu, Mar 14, 2019 at 09:57:27AM +0100, Richard Biener wrote:
> > I'd say make it work, thus your patch below is OK.
>
> Ok, here is an updated patch with some self-tests coverage as well that I'll
> bootstrap/regtest.
I had the simple slot == NULL || is_empty (*slot) hack in
remove_elt_with_hash in my aldot/fortran-fe-stringpool stash since a
long time now and hence support this change, fwiw.
Many thanks!
>
> 2019-03-14 Jason Merrill
> Jakub Jelinek
>
> * hash-table.h (remove_elt_with_hash): Return if slot is NULL rather
> than if is_empty (*slot).
> * hash-set-tests.c (test_set_of_strings): Add tests for addition of
> existing elt and for elt removal.
> * hash-map-tests.c (test_map_of_strings_to_int): Add test for removal
> of already removed elt.
>
> * hashtab.c (htab_remove_elt_with_hash): Return if slot is NULL rather
> than if *slot is HTAB_EMPTY_ENTRY.
>
> --- gcc/hash-table.h.jj 2019-01-01 12:37:17.446970209 +0100
> +++ gcc/hash-table.h 2019-03-14 08:48:18.861131498 +0100
> @@ -940,7 +940,7 @@ hash_table
> ::remove_elt_with_hash (const compare_type &comparable, hashval_t hash)
> {
>value_type *slot = find_slot_with_hash (comparable, hash, NO_INSERT);
> - if (is_empty (*slot))
> + if (slot == NULL)
> return;
>
>Descriptor::remove (*slot);
> --- gcc/hash-set-tests.c.jj 2019-01-01 12:37:21.648901265 +0100
> +++ gcc/hash-set-tests.c 2019-03-14 10:06:04.688950764 +0100
> @@ -48,11 +48,26 @@ test_set_of_strings ()
>ASSERT_EQ (false, s.add (red));
>ASSERT_EQ (false, s.add (green));
>ASSERT_EQ (false, s.add (blue));
> + ASSERT_EQ (true, s.add (green));
>
>/* Verify that the values are now within the set. */
>ASSERT_EQ (true, s.contains (red));
>ASSERT_EQ (true, s.contains (green));
>ASSERT_EQ (true, s.contains (blue));
> + ASSERT_EQ (3, s.elements ());
> +
> + /* Test removal. */
> + s.remove (red);
> + ASSERT_EQ (false, s.contains (red));
> + ASSERT_EQ (true, s.contains (green));
> + ASSERT_EQ (true, s.contains (blue));
> + ASSERT_EQ (2, s.elements ());
> +
> + s.remove (red);
> + ASSERT_EQ (false, s.contains (red));
> + ASSERT_EQ (true, s.contains (green));
> + ASSERT_EQ (true, s.contains (blue));
> + ASSERT_EQ (2, s.elements ());
> }
>
> /* Run all of the selftests within this file. */
> --- gcc/hash-map-tests.c.jj 2019-01-21 20:46:21.963092085 +0100
> +++ gcc/hash-map-tests.c 2019-03-14 10:06:56.994105872 +0100
> @@ -78,6 +78,10 @@ test_map_of_strings_to_int ()
>ASSERT_EQ (5, m.elements ());
>ASSERT_EQ (NULL, m.get (eric));
>
> + m.remove (eric);
> + ASSERT_EQ (5, m.elements ());
> + ASSERT_EQ (NULL, m.get (eric));
> +
>/* A plain char * key is hashed based on its value (address), rather
> than the string it points to. */
>char *another_ant = static_cast (xcalloc (4, 1));
> --- libiberty/hashtab.c.jj2019-01-01 12:38:46.868503025 +0100
> +++ libiberty/hashtab.c 2019-03-14 08:47:49.172612001 +0100
> @@ -725,7 +725,7 @@ htab_remove_elt_with_hash (htab_t htab,
>PTR *slot;
>
>slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
> - if (*slot == HTAB_EMPTY_ENTRY)
> + if (slot == NULL)
> return;
>
>if (htab->del_f)
>
>
> Jakub
