+/* We use linear probing instead of double hashing, despite its lack
+ of blessing by Knuth and company, because, as a result of the
+ increasing discrepancy between CPU speeds and memory speeds, cache
+ behavior is becoming increasingly important, e.g:
+
+ For a trivial loop, the penalty for non-sequential access of an array is:
+ - a factor of 3-4 on Pentium Pro 200 Mhz
+ - a factor of 10 on Ultrasparc 300 Mhz */
+
+/* Return a suitable size for a hash table, with at least SIZE slots. */
+static size_t
+hash_table_size (size_t requested_size)
+{
+ /* Return some prime near, but greater than or equal to, SIZE.
+ Decades from the time of writing, someone will have a system large
+ enough that the list below will be too short... */
+ static CONST size_t primes [] =
+ {
+ 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
+ 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
+ 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
+ 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
+ 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
+ 10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
+ 50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
+ 243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
+ 1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL
+ };
+ /* We've heard of binary search. */
+ int low, high;
+ for (low = 0, high = countof (primes) - 1; high - low > 1;)