[Mesa-dev] [PATCH 1/3] util/tests: Expand collision test for hash table

[Thomas Helland]

12. apr. 2015 18.33 skrev "Emil Velikov" <emil.l.velikov at gmail.com>:
>
> Hi Thomas,
>
> On 11/04/15 23:25, Thomas Helland wrote:
> > Add a test to exercise a worst case collision scenario
> > that may cause us to not be able to find an empty
> > slot in the table even though it is not full.
> > This hits the bug in my last revision of the series
> > converting the hash table to quadratic probing.
> >
> > Signed-off-by: Thomas Helland <thomashelland90 at gmail.com>
> > ---
> >  src/util/tests/hash_table/collision.c | 14 ++++++++++++++
> >  1 file changed, 14 insertions(+)
> >
> > diff --git a/src/util/tests/hash_table/collision.c
b/src/util/tests/hash_table/collision.c
> > index 69a4c29..ba284d8 100644
> > --- a/src/util/tests/hash_table/collision.c
> > +++ b/src/util/tests/hash_table/collision.c
> > @@ -89,6 +89,20 @@ main(int argc, char **argv)
> >     entry2 = _mesa_hash_table_search_pre_hashed(ht, bad_hash, str2);
> >     assert(entry2->key == str2);
> >
> > +
> > +   _mesa_hash_table_destroy(ht, NULL);
> > +
> > +   /* Try inserting multiple items with the same hash
> > +    * This exercises a worst case scenario where we might fail to find
> > +    * an empty slot in the table, even though there is free space
> > +    */
> > +   ht = _mesa_hash_table_create(NULL, NULL, _mesa_key_string_equal);
> > +   for (i = 0; i < 100; i++) {
> > +      char *key = malloc(10);
> > +      sprintf(key, "spam%d", i);
> > +      assert(_mesa_hash_table_insert_pre_hashed(ht, bad_hash, key,
NULL) != NULL);
> Please don't include code in asserts - it won't exist for non-debug
builds.

I'll post an updated version by tomorrow.

-Thomas

>
> -Emil
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20150412/e5d8342f/attachment.html>