[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