#ifndef lint
static char *rcsid = "$Header: /tmp_mnt/vida/disks/disk5/Users/terry/r/gassy/RCS/hash.c,v 1.10 1992/10/09 06:43:50 terry Exp terry $";
#endif

#include "types.h"

#if defined(APP_HASHING)

#include <string.h>
#include <sys/types.h>

#define HASH_NULL    (HASH_TABLE *)0
#define NODE_NULL    (HASH_NODE *)0
#define GENERIC_NULL (VOID *)0

#define HASH_SZ 97


static INT hash();
static HASH_NODE *list_find();


/*
 * hash_create()
 *
 * Malloc room for a new hash table and then room for its
 * bucket pointers. Then set all the buckets to
 * point to 0. Return the address of the new table.
 */
HASH_TABLE *
hash_create(size)
INT size;
{
    register INT i;  
    HASH_TABLE *new = (HASH_TABLE *)Malloc(sizeof(HASH_TABLE));

    if (!new || size < 0){
	return HASH_NULL;
    }
    
    if (size == 0){
	size = HASH_SZ;
    }
    
    if (!(new->buckets = (HASH_NODE **)Malloc(size * sizeof(HASH_NODE *)))){
	return HASH_NULL;
    }

    for (i = 0; i < size; i++){
	new->buckets[i] = NODE_NULL;
    } 
    new->size = size;
    
    return new;
}


/*
 * list_find()
 *
 * Find the key in the linked list pointed to by head.
 */
static HASH_NODE *
list_find(key, head)
STRING key;
HASH_NODE *head;
{
    while (head){
	if (!strcmp(head->key, key)){
	    return head;
	}
	head = head->next;
    }
    return NODE_NULL;
}


/*
 * hash()
 *
 * Compute the hash value for the given key.
 */
static INT
hash(size, key)
INT size;
register STRING key;
{
    register INT h = 0x0;

    while (*key){
	h = (h << 1) ^ (h ^ *key);
	key++;
    }	

    h %= size;
    return h < 0 ? -1 * h : h;
}

/*
 * hash_destroy()
 *
 * Find the key and (if it's there) remove it entirely.
 * The function (*nukefunc)() is in charge of disposing
 * of the storage help by the data associated with the node.
 */
void 
hash_destroy(table, key, nukefunc)
HASH_TABLE *table;
STRING key;
void (*nukefunc)();
{
    INT bucket = hash(table->size, key);
    HASH_NODE *found = table->buckets[bucket];
    HASH_NODE *to_free = NODE_NULL;
    
    if (!found){
	return;
    }
    
    if (!strcmp(found->key, key)){
	/*
	 * It was the head of the list.
	 */
	table->buckets[bucket] = found->next;
	to_free = found;
    }
    else{
	/*
	 * Walk the list, looking one ahead.
	 */
	while (found->next){
	    if (!strcmp(found->next->key, key)){
		to_free = found->next;
		found->next = found->next->next;
		break;
	    }
	    found = found->next;
	}
	
	if (!to_free){
	    return;
	}
    }
    
    if (nukefunc){
	(*nukefunc)(to_free->data);
    }
    free(to_free);
    return;
}


/*
 * hash_search()
 *
 * Search the table for the given key. Then:
 *
 * 1) If you find it and there is no replacement function, just 
 *    return what you found. (This is a simple search). 
 * 2) If you find it and there is a replacement function, run
 *    the function on the data you found, and replace the old
 *    data with whatever is passed in datum. Return 0.
 * 3) If you don't find it and there is some datum, insert a
 *    new item into the table. Insertions go at the front of
 *    the bucket. Return 0.
 * 4) Otherwise just return 0.
 *
 */
VOID *
hash_search(table, key, datum, replace_func)
HASH_TABLE *table;
STRING key;
VOID *datum;
void (*replace_func)(); 
{
    INT bucket = hash(table->size, key);
    HASH_NODE *found = list_find(key, table->buckets[bucket]);

    if (found){
	if (!replace_func){
	    return found->data;
	}
	else{
	    (*replace_func)(found->data);
	    found->data = datum;
	}
    }
    else{
	if (datum){
	    
	    static INT assign_key();
	    
	    HASH_NODE *new = (HASH_NODE *)Malloc(sizeof(HASH_NODE));
	    
	    if (!new || !assign_key(key, new)){
		return GENERIC_NULL;
	    }
	    new->data = datum;
	    new->next = table->buckets[bucket];
	    table->buckets[bucket] = new;
	}
    }
    return GENERIC_NULL;
}


