1 files changed, 125 insertions, 77 deletions

diff --git a/st.c b/st.c
index d825a7d3c9..3efba70e22 100644
--- a/st.c
+++ b/st.c
@@ -1,21 +1,13 @@
 /* This is a general purpose hash table package written by Peter Moore @ UCB. */
 
 static	char	sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible";
-#ifndef lint
-static char *rcsid = "$Header: /usr/ext/cvsroot/ruby/st.c,v 1.3 1994/12/09 01:28:33 matz Exp $";
-#endif
 
 #include "config.h"
 #include <stdio.h>
 #include "st.h"
 
-extern void *xmalloc();
-static void rehash();
-
-#define max(a,b) ((a) > (b) ? (a) : (b))
-#define nil(type) ((type *) 0)
-#define alloc(type) (type *)xmalloc((unsigned)sizeof(type))
-#define Calloc(n,s) (char *)xcalloc((n),(s))
+#define ST_DEFAULT_MAX_DENSITY 5
+#define ST_DEFAULT_INIT_TABLE_SIZE 11
 
     /*
      * DEFAULT_MAX_DENSITY is the default for the largest we allow the
@@ -26,47 +18,98 @@ static void rehash();
      * allocated initially
      *
      */
+static int numcmp();
+static int numhash();
+struct st_hash_type type_numhash = {
+    numcmp,
+    numhash,
+};
+
+extern int strcmp();
+static int strhash();
+struct st_hash_type type_strhash = {
+    strcmp,
+    strhash,
+};
+
+#include "sig.h"
+
+extern void *xmalloc();
+static void rehash();
+
+#define max(a,b) ((a) > (b) ? (a) : (b))
+#define nil(type) ((type*)0)
+#define alloc(type) (type*)xmalloc((unsigned)sizeof(type))
+#define Calloc(n,s) (char*)xcalloc((n),(s))
+
+static int
+call_cmp_func(table, x, y)
+    st_table *table;
+    char *x, *y;
+{
+    int cmp;
+
+    DEFER_INTS;
+    cmp = (*table->type->compare)(x, y);
+    ALLOW_INTS;
+    return cmp;
+}
+
+#define EQUAL(table, x, y) (call_cmp_func((table),(x), (y)) == 0)
 
-#define EQUAL(func, x, y) \
-    ((func == ST_NUMCMP) ? ((x) == (y)) : ((*func)((x), (y)) == 0))
+static int
+call_hash_func(key, table)
+    char *key;
+    st_table *table;
+{
+    int hash;
 
-/*#define do_hash(key, table) (*table->hash)(key, table->num_bins)*/
+    DEFER_INTS;
+    hash = (*table->type->hash)((key), table->num_bins);
+    ALLOW_INTS;
+    return hash;
+}
 
-#define do_hash(key, table)\
-    ((table->hash == ST_PTRHASH) ? (((int) (key) >> 2) % table->num_bins) :\
-	(table->hash == ST_NUMHASH) ? ((int) (key) % table->num_bins) :\
-	(*table->hash)((key), table->num_bins))
+#define do_hash(key, table) call_hash_func((key), table)
 
 st_table*
-st_init_table_with_params(compare, hash, size, density, reorder_flag)
-    int (*compare)();
-    int (*hash)();
+st_init_table_with_size(type, size)
+    struct st_hash_type *type;
     int size;
-    int density;
-    int reorder_flag;
 {
     st_table *tbl;
 
+    if (size == 0) size = ST_DEFAULT_INIT_TABLE_SIZE;
+    else size /= ST_DEFAULT_MAX_DENSITY*0.87;
+
+    if (size < ST_DEFAULT_INIT_TABLE_SIZE)
+	size = ST_DEFAULT_INIT_TABLE_SIZE;
+
     tbl = alloc(st_table);
-    tbl->compare = compare;
-    tbl->hash = hash;
+    tbl->type = type;
     tbl->num_entries = 0;
-    tbl->max_density = density;
-    tbl->reorder_flag = reorder_flag;
     tbl->num_bins = size;
-    tbl->bins =
-	(st_table_entry **) Calloc((unsigned)size, sizeof(st_table_entry *));
+    tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
     return tbl;
 }
 
 st_table*
-st_init_table(compare, hash)
-    int (*compare)();
-    int (*hash)();
+st_init_table(type)
+    struct st_hash_type *type;
+{
+    return st_init_table_with_size(type, 0);
+}
+
+st_table*
+st_init_numtable()
 {
-    return st_init_table_with_params(compare, hash, ST_DEFAULT_INIT_TABLE_SIZE,
-				     ST_DEFAULT_MAX_DENSITY,
-				     ST_DEFAULT_REORDER_FLAG);
+    return st_init_table(&type_numhash);
+}
+
+st_table*
+st_init_strtable()
+{
+    return st_init_table(&type_strhash);
 }
 
 int
@@ -80,32 +123,24 @@ st_free_table(table)
 	ptr = table->bins[i];
 	while (ptr != nil(st_table_entry)) {
 	    next = ptr->next;
-	    free((char *) ptr);
+	    free((char*)ptr);
 	    ptr = next;
 	}
     }
-    free((char *) table->bins);
-    free((char *) table);
+    free((char*)table->bins);
+    free((char*)table);
 }
 
-#define PTR_NOT_EQUAL(table, ptr, key)\
-(ptr != nil(st_table_entry) && !EQUAL(table->compare, key, (ptr)->key))
+#define PTR_NOT_EQUAL(table, ptr, key) \
+(ptr != nil(st_table_entry) && !EQUAL(table, key, (ptr)->key))
 
-#define FIND_ENTRY(table, ptr, hash_val)\
+#define FIND_ENTRY(table, ptr, hash_val) \
 ptr = (table)->bins[hash_val];\
 if (PTR_NOT_EQUAL(table, ptr, key)) {\
     while (PTR_NOT_EQUAL(table, ptr->next, key)) {\
 	ptr = ptr->next;\
     }\
-    if (ptr->next != nil(st_table_entry) && (table)->reorder_flag) {\
-	st_table_entry *_tmp = (ptr)->next;\
-	(ptr)->next = (ptr)->next->next;\
-	_tmp->next = (table)->bins[hash_val];\
-	(table)->bins[hash_val] = _tmp;\
-	ptr = _tmp;\
-    } else {\
-	ptr = ptr->next;\
-    }\
+    ptr = ptr->next;\
 }
 
 int
@@ -124,16 +159,16 @@ st_lookup(table, key, value)
     if (ptr == nil(st_table_entry)) {
 	return 0;
     } else {
-	if (value != nil(char *))  *value = ptr->record;
+	if (value != nil(char*))  *value = ptr->record;
 	return 1;
     }
 }
 
 #define ADD_DIRECT(table, key, value, hash_val, tbl)\
 {\
-    if (table->num_entries/table->num_bins > table->max_density) {\
+    if (table->num_entries/table->num_bins > ST_DEFAULT_MAX_DENSITY) {\
 	rehash(table);\
-	hash_val = do_hash(key,table);\
+	hash_val = do_hash(key, table);\
     }\
     \
     tbl = alloc(st_table_entry);\
@@ -195,11 +230,11 @@ st_find_or_add(table, key, slot)
     FIND_ENTRY(table, ptr, hash_val);
 
     if (ptr == nil(st_table_entry)) {
-	ADD_DIRECT(table, key, (char *)0, hash_val, tbl)
-	if (slot != nil(char **)) *slot = &tbl->record;
+	ADD_DIRECT(table, key, (char*)0, hash_val, tbl)
+	if (slot != nil(char**)) *slot = &tbl->record;
 	return 0;
     } else {
-	if (slot != nil(char **)) *slot = &ptr->record;
+	if (slot != nil(char**)) *slot = &ptr->record;
 	return 1;
     }
 }
@@ -211,16 +246,15 @@ rehash(table)
     register st_table_entry *ptr, *next, **old_bins = table->bins;
     int i, old_num_bins = table->num_bins, hash_val;
 
-    table->num_bins = 2*old_num_bins;
+    table->num_bins = 1.79*old_num_bins;
 
     if (table->num_bins%2 == 0) {
 	table->num_bins += 1;
     }
 
     table->num_entries = 0;
-    table->bins =
-      (st_table_entry **) Calloc((unsigned) table->num_bins,
-	    sizeof(st_table_entry *));
+    table->bins = (st_table_entry **)
+	Calloc((unsigned)table->num_bins, sizeof(st_table_entry*));
 
     for(i = 0; i < old_num_bins ; i++) {
 	ptr = old_bins[i];
@@ -233,7 +267,7 @@ rehash(table)
 	    ptr = next;
 	}
     }
