| Message ID | or1qojelwj.fsf_-_@lxoliva.fsfla.org |
|---|---|
| State | New |
| Headers | show |
| Series | [01/13] scoped tables: insert before further lookups | expand |
On Wed, Dec 28, 2022 at 1:47 PM Alexandre Oliva via Gcc-patches <gcc-patches@gcc.gnu.org> wrote: > > On Dec 28, 2022, Martin Liška <mliska@suse.cz> wrote: > > > I really like the verification code you added. It's quite similar to what > > I added to hash-table.h: > > *nod* > > Prompted by your encouragement, I've combined the element count > verification code with the verify() loop, and also added it to expand, > where it can be done cheaply. > > > Add cheap verification of element and deleted entry counts during > expand and hash verify. > > Regstrapped on x86_64-linux-gnu. Ok to install? OK. > > for gcc/ChangeLog > > * hash-table.h (expand): Check elements and deleted counts. > (verify): Likewise. > --- > gcc/hash-table.h | 35 ++++++++++++++++++++++++++++------- > 1 file changed, 28 insertions(+), 7 deletions(-) > > diff --git a/gcc/hash-table.h b/gcc/hash-table.h > index 53507daae26c3..f4bda6102323e 100644 > --- a/gcc/hash-table.h > +++ b/gcc/hash-table.h > @@ -805,19 +805,28 @@ hash_table<Descriptor, Lazy, Allocator>::expand () > hash_table_usage ().release_instance_overhead (this, sizeof (value_type) > * osize); > > + size_t n_deleted = m_n_deleted; > + > m_entries = nentries; > m_size = nsize; > m_size_prime_index = nindex; > m_n_elements -= m_n_deleted; > m_n_deleted = 0; > > + size_t n_elements = m_n_elements; > + > value_type *p = oentries; > do > { > value_type &x = *p; > > - if (!is_empty (x) && !is_deleted (x)) > + if (is_empty (x)) > + ; > + else if (is_deleted (x)) > + n_deleted--; > + else > { > + n_elements--; > value_type *q = find_empty_slot_for_expand (Descriptor::hash (x)); > new ((void*) q) value_type (std::move (x)); > /* After the resources of 'x' have been moved to a new object at 'q', > @@ -829,6 +838,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand () > } > while (p < olimit); > > + gcc_checking_assert (!n_elements && !n_deleted); > + > if (!m_ggc) > Allocator <value_type> ::data_free (oentries); > else > @@ -1018,8 +1029,9 @@ hash_table<Descriptor, Lazy, Allocator> > return &m_entries[index]; > } > > -/* Verify that all existing elements in th hash table which are > - equal to COMPARABLE have an equal HASH value provided as argument. */ > +/* Verify that all existing elements in the hash table which are > + equal to COMPARABLE have an equal HASH value provided as argument. > + Also check that the hash table element counts are correct. */ > > template<typename Descriptor, bool Lazy, > template<typename Type> class Allocator> > @@ -1027,14 +1039,23 @@ void > hash_table<Descriptor, Lazy, Allocator> > ::verify (const compare_type &comparable, hashval_t hash) > { > + size_t n_elements = m_n_elements; > + size_t n_deleted = m_n_deleted; > for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++) > { > value_type *entry = &m_entries[i]; > - if (!is_empty (*entry) && !is_deleted (*entry) > - && hash != Descriptor::hash (*entry) > - && Descriptor::equal (*entry, comparable)) > - hashtab_chk_error (); > + if (!is_empty (*entry)) > + { > + n_elements--; > + if (is_deleted (*entry)) > + n_deleted--; > + else if (hash != Descriptor::hash (*entry) > + && Descriptor::equal (*entry, comparable)) > + hashtab_chk_error (); > + } > } > + if (hash_table_sanitize_eq_limit >= m_size) > + gcc_checking_assert (!n_elements && !n_deleted); > } > > /* This function deletes an element with the given COMPARABLE value > > > -- > Alexandre Oliva, happy hacker https://FSFLA.org/blogs/lxo/ > Free Software Activist GNU Toolchain Engineer > Disinformation flourishes because many people care deeply about injustice > but very few check the facts. Ask me about <https://stallmansupport.org>
diff --git a/gcc/hash-table.h b/gcc/hash-table.h index 53507daae26c3..f4bda6102323e 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -805,19 +805,28 @@ hash_table<Descriptor, Lazy, Allocator>::expand () hash_table_usage ().release_instance_overhead (this, sizeof (value_type) * osize); + size_t n_deleted = m_n_deleted; + m_entries = nentries; m_size = nsize; m_size_prime_index = nindex; m_n_elements -= m_n_deleted; m_n_deleted = 0; + size_t n_elements = m_n_elements; + value_type *p = oentries; do { value_type &x = *p; - if (!is_empty (x) && !is_deleted (x)) + if (is_empty (x)) + ; + else if (is_deleted (x)) + n_deleted--; + else { + n_elements--; value_type *q = find_empty_slot_for_expand (Descriptor::hash (x)); new ((void*) q) value_type (std::move (x)); /* After the resources of 'x' have been moved to a new object at 'q', @@ -829,6 +838,8 @@ hash_table<Descriptor, Lazy, Allocator>::expand () } while (p < olimit); + gcc_checking_assert (!n_elements && !n_deleted); + if (!m_ggc) Allocator <value_type> ::data_free (oentries); else @@ -1018,8 +1029,9 @@ hash_table<Descriptor, Lazy, Allocator> return &m_entries[index]; } -/* Verify that all existing elements in th hash table which are - equal to COMPARABLE have an equal HASH value provided as argument. */ +/* Verify that all existing elements in the hash table which are + equal to COMPARABLE have an equal HASH value provided as argument. + Also check that the hash table element counts are correct. */ template<typename Descriptor, bool Lazy, template<typename Type> class Allocator> @@ -1027,14 +1039,23 @@ void hash_table<Descriptor, Lazy, Allocator> ::verify (const compare_type &comparable, hashval_t hash) { + size_t n_elements = m_n_elements; + size_t n_deleted = m_n_deleted; for (size_t i = 0; i < MIN (hash_table_sanitize_eq_limit, m_size); i++) { value_type *entry = &m_entries[i]; - if (!is_empty (*entry) && !is_deleted (*entry) - && hash != Descriptor::hash (*entry) - && Descriptor::equal (*entry, comparable)) - hashtab_chk_error (); + if (!is_empty (*entry)) + { + n_elements--; + if (is_deleted (*entry)) + n_deleted--; + else if (hash != Descriptor::hash (*entry) + && Descriptor::equal (*entry, comparable)) + hashtab_chk_error (); + } } + if (hash_table_sanitize_eq_limit >= m_size) + gcc_checking_assert (!n_elements && !n_deleted); } /* This function deletes an element with the given COMPARABLE value