/*
 * assign_key()
 *
 * Set the key value of a node to be 'key'. Get some space from 
 * Malloc and copy it in etc. Return 1 if all is well, 0 otherwise.
 */
static INT
assign_key(key, node)
STRING key;
HASH_NODE *node;
{
    if (!node || !key){
	return 0;
    }
    
    if (!(node->key = Malloc(strlen(key) + 1))){
	return 0;
    }
    
    node->key[0] = '\0';
    strcat(node->key, key);
    return 1;
}

/*
 * hash_traverse()
 *
 * Traverse the hash table and run the function func on the
 * data found at each node and the argument we're passed for it.
 */
void
hash_traverse(table, func, arg)
HASH_TABLE *table;
INT (*func)();
VOID *arg;
{
    register INT i; 
    register INT size = table->size;

    if (!func){
	return;
    }
    
    for (i = 0; i < size; i++){
	HASH_NODE *n = table->buckets[i];
	while (n){
	    if ((*func)(n->data, arg) == 0){
		return;
	    }
	    n = n->next;
	}
    } 
    
    return;
}

/*
 * hash_purge()
 *
 * Run through the entire hash table. Call purge_func
 * on the data found at each node, and then free the node.
 * Set all the bucket pointers to 0.
 */
void
hash_purge(table, purge_func)
HASH_TABLE *table;
void (*purge_func)();
{
    register INT i; 
    register INT size = table->size;
    
    for (i = 0; i < size; i++){
	HASH_NODE *n = table->buckets[i];
	if (n){
	    do {
		HASH_NODE *to_free = n;
		if (purge_func){
		    (*purge_func)(n->data);
		}
		n = n->next;
		free(to_free);
	    } while (n);
	    
	    table->buckets[i] = NODE_NULL;
	}
    } 
}

#define min(a, b) (a) < (b) ? (a) : (b)

/*
 * hash_stats()
 *
 * Print statistics about the current table allocation to stdout.
 */
void
hash_stats(fp, table, verbose)
FILE *fp;
HASH_TABLE *table;
BOOLEAN verbose;
{
    register INT i; 
    INT total_elements = 0;
    INT non_empty_buckets = 0;
    INT max_count = 0;
    INT max_repeats = 0;
    INT *counts;
    INT size = table->size;
    
    counts = (INT *)Malloc(size * sizeof(INT));
    
    for (i = 0; i < size; i++){
	INT x = 0;
	HASH_NODE *n = table->buckets[i];
	counts[i] = 0;
	while (n){
	    if (!x){
		x = 1;
		non_empty_buckets++;
		if (verbose == TRUE){
		    fprintf(fp, "bucket %2d: ", i);
		}
	    }
	    if (verbose == TRUE){
		STRING tmp = n->key;
		
		while (*tmp){
		    fprintf(fp, "%d ", (INT)*tmp);
		    tmp++;
		}

		/* fprintf(fp, " %s", n->key); */
	    }
	    counts[i]++;
	    n = n->next;
	}
	
	total_elements += counts[i];
	if (counts[i] > max_count){
	    max_count = counts[i];
	    max_repeats = 1;
	}
	else if (counts[i] == max_count){
	    max_repeats++;
	}
	
	if (counts[i] && verbose == TRUE){
	    fprintf(fp, " (%d)\n", counts[i]);
	}
    } 
    
    fprintf(fp, "\n");
    fprintf(fp, "%d element%s in storage.\n", total_elements, total_elements == 1 ? "" : "s");
    
    if (total_elements){
	fprintf(fp, "%d of %d (%.2f%%) buckets are in use\n", non_empty_buckets, size, 
	       (double)100 * (double)non_empty_buckets / (double)(size));
	fprintf(fp, "the maximum number of elements in a bucket is %d (%d times)\n", max_count, max_repeats);
	fprintf(fp, "average per bucket is %f\n", (double)total_elements / (double)non_empty_buckets);
	fprintf(fp, "optimal would be %f\n", (double)total_elements / (double)(min(size, total_elements)));
    }
    return;
}

#endif