On Sat, Feb 28, 2015 at 1:53 PM, Thomas Helland <thomashellan...@gmail.com> wrote: > This should give better cache locality, less memory consumption, > less code, and should also be faster since we avoid a modulo operation. > > This is not the quadratic probing function you see most places. > They do not accumulate, so you try hash +1, +4, +9, etc. > My code accumulates; so it becomes hash +1, +5, +14, etc. > It felt more natural to do it like this. > > However, it causes an assertion failure. > The search function is apparently returning null when it shouldn't. > This does not get caught by make-check. > This gets fixed by the next patch. > --- > src/util/hash_table.c | 91 > ++++++++++++++++++++++++--------------------------- > src/util/hash_table.h | 1 - > 2 files changed, 43 insertions(+), 49 deletions(-) > > diff --git a/src/util/hash_table.c b/src/util/hash_table.c > index 3247593..542f583 100644 > --- a/src/util/hash_table.c > +++ b/src/util/hash_table.c > @@ -33,7 +33,7 @@ > */ > > /** > - * Implements an open-addressing, linear-reprobing hash table. > + * Implements an open-addressing, quadratic probing hash table. > * > * For more information, see: > * > @@ -51,44 +51,44 @@ > static const uint32_t deleted_key_value; > > /** > - * From Knuth -- a good choice for hash/rehash values is p, p-2 where > - * p and p-2 are both prime. These tables are sized to have an extra 10% > - * free to avoid exponential performance degradation as the hash table fills > + * From Knuth -- a good choice for hash values is p, where is prime. > + * These tables are sized to have an extra 10% free to avoid > + * exponential performance degradation as the hash table fills
"[...] where is prime"? Where what is prime? _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev