diff options
| author | Andrew Tridgell <tridge@samba.org> | 2001-09-25 06:39:41 +0000 |
|---|---|---|
| committer | Andrew Tridgell <tridge@samba.org> | 2001-09-25 06:39:41 +0000 |
| commit | 666f8a09b2701d01e67d711eaccff599b036de9b (patch) | |
| tree | 61f16722d66bf3aeac2a318c1854faec582b732a | |
| parent | 827e1897783161a2a5ba797c0ff8727bd33a6f54 (diff) | |
| download | samba-666f8a09b2701d01e67d711eaccff599b036de9b.tar.gz samba-666f8a09b2701d01e67d711eaccff599b036de9b.tar.bz2 samba-666f8a09b2701d01e67d711eaccff599b036de9b.zip | |
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)
| -rw-r--r-- | source3/include/hash.h | 2 | ||||
| -rw-r--r-- | source3/lib/hash.c | 18 |
2 files changed, 11 insertions, 9 deletions
diff --git a/source3/include/hash.h b/source3/include/hash.h index 2de7031855..80a1aaae50 100644 --- a/source3/include/hash.h +++ b/source3/include/hash.h @@ -22,7 +22,7 @@ #ifndef _HASH_H_ #define _HASH_H_ -#define MAX_HASH_TABLE_SIZE 32768 +#define MAX_HASH_TABLE_SIZE 16384 #define HASH_TABLE_INCREMENT 2 typedef int (*compare_function)(char *, char *); 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 |