You should have received a copy of the GNU General Public License
along with Wget; if not, write to the Free Software
-Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
+Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+
+In addition, as a special exception, the Free Software Foundation
+gives permission to link the code of its release of Wget with the
+OpenSSL project's "OpenSSL" library (or with modified versions of it
+that use the same license as the "OpenSSL" library), and distribute
+the linked executables. You must obey the GNU General Public License
+in all respects for all of the code used other than "OpenSSL". If you
+modify this file, you may extend this exception to your version of the
+file, but you are not obligated to do so. If you do not wish to do
+so, delete this exception statement from your version. */
#ifdef HAVE_CONFIG_H
# include <config.h>
# define xmalloc malloc
# define xrealloc realloc
# define xfree free
+
+# undef TOLOWER
+# define TOLOWER(x) ('A' <= (x) && (x) <= 'Z' ? (x) - 32 : (x))
#endif
/* INTERFACE:
};
struct hash_table {
- unsigned long (*hash_function) (const void *);
- int (*test_function) (const void *, const void *);
+ unsigned long (*hash_function) PARAMS ((const void *));
+ int (*test_function) PARAMS ((const void *, const void *));
int size; /* size of the array */
int count; /* number of non-empty, non-deleted
int resize_threshold; /* after size exceeds this number of
entries, resize the table. */
+ int prime_offset; /* the offset of the current prime in
+ the prime table. */
- struct mapping *mappings;
+ struct mapping *mappings; /* the array of mapping pairs. */
};
#define EMPTY_MAPPING_P(mp) ((mp)->key == NULL)
#define LOOP_NON_EMPTY(mp, mappings, size) \
for (; !EMPTY_MAPPING_P (mp); mp = NEXT_MAPPING (mp, mappings, size))
+/* #### We might want to multiply with the "golden ratio" here to get
+ better randomness for keys that do not result from a good hash
+ function. This is currently not a problem in Wget because we only
+ use the string hash tables. */
+
#define HASH_POSITION(ht, key) (ht->hash_function (key) % ht->size)
-/* Find a prime near, but greather than or equal to SIZE. */
+/* Find a prime near, but greather than or equal to SIZE. Of course,
+ the primes are not calculated, but looked up from a table. The
+ table does not contain all primes in range, just a selection useful
+ for this purpose.
+
+ PRIME_OFFSET is a micro-optimization: if specified, it starts the
+ search for the prime number beginning with the specific offset in
+ the prime number table. The final offset is stored in the same
+ variable. */
static int
-prime_size (int size)
+prime_size (int size, int *prime_offset)
{
static const unsigned long primes [] = {
- 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
+ 13, 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,
10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
- 1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL
+ 1174703521, 1527114613, 1985248999,
+ (unsigned long)0x99d43ea5, (unsigned long)0xc7fa5177
};
- int i;
- for (i = 0; i < ARRAY_SIZE (primes); i++)
+ int i = *prime_offset;
+
+ for (; i < countof (primes); i++)
if (primes[i] >= size)
- return primes[i];
- /* huh? */
- return size;
+ {
+ /* Set the offset to the next prime. That is safe because,
+ next time we are called, it will be with a larger SIZE,
+ which means we could never return the same prime anyway.
+ (If that is not the case, the caller can simply reset
+ *prime_offset.) */
+ *prime_offset = i + 1;
+ return primes[i];
+ }
+
+ abort ();
+ return 0;
}
/* Create a hash table of INITIAL_SIZE with hash function
ht->hash_function = hash_function;
ht->test_function = test_function;
- ht->size = prime_size (initial_size);
+ ht->prime_offset = 0;
+ ht->size = prime_size (initial_size, &ht->prime_offset);
ht->resize_threshold = ht->size * 3 / 4;
- ht->count = 0;
+ ht->count = 0;
ht->mappings = xmalloc (ht->size * sizeof (struct mapping));
memset (ht->mappings, '\0', ht->size * sizeof (struct mapping));
struct mapping *mappings = ht->mappings;
int size = ht->size;
struct mapping *mp = mappings + HASH_POSITION (ht, key);
- int (*equals) (const void *, const void *) = ht->test_function;
+ int (*equals) PARAMS ((const void *, const void *)) = ht->test_function;
LOOP_NON_EMPTY (mp, mappings, size)
if (equals (key, mp->key))
struct mapping *mp, *mappings;
int newsize;
- newsize = prime_size (ht->size * 2);
+ newsize = prime_size (ht->size * 2, &ht->prime_offset);
#if 0
- printf ("growing from %d to %d\n", ht->size, newsize);
+ printf ("growing from %d to %d; fullness %.2f%% to %.2f%%\n",
+ ht->size, newsize,
+ (double)100 * ht->count / ht->size,
+ (double)100 * ht->count / newsize);
#endif
ht->size = newsize;
{
struct mapping *mappings = ht->mappings;
int size = ht->size;
- int (*equals) (const void *, const void *) = ht->test_function;
+ int (*equals) PARAMS ((const void *, const void *)) = ht->test_function;
struct mapping *mp = mappings + HASH_POSITION (ht, key);
projects / wget / blobdiff