[Mesa-dev] [PATCH 3/4] util: Change util/set to use quadratic probing

[Jan Ziak]

Hello

IMPORTANT NOTE: Using the uint32_t data type, quad_hash*quad_hash will
overflow as soon as the hash table has more than 2**16=65536=64K
elements. To enable more than 64K elements in hash table, the data
types need to be changed to uint64_t - unfortunately uint64_t
arithmetic operations will slow down the hash table in 32-bit OpenGL
apps.

OPTIMIZATION: All "} while (hash_address != start_hash_address);" can
be replaced with "} while (1);" assuming that the hash table always
contains at least several free/unallocated entries. This optimization
applies both to current mesa-git and to the quadratic probing patch.
For quadratic probing this optimization works if the statement "values
of h(k,i) for i in [0,m-1] are all distinct" at
https://en.wikipedia.org/wiki/Quadratic_probing is correct.

Jan