12. apr. 2015 18.33 skrev "Emil Velikov" <<a href="mailto:emil.l.velikov@gmail.com">emil.l.velikov@gmail.com</a>>: > > 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 <<a href="mailto:thomashelland90@gmail.com">thomashelland90@gmail.com</a>> > > --- > > 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