summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndrew Tridgell <tridge@samba.org>2001-09-25 06:39:41 +0000
committerAndrew Tridgell <tridge@samba.org>2001-09-25 06:39:41 +0000
commit666f8a09b2701d01e67d711eaccff599b036de9b (patch)
tree61f16722d66bf3aeac2a318c1854faec582b732a
parent827e1897783161a2a5ba797c0ff8727bd33a6f54 (diff)
downloadsamba-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.h2
-rw-r--r--source3/lib/hash.c18
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