2000-02-25

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@627 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 51 insertions, 21 deletions

diff --git a/st.c b/st.c
index 225fd52cdd..cd72d26af8 100644
--- a/st.c
+++ b/st.c
@@ -62,7 +62,7 @@ static void rehash();
 #define EQUAL(table, x, y) ((*table->type->compare)(x, y) == 0)
 
 #define do_hash(key, table) (unsigned int)(*(table)->type->hash)((key))
-#define do_hash_bin(key, table) (do_hash(key, table)%(table)->num_bins)
+#define do_hash_bin(key, table) (do_hash(key, table)&(table)->num_bins)
 
 /*
  * MINSIZE is the minimum size of a dictionary.
@@ -112,6 +112,11 @@ new_size(size)
     int i, newsize;
 
 #if 1
+    for (i=3; i<31; i++) {
+	if ((1<<i) > size) return 1<<i;
+    }
+    return -1;
+#else
     for (i = 0, newsize = MINSIZE;
 	 i < sizeof(primes)/sizeof(primes[0]);
 	 i++, newsize <<= 1)
@@ -120,14 +125,10 @@ new_size(size)
     }
     /* Ran out of polynomials */
     return -1;			/* should raise exception */
-#else
-    for (i=3; i<31; i++) {
-	if ((1<<i) > size) return 1<<i;
-    }
-    return -1;
 #endif
 }
 
+#ifdef HASH_LOG
 static int collision = 0;
 static int init_st = 0;
 
@@ -138,6 +139,7 @@ stat_col()
     fprintf(f, "collision: %d\n", collision);
     fclose(f);
 }
+#endif
 
 st_table*
 st_init_table_with_size(type, size)
@@ -146,7 +148,7 @@ st_init_table_with_size(type, size)
 {
     st_table *tbl;
 
-#if 0
+#ifdef HASH_LOG
     if (init_st == 0) {
 	init_st = 1;
 	atexit(stat_col);
@@ -158,7 +160,7 @@ st_init_table_with_size(type, size)
     tbl = alloc(st_table);
     tbl->type = type;
     tbl->num_entries = 0;
-    tbl->num_bins = size;
+    tbl->num_bins = size-1;
     tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
 
     return tbl;
@@ -204,7 +206,7 @@ st_free_table(table)
     register st_table_entry *ptr, *next;
     int i;
 
-    for(i = 0; i < table->num_bins; i++) {
+    for(i = 0; i <= table->num_bins; i++) {
 	ptr = table->bins[i];
 	while (ptr != 0) {
 	    next = ptr->next;
@@ -219,11 +221,17 @@ st_free_table(table)
 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
 
+#ifdef HASH_LOG
+#define COLLISION collision++
+#else
+#define COLLISION
+#endif
+
 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) \
-bin_pos = hash_val%(table)->num_bins;\
+bin_pos = hash_val&(table)->num_bins;\
 ptr = (table)->bins[bin_pos];\
 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
-    collision++;\
+    COLLISION;\
     while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
 	ptr = ptr->next;\
     }\
@@ -253,9 +261,9 @@ st_lookup(table, key, value)
 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
 {\
     st_table_entry *entry;\
-    if (table->num_entries/table->num_bins > ST_DEFAULT_MAX_DENSITY) {\
+    if (table->num_entries/(table->num_bins+1) > ST_DEFAULT_MAX_DENSITY) {\
 	rehash(table);\
-        bin_pos = hash_val % table->num_bins;\
+        bin_pos = hash_val & table->num_bins;\
     }\
     \
     entry = alloc(st_table_entry);\
@@ -298,7 +306,7 @@ st_add_direct(table, key, value)
     unsigned int hash_val, bin_pos;
 
     hash_val = do_hash(key, table);
-    bin_pos = hash_val % table->num_bins;
+    bin_pos = hash_val & table->num_bins;
     ADD_DIRECT(table, key, value, hash_val, bin_pos);
 }
 
@@ -310,14 +318,15 @@ rehash(table)
     int i, old_num_bins = table->num_bins, new_num_bins;
     unsigned int hash_val;
 
-    new_num_bins = new_size(old_num_bins);
+    new_num_bins = new_size(old_num_bins+1);
     new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
 
-    for(i = 0; i < old_num_bins; i++) {
+    new_num_bins--;
+    for(i = 0; i <= old_num_bins; i++) {
 	ptr = table->bins[i];
 	while (ptr != 0) {
 	    next = ptr->next;
-	    hash_val = ptr->hash % new_num_bins;
+	    hash_val = ptr->hash & new_num_bins;
 	    ptr->next = new_bins[hash_val];
 	    new_bins[hash_val] = ptr;
 	    ptr = next;
@@ -334,7 +343,7 @@ st_copy(old_table)
 {
     st_table *new_table;
     st_table_entry *ptr, *entry;
-    int i, num_bins = old_table->num_bins;
+    int i, num_bins = old_table->num_bins+1;
 
     new_table = alloc(st_table);
     if (new_table == 0) {
@@ -471,7 +480,7 @@ st_foreach(table, func, arg)
     enum st_retval retval;
     int i;
 
-    for(i = 0; i < table->num_bins; i++) {
+    for(i = 0; i <= table->num_bins; i++) {
 	last = 0;
 	for(ptr = table->bins[i]; ptr != 0;) {
 	    retval = (*func)(ptr->key, ptr->record, arg);
@@ -501,14 +510,35 @@ static int
 strhash(string)
     register char *string;
 {
-    register int val = 0;
     register int c;
 
+#ifdef HASH_ELFHASH
+    register unsigned int h = 0, g;
+
+    while ((c = *string++) != '\0') {
+	h = ( h << 4 ) + c;
+	if ( g = h & 0xF0000000 )
+	    h ^= g >> 24;
+	h &= ~g;
+    }
+    return h;
+#elif HASH_PERL
+    register int val = 0;
+
+    while ((c = *string++) != '\0') {
+	val = val*33 + c;
+    }
+
+    return val + (val>>5);
+#else
+    register int val = 0;
+
     while ((c = *string++) != '\0') {
 	val = val*997 + c;
     }
 
-    return val;
+    return val + (val>>5);
+#endif
 }
 
 static int