summaryrefslogtreecommitdiff
path: root/st.c
diff options
context:
space:
mode:
Diffstat (limited to 'st.c')
-rw-r--r--st.c435
1 files changed, 0 insertions, 435 deletions
diff --git a/st.c b/st.c
deleted file mode 100644
index 6b25bc854b..0000000000
--- a/st.c
+++ /dev/null
@@ -1,435 +0,0 @@
-/* This is a general purpose hash table package written by Peter Moore @ UCB. */
-
-static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible";
-
-#include "config.h"
-#include <stdio.h>
-#include "st.h"
-
-#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
- * average number of items per bin before increasing the number of
- * bins
- *
- * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
- * allocated initially
- *
- */
-static int numcmp();
-static int numhash();
-static struct st_hash_type type_numhash = {
- numcmp,
- numhash,
-};
-
-extern int strcmp();
-static int strhash();
-static struct st_hash_type type_strhash = {
- strcmp,
- strhash,
-};
-
-void *xmalloc();
-void *xcalloc();
-void *xrealloc();
-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 EQUAL(table, x, y) ((*table->type->compare)(x, y) == 0)
-
-#define do_hash(key, table) (*(table)->type->hash)((key), (table)->num_bins)
-
-st_table*
-st_init_table_with_size(type, size)
- struct st_hash_type *type;
- int size;
-{
- 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->type = type;
- tbl->num_entries = 0;
- tbl->num_bins = size;
- tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
- return tbl;
-}
-
-st_table*
-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(&type_numhash);
-}
-
-st_table*
-st_init_strtable()
-{
- return st_init_table(&type_strhash);
-}
-
-void
-st_free_table(table)
- st_table *table;
-{
- register st_table_entry *ptr, *next;
- int i;
-
- for(i = 0; i < table->num_bins ; i++) {
- ptr = table->bins[i];
- while (ptr != nil(st_table_entry)) {
- next = ptr->next;
- free((char*)ptr);
- ptr = next;
- }
- }
- free((char*)table->bins);
- free((char*)table);
-}
-
-#define PTR_NOT_EQUAL(table, ptr, key) \
-(ptr != nil(st_table_entry) && !EQUAL(table, key, (ptr)->key))
-
-#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;\
- }\
- ptr = ptr->next;\
-}
-
-int
-st_lookup(table, key, value)
- st_table *table;
- register char *key;
- char **value;
-{
- int hash_val;
- register st_table_entry *ptr;
-
- hash_val = do_hash(key, table);
-
- FIND_ENTRY(table, ptr, hash_val);
-
- if (ptr == nil(st_table_entry)) {
- return 0;
- } else {
- 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 > ST_DEFAULT_MAX_DENSITY) {\
- rehash(table);\
- hash_val = do_hash(key, table);\
- }\
- \
- tbl = alloc(st_table_entry);\
- \
- tbl->key = key;\
- tbl->record = value;\
- tbl->next = table->bins[hash_val];\
- table->bins[hash_val] = tbl;\
- table->num_entries++;\
-}
-
-int
-st_insert(table, key, value)
- register st_table *table;
- register char *key;
- char *value;
-{
- int hash_val;
- st_table_entry *tbl;
- register st_table_entry *ptr;
-
- hash_val = do_hash(key, table);
-
- FIND_ENTRY(table, ptr, hash_val);
-
- if (ptr == nil(st_table_entry)) {
- ADD_DIRECT(table,key,value,hash_val,tbl);
- return 0;
- } else {
- ptr->record = value;
- return 1;
- }
-}
-
-void
-st_add_direct(table, key, value)
- st_table *table;
- char *key;
- char *value;
-{
- int hash_val;
- st_table_entry *tbl;
-
- hash_val = do_hash(key, table);
- ADD_DIRECT(table, key, value, hash_val, tbl);
-}
-
-int
-st_find_or_add(table, key, slot)
- st_table *table;
- char *key;
- char ***slot;
-{
- int hash_val;
- st_table_entry *tbl, *ptr;
-
- hash_val = do_hash(key, table);
-
- 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;
- return 0;
- } else {
- if (slot != nil(char**)) *slot = &ptr->record;
- return 1;
- }
-}
-
-static void
-rehash(table)
- register st_table *table;
-{
- register st_table_entry *ptr, *next, **old_bins = table->bins;
- int i, old_num_bins = table->num_bins, hash_val;
-
- 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*));
-
- for(i = 0; i < old_num_bins ; i++) {
- ptr = old_bins[i];
- while (ptr != nil(st_table_entry)) {
- next = ptr->next;
- hash_val = do_hash(ptr->key, table);
- ptr->next = table->bins[hash_val];
- table->bins[hash_val] = ptr;
- table->num_entries++;
- ptr = next;
- }
- }
- free((char*)old_bins);
-}
-
-st_table*
-st_copy(old_table)
- st_table *old_table;
-{
- st_table *new_table;
- st_table_entry *ptr, *tbl;
- int i, num_bins = old_table->num_bins;
-
- new_table = alloc(st_table);
- if (new_table == nil(st_table)) {
- return nil(st_table);
- }
-
- *new_table = *old_table;
- 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);
- return nil(st_table);
- }
-
- for(i = 0; i < num_bins ; i++) {
- new_table->bins[i] = nil(st_table_entry);
- ptr = old_table->bins[i];
- 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);
- return nil(st_table);
- }
- *tbl = *ptr;
- tbl->next = new_table->bins[i];
- new_table->bins[i] = tbl;
- ptr = ptr->next;
- }
- }
- return new_table;
-}
-
-int
-st_delete(table, key, value)
- register st_table *table;
- register char **key;
- char **value;
-{
- int hash_val;
- st_table_entry *tmp;
- register st_table_entry *ptr;
-
- hash_val = do_hash(*key, table);
-
- ptr = table->bins[hash_val];
-
- if (ptr == nil(st_table_entry)) {
- if (value != nil(char*)) *value = nil(char);
- return 0;
- }
-
- if (EQUAL(table, *key, ptr->key)) {
- table->bins[hash_val] = ptr->next;
- table->num_entries--;
- if (value != nil(char*)) *value = ptr->record;
- *key = ptr->key;
- free((char*)ptr);
- return 1;
- }
-
- for(; ptr->next != nil(st_table_entry); ptr = ptr->next) {
- 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;
- *key = tmp->key;
- free((char*)tmp);
- return 1;
- }
- }
-
- return 0;
-}
-
-int
-st_delete_safe(table, key, value, never)
- register st_table *table;
- register char **key;
- char **value;
- char *never;
-{
- int hash_val;
- register st_table_entry *ptr;
-
- hash_val = do_hash(*key, table);
-
- ptr = table->bins[hash_val];
-
- if (ptr == nil(st_table_entry)) {
- if (value != nil(char*)) *value = nil(char);
- return 0;
- }
-
- if (EQUAL(table, *key, ptr->key)) {
- table->num_entries--;
- *key = ptr->key;
- if (value != nil(char*)) *value = ptr->record;
- ptr->key = ptr->record = never;
- return 1;
- }
-
- for(; ptr->next != nil(st_table_entry); ptr = ptr->next) {
- if (EQUAL(table, ptr->next->key, *key)) {
- table->num_entries--;
- *key = ptr->key;
- if (value != nil(char*)) *value = ptr->record;
- ptr->key = ptr->record = never;
- return 1;
- }
- }
-
- return 0;
-}
-
-void
-st_foreach(table, func, arg)
- st_table *table;
- enum st_retval (*func)();
- char *arg;
-{
- st_table_entry *ptr, *last, *tmp;
- enum st_retval retval;
- int i;
-
- for(i = 0; i < table->num_bins; i++) {
- last = nil(st_table_entry);
- for(ptr = table->bins[i]; ptr != nil(st_table_entry);) {
- retval = (*func)(ptr->key, ptr->record, arg);
- switch (retval) {
- case ST_CONTINUE:
- last = ptr;
- ptr = ptr->next;
- break;
- case ST_STOP:
- return;
- case ST_DELETE:
- tmp = ptr;
- if (last == nil(st_table_entry)) {
- table->bins[i] = ptr->next;
- } else {
- last->next = ptr->next;
- }
- ptr = ptr->next;
- free((char*)tmp);
- table->num_entries--;
- }
- }
- }
-}
-
-static int
-strhash(string, modulus)
- register char *string;
- int modulus;
-{
- register int val = 0;
- register int c;
-
- while ((c = *string++) != '\0') {
- val = val*997 + c;
- }
-
- 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;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-25 10:08:41 +0000