From 666f8a09b2701d01e67d711eaccff599b036de9b Mon Sep 17 00:00:00 2001 From: Andrew Tridgell Date: Tue, 25 Sep 2001 06:39:41 +0000 Subject: fixed the really awful performance problem with the stat cache when it ran out of primes and used a power of two hash modulus. It ended up sticking all the entries in just a few buckets. Yuck! (This used to be commit fdc9952391027e209fbd24f7794b1c2b551b1f9f) --- source3/lib/hash.c | 18 ++++++++++-------- 1 file changed, 10 insertions(+), 8 deletions(-) (limited to 'source3/lib/hash.c') diff --git a/source3/lib/hash.c b/source3/lib/hash.c index 44cd640b8d..3abdc2ef11 100644 --- a/source3/lib/hash.c +++ b/source3/lib/hash.c @@ -30,10 +30,8 @@ extern int DEBUGLEVEL; -#define NUM_PRIMES 11 - static BOOL enlarge_hash_table(hash_table *table); -static int primes[NUM_PRIMES] = +static int primes[] = {17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411}; /**************************************************************************** @@ -62,7 +60,7 @@ BOOL hash_table_init(hash_table *table, int num_buckets, compare_function compar table->comp_func = compare_func; while (table->size < num_buckets) table->size <<= 1; - for (i = 0; i < NUM_PRIMES; i++) { + for (i = 0; i < ARRAY_SIZE(primes); i++) { if (primes[i] > table->size) { table->size = primes[i]; break; @@ -94,12 +92,16 @@ BOOL hash_table_init(hash_table *table, int num_buckets, compare_function compar static int string_hash(int hash_size, const char *key) { - int j=0; - while (*key) - j = j*10 + *key++; - return(((j>=0)?j:(-j)) % hash_size); + u32 value; /* Used to compute the hash value. */ + u32 i; /* Used to cycle through random values. */ + + for (value = 0x238F13AF, i=0; key[i]; i++) + value = (value + (key[i] << (i*5 % 24))); + + return (1103515243 * value + 12345) % hash_size; } + /* ************************************************************************* * Search the hash table for the entry in the hash chain. * The function returns the pointer to the -- cgit