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

Jan Ziak 0xe2.0x9a.0x9b at gmail.com
Thu Feb 9 21:16:30 UTC 2017


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

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.


More information about the mesa-dev mailing list