#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define START_LOC	    19
#define HASH_TABLE_SIZE	    32768

struct names {
    char *name;
    int count;
};

struct hash_entry {
    struct names *name_ptr;
    struct hash_entry *next;
};

struct hash_entry hash_table[HASH_TABLE_SIZE];

/* Hash table instrumentation */
#define MAXCHAIN	    200
int chain_distribution[MAXCHAIN+1];

unsigned long getblockname(char *);

main(int argc,  char *argv[])
{
    FILE *filep;
    char line[256];
    char *string;
    struct hash_entry *hp;
    struct names *namep;
    int i;
    long value;
   
    
    if (argc != 2) {
        fprintf(stderr, "usage: %s file\n",  argv[0]);
	exit(1);
    }
    
    filep = fopen(argv[1], "r");
    if (filep == NULL) {
	fprintf(stderr, "cannot open %s\n", argv[1]);
	exit(2);
    }
    
    while (1) {
	if (fgets(line, 256, filep) == NULL)
	    break;
	
	/* find the sting after 3 numbers */
	string = line;
	for (i = 0; i < 3; i++) {
	    while (isspace(*string))
		string++;
		
	    if (!*string)
		break;
		
	    if (!isdigit(*string))
		break;
		
	    while (isdigit(*string))
		string++;
		
	    if (!*string)
		break;
	}	
	while (isspace(*string))
	    string++;
	    
	if (!*string || i != 3)
	    continue;

	value = getblockname(string);
	
	/* find or place string in hash table */
	hp = &hash_table[value];
	if (hp->name_ptr == 0) {
	    namep = (struct names *)malloc(sizeof(struct names));
	    namep->name = strdup(string);
	    namep->count = 1;
	    hp->name_ptr = namep;
	} else {
	    /* walk down the chain looking for a match */
	    while (hp != 0) {
		if (strcmp(string, hp->name_ptr->name) == 0) {
		    hp->name_ptr->count++;
		    break;
		} else {
		    hp = hp->next;
		}
	    }
	    if (hp == NULL) {
		/* did not find match in chain */
		namep = (struct names *)malloc(sizeof(struct names));
		namep->name = strdup(string);
		namep->count = 1;
		
		hp = (struct hash_entry *)malloc(sizeof(struct hash_entry));
		hp->name_ptr = hash_table[value].name_ptr;
		hp->next = hash_table[value].next;
		hash_table[value].name_ptr = namep;
		hash_table[value].next = hp;
	    }
	}
    }
    
    /* now print out the list */
    
    for (i = 0; i < HASH_TABLE_SIZE; i++) {
	int chain;
	
	chain = 0;
	hp = &hash_table[i];
	while (hp) {
	    namep = hp->name_ptr;
	    if (namep) {
		printf("%5d  %s\n", namep->count, namep->name);
		chain++;
	    }
	    hp = hp->next;
	}

	if (chain >= MAXCHAIN) {
	    chain = MAXCHAIN;
	}
	chain_distribution[chain]++;
    }
    
    for (i=0; i < MAXCHAIN+1; i++) {
	if (chain_distribution[i])
	   fprintf(stderr, "chain_distribution[%d] is %d\n", i, chain_distribution[i]);
    }
}

/*
 * retrive the block name from the entire netname.  Put a 0 (ie
 * end the string) at the '.'
 * Also calculate the hash value
 */
unsigned long
getblockname(char *s)
{
    unsigned long value;
    unsigned char c;
    
    value = 0;
    
    while (1) {
	c = (unsigned)*s;
	if (c == '.' || c == '\n' || c == 0) {
	    *s = 0;
	    return (value % 32768);
	}
	value <<= 1;
	value += c;
	s++;
    }
}