-    free((char *) old_bins);
+    free((char*)old_bins);
 }
 
 st_table*
@@ -250,12 +284,11 @@ st_copy(old_table)
     }
 
     *new_table = *old_table;
-    new_table->bins =
-      (st_table_entry **) Calloc((unsigned) num_bins,
-		sizeof(st_table_entry *));
+    new_table->bins = (st_table_entry**)
+	Calloc((unsigned)num_bins, sizeof(st_table_entry*));
 
-    if (new_table->bins == nil(st_table_entry *)) {
-	free((char *) new_table);
+    if (new_table->bins == nil(st_table_entry*)) {
+	free((char*)new_table);
 	return nil(st_table);
     }
 
@@ -265,8 +298,8 @@ st_copy(old_table)
 	while (ptr != nil(st_table_entry)) {
 	    tbl = alloc(st_table_entry);
 	    if (tbl == nil(st_table_entry)) {
-		free((char *) new_table->bins);
-		free((char *) new_table);
+		free((char*)new_table->bins);
+		free((char*)new_table);
 		return nil(st_table);
 	    }
 	    *tbl = *ptr;
@@ -293,27 +326,27 @@ st_delete(table, key, value)
     ptr = table->bins[hash_val];
 
     if (ptr == nil(st_table_entry)) {
-	if (value != nil(char *)) *value = nil(char);
+	if (value != nil(char*)) *value = nil(char);
 	return 0;
     }
 
-    if (EQUAL(table->compare, *key, ptr->key)) {
+    if (EQUAL(table, *key, ptr->key)) {
 	table->bins[hash_val] = ptr->next;
 	table->num_entries--;
-	if (value != nil(char *)) *value = ptr->record;
+	if (value != nil(char*)) *value = ptr->record;
 	*key = ptr->key;
-	free((char *) ptr);
+	free((char*)ptr);
 	return 1;
     }
 
     for(; ptr->next != nil(st_table_entry); ptr = ptr->next) {
-	if (EQUAL(table->compare, ptr->next->key, *key)) {
+	if (EQUAL(table, ptr->next->key, *key)) {
 	    tmp = ptr->next;
 	    ptr->next = ptr->next->next;
 	    table->num_entries--;
-	    if (value != nil(char *)) *value = tmp->record;
+	    if (value != nil(char*)) *value = tmp->record;
 	    *key = tmp->key;
-	    free((char *) tmp);
+	    free((char*)tmp);
 	    return 1;
 	}
     }
@@ -350,15 +383,15 @@ st_foreach(table, func, arg)
 		    last->next = ptr->next;
 		}
 		ptr = ptr->next;
-		free((char *) tmp);
+		free((char*)tmp);
 		table->num_entries--;
 	    }
 	}
     }
 }
 
-int
-st_strhash(string, modulus)
+static int
+strhash(string, modulus)
     register char *string;
     int modulus;
 {
@@ -371,3 +404,18 @@ st_strhash(string, modulus)
 
     return ((val < 0) ? -val : val)%modulus;
 }
+
+static int
+numcmp(x, y)
+    int x, y;
+{
+    return x != y;
+}
+
+static int
+numhash(n, modulus)
+    int n;
+    int modulus;
+{
+    return n % modulus;
+}