/* * Revision Control Information * * /projects/hsis/CVS/utilities/st/st.c,v * serdar * 1.1 * 1993/07/29 01:00:13 * */#include <stdio.h>#include "util.h"#include "st.h"#define ST_NUMCMP(x,y) ((x) != (y))#define ST_NUMHASH(x,size) (ABS((long)x)%(size))#define ST_PTRHASH(x,size) ((int)((unsigned long)(x)>>2)%size)#define EQUAL(func, x, y) \    ((((func) == st_numcmp) || ((func) == st_ptrcmp)) ?\      (ST_NUMCMP((x),(y)) == 0) : ((*func)((x), (y)) == 0))#define do_hash(key, table)\    ((table->hash == st_ptrhash) ? ST_PTRHASH((key),(table)->num_bins) :\     (table->hash == st_numhash) ? ST_NUMHASH((key), (table)->num_bins) :\     (*table->hash)((key), (table)->num_bins))static int rehash();int st_numhash(), st_ptrhash(), st_numcmp(), st_ptrcmp();st_table *st_init_table_with_params(compare, hash, size, density, grow_factor,			  reorder_flag)int (*compare)();int (*hash)();int size;int density;double grow_factor;int reorder_flag;{    int i;    st_table *new;    new = ALLOC(st_table, 1);    if (new == NIL(st_table)) {	return NIL(st_table);    }    new->compare = compare;    new->hash = hash;    new->num_entries = 0;    new->max_density = density;    new->grow_factor = grow_factor;    new->reorder_flag = reorder_flag;    if (size <= 0) {	size = 1;    }    new->num_bins = size;    new->bins = ALLOC(st_table_entry *, size);    if (new->bins == NIL(st_table_entry *)) {	FREE(new);	return NIL(st_table);    }    for(i = 0; i < size; i++) {	new->bins[i] = 0;    }    return new;}st_table *st_init_table(compare, hash)int (*compare)();int (*hash)();{    return st_init_table_with_params(compare, hash, ST_DEFAULT_INIT_TABLE_SIZE,				     ST_DEFAULT_MAX_DENSITY,				     ST_DEFAULT_GROW_FACTOR,				     ST_DEFAULT_REORDER_FLAG);}			    voidst_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(ptr);	    ptr = next;	}    }    FREE(table->bins);    FREE(table);}#define PTR_NOT_EQUAL(table, ptr, user_key)\(ptr != NIL(st_table_entry) && !EQUAL(table->compare, user_key, (ptr)->key))#define FIND_ENTRY(table, hash_val, key, ptr, last) \    (last) = &(table)->bins[hash_val];\    (ptr) = *(last);\    while (PTR_NOT_EQUAL((table), (ptr), (key))) {\	(last) = &(ptr)->next; (ptr) = *(last);\    }\    if ((ptr) != NIL(st_table_entry) && (table)->reorder_flag) {\	*(last) = (ptr)->next;\	(ptr)->next = (table)->bins[hash_val];\	(table)->bins[hash_val] = (ptr);\    }intst_lookup(table, key, value)st_table *table;register char *key;char **value;{    int hash_val;    register st_table_entry *ptr, **last;    hash_val = do_hash(key, table);    FIND_ENTRY(table, hash_val, key, ptr, last);        if (ptr == NIL(st_table_entry)) {	return 0;    } else {	if (value != NIL(char *)) {	    *value = ptr->record; 	}	return 1;    }}intst_lookup_int(table, key, value)st_table *table;register char *key;int *value;{    int hash_val;    register st_table_entry *ptr, **last;    hash_val = do_hash(key, table);    FIND_ENTRY(table, hash_val, key, ptr, last);        if (ptr == NIL(st_table_entry)) {	return 0;    } else {	if (value != NIL(int)) {	    *value = (long) ptr->record;	}	return 1;    }}/* This macro does not check if memory allocation fails. Use at you own risk */#define ADD_DIRECT(table, key, value, hash_val, new)\{\    if (table->num_entries/table->num_bins >= table->max_density) {\	rehash(table);\	hash_val = do_hash(key,table);\    }\    \    new = ALLOC(st_table_entry, 1);\    \    new->key = key;\    new->record = value;\    new->next = table->bins[hash_val];\    table->bins[hash_val] = new;\    table->num_entries++;\}intst_insert(table, key, value)register st_table *table;register char *key;char *value;{    int hash_val;    st_table_entry *new;    register st_table_entry *ptr, **last;    hash_val = do_hash(key, table);    FIND_ENTRY(table, hash_val, key, ptr, last);    if (ptr == NIL(st_table_entry)) {	if (table->num_entries/table->num_bins >= table->max_density) {	    if (rehash(table) == ST_OUT_OF_MEM) {		return ST_OUT_OF_MEM;	    }	    hash_val = do_hash(key, table);	}	new = ALLOC(st_table_entry, 1);	if (new == NIL(st_table_entry)) {	    return ST_OUT_OF_MEM;	}	new->key = key;	new->record = value;	new->next = table->bins[hash_val];	table->bins[hash_val] = new;	table->num_entries++;	return 0;    } else {	ptr->record = value;	return 1;    }}intst_add_direct(table, key, value)st_table *table;char *key;char *value;{    int hash_val;    st_table_entry *new;        hash_val = do_hash(key, table);    if (table->num_entries / table->num_bins >= table->max_density) {	if (rehash(table) == ST_OUT_OF_MEM) {	    return ST_OUT_OF_MEM;	}    }    hash_val = do_hash(key, table);    new = ALLOC(st_table_entry, 1);    if (new == NIL(st_table_entry)) {	return ST_OUT_OF_MEM;    }    new->key = key;    new->record = value;    new->next = table->bins[hash_val];    table->bins[hash_val] = new;    table->num_entries++;    return 1;}intst_find_or_add(table, key, slot)st_table *table;char *key;char ***slot;{    int hash_val;    st_table_entry *new, *ptr, **last;    hash_val = do_hash(key, table);    FIND_ENTRY(table, hash_val, key, ptr, last);    if (ptr == NIL(st_table_entry)) {	if (table->num_entries / table->num_bins >= table->max_density) {	    if (rehash(table) == ST_OUT_OF_MEM) {		return ST_OUT_OF_MEM;	    }	    hash_val = do_hash(key, table);	}	new = ALLOC(st_table_entry, 1);	if (new == NIL(st_table_entry)) {	    return ST_OUT_OF_MEM;	}	new->key = key;	new->record = (char *) 0;	new->next = table->bins[hash_val];	table->bins[hash_val] = new;	table->num_entries++;	if (slot != NIL(char **)) *slot = &new->record;	return 0;    } else {	if (slot != NIL(char **)) *slot = &ptr->record;	return 1;    }}intst_find(table, key, slot)st_table *table;char *key;char ***slot;{    int hash_val;    st_table_entry *ptr, **last;    hash_val = do_hash(key, table);    FIND_ENTRY(table, hash_val, key, ptr, last);    if (ptr == NIL(st_table_entry)) {	return 0;    } else {	if (slot != NIL(char **)) {	    *slot = &ptr->record;	}	return 1;    }}static intrehash(table)register st_table *table;{    register st_table_entry *ptr, *next, **old_bins;    int             i, old_num_bins, hash_val, old_num_entries;    /* save old values */    old_bins = table->bins;    old_num_bins = table->num_bins;    old_num_entries = table->num_entries;    /* rehash */    table->num_bins = table->grow_factor * old_num_bins;    if (table->num_bins % 2 == 0) {	table->num_bins += 1;    }    table->num_entries = 0;    table->bins = ALLOC(st_table_entry *, table->num_bins);    if (table->bins == NIL(st_table_entry *)) {	table->bins = old_bins;	table->num_bins = old_num_bins;	table->num_entries = old_num_entries;	return ST_OUT_OF_MEM;    }    /* initialize */    for (i = 0; i < table->num_bins; i++) {	table->bins[i] = 0;    }    /* copy data over */    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(old_bins);    return 1;}st_table *st_copy(old_table)st_table *old_table;{    st_table *new_table;    st_table_entry *ptr, *newptr, *next, *new;    int i, j, num_bins = old_table->num_bins;    new_table = ALLOC(st_table, 1);    if (new_table == NIL(st_table)) {	return NIL(st_table);    }        *new_table = *old_table;    new_table->bins = ALLOC(st_table_entry *, num_bins);    if (new_table->bins == NIL(st_table_entry *)) {	FREE(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)) {	    new = ALLOC(st_table_entry, 1);	    if (new == NIL(st_table_entry)) {		for (j = 0; j <= i; j++) {		    newptr = new_table->bins[j];		    while (newptr != NIL(st_table_entry)) {			next = newptr->next;			FREE(newptr);			newptr = next;		    }		}		FREE(new_table->bins);		FREE(new_table);		return NIL(st_table);	    }	    *new = *ptr;	    new->next = new_table->bins[i];	    new_table->bins[i] = new;	    ptr = ptr->next;	}    }    return new_table;}intst_delete(table, keyp, value)register st_table *table;register char **keyp;char **value;{    int hash_val;    char *key = *keyp;    register st_table_entry *ptr, **last;    hash_val = do_hash(key, table);    FIND_ENTRY(table, hash_val, key, ptr ,last);        if (ptr == NIL(st_table_entry)) {	return 0;    }    *last = ptr->next;    if (value != NIL(char *)) *value = ptr->record;    *keyp = ptr->key;    FREE(ptr);    table->num_entries--;    return 1;}intst_delete_int(table, keyp, value)register st_table *table;register long *keyp;char **value;{    int hash_val;    char *key = (char *) *keyp;    register st_table_entry *ptr, **last;    hash_val = do_hash(key, table);    FIND_ENTRY(table, hash_val, key, ptr ,last);    if (ptr == NIL(st_table_entry)) {        return 0;    }    *last = ptr->next;    if (value != NIL(char *)) *value = ptr->record;    *keyp = (long) ptr->key;    FREE(ptr);    table->num_entries--;    return 1;}intst_foreach(table, func, arg)st_table *table;enum st_retval (*func)();char *arg;{    st_table_entry *ptr, **last;    enum st_retval retval;    int i;    for(i = 0; i < table->num_bins; i++) {	last = &table->bins[i]; ptr = *last;	while (ptr != NIL(st_table_entry)) {	    retval = (*func)(ptr->key, ptr->record, arg);	    switch (retval) {	    case ST_CONTINUE:		last = &ptr->next; ptr = *last;		break;	    case ST_STOP:		return 0;	    case ST_DELETE:		*last = ptr->next;		table->num_entries--;	/* cstevens@ic */		FREE(ptr);		ptr = *last;	    }	}    }    return 1;}intst_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;}intst_numhash(x, size)char *x;int size;{    return ST_NUMHASH(x, size);}intst_ptrhash(x, size)char *x;int size;{    return ST_PTRHASH(x, size);}intst_numcmp(x, y)char *x;char *y;{    return ST_NUMCMP(x, y);}intst_ptrcmp(x, y)char *x;char *y;{    return ST_NUMCMP(x, y);}st_generator *st_init_gen(table)st_table *table;{    st_generator *gen;    gen = ALLOC(st_generator, 1);    if (gen == NIL(st_generator)) {	return NIL(st_generator);    }    gen->table = table;    gen->entry = NIL(st_table_entry);    gen->index = 0;    return gen;}int st_gen(gen, key_p, value_p)st_generator *gen;char **key_p;char **value_p;{    register int i;    if (gen->entry == NIL(st_table_entry)) {	/* try to find next entry */	for(i = gen->index; i < gen->table->num_bins; i++) {	    if (gen->table->bins[i] != NIL(st_table_entry)) {		gen->index = i+1;		gen->entry = gen->table->bins[i];		break;	    }	}	if (gen->entry == NIL(st_table_entry)) {	    return 0;		/* that's all folks ! */	}    }    *key_p = gen->entry->key;    if (value_p != 0) {	*value_p = gen->entry->record;    }    gen->entry = gen->entry->next;    return 1;}int st_gen_int(gen, key_p, value_p)st_generator *gen;char **key_p;long *value_p;{    register int i;    if (gen->entry == NIL(st_table_entry)) {	/* try to find next entry */	for(i = gen->index; i < gen->table->num_bins; i++) {	    if (gen->table->bins[i] != NIL(st_table_entry)) {		gen->index = i+1;		gen->entry = gen->table->bins[i];		break;	    }	}	if (gen->entry == NIL(st_table_entry)) {	    return 0;		/* that's all folks ! */	}    }    *key_p = gen->entry->key;    if (value_p != NIL(long)) {   	*value_p = (long) gen->entry->record;    }    gen->entry = gen->entry->next;    return 1;}voidst_free_gen(gen)st_generator *gen;{    FREE(gen